How do you prove that this is a tautology?

Question

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

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 09 '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 09 '16 at 10:45
for the natural deduction, I am wondering what sort of answer should I be aiming for? — Tom chan, Apr 09 '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 09 '16 at 11:55
@robertbristow-johnson the soundness theorem for propositional logic guarantees that any theorem is a tautology. — E..., Apr 11 '16 at 13:43
i realize that @EliranH. there is "tautology" from a POV of logic and reasoning and there is "tautology" from the POV of rhetoric and debate. in the latter case, it's a statement in which the conclusion is simply a reworded form of the premise. "If this assertion is not false, then it's true." like saying 5 = 5. but in "rhetorical" usage, perhaps saying "If 5 = y^2 - (x-y)^2 - xy, then -5 = (-x)(y-x) is not a tautology because the conclusion is not obviously a restatement of the premise. but in logic, it is a tautology. — robert bristow-johnson, Apr 11 '16 at 17:33
Possible duplicate of How do I check if two logical expressions are equivalent? — , Apr 20 '16 at 04:03

E... · Answer 1 · 2016-04-09T10:58:18.317

1

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

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

edited Apr 09 '16 at 10:58

answered Apr 09 '16 at 10:51

E...

6,496
4
22
39

Using algorithms like DPLL. But we need to change the problem from tautology to non-falsifiability.

rus9384

Sep 30 '18 at 05:03

score 1 · Answer 2 · answered Apr 19 '16 at 11:25

1

Draw a truth table, like this:

answered Apr 19 '16 at 11:25

Araucaria - Not here any more.

235
3
12

Araucaria - Not here any more. · Answer 3 · 2016-04-19T00:14:04.830

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.

score 0 · Answer 4 · answered Apr 11 '16 at 12:13

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.

"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

score 0 · Answer 5 · answered Apr 11 '16 at 17:13

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.)

score 0 · Answer 6 · edited Jun 17 '20 at 08:34

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:

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:

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/

score 0 · Answer 7 · answered Sep 30 '18 at 11:40

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.

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

How do you prove that this is a tautology?

7 Answers7