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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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}

Answer 5

*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!

Answer 6

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.

Answer 7

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.

Answer 8

"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).

Answer 9

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.

Answer 10

[~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^^