Tugas Akhir M1 Profesional Prodi Matematika.docx

TUGAS M1 PROFESIONAL 1) Berdasarkan penjelasan tentang tautologi dan kontradiksi. Selesaikan masalah berikut ini dengan menuliskan langkah-langkahnya. a) (𝑝 ⇒ 𝑞) ∧ (𝑟 ⇒ 𝑞)) ⇒ ((𝑝 ⇒ 𝑟) ⇒ 𝑞) b) 𝑝 ∧ (~𝑝 ∧ 𝑞) Penyelesaian : a)

(𝒑 ⇒ 𝒒) ∧ (𝒓 ⇒ 𝒒)) ⇒ ((𝒑 ⇒ 𝒓) ⇒ 𝒒) (𝒑 ⇒ 𝒒)

(𝒓 ⇒ 𝒒)

(𝒑 ⇒ 𝒒) ∧ (𝒓 ⇒ 𝒒)

(𝒑 ⇒ 𝒓)

((𝒑 ⇒ 𝒓) ⇒ 𝒒)

((𝒑 ⇒ 𝒒) ∧ (𝒓 ⇒ 𝒒) ⇒ ((𝒑 ⇒ 𝒓) ⇒ 𝒒)

B B

B

B

B

B

B

B

B

B

S

B

B

B

S

B

B

B

S

B

S

S

S

B

S

B

B

S

S

S

B

S

S

B

B

S S S

B B B S S B

B B B

B B S

B B S

B B B

B B S

B B B

S

S

B

B

B

B

S

S

𝒑

𝒒

B

𝒓

S

Berdasarkan tabel diatas, maka pernyataan ((𝑝 ⇒ 𝑞) ∧ (𝑟 ⇒ 𝑞) ⇒ ((𝑝 ⇒ 𝑟) ⇒ 𝑞) bukan tautologi dan bukan kontradiksi b)

𝒑 ∧ (~𝒑 ∧ 𝒒) 𝒑

𝒒

~𝒑

(~𝒑 ∧ 𝒒)

𝒑 ∧ (~𝒑 ∧ 𝒒)

B

B

S

S

S

B

S

S

S

S

S

B

B

B

S

S

S

B

S

S

Berdasarkan tabel di atas, maka pernyataan 𝒑 ∧ (~𝒑 ∧ 𝒒) merupakan kontradiksi.

2. Buktikan keabsahan argumen berikut dengan menuliskan langkah dan aturan-aturan yang digunakan untuk pembuktian (𝑝 ∧ 𝑞) ⇒ (𝑟 ∧ 𝑠) ~𝒓 ∨ ~𝒔 ∴ ~𝒑 ∨ ~𝒒

Pembuktian 1

(𝑝 ∧ 𝑞) ⇒ (𝑟 ∧ 𝑠)

(Premis 1)

2

~𝒓 ∨ ~𝒔

(Premis 2)

3

~(𝒓 ∧ 𝒔)

(2 Hukum de Morgan)

4

~( 𝒑 ∧ 𝒒 )

(1,3 Modus Tollens)

5

~𝒑 ∨ ~𝒒

(4 Hukum de Morgan)

Jadi argumen tersebut sah/valid (Terbukti)

3. Tentukan banyaknya solusi dari persamaan 𝑥1 + 𝑥2 + 𝑥3 = 20 dengan syarat 𝑥1 ≥ 20 0 ≤ 𝑥2 ≤ 3 dan 3 ≤ 𝑥3 ≤ 5. (selesaikan dengan fungsi pembangkit). Penyelesaian : Banyaknya solusi dari persamaan 𝑥1 + 𝑥2 + 𝑥3 = 20 dapat dinyatakan oleh koefisien 𝑥 20 dalam ekspansi: 𝐺(𝑥) = (𝑥 2 + 𝑥 3 + ⋯ )(𝑥 0 + 𝑥1 + 𝑥 2 + 𝑥 3 )(𝑥 3 + 𝑥 4 + 𝑥 5 ) 𝐺(𝑥) = 𝑥 2 (1 + 𝑥1 + ⋯ )(1 + 𝑥1 + 𝑥 2 + 𝑥 3 )𝑥 3 (1 + 𝑥1 + 𝑥 2 ) 𝐺(𝑥) = 𝑥 5 (1 + 𝑥1 + ⋯ )(1 + 𝑥1 + 𝑥 2 + 𝑥 3 )(1 + 𝑥1 + 𝑥 2 ) 1−𝑥 4

1

1−𝑥 3

𝐺(𝑥) = 𝑥 5 (1−𝑥) ( 1−𝑥 ) ( 1−𝑥 ) 1

𝐺(𝑥) = 𝑥 5 ((1−𝑥)3 ) (1 − 𝑥 4 )(1 − 𝑥 3 ) 1

𝐺(𝑥) = 𝑥 5 ((1−𝑥)3 ) (1 − 𝑥 4 − 𝑥 3 + 𝑥 7 ) 1

𝐺(𝑥) = 𝑥 5 (1 − 𝑥 4 − 𝑥 3 + 𝑥 7 ) ((1−𝑥)3 ) 𝐺(𝑥) = 𝑥 5 (1 − 𝑥 3 − 𝑥 4 + 𝑥 7 ) ((

1

1−𝑥)3

)

1

𝐺(𝑥) = (𝑥 5 − 𝑥 8 − 𝑥 9 + 𝑥12 ) ((1−𝑥)3 ) Koefisien 𝑥 20 yaitu : 𝑥 5 ∙ 𝑥15 = ∑ (

17! 16×17 17 3 + 15 − 1 15 ) 𝑥 = ( ) = 15!2! = 2 = 136 15 15

𝑥 8 ∙ 𝑥12 = ∑ (

14! 13×14 3 + 12 − 1 12 14 ) 𝑥 = ( ) = 12!2! = 2 = 91 12 12

13! 12×13 3 + 11 − 1 11 13 )𝑥 = ( ) = = = 78 11!2! 2 11 11

𝑥 9 ∙ 𝑥11 = ∑ (

𝑥12 ∙ 𝑥 8 = ∑ (

10! 9×10 3+8−1 8 10 )𝑥 = ( ) = = = 45 8!2! 2 8 8

Banyak solusi koefisien 𝑥 20 = 136 − 91 − 78 + 45 = 𝟏𝟐 solusi

4. Perhatikan graf berikut!

Apakah graf pada gambar di atas merupakan graf bipartisi? Apakah graf tersebut merupakan graf bipartisi lengkap? Jelaskan jawaban Anda! Penyelesaian :

𝑽𝟏

𝑽𝟐

a

b

c

d

f

e

h

g

Dari diagram di atas, dapat disimpulkan bahwa gambar tersebut merupakan graf bipartisi karena graf bipartisi adalah suatu graf yang himpunan titiknya dapat dikelompokkan menjadi dua himpunan bagian misal 𝑉1 dan 𝑉2 sedemikian sehingga setiap sisi di dalam graf tersebut menghubungkan sebuah titik di 𝑉1 ke sebuah titik di 𝑉2 . Tapi bukan merupakan graf bipartisi lengkap karena setiap titik di 𝑉1 tidak terhubung dengan semua titik di 𝑉2. 5. Perhatikan graf berikut!

Tersedia enam warna berbeda untuk mewarnai semua titik sehingga dua titik yang bertetangga (adjacent) berbeda warna. Ada berapa cara mewarnai semua titik tersebut ?

Penyelesaian :

Minimal pewarnaan graph ada 4 warna. Karena tersedia 6 warna, maka banyaknya cara mewarnai semua titik adalah : 6!

Untuk mewarnai titik a,b,e,f dapat dilakukan dengan 𝑃(6,4) = 2! = 320 cara. Sedangkan untuk menentukan warna titik d dan c dilakukan dengan 5 𝑥 4 = 20 𝑐𝑎𝑟𝑎 sehingga banyak kemungkinan adalah 320 𝑥 20 = 6400 𝑐𝑎𝑟𝑎 , ditambah kasus ketika titik d berwarna sama dengan titik b yaitu 5 𝑥 𝑃(5,3) = 5 𝑥 300 = 6700 cara.

5! 2!

= 300, sehingga total kemungkinan adalah 6400 +