Philosophy Stack Exchange is a question and answer site for those interested in the study of the fundamental nature of knowledge, reality, and existence. It only takes a minute to sign up.
Sign up to join this community
((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?
Generally, there are 2 main ways to demonstrate that a given formula is a tautology in propositional logic:
Draw a truth table, like this:
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 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.)
If we convert the conditionals into disjunctions we get:
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.
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/
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.
