1
$\begingroup$

I have been trying to refresh my memory with regards to classical logic. As a result, I am currently going over the basics.

The following proposition seems to be false in all possible worlds. However, this isn't the smallest proposition in the world and it required me to analyse $2^{3}$ possible worlds through truth tables.

I'm just wondering, is there a quicker way to check if the proposition is false in all possible worlds?

$\left[p \wedge (q \lor r)\right] \equiv \left[( \sim q \ \ \lor \sim p) \wedge (\sim r \ \ \lor \sim p)\right]$

$\endgroup$
  • $\begingroup$ Do you know about De Morgan's laws? $\endgroup$ – Git Gud Jan 25 '15 at 18:32
  • $\begingroup$ I do, only at a superficial level however. $\endgroup$ – user4568 Jan 25 '15 at 18:33
7
$\begingroup$

DeMorgan's laws:

  1. $\sim (x \vee y) = (\sim x ) \wedge (\sim y)$

  2. $\sim (x \wedge y) = (\sim x ) \vee (\sim y)$

In some notations where the overline indicates the complement, the rule is "break the line, change the sign":

  1. $\overline{x+y} = \overline{x} \ \overline{y}$

  2. $\overline{xy} = \overline{x} + \overline{y}$


By only manipulating the right hand side, we have $$( \sim q \ \lor \sim p) \wedge (\sim r \ \lor \sim p) \\ = [\sim (q\wedge p)] \wedge [\sim (r \land p)] \\ = \sim [(q\wedge p) \lor (r \land p)] \\ = \sim [(p \land q) \lor (p \land r)] \\ = \sim [p \land (q \lor r)] $$

which is contradictory (false in all possible worlds) to the original left hand side.

$\endgroup$
  • $\begingroup$ Brilliant, I appreciate the help. $\endgroup$ – user4568 Jan 25 '15 at 19:56
  • $\begingroup$ @Qtian Of course! $\endgroup$ – Xoque55 Jan 25 '15 at 21:37
4
$\begingroup$

I'll show you why the left-hand side and left hand side of the claim are contradictory: $$\begin{align} \left[p \wedge (q \lor r)\right] &\equiv \left[( \lnot q \lor \lnot p) \wedge (\lnot r \ \ \lor \lnot p)\right]\tag{1}\\ \\ \iff (p\land q )\lor (p \land r) &\equiv \lnot(q \land p) \land \lnot(r \land p)\tag{2}\\ \\ \iff (p\land q )\lor (p \land r) &\equiv \lnot[(p\land q) \lor (p\land r)]\tag{3}\end{align}$$

$(1 \to 2)$: Distributive law (left), DeMorgan's, twice (right)

$(2\to 3)$ DeMorgan's Law, applied on the left.

This is clearly a self-contradictory proposition, since the right-hand side is the negation of the left-hand side. This means the claim is false in any/all possible worlds, i.e., it is a contradiction (always false, regardless of the truth values of $p, q, r)$.

$\endgroup$
  • $\begingroup$ It might be helpful to add where you used distributivity and DeMorgan as tags :) $\endgroup$ – Daniel W. Farlow Jan 25 '15 at 18:53
3
$\begingroup$

The left hand statement is equivalent to $$(p\land q)\lor (p\land r)$$

Its negation is precisely the right hand statement. So this is indeed a self-contradictory proposition.

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