1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Logical equivalencies

  1. Jan 12, 2017 #1
    1. The problem statement, all variables and given/known data

    upload_2017-1-12_18-50-46.png

    2. Relevant equations

    upload_2017-1-12_18-46-10.png

    3. The attempt at a solution

    upload_2017-1-12_18-48-21.png


    And I just don't know what to do from here... Any help will be greatly appreciated!
     
  2. jcsd
  3. Jan 12, 2017 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    I think you should use the distributive law on expressions like:
    ##(\lnot p \land \lnot q) \lor (q \lor \lnot r)##
    to get:
    ## (\lnot p \lor ( q \lor \lnot r) ) \ \land \ (\lnot q \lor (q \lor \lnot r) )##

    Then, in those propositions that involve only "##\lor##"'s, you can change the pattern ##A \lor B \lor C## to ## \lnot( \lnot A \land \lnot B) \lor C## and then get rid of the last ##\lor## by changing it to ##(\lnot A \land \lnot B) \implies C##.
     
  4. Jan 13, 2017 #3
    Hi, thanks for taking the time to respond. Does this look correct to you?

    upload_2017-1-13_1-16-1.png

    Also, how would I prove that the original expression and the one I derived are equivalent using logical equivalencies? (I.e., I think I have to convert everything in the original and derived expressions to T's and F's (True's and False's), and they both have to reduce to the same.)

    Again, thanks so much for your help!
     
    Last edited: Jan 13, 2017
  5. Jan 13, 2017 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    You are doing the double negations like changing ##\lnot (\lnot p) ## to ##p## without showing it as a step. Some instructors may permit that.

    The expression ##\lnot q \lor (q \lor \lnot r)## could be simplifed to ## ( \lnot q \lor q) \lor \lnot r## and then to ## T \lor \lnot r## and then to ##T##.

    The rules you are using change expressions to logically equivalent expressions, so your steps are guaranteed to result in a logical equivalence.

    Of course, you can check your work by using a truth table.

    If you had a rule that was not a logical equivalence such as ##p \lor q \lor r \implies p ## and you changed the expression ##(p \lor q \lor r)## to ##(p)## then you could not claim that such a step produced a new expression that was logically equivalent to the old expression. However, all the rules you listed use the relation ##\equiv##.
     
  6. Jan 13, 2017 #5
    Hi Stephen,

    The next question in the assignment asks me to use a truth table, which should be easy enough. However, the preceding question asks for the use of logical equivalencies (reduction to T's and F's) to prove the original and derived expressions are logically equivalent. For this part, based on what you said, this is what I have so far (sorry if the snip resolution is suboptimal):

    upload_2017-1-13_14-43-52.png

    However, I'm not sure how to further reduce the last line... Can the original and derived expressions be further reduced?

    Any help you can lend in this matter would be greatly appreciated. Thanks for all the help you've provided thus far.
     
    Last edited: Jan 13, 2017
  7. Jan 29, 2017 #6

    Stephen Tashi

    User Avatar
    Science Advisor


    It might be simpler to continue by using the associative and commutative laws after you reach the expression:
    ##( (\lnot p \lor ( q \lor \lnot r)) \land (\lnot q \lor (q \lor \lnot r)) ) \land ( (\lnot q \lor (p \lor q) )\land (r \lor (p \lor q))) ##
    by doing:
    ##\equiv ((\lnot p \lor ( q \lor \lnot r)) \land (( \lnot q \lor q) \lor \lnot r)) \land ((\lnot q \lor (p \lor q)) \land (r \lor (p \lor q)))##
    ##\equiv ((\lnot p \lor ( q \lor \lnot r)) \land (( \lnot q \lor q) \lor \lnot r)) \land ((\lnot q \lor q) \lor p) \land (r \lor (p \lor q)))##
    The negation and domination laws are very useful in reducing logical expressions:
    ##\equiv ((\lnot p \lor ( q \lor \lnot r)) \land (T \lor \lnot r)) \land( (T \lor p) \land (r \lor (p \lor q)))##
    ##\equiv ((\lnot p \lor ( q \lor \lnot r)) \land T) \land ( T \land (r \lor (p \lor q)))##
    ##\equiv ((\lnot p \lor ( q \lor \lnot r))) \land ( (r \lor (p \lor q)))##
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Logical equivalencies
  1. Logic Design (Replies: 2)

  2. Logical equivalence (Replies: 1)

  3. Logic Gates (Replies: 26)

  4. Logic Circuits (Replies: 7)

  5. Logic gate (Replies: 14)

Loading...