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.


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

  • $\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

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.


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.