A formula is said to be in conjunctive normal form (CNF) if it is a conjunction of Clauses. A Clause is a disjunction of atoms or their negations. Informally, a formula is in conjunctive normal form if it can be written as clauses connected with the and operator, and a formula is a clause if the atoms and their negations are connected using or operations. For example:

a b, a, , and a b c a are all examples of clauses whereas a, (a b), a b are not examples of clauses.

Any clause or conjunction of clauses are said to be in conjunctive normal form. So a b, (a b) (a b), a b c are all in conjunctve normal form but the formula a b c is not. This last formula is not in conjunctive normal form as takes precedence over , hence we see (a b) c is not a conjunction of clauses.

Applying distributivity to (ab)c we get the logically equivalent formula, (a b) (a c) which is in conjunctive normal form (it is the conjunction of two clauses).

The only operators that can be used in a formula in conjunctive normal form are and, or, and not. Every formula has a logically equivalent formula in conjunctive normal form.

answer a,b,c and d

For each of the below formulas, write a logically equivalent formula in con- junctive normal form. Simplify each clause in your final answer. For example the formula (a V - V-b) ^ (CV dV-d) should be simplified to (a V -b), since (a V - V-b) = (a V -b) by the absorbtion law, c V dV-d = CVT = T by excluded middle and domination laws, and finally (a V-b) AT = a V-b, by the identity law. a) a V (b Acid) b) -(-a VbVc) c) (a 1-6) V (cAd) d) -a V (b^c) V-(c V a)