Day 58 – Logic Laws – rose learns.to('code');

We can use logical equivalences to reduce complex formulas into simpler ones.

Two new symbols

p\;\wedge\;T\;\iff\;p\\p\;\vee\;F\;\iff\;p

P and True will be true when both P and Tautology are true.

P or False will be true when either is true, but False will never be true.

p\;\vee\;T\;\iff\;T\\p\wedge F\iff F

In domination law, P or True, P doesn’t really matter as T will always be true.

Example:

(p\;\vee\;F)\;\wedge\;(q\;\vee T)\\(p\;\vee\;F)\;\iff p\;=Identity Law\\(q\;\vee\;T)\iff T\;=DominationLaw\\p\;\wedge\;T\iff p\;=\;IdentityLaw\\Therefore:\\p

Therefore, we can replace the formula as they are logically equivalent with each other:

(p\;\vee\;F)\;\wedge\;(q\;\vee T)\;\iff p

\neg\neg p\;\iff p

If you reverse a value twice, it’s like not reversing at all.

\neg(p\;\wedge q)\iff \neg p\;\vee\;\neg q\\\neg(p\;\vee q)\iff\neg p\;\wedge\;\neg q

One thing to remember, distribute the negation and flip the connective.

Example:

\neg(\neg p\;\wedge\;\neg q)\\\neg\neg p\;\vee\;\neg\neg q\;=DeMorgan's\\p\;\vee\;q\;=\;Double Negation

p\;\wedge\;(q\;\vee\;r)\;\iff (p\,\wedge\,q)\,\vee\,(p\,\wedge\,r)\\p\;\vee\;(q\;\wedge\;r)\iff\,(p\,\vee\,q)\,\wedge\,(p\,\vee\,r)

Review:=

3x(1+2)\;=(3x1)\,+\,(3x2)

p\;\wedge\;(p\;\vee\;q)\;\iff p\\p\;\vee\;(p\;\wedge\;q)\;\iff p

Example:

\neg\neg p\,\vee ((p\,\vee\,F)\,\wedge\,\neg\neg q)\\p\,\vee\,((p\,\vee\,F)\,\wedge\,q)\;=DN*2\\p\,\vee\,(p\,\wedge\,q)\;=ID\\p\;=\;AbsorptionLaw

Flip the order.

p\,\wedge q\iff q\,\wedge\,p\\p\,\vee\,q\iff q\,\vee p

Moving the order, just make sure they share the same connectives, otherwise we would be doing Distributive Law.

p\,\wedge\,(q\,\wedge\,r)\;\iff (p\,\wedge q)\,\wedge r\\p\,\vee\,(q\,\vee\,r)\;\iff (p\,\vee q)\,\vee r

p\,\wedge \neg p \iff F\\p\,\vee\,\neg p\iff T

p \rightarrow\,q\iff \neg p\,\vee q

Example:

Show:

(\neg (p\,\wedge q)\wedge q)\iff (\neg p\,\wedge q)

Whenever we see a ¬ outside of brackets, we can do DeMorgan’s first.

(\neg p\,\vee \neg q)\,\wedge q

Whenever we see opposite ∧ and ∨ inside and outside brackets, we can use Distributivity.

(q\,\wedge \neg p)\,\vee\,(q\,\wedge \neg q)

Next, we see:

q\,\wedge\,\neg q

This is Contradiction or always false, so we can do Inverse Law:

(q\,\wedge \neg p)\,\vee\,F

Now, anything with “or False” is Identity Law

(q\,\wedge \neg p)\,\vee\,F\;\iff q\,\wedge \neg p

Then using Commutativity Law, we can flip the order:

\neg p \wedge q

Therefore, the answer is TRUE:

(\neg (p\,\wedge q)\wedge q)\iff (\neg p\,\wedge q)