0
$\begingroup$

Hurley, "...Logic" 8th ed. section 7.5 introduces conditional proof. Some exercises are designed to show proofs that are much easier using conditional proof. For example 7.5 I (2):

  1. $(F \implies E) \land (F \land E \implies R) $ Premise
  2. $(F \implies E) $ 1.
  3. $(F \land E \implies R)$ 1.
  4. $F$ Assumption
  5. $E$ 2.
  6. $F \land E$ 4, 5.
  7. $R$ 3.
  8. $F \implies R$ 4, 7.

I would like to see a proof of this without conditional proof. The allowable rules are these: Modus ponens, Modus tollens, Hypothetical syllogism, Disjunctive syllogism, Constructive Dilemma, And-introduction and elimination (named differently), Or-introduction, DeMorgan's laws, Commutivity, Associativity, distribution, double negation, Transposition (contrapositive), Material implication, Exportation $ (P \land Q) \implies R \iff (P \implies (Q \implies R))$, and tautologies $p \iff p \land p$, and $p \iff p \lor p$.

Translating things using material implication and then reducing using DeMorgan's and distribution is not working out for me. Constructive dilemma could be used on $ \lnot E \implies \lnot F $ and $E \implies (\lnot F \lor R))$ if we could introduce $E \lor \lnot E$, but there is no rule allowing this.

$\endgroup$
2
  • $\begingroup$ $E\vee\neg E$ is a tautology. You stated that you could use tautologies. (Or are you limited to the idempotencies?) $\endgroup$ Commented Jul 14, 2020 at 23:36
  • $\begingroup$ Only the idempotencies. $\endgroup$
    – djbennett
    Commented Jul 15, 2020 at 0:33

3 Answers 3

1
$\begingroup$

I think a possible proof in the style of Hurley's book (without using Conditional Proof), could be:

$ \def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}} $ $ \fitch{1.\,F \supset E\\ 2.\,(F \bullet E) \supset R \qquad \backslash F \supset R }{ 3.\,\lnot R \supset \lnot(F \bullet E) \qquad 2, \text{Trans}\\ 4.\,\lnot \lnot R \lor \lnot(F \bullet E)\qquad 3, \text{Impl}\\ 5.\,R \lor \lnot(F \bullet E)\qquad 4, \text{DN}\\ 6.\,R \lor (\lnot F \lor \lnot E)\qquad 5, \text{DM}\\ 7.\,(R \lor \lnot F) \lor \lnot E\qquad 6, \text{Assoc}\\ 8.\,\lnot E \lor (R \lor \lnot F)\qquad 7, \text{Com}\\ 9.\,\lnot E \lor (\lnot F \lor R)\qquad 8, \text{Com}\\ 10.\,E \supset (\lnot F \lor R)\qquad 9, \text{Impl}\\ 11.\,E \supset (F \supset R)\qquad 10, \text{Impl}\\ 12.\,F \supset (F \supset R)\qquad 1,11\,\text{HS}\\ 13.\,(F \bullet F) \supset R\qquad 12, \text{Exp}\\ 14.\,F \supset R \qquad 13, \text{Taut} } $

$\endgroup$
3
  • 1
    $\begingroup$ As is common, once a complete answer is seen, one can go back and so, "but why didn't I just..." I think I used a truth table tool to incorrectly conclude that e=>(f=>r) was not derivable from the premises, even though I used Exportation in some previous attempts. Note that Exportation makes for a shorter proof: commute F&E, then do (E&F)=>R give E=>(F=>R). $\endgroup$
    – djbennett
    Commented Jul 16, 2020 at 16:43
  • $\begingroup$ @F.Zer Well, I stand corrected! Very nice!! :) +1 But yes, with Exportation this would be even easier. As the OP said, I can't believe I didn't see that :P $\endgroup$
    – Bram28
    Commented Jul 16, 2020 at 19:46
  • 1
    $\begingroup$ Thanks for your comment, @Bram28 ! I appreciate it :-) $\endgroup$
    – F. Zer
    Commented Jul 16, 2020 at 21:15
0
$\begingroup$

Here's an outline, just fill in the gaps.

$\begin{array}{|rll}1.&(F\to E)\wedge((F\wedge E)\to R)&\text{Premise}\\\hline 2.&F\to E&\text{And elimination 1} \\3.&(F\wedge E)\to R&\text{And elimination 1}\\4.&F\to (F\wedge F)&\text{Tautology (Idempotence of And)}\\\vdots&\vdots&\vdots\\n{-}1.&{(F\wedge F)\to R}&\text{Exportation }\ldots\\n.&F\to R&\text{Hypothetical Syllogism 4,n-1}\end{array}$

$\endgroup$
1
  • $\begingroup$ There is no rule for introducing the implication at 4. $\endgroup$
    – djbennett
    Commented Jul 15, 2020 at 5:43
0
$\begingroup$

I don't have a proof for this, but I have a feeling there might be no such formal proof possible. One of Hurley's rules is Absorption, which allows you to derive $P \to (P \land Q)$ from $P \to Q$, and that is exactly what seems to be needed here. Or at least: with Absorption you can then go from $F \to E$ to $F \to (F \land E)$, and so with a simple Hypothetical Syllogism you can combine that with $(F \land E) \to R$ to get $F \to R$. But without Absorption .... you seem to be up the creek!

$\endgroup$
5
  • $\begingroup$ This comment made me go back and find this on p. 359 of the version I am using: "Some texts include..."absorption"...This rule is necessary only if conditional proof is not presented...". Absorption very simply gives the proof I asked for. $\endgroup$
    – djbennett
    Commented Jul 16, 2020 at 16:45
  • $\begingroup$ Note that F. Zer's proof gives a derivation of Absorption: A=>(A=>A) by two OR-additions of ~A and going back and forth with Material Implication. Zer's proof is ((A=>B)&(A&B)=>C)=>(A=>C). Take C=(A&B) $\endgroup$
    – djbennett
    Commented Jul 16, 2020 at 17:07
  • $\begingroup$ @djbennett I am glad I did not actually claim that there was no proof ... just that I had a feeling :P. Because yes, while Absorption may sometimes be needed to complete a proof without CP, that of course does not mean that in this case we couldn't do it without CD or Absorption ... even as Absorption would have made this proof trivial. But, I don't see how Xer's proof gives a derivation of Absorption without CP ... this would require you to have $(A \land B) \to (A \land B)$ as a premise, i.e. an ability to derive $A \to A$ without CP ... I believe for that you really need Absorption itself $\endgroup$
    – Bram28
    Commented Jul 16, 2020 at 19:55
  • $\begingroup$ I think you are right Bram28. I confused having (A=>B)=>(A=>B) which is derivable from premises with (A&B)=>(A&B), which is not. "Take C=(A&B)" is a disguised form of conditional proof, is it not? $\endgroup$
    – djbennett
    Commented Jul 16, 2020 at 20:17
  • $\begingroup$ @djbennett I would say no on the latter ... you are just pointing out a substitution ... that is not a conditional proof. $\endgroup$
    – Bram28
    Commented Jul 16, 2020 at 22:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .