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)

1 comment:

  1. Las Vegas (NV) Casinos | Mapyro
    At its best, 평택 출장마사지 these two casinos are 동해 출장샵 home to several things 과천 출장샵 that most casinos don't know about. Las Vegas is the place to go 서귀포 출장샵 if you want to play in a place 문경 출장샵

    ReplyDelete