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:
Name Equivalences Double Negation \(\neg(\neg p)\equiv p\) Commutative \(p\vee q \equiv q\vee p\\p\wedge q \equiv q\wedge p\) Associative \((p\vee q)\vee r \equiv p\vee(q\vee r)\\(p\wedge q)\wedge r \equiv p\wedge(q\wedge r)\) Distributive \(p\vee(q\wedge r) \equiv (p\vee q)\wedge(p\vee r)\\p\wedge(q\vee r) \equiv (p\wedge q)\vee(p\wedge r)\) De Morgan's Law \(\neg(p\wedge q)\equiv \neg p \vee \neg q\\\neg(p\vee q)\equiv \neg p \wedge \neg q\) - [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…