1
$\begingroup$
(( P ∧ Q ) ∨ R ) ⇒ (R ⇒ Q ) ≡ ¬ (( P ∧ Q ) ∨ R ) ∨ (R ⇒ Q )
≡ ¬ (( P ∧ Q ) ∨ R ) ∨ ( ¬ R ∨ Q ) ≡ ( ¬ ( P ∧ Q ) ∧ ¬ R ) ∨ ( ¬ R ∨ Q )
≡ (( ¬ P ∨ ¬ Q ) ∧ ¬ R ) ∨ ( ¬ R ∨ Q ) to CNF from here
≡ (( ¬ P ∨ ¬ Q ) ∨ ( ¬ R ∨ Q )) ∧ ( ¬ R ∨ ( ¬ R ∨ Q ))
≡ ( ¬ P ∨ ¬ Q ∨ ¬ R ∨ Q ) ∧ ( ¬ R ∨ Q ) CNF
≡ Τ ∧ ( ¬ R ∨ Q ) ≡ ¬ R ∨ Q simplified CNF

What happens when it goes from

≡ (( ¬ P ∨ ¬ Q ) ∧ ¬ R ) ∨ ( ¬ R ∨ Q ) to CNF from here
≡ (( ¬ P ∨ ¬ Q ) ∨ ( ¬ R ∨ Q )) ∧ ( ¬ R ∨ ( ¬ R ∨ Q ))

What gets distributed to gain these results?


Also, in this line:

 ( ¬ P ∨ ¬ Q ∨ ¬ R ∨ Q ) ∧ ( ¬ R ∨ Q ) CNF 
 ≡ Τ ∧ ( ¬ R ∨ Q ) ≡ ¬ R ∨ Q simplified CNF

Shouldn't -Q and Q be the one that are getting pulled out as True? In my head, I believe it should be :

$$T\land(\lnot P \lor \lnot R) \land (\lnot R \lor Q)$$

Which can be simplified down into $\lnot R \land (\lnot P \lor Q)$??

$\endgroup$
1
  • 6
    $\begingroup$ Woah symbol overload! Is it possible you could "distill" the problem down to its "core essence"? People will be more likely to help, if you do this. $\endgroup$ Mar 2, 2013 at 22:43

2 Answers 2

3
$\begingroup$

You're correct on the second question: it should be $$Q \lor \lnot Q \equiv T,$$ leaving what you wrote:

$$ T\land(-P \lor -R) \land (-R \lor Q) \;\;\equiv\;\; (\lnot P \lor \lnot R) \land (\lnot R \lor Q)\tag{1}$$

which can be simplified, but simplified to $$\lnot R \lor (\lnot P \land Q)\tag{2}$$ and NOT to $\lnot R \land (\lnot P \lor Q)$, as you wrote: $\; (2)$ follows from $(1)$ by the distributive laws: $$ (A\lor B) \land (A \lor C) \equiv A \lor (B \land C)$$

But $(2)$ is not in CNF, whereas the highlighted expression $(1)$ is already in CNF.


First Question: We have the distributive rule:$$(A \land B) \lor C \equiv (A\lor C) \land (B\lor C)$$

Where $\quad A = (\lnot P \lor \lnot Q);\quad B = \lnot R;\quad C = (\lnot R \lor Q).\;$ So $$ (( ¬ P ∨ ¬ Q ) ∧ ¬ R ) ∨ ( ¬ R ∨ Q )\quad \equiv \quad (( ¬ P ∨ ¬ Q ) ∨ ( ¬ R ∨ Q )) ∧ ( ¬ R ∨ ( ¬ R ∨ Q ))$$

  • $(\lnot P \lor \lnot Q)$ is or'ed with $(\lnot R \lor Q),$
  • then, $\quad\lnot R$ is or'ed with $(\lnot R \lor Q)$
  • And they are conjoined by $\land$ because $\land$ connects the two terms $(\lnot P \lor \lnot Q)$ and $\lnot R$.

    You're correct, this is one of the distributive laws.

$\endgroup$
1
  • $\begingroup$ Such a nice answer! =1 $\endgroup$
    – Amzoti
    May 11, 2013 at 0:47
0
$\begingroup$

Assuming you have reason to believe an expansion using distributive rule was used....

There are only four binary operations in

(( ¬ P ∨ ¬ Q ) ∧ ¬ R ) ∨ ( ¬ R ∨ Q )

furthermore, two of them aren't in an expression that one could expand with the distributive rule. So there is a very small number of cases to check....

Or working backwards

(( ¬ P ∨ ¬ Q ) ∨ ( ¬ R ∨ Q )) ∧ ( ¬ R ∨ ( ¬ R ∨ Q ))

There aren't terribly many subexpressions of this expression; it's not hard to check all of them to find an expression that is repeated twice, and then factor using the distributive rule to see if it provides the previous expression.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .