# Propositional Logic. I'm unsure about a few steps of this problem.

(( 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)$??

-
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

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.

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

-