$$ (\neg A \wedge \neg C) \vee (\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C) $$ can simplify down to  $$ (\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C) $$ I've computed the truth tables for the two expressions, and they're the same. But I'm supposed to prove it without using truth tables. What law(s) am I supposed to use?

  • $\begingroup$ I don't know what law is supposed to be used to simplify the first expression further. i used wolfram alpha to check if my expression was simplified to it's extent. Thats why i have the second expression. my question is what laws do i need to use to make expression 1 into expression 2 (e.g inverse law, de-morgan's law etc). i can find no way to simplify expression 1. $\endgroup$
    – hhxx
    Dec 5 '13 at 1:52
  • 1
    $\begingroup$ P.S. Presumably the reason why the assignment tells you not to use a truth table is because it wants you to get practice using other methods -- it wants to help you learn those methods. You're not going to learn by watching someone else do it; the only way you'll learn is by doing it yourself. So, you need to try on your own, not hope someone else will solve it for you. $\endgroup$
    – D.W.
    Dec 5 '13 at 21:46

You have $(\neg A \wedge \neg C) \vee \text{some_big_expression} $ and you want to show that it's equivalent to $\text{some_big_expression} $.

Simplification rules won't necessarily lead you from the first expression to the second expression. There are systematic ways to test whether two expressions are equivalent, by applying De Morgan's laws in a certain way and other simplification rules (such as $\neg (\neg P) \longrightarrow P$) to transform a formula into equivalent formulas until you reach a disjunctive normal form (or other normal forms, if you apply the laws in a different way). But this doesn't directly get you from one expression to the other.

Another way to prove that two formulas are equivalent is to show that the first implies the second and the second implies the first. Here, it's obvious that $\text{some_big_expression}$ implies $(\neg A \wedge \neg C) \vee \text{some_big_expression}$, so the difficulty is to prove the opposite implication: $(\neg A \wedge \neg C) \vee \text{some_big_expression}$ implies $\text{some_big_expression}$. Think about what this means: you want to prove that if $P$ or $Q$ holds then $Q$ holds — in other words, if you already know $Q$, then you don't need to prove $P$, it's already implied by $Q$. This is a consequence of two properties of disjunction, idempotency and monotonicity: if $Q \Rightarrow P$ then $(P \vee Q) \Rightarrow (P \vee P) \Rightarrow P$.

So what's left is to prove that $\neg A \wedge \neg C$ implies $(\neg A \wedge D) \vee (\neg A \wedge B) \vee (\neg B \wedge \neg C)$. I'll let you finish. Hint: the right-hand side has both $B$ and $\neg B$, what can you say about these?

Second exercise: use De Morgan's laws to grind the first formula into the second one.


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.