# How do I prove that $[¬P ∧ (P ∨ Q)] → Q$ is tautology without using truth tables?

How do I prove the following statement is a tautology, without using truth tables? $$[¬P ∧ (P ∨ Q)] → Q$$

I know that if we assume $Q ≡ T$ then no matter what the truth value of what is to the left of the implication operator is, the statement will be a tautology. But if we assume that $Q ≡ F$ then there could be two possibilities of the outcome of the statement: If $\;[¬P ∧ (P ∨ Q)] ≡ T,\;$ then the statement is false, and if $\;[¬P ∧ (P ∨ Q)] ≡ F,\;$ then the statement is true (according to the truth table of implication statements: $\;T → F = F\;\text{ and }\;F → F = T.)$

Is there a way of proving $\;[¬P ∧ (P ∨ Q)]\rightarrow Q\;$ is always true without using any truth tables, instead can it be solely proven by words/logic? Or am I just being dumb?

• You should be able to use distributive property. – MasterOfBinary Nov 6 '13 at 17:48
• In the final paragraph, I think you meant to ask if there is a way of proving the full statement is always true, not just the portion before the arrow. – Barry Cipra Nov 6 '13 at 18:25
• @MasterOfBinary Why bother with the distributive property for this question? – Doug Spoonwood Nov 8 '13 at 16:26
• @MasterOfBinary Because it involves properties of two operations. So, you have to understand how logical operations interact to some extent. Consequently, using the distributive property may well require more understanding than you need for solving this problem, and perhaps we should try to solve such problems from a position of as little knowledge as possible. If you're doing things from "the ground-up" you'd have to prove the relevant distributive property first. That may well require more work than other sorts of solutions. – Doug Spoonwood Nov 8 '13 at 16:49
• @DougSpoonwood You can simplify the left side to get $\neg P \wedge Q$, which implies $Q$. – MasterOfBinary Nov 8 '13 at 16:54

As you note, if $Q$ is true, then the implication is true.

And if $Q$ is false, we have that $\lnot P \land (P \lor Q) \equiv \underbrace{\underbrace{(\lnot P \land P)}_{F} \lor \underbrace{(\lnot P \land \underbrace{Q}_{F})}_{F}}_{F}$ and any implication with a false premise is true.

Hence, the implication is a tautology.

So, this is probably a silly approach to this sort of thing, but I hate truth tables and take a slightly more circuitous route through what Quine referred to as "alternational normal form". @amWhy cast the antecedent of the conditional in alternational normal form above, but casting the entire sentence into that form gives a pretty clear test of tautology. The drawback is that alternational form can get very long.

So the original formula is $(\neg P\wedge(P\vee Q))\to Q$. First thing is to eliminate the conditionals by writing this as $(P\vee(\neg P\wedge\neg Q))\vee Q$.

On a more complicated sentence we would make use of the distributive properties of alternation and conjunction to make sure we have a chain of alternations of conjunctions. In this case, we have it in a single step above: $P\vee(\neg P\wedge\neg Q)\vee Q$. By changing the order of our alternated elements and adding back in parentheses, we see we have $(P\vee Q)\vee(\neg P\wedge\neg Q)$ or $(P\vee Q)\vee\neg(P\vee Q)$, an obvious tautology.

The thing I like about alternational normal form is A) the resulting sentence is clear, if cumbersome and B) can show a tautology or inconsistency by an extremely syntax-focused method of evaluation.

To prove the implication $\neg P \wedge (P \vee Q) \to Q$, we assume $\neg P \wedge (P \vee Q)$ and then prove $Q$ from this assumption.

From the conjunction $\neg P \wedge (P \vee Q)$ we can infer $\neg P$ and we can also infer $P \vee Q$. Consider two cases according to the two disjuncts of $P \vee Q$.

1. $P$ holds. Then from $\neg P$ we get a contradiction, and from a contradiction we can infer $Q$.

2. $Q$ holds.

In either case we have shown that $Q$ holds.

I agree with Malice Vidrine's answer, and would write it down in the following format: \begin{align} & \lnot P \land (P \lor Q) \;\Rightarrow\; Q \\ \equiv & \;\;\;\;\;\text{"expand $\;\Rightarrow\;$ -- that usually simplifies formulas"} \\ & \lnot(\lnot P \land (P \lor Q)) \lor Q \\ \equiv & \;\;\;\;\;\text{"DeMorgan -- that seems the only way to make progress"} \\ & P \lor \lnot(P \lor Q) \lor Q \\ \equiv & \;\;\;\;\;\text{"reorder disjuncts -- since this introduces more symmetry"} \\ & (P \lor Q) \lor \lnot(P \lor Q) \\ \equiv & \;\;\;\;\;\text{"excluded middle"} \\ & \text{true} \end{align}

Alternatively, we can start with the antecedent, and try to simplify:

\begin{align} & \lnot P \land (P \lor Q) \\ \equiv & \;\;\;\;\;\text{"distribute $\;\land\;$ over $\;\lor\;$"} \\ & (\lnot P \land P) \lor (\lnot P \land Q) \\ \equiv & \;\;\;\;\;\text{"contradiction"} \\ & \text{false} \lor (\lnot P \land Q) \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & \lnot P \land Q \\ \Rightarrow & \;\;\;\;\;\text{"weaken -- to achieve our goal"} \\ & Q \\ \end{align}

*Using the algorithm tautology test*

[P'∧(P∨Q)]→Q

Assume: [P'∧(P∨Q)] is true and Q is false

Assume that [P'∧(P∨Q)] is true and Q is false. -If [P'∧(P∨Q)] is true, then P' is true and (P∨Q) is true. -If P' is true, then P is false. -If P is false in (P∨Q), then Q is true in order for (P∨Q) to be true.

So Q contradicts, it says that is false and at the same time is says that is true. Because of this, we know that this WFF(well formed formula) is a tautology!

Using a Fitch style proof, this tautology can be proved by contradiction. Assume the statement is false, show that this assumption entails a contradiction, then negate the assumption.

• which program did you use for this? – ndrizza Oct 12 '14 at 22:09

The only way for ¬P ∧ (P ∨ Q) to be true is for P to be false and Q to be true. So the full statement [¬P ∧ (P ∨ Q)] → Q cannot be false. Hence it is a tautology.

"But if we assume that Q≡F then there could be two possibilities of the outcome of the statement"

That's not correct. If you assume Q≡F (I'm not assuming ≡ as a logical operator here), then it follows that

[¬p∧(p∨q)]≡[¬p∧(p∨F)] where F indicates the constant false proposition.

(p∨F)≡p, since (T∨F)≡T, and (T∨T)≡T. Or in more algebraic terminology we can say that "F" is the neutral or identity element for ∨.

Thus,

[¬p∧(p∨F)]≡(¬p∧p). From here I think you can complete this sort of proof.

Additionally, I'll add that you could have considered the cases where P holds false, and P holds true. In which case you'll similarly end up using "F" as the neutral element for ∨. In this way, the truth value of a disjunction of two propositions behaves like the maximum of two natural numbers (and in general this holds also).

Assume [¬P∧(P∨Q)]. From "both x and y" as true, we may infer x as true. We may also infer y as true. So, we can infer ¬P as true, as well as (P∨Q) as true. Assume P true. Assume ¬Q true. Then since we have ¬P and P true, we may discharge the negation and infer Q. So, (P→Q) holds true. Suppose Q true. Then Q holds true. So, we can infer (Q→Q) holds true. Since (P∨Q), (P→Q), and (Q→Q) hold true, it follows that Q holds true. Since [¬P∧(P∨Q)] comes as the only assumption still in place, we may infer {[¬P∧(P∨Q)]→Q} as true as desired.

Via Polish notation, (P∨Q) can get rewritten as Apq, [¬P∧(P∨Q)] can get rewritten as KNpApq, and {[¬P∧(P∨Q)]→Q} can get rewritten as CKNpApqq. We can then use the following axioms to prove CKNpApqq as a theorem. By a relevant soundness meta-theorem, we'll have CKNpApqq as a tautology also.

A1 CpCqp - recursive variable prefixing - RVP

A2 CCpCqrCCpqCpr - self-distribution - SD

A3 CCNpKqNqp - negation out - No

A4 CKpqp - conjunction out left - Kol

A5 CKpqq - conjunction out right - Kor

A6 CpCqKpq - conjunction in - Ki

A7 CCpqCCrqCAprq - disjunction out - Ao

Via the relevant deduction meta-theorem which SD and RVP enable, we have conditional introduction as a derivable rule of inference, which I'll denote as Ci. The only other rule of inference I'll use is C-detachment or C-d

{C$\alpha$$\beta$, $\alpha$} $\vdash$ $\beta$.

  1 hypothesis  |    KNpApq
2 Kol         |    CKNpApqNp
3 C-d 2, 1    |    Np
4 Kor         |    CKNpApqApq
5 C-d 4, 1    |    Apq
6 hypothesis  ||   p
7 hypothesis  |||  Nq
8 Ki          |||  CpCNpKpNp
9 C-d 8, 6    |||  CNpKpNp
10 C-d 9, 3    |||  KpNp
11 Ci 7-10     ||   CNqKpNp
12 No          ||   CCNqKpNpq
13 C-d 12, 11  ||   q
14 Ci 6-13     |    Cpq
15 hypothesis  ||   q
16 Ci 15-15    |    Cqq
17 Ao          |    CCpqCCqqCApqq
18 C-d 17, 14  |    CCqqCApqq
19 C-d 18, 16  |    CApqq
20 C-d 19, 5   |    q
21 Ci 1-20          CKNpApqq.


[~p^(pvq)]->q

[pv(~p^~q)]vq

[(pv~p)^(pv~q)]vq

[T^(pv~q)]vq

(pv~q)vq

pvT

T

====================== Therefore its a tautology^^