Everything (Mustikasari): May 2013

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)

5.17 Graf dalam gambar 5P.5 menunjukkan saluran-saluran komunikasi dan tertahannya waktu komunikasi di dalam saluran di antara delapan pusat komunikasi. Pusat komunikasi dipresentasikan oleh verteks, saluran dipresentasikan oleh rusuk, dan tertahannya waktu komunikasi ( dalam menit ) dalam setiap saluran dipresentasikan oleh pembobot rusuk bersangkutan. Misalkan bahwa pada jam 15.00, pusat komunikasi a memancarkan ke semua salurannya berita bahwa seseorang telah menemukan cara untuk membuat perangkap tikus yang lebih baik. Pusat-pusat komunikasi lainnya segera menyebarluaskan berita ini ke semua salurannya begitu mereka menerimanya. Untuk pusat-pusat komunikasi b, c, d, e, f, g, dan h, tentukan kapan pertama kali mereka menerima berita ini ?

Gambar 5P.5

Jawab :

Lintasannya adalah a ke b = 3

Jadi : Pusat komunikasi b menerima berita pertama kali pada pukul 15.03

Lintasannya adalah a,b,c = 3 + 1 = 4

Jadi : Pusat komunikasi c menerima berita pertama kali pada pukul 15.04

Lintasannya adalah a,b,f,d = 3 + 1 + 1 = 5

Jadi : Pusat komunikasi d menerima berita pertama kali pada pukul 15.05

Lintasannya adalah a,b,f,e = 3 + 1 + 2 = 6

Jadi : Pusat komunikasi e menerima berita pertama kali pada pukul 15.06

Lintasannya adalah a,b,f = 3 + 1 = 4

Jadi : Pusat komunikasi f menerima berita pertama kali pada pukul 15.04

Lintasannya adalah a,b,f,d,g = 3 + 1 + 1 + 2 = 7

Jadi : Pusat komunikasi g menerima berita pertama kali pada pukul 15.07

Lintasannya adalah a,b,f,g ,h = 3 + 1 + 4 + 1 = 9

Jadi : Pusat komunikasi h menerima berita pertama kali pada pukul 15.09

5.18

Gunakan algoritma yang diberikan di dalam Pasal 5.5 untuk menentukan suatu lintasan terpendek antara a dan z pada graf dalam gambar 5P.6, jika bilangan pada setiap rusuk menyatakan jarak antara kedua verteks bersangkutan.