1. Transformations using Logical Equivalence

Transformations using Logical Equivalence

Fundamental Equivalences

$$\begin{array}{rlrl}P\vee P& \equiv P& & \text{idempotency}\\ P\wedge P& \equiv P& & \text{idempotency}\\ P\vee Q& \equiv Q\vee P& & \text{commutativity}\\ P\wedge Q& \equiv Q\wedge P& & \text{commutativity}\\ P\vee (Q\vee R)& \equiv (P\vee Q)\vee R& & \text{associativity}\\ P\wedge (Q\wedge R)& \equiv (P\wedge Q)\wedge R& & \text{associativity}\\ P\wedge (Q\vee R)& \equiv (P\wedge Q)\vee (P\wedge R)& & \text{distributivity}\\ P\vee (Q\wedge R)& \equiv (P\vee Q)\wedge (P\vee R)& & \text{distributivity}\\ \neg (P\wedge Q)& \equiv (\neg P\vee \neg Q)& & \text{De Morgan’s law}\\ \neg (P\vee Q)& \equiv (\neg P\wedge \neg Q)& & \text{De Morgan’s law}\\ P\vee \neg P& \equiv \text{1}& & \text{excluded middle}\\ P\wedge \neg P& \equiv \text{0}& & \\ \neg \neg P& \equiv P& & \\ P\vee 1& \equiv 1& & \\ P\wedge 1& \equiv P& & \\ P\vee 0& \equiv P& & \\ P\wedge 0& \equiv 0& & \\ P\to Q& \equiv \neg P\vee Q& & \\ P\to Q& \equiv \neg Q\to \neg P& & \text{contraposition}\\ \neg (P\to Q)& \equiv P\wedge \neg Q& & \\ 1⟺P& \equiv P& & \\ 0⟺P& \equiv \neg P& & \\ 1\to P& \equiv P& & \\ P\to 1& \equiv 1& & \\ 0\to P& \equiv 1& & \\ P\to 0& \equiv \neg P& & \\ P⟺P& \equiv 1& & \\ p⟺\neg Q& \equiv \neg (P⟺Q)& & \\ P\vee (P\wedge Q)& \equiv P& & \text{absorption}\\ P\wedge (P\vee Q)& \equiv P& & \end{array}$$Link to original

2. Disjunctive Normal Form

Disjunctive Normal Form

Literal

A literal is a propositional symbol or the negation of a propositional symbol.

For example, $p$ or $\neg p$ meanwhile $\neg \neg p$ or $p\vee q$ are not since literals may have at most one logical connective and it must be a negation.

Link to original

Disjunctive Normal Form

Disjunctive Normal Form (DNF) is when a formula: ?

• contains no connectives other than conjunction, disjunction and negation.
• only applies negation to propositional symbols (within literals)
• no disjunction appears in a sub-formula of a formula whose main connective is conjunction

Alternatively, you can see it as a disjunction of one or more formulae, each of which is a conjunction of one or more literals.

Link to original

Rewrite Rules

DNF Rewrite Rules

To obtain DNF, we can preform a series of transformations:

$$\begin{array}{rl}F\to G& \Rightarrow \neg F\vee G\\ F⟺G& \Rightarrow (F\to G)\vee (G\to F)\\ \neg (F\vee G)& \Rightarrow \neg F\wedge \neg G\\ \neg (F\wedge G)& \Rightarrow \neg F\vee \neg G\\ \neg \neg F& \Rightarrow F\\ F\wedge (G\vee H)& \Rightarrow (F\wedge G)\vee (F\wedge H)\\ (F\vee G)\wedge H& \Rightarrow (F\wedge H)\vee (G\wedge H)\end{array}$$Link to original

title: Example 1
Represent $P \land (P \rightarrow Q)$ in DNF.
 
$$
	\begin{aligned}
		P \land (P \rightarrow Q) &\Rightarrow P \land (\neg P \lor Q) \\
		&\Rightarrow (P \land \neg P) \lor (P \land Q) \\
		&\Rightarrow 0 \lor (P \land Q) \\
		&\Rightarrow P \land Q
	\end{aligned}
$$

Truth Table to DNF

Given the truth table for $(P\vee \neg Q)\wedge R$ with the models highlighted:

interpretation	$p$	$q$	$r$	$\neg q$	$p\vee (\neg q)$	$(p\vee (\neg q))\wedge r$
$v_0$	0	0	0	1	1	0
$v_1$	0	0	1	1	1	1
$v_2$	0	1	0	0	0	0
$v_3$	0	1	1	0	0	0
$v_4$	1	0	0	1	1	0
$v_5$	1	0	1	1	1	1
$v_6$	1	1	0	0	1	0
$v_7$	1	1	1	0	1	1

We can associate each propositional symbol $P_i$ and interpretation $v_j$ with the literal $P_i$ if $v_j$ makes $P_i$ true or $\neg P_i$ if $v_1$ makes $P_i$ false.

Hence we find that:

• $v_1$ is associated with $\neg P\wedge \neg Q\wedge R$
• $v_5$ is associated with $P\wedge \neg Q\wedge R$
• $v_7$ is associated with $P\wedge Q\wedge R$

So we can now combine these to find the DNF:

$$\begin{array}{rl}\text{DNF}& =(\neg P\wedge \neg Q\wedge R)\vee (P\wedge \neg Q\wedge R)\vee (P\wedge Q\wedge R)\\ & =(\neg Q\wedge R)\vee (P\wedge R)\end{array}$$

Special Cases

These apply to both DNF and CNF.

Any contradictory formula $F$ is equivalent to the single conjunction $P\wedge \neg P$, which can be abbreviated to $0$. Any tautology $F$ is equivalent to the single disjunction $P\vee \neg P$, which can be abbreviated to $1$.

Link to original

3. Conjunctive Normal Form

Conjunctive Normal Form

Conjunctive Normal Form

Conjunctive Normal Form (CNF) is when a formula: ?

• contains no connectives other than conjunction, disjunction and negation.
• only applies negation to propositional symbols (within literals)
• no conjunction appears in a sub-formula of a formula whose main connective is disjunction

Alternatively, you can see it as a conjunction of one or more formulae, each of which is a disjunction of one or more literals.

Link to original

Rewrite Rules

CNF Rewrite Rules

To obtain CNF, we can perform a series of transformations:

$$\begin{array}{rl}F\to G& \Rightarrow \neg F\vee G\\ F⟺G& \Rightarrow (F\to G)\vee (G\to F)\\ \neg (F\vee G)& \Rightarrow \neg F\wedge \neg G\\ \neg (F\wedge G)& \Rightarrow \neg F\vee \neg G\\ \neg \neg F& \Rightarrow F\\ F\vee (G\wedge H)& \Rightarrow (F\vee G)\wedge (F\vee H)\\ (F\wedge G)\vee H& \Rightarrow (F\vee H)\wedge (G\vee H)\end{array}$$Link to original

Truth Table to CNF

We cannot go directly from a truth table to CNF, as we will end up with DNF. We can use rules such as De Morgan’s Law to fix our formula.

Suppose we are given $P⟺Q$:

interpretation	$p$	$q$	$p⟺q$
$v_0$	0	0	1
$v_1$	0	1	0
$v_2$	1	0	0
$v_3$	1	1	1

The highlighted values make the formula false.

So when the formula $(\neg P\wedge Q)\vee (P\wedge \neg Q)$ is true, the formula is false, so we can find when $P⟺Q$ is true when the formula we just found is false.

$$\neg ((\neg P\wedge Q)\vee (P\wedge \neg Q))=\boxed{(P\vee \neg Q)\wedge (\neg P\vee Q)}$$

We can manipulate the formula to find it in CNF.

Link to original