**Maintainer:**admin

(Propositional logic continued)

*1*Propositional arguments continued¶

*1.1*Relating consistency and validity¶

A propositional argument is **valid** if the conclusion is true *every* time the premises are all true.

It is **consistent** if there *is* such a valuation $V$.

Proposition: $\Phi_1, ... \Phi_n \vdash \Psi$ is valid $\iff$ $\{ \Phi_1, ... \Phi_n, \neg \Psi \}$ is inconsistent.

Proof: Suppose the left side is true. Then, for any valuation $V$, the left side 9A) implies the right side (B) if $V(\Phi_1) = ... = V(\Phi_n) = \top$. So $V(\neg \Psi) = \bot$. So yeah, inconsistent.

Now show that B implies A. Suppose B and $V(\Phi_1) = ... = V(\Phi_n) = \top$. By B, $V(\neg \Phi) = \bot$ so $V(\Phi) = \top$. So A is correct, and so $A \iff B$. No idea what this proof is doing.

*2*Disjuncts and conjuncts¶

Disjunctive normal form: conjunctive clauses^{1}joined by $\lor$ ($\Phi_1 \lor \Phi_2 \lor ... \lor \Phi_m$)^{2}

Conjunctive normal form: disjunctive clauses^{3}joined by $\land$ ($\Phi_1 \land \Phi_2 \land ... \land \Phi_m$)^{2}

A basic disjunct is sort of the opposite of what you'd expect - $\alpha_1 \land \alpha_2 \land \alpha_k$ where $\alpha$ is either $\top$ or $\bot$ or $p$ or $\neg p$ for some variable $p$^{confirm}. A basic conjunct is the above with the $\land$s replaced with $\lor$s.

*2.1*From truth tables to disjunctive normal forms¶

Given the following truth table for an unknown formula in conjunctive normal form^{confirm} involving the variables $(p, q, r)$, it is possible to write out the formula in both disjunctive and conjunctive normal form:

$p$ | $q$ | $r$ | $\Phi(p, q, r)$ |
---|---|---|---|

$\top$ | $\top$ | $\top$ | $\top$ |

$\top$ | $\top$ | $\bot$ | $\bot$ |

$\top$ | $\bot$ | $\top$ | $\top$ |

$\top$ | $\bot$ | $\bot$ | $\top$ |

$\bot$ | $\top$ | $\top$ | $\top$ |

$\bot$ | $\top$ | $\bot$ | $\bot$ |

$\bot$ | $\bot$ | $\top$ | $\top$ |

$\bot$ | $\bot$ | $\bot$ | $\bot$ |

To find the disjunctive normal form, first identify the rows of the truth table that come out $\top$. For each row, find a basic disjunct that represents it. Then, join them together with $\lor$s. I can't really articulate it, so here's an example using the truth table above:

$$(p \land q \land r) \lor (p \land \neg q \land r) \lor (p \land \neg q \land \neg r) \lor (\neg p \land q \land r) \lor (\neg p \land \neg q \land r)$$

Another example:

$p$ | $q$ | $r$ | $\Phi(p, q, r)$ |
---|---|---|---|

$\top$ | $\top$ | $\top$ | $\bot$ |

$\top$ | $\top$ | $\bot$ | $\top$ |

$\top$ | $\bot$ | $\top$ | $\bot$ |

$\top$ | $\bot$ | $\bot$ | $\top$ |

$\bot$ | $\top$ | $\top$ | $\top$ |

$\bot$ | $\top$ | $\bot$ | $\bot$ |

$\bot$ | $\bot$ | $\top$ | $\bot$ |

$\bot$ | $\bot$ | $\bot$ | $\bot$ |

In this case, there are three rows that come out $\top$ and so there are three basic disjuncts, resulting in the following formula in d.n.f:

$$(p \land q \land \neg r) \lor (p \land \neg q \land \neg r) \lor (\neg p \land q \land r)$$

*2.2*Simplifying formulas in normal form¶

We can simplify formulas in disjunctive normal form by finding equivalent formulas. For example, we can simplify $(p \land q \land \neg r) \lor (p \land \neg q \land \neg r)$ as $(p \land \neg r)$, which is a basic disjunct and which has the same truth table (the $q$s in the expanded form have merely been dropped, since we have both $q$ and $\neg q$). I don't think we can simplify this example any more, so let's return to the first example:

$$[ (p \land \neg q \land r) \lor (p \land q \land r) ] \lor (p \land \neg q \land r) \lor (p \land \neg q \land \neg r) \lor (\neg p \land q \land r) \lor (\neg p \land \neg q \land r)$$

$$\therefore (p \land r) \lor (\neg p \land r) \lor (p \land \neg q)$$

$$\therefore r \lor (p \land \neg q)$$

(magic)

*2.3*From disjunctive to conjunctive¶

Now let's turn the above into conjunctive normal form. We can use the distribute law for this, as follows:

$$r \lor (p \land \neg q) \iff (r \lor p) \land (r \lor \neg q)$$

which is in conjunctive normal form.

Now, consider $(p \land q \land \neg r) \lor (\neg p \land q \land \neg r) \lor (\neg p \land \neg q \land \neg r)$ which is equivalent to $(\neg p \land \neg r) \lor (q \land \neg r)$ which is equivalent to the negation of the first example^{confirm}.

Using the de Morgan laws^{4} we see that this is equivalent to $\neg (p \land q \land \neg r) \land \neg (\neg p \land q \land \neg r) \land \neg (\neg p \land \neg q \land \neg r)$ (de Morgan laws used twice). This was found by applying the de Morgan laws to the ones that come out $\bot$ in the truth table, and resulted in a conjunctive normal form, but the other way, with the distributive law, resulted in a shorter one. There's probably a simpler way using the truth table but I don't remember it right now^{later?}.

*2.4*The universality of disjunctive and conjunctive normal forms¶

So we reach the following conclusion: any conceivable formula in any number of variables is equivalent to a formula in cnf as well as to a (different) formula in dnf. In particular, any formula is equivalent to a formula using only the connectives $\land, \lor$ and $\neg$. In fact, we could even disperse with one of the binary connectives if we wanted, using the de Morgan laws.

This brings us to a more general conclusion. If any formula is equivalent to a formula using only $\land$ and $\neg$, then the set $\{ \land, \neg\}$ is functionally complete. We can even get rid of the propositional constants of $\top$ and $\bot$ if we liked, replacing them with $p \lor \neg p$ and $p \land \neg p$, respectively. But the set $\{ \land, \lor \}$ is *not* functionally complete, because no matter how many $\land$s and $\lor$s you use, if $V(p) = \top$, the whole thing comes out $\top$, no matter what.

But do we need two connectives to make a functionally complete set? Isn't there a connective that is functionally complete just by itself? In fact, there are several. One particular such connective is discussed in detail next lecture.