Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Transformation rules in Boolean algebra

  1. Mar 31, 2015 #1
    I know De-Morgan's law that $$ -(p∧q) = -p∨-q $$
    Also $$ -(p∨q) = -p∧-q $$
    But for material implication and bi conditional operations there are also some transformation.
    What is the law or proof for it? Like
    $$ p⇒q = -p∨q $$
    $$ p ↔q = (p∧q) ∨ (-p∧-q) $$
    There may be other properties also that I don't know.
    How one can derive or say that?

    SideNote: Why PF don't have a negation ( tilda symbol) ?
     
  2. jcsd
  3. Mar 31, 2015 #2

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    This should strictly be logical equivalence and not equality.
    You can show $$ p⇒q = -p∨q $$ , e.g., with truth tables, showing that the two associated tables are identical, or by using a derivation, assuming $$ p⇒q $$ and deriving $$-p∨q $$ from it. Example: rewrite$$ -p ∨ q = -(p ∧-q)$$ , and assume p , then assume $$ (p ∧-q)$$, and arrive at a contradiction . From previous, p follows, then q follows and then you conclude$$ q ∧-q $$ , a contradiction, from which $$ -(p ∧-q) $$ follows.
     
    Last edited: Mar 31, 2015
  4. Mar 31, 2015 #3
    rewrite$$ -p ∨ q = -(p ∧-q)$$
    That you have written by De-Morgan's Law. Then I am not able to understand afterwards.
     
  5. Mar 31, 2015 #4

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    I just rewrote. Please point out the steps you don't understand. I want to show A->B, and I do that by trying to show A-> -B, i.e., I assume A, and I assume it implies -B, and arriving at a contradiction from this last. Here B is (p∧-q) and A is $$ p⇒q $$ . It is a proof by contradiction.
     
    Last edited: Mar 31, 2015
  6. Mar 31, 2015 #5
    I am not understanding that,
    If A is $$ p ⇒q $$ and B is $$ p ∧-q $$ then how A implying -B is a contradiction?
     
  7. Mar 31, 2015 #6

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    If you assume A ->B and you arrive at a contradiction, then you can conclude A--> -B. In our case, if you assume (P-->Q)-> -[ P/\-Q] and you derive a contradiction from that, then, by contradiction, you conclude (P-->Q)->[P/\-Q].

    So what we do is: we assume that (P-->Q) implies the negation of what we want to prove, i.e., we assume that (P-->Q) -->-[P/\-Q] and from this we arrive at a contradiction, then we conclude (P-->Q)-->-(-[P/\-Q])==[P/\-Q].
     
    Last edited: Mar 31, 2015
  8. Mar 31, 2015 #7

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    More Formally/ in more detail:

    We assume P-->Q and we assume -[-P \/ Q]=[P/\-Q] , i.e., we assume (P-->Q)-->[P/\-Q] , and from this we arrive at a contradiction, from which we conclude

    (P-->Q)-->[P/\-Q] ==[-P\/Q]:

    Assume
    (P-->Q)--> [P/\-Q] , and assume (P-->Q)
    i) Then we conclude [P/\-Q] == P
    ii) From [P/\-Q] ,we conclude P
    iii) From [P/\-Q] , we conclude- Q
    iv) From ii and the premise, we conclude Q
    v)From iv) and iii) , we conclude Q/\-Q , a contradiction
    vi)By contradiction, we conclude -[P/\-Q]
    ___________________________________ We discharge our assumption, to get:

    (P-->Q) --> -[[P/\-Q]]==-P \/ Q

    Which is what we wanted to show.
     
  9. Mar 31, 2015 #8
    I think it is better to go by truth table.
    I am able to show they are both equivalent by truth table. I am not able to understand these statements much.
    Why we are in the first place going for a proof by contradiction?
    I am not understanding the first point that how we are concluding [PΛ-Q]== P ?
     
  10. Apr 2, 2015 #9

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    My mistake, should be just [P/\-Q]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Transformation rules in Boolean algebra
  1. Boolean Algebra (Replies: 1)

Loading...