Verify that the following are tautologies. Do not make truth tables.
a. $\lnot(\lnot) P \leftrightarrow P$
The first question is just a double negation law. So, if I have to take the left side and make it equivalent to the right side, then I would just use the double negation law on the left which will result in $P \leftrightarrow P$.
$\lnot(\lnot) P \leftrightarrow P$ (double negation )
$P \leftrightarrow P$.
b. $\lnot (P \lor Q) \leftrightarrow \lnot P \land \lnot Q$
This is one of the DeMorgan's Law. If I want the left side to be equivalent as the right side, won't I have to use one of DeMorgan's Laws to achieve that result?
Edit: I had to find some of my notes from last night.
I got this for b because it may be equivalent to
$\lnot P \land \lnot Q \leftrightarrow \lnot P \land \lnot Q$ from c
c.$\lnot (P \land Q) \leftrightarrow \lnot P \lor \lnot Q$
This is also a DeMorgan's law. Again, should I use one of DeMorgan's Laws as well?
$\lnot P \lor \lnot Q \leftrightarrow \lnot P \lor \lnot Q$ from b
$\lnot (P \land Q) \leftrightarrow \lnot (P \land Q)$
d. $P \land (Q \lor R) \leftrightarrow (P \land Q) \lor (P \land R)$
This is the distributive law. I'm wondering if I should just distribute the $P \land$ on the left to make it equivalent to the right side.
$P \land (Q \lor R) \leftrightarrow (P \land Q) \lor (P \land R)$
$P \land Q \space \lor P \land R \leftrightarrow (P \land Q) \lor (P \land R)$ (distributive law)
$(P \land Q) \space \lor (P \land R) \leftrightarrow (P \land Q) \lor (P \land R)$
Edit: What if I substitute $A$ for $P$ and $B$ for $(Q \lor R)$?
I'm starting from the left $P \land (Q \lor R)$
So, let $P=A$ and $(Q \lor R) = B$?
then we have $A \land B$
Using Double Negation
$\lnot(\lnot P) \leftrightarrow P$
we obtain
$ \lnot (\lnot A) \land \lnot (\lnot B)$
The first part of DeMorgan's Law states that $\lnot (P \lor Q) \leftrightarrow \lnot P \land \lnot Q$
Therefore,
$\lnot(\lnot(\lnot A) \lor \lnot (\lnot B))$
Using Double Negation Law
$\lnot (A \lor B)$
Substitute back
$\lnot (P \lor (Q \lor R))$
Well that somewhat worked but if I were to use the distributive law now, I would have a lot of $\lor$ signs
$\lnot [( P \lor Q) \lor (P \lor \lor R)]$
unless the $\lor \lor$ changes into an $\land$ ? And the $\lnot$ sticks around which doesn't happen on the right side of d.
e. $P \lor (Q \land R) \leftrightarrow (P \lor Q) \land (P \lor R)$
This is also a distributive law, so maybe I should distribute the $P \lor$
$P \lor (Q \land R) \leftrightarrow (P \lor Q) \land (P \lor R)$
$P \lor Q \land P \lor R \leftrightarrow (P \lor Q) \land (P \lor R)$ (distributive law)
$(P \lor Q) \land (P \lor R) \leftrightarrow (P \lor Q) \land (P \lor R)$
Edit:
I am using the left side of e which is $P \lor (Q \land R)$
Let $A=P$ and $B=(Q \land R )$
$A \lor B$
Using Double Negation
$\lnot(\lnot P) \leftrightarrow P$
$\lnot (\lnot A) \lor \lnot (\lnot B)$
DeMorgan's Law from C.
$\lnot (\lnot (\lnot A) \land \lnot (\lnot B))$
Double negation
$\lnot ( A \land B)$
Substituting Back
$\lnot (P \land (Q \land R)$
Distributive Law.
$\lnot ( (P \land Q) \land (P \land \land R))$
There has got to be a way to get rid of the $\lnot$ and the extra symbol in D and E
Best Answer
We verify b) and c) (De Morgan's laws) using a) (double-negation law).
a) $\lnot (\lnot P) \leftrightarrow P$.
b) - Start with the left-hand side and put $\lnot \lnot P$ in place of $P$ and $\lnot \lnot Q$ in place of $Q$ (i.e., use double-negation a)) :
$\lnot (P \lor Q) \leftrightarrow \lnot (\lnot \lnot P \lor \lnot \lnot Q)$
then use c) to transform the content of right-hand side parentheses into : $\lnot (\lnot P \land \lnot Q)$ [ rewrite it as : $\lnot [\lnot (\lnot P) \lor \lnot (\lnot Q) ]$ ; now it is of the "form" : $\lnot [\lnot P_1 \lor \lnot Q_1]$; then you must replace $\lnot P_1 \lor \lnot Q_1$ with $\lnot (P_1 \land Q_1)$, by c), that is really : $\lnot (\lnot P \land \lnot Q)$]. In this way you will get :
$\lnot (P \lor Q) \leftrightarrow \lnot (\lnot \lnot P \lor \lnot \lnot Q) \leftrightarrow \lnot \lnot (\lnot P \land \lnot Q)$
then apply again double-negation to the right-hand side ("cancelling" $\lnot \lnot$) and you will have :
$\lnot (P \lor Q) \leftrightarrow (\lnot P \land \lnot Q)$.
c) - Start with the left-hand side and put $\lnot \lnot P$ in place of $P$ and $\lnot \lnot Q$ in place of $Q$ (i.e., use double-negation a)) :
$\lnot (P \land Q) \leftrightarrow \lnot (\lnot \lnot P \land \lnot \lnot Q)$
then use b) to transform the content of right-hand side parentheses into : $\lnot (\lnot P \lor \lnot Q)$ getting :
$\lnot (P \land Q) \leftrightarrow \lnot (\lnot \lnot P \land \lnot \lnot Q) \leftrightarrow \lnot \lnot (\lnot P \lor \lnot Q)$
then apply again double-negation and it's done.