# Use of hypothesis to prove a tautology

Given $$(¬(P ∧¬Q)⇒S)∧¬P ∧(R⇒¬S) ⇒ ¬R$$ prove that this is a tautology.

One way is to use a hypothesis taken from the proposition itself.

As an example: If we want to prove this rule: $P ⇒ (P ∧ Q ≡ Q)$ , we can do as follows:

We prove the equation $P ∧ Q ≡ Q$ using the hypothesis $P$ as justification:

$$P ∧ Q$$ $$≡ \{Hypothesis: P, P ≡ T \}$$ $$T ∧ Q$$ $$≡ \{Unity \}$$ $$Q$$

How do I do the same thing, with the proposition i wrote at the beginning?

]Proof system example:

[

It's in italian but it should be clear, those in brackets are, for example, the Commutative or Associative property.

• Could you rephrase/clarify your question a little? It is unclear what you are asking. Are you trying to avoid making standard boolean algebraic manipulations? – Ben I. Jan 26 '17 at 16:23
• I have to prove it through a formal proof (a derivation). I cannot make, for example, P → T, Q → F, S → T, R → T and then check the values according to the table. – emaph Jan 26 '17 at 16:33
• You'll have to explain what kind of formal proof system you are supposed to use. There are several ones and we cannot guess which one is used in your class. – Yuval Filmus Jan 26 '17 at 16:34
• I don't understand. What is "the hypothesis of the proposition itself"? What does $P\Rightarrow (P\land Q\equiv Q)$ have to do with the thing you're trying to prove? – David Richerby Jan 26 '17 at 16:36
• We need a complete list of axioms. Otherwise we can't know what you're allowed to use. – Yuval Filmus Jan 26 '17 at 16:53

(¬(P∧¬Q)⇒S)∧¬P∧(R⇒¬S)⇒¬R

I've added in an extra parens for clarity:

((¬(P∧¬Q)⇒S)∧¬P∧(R⇒¬S))⇒¬R

First, replace x⇒y with ¬x∨y. This is definitional.

¬ ((¬¬(P∧¬Q)∨ S)∧¬P∧(¬R∨¬S)) ∨ ¬R

Cancel out ¬¬

¬ (((P∧¬Q)∨ S)∧¬P∧(¬R∨¬S)) ∨ ¬R

(¬((P∧¬Q)∨ S) ∨ ¬¬P ∨ ¬(¬R∨¬S)) ∨ ¬R

Cancel out ¬¬

(¬((P∧¬Q)∨ S) ∨ P ∨ ¬(¬R∨¬S)) ∨ ¬R

((¬(P∧¬Q)∧ ¬S) ∨ P ∨ (¬¬R∧¬¬S)) ∨ ¬R

Cancel out ¬¬

((¬(P∧¬Q)∧ ¬S) ∨ P ∨ (R ∧ S)) ∨ ¬R

Demorgan's again:

(((¬P ∨ ¬¬Q) ∧ ¬S) ∨ P ∨ (R ∧ S)) ∨ ¬R

Cancel out ¬¬ one last time

(((¬P ∨ Q) ∧ ¬S) ∨ P ∨ (R ∧ S)) ∨ ¬R

Drop outer parens (using associativity)

((¬P ∨ Q) ∧ ¬S) ∨ P ∨ (R ∧ S) ∨ ¬R

Use the distributive property on the first term

((¬P∧ ¬S) ∨ (Q ∧ ¬S)) ∨ P ∨ (R ∧ S) ∨ ¬R

Drop parens (using associativity)

(¬P ∧ ¬S) ∨ (Q ∧ ¬S) ∨ P ∨ (R ∧ S) ∨ ¬R

At this point, we have a chain of or statements. Use the distributive property on the last 2 terms:

(¬P ∧ ¬S) ∨ (Q ∧ ¬S) ∨ P ∨ ((R ∨ ¬R) ∧ (S ∨ ¬R))

(R ∨ ¬R) is always true, and T ∧ x ≡ x, thus:

(¬P ∧ ¬S) ∨ (Q ∧ ¬S) ∨ P ∨ S ∨ ¬R

Commutative property:

(¬P ∧ ¬S) ∨ P ∨ (Q ∧ ¬S) ∨ S ∨ ¬R

We will repeat the procedure with the distributive property on (¬P ∧ ¬S) ∨ P and on (Q ∧ ¬S) ∨ S:

((¬P ∨ P) ∧ (¬S ∨ P)) ∨ ((Q ∨ S) ∧ (¬S ∨ S)) ∨ ¬R (T ∧ (¬S ∨ P)) ∨ ((Q ∨ S) ∧ T) ∨ ¬R ¬S ∨ P ∨ Q ∨ S ∨ ¬R

Commutative property:

¬S ∨ S ∨ P ∨ Q ∨ ¬R

¬S ∨ S is T, and True or'd with anything becomes True by domination.

• Thank you, that one possibility. The exercises specified to use another technique, but I'm not able to explain it here, so I will try to gather more information and then I'll do another question. But thanks, that's also been useful. – emaph Jan 26 '17 at 18:44