2
$\begingroup$

Task: Prove following with rules of inference (do not use truth table)

$$ (A \vee B \rightarrow C) \wedge (C \rightarrow D \wedge C) \wedge (C \rightarrow D) \rightarrow (A \rightarrow D) $$

Attempt to prove

  1. $A \vee B \rightarrow C$ (premise)
  2. $C \rightarrow D \wedge C$ (premise)
  3. $C \rightarrow D$ (premise)
  4. $A \vee B \rightarrow D \wedge C$ (Hypothetical syllogism 1,2)
  5. $\neg(A \vee B) \vee (D \wedge C)$ (Logical equivalence 4)
  6. $(\neg A \wedge \neg B)\vee (D \wedge C)$ (Logical equivalence 5)
  7. $\neg A \vee D$ (Add 6)
  8. $A \rightarrow D$ (Logical equivalence)

Q.E.D.


Is my proof valid?

$\endgroup$
  • $\begingroup$ Either the formula or the proof are incorrect, you have an $\lor$ followed by an $\land$, but you interpreted them all as premises. $\endgroup$ – Luke Collins Jun 11 '19 at 14:36
  • $\begingroup$ @LukeCollins There would be typo in the formula, I'll fix that $\endgroup$ – Tuki Jun 11 '19 at 14:37
  • $\begingroup$ What do you get when you evaluate the formula with A being true and all the rest being false? $\endgroup$ – DanielV Jun 11 '19 at 14:51
2
$\begingroup$

I'm not sure how technical you want to be, but you actually gave the proof for $$A\lor B\to C, C\to D\land C, C\to D \vdash A\to D,$$ not what you showed. You would have to use $\land$-elimination to obtain what you dubbed the "premises" separately. This is the difference between a "proof" (in a metalanguage) and a "true implication".

Have you encountered the symbol $\vdash$ before? If not, don't worry about my point. As long as you only applied the rules you are allowed to apply, then the actual reasoning behind the proof you provided appears to be correct.

(Usually, I take the deduction rules listed here for propositional logic).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I haven't encountered this symbol before. I'm taking a course called "Algorithm mathematics" which introduces us to various topics including introduction to logic. $\endgroup$ – Tuki Jun 11 '19 at 14:47
  • $\begingroup$ Yes, probably these subtle distinctions are not that important then. Do you have a list of rules which you are allowed to apply to prove a formula? And if so, is each step you carried out justified by one of these rules? If yes, then your proof is correct. $\endgroup$ – Luke Collins Jun 11 '19 at 14:49
  • $\begingroup$ Yes we do indeed.It's in Finnish but you can probably understand it, here is the list i.imgur.com/qVTimfL.png $\endgroup$ – Tuki Jun 11 '19 at 14:51
  • $\begingroup$ I'm not quite sure if my interpretation of "Add rule" is correct on 7. row $\endgroup$ – Tuki Jun 11 '19 at 14:54
  • $\begingroup$ Ah okay. The symbol $A\vdash B$ is basically like an inline version of $\frac AB$, so you actually do have to make some changes. You do not have three premises, but one (the whole thing before the $\to$). You need to first separate the conjoined statements using the Simp rule. $\endgroup$ – Luke Collins Jun 11 '19 at 14:56

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.