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.$]$Given a set of Boolean variables, $A=\{a_1,a_2,$dots,$a_n\},$ a logical sentence, $S,$ is in

Conjunctive Normal Form $($CNF$)$ if it is a set of conjuncts, $C_i,$ as follows:

$S=C_1^{{?}^{?}}{C}_2^{{?}^{?}}dot{s}^{{?}^{?}}{C}_m$

where $m1$ and each conjunct, $C_i$ is a disjunction:

$C_i=D_{i,1}vv{D}_{i,2}vvdotsvv{D}_{i,k_i}$

where $k_{i}1$ and each disjunct, $D_{i,j},$ is a literal $($either an atom or the negation of an atom$)$:

$D_{i,j}=a_{p}ornot{a}_p$

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: