0

Can you prove this conclusion follows from the premiss without the use of any tautology? I've been trying to do it but I haven't succeeded without using the tautology equivalences.

p → q ⊢ (p ∨ r) → (q ∨ r)

Sahiba Arora
  • 10,847
Lauro Morais
  • 11
  • how do you need to prove this? Truth-table? Short Truth-table? Truth Tree? Algebra? Formal proof? Informal proof? Using semantics? And what do you mean by 'tautology equivalences'? – Bram28 Jul 27 '17 at 19:25
  • Via formal proof. By 'tautology equivalences' I mean rules such as (B ∨ ~B) ↔T, (B ∨ T) ↔ T, (B ∧ T) ↔ B, (B ∨ C) ↔ B, (B ∧ C) ↔ C (where T stands for tautolgy and C for contradiction) – Lauro Morais Jul 27 '17 at 19:37
  • OK, what rules do you have available to you? Because there are a lot of different formal proof systems, each with their own set of rules. Can you post those rules? And did you try anything at all, or at least have some thoughts about how to do this? Some strategy? – Bram28 Jul 27 '17 at 19:41
  • All introduction and elimination rules for logical operators (conjunction, disjunction, negation, implication), besides absorption and all equivalences related do these operators as well as distributivity and associativity. – Lauro Morais Jul 27 '17 at 19:46
  • OK, since your goal is a conditional ($\rightarrow$), did you try to set this up as a Conditional proof? $\def\fitch#1#2{\begin{array}{|l}#1 \ \hline #2\end{array}}$

    $\fitch{P \rightarrow Q}{\fitch{P \lor R}{ \ Q \lor R}\(P \lor R) \rightarrow (Q \lor R) \quad \rightarrow \ Intro}$

     – Bram28 Jul 27 '17 at 19:48
  • Although I was able to get it through conditional proof, I wonder how can we get it without using it. – Lauro Morais Jul 27 '17 at 19:52
  • Oh! OK, well, that's quite a more difficult question .... let me think about that ... so you don't want to use any subproofs at all? – Bram28 Jul 27 '17 at 19:53

1 Answers1

2

I don't know what system you are using. In natural deduction, you eliminate the implication to get (p$\lor$r) as hypothesis, use the rule of disjunction with (p$\lor$r) and tem vou need to prove (i) q $\lor$ r from p $\to$ q and p and need to prove (ii) q $\lor$ r from p $\to$ q and r. To (i) tou use modus ponens, to (ii) you have r as hypothesis.

Aaron Maroja
  • 17,571
Thiago Nascimento
  • 455