Friday, May 3, 2013

MATHEMATIC DISCRETE



EXERCISES  1-3.5
1.   Write equivalent forms for the following formulas in which negations are applied to the  variables only.
(a). ¬(PVQ)
(b). ¬(PΛQ)
Obtain the principal conjunctive normal forms of (a), (c), and (d).

Solution:
(a). ¬(PVQ)↔ (¬PΛ¬Q)
(b). ¬(PΛQ)↔ (¬PV¬Q)

Principal conjunctive normal forms of :
(a). ¬(PVQ)↔ (¬PΛ¬Q)
       ↔ (¬PVF) Λ(FV¬Q)
       ↔ (¬PV(QΛ¬Q)) Λ((PΛ¬P)V¬Q)
       ↔ (¬PVQ)Λ(¬PV¬Q)Λ(PV¬Q)Λ(¬PV¬Q)
       ↔ (¬PVQ)Λ(¬PV¬Q)Λ(PV¬Q)
       ↔ (PV¬Q)Λ(¬PVQ)Λ(¬PV¬Q)

(c). ¬(P→Q)↔ ¬(¬PVQ)
        ↔ (PΛ¬Q)
        ↔ (PVF) Λ(FV¬Q)
        ↔ (PV(QΛ¬Q))Λ(PΛ¬P)V¬Q)
        ↔ (PVQ)Λ(PV¬Q)Λ(PV¬Q)Λ(¬PV¬Q)
        ↔ (PVQ)Λ(PV¬Q)Λ(¬PV¬Q)

(d). ¬(P   Q)↔ ¬((P→Q)Λ(Q→P))
       ↔ ¬((¬PVQ)Λ(¬QVP))
       ↔ ¬(¬PVQ)V¬(¬QVP)
       ↔ (PΛ¬Q)V(QΛ¬P)
       ↔ (PΛ¬Q)V(¬PΛQ)
       ↔ (PV(¬PΛQ))Λ(¬QV(¬PΛQ))
       ↔ (PV¬P)Λ(PVQ)Λ(¬PV¬Q)Λ(QV¬Q)
       ↔ TΛ(PVQ)Λ(¬PV¬Q)ΛT
       ↔ (PVQ)Λ(¬PV¬Q)











2.   Obtain the product-of-sums canonical forms of the following formulas.
(a). (PΛQΛR)V(¬PΛRΛQ)V(¬PΛ¬QΛ¬R)
      (c). (PΛQ)V(¬PΛQ)V(PΛ¬Q)

Solution:
(a). (PΛQΛR)V(¬PΛRΛQ)V(¬PΛ¬QΛ¬R)
       ↔ ((QΛR)Λ(PV¬P))V(¬PΛ¬QΛ¬R)
       ↔ ((QΛR)ΛT)V(¬PΛ¬QΛ¬R)
       ↔ (QΛR)V(¬PΛ¬QΛ¬R)
       ↔ (¬PVQ)Λ(QV¬Q)Λ(QV¬R)Λ(¬PV¬R)Λ(¬QVR)Λ(RV¬R)
       ↔ (¬PVQ)ΛTΛ(QV¬R)Λ(¬PV¬R)Λ(¬QVR)ΛT
       ↔ (¬PVQ)Λ(QV¬R)Λ(¬PV¬R)Λ(¬QVR)
       ↔ (¬PVQVF)Λ(FVQV¬R)Λ(¬PV¬RVF)Λ(FV¬QVR)
       ↔((¬PVQ)V(RΛ¬R))Λ((PΛ¬P)V(QV¬R))Λ((¬PV¬R)V(QV¬Q))Λ((PΛ¬P)V(¬QVR))
    ↔(¬PVQVR)Λ(¬PVQV¬R)Λ(PVQV¬R)Λ(¬PVQV¬R)Λ(¬PVQV¬R)Λ(¬PV¬QVR)
Λ(PV¬QVR)Λ(¬PV¬QVR)
       ↔(¬PVQVR)Λ(¬PVQV¬R)Λ(PVQV¬R)Λ(¬PV¬QVR) Λ(PV¬QVR)
       ↔(PVQV¬R)Λ(PV¬QVR)Λ(¬PVQVR)Λ(¬PVQV¬R) Λ(¬PV¬QVR)
       ↔Π 1,2,4,5,6


(c). (PΛQ)V(¬PΛQ)V(PΛ¬Q)
      ↔(PΛQ)V(PΛ¬Q)V(¬PΛQ)
      ↔(PΛ(QV¬Q))V(¬PΛQ)
      ↔(PΛT)V(¬PΛQ)
      ↔PV(¬PΛQ)
      ↔(PV¬P)Λ(PVQ)
      ↔TΛ(PVQ)
      ↔(PVQ)
      ↔Π 0


3.  Obtain the principal disjunctive and conjunctive normal forms of the following formulas.
     (b). QΛ(PV¬Q)
     (e).  P→ (PΛ(Q→ P))
     (f).  (Q→ P)Λ(¬PΛQ)
     Which of the above formulas are tautologies?

Solution:
(b). QΛ(PV¬Q)
Principal disjunctive normal forms
QΛ(PV¬Q)
      ↔(QΛP)V(QΛ¬Q)
      ↔(QΛP)VF
↔(QΛP)
↔(PΛQ)  (Tautologi)




Principal conjunctive normal forms
QΛ(PV¬Q)
↔(QΛT)Λ(PV¬Q)
↔(QΛ(PV¬P))Λ(PV¬Q)
↔(QVP)Λ(QV¬P)Λ(PV¬Q)
↔(PVQ)Λ(PV¬Q)Λ(¬PVQ)  (Tautologi)

(e). P→ (PΛ(Q→ P))
Principal disjunctive normal forms
P→ (PΛ(Q→ P))
↔ P→ (PΛ(¬QVP))
↔ ¬PV(PΛ(¬QVP))
↔ (¬PVP)Λ(¬PV(¬QVP))
↔ TΛ((PV¬P)V(¬PV¬Q))
↔ TΛ(TV(¬PV¬Q))
↔ TΛT
↔ T (Tautologi)

Principal conjunctive normal forms
P→ (PΛ(Q→ P))
↔ ¬PV(PΛ(¬QVP))
↔ ¬PV((PΛ¬Q)V(PΛP))
↔ ¬PV((PΛ¬Q)VP)
↔ (¬PΛT)V(PΛ¬Q)V(PΛT)
↔ (¬PΛ(QV¬Q))V(PΛ¬Q)V(PΛ(QV¬Q))
↔ (¬PΛQ)V(¬PΛ¬Q)V(PΛ¬Q)V(PΛQ)V(PΛ¬Q)
↔ (PΛQ)V(PΛ¬Q)V(¬PΛQ)V(¬PΛ¬Q)  (tautologi)

(f). (Q→ P)Λ(¬PΛQ)
Principal disjunctive normal forms
(Q→ P)Λ(¬PΛQ)
↔(¬QVP)Λ(¬PΛQ)
↔(¬QΛ(¬PΛQ))V(PΛ(¬PΛQ))
↔(¬QΛ¬PΛQ)V(PΛ¬PΛQ)
↔( ¬PΛQΛ¬Q)V(PΛ¬PΛQ)
↔( ¬PΛF)V(FΛQ)
↔FVF
↔F (Kontradiksi)

Principal conjunctive normal forms
(Q→ P)Λ(¬PΛQ)
↔(¬QVP)Λ(¬PΛQ)
↔(¬QVP)Λ(¬PVF)Λ(FVQ)
↔(¬QVP)Λ((¬PV(QΛ¬Q)Λ((PΛ¬P)VQ)
↔(¬QVP)Λ(¬PVQ)Λ(¬PV¬Q)Λ(PVQ)Λ(¬PVQ)
↔(PVQ)Λ(PV¬Q)Λ(¬PVQ)Λ(¬PV¬Q)   (Kontradiksi)

No comments:

Post a Comment