Results 1 to 7 of 7

Math Help - Stuck on a simple logic simplification

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    22

    Stuck on a simple logic simplification

    Hi,

    I'm stuck on a simple problem - I have the following equivalences:
    (星^昨)v(R^Q)v(星^R)=(星^昨)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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    22
    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)=星v昨
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jul 2010
    Posts
    22
    Thanks for your help guys. However, I'm still somewhat confused.
    How do I get (星^昨)v(R^Q)v(星^R) into a form that I can reduce by the law of the distributed middle?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Logic Simplification
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 27th 2011, 11:46 AM
  2. simple simplification
    Posted in the Calculus Forum
    Replies: 1
    Last Post: July 5th 2009, 01:46 PM
  3. Simple Simplification
    Posted in the Algebra Forum
    Replies: 5
    Last Post: October 31st 2008, 06:51 AM
  4. Replies: 15
    Last Post: June 3rd 2008, 04:58 PM
  5. Simplification too simple?
    Posted in the Algebra Forum
    Replies: 8
    Last Post: September 25th 2007, 05:16 PM

Search Tags


/mathhelpforum @mathhelpforum