Question

Consider the following propositional formula:

(((A ^ B) -> C) ^ ((A ^ C) -> D)) -> ((A ^ B) -> D)

Perform the following tasks for this formula:

Convert this formula into CNF form and write a numbered list of all clauses obtained from this formula.

Answer 1

Given Propositional formula

(((A B) C) ((A C) D))    ((A B)   D)

((¬(A B) V C) (¬(A C) V D))    (¬(A B) V  D)  { Law of Implies (PQ) = ¬PVQ }

¬((¬(A B) V C) (¬(A C) V D)) V (¬(A B) V  D)  { Law of Implies (PQ) = ¬PVQ }

(¬(¬(A B) V C) V ¬(¬(A C) V D)) V (¬(A B) V  D)   {By De Morgan's law ¬ (P Q) = ¬P V ¬Q }

[¬(¬(A B))   ¬C) V (¬(¬(A C)) ¬D)]   V (¬(A B) V  D)   {By De Morgan's law ¬ (P V Q) = ¬P ¬Q }

[((A B)   ¬C) V ((A C)   ¬D)] V (¬(A B) V  D)   {By De Morgan's law ¬ (¬P ) = P }

[(A B   ¬C V (A C) ¬D] V ((¬A V ¬B) V  D)   {By De Morgan's law ¬ (P Q) = ¬P V ¬Q }

[A B   (A C) V ¬C ¬D] V (¬A V ¬B V  D) {Commutative law (P V Q) = (Q V P)}

[A A   B (C V ¬C) ¬D] V (¬A V ¬B V  D)   {Associative law (P V Q) V R = P V (Q V R)}

[(A A)   B (C V ¬C) ¬D] V (¬A V ¬B V  D)   {Associative law (P Q) R = P (Q R)}

[(A)   B (T) ¬D] V (¬A V ¬B V  D)  { we know that P P = P &   P V ¬P = T } }

[A   B (T ¬D)] V (¬A V ¬B V  D)  {Associative law (P Q) R = P (Q R)}

[A   B (¬D)] V (¬A V ¬B V  D)  { we know that T ¬P = ¬P }

[A   B (¬D)] V (D V  ¬A V ¬B)  {Commutative law (P V Q) = (Q V P)}

A   B (¬D V D) V  ¬A V ¬B  {Associative law (P V Q) V R = P V (Q V R)}

A   B (T) V  ¬A V ¬B   { we know that P V ¬P = T } }

A   (B T) V  ¬A V ¬B  {Associative law (P Q) R = P (Q R)}

A   (B) V  ¬A V ¬B  { we know that P T = P }

A   (B V ¬A V ¬B) {Associative law (P V Q) V R = P V (Q V R)}

A   (B V ¬A V ¬B)

Which is Required Conjunctive Normal Form(CNF)

Given Conjunctive Normal Form(CNF)

A   (B V ¬A V ¬B)

A   (¬A V B V ¬B)  {Commutative law (P V Q) = (Q V P)}

(A   ¬A) V (B V ¬B)    {Associative law (P Q) R = P (Q R)}

(F) V (T) { we know that P ¬P = F &   P V ¬P = T } }

(F V T)  

(T) { we know that F V T = T }

T

From the above the numbered list of all clauses obtained from this formula is

F (A, B, C, D) = ​ m (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)