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)

Matematika Diskrit



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         
10
 
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.



 








Jawab :









 








Panjang lintasan dari a sampai z adalah 1 + 10 + 5 = 16





 








Panjang lintasan dari a sampai z adalah 10 + 4 + 2 = 16








10
 
 









Panjang lintasan dari a sampai z adalah 6 + 3 + 8 = 17




 







Panjang lintasan dari a sampai z adalah 3 + 8 + 5 = 16




 







Panjang lintasan dari a sampai z adalah 1 + 10 + 1 + 2 + 2  = 16










 









































5.19          G
5.20          G
5.21          G
5.22          G
5.23          G

Friday, April 26, 2013

Soal Subgrup dan Koset



SOAL LATIHAN  ;

1.   Tunjukkan  apakah  (20) subgrup  U(20).

2.    Misalkan   G grup dari bilangan bulat dalam penjumlahan.  H subset berisi kelipatan
       dari  5   cek H subgrup G.

3.   Misalkan   K = { 1, -1. i ,-i } dengan  i =    maka dapat diperiksa bahwa K
      terhadap perkalian  pada bilangan komplek  membentuk grup
      Tulislah semua subgrup dari grup K.

4.   Misalkan  G grup dengan 2x 2  matrik    dengan ad – bc ≠  0   pada operasi
      perkalian.  Msialkan H  = {   G  |  ad ≠ 0 }
      Tunjukkan   H  subgrup  G.

5.   Misalkam  H grup  dari soal nomor 4   dan misalkan  K = {} maka
      K  subgrup  H.
 
 KOSET

6.   Misalkan   K = { 1, -1. i ,-i } dengan  i =    atau   i   =  -1 maka  (K, x)
      merupakan  grup  dengan elemen identitas 1.  misalkan H = ( 1,-1)  maka
      H subgrup K .  Tunjukkan koset kanan dari H dalam K   dan koset kiri dari
      H dalam K.

7.   Grup (Z ,+ )   dan  H  subgrup Z,  H = {0 , 3}
      Tunjukkan koset kanan dan koset kiri  dari  H  dalam Z

8.   Tuliskan semua koset kanan  H subgrup G  dimana
       G = (a)  adalah grup siklis  berorder  10  dan
       H = (a) adalah  subgrup G generator  a

9 .   Tuliskan semua koset kanan  H subgrup G  dimana
       G = (a)  adalah grup siklis  berorder  10  dan
       H = (a) adalah  subgrup G generator  a5



10.   Tuliskan semua koset kiri  H subgrup G  dimana
        G = (a)  adalah grup siklis  berorder  10  dan
        H = (a) adalah  subgrup G generator  a


11.   Tuliskan semua koset kanan  H subgrup G  dimana
         G =  A(S)  ,  S = { x, x, x } dan  H = { σ G |  x σ =  x }


12.   Tuliskan semua koset kiri  H subgrup G  dimana
         G =  A(S)  ,  S = { x, x, x } dan  H = { σ G |  x σ =  x }