Decide if $((((P\wedge Q)\wedge R)\wedge S)\wedge T)\Rightarrow(\neg P\vee T)$ is a tautology

Question

How can I show that $((((P\wedge Q)\wedge R)\wedge S)\wedge T)\Rightarrow(\neg P\vee T)$ is a tautology?

I tried to apply the implication rule $(p\Rightarrow q)\equiv (\neg p\vee q)$ but it doesn't seem to bring me anywhere.

@Inazuma Yes, I can do that. I just thought I could apply some formulas to simplify it. — stillenat, Apr 01 '16 at 01:05
@stillenat Nevermind, G. Sassatelli has already provided a valid explanation! — Inazuma, Apr 01 '16 at 01:07

score 2 · Accepted Answer · 2016-04-02T13:50:55.460

2

\begin{align}\text{your expression}&\equiv \neg ((\text{stuff})\wedge T)\vee(\neg P\vee T)\\\color{blue}{[\text{De Morgan}+\text{associativity}]}&\equiv\neg(\text{stuff})\vee\neg T\vee\neg P\vee T\\\color{blue}{[\text{commutativity}+\text{associativity}]}&\equiv(\neg T\vee T)\vee (\text{whatever})\end{align}

The last is a tautology.

edited Apr 02 '16 at 13:50

answered Apr 01 '16 at 01:04

score 1 · Answer 2 · answered Apr 02 '16 at 14:40

You have (conjunction ⇒ disjunction). T is present in the conjunction and the disjunction. Your implication is a tautology.

Formal proof (e.g., sequent calculus):

Start from (T ⇒ T)

Dilute the antecedent (by adding conjuncts) and the consequent (by adding disjuncts)

Decide if $((((P\wedge Q)\wedge R)\wedge S)\wedge T)\Rightarrow(\neg P\vee T)$ is a tautology

2 Answers2