Verify a Tautology without a truth table.

Question

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

Answer 1

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.

Answer 2

One way to do these is with the method of analytic tableaux. [I'll do (b) as an example and leave the rest as an exercise. I hope you don't mind :)]

You start with the negation of the original formula then apply a series of contradiction-hunting rules to get

,

which is closed (i.e. its paths end in contradictions), meaning that the original formula was indeed a tautology.

These notes (in pdf form) explain the method in detail.