Task 2

Question

Suppose that some knowledge base contains various propositional-logic sentences that utilize symbols A, B, C, D (connected with various connectives). There are only two cases when the knowledge base is false:

• First case: when A is true, B is false, C is true, D is false.
• Second case: when A is false, B is false, C is true, D is true.

In all other cases, the knowledge base is true.
Write a conjunctive normal form (CNF) for the knowledge base.

Answer

To write a conjunctive normal form (CNF) for the given knowledge base, we first consider the conditions under which the knowledge base is false and then negate these conditions.

The knowledge base is false in two cases:

1. A is true, B is false, C is true, D is false.
2. A is false, B is false, C is true, D is true.

We can represent these two cases with the following propositional logic expressions:

1. $A\wedge \mathrm{\neg }B\wedge C\wedge \mathrm{\neg }D$
2. $(\mathrm{\neg }A\wedge \mathrm{\neg }B\wedge C\wedge D)$

Now, to convert this into a CNF, we will use the negation of these expressions (since these are the cases where the knowledge base is false, and we want to represent when it is true). We then use De Morgan's Laws and distribute the negation across the conjunctions:

1. Negation of the first case: $\mathrm{\neg }(A\wedge \mathrm{\neg }B\wedge C\wedge \mathrm{\neg }D)$
   Which is equivalent to:
   $\mathrm{\neg }A\vee B\vee \mathrm{\neg }C\vee D$

2. Negation of the second case: $\mathrm{\neg }(\mathrm{\neg }A\wedge \mathrm{\neg }B\wedge C\wedge D)$ Which is equivalent to:
   $A\vee B\vee \mathrm{\neg }C\vee \mathrm{\neg }D$

Finally, the CNF for the knowledge base (representing when the knowledge base is true) is the conjunction of these two expressions:

$(\mathrm{\neg }A\vee B\vee \mathrm{\neg }C\vee D)\wedge (A\vee B\vee \mathrm{\neg }C\vee \mathrm{\neg }D)$

This expression captures all the conditions under which the knowledge base is true, except for the two specific false cases.