Given a set of Boolean variables, A $=\{$a$1,$ a$2,...,$ an$\},$ a logical sentence, S$,$ is in

Conjunctive Normal Form $($CNF$)$ if it is a set of conjuncts, Ci

$,$ as follows:

S $=$ C$1$ C$2...$ Cm

where m $>=1$ and each conjunct, Ci

is a disjunction:

Ci $=$ Di$,1$ Di$,2...$ Di$,$ki

where ki $>=1$ and each disjunct, Di$,$j $,$ is a literal $($either an atom or the negation of an atom$)$:

Di$,$j $=$ ap or $$ap

Consider the case where A $=\{$a$1,$ a$2\}.$ Provide the rationale for your answers and proofs.

$2$a$.$ How many literals can be formed? Give them.

$2$b$.$ State how many well$-$formed disjunctions can be formed given the following constraints

on each disjunction:

$$ must be distinct and syntactically correct.

Explain your reasoning in detail, including assumptions, as to how you determined your

answer.

$2$c$.$ State how many well$-$formed disjunctions can be formed given the following constraints

on each disjunction:

$$ must be distinct and syntactically correct,

$$ no commutative similar disjunctions are allowed.

Explain your reasoning in detail, including assumptions, as to how you determined your

answer.

$2$d$.$ State how many well$-$formed disjunctions can be formed given the following constraints

on each disjunction:

$2$

$$ must be distinct and syntactically correct,

$$ no commutative similar disjunctions are allowed,

$$ the appearance of an atom and its negation is not allowed.

Explain your reasoning in detail, including assumptions, as to how you determined your

answer.

$2$e$.$ State how many well$-$formed disjunctions can be formed given the following constraints

on each disjunction:

$$ must be distinct and syntactically correct,

$$ no commutative similar disjunctions are allowed,

$$ the appearance of an atom and its negation is not allowed,

$$ no literal may appear more than once.

Give this set explicitly and explain your reasoning in detail, including assumptions, as to

how you determined your answer.

$2$f$.$ How many distinct CNF sentences can be formed from the disjunctions in $2$e $($assume

similar constraints apply to conjunctions as disjunctions$)?$ Explain your reasoning. $[$Note

that each CNF sentence can be considered a specific subset of the power set of disjunctions.$]$