# Stuck on a simple logic simplification

Printable View

• Oct 26th 2010, 03:42 PM
entropyslave
Stuck on a simple logic simplification
Hi,

I'm stuck on a simple problem - I have the following equivalences:
(¬P^¬Q)v(R^Q)v(¬P^R)=(¬P^¬Q)v(R^Q)
I can see why it is so simply by seeing that the first two terms already account for the truth of the third under the possible permutations.
However, I cannot see how to derive the result just using the propositional logic laws/manipulations.

Thanks for your help!

Chris
• Oct 26th 2010, 05:02 PM
Ackbeet
Well, I'm going to take a page out of emakarov's book and ask which propositional logic system you're using? Copi and Cohen? Natural deduction? Another way of asking this question is to ask what the basic assumptions are. What are your axioms?
• Oct 26th 2010, 11:46 PM
entropyslave
Not sure the name of the system, but the laws are as follows, all using either AND (^) or OR (v) or NOT (¬) and brackets:
DeMorgan ¬(PvQ)=¬P^¬Q ¬(P^Q)=¬Pv¬Q
Commutative, Associative, Double negation
Distributive: P^(QvR)=(P^Q)v(P^R) Pv(Q^R)=(PvQ)^(PvR)
Idemopotent: P^P=P PvP=P
Absorbtion: Pv(P^Q)=P P^(PvQ)=P
• Oct 27th 2010, 05:47 AM
Ackbeet
Well, probably the easiest way to do this problem is with a Karnaugh map, but I doubt you've studied that yet. How about this line of inquiry:

Simplify the expression

$\displaystyle (\neg P\land\neg Q\land\neg R)\lor(\neg P\land\neg Q\land R)\lor(\neg P\land Q\land R)\lor(P\land Q\land R)$

two different ways. This will depend on the law of the excluded middle ($\displaystyle x\lor\neg x=1$). Can you derive that, or is that just a rule you already have but didn't mention?

First way:

$\displaystyle ((\neg P\land\neg Q)\land(R\lor\neg R))\lor((P\lor\neg P)\land (Q\land R))$ (distributive law and associativity)

$\displaystyle ((\neg P\land\neg Q)\land\text{True}))\lor(\text{True}\land (Q\land R))$ etc.

Second way:

$\displaystyle (\neg P\land\neg Q\land\neg R)\lor(\neg P\land\neg Q\land R)\lor(\neg P\land\neg Q\land R)\lor(\neg P\land Q\land R)\lor(\neg P\land Q\land R)\lor(P\land Q\land R)$ (absorption)

Then reduce pairwise (1 and 2, 3 and 4, 5 and 6) in the same manner as above.
• Oct 27th 2010, 05:54 AM
Ackbeet
I think that the combination of the law of non-contradiction, DeMorgan, and double-negation will get you the law of the distributed middle thus:

$\displaystyle \text{True}=\neg\text{False}$ (definition)

$\displaystyle =\neg(P\land\neg P)$ (law of non-contradiction)

$\displaystyle =\neg P\lor\neg\neg P$ (DeMorgan)

$\displaystyle =\neg P\lor P$ (double negation).
• Oct 27th 2010, 01:41 PM
entropyslave
Thanks for your help guys. However, I'm still somewhat confused.
How do I get (¬P^¬Q)v(R^Q)v(¬P^R) into a form that I can reduce by the law of the distributed middle?
• Oct 27th 2010, 04:20 PM
Ackbeet
You don't. If you notice, the starting point I took is larger than either of the two sides of the equality you're trying to prove. I didn't start from either side of your equation. My idea was to start from an expression which I could simplify into either side of the equation. Since both sides would then be equal to my starting expression, I would be done. Make sense?