Logic Review

• When we were looking at propositional logic operations, we defined several things using and/or/not.
• For example: \begin{align*} p\oplus q &\equiv (p\vee q) \wedge \neg(p\wedge q)\,, \\ p\rightarrow q &\equiv \neg p \vee q\,,\\ p\leftrightarrow q &\equiv (p\rightarrow q) \wedge (q \rightarrow p) \equiv (\neg p \vee q)\wedge (\neg q \vee p)\,. \end{align*}
• We did that to help us understand the new symbols in terms of things we already knew.
• But it is also nice to have a standard definition of the operators we can use.
• When proving equivalences, it let us apply equivalences we already had that used and/or/not.
• We also had some equivalence rules that helped us rearrange propositions so we could get at the parts we needed:
• [And the others, but let's stick with these for now.]
• We can be a little stricter about how we arrange the proposition.

Normal Forms

• Remember that we also called “or” “disjunction” and “and” “conjunction”.
• A clause that contains only $$\vee$$ is called a disjunctive clause and only $$\wedge$$ is called a conjunctive clause.
• Negation is allowed, but only directly on variables.
• $$p\vee \neg q\vee r$$: a disjunctive clause
• $$\neg p\wedge q\wedge \neg r$$: a conjunctive clause
• $$\neg p\wedge \neg q\vee r$$: neither
• If we put a bunch of disjunctive clauses together with $$\wedge$$, it is called conjunctive normal form.
• For example: $$(p\vee r)\wedge(\neg q\vee \neg r)\wedge q$$ is in conjunctive normal form.
• Similarly, putting conjunctive clauses together with $$\vee$$, it is called disjunctive normal form.
• For example: $$(p\wedge\neg q\wedge r)\vee(\neg q\wedge \neg r)$$ is in disjunctive normal form.
• More examples:
• $$(p\wedge q\wedge \neg r\wedge s)\vee(\neg q\wedge s)\vee(p\wedge s)$$ is in disjunctive normal form.
• $$(p\vee q\vee \neg r\vee s)\wedge(\neg q\vee s)\wedge\neg s$$ is in conjunctive normal form.
• $$(p\vee r)\wedge (q\wedge(p\vee \neg q))$$ is not in a normal form.
• $$\neg p \vee q \vee r$$ and $$\neg p \wedge q \wedge r$$ are in both normal forms.
• It turns out we can turn any proposition into either normal form.
• We can use the definitions to get rid of $$\rightarrow$$, $$\leftrightarrow$$, and $$\oplus$$.
• Use DeMorgan's laws to move any $$\neg$$ in past parens, so they sit on the variables.
• Use double negation to get rid of any $$\neg\neg$$ that showed up.
• Use the distributive rules to move things in/out of parens as we need to.
• For example, converting to conjunctive normal form: \begin{align*} \neg((\neg p\rightarrow \neg q)\wedge \neg r) &\equiv\neg((\neg\neg p\vee \neg q)\wedge \neg r) & \mbox{[definition]} \\ &\equiv\neg((p\vee \neg q)\wedge \neg r) & \mbox{[double negation]} \\ &\equiv \neg(p\vee \neg q) \vee \neg\neg r & \mbox{[DeMorgan's]} \\ &\equiv \neg(p\vee \neg q) \vee r & \mbox{[double negation]} \\ &\equiv (\neg p\wedge \neg\neg q) \vee r & \mbox{[DeMorgan's]} \\ &\equiv (\neg p\wedge q) \vee r & \mbox{[double negation]} \\ &\equiv (\neg p\vee r)\wedge (q \vee r) & \mbox{[distributive]} \end{align*}
• It was actually in disjunctive normal form in the second-last step.
• Why would we want to convert to a normal form?
• May be easier to prove equivalence: to show $$A\equiv B$$, convert both to normal form, and then re-write one proof backwards.
• Maybe we simplify a lot: if we end up with $$(p\vee\neg p\vee\cdots)$$ terms, we know they are true.
• Proving theorems about all propositions: only have to handle boolean expressions in a normal form and that covers every proposition.
• Shows that we can use circuitry to calculate any boolean expression with two layers of logic gates.
• Another example: \begin{align*} (p\rightarrow q)\rightarrow(\neg r\wedge q) &\equiv \neg(p\rightarrow q)\vee(\neg r\wedge q) & \mbox{[definition]} \\ &\equiv \neg(\neg p\vee q)\vee(\neg r\wedge q) & \mbox{[definition]} \\ &\equiv (\neg\neg p\wedge\neg q)\vee(\neg r\wedge q) & \mbox{[DeMorgan's]} \\ &\equiv ( p\wedge\neg q)\vee(\neg r\wedge q) & \mbox{[double negation]} \\ \end{align*}
• At this point, it's in DNF. Continuing…
\begin{align*} (p\rightarrow q)\rightarrow(\neg r\wedge q) &\equiv ( p\wedge\neg q)\vee(\neg r\wedge q) & \mbox{[as above]} \\ &\equiv (p\vee (\neg r\wedge q))\wedge(\neg q \vee (\neg r\wedge q)) & \mbox{[distributive]} \\ &\equiv (p\vee (\neg r\wedge q))\wedge(\neg q \vee \neg r)\wedge (\neg q \vee q) & \mbox{[distributive]} \\ &\equiv (p\vee (\neg r\wedge q))\wedge(\neg q \vee \neg r)\wedge \mathbf{T} & \mbox{[negation]} \\ &\equiv (p\vee (\neg r\wedge q))\wedge(\neg q \vee \neg r) & \mbox{[identity]} \\ &\equiv (p\vee\neg r)\wedge (p\vee q)\wedge (\neg q \vee \neg r) & \mbox{[distributive]} \end{align*}