# Verify a Tautology without a truth table.

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

• Your question is unclear. In (c): yes, go ahead and use DeMorgan's laws. In (d), sure, why not distribute? In the other parts it is not clear what you are asking. – Matthew Conroy Jan 20 '14 at 2:20
• The book itself was unclear to begin with. I had no clue about "citing the appropriate result". I don't understand that part at all. Had this problem allow me to draw truth tables, I would've been done ages ago. my book page – usukidoll Jan 20 '14 at 3:02
• When assignment instructions are unclear, the best thing for you to do is contact your instructor for clarification. My guess is that your methods (DeMorgan's, distributive law, etc.) are exactly what the author of the problem is looking for. – Matthew Conroy Jan 20 '14 at 4:32
• that's what I'm doing. I just contacted the instructor through email. But, hmm I don't know if I'm doing this right... Do I have to take the left side of each problem and use the laws to achieve the result from the right side like...let's take $\lnot(\lnot P) \leftrightarrow P$ I see a double negation...I'm taking the left side. So do I use the double negation law to make $\lnot(\lnot P)$ $P$ ? So, this would be the end result $P \leftrightarrow P$ – usukidoll Jan 20 '14 at 6:05
• Yes, that's the usual idea. However, you should check with your instructor about how you are expected to format your arguments. Notice that the last lines of your work for (c), (d) and (e) are tautologies, so they don't say anything. You are actually writing more than you need to, and starting with an expression you haven't shown to be true. Again, check with your instructor about how you should do this kind of thing. – Matthew Conroy Jan 20 '14 at 6:24

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.

• How were you able to get this so fast? It took me a while to realize that the problems I was given were not ordinary. They were laws. So if I were to solve b ... should I use double negation from a and the demorgan from c? – usukidoll Jan 20 '14 at 8:47
• I've studied them long time ago ... this is the "magic". But as Matthew sayd, don't forget the "basic law of learning" : "if you don't understand, ask". – Mauro ALLEGRANZA Jan 20 '14 at 8:50
• I am asking... but ok. I understand that were are using the left side of c $\lnot (P \land Q) \leftrightarrow \lnot P \lor \lnot Q$ this is the left side $\lnot (P \land Q)$ now I apply the double negation law from a for $P$ and $Q$ $\lnot (\lnot \lnot P \land \lnot \lnot Q)$ but I don't understand how to use b unless we are using b to transform $\lnot (\lnot \lnot P \land \lnot \lnot Q)$ – usukidoll Jan 20 '14 at 8:52
• No, we have proved the equivalence of $\lnot (P \land Q)$ and $\lnot P \lor \lnot Q$ (i.e.of "second" De Morgan's law), assuming : doble-negation law, "first" De Morgan's law, transitivity of equivalence (the conncetive $\leftrightarrow$) and replacement properties (i.e. if in a formula $A$ with the propositional variable $P$ I replace all occurrences of $P$ with a formula $B$, the truth-value of the result does not change; we apply it - for example -when we replaced $P$ with $\lnot \lnot P$). – Mauro ALLEGRANZA Jan 20 '14 at 8:58
• O_O that was lightning fast. so b is $\lnot (P \lor Q) \leftrightarrow \lnot P \land \lnot Q$ oh I see how the double negation would occur again for $\lnot (P \land Q) \leftrightarrow \lnot (\lnot \lnot P \land \lnot \lnot Q) \leftrightarrow \lnot \lnot (\lnot P \lor \lnot Q)$ $\lnot \lnot [\lnot \lnot ( \lnot P \lor \lnot Q)$] – usukidoll Jan 20 '14 at 8:59

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.

• The code for the diagram above can be found here. – Shaun Jan 20 '14 at 10:29
• I haven't learned this method :( but you could tell me if I should just use the distributive laws for d and e... because they seem so straight forward, but I could be wrong. – usukidoll Jan 20 '14 at 10:36
• That's okay. I get the impression that it's not widely used, perhaps because tableaux are fiddly to format. But it's my preferred method. The distributive law looks appropriate on the face of it $\ddot\smile$ – Shaun Jan 20 '14 at 10:42
• really? wait I don't know what that means...yeah you could tell that I'm new at this.. but I do know that I have to use the left side of d and somehow get it to be the same as the right hand side. I figure distributing the $P \land$ might work and for e distribute the $P \lor$. – usukidoll Jan 20 '14 at 10:44
• @Shaun - regarding tableau method, in addition to "my preferred" Smullyan's book, you can see also : Mordechai Ben-Ari, Mathematical Logic for Computer Science (3rd ed - 2012) and Marcello D'Agostino & Dov Gabbay (editors), Handbook of Tableau Methods (1998). – Mauro ALLEGRANZA Jan 21 '14 at 9:32