1

I am working on a problem in logic. The proof is supposed to involve only 19 rules of inference.

The problem is:

Given:

$$ Z \implies A $$ $$ Z \lor A $$

Deduce:

$$ A$$

My proof is

$$ (Z \implies A) \land (Z \lor A) $$ $$ (Z \implies A) \land (\lnot \lnot Z \lor A) \text{(Double negation)}$$ $$ (Z \implies A) \land (\lnot Z \implies A) \text {(implication)} $$ $$ Z \lor \lnot Z \text{(tautology)} $$ $$ A \lor A \text {(constructive dilemma)} $$ $$ A \text{(tautology)} $$

What is my mistake?

ardhajya
  • 514
  • I don't see any mistake. – 5xum Dec 05 '16 at 11:39
  • Is it okay to deduce Z∨¬Z from (Z⟹A)∧(¬Z⟹A) ? Which of the 19 rules of inference is active here? (It seems to me, there may be a missing link somewhere in between these two steps) – ardhajya Dec 05 '16 at 11:50
  • As $Z\lor\neg Z$ is a tautology, you don't need to deduce it from anything... But if you want, you could have $X$, and from $X$ you deduce $X\land \top$, and from that you deduce $X\land (Z\lor \neg Z)$. – 5xum Dec 05 '16 at 11:51
  • 2
    If arbitrary tautologies are allowed without deducing them, you can just start out by saying that $(Z\Rightarrow A)\Rightarrow((Z\lor A)\Rightarrow A)$ is a tautology (which it is) and apply MP two times. So most probably arbitrary tautologies are not allowed. But you need to tell us what IS allowed. Just saying that there are 19 rules that are allowed doesn't tell us which they are -- there are many ways to create proof systems for propositional calculus and we have no way of knowing which way the author of the text you're looking at has chosen to set up his. – hmakholm left over Monica Dec 05 '16 at 12:18

1 Answers1

1

I think that it would be much better illustrated as follows:

$ (Z \implies A) \land (Z \lor A) $

$ (\lnot Z \lor A) \land (Z \lor A) $

$ (A \lor \lnot Z) \land (A \lor Z) $

$ A \land (\lnot Z \lor Z) $

$ A \land true $

$ A $

barak manos
  • 43,109