Friday, September 9, 2011

Propositional arguments and normal forms

(Propositional logic continued)

1Propositional arguments continued¶

1.1Relating 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.

2Disjuncts and conjuncts¶

Disjunctive normal form: conjunctive clauses¹ joined by $\lor$ ($\Phi_1 \lor \Phi_2 \lor ... \lor \Phi_m$)²
Conjunctive normal form: disjunctive clauses³ joined by $\land$ ($\Phi_1 \land \Phi_2 \land ... \land \Phi_m$)²

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.1From 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:

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:

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.2Simplifying 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.3From 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⁴ 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.4The 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.