2

As a practice problem, I'm asked to determine whether the following proposition is a tautology, contradiction, or contingency through the use of logical equivalences.

I get how to determine what truth value the proposition is and I understand most of the logic rules, but I'm stumped on what the first step would be on solving this one. I can't use distribution on ( ( ∨ ) ∧ ( ¬ ∨ ) ) because of the negation symbol on p. If I use de morgan's by moving that outer negation inside, I don't see how it would make a difference because all it'd do is just flip the signs. If I used association and moved the bracket to ( ( ∨ ) ∨ ( ∨ )) I still can't use distribution because all the symbols are a ∨.

¬ ( ( ∨ ) ∨ ( ( ∨ ) ∧ ( ¬ ∨ ) ) )

Any help or push in the right direction would be appreciated.

GilmoreGirling
  • 305
  • 1
  • 7
  • Have you covered the consensus theorem in your class? (You may have called it "resolution.") – Fabio Somenzi May 16 '19 at 20:20
  • No, we haven't covered that. – GilmoreGirling May 16 '19 at 20:21
  • Ignore the outside negation until the end. Apply distributivity to $(p \vee q) \wedge (\neg p \vee r)$, and then apply "$a \vee (a \wedge b)$ simplifies to $a$ twice. – Fabio Somenzi May 16 '19 at 20:31
  • But distributivity is (A ∨ (B ∧ C)) ≡ (A ∨ B) ∧ (A ∨ C) right? I thought I could only do it if there wasn't a negation on the 2nd p. – GilmoreGirling May 16 '19 at 20:34
  • Distributivity in Boolean algebras is also $(A \wedge (B \vee C)) \equiv (A \wedge B) \vee (A \wedge C)$. It feels wrong because it doesn't work for the real numbers, but Boolean algebras enjoy duality of $\wedge$ and $\vee$. – Fabio Somenzi May 16 '19 at 20:42

1 Answers1

1

I will in the following show the reduction of $\neg ((q \lor r) \lor ((p \lor q) \land (\neg p \lor r)))$:

By De Morgan's laws:

$\equiv \neg (q \lor r) \land \neg ((p \lor q) \land (\neg p \lor r))$

By De Morgan's laws:

$\equiv \neg (q \lor r) \land \neg (p \lor q) \lor \neg (\neg p \lor r)$

By De Morgan's laws:

$\equiv (\neg q \land \neg r) \land (\neg p \land \neg q) \lor (p \land \neg r)$

$\equiv (\neg q \land \neg r \land \neg p) \lor (p \land \neg r)$

$\equiv (\neg q \lor p) \land (\neg r \lor p) \land (\neg p \lor p) \land (\neg q \lor \neg r) \land (\neg r \lor \neg r) \land (\neg p \lor \neg r)$

$\equiv (\neg q \lor p) \land (\neg r \lor p) \land T \land (\neg q \lor \neg r) \land T \land (\neg p \lor \neg r)$

$\equiv (\neg q \lor p) \land (\neg r \lor p) \land (\neg q \lor \neg r) \land (\neg p \lor \neg r)$

$\equiv (\neg q \lor p) \land (\neg q \lor \neg r) \land (\neg r \lor (p \land \neg q))$

$\equiv (\neg q \lor (p \land \neg r)) \land (\neg r \lor (p \land \neg q))$

As you can see, I have used De Morgan's laws or the first 3 steps. Even though it doesn't seem like it will make any difference swapping the negation sign and inverting the boolean operator, it might actually give a surprising result since some parentheses may be eliminated because they contain a tautology or contradiction. This is exactly what I have done after the first 3 steps.

Martin Pekár
  • 197
  • 2
    Your final result is incorrect. Careful with parentheses and with the application of distributivity. – Fabio Somenzi May 16 '19 at 22:17
  • What happened to the brackets for ¬(q∨r)∧¬(p∨q)∨¬(¬p∨r)? – GilmoreGirling May 16 '19 at 22:34
  • I will fix it a bit later. @GilmoreGirling I used De Morgan's law to apply the negation to the inner value in the parentheses. By doing this, the boolean operator must be swapped to its opposite. – Martin Pekár May 17 '19 at 07:09