0
$\begingroup$

Hi hope you're having a good day. I'm working through some work about CNF and DNF and one of the questions was write the answer from a truth table in the CNF, then DNF from the table.

So I wrote the CNF from the '1's in the final column, but it was wrong. CNF was supposed for the '0's and DNF for the '1's. I really do not understand the reasoning behind this I can't find much information on it either.

I'm really stuck and I have an exam on this tomorrow. I don't unerstand why CNF uses the False values and DNF uses the truths, and what I(P) is.

Below is the correct completed truth table and everything from answer sheet.

Consider the formula (P∨ ¬R)→ ¬(¬Q∨R)

(i) Build a conjunctive normal form for this formula from its truth table

(ii) Transform this formula in a logical equivalent disjunctive normal form(DNF) using the rewrite rules.

P | Q | R | (P v ¬R) | ¬(¬Q v R) |  (P v ¬R) → ¬(¬Q v R)
1 | 1 | 1 |    1     |     0     |           0
1 | 1 | 0 |    1     |     1     |           1      
1 | 0 | 1 |    1     |     0     |           0
1 | 0 | 0 |    1     |     0     |           0
0 | 1 | 1 |    0     |     1     |           0
0 | 1 | 0 |    1     |     1     |           1
0 | 0 | 1 |    0     |     1     |           0
0 | 0 | 0 |    1     |     0     |           0
  1. A disjunction of three literals is created for each line (for each interpretation of propositional variables) with a false(i.e. 0) value of the formula.For each propositional variable P, the literal P is added to the disjunction if I(P) = 0, and ¬P is added to the disjunction if I(P) = 1. Such disjunction is false for the interpretation given by this line. The corresponding CNF is :

(¬P ∨¬Q ∨¬R) ∧ (¬P ∨ Q ∨¬R) ∧ (¬P ∨ Q ∨ R) ∧ (P ∨ Q ∨ R)

Here each disjunction has exactly 3 literals, one for each variables appearingin the formula. Such CNFs are called full CNFs.

  1. A conjunction of three literals is created for each line (for each interpreta-tion of propositional variables) with a true (i.e., 1) valueof the formula. Foreach propositional variable P, the literal ¬P is added to the conjunction ifI(P) = 0, andPis added to the conjunction is I(P) = 1. Such conjunctionis true for the interpretation given by this line. The corresponding DNF is :

(P∧Q∧ ¬R)∨(¬P∧Q∧R)∨(¬P∧Q∧ ¬R)∨(¬P∧ ¬Q∧R)

Here each conjunction has exactly 3 literals, one for each variables appearing in the formula. Such DNFs are called full DNFs.

$\endgroup$
0
$\begingroup$

Okay, let me see if I can walk you through this. First of all, I(P) just means that I is a function that tells you if the literal propositional variable P is true or false, and returns 1 or 0 accordingly. (Maybe the I stands for interpretation? Check your text.)

DNF is the more straightforward one intuitively. It's describing the truth table where you want to OR together a bunch of conjunctions of propositional variables (or their negations). It's exactly how you would describe the truth table to someone else. In the table you listed, you would say that the final statement is true iff P is true and Q is true and R is false OR P is false and Q is true and R is false. Symbolically, you would write that as $(P\wedge Q\wedge\neg R)\vee(\neg P\wedge Q\wedge\neg R) $.

CNF is the opposite, where you're ANDing together a bunch of "rules" instead of ORing together a bunch of "cases". The general way of making a CNF expression for a formula $A$ is to make the DNF of $\neg A$ and then use the De Morgan laws to propogate that negation down to the literals, which switches all of the conjunctions to disjunctions and vice-versa.

It's been a while, so I might be missing a detail or two, but hopefully that gives you some intuition about how and why you'd want to do this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.