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!

Boolean Equation Equivalence Problem

  1. Apr 29, 2010 #1
    1. The problem statement, all variables and given/known data
    Part a was to prove the equivalence of the two equations using a truth table. Done.
    Part b is to prove the equation using the 10 properties of boolean logic, as seen in http://en.wikipedia.org/wiki/Boolean_logic#Properties"

    We are trying to prove:
    (p∨q)∧(¬q∨r) ⇔ (p∧r)∨((p∧(¬q∧¬r))∨(¬p∧(q∧r))).


    2. Relevant equations



    3. The attempt at a solution

    I have done one solution, which was basically a brute force attempt at the problem including lots of distribution over and over again. It was over two pages long and about 40 steps. Not ideal, and not full credit for the problem either. My current attempt I am just in need of a way to 'legally' add in a "not p" into the second term of the first line in the second block of expressions. The first block is working from the longer equation to the short one, and the other block is from the shorter to the longer, trying to meet in the middle.

    I have no idea if this will lead to a solution, but I am being hopeful!

    (p∧r)∨((p∧(¬q∧¬r))∨(¬p∧(q∧r)))
    (p∧(r∨(¬q∧¬r)))∨(¬p∧(q∧r))
    (p∧((r∨¬r)∧(r∨¬q)))∨(¬p∧(q∧r))
    (p∧(T_0∧(r∨¬q)))∨(¬p∧(q∧r))
    (p∧(r∨¬q))∨(¬p∧(q∧r ))

    (p∧(r∨¬q))∨(q∧r)
    (p∧(r∨¬q))∨(F_0∨(q∧r))
    (p∧(r∨¬q))∨((q∧¬q)∨(q∧r))
    (p∧(r∨¬q))∨(q∧(r∨¬q))
    (p∨q)∧(r∨¬q)

    I am just wondering if anyone has any suggestions on how to get that last step on the proof I just posted, or any guidance of another short (half a page typed) proofs for this equation.

    Edit: the half that contains the difference is not equal on a truth table, meaning it cannot be directly converted. If I were to connect those two equations, I believe that the entire equation would have to be manipulated.
     
    Last edited by a moderator: Apr 25, 2017
  2. jcsd
  3. Apr 30, 2010 #2
    Start by posting which properties you're using in each stage. You'll quickly see that you're only using about 4 and dropping out two key properties that'll go a long way towards getting you to a solution.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Boolean Equation Equivalence Problem
  1. Boolean equation (Replies: 4)

Loading...