Conjunctive/disjunctive normal form

  • Context: Undergrad 
  • Thread starter Thread starter XodoX
  • Start date Start date
  • Tags Tags
    Form Normal
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
1 reply · 3K views
XodoX
Messages
195
Reaction score
0
Let's say I have p<-> q.. how do I get the disjunctive and conjunctive normal form ? I think I'd have to apply DeMorgan to get one of them. I don't know. Can anybody please explain this to me?
 
Physics news on Phys.org
p<->q = (p [tex]\wedge[/tex] q) [tex]\vee[/tex] (~p [tex]\wedge[/tex] ~q)
=(p [tex]\wedge[/tex] q) [tex]\vee[/tex] (~p [tex]\wedge[/tex] ~q) [tex]\vee[/tex] (p [tex]\wedge[/tex] ~p) [tex]\vee[/tex] (q [tex]\wedge[/tex] ~q)
=(~p [tex]\vee[/tex] q) [tex]\wedge[/tex] (~q [tex]\vee[/tex] p)

So, the form in red is DNF, while the form in blue is CNF.