-2
$\begingroup$

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:

[enter image description here

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Ben I. Jan 26 '17 at 16:23
  • $\begingroup$ 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. $\endgroup$ – emaph Jan 26 '17 at 16:33
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 26 '17 at 16:34
  • $\begingroup$ 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? $\endgroup$ – David Richerby Jan 26 '17 at 16:36
  • 2
    $\begingroup$ We need a complete list of axioms. Otherwise we can't know what you're allowed to use. $\endgroup$ – Yuval Filmus Jan 26 '17 at 16:53
1
$\begingroup$

(¬(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

Demorgan's in your first ¬

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

Cancel out ¬¬

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

Demorgan's in your outer ¬s

((¬(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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – emaph Jan 26 '17 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.