3

((p->q) and (r->s) and (p or r)) -> (q or s)

How would you prove that this is a tautology? Using natural deduction?

My attempt on this question is the following.

Since a tautology means W entails by empty premise and W is something of A->B, where A is a conjunction of sentences, then all I have to do is prove B is entailed of all the sentences of A.

Then is it done right?

|improve this question
  • Can you show us some work you've made on the problem or your thoughts as to a solution? After that, we can give you tips. – virmaior Apr 9 '16 at 10:41
  • for the equivalence, I turn all the implications into or , but it looks very messy, so was wondering if there is any shortcut. – Tom chan Apr 9 '16 at 10:45
  • for the natural deduction, I am wondering what sort of answer should I be aiming for? – Tom chan Apr 9 '16 at 10:45
  • With natural deduction, the proof is quite straightforward: apply and-elimination followed by or-elimination (i.e. proof by cases) with p or rderiving in the first case q followed by q or s by or-introduction and s followed by q or s again by or-introduction. – Mauro ALLEGRANZA Apr 9 '16 at 11:55
  • i guess any proven theorem becomes a tautology of sorts. – robert bristow-johnson Apr 9 '16 at 23:28
1

Generally, there are 2 main ways to demonstrate that a given formula is a tautology in propositional logic:

  1. Using truth tables (a given formula is a tautology if all the rows in the truth table come out as True), which is usually easier.
  2. Using natural deduction with no premises, which is usually harder. If you get a conclusion using no premises then it is a tautology, since propositional logic (with respect to natural deduction) is sound.
|improve this answer
  • 3. Using algorithms like DPLL. But we need to change the problem from tautology to non-falsifiability. – rus9384 Sep 30 '18 at 5:03
1

Draw a truth table, like this:

enter image description here

|improve this answer
0

Is ((p->q) and (r->s) and (p or r)) -> (q or s), a tautology?

This is tautologous iff the premises ((p->q) and (r->s) and (p or r)) are true and the conclusion (q v s) is false.

If (q v s) is false then both q and s are false.

If q and s are false then the premises become ((p->F) & (r -> F) & (p v r)),

That is: ((~p) & (~r) & (p v r)).

That is: ((~p & ~r) & (p v r)).

That is: (~(p v r) & (p v r)) which is clearly a contradiction.

That is: It cannot be the case that ((p -> q) & (r -> s) & (p v r)) is true while (q v s) is false.

Therefore: ((p -> q) & (r -> s) & (p v r)) -> (q v s), is tautologous.

|improve this answer
  • "This is tautologous iff the premises ((p->q) and (r->s) and (p or r)) are true and the conclusion (q v s) is false." <--- Don't you mean iff the premises cannot be true when the conclusion is false? – Araucaria - Not here any more. Apr 11 '16 at 12:19
0

This is a conditional, so assume the antecedent. If you can derive the consequent (with no additional premises), the conditional is a tautology.

You can divide the antecedent into three statements, using and elimination. Of those, the "Or" is the most promising.

Assume p on one side, r on the other. On the p branch, you can get q via the conditional. Make that "q or s" with or introduction. Do the same thing in reverse on the other branch. Then you can derive "q or s" with or elimination.

In general, with natural deduction, assuming the antecedent is the best way to derive a conditional. (For most other forms, assuming the opposite and demonstrating a contradiction is the most reliable approach.)

|improve this answer
0

If we convert the conditionals into disjunctions we get:

  • (Not P or Q) and (Not R or S) and (P or R) --> (Q or S)

If we assume P is true then, Not P is false. Because of the first disjunction, Q must therefore be true. This is sufficient to make (Q or S) true.

If we assume P is false, R is true because of the third disjunction. If R is true, Not R is false. Therefore because of the second disjunction, (Not R or S), S must be true. This is enough for the disjunction (Q or S) to be true.

Therefore because P must be either true or false, (Q or S) is true.

Assuming the statement is a material implication, if (Q or S) is true, so the statement is true by definition.

|improve this answer
0

Here is the question:

((p->q) and (r->s) and (p or r)) -> (q or s)

How would you prove that this is tautology? Using natural deduction?

Since one wants to prove that this is a tautology one would use a truth table, that is, one would use a semantic approach to solving the problem in truth-functional logic. The semantics refers to the true or false valuations of the atomic sentences.

Since there are four atomic sentences, p, q, r and s, the truth table should have 16 lines as Araucaria's answer showed. Here is a proof using Stanford's truth table tool:

enter image description here

That should be the end of it, however, one could approach the problem from a syntactic, rather than a semantic, approach. Then one would use something like natural deduction. One would derive the result using inference rules. Considering that this is described as a "tautology", that may not be what the assignment is asking for.

Here is one way to do that using Klement's Fitch-style natural deduction proof checker:

enter image description here

I used the following rules which can be found described in forall x: conjunction elimination (∧E), conditional elimination (→E), disjunctive introduction (DS), law of excluded middle (LEM) and (conditional introduction (→I).

Using this syntactic approach for a tautology is questionable unless one knows that the two approaches, truth tables and derivations give the same results.

This goes beyond the original question, but it is covered with an outline of a proof in forall x in Chapter 20. It is covered in more detail in Lemmon's Beginning Logic, pages 75-91.

References

Araucaria's answer: https://philosophy.stackexchange.com/a/33727/29944

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

Lemmon, E. J. (1971). Beginning logic. CRC Press.

P. D. Magnus, Tim Button with additions by J. Robert Loftis remixed and revised by Aaron Thomas-Bolduc, Richard Zach, forallx Calgary Remix: An Introduction to Formal Logic, Winter 2018. http://forallx.openlogicproject.org/ Wikipedia, "Fitch notation" https://en.wikipedia.org/wiki/Fitch_notation

Stanford's Truth Table Tool: http://web.stanford.edu/class/cs103/tools/truth-table-tool/

|improve this answer
0

You wish to prove the assumptions entail a conditional statement. Clearly you need a Condtional Proof: Assume the antecedant to attempt a derivation for the consequent, so that you can introduce that conditional.

 |  P -> Q               Premise
 |_ R -> S               Premise
 |  |_ P v R             Assumption
 |  |  ...
 |  |  Q v S
 |  (P v R) -> (Q v S)   Conditional Introduction

How might you prove a something from the assumption of a disjunction? Well, disjunction elimination should be the likely route.

 |  P -> Q              Premise
 |_ R -> S              Premise
 |  |_ P v R            Assumption
 |  |  |_ P             Assumption
 |  |  |  ...
 |  |  |  Q v S
 |  |  P -> (Q v S)     Conditional Introduction
 |  |  |_ R             Assumption
 |  |  |  ...
 |  |  |  Q v S
 |  |  R -> (Q v S)     Conditional Introduction
 |  |  Q v S            Disjunction Elimination
 |  (P v R) -> (Q v S)  Conditional Introduction

Well now, I am sure you can see how to complete those subproofs.

|improve this answer
  • I think P v R is one of the three premises and the goal is Q v S. – Frank Hubeny Sep 30 '18 at 14:47

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.