Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
(( 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)$??

share|improve this question
6  
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. –  goblin Mar 2 '13 at 22:43

2 Answers 2

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.

share|improve this answer
    
Such a nice answer! =1 –  Amzoti May 11 '13 at 0:47
    
Thanks, @Amzoti! –  amWhy May 11 '13 at 0:48

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.