Stuck on a simple logic simplification

Printable View

October 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
October 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?
October 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
October 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

$(\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 ( $x\lor\neg x=1$ ). Can you derive that, or is that just a rule you already have but didn't mention?

First way:

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

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

Second way:

$(\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.
October 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:

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

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

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

$=\neg P\lor P$ (double negation).
October 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?
October 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?