0
$\begingroup$

I'm doing textbook homework for discrete mathematics and I'm struggling to understand how to solve the following practice problem. I would understand if they gave me variables and asked me to use premises to construct a specific argument, but I don't understand how to reduce it just to a value of false? Any help or hints would be appreciated.

Question:

Using only the rules of inference and the logical equivalences, show that the following argument is a contradiction by reducing it to a value of "False". You may assume that all the premises given are true.

𝑎 → 𝑏

¬𝑏 ∧ 𝑐

¬𝑎 → 𝑑

𝑑 → ¬𝑒

𝑒 ∧ f

$\endgroup$
6
  • $\begingroup$ It seems like these are five premises, but you haven't given the conclusion. Is this really all there is to the exercise? It doesn't make sense to me. $\endgroup$ – saulspatz Feb 15 '19 at 15:15
  • $\begingroup$ From 3 and 4 derive $\lnot a \to \lnot e$. Then use it and 1 with $a \lor \lnot a$ to apply Dilemma to derive $\lnot e \lor b$. $\endgroup$ – Mauro ALLEGRANZA Feb 15 '19 at 15:20
  • $\begingroup$ Yeah, this is all that was given. I don't really understand it. $\endgroup$ – Eagerissac Feb 15 '19 at 15:23
  • $\begingroup$ Now you have $\lnot e \lor b$ with $\lnot b$ from 2 and $e$ from 5. $\endgroup$ – Mauro ALLEGRANZA Feb 15 '19 at 15:23
  • $\begingroup$ Is it enough to proceed, or do you need more hints ? $\endgroup$ – Mauro ALLEGRANZA Feb 15 '19 at 15:51
0
$\begingroup$

The implication $a \to b$ is equivalent to $\lnot a \lor b$

Similarly, the other two implications can be written as $a \lor d$ and $\lnot d \lor \lnot e$

The two conjunctions $\lnot b \land c$ and $e \land f$ can only be true, if all four operands are true: $\lnot b$, $c$, $e$ and $f$

This simplifies $\lnot a \lor b$ to $\lnot a$

$\lnot d \lor \lnot e$ is simplified to $\lnot d$ which in turn simplifies $a \lor d$ to $a$.

The last step unveils a contradiction, as $\lnot a$ was found to be true earlier on.

$\endgroup$

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.