1.1.1 bab i pendahuluan teori himpunan … matematika institut teknologi telkom | 2 2. notasi khusus...

64
LOGIKA MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 1 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN 1.1 DEFINISI HIMPUNAN Pengertian Himpunan adalah kumpulan objek yang didefinisikan secara jelas dalam sembarang urutan atau keberurutan objek-objek anggotanya tidak diperhatikan. Objek-objek itu disebut elemen-elemen atau anggota-anggota himpunan Anggota Himpunan Himpunan memiliki objek yang disebut anggota atau elemen himpunan. Jika himpunan A memiliki x sebagai anggotanya maka dapat dituliskan sebagai A x , dibaca ”x adalah anggota himpunan Aatau “x adalah elemen dari himpunan A”. Jika objek y bukan elemen atau anggota dari himpunan A maka dapat ditulis A y . Himpunan Hingga dan Takhingga (Finite and Infinite Set) Himpunan hingga (Finite set) merupakan himpunan yang berisi sejumlah hingga elemen yang berbeda selain itu disebut sebagai himpunan tak hingga (Infinite set). 1.2 NOTASI Notasi Himpunan Himpunan dinyatakan dengan huruf besar : A, B, C, D, E, … . Sedangkan elemen-elemen dalam suatu himpunan dinyatakan dengan huruf kecil : a, b, c, d, e, … Contoh : 1. Himpunan A terdiri atas bilangan 2, 4, 6, 8, maka dapat dituliskan sebagai : A = {2, 4, 6, 8}; elemen-elemen didaftarkan dengan dipisahkan tanda koma (‘,’) dan dalam tanda kurung kurawal {}. 2. Himpunan B adalah himpunan bilangan genap positif, maka dapat dituliskan dengan : B = {x | x genap > 0} Cara Penulisan Himpunan Cara penulisan himpunan terdiri atas 3 cara, yaitu : 1. Enumerasi Dengan menyebutkan semua (satu per satu) elemen himpunan Contoh: B = {1,2,3,4,5} D = {apel, mangga, jambu}

Upload: lynhi

Post on 11-Apr-2019

218 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 1

1.1.1 BAB I

PENDAHULUAN TEORI HIMPUNAN

1.1 DEFINISI HIMPUNAN Pengertian Himpunan adalah kumpulan objek yang didefinisikan secara jelas dalam sembarang urutan atau keberurutan objek-objek anggotanya tidak diperhatikan. Objek-objek itu disebut elemen-elemen atau anggota-anggota himpunan Anggota Himpunan Himpunan memiliki objek yang disebut anggota atau elemen himpunan. Jika himpunan A memiliki x sebagai anggotanya maka dapat dituliskan sebagai Ax∈ , dibaca ”x adalah anggota himpunan A” atau “x adalah elemen dari himpunan A”. Jika objek y bukan elemen atau anggota dari himpunan A maka dapat ditulis Ay∉ . Himpunan Hingga dan Takhingga (Finite and Infinite Set) Himpunan hingga (Finite set) merupakan himpunan yang berisi sejumlah hingga elemen yang berbeda selain itu disebut sebagai himpunan tak hingga (Infinite set). 1.2 NOTASI

Notasi Himpunan Himpunan dinyatakan dengan huruf besar : A, B, C, D, E, … . Sedangkan elemen-elemen dalam suatu himpunan dinyatakan dengan huruf kecil : a, b, c, d, e, …

Contoh : 1. Himpunan A terdiri atas bilangan 2, 4, 6, 8, maka dapat dituliskan sebagai :

A = {2, 4, 6, 8}; elemen-elemen didaftarkan dengan dipisahkan tanda koma (‘,’) dan dalam tanda kurung kurawal {}.

2. Himpunan B adalah himpunan bilangan genap positif, maka dapat dituliskan dengan : B = {x | x genap > 0}

Cara Penulisan Himpunan Cara penulisan himpunan terdiri atas 3 cara, yaitu : 1. Enumerasi

Dengan menyebutkan semua (satu per satu) elemen himpunan Contoh: B = {1,2,3,4,5} D = {apel, mangga, jambu}

Page 2: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 2

2. Notasi khusus himpunan atau simbol standar

Dengan simbol-simbol standar yang biasa digunakan untuk mewakili suatu himpunan, antara lain : Contoh : P = Himpunan bilangan integer positif = {1,2,3, …} Q = Himpunan bilangan natural = {0,1,2, …} Z = Himpunan bilangan rasional = {… , -2, -1, 0, 1, 2, …}

3. Notasi Pembentuk Himpunan

Dengan menyebutkan sifat atau syarat keanggotaan dari himpunan. Contoh :

B = { x | x ≤ 5 , x ∈ A } Aturan dalam penulisan syarat keanggotaan himpunan : • Bagian kiri tanda ‘|’ melambangkan elemen himpunan • Tanda ‘|’ dibaca sebagai dimana atau sedemikian sehingga • Bagian di kanan tanda ‘|’ menunjukkan syarat keanggotaan himpunan • Setiap tanda ‘,’ dibaca sebagai dan

4. Diagram Venn

Dengan menggambarkan keberadaan himpunan terhadap himpunan lain. Himpunan Semesta (S) digambarkan sebagai suatu segi empat sedangkan himpunan lain digambarkan sebagai lingkaran. Contoh : S = {1,2, … , 7, 8} A = {1,2,3,5} B = {2,5,6,8}

S A B 1 2 6 3 5 8

Page 3: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 3

Atau dengan area himpunan

Himpunan Area A 1,2 B 2,3 A ∩ B 2 A ∪ B 1, 2, 3

Definisi-Definisi a. Himpunan semesta/universal

Simbol : S atau U

b. Himpunan bagian (Subset) A merupakan himpunan bagian dari B jika dan hanya jika setiap elemen A juga merupakan elemen B. Simbol : A ⊆ B Contoh : A = Bilangan Integer dan B = Bilangan Real Maka A ⊆ B Catatan : ∅ ⊆ A dan A ⊆ A

c. Himpunan Kosong (Null Set) Himpunan kosong merupakan himpunan yang tidak memiliki elemen atau anggota. Himpunan kosong selalu merupakan salah satu himpunan bagiannya. Simbol : { } atau ∅ Contoh : F = { x | x < x }

S A B

1 2 3

Page 4: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 4

d. Himpunan Kuasa (Power Set)

Himpunan dari seluruh himpunan bagian dari suatu himpunan Contoh : Himpunan bagian dari A = {1, 2} adalah ∅, {1}, {2}, {1, 2} maka Himpunan kuasa dari A = {∅, {1}, {2}, {1, 2}}

e. Himpunan bagian yang sebenarnya ( Proper Subset )

A himpunan bagian yang sebenarnya dari B bila tiap elemen A adalah elemen B dan B≠∅, tapi himpunan A tidak sama dengan B atau bila A ⊆ B dan A ≠ B Contoh : A = {1, 2, 3, 4} B = {0, 1, 2, 3, 4} Maka A merupakan proper subset dari B

f. Himpunan yang sama

Himpunan A dikatakan sama dengan himpunan B jika dan hanya jika setiap elemen A merupakan elemen B dan sebaliknya setiap elemen B juga merupakan elemen A.

Simbol : A = B ↔ A ⊆ B dan B ⊆ A Contoh : A = {0, 1, 2, 3} B = {0, 1, 2, 3} Maka A = B

g. Himpunan yang ekivalen

Himpunan A dikatakan ekivalen dengan himpunan B jika dan hanya jika kardinal dari kedua himupunan tersebut sama. Simbol : A ∼ B Contoh : A = {0, 1, 2, 3, 4} | A | = 5 B = {5, 6, 7, 8, 9} | B | = 5 Maka A ~ B

h. Himpunan Saling Lepas ( Disjoint ) Dua himupunan A dan B dikatakan saling lepas jika tidak memiliki elemen yang sama. Contoh : A = { x | x < 8, x ∈ P } B = { 10, 20, 30, … } Maka A dan B adalah himpunan yang saling lepas.

Page 5: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 5

1.3 OPERASI-OPERASI DASAR HIMPUNAN

Union (Gabungan) Union himpunan A dan himpunan B adalah himpunan dari semua elemen yang termasuk dalam A atau B atau keduanya. Union teresebut dapat dinyatakan sebagai : A ∪ B : dibaca A Union B Contoh : A = { a, b, c, d } dan B = {e, f, g }, maka A ∪ B = { a, b, c, d, e, f, g } Union A dan B dapat didefinisikan secara ringkas sebagai berikut : A ∪ B = { x | x ∈ A atau x ∈ B }

Berlaku hukum : A ∪ B = B ∪ A Subhimpunan : A dan B keduanya selalu berupa subhimpunan dari A ∪ B, yaitu : A ⊂ (A ∪ B) dan B ⊂ (A ∪ B) Irisan (Perpotongan) Irisan himpunan A dengan himpunan B adalah himpunan dari elemen-elemen yang dimiliki bersama oleh A dan B, yatu elemen-elemen yang termasuk di A dan juga termasuk di B. Irisan dinyatakan dengan : A ∩ B dibaca A “irisan” B Contoh A = { a, b, c, d } dan B = { b, d, f, g } maka A ∩ B = { b, d } Dapat dinyatakan dengan : A ∩ B = { x | x ∈ A dan x ∈ B } Setiap himpunan A dan himpunan B mengandung A ∩ B sebagai subhimpunan, yaitu : (A ∩ B) ⊂ A dan (A ∩ B) ⊂ B Jika himpunan A dan himpunan B tidak mempunyai elemen-elemen yang dimiliki bersama, berarti A dan B terpisah, maka irisan dari keduanya adalah himpunan kosong : A ∩ B = ∅

Page 6: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 6

Selisih Selisih himpunan A dan himpunan B adalah himpunan dari elemen-elemen yang termasuk A tetapi tidak termasuk B, dan dinyatakan dengan : A – B dibaca “selisih A dan B’ atau ‘A kurang B’ Dapat dinyakan dengan : A – B = { x | x ∈ A dan x ∉ B } Himpunan A mengandung A – B sebagai subhimpunan, berarti : (A – B) ⊂ A Komplemen Komplemen dari himpunan A adalah himpunan dari elemen-elemen yang tidak termasuk A, yaitu selisih dari himpunan semesta S dan A. Komplemen dapat didefinisikan secara ringkas sebagai berikut : A’ = { x | x ∈ S dan x ∉ A } atau A’ = { x | x ∉ A } Union sebarang himpunan A dan komplemennya A’ adalah himpunan semesta, yaitu : A ∪ A’ = S A ∩ A’ = ∅ Komplemen dari komplemen himpunan A adalah himpunan A sendiri : (A’)’ = A Selisih dari A dan B sama dengan irisan A dan komplemen B; A – B = A ∩ B’ Perbedaan Simetris ( Symmetric Difference ) Perbedaan simetris dari himpunan A dan B adalah sutau himpunan yang elemennya ada pada himpunan A atau B tetapi tidak pada keduanya. Simbol : A ∆ B = A ⊕ B = ( A ∪ B ) – ( A ∩ B ) = ( A – B ) ∪ ( B – A ) Contoh : A = { 2, 4, 6 } ; B = { 2, 3, 5 } A ⊕ B = { 3, 4, 5, 6 } 1.4 ALJABAR HIMPUNAN Aljabar himpunan mempunyai sifat yang analogi dengan aljabar aritmetika. Operasi pada aljabar aritmetika adalah penambahan (+) dan perkalian (•). Sifat-sifat operasi pada aljbar aritmetika : Misal a, b, c, adalah sembarang bilangan 1. Tertutup ( Closure )

A1 : a + b adalah bilangan M1 : a • b adalah bilangan

Page 7: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 7

2. Assosiatif A2 : ( a + b ) + c = a + ( b + c ) M2 : (a • b) • c = a • ( b • c )

3. Identitas A3 : Ada sebuah bilangan unik yaitu nol (0) sedemikian sehingga untuk semua bilangan berlaku bahwa a + 0 = 0 + a = a M3 : Ada sebuah bilangan unik yaitu 1 sedemikian sehingga untuk semua bilangan berlaku bahwa a • 1 = 1 • a = a

4. Invers A4 : Untuk setiap bilangan a terdapat bilangan unik (-a) sedemikian sehingga berlaku a + (-a) = (-a) + a = 0 M4 : Untuk setiap bilangan a ≠ 0, terdapat bilangan unik ( a 1 ) sedemikian sehingga berlaku a • a 1 = a 1 • a = 1

5. Komutatif A5 : a + b = b + a M6 : a • b = b • a

6. Distributif A6 : a • ( b + c ) = ( a b ) + ( a c ) M6 : (a + b) • c = ( a c ) + ( b c )

Sifat-sifat tersebut berlaku pula pada aljabar himpunan dimana terdapat perubahan :

• Operator penjumlahan (+) diganti dengan operator perbedaan simetris (∆ ) • Operator perkalian (•) diganti dengan operator irisan (∩) • Sifat M4 bilangan unik nol (0) diganti himpunan ∅, bilangan unik 1 diganti

himpunan semesta S • A4 Bilangan unik (-a) diganti dengan A’, sedemikian sehingga berlaku :

A ∆ A’ = S A ∩ A = ∅

1.5 TRANSISI DARI HIMPUNAN KE LOGIKA Pada dasarnya Aljabar Boolean memberikan perantaraan antara Aljabar himpunan dan Logika sebagai berikut : • Operasi-operasi dasar dalam aljabar himpunan dengan 2 elemen yaitu ∅ dan A

∅ A ∅ A ∅ ∅ A ∅ ∅ ∅ A A A A ∅ A

α ∪ β α ∩ β Jika diinterpretasikan sebagai aljabar boolean maka kedua elemen pada aljabar himpunan berkorespodensi dengan elemen pada aljabar Boolean yaitu 0 dan 1

Page 8: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 8

• Operasi-operasi dasar dalam Aljabar Boolean dengan 2 elemen yaitu : 0 dan 1 0 1 0 1

0 0 1 0 0 0 1 1 1 1 0 1

α + β α • β • Operasi-operasi dasar dalam Logika (Kalkulus Proposisi) melibatkan elemen False dan

True False True False True

False False True False False True True True True True False True

α ∨ β α ∧ β

Page 9: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 9

1.6 SOAL LATIHAN 1. Tentukan Elemen dari Himpunan A = {x | x2 = 11x – 30 OR 4 – x > 0}, dimana U

adalah : a. Himpunan Bilangan Riil b. Himpunan Bilangan Bulat c. Himpunan Bilangan Bulat positif d. Himpunan Bilangan Bulat negatif e. Himpunan Bilangan Bulat positif kurang dari 10

2. Tentukan Symmetric Difference dari pasangan himpunan berikut ini :

a. A = {2, 5, 8} B = {1,2, 5, 10} b. A = {1, 3, 5 } B = {1, 2, 4, 7} c. A = {a, *, $ } B = {1, 2, 3} d. A = ∅ B = {a, *, $ } e. A = {1, 3, 5 } B = {2, 4, 6}

3. Tunjukkan persamaan berikut ini dengan menggunakan Diagram Venn :

a. A ∩ (B ∩ C) = (A ∩ B) ∩ C b. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) c. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) d. A ∩ (B ⊕ C) = (A ∩ B) ⊕ (A ∩ C)

4. Diketahui :

A – B = {0, 3} A ⊕ B = {0, 1, 3, 5, 6} A ∪ B = {0, 1, 2, 3, 5, 6, 7, 11} Tentukan Elemen dari Himpunan A dan Himpunan B !

5. Diketahui :

A – B = {1, 5, 7, 8} B – A = {2, 10} A ∩ B = {3, 6, 9} Tentukan Elemen dari Himpunan A dan Himpunan B !

Page 10: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 10

BAB II ALJABAR BOOLEAN

2.1 DEFINISI

Aljabar Boolean adalah sistem aljabar yang berisi Himpunan Semesta (set S) dengan dua operasi penjumlahan (+) dan perkalian (.) yang didefinisikan pada set itu sehingga memenuhi ketentuan berikut ini :

• Aturan A1 sampai dengan A5, M1 sampai M3, M5, D1, dan D2 • Setiap elemen adalah “idempotent”, yaitu Jika a ∈ S, maka a.a = a • setiap elemen a, b, c dari S mempunyai sifat-sifat atau aksioma-aksioma berikut ini :

2 A1 a + b ∈ S < closure > M2 a.b ∈ S < closure > A2 a + (b + c) = (a + b) + c < asosiatif > M2 a . (b.c) = (a.b).c < asosiatif > A3 Jika 0 ∈ S maka untuk setiap a ∈ S,

adalah a + 0 = 0 + a = a < identitias >

M3 Jika 1 ∈ S maka untuk setiap a ∈ S, Adalah a . 1 = 1 . a = a

< identitas >

A5 a + b = b + a < komutatif > M5 a.b = b.a < komutatif > D1 a.(b+c) = a.b + a.c < distributif > D2 (a + b) . c = a.c + b.c < distributif > D3 a + (b.c) = (a + b) . (a + c) < distributif > D4 (a.b) + c = (a + c) . ( b + c) < distributif > C1 Untuk setiap a ∈ S, dan a’ ∈ S, maka a + a’ =

1 dan a . a’ = 0 < komplemen >

2.2 PRINSIP DUALITAS Teorema 2.1 Untuk setiap elemen a, berlaku : a + a = a dan a . a = a Bukti a + a = (a+a) (1) identitas = (a+a) (a+a’) komplemen = a + (a.a’) distributif = a + 0 komplemen = a identitas

Page 11: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 11

a.a = a.a + 0 identitas = a.a + a.a’ komplemen = a. (a.a’) distributif = a.1 komplemen = a identitas Teorema 2.2 Untuk setiap elemen a, berlaku : a + 1 = 1 dan a . 0 = 0 Bukti a + 1 = a + (a+a’) komplemen = (a+a) + a’ asosiatif = a+a’ teorema 1a = 1 komplemen a . 0 = a.(a.a’) komplemen = (a.a).a’ asosiatif = a.a’ idempoten = 0 komplemen Teorema 2.3 (Hukum Penyerapan) Untuk setiap elemen a dan b, berlaku : a + a.b = a dan a.(a+b) = 1 Bukti a+ab = a.1 + a.b Identitas = a . (1+b) distributif = a + 1 teorema 2a = a identitas a. (a+b)= a.a + a.b distributif = a+ab idempoten = a.1 + ab identitas = a. (1+b) distributif = a.1 teorema 2a = a identitas

Page 12: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 12

Teorema 2.4 (Hukum de Morgan) Untuk setiap elemen a dan b, berlaku : (a.b)’ = a’ + b’ dan (a+b)’ = a’b’ Bukti (a.b)’ = a’ + b’ Diketahui : (ab) (ab)’ = 0 Diperlihatkan : (ab) (a’+b’) = 0 (ab) (a’+b’) = aba’ + abb’ distributif = 0.b + a.0 komplemen = 0 + 0 teorema 2b = 0 identitas (a + b)’ = a’b’ Diketahui : (ab) + (ab)’ = 1 Diperlihatkan : ab + a’ + b’ = 1 ab + (a’ + b’) = ( a + a’ + b’) (b + a’ + b’) Teorema 2.5 0’ = 1 dan 1’ = 0 Teorema 2.6 Jika suatu Aljabar Boolean berisi paling sedikit dua elemen yang berbeda, maka 0 ≠ 1 Definisi x dan y adalah elemen-elemen dari aljabar Boolean. Dinyatakan bahwa: x lebih kecil daripada y (x<= y) jika dan hanya jika x + y = y Teorema 2.7 < = adalah suatu bagian dari urutan Bukti Dari Teorema 2.1 : x + x = x, sehingga x < = x Jika x < = y, maka x + y = y Jika y < = x, maka x = y = y + x = x Sehingga jika x < = y dan y < = x, maka x = y Dapat disimpulkan : x < = y dan y < = z, maka x + y = y dan y + z = z x + z = x + (y + z) = (x + y) + z = y + z = z Sehingga x < = z

Page 13: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 13

Teorema 2.8 Jika x, y, dan x adalah elemen-elemen dari aljabar Boolean, maka < = mempunyai sifat-sifat berikut ini : Jika x < = y dan x < = z, maka x < = yz Jika x < = y, maka x < = y + z untuk elemen z Jika x < = y, maka xz < = y untuk elemen z x < = y jika dan hanya jika y’ < = x’ Bukti x + y = y dan x + z = z, sehingga x + yz = (x + y)(x + z) = yz Jika x + y = y, maka x + (y+z) = (x+y)+z = y + z Dengan hukum penyerapan, xz + x = x atau xz < = x x < = y maka x + y = y dan y’ = (x+y)’ Sehingga y’ + x’ = (x+y)’ + x’ = ((x+y)x)’ dengan hukum penyerapan Konversi (x’)’ = x 2.3 FUNGSI BOOLEAN Misalkan x1, x2, x3, … , xn merupakan variabel-variabel aljabar Boolean. Fungsi Boolean dengan n variable adalah fungsi yang dapat dibentuk dari aturan-aturan berikut : 1. Fungsi Konstan

f(x1, x2, x3, … , xn) = a 2. Fungsi Proyeksi

f(x1, x2, x3, … , xn) = xi I = 1, 2, 3, … , n 3. Fungsi Komplemen

g(x1, x2, x3, … , xn) = (f(x1, x2, x3, … , xn))’ 4. Fungsi Gabungan

h(x1, x2, x3, … , xn) = f(x1, x2, x3, … , xn) + g(x1, x2, x3, … , xn) h(x1, x2, x3, … , xn) = f(x1, x2, x3, … , xn) . g(x1, x2, x3, … , xn)

Catatan Fungsi identitas : fungsi proyeksi satu variabel, dimana f(x) = x Teorema 3.1 Jika f adalah fungsi Boolean dengan satu variabel, maka untuk semua nilai x, adalah f(x) = f(1) x + f(0)x’ Untuk kemungkinan bentuk f : Kemungkinan 1 : f adalah fungsi konstan, f(x) = a f(1)x + f(0)x’ = ax + ax’ = a(x+x’) = a1 = a = f(x) Kemungkinan 2 :

Page 14: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 14

f adalah fungsi identitas f(1)x + f(0)x’ = 1x + 0x’ = x + 0 = x = f(x) Kemungkinan 3 : g(x) = (f(x))’ g(x) = (f(x))’ = (f(1)x + f(0)x’)’ = (f(1)x)’ + (f(0)x’)’ = ((f(1))’ + x’) ((f(0))’ + x) = (f(1))’ (f(0))’ + (f(1))’ x + (f(0))’ x’ + xx’ = (f(1))’ (f(0))’ (1) + (f(1))’ x + (f(0))’ x’ = (f(1))’ (f(0))’ (x + x’) + (f(1))’ x + (f(0))’ x’ = (f(1))’ (f(0))’ x + (f(1))’ x + (f(1))’ (f(0))’ x’ + (f(0))’ x’ = (f(1))’ x + (f(0))’ x’ (Hukum Penyerapan) = g(1)x + g(0)x’ Kemungkinan 4 : h(x) = f(x) + g(x) h(x) = f(x) + g(x) = f(1)x + f(0)x’ + g(1)x + g(0) x’ = (f(1) + g(1)) x + (f(0) + g(0)) x’ = h(1) x + h(0) x’ Kemungkinan 5 : k(x) = f(x) g(x) k(x) = f(x) g(x) = (f(1) x + f(0)x’) (g(1)x +g(0)x’) = f(1)g(1)xx + f(1)g(0)xx’ + f(0)g(1)x’x + f(0)g(0)x’x’ = f(1) g(1) x + f(0)g(0) x’ = k(1)x + k(0)x’ Bentuk diatas adalah bentuk standar fungsi Boolean satu variabel. Dengan cara yang sama, jika f adalah fungsi Boolean dengan dua variabel, maka untuk nilai x dan y bentuk standarnya adalah sebagai berikut : f(x,y) = f(1,1) xy + f(1,0) xy’ + f(0,1) x’y + f(0,0) x’y’ 2.4 BENTUK FUNGSI BOOLEAN Suatu fungsi Boolean dapat dinyatakan dalam bentuk yang berbeda tetapi memiliki arti yang sama. Contoh : f1(x,y) = x’ . y’ f2(x,y) = (x + y)’ f1 dan f1 merupakan bentuk fungsi boolean yang sama, yaitu dengan menggunakan Hukum De Morgan.

Page 15: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 15

Nilai Fungsi Fungsi Boolean dinyatakan nilainya pada setiap variabel yaitu pada setiap kombinasi (0,1). Contoh : Fungsi Boolean f(x,y) = x’y + xy’ + y’ x y x’y xy’ y’ f(x,y)0 0 0 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 0 0 0 0

Cara Representasi Terdapat dua cara merepresentasikan fungsi Boolean yakni dengan cara : aljabar dan table kebenaran. Untuk dapat memahami penggunaannya, perhatikanlah contoh di bawah ini : Contoh : Fungsi f(x,y,z) = xyz’ 1. Aljabar

Representasi secara aljabar adalah f(x,y,z) = xyz’

2. Dengan menggunakan Tabel Kebenaran Dengan menggunakan Tabel Kebenaran, sbb :

x y z xyz’ 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0

Jumlah elemen dalam tabel kebenaran adalah jumlah kombinasi dari nilai variabel-variabelnya, yaitu sejumlah 2n, dimana n adalah banyaknya variabel biner.

Page 16: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 16

Konversi dari Tabel Kebenaran

x y z f(x,y,z) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1

1). f1(x,y,z) = x’y’z + xy’z’ + xyz SOP = m1 + m4 + m7

f1’(x,y,z) = x’y’z’ + x’yz’ + x’yz + xy’z + xyz’ 2). f2(x,y,z) = (x+y+z) (x+y’+z)(x+y’+z’)(x’+y+z’) (x’+y’+z) POS = (f1’(x,y,z))’ = M0 M2 M3 M5 M6

∴F = m1 + m 4 + m7 = M0 . M2 . M3 . M5 . M6

x y z f(x,y,z) 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0

f1(x,y,z) = x’y’z’ + x’y’z + x’yz’ + x’yz + xy’z’ + xyz’ = m0 + m1 + m2 + m3 + m4 + m6

f1’(x,y,z) = xy’z + xyz

f2(x,y,z) = (x’ + y + z’)(x’ + y’ + z’)

= (f1’(x,y,z))’

= M5 . M7

∴F = m0 + m 1 + m2 + m3 + m4 + m6 = M5 . M7 Bentuk (1) dan (2) merupakan fungsi/bentuk standar, yaitu fungsi yang literalnya ditulis lengkap pada tiap suku.

• Bentuk pertama (1) disebut SOP (Sum Of Product) / Minterm • Bentuk kedua (2) disebut POS (Product Of Sum) / Maxterm

Page 17: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 17

Fungsi Boolean yang diekspresikan dalam bentuk SOP atau POS disebut fungsi/bentuk Kanonik. 2.5 BENTUK STANDAR/KANONIK FUNGSI BOOLEAN Jika f adalah fungsi boolean satu variabel maka untuk semua nilai x berlaku : Jika f adalah fungsi boolean dua variabel maka untuk semua nilai x berlaku : Bentuk Standar dan Bentuk Kanonik 2 variabel :

x y Minterm Maxterm Term Nilai Term nilai

0 0 x’y’ m0 x + y M00 1 x’y m1 x + y’ M1 1 0 xy’ m2 x’ + y M2 1 1 xy m3 x’ + y’ M3

3 variabel

x y z Minterm Maxterm Term Nilai Term Nilai

0 0 0 x’y’z’ m0 x + y + z M0 0 0 1 x’yz m1 x + y + z’ M1 0 1 0 x’yz’ m2 x + y’ + z M2 0 1 1 x’yz m3 x + y ‘+ z’ M3 1 0 0 xy’z’ m4 x’ + y + z M4 1 0 1 xy’z m5 x’ + y + z’ M5 1 1 0 xyz’ m6 x’ + y’ + z M6 1 1 1 xyz m7 x’ + y’ + z’ M7

f(x) = f(1) . x + f(0) . x’

f(x,y) = f(0,0) . x’y’ + f(0,1) . x’y + f(1,0) . xy’ + f(1,1) . xy

Page 18: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 18

2.6 KONVERSI KE BENTUK STANDAR DAN KANONIK 1. Cari bentuk standar dari f(x,y) = x’

Jawab : f(x,y) = x’ . 1 identitas = x’ . (y+y’) komplemen = x’y + x’y’ distributif = ∑m(0, 1)

∴Bentuk Standar : f(x,y) = x’y + x’y’ bentuk SOP ∴Bentuk Kanonik : f(x,y) = ∑m(0, 1)

dengan mj’ = Mj

f’(x,y) = x . 1 identitas = x .(y+y’) komplemen = xy + xy’ distributif (f’(x,y))’= (x’+y’)(x’+y)

= ΠM(2, 3) ∴Bentuk Standar : f(x,y) = (x’+y’)(x’+y) bentuk POS ∴Bentuk Kanonik : f(x,y) = ΠM(2, 3)

2. Cari bentuk standar dari f(x,y,z) = y’ + xy + x’yz’

Jawab : f(x,y,z) = y’ + xy + x’yz’ lengkapi literal pada tiap suku = y’(x+x’)(z+z’) + xy(z+z’) + x’yz’ = (xy’ + x’y’)(z+z’) + xyz + xyz’ + x’yz’ f(x,y,z) = xy’z + xy’z’ + x’y’z + x’y’z’ + xyz + xyz’ + x’yz’ = m5 + m4 + m1+ m0 + m7 + m6 + m2

SOP ∴Bentuk Standar : f(x,y,z) = xy’z + xy’z’ + x’y’z + x’y’z’ + xyz + xyz’ + x’yz’ ∴Bentuk Kanonik : f(x,y) = ∑m(0, 1, 2, 4, 5, 6, 7)

atau

POS ∴Bentuk Standar : f(x,y,z) = x + y’ + z’ ∴Bentuk Kanonik : f(x,y) = ΠM(3)

Page 19: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 19

3. Cari bentuk Kanonik dari : f(x,y) = x’y + xy’

Jawab : Tabel Nilainya

x y Minterm Maxterm Term Nilai Value Term Nilai Value

0 0 x’y’ m0 0 x + y M0 0 0 1 x’y m1 1 x + y’ M1 1 1 0 xy’ m2 1 x’ + y M2 1 1 1 xy m3 0 x’ + y’ M3 0

Dari tabel : Nilai 1 : Minterm (SOP) : f(x,y) = m1 + m2 = ∑m(1, 2) Nilai 0 : Maxterm (POS) : f(x,y) = M0 . M3 = ΠM(0, 3) Cara Konversi : f’(x,y) = x’y’ + xy = m0 + m3 dari tabel dual-nya (f’(x,y))’ = (x+y)(x’+y’) f(x,y) = (x+y) (x’+y’) = M0 . M3 dari tabel

4. Cari Bentuk Kanonik dari : f(x,y,z) = x’y’z + xy’z’ + xyz Jawab : Tabel Nilainya

x y z Minterm Maxterm f(x,y,z)

0 0 0 x’y’z’ x + y + z 0 0 0 1 x’yz x + y + z’ 1 0 1 0 x’yz’ x + y’ + z 0 0 1 1 x’yz x + y ‘+ z’ 0 1 0 0 xy’z’ x’ + y + z 1 1 0 1 xy’z x’ + y + z’ 0 1 1 0 xyz’ x’ + y’ + z 0 1 1 1 xyz x’ + y’ + z’ 1

Jadi f(x,y,z) = m1 + m4 + m7 = ∑m(1, 4, 7) = M0 . M2 . M3 . M5. M6 = ΠM(0, 2, 3, 5, 6)

Page 20: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 20

Cara konversi : Dari tabel kebenaran diperoleh : f’(x,y,z) = x’y’z’ + x’yz’ + x’yz + xy’z + xyz’

dual : (f’(x,y,z))’ = (x+y+z)(x+y’+z)(x+y’+z’)(x’+y+z’)(x’+y’+z) f(x,y,z) = (x+y+z)(x+y’+z)(x+y’+z’)(x’+y+z’)(x’+y’+z) dari tabel

2.7 KONVERSI KE BENTUK SOP 1. Nyatakan Fungsi Boolean f(x,y,z) = x + y’z dalam SOP

Jawab : Lengkapi literal untuk setiap suku agar sama f(x,y,z) = x . (y+y’).(z+z’) + (x+x’) . y’z = (xy+xy’)(z+z’) + xy’z + x’y’z = xyz + xyz’ + xy’z + xy’z’ + xy’z + x’y’z = xyz + xyz’ + xy’z + xy’z’ + x’y’z = m7 + m6 + m5 + m4 + m1 = ∑m(1, 4, 5, 6, 7)

2. Nyatakan Fungsi Boolean f(x,y,z) = x’y’z + xz + yz dalam SOP

Jawab : Lengkapi literal untuk setiap suku agar sama f(x,y,z) = x’y’z + xz + yz = x’y’z + x. (y+y’) . z + (x+x’) . yz = x’y’z + xyz + xy’z + xyz + x’yz = m1 + m3 + m5 + m7 = ∑m(1, 3, 5, 7)

3. Nyatakan Fungsi Boolean f(w,x,y,z) = wxy + yz + xy dalam SOP

Jawab ; Lengkapi literal untuk setiap suku agar sama f(w,x,y,z) = wxy + yz + xy = wxy . (z+z’) + (w+w’)(x+x’) . yz + (w+w’) . xy . (z+z’) = wxyz + wxyz’ + (wx+wx’+w’x+w’x’)yz + (wxy+w’xy)(z+z’)

= wxyz + wxyz’ + wxyz + wx’yz + w’xyz + w’x’yz + wxyz + wxyz’ + w’xyz + w’xyz’ = w’x’yz + w’xyz’ + w’xyz + wx’yz + wxyz’ + wxyz

= ∑m(3, 6, 7, 10, 14, 15)

Page 21: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 21

2.8 KONVERSI KE BENTUK POS 1. Nyatakan Fungsi Boolean f(x,y,z) = x y+ x’z dalam POS

Jawab : a) Bentuk fungsi ke POS

f(x,y,z) = xy + x’z = (xy + x’)(xy + z) distributif = (x + x’)(y + x’)(x + z)(y + z) distributif = (x’ + y)(x + z)(y + z) komplemen, identitas

b) Lengkapi literal untuk setiap suku agar sama

Suku-1 x’ + y = x’ + y + z z’ = (x’ + y + z)(x’ + y + z’) Suku-2 x + z = x + z + yy’’ = (x + y + z)(x + y’ + z) Suku-3 y + z = xx’ + y + z = (x + y + z)(x’ + y + z)

c) Semua suku dengan literal lengkap : f(x,y,z) = (xy + x’)(xy + z)

= (x + x’)(y + x’)(x + z)(y + z) = (x’ + y)(x + z)(y + z) = (x’+y+z)(x’+y+z’)(x+y+z)(x+y’+z)(x+y+z)(x’+y+z) = (x+y+z)(x+y’+z)(x’+y+z)(x’+y+z’) = M0 . M2 . M4 . M5 = ΠM(0, 2, 4, 5)

2. Nyatakan Fungsi Boolean f(x,y,z) = (x+z)(y’+z’) dalam POS

Jawab : Fungsi Boolean asumsi sudah dalam bentuk POS f(x,y,z) = (x+z)(y’+z’) lengkapi literal pada tiap suku = (x+yy’+z)(xx’+y’+z’) Identitas, Komplemen = (x+y+z)(x+y’+z)(x+y’+z’)(x’+y’+z’) distributif = M0 . M2 . M3 . M7

Page 22: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 22

2.9 PENYEDERHANAAN FUNGSI BOOLEAN Fungsi Boolean dapat diimplementasikan menjadi sebuah rangkaian logika. Dimana rangkaian logika terdiri atas gerbang-gerbang logika, contoh gerbang AND (Perkalian), gerbang OR (Penjumlahan) dan gerbang INVERTER (Komplemen). Salah satu tujuan dari menyederhanakan Fungsi Boolean adalah untuk meminimasi penggunaan gerbang-gerbang logika pada saat implementasi sehingga membentuk sebuah rangkaian logika. Penyederhanaan Fungsi Boolean menghasilkan bentuk Fungsi yang berbeda (lebih sederhana) tetapi menghasilkan nilai fungsi yang sama. Asumsi yang dipakai dalam penyederhanaan :

1. Bentuk fungsi Boolean paling sederhana adalah SOP 2. Operasi yang digunakan adalah operasi penjumlahan (+), perkalian (.) dan

komplemen (‘) Terdapat tiga cara dalam penyederhanaan fungsi Boolean :

1. Cara Aljabar • Bersifat trial and error tidak ada pegangan • Dalam menyederhanakannya menggunakan aksioma-aksioma dan teorema-

teorema yang ada pada aljabar Boolean. 2. Peta Karnaugh

• Mengacu pada Diagram Venn • Menggunakan bentuk-bentuk peta karnaugh

a). K’Map 2 variabel

0 1 0 1 0 x’y’ x’y 0 m0 m1 1 xy’ xy 1 m2 m3

b) K’Map 3 variabel

00 01 11 10 00 01 11 10 0 x’y’z’ x’y’z x’yz x’yz’ 0 m0 M1 m3 m2 1 xy’z’ xy’z xyz xyz’ 1 m4 M5 m7 m6

x y

x y

x yz x yz

Page 23: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 23

c) K’Map 4 variabel

00 01 11 10 00 01 11 10

00 w’x’y’z’ w’x’y’z w’x’yz w’x’yz’ 00 m0 m1 m3 m2 01 w’xy’z’ w’xy’z w’xyz w’xyz’ 01 m4 m5 m7 m6 11 Wxy’z’ wxy’z wxyz wxyz’ 11 m12 m13 m15 m14 10 wx’y’z’ wx’y’z wx’yz wx’yz’ 10 m8 m9 m11 m10

3. Metode Quine-McCluskey • Penyederhanaan didasarkan pada hukum distribusi • Eliminasi Prime Implicant Redundan Tahapannya : 1. Nyatakan variabel komplemen dengan ‘0’, sebaliknya ‘1’ 2. Kelompokkan suku-suku berdasarkan jumlah ‘1’ 3. Kombinasikan suku-suku tersebut dengan kelompok lain yang jumlah ‘1’ –nya

berbeda satu diperoleh bentuk prime yang lebih sederhana Selanjutnya : 1. Mencari prime-implicant, term yang menjadi calon yang terdapat dalam fungsi

sederhana 2. Memilih prime-implicant yang mempunyai jumlah literal paling sedikit

2.9.1 CARA ALJABAR 1. Sederhanakanlah fungsi Boolean f(x,y) = x’y + xy’ + xy

Jawab : f(x,y) = x’y + xy’ + xy = x’y + x . (y’+y) Distributif = x’y + x . 1 Komplemen = x’y + x Identitas = (x’+x)(x+y) Distributif = 1 . (x+y) Komplemen = x + y Identitas

wx yz

wx yz

Page 24: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 24

2. Sederhanakanlah fungsi Boolean dibawah ini : f(x,y,z) = x’y’z’ + x’y’z + x’yz + x’yz’ + xy’z’ + xyz’ Jawab : f(x,y,z) = x’y’z’ + x’y’z + x’yz + x’yz’ + xy’z’ + xyz’ = x’.(y’z’+y’z+yz+yz’) + x . (y’z’+yz’) Distributif = x’.((y’(z+z’) + y(z+z’)) + x . ((y’+y)z’) Distributif = x’.(y’ .1 + y.1) + x(1 . z’) Komplemen = x’.(y’+y) + xz’ Identitas = x’ .1 + xz’ Komplemen = x’ + xz’ Identitas = (x’+x)(x’+z’) Distributif = 1. (x’+z’) Komplemen = x’ + z’ Identitas

3. Sederhanakanlah fungsi Boolean : f(x,y,z) = xy + xy’z + y(x’+z) + y’z’ Jawab : f(x,y,z) = xy + xy’z + y(x’+z) + y’z’ = x(y+y’z) + y(x’+z) + y’z’ Distributif = x((y+y’)(y+z)) + x’y + yz + y’z’ Distributif = x( 1 . (y+z)) + x’y + yz + y’z’ Komplemen = x . (y+z) + x’y + yz + y’z’ Identitas = xy + xz + x’y + yz + y’z’ Distributif = y(x+x’) + xz + yz + y’z’ Distributif = y . 1 + xz + yz + y’z’ Komplemen = y + xz + yz + y’z’ Identitas = (y+y’)(y+z’) + xz + yz Distributif = 1.(y+z’) + xz + yz Komplemen = y + yz + xz + z’ Identitas = y (1 + z) + (x+z’)(z+z’) Distibutif = y . 1 + (x+z’)(z+z’) Teorema 2 = y + (x+z’)(z+z’) Identitas = y + (x + z’) . 1 Komplemen = x + y + z’ Identitas

Page 25: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 25

2.9.2 PETA KARNAUGH 1. Sederhanakanlah persamaan f(x,y) = x’y + xy’ + xy = m1 + m2 + m3

Jawab : Sesuai dengan bentuk minterm, maka 3 kotak dalam K’Map 2 dimensi, diisi dengan 1 :

0 1 0 1 1 1 1

Selanjutnya pengelompokkan semua 1 yang ada dengan membuat kumpulan kotak atau persegi panjang dentgan jumlah bujursangkar kecil 2n. Buatlah kelompok yang sebesar-besarnya.

0 1

0 1

1 1 1

Cara menentukan bentuk sederhana dari hasil pengelompokkan adalah :

• Carilah variabel mana saja yang memiliki nilai yang sama dalam kelompok tersebut, sebagai contoh kelompok A. Pada kelompok A, variabel yang memiliki nilai yang sama adalah variabel y dengan harga 1. Pada kelompok B, variabel yang memiliki nilai yang sama adalah variabel x dengan harga 1

• Selanjutnya menentukan bentuk hasil pengelompokkan diatas. Pada contoh diatas hasil kelompok A adalah y dan hasil kelompok B adalah x. Hasil bentuk sederhana dari contoh diatas A + B = y + x

2. Sederhanakanlah persamaan :

f(x,y,z) = x’y’z’ + x’y’z + x’yz + x’yz’ + xy’z’ + xyz’ Jawab :

00 01 11 10

0

1 1 1

1

1 1

1

x y

x A

B

∴f(x,y,z) = z’ + x’

y

yz x

Page 26: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 26

3. Sederhanakanlah fungsi Boolean berikut :

f(w,x,y,z) = ∑m(0, 1, 2, 3, 4, 6, 8, 9, 10, 11, 12, 13, 14) Jawab :

00 01 11 10

00

1 1 1

1

01 1 1

11 1 1 1

10

1 1 1

1

2.9.3 METODE QUINE – McCLUSKEY Metode Quine – McCluskey digunakan untuk menyederhanakan fungsi Boolean dengan 4 atau lebih variabel. Contoh : Sederhanakanlah fungsi Boolean dibawah ini : F = ∑m(0, 1, 2, 8, 10, 11, 14, 15) Jawab : Langkah-langkah penyelesaiannya : 1. Kelompokkan representasi biner untuk tiap minterm menurut jumlah digit ‘1’ :

Desimal Biner 0 0000 1 0001 2 0010 8 1000 10 1010 11 1011 14 1110 15 1111

∴ f(w,x,y,z) = x’ + z’ + wy’

wx yz

Page 27: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 27

Dari tabel konversi tersebut dapat dilihat bahwa jumlah digit adalah : Jumlah Digit 1 Desimal w x Y z 0 0 0 0 0 0 0 √1 1, 2, 8 1 0 0 0 1 √2 10 2 0 0 1 0 √3 11, 14 8 1 0 0 0 √4 15 10 1 0 1 0 √

11 1 0 1 1 √ 14 1 1 1 0 √ 15 1 1 1 1 √

2. Minterm dari satu bagian dengan bagian lainnya jika mempunyai nilai bit yang sama

dalam semua posisi kecuali satu posisi yang berbeda diganti dengan tanda ‘-‘. Misal bagian I : 0000 Bagian II : 0001 Sehingga dari tabel diatas menjadi :

w x y z w x y z 0 0 0 0 0 √ 0, 1 0 0 0 - 1 0 0 0 1 √ 0, 2 0 0 - 0 √ 2 0 0 1 0 √ 0, 8 - 0 0 0 √ 8 1 0 0 0 √ 2, 10 - 0 1 0 √

10 1 0 1 0 √ 8, 10 1 0 - 0 √ 11 1 0 1 1 √ 10, 11 1 0 1 - √ 14 1 1 1 0 √ 10, 14 1 - 1 0 √ 15 1 1 1 1 √ 11, 15 1 - 1 1 √

14, 15 1 1 1 - √

Tanda √ , berarti minterm tersebut dipilih untuk tahap selanjutnya.

000-

Page 28: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 28

3. Kelompokkan hasil minterm tahap 2) seperti tahap 1) kemudian lakukan seperti pada tahap 2)

A B

w x y z w x y z 0, 1 0 0 0 - 0, 2 0 0 - 0 √ 0, 2, 8, 10 - 0 - 0 0, 8 - 0 0 0 √ 0, 8, 2, 10 - 0 - 0

2, 10 - 0 1 0 √ 10, 11, 14, 15 1 - 1 - 8, 10 1 0 - 0 √ 10, 14, 11, 15 1 - 1 -

10, 11 1 0 1 - √ 10, 14 1 - 1 0 √ 11, 15 1 - 1 1 √ 14, 15 1 1 1 - √

4. Memilih Prime-Implicant

Dari tabel diatas terlihat hasil dari tahap penentuan prime implicant. Pada kolom B (sudah tidak dapat saling dihilangkan), terlihat pada bagian pertama mencakup desimal 0, 2, 8, 10, dan pada bagian kedua mencakup desimal 10, 11, 14, 15. Hal ini berarti dari fungsi Boolean F = ∑m(0, 1, 2, 8, 10, 11, 14, 15); desimal yang belum ada pada kolom B adalah desimal ‘1’. Tetapi pada kolom A telah didapat desimal 0, 1, sehingga semua desimal pada fungsi Boolean telah tercakup semua.

Hal ini berarti calon prime-implicant adalah - 0, 1 (0 0 0 -) ditandai dengan A - 0, 2, 8, 10 ( - 0 - 0) ditandai dengan B - 10, 11, 14, 15 (1 – 1 -) ditandai dengan C

0 1 2 8 10 11 14 15 A ⊗ ⊗ B x ⊗ ⊗ ⊗ C x ⊗ ⊗ ⊗

√ √ √ √ √ √ √ √

Jadi bentuk sederhana dari fungsi Boolean F = ∑m(0, 1, 2, 8, 10, 11, 14, 15) adalah : F = A + B + C = w’x’y’ + x’z’ + wy

Page 29: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 29

2. Sederhanakanlah fungsi Boolean F = ∑m(0, 1, 3, 4, 5, 7) Jawab :

x y z x y z x y z 0 0 0 0 √ 0, 1 0 0 - √ 0, 1, 4, 5 - 0 -

A 1 0 0 1 √ 0, 4 - 0 0 √ 0, 4, 1, 5 - 0 - 4 1 0 0 √ 1, 3 0 - 1 √ 1, 3, 5, 7 - - 1

B 3 0 1 1 √ 1, 5 - 0 1 √ 1, 5, 3, 7 - - 1 5 1 0 1 √ 4, 5 1 0 - √ 7 1 1 1 √ 3, 7 - 1 1 √ 5, 7 1 - 1 √

0 1 3 4 5 7 A ⊗ ⊗ ⊗ X B X ⊗ ⊗ ⊗ √ √ √ √ √ √

F = ∑m(0, 1, 3, 4, 5, 7) = A + B = y’ + z

3. Sederhanakanlah fungsi Boolean F = ∑m(0, 2, 4, 5, 6, 8, 10, 11, 13) Jawab :

w x y z w x y z 0 0 0 0 0 0, 2 0 0 - 0 2 0 0 1 0 0, 4 0 - 0 0 √ 4 0 1 0 0 0, 8 - 0 0 0 √ 8 1 0 0 0 4, 5 0 1 0 - √ 5 0 1 0 1 4, 6 0 1 - 0 6 0 1 1 0 A 5, 13 - 1 0 1 √

10 1 0 1 0 10, 11 1 0 1 - √ 11 1 0 1 1 13 1 1 0 1 B

w x y z w x y z

0, 2 0 0 - 0 0, 2, 4, 6 0 - - 0 H 0, 4 0 - 0 0 C 0, 8 - 0 0 0 D 4, 5 0 1 0 - E 4, 6 0 1 - 0 5, 13 - 1 0 1 F 10, 11 1 0 1 - G

Page 30: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 30

0 2 4 5 6 8 10 11 13

A X B X C X X D X ⊗ E X X F ⊗ ⊗G ⊗ ⊗ H ⊗ ⊗ ⊗ ⊗ √ √ √ √ √ √ √ √ √

F = ∑m(0, 2, 4, 5, 6, 8, 10, 11, 13) = D + F + G + H = x’y’z’ + xy’z + wx’y + w’z’

Page 31: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 31

2.10 SOAL LATIHAN 1. Sederhanakanlah Fungsi Boolean dibawah ini dengan menggunakan Cara Aljabar :

a. xy + xy’z + y(x’ +z) + y’z’ b. wx + xy + yz + zw + w’x’yz’ + w’x’y’z c. wxy’z’ + wxy’z + wxyz + wx’yz + w’x’yz + w’x’yz’ + w’x’y’z’ + w’xyz’ +

w’xy’z’ + w’xy’z d. A’B’CE’ + A’B’C’D’ + B’D’E’ + B’CD’ + CDE’ + BDE’

2. Sederhanakanlah Fungsi Boolean dibawah ini dengan menggunakan Peta Kaurnaugh :

a. F = BDE + B’C’D + CDE + A’B’CE + A’B’C + B’C’D’E’ b. wx + xy + yz + zw + w’x’yz’ + w’x’y’z c. wxy’z’ + wxy’z + wxyz + wx’yz + w’x’yz + w’x’yz’ + w’x’y’z’ + w’xyz’ +

w’xy’z’ + w’xy’z 3. Sederhanakanlah fungsi Boolean dibawah ini dengan menggunakan metode Quine-

McCluskey a. F(A,B,C,D,E) = Σ(0, 1, 4, 5, 16, 17, 21, 25, 29) b. F(A,B,C,D,E,F,G) = Σ(20,28,52,60) c. F(A,B,C,D,E,F,G) = Σ(20,28,38, 39, 52, 60, 102, 103, 127) d. F(A,B,C,D,E,F,G) = Σ(6, 9, 13, 18, 19, 25, 27, 29, 41, 45, 57, 61)

Page 32: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 32

BAB III KALKULUS PROPOSISI

3.1 KONSEP DAN NOTASI DASAR Kalkulus proposisi merupakan metode untuk kalkulasi yang menggunakan proposisi/kalimat. Dalam kalkulus proposisi yang ditinjau adalah nilai kalimat deklaratif (true/false), metode penggabungan kalimat dan penarikan kesimpulan (kalimat) berdasarkan kalimat tersebut. Kebenaran kalimat dapat ditentukan dari struktur kalimat itu sendiri, tanpa melihat apakah unsur-unsur pokoknya benar atau salah atau sesuai dengan kenyataan di alam. Contoh : Jika kita tidak mengetahui apakah ada kehidupan di planet jupiter, maka kalimat berikut ini:

Ada monyet di planet Jupiter

Atau Tidak ada monyet di planet Jupiter

Adalah BENAR. Kedua kalimat tersebut dapat dinotasikan dengan : P or (not P) Definisi 3.1 : Proposisi Kalimat proposisi logik dibentuk oleh simbol berikut yang disebut proposisi : - Simbol kebenaran : True dan False - Simbol proposisional: P, Q, R, S, P1, Q1, R1, S1, …. Definisi 3.2 : Kalimat Kalimat proposisi dibentuk dari konektivitas proposisional :

Not, and, or, if-then, if-and-only-if, if-then-else Kalimat-kalimat dibentuk menurut aturan-aturan berikut ini : • Setiap proposisi adalah kalimat • Jika F adalah kalimat, maka negasi (not F) adalah kalimat • Jika F dan G adalah kalimat, maka konjungsi : (F and G) adalah kalimat • Jika F dan G adalah kalimat, maka disjungsi : (F or G) adalah kalimat • Jika F dan G adalah kalimat, maka implikasi : (If F then G) adalah kalimat

F disebut sebagai anticendent dan G sebagai consequent

Page 33: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 33

• Jika F dan G adalah kalimat, maka ekivalensi : (F if and only if G) adalah kalimat.

F disebut sebagai left-hand-side dan G sebagai rigth-hand-side dari ekivalensi jika F, G, dan H adalah kalimat, maka kondisional: if F then G else H adalah kalimat. F disebut sebagai if-clausa, G sebagai then-clausa, dan H adalah sebagai else-clausa

Contoh : Diketahui ekspresi : E : ((not (P or Q) if only if ((not P) and (not Q))) adalah kalimat. Karena :

1. P adalah kalimat, Q adalah kalimat 2. (P or Q), (not P), (not Q) adalah kalimat 3. (not (P or Q) and ((notP) and (notQ)) adalah kalimat 4. ((not (P or Q)) if and only if ((not P) and (not Q))) adalah kalimat

3.2 ARTI KALIMAT Suatu kalimat (P or (not Q)) dapat diketahui kebenarannya, jika diketahui nilai kebenaran dari simbol proposisi P dan Q. 3.2.1 Interpretasi Definisi 3.3 : Suatu interpretasi I adalah suatu tanda untuk nilai kebenaran, true atau false, untuk setiap kumpulan simbol proposisi. Untuk setiap kalimat F, interpretasi I disebut dengan interpretasi untuk F jika I bernilai true atau false untuk setiap simbol proposisi F. Contoh : Diketahui kalimat F : P or (not Q) Satu interpretasi I1 bernilai false untuk P dan true untuk Q, yaitu : I1 : P adalah false Q adalah true Interpretasi lain I2 untuk kalimat F adalah false untuk P dan false untuk Q, yaitu : I2 : P adalah false Q adalah false Sehingga kita dapat mengatakan bahwa, P adalah false dan Q adalah true untuk I1, dan P adalah false dan Q adalah false untuk I2

Page 34: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 34

3.2.2 Aturan-aturan semantik

Definisi 3.4 Jika E berupa kalimat dan I adalah intepretasi dari E, maka nilai kebenaran dari E (dan semua subkalimatnya) dengan interpretasi I ditentukan dengan melakukan pengulangan aturan-aturan semantik berikut ini : • Aturan Proposisi

Nilai kebenaran dari setiap simbol proposisi : P, Q, R, … dalam E adalah sama dengan nilai kebenaran yang diberikan untuk I

• Aturan true Kalimat true adalah true untuk I

• Aturan false Kalimat false adalah false untuk I

• Aturan not Negasi kalimat : not F adalah true jika F adalah false dan false jika F adalah true

• Aturan and Konjungsi F and G adalah true jika F dan G keduanya benar, dan false jika sebaliknya (yaitu jika F false atau G false)

• Aturan or Disjunngsi F or G adalah true jika F true atau jika G true, dan false jika keduanya false

• Aturan if-then Implikasi if F then G adalah true jika F false atau jika G true dan false jika F true dan G false

• Aturan if-and-only-if Ekivalensi F if and only if G adalah true jika nilai kebenaran F adalah sama dengan nilai kebenaran G, sebaliknya false jika memiliki nilai kebenaran keduanya berbeda.

• Aturan if-then-else Nilai kebenaran kondisional if F then G else H adalah nilai kebenaran G jika F true dan nilai kebenaran H jika F false.

Page 35: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 35

Contoh : Misalkan sebuah kalimat : A : if (x and (not y)) then ((not x) or z) Dan interpretasi I untuk A adalah : I : x T y F z F Dengan menggunakan aturan semantik di atas, maka kalimat A dapat ditentukan nilai kebenarannya, sebagai berikut : - karena y F, maka berdasarkan aturan not, (not y) T - karena x T dan (not y) T, maka berdasarkan aturan and, (x and (not y)) T - karena x T, maka berdasarkan aturan Not, (not x) F - karena (not x) f dan z F, maka berdasarkan aturan or, ((not x) or z) F - karena (x and (not y)) T dan ((not x) or z) F, maka berdasarkan aturan if-then, if

(x and (not y)) then ((not x) or z) F 3.3 SIFAT-SIFAT KALIMAT 1. VALID

Kalimat A valid jika bernilai true berdasarkan semua interpretasi untuk A (disebut juga Tautologi)

2. STATISFIABLE Kalimat A statisfiable jika bernilai true berdasarkan beberapa interpretasi untuk A

3. CONTRADICTORY (UNSTATISFIABLE) Kalimat A contradictory jika bernilai False berdasarkan semua interpretasi untuk A

4. IMPLIES Kalimat A implies kalimat B, jika untuk sebarang interpretasi I untuk A dan B, jika A bernilai true berdasarkan I maka B juga bernilai true berdasarkan I

5. EQUIVALENT Kalimat A dan B ekivalen jika, untuk setiap interpretasi untuk A dan B, A mempunyai nilai kebenaran yang sama dengan B

6. CONSISTENT Sekumpulan kalimat A1, A2, … konsisten jika ada interpretasi untuk A1, A2, … sehingga Ai (I = 1, 2, 3, …) bernilai true

Contoh :

- Kalimat w or (not w) adalah kalimat valid - Kalimat x and (not x) adalah kalimat contadictory

Page 36: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 36

3.4 PENENTUAN NILAI KEBENARAN Penentuan nilai kebenaran suatu kalimat dapat dilakukan dengan 3 cara yaitu :

1. Tabel Kebenaran 2. Tabel Jarang (sparse) 3. Pohon Semantik

Contoh : 1. if (p and q) then (p or (not r) Menggunakan Tabel Kebenaran

p q r p and q not r p or not r If (p and q) then (p or not r F F F F T T T F F T F F F T F T F F T T T F T T F F F T T F F F T T T T F T F F T T T T F T T T T T T T T F T T

Menggunakan Tabel Jarang

p Q r p and q If-then p or not r T - - - T T F - - F T -

Menggunakan Pohon Semantik

1

2

Tp Fp

3T T

Page 37: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 37

2. if (if x then y) then (if (not x) then (not y)) Dengan menggunakan Pohon Semantik x memiliki dua kemungkinan nilai yaitu T atau F, maka dibentuk

Jika x T, maka nilai A pasti T sehingga pohon menjadi :

Jika x F, maka nilai A bergantung pada y, sehingga pohon menjadi :

Jika y T, maka nilai kebenaran A adalah F, Jika y F, maka nilai kebenaran A adalah T; sehingga phon semantik menjadi :

1

2

Tx Fx

3

1

2

Tx Fx

3T

1

2

Tx Fx

3T

Ty F

4 5

1

2

Tx Fx

3T

Ty F

F T4 5

y

Page 38: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 38

PEMBUKTIAN DENGAN ASUMSI SALAH

Untuk membuktikan validitas sebuah kalimat diperlukan pembuktian nilai True, untuk semua interpretasi yang mungkin pada kalimat tersebut. Akan lebih mudah untuk membuktikan bahwa jika ada 1 interpretasi yang mengakibatkan nilai kalimat tersebut False maka kalimat tersebut tidak valid.

Contoh :

1. A : if ((not x) or (not y)) then (not (x and y)) Misalkan A bernilai False berdasarkan suatu interpretasi, sehingga :

if ((not x) or (not y)) then (not (x and y)) False Akan dicoba untuk menurunkan kondisi-kondisi sehingga akan terlihat apakah asusmsi

awal yang diambil dapat terjadi/tidak A akan bernilai F jika anticendent T dan consequent F

if ((not x) or (not y)) then (not (x and y)) F T F Dari anticendent belum dapat ditarik kesimpulan, sehingga lihatlah ke consequentnya.

Consequent bernilai F jika (x and y) T, berarti x T dan y T, sehingga : if ((not x) or (not y)) then (not (x and y)) False F T T T F T T T

F (?) Terlihat pada anticendent bahwa terjadi kontradiksi, berarti kondisi A F tidak pernah terjadi. Sehingga kesimpulannya A valid

2. B : (if x then y) if and only if ((not x) or y) Ada 2 kasus yang membuat kalimat B bernilai False Kasus I :

(if x then y) iff ((not x) or y) T F F

Page 39: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 39

Sisi kiri belum dapat ditarik kesimpulan, lihatlah sisi kanan : ((not x) or y) akan bernilai F jika x T dan y F, sehingga : (if x then y) iff ((not x) or y) T T F F T F F

Terjadi kontradiksi pada bagian sisi kiri. Kasus II :

(if x then y) iff ((not x) or y) F F T

Lihat pada bagian anticendent, (if x then y) akan bernilai F jika x T dan y F, sehingga : (if x then y) iff ((not x) or y) F T F F T T F

Terjadi kontradiksi pada bagian sisi kanan. Karena 1 kasus yang menyebabkan B bernilai False tidak mungkin terjadi, maka dapat ditarik kesimpulan : B valid 3.6 EKIVALENSI LOGIK DAN KONSEKUENSI LOGIK Definisi Ekivalensi Logik : Dua buah kalimat A dan B merupakan ekivalensi logik jika dan hanya jika memiliki nilai yang sama pada semua interpretasi yang diberikan. Teorema A Ekivalensi B, jika dan hanya jika ( A iff B) merupakan Tautologi Definisi Konsekuensi Logik B adalah konsekuensi logik dari A jika untuk setiap pemberian nilai kebenaran ke variabel pada A dan pada B sedemikian sehingga jika A mempunyai nilai TRUE maka B juga mempunyai nilai TRUE Teorema B Konsekuensi Logis dari A, jika dan hanya jika (if A then B) merupakan Tautologi

F (?)

F (?)

Page 40: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 40

Catatan : Jika pernyataan lebih dari 1, misal A1, A2, A3 maka bentuk konsekuensi logiknya menjadi :

IF (A1 AND A2 AND A3) THEN B

Contoh Kasus : Periksa apakah B merupakan kesimpulan dari 6 argumen dibawah ini ? A1 : if P then (Q and R and S) A2 : if T then (if U then (if not Y then not S)) A3 : if Q then T A4 : if R then (if X then U) A5 : if Y then not X A6 : X ---------------------------------------------------------------- B : not P Jawaban harus dibuktikan bahwa kalimat :

IF (A1 and A2 and A3 and A4 and A5 and A6) THEN B adalah VALID 3.7 KONJUNGSI DAN DISJUNGSI JAMAK Misal diberikan kalimat yang mengandung operator konjungsi atau konjungsi lebih dari satu, sebagai berikut : A : p and q and r B : p or q or r Maka urutan perngerjaan operasi pada kalimat tersebut dilakukan dari kiri ke kanan sesuai aturan sebagai berikut : 1. Konjungsi Jamak

A1 and A2 and A3 and A4 and … and An

Memiliki arti : ((… ((A1 and A2) and A3) and A4) and … ) and An)

2. Disjungsi Jamak

A1 or A2 or A3 or A4 or … or An

Memiliki arti : ((… ((A1 or A2) orA3) or A4) or … ) and An)

Page 41: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 41

Kalimat-kalimat berikut adalah ekivalen karena adanya hukum asosiasi : A : ((w and x) and y) and z B : w and (x and (y and z)) C : w and ((x and y) and z)

Aturan semantik untuk hubungan jamak : 1. Konjungsi jamak

A1 and A2 and A3 and … and An bernilai True jika tiap conjuct A1, A2, A3, A4, … An adalah True

2. Disjungsi Jamak A1 or A2 or A3 or … or An adalah bernilai True jika setidaknya salah satu dari A1, A2, A3, A4, … An adalah true

3.8 SUBSTITUSI Substitusi adalah operasi pengantian subkalimat dari suatu kalimat dengan subkalimat yang lain. Ada dua jenis substitusi 1. Substitusi Total

Penggantian seluruh kemunculan suatu subkalimat 2. Substitusi Parsial

Penggantian nol, satu, atau lebih kemunculan suatu subkalimat. Definisi : (Substitusi Total) Jika A, B, C adalah kalimat, maka

A w{B C} Adalah kalimat yang dihasilkan dengan mengganti seluruh kemunculan B di A dengan C. Contoh : 1. [ x and (y or x) ] w { x (if w then z) }

menghasilkan : (if w then z) and (y or (if w then z))

2. [ if x then (y and z) ] w { (y and z) w } menghasilkan : if x then w

Page 42: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 42

Catatan : • Substitusi dikerjakan dalam 1 langkah

[x and y] w { x (x and z)} menghasilkan (x and z) and y • Substitusi tidak memiliki efek jika subkalimat yang akan diganti tidak muncul dalam

kalimat, [x and y] w { z w } menghasilkan menghasilkan x and y

• Substitusi untuk konjungsi dan disjungsi jamak :

[x and y and z] w{(x and y) w} Sebenarnya [(x and y) and z]w{(x and y) w} menghasilkan w and z

Definisi : (Substitusi Parsial) Jika A, B, C, adalah kalimat maka

A {B C} Akan menghasilkan salah satu kalimat dengan mengganti nol, sebagian, atau seluruh kemunculan subkalimat b di A dengan subkalimat C Contoh : [ x and x ] {x y} akan menghasilkan salah satu dari kalimat-kalimat berikut : 1. x or a {mengganti nol kemunculan x } 2. y or x {mengganti kemunculan x pertama} 3. x or y {mengganti kemunculan x kedua} 4. y or y {mengganti seluruh kemunculan dari x} Substitusi parsial bersifat invertible, yaitu salah satu kalimat yang mungkin dihasilkan adalah kalimat semula.

( A {B C}) {C B} hasilnya adalah A Contoh : [ (x or y) {x y}] {y x} salah satu kalimat yang mungkin adalah : x or y [(x or y) w {x y}] w {y x } hasil yang diperoleh tepat 1 kalimat yaitu : x or x

Page 43: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 43

3.9 SUBSTITUSI JAMAK Definisi : Misal A, B1, B2, …, dan C1, C2, …, Cn adalah kalimat dengan B1, B2, …, Bn saling berlainan. a. Substitusi Total

Substitusi total dituliskan sebagai : A w [ B1 C1 B2 C2 … Bn Cn ] Adalah kalimat yang diperoleh dengan menggantikan secara simultan (serempak) setiap kemunculan Bi di Ai dengan Ci

b. Substitusi Partial Substitusi partial dituliskan sebagai : A [ B1 C1 B2 C2 … Bn Cn ] Adalah salah satu kalimat yang diperoleh dengan menggantikan nol, satu, atau lebih kemunculan Bi di Ai dengan Ci

Contoh : 1. Substitusi jamak dilakukan serentak dalam 1 langkah

x w [ x y y x ]

menghasilkan kalimat : y Bedakan dengan substitusi bertahap sebagai berikut :

x w {x y} w {y z} menghasilkan kalimat : z

2. [ if x

then if y or x x z then y or z ] (y or z ) not z menghasilkan : if x then [if (y or x) then y or z ]

Page 44: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 44

3. [ if x then if (y or x) x z then (y or z) ] (y or z) not z menghasilkan salah satu dari 8 kalimat. 3.10 PERLUASAN INTERPRETASI Definisi : (Interpretasi yang diperluas) Jika I adalah suatu interpretasi, x adalah simbol proposisi dan τ adalah nilai kebenaran (true/false) maka perluasan interpretasi :

[ x I ] o I

adalah interpretasi yang memberikan nilai τ pada x dan memberikan nilai kebenaran yang sesuai dengan interpretasi I untuk semua simbol proposisi selain x. Contoh :

IA : x T Y F

Jika IB = [y T] o IA

maka IB interpretasi dengan x T, y T Untuk suatu interpretasi I dengan simbol proposisi x1, x2, … , xn dan nilai kebenaran τ1, τ2, … , τn maka

[x1 ] τ1] o [x2 τ1] o … o [xn τn] o I berarti

([x1 ] τ1] o ([x2 τ1] o (… o ([xn τn] o I)))

Page 45: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 45

3.11 METODE DEDUKSI

- Salah satu metode yang digunakan untuk menarik suatu kesimpulan berdasarkan pernyataan atau premis-premis yang diketahui.

- Metode deduksi ini menggunakan aturan-aturan penalaran, ekivalensi logik dan tautologi

- Untuk mempermudah operasi penurunan digunakan operator-operator lama sbb:

Operasi Simbol Baru Simbol Lama

NEGASI NOT ~ KONJUNGSI AND ∧DISJUNGSI OR ∨IMPLIKASI IF-THEN ⊃EKIVALENSI IF-AND-ONLY-IF ≡KONDISIONAL IF-THEN-ELSE Tidak Ada

- Metode Deduksi hanya dapat menunjukkan bahwa kesimpulan dari suatu penalaran valid;

yaitu Jika kesimpulan yang diperoleh dapat dicapai/dibuktikan dengan aturan yang ada - Jika tidak dapat menarik suatu kesimpulan dengan metode deduksi, maka tidak berarti

penalaran tersebut tidak valid. Ketidakvalidan suatu penalaran harus tetap dibuktikan secara eksplisit dengan Tabel Kebenaran atau Analisis Asumsi Salah (Falsification)

ATURAN PENALARAN DASAR 1. KONJUNGSI

Jika diketahui proposisi p dan q TRUE maka dapat disimpulkan bahwa penalaran berbentuk konjungsi (p ∧ q) juga akan bernilai TRUE p q Atau dapat ditulis (p ∧ q ) ⊃ (p ∧ q) p ∧ q

2. SIMPLIFIKASI

Jika penalaran berbentuk konjungsi (p ∧ q) bernilai TRUE maka dapat disimpulkan bahwa proposisi unsur pembentuknya, yaitu p dan q TRUE

p ∧ q dan p ∧ q Atau dapat ditulis (p ∧ q ) ⊃ p p q (p ∧ q ) ⊃ q

Page 46: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 46

3. ADDITION DISJUNGSI Jika diketahui suatu proposisi p bernilai TRUE maka dapat disimpulkan bahwa proposisi disjungsi dengan proposisi lain juga bernilai TRUE P atau q p ∨ q p ∨ q

4. SILOGISME DISJUNGTIVE

Jika diketahui : p ∨ q bernilai TRUE dan salah satu proposisi pembentuknya FALSE maka dapat ditarik kesimpulan proposisi yang lain TRUE

p ∨ q p ∨ q ~ p dan ~ q q P

5. MODUS PONEN

Jika kondisional p ⊃ q TRUE; dimana antisendennya TRUE maka dapat disimpulkan bahwa konsekuen harus TRUE

p ⊃ q p q

6. MODUS TOLLENS

Jika kondisional p ⊃ q TRUE; dimana konsekuennya FALSE maka dapat disimpulkan bahwa antisenden harus FALSE

p ⊃ q ~ q ~ p

7. SILOGISME HIPOTETIK

Jika diketahui 2 buah kondisional yang berkesinambungan maka dapat disimpulkan suatu kalimat kondisional yang baru. p ⊃ q q ⊃ r p ⊃ r

Page 47: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 47

TABEL ATURAN EKIVALENSI LOGIK

NO ATURAN BENTUK 1. Negasi Ganda p ≡ ~ (~p) 2. Assosiatif p ∧ ( q ∧ r) ≡ (p ∧ q) ∧ r

p ∨ ( q ∨ r) ≡ (p ∨ q) ∨ r 3. Komutatif p ∧ q ≡ q ∧ p

p ∨ q ≡ q ∨ p 4. Identitas p ∧ p ≡ p

p ∨ p ≡ p 5. Distributif p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧

r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

6. Hukum De Morgan ~ (p ∨ q) ≡ ~p ∧ ~q ~ (p ∧ q) ≡ ~p ∨ ~q

7. Hukum Penyerapan p ∧ (p ∨ q) ≡ p p ∨ (p ∧ q) ≡ p

8. Implikasi p ⊃ q ≡ ~(p ∧ ~q) ≡ ~p ∨ q 9. Kontrapositif p ⊃ q ≡ ~ q ⊃ ~p 10. Eksportasi (p ∧ q) ⊃ r ≡ p ⊃ (q ⊃ r)

Catatan : Metode Deduksi mengandung kesulitan karena tidak ada suatu pegangan yang pasti untk menurunkan kesimpulan, yaitu apakah harus menggunakan suatu aturan penalaran tertentu (misal : Simplifikasi, Modus Ponen, dll) atau menggunakan aturan ekivalensi atau aturan lainnya. Contoh : 1. Diketahui :

Jika ibu datang dari pasar, maka ani senang sekali Ibu datang dari pasar dan membawa kue bolu Jadi : Ani senang sekali Kesimpulan tersebut Valid atau tidak Valid ?

Jawab :

Ubah penalaran tersebut menjadi kalimat proposisi Premis:

Jika ibu datang dari pasar, maka ani senang sekali : p ⊃ q Ibu datang dari pasar dan membawa kue bolu : p ∧ r

Kesimpulan: Ani senang sekali : q

Page 48: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 48

Telusuri dengan menggunakan tabel : Premis Alasan Keterangan 1. p ⊃ q 2. p ∧ r 3. P 2, simplifikasi Disimpulkan dari baris 2 dengan simplifikasi 4 q 1,3 Modus Ponen Disimpulkan dari baris 1 dan 3 dengan Modus

Ponen 2. Diketahui :

Ani masuk sekolah atau ani tidak masuk sekolah Jika ani tidak masuk sekolah maka sekolah pasti libur Sekolah Tidak Libur Apa Kesimpulan dari penalaran tersebut ?

Jawab :

Gunakan metode deduksi ! Premis:

Ani masuk sekolah atau ani tidak masuk sekolah : p ∨ ~ p Jika ani tidak masuk sekolah maka sekolah pasti libur : ~ p ⊃ q Sekolah Tidak Libur : ~ q

Telusuri dengan menggunakan tabel : Premis Alasan Keterangan 1. p ∨ ~ p 2. ~ p ⊃ q 3. ~ q 4 ~ (~ p) 2, 3 Modus Tollens Disimpulkan dari baris 2 dan 3 dengan modus

ponen 5 p 4,Negasi ganda Kesimpulan

Jadi kesimpulannya adalah : Ani Masuk Sekolah.

Page 49: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 49

3.12 SOAL LATIHAN 1. Tentukan sifat kalimat dibawah ini dengan menggunakan Tabel Jarang (Sparse Table) :

A : if (p and not q) then (p if and only if q) 2. Buatlah pohon semantik dari kalimat berikut dan simpulkan tentang sifat dari kalimat

tersebut B : (if x then not y) if and only if (not (x and z))

3. Diketahui pernyataan :

A : Sore hari ini mendung dan lebih dingin dari kemarin. B : Saya akan pergi berenang jika cuaca cerah. C : Jika saya tidak berenang maka saya akan pergi belanja. D : Jika saya pergi belanja maka saya akan berada dirumah

tepat pada saat matahari terbenam E : Saya berada di rumah tepat pada saat matahari terbenam a). Buatlah struktuk kalimat abstrak untuk pernyataan

tersebut dalam bentuk : Jika A dan B dan C dan D Maka E

b). Selidiki validitas kalimat/proposisi diatas dengan menggunakan Pohon Semantik

4.

IF x THEN y A : IF AND AND (x or z) THEN ( y OR w ) IF x THEN w

Tentukan : a. Sifat dari Proposisi dibawah ini dengan menggunakan Pohon Semantik b. Selidiki Validitasnya dengan menggunakan Metode Asumsi Salah

IF x IF x THEN y 5. B : THEN IFF OR

( y AND z) IF x THEN z

Tentukan : a. Sifat dari Proposisi dibawah ini dengan menggunakan Pohon Semantik b. Selidiki Validitasnya dengan menggunakan Metode Asumsi Salah

Page 50: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 50

6. Jika penawaran emas dibiarkan konstan dan permintaan semas bertambah maka harga

emas naik. Jika permintaan emas bertambah yang menyebabkan harga emas naik, maka ada keuntungan bagi spekulator. Penawaran emas dibiarkan konstan. Oleh karena itu ada keuntungan bagi spekulator. Analisis apakah penalaran tersebut valid dengan menggunakan metode asumsi salah

7. p AND q

C : OR IF r THEN ( p AND q AND r )

Substitusikan dengan interpretasi berikut ini : a. C { (p AND q) P } b. C p s ( p AND q) p c. C { (p AND q) P } d. C p s ( p AND q) p

Page 51: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 51

BAB IV KALKULUS PREDIKAT

4.1 DEFINISI

Kalimat pada kalkulus proposisi tidak dapat menjelaskan konsep objek dan relasi antar objek. Contoh :

Batuan di Mars berwarna putih Atau

Batuan di Mars tidak berwarna putih Dengan aturan kalkulus proposisi, pernyataan tersebut dapat dibuat menjadi skema kalimat

(p or not p) dan selanjutnya dapat ditentukan nilai kebenarannya. Jika ada pernyataan lain :

Ada batuan di Mars berwarna putih Atau

Semua batuan di Mars berwarna putih Maka pernyataan tersebut tidak dapat dibentuk menjadi skema kalimat kalkulus proposisi. Hal ini disebabkan karena pernyataan tersebut mengandung kuantisasi dari objek. Oleh karena itu dibutuhkan bahasa baru yang mengenal adanya konsep objek dan relasi antar objek, yaitu menggunakan Kalkulus Predikat. Dengan kalkulus predikat maka pernyataan tersebut diubah menjadi :

(for some x) (p(x) and q(x)) or (for all x)(if p(x) then q(x))

dimana : p(x) = x adalah batuan di Mars q(x) = x adalah batuan berwarna putih “for some x” disebut kuantifier (simbol : ∃x) “for all x” disebut kuantifier (simbol : ∀x) Pada dasarnya Kalkulus Predikat merupakan perluasan dari Kalkulus Proposisi dimana Kalkulus Predikat mengatasi kelemahan pada kalkulus proposisi dengan menambahkan representasi :

- Objek yang memiliki sifat tertentu - Relasi antar objek

Page 52: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 52

Definisi : Simbol Kalimat dalam kalkulus predikat dibuat dari simbol-simbol berikut : a. Simbol Kebenaran : true dan false b. Simbol Konstanta : a, b, c, a1, b1, … c. Simbol variabel : x, y, z, x1, x2, … d. Simbol fungsi : f, g, h, g1, f1, h1, …

Setiap simbol fungsi mempunyai arity yang menyatakan banyaknya parameter/ argumen yang harus dipenuhi.

e. Simbol Predikat (menyatakan relasi) : p, q, r, s, p1, q1, r1, … Setiap simbol predikat juga memiliki arity

Catatan : Objek didalam kalkulus predikat dinyatakan sebagai konstanta atau variabel. Definisi : Term Term adalah sebuah ekspresi yang menyatakan objek. Term dibangun berdasarkan aturan-aturan sebagai berikut : - Semua konstanta adalah term - Semua variabel adalah term - Jika t1, t2, …, tn adalah (n ≥ 1) dan f adalah fungsi dengan arity = n, maka fungsi

f(t1,t2, …, tn) adalah term - Jika A adalah kalimat, sedang s dan t adalah term, maka kondisional if A then s else t

adalah term Contoh : 1. f(a,x) adalah term

(a dan x adalah term, f adalah simbol fungsi dan semua fungsi adalah term) 2. g(x, f(a,x)) adalah term Definisi : Proposisi Proposisi digunakan untuk merepresentasikan relasi antar objek Proposisi dibangun berdasarkan aturan sebagai berikut : - Simbol kebenaran adalah proposisi - Jika t1, t2, …, tn adalah term dan p adalah simbol predikat dengan n – ary maka

p (t1,t2, …, tn) adalah proposisi Contoh : p (a, x, f (a,x)) adalah proposisi, karena a, x, f (a,x) adalah term, dan p adalah simbol predikat 3-ary

Page 53: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 53

Definisi : Kalimat Kalimat dalam kalkulus predikat dibangun dengan aturan : 1. Setiap proposisi adalah kalimat 2. Jika A, B, C adalah kalimat maka :

• Negasi (not A) adalah kalimat • Konjungsi A dengan B: (A and B) adalah kalimat • Disjungsi A dengan B : (A or B) adalah kalimat • Implikasi (If A then B) adalah kalimat • Ekivalensi A dan B (A if and only if B) adalah kalimat • Kondisional if A then Belse C adalah kalimat.

3. Jika A adalah kalimat dan x adalah variabel maka : (For all x) A adalah kalimat (For some x) A adalah kalimat

Catatan : kemunculan A dikatakan berada dalam lingkup kuantifier Contoh : 1. if (for all x) p(a, b, x) then g (y) else f(a, y) adalah term 2. if (for all x) p(a, b, x) then (for some y) q(y) else not p(a, b, c) adalah kalimat Definisi Ekspresi Suatu ekspresi dalam kalkulus predikat dapat berupa kalimat atau term Contoh : - x merupakan ekspresi - f(x,y) merupakan ekspresi - (for some x) p(x) merupakan ekspresi Definisi : Subterm, Subkalimat, SubEkspresi - Subterm dari term t atau dari kalimat A adalah setiap term antara yang digunakan untuk

membangun t atau A - Subkalimat adalah setiap kalimat antara yang digunakan untuk membangun term atau

kalimat yang lebih luas - Subekspresi adalah subterm atau subkalimat yang terdapat pada sebuah ekspresi Contoh : Sebutkan semua subterm dan subkalimat yang terdapat pada ekspresi berikut :

E : if (for all x) q (x, f(a) then f (a) else b Subterm : a, x, f(a), b, if (for all x) q (x, f(a) then f (a) else b Subkalimat : q(x, f(a), (for all x) q(x,f(a)) Semuanya merupakan subekspresi dari E

Page 54: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 54

4.2 REPRESENTASI KALIMAT Contoh representasi bahasa alami ke dalam Kalkulus Predikat

• Ada Apel berwarna merah (FOR SOME x) ( Apel(x) AND Merah(x))

• Semua apel berwarna merah (FOR ALL x) ( IF Apel(x) THEN Merah(x))

• Setiap orang mencintai seseorang (FOR ALL x) (FOR SOME y) LOVES(x,y

• Ani dicintai banyak orang (FOR ALL x) LOVES(x, Ani)

• Semua Apel berwarna merah terasa manis (FOR ALL x) IF (A(x) AND R(x)) THEN M(x) (FOR ALL x) IF (A(x) THEN (IF R(x) THEN M(x)))

• Tidak semua apel berwarna hijau terasa manis NOT ((FOR ALL x) (IF (A(x) AND R(x)) THEN M(x))) (FOR SOME x) (A(x) AND R(x) AND NOT M(x)) 4.3 VARIABEL BEBAS ATAU TERIKAT Suatu variabel dikatakan terikat dalam sebuah ekspresi jika sedikitnya ada satu kemunculan x terikat pada ekspresi tersebut Sebaliknya dikatakan variabel bebas jika sedikitnya ada satu kemunculan bebas dalam ekspresi tersebut. Definisi : Kemunculan Bebas dan Terikat Misalkan x adalah variabel dan A adalah ekspresi. Kemunculan x adalah terikat jika x berada didalam lingkup suatu kuantifier dan x terikat oleh kuantifier terdekat Kemunculan x bebas jika tidak berada dalam lingkup suatu kuantifier Contoh : (FOR ALL x) [p(x,y) AND (FOR SOME y) q(y,z)] Keterangan : x pada p(x, y) adalah terikat y pada p(x, y) adalah bebas y pada q(y, z) adalah terikat z pada q(y, z) adalah bebas

Page 55: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 55

Kemunculan variabel terikat dipengaruhi oleh kemunculan kuantifier yang paling dekat. Contoh : (FOR ALL x) [p(x) OR (FOR SOME x) (FOR ALL y) r(x, y)] Keterangan : variabel x pada p(x) dipengaruhi kuantifier FOR ALL x variabel x pada r(x, y) dipengaruhi kuantifier FOR SOME x Catatan : Perbedaan antara variabel Bebas dan Variabel Terikat adalah : Variabel Bebas : Nilainya diberikan oleh interpretasi Variabel Terikat : Nilainya terbatas dari interpretasi yang diberikan Definisi : Kalimat Tertutup Sebuah kalimat dikatakan tertutup jika tidak mempunyai kemunculan bebas dari variabel-variabelnya Contoh : 1. (FOR ALL x) (FOR SOME y) p(x, y) adalah kalimat tertutup 2. (FOR ALL x) p(x, y) adalah bukan merupakan kalimat tertutup Definisi : Simbol Bebas Simbol bebas dari ekspresi A adalah :

• variabel-variabel bebas • semua konstanta • semua simbol fungsi • semua simbol predikat • dari ekspresi A

4.4 INTERPRETASI Definisi : Interpretasi Misal D adalah sebarang himpunan tak kosong, maka sebuah interpretasi I dalam domain D akan memberi nilai pada setiap simbol konstanta, variabel bebas, fungsi dan predikat yang ada pada kalimat dengan aturan sebagai berikut : - Untuk setiap konstanta a, yaitu elemen a1 ari D - Untuk setiap variabel x, yaitu elemen x1 dari D - Untuk setiap simbol fungsi f dengan arity = n , yaitu : - Fungsi f1(d1, d2, …, dn) dimana argumen d1, d2, …, dn merupakan elemen dari D, dan

nilai fungsi f1(d1, d2, …, dn) merupakan anggota D

Page 56: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 56

- Untuk setiap simbol predikat p dengan arity = n, yaitu relasi p1(d1, d2, …, dn) dimana argumen d1, d2, …, dn merupakan elemen dari D dan nilai p1(d1, d2, …, dn) adalah TRUE atau FALSE

Jadi untuk suatu ekspresi A, sebuah interpretasi I dikatakan interpretasi untuk A, jika I memberikan nilai kepada setiap simbol bebas dari A. 4.5 ARTI KALIMAT Arti kalimat ditentukan oleh interpretasi yang diberikan. Tetapi karena dalam kalkulus predikat mengandung pengertian objek, maka interpretasi dalam kalimat predikat harus juga mendefinisikan suatu domain yaitu himpunan objek yang memberi arti pada term. Suatu interpretasi harus memberi nilai pada setiap simbol bebas pada kalimat tersebut. Misalkan ada kalimat tertutup : A : IF (FOR ALL x) (FOR SOME y) p(x, y) THEN p(a, f(a)) Interpretasi untuk kalimat A harus • Mendefinisikan Domain • Memberikan nilai untuk simbol bebas dalam hal ini :

o Konstanta a o Simbol fungsi f o Simbol p

Contoh : 1. Diberikan interpretasi I dengan Domain D adalah himpunan bilangan integer positif,

dimana : a = 0 p = relasi “lebih besar” yaitu : p(d1, d2) = (d1 > d2) f = fungsi suksesor yaitu f(d) = d + 1 Maka berdasarkan interpretasi I, kalimat tersebut dapat diartikan sebagai : IF untuk setiap integer x Ada integer y sedemikian sehingga x > y THEN 0 > 0 + 1

2. Misalkan interpretasi J dengan domain bilangan interger positif, yang akan memberi

nilai : a = 0 p = relasi “ketidaksamaan” yaitu : p(d1, d2) = (d1 ≠ d2) f = fungsi predesesor yaitu f(d) = d - 1 Maka berdasarkan interpretasi J, kalimat tersebut dapat diartikan sebagai : IF untuk setiap integer x Ada integer y sedemikian sehingga x ≠ y THEN 0 ≠ 0 – 1

Page 57: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 57

Contoh Soal : Diberikan Ekspresi : E = IF p(x, f(x)) THEN (FOR SOME y) p(a, y) 1. Misalkan I adalah interpretasi untuk E dengan Domain bilangan real; dimana

a = √2 x = Π f = fungsi “dibagi 2” yaitu : f1(d1) = d1/2 p = relasi “lebih besar atau sama dengan” yaitu p(d1, d2) = (d1 ≥ d2)

2. Misalkan J adalah interpretasi untuk E dengan Domain semua orang; dimana

a = Soeharto x = Soekarno f = fungsi “Ibu dari” yaitu : f1(d1) = ibu dari d1 p = relasi “anak dari” yaitu p(d1, d2) = d1 adalah anak dari d2

Apakah arti ekspresi E berdasarkan interpretasi I dan interpretasi J ? 4.6 ATURAN SEMANTIK Definisi : Aturan Semantik Dasar Misal A adalah suatu ekspresi dan I adalah interpretasi untuk A yang meliputi domain tak kosong D. Maka nilai dibawah I ditentukan berdasarkan aturan semantik sebagai berikut : • Nilai suatu konstanta a adalah elemen domain D • Nilai variabel x adalah elemen domain D • Nilai aplikasi f1(t1, t2, …, tn) adalah elemen domain D dimana f1(t1, t2, …, tn) f adalah

fungsi yang diberikan kepada f dan t1, t2, …, tn adalah nilai term berdasarkan interpretasi I

• Nilai Term kondisional if A then s else t adalah nilai term s jika A bernilai TRUE dan sama dengan nilai term t jika A bernilai FALSE

• Nilai proposisi p1(t1, t2, …, tn) adalah nilai kebenaran TRUE atau FALSE dimana p adalah relasi yang diberikan oleh interpretasi I dan nilai dari t1, t2, …, tn berdasarkan I.

• Aturan untuk penghubung logik (not, or, dsb) sama dengan aturan pada kalkulus proposisi

Page 58: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 58

4.7 INTERPRETASI YANG DIPERLUAS Misal I adalah suatu interpretasi yang mencakup domain D maka untuk sembarang variabel x dan elemen d pada domain D, interpretasi yang diperluas : < x d > o I dari I adalah interpretasi yang mencakup domain D dimana : 1. Variabel x diberik nilai elemen domain D 2. Setiap variabel y (selain x) diberi nilai sama dengan elemen domain y1 (yaitu nilai

berdasar interpretasi D. jika y tidak mempunyai nilai berdasar I maka y juga tidak mempunyai nilai berdasar < x d > o I

3. Setiap konstanta a, simbol fungsi f, dan simbol predikat p diberi nilai sesuai dengan nilai aslinya yaitu aI, fI, pI

Contoh : 1. I adalah interpretasi yang meliputi bilangan integer, dengan

x = 1 y = 2 Maka perluasan interpretasi terhadap I : < x 3 > o I akan memberikan nilai : x = 3

y = 2

2. I adalah interpretasi yang meliputi bilangan integer, dengan f adalah simbol fungsi biner, + adalah fungsi penambahan integer maka : < f + > o I adalah interpretasi yang meliputi domain bilangan integer dengan f fungsi penambahan +.

Sifat interpretasi yang diperluas Jika I adalah interpretasi untuk kalimat berbentuk

(FOR ALL x) A atau (FOR SOME x) A, maka < x d > o I adalah interpretasi yang berlaku untuk A juga 4.8 ATURAN SEMANTIK UNTUK KUANTIFIER 1. Aturan FOR ALL

Kalimat (FOR ALL x) A bernilai TRUE berdasarkan interpretasi I jika : Untuk setiap elemen d dari domain D menyebabkan subkalimat A bernilai TRUE berdasarkan interpretasi yang diperluas < x d> o I Kalimat (FOR ALL x) A bernilai FALSE berdasarkan interpretasi I jika : Ada elemen d dari domain D sedemikian sehingga subkalimat A bernilai FALSE berdasarkan interpretasi yang diperluas < x d> o I

Page 59: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 59

2. Aturan FOR SOME

Kalimat (FOR SOME x) A bernilai FALSE berdasarkan interpretasi I jika : Untuk setiap elemen d dari domain D menyebabkan subkalimat A bernilai FALSE berdasarkan interpretasi yang diperluas < x d> o I Kalimat (FOR SOME x) A bernilai TRUE berdasarkan interpretasi I jika : Ada elemen d dari domain D sedemikian sehingga subkalimat A bernilai TRUE berdasarkan interpretasi yang diperluas < x d> o I

Contoh 1. A : (FOR SOME x) p(x,y)

Diberikan interpretasi I yang meliputi himpunan bilangan integer positif y = 2 p : relasi “kurang dari”, yaitu p1(d1, d2) = d1 < d2 Berdasarkan aturan (FOR SOME x) maka (FOR SOME x) p(x, y) bernilai TRUE jika ada elemen dari D sehingga nilai p(x, y) TRUE berdasarkan interpretasi < x d > o I Misal diambil d = 1 maka perluasan interpretasi menjadi < x 1 > o I sehingga berdasarkan aturan proposisi diperoleh bahwa p(1, 2) yaitu 1 < 2 adalah TRUE

2. B : IF (FOR ALL x) (FOR SOME y) p(x, y) THEN p(a, f(a))

Misal I adalah interpretasi untuk B yang meliputi domain bilangan real positif dimana: a = 1 f : fungsi “akar dari” yaitu f1(d) = √d p : relasi “tidak sama dengan”, yaitu p1(d1, d2) = d1 ≠ d2 Misal diasumsikan bahwa A bernilai FALSE Maka harus diperhatikan bahwa : Antisenden : (FOR ALL x) (FOR SOME y) p(x, y) bernilai TRUE Konsekuen : p(a, f(a)) bernilai FALSE Untuk lebih mudahnya, dimulai dari Konsekuen karena bentuknya lebih sedehana. Berdasakan aturan proposisi, maka nilai konsekuen p(a, f(a)) yaitu 1 ≠ √1 adalah FALSE berdasarkan I Antisenden : berdasarkan Aturan (FOR ALL x) Untuk setiap elemen d1 dari D, subkalimat (for some y) p(x,y) bernilai TRUE berdasarkan < x d > o I

Page 60: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 60

Berdasarkan Aturan (FOR SOME y) Untuk setiap elemen d1 dari D, ada elemen d2 sedemikian sehingga p(x,y) bernilai TRUE berdasarkan < y d2 > o < x d1 > o I Misal ambil sembarang elemen domain dan d2 = d1 + 1 Maka berdasarkan aturan proposisi, nilai p(x,y) yaitu p(d1, d2) Berarti p(d1, d1+1) menyatakan bahwa d1 ≠ d1 + 1 adalah TRUE berdasarkan < y d2 > o < x d1 > o I Jadi dapat disimpulkan bahwa kalimat B bernilai FALSE berdasarkan I

4.9 KECOCOKAN Definisi • Dua interpretasi dikatakan cocok jika keduanya memberni nilai yang sama untuk

simbol-simbolnya atau keduanya tidak memberi nilai untuk simbol-simbolnya • Dua interpretasi I dan J cocok untuk ekspresi A jika nilai A berdasarkan I sama dengan

nilai A berdasarkan J atau I dan J bukan interpretasi untuk A Contoh : Misalkan I adalah interpretasi yang meliputi bilangan integer dengan : a 0 b 2 x -1 f fungsi suksessor f1(d) = d + 1 dan interpretasi J yang meliputi integer dengan : a 0 x 1 f fungsi predesesor f1(d) = d – 1 • I dan J cocok untuk konstanta a • I dan J cocok untuk simbol predikat p • I dan J tidak cocok untuk variabel x • I dan J cocok untuk ekspresi f(x) • I dan J cocok untuk ekspresi f(y) • I dan J tidak cocok untuk ekspresi f(b), karena I adalah interpretasi untuk f(b) tetapi

tidak untuk J

Page 61: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 61

VALIDITAS Validitas di dalam kalkulus predikat didefinisikan hanya untuk kalimat tertutup, yaitu kalimat yang tidak memiliki variabel bebas. Definisi Sebuah kalimat A dikatakan valid jika kalimat tersebut bernilai TRUE berdasarkan setiap interpretasi untuk A Pembuktian validitas kalimat dapat menggunakan : Dengan membuktikan bahwa kalimat tertutup A adalah VALID (biasanya lebih “enak” untuk kalimat-kalimat yang memiliki penghubung logik : IFF, AND, NOT) Dengan membuktikan bahwa kalimat tertutup A adalah TIDAK VALID dengan cara mencari satu interpretasi tertentu yang menyebabkan kalimat tersebut bernilai FALSE. (biasanya untuk kalimat-kalimat yang memiliki penghubung logik : IF-THEN, OR) Contoh Cara 1 Misalkan ingin dibuktikan validitas kalimat A berikut : 1. A : [ NOT (FOR ALL x) p(x) ] IFF [ (FOR SOME x) NOT p(x) ]

Berdasarkan aturan IFF, cukup diperlihatkan bahwa : NOT (FOR ALL x) p(x) ] dan [ (FOR SOME x) NOT p(x) ] memiliki nilai kebenaran yang sama berdasarkan setiap interpretasi, atau dengan kata lain subkalimat pertama bernilai TRUE tepat bilai subkalimat kedua juga bernilai TRUE Misalkan terdapat sebarang interpretasi I untuk A, maka NOT (FOR ALL x) p(x) bernilai TRUE berdasarkan I Tepat bila (berdasarkan aturan NOT) (FOR ALL x) p(x) bernilai FALSE berdasarkan I Tepat bila (berdasarkan (FOR ALL x)) Ada elemen d di dalam domain D Sehingga p(x) bernilai FALSE berdasarkan < x d > o I Tepat bila (berdasarkan aturan NOT) Ada elemen d di dalam domain D sehingga NOT p(x) bernilai TRUE berdasarkan < x d > o I Tepat bila (berdasarkan aturan (FOR SOME x)) (FOR SOME x) NOT p(x) bernilai TRUE berdasarkan Interpretasi I

Page 62: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 62

2. Misalkan ingin dibuktikan validitas kalimat B berikut : (cara 2)

B : IF (FOR SOME y) (FOR ALL x) q(x, y) THEN (FOR ALL x) (FOR SOME y) q(x, y)

Asumsikan bahwa B tidak valid, sehingga bahwa untuk suatu interpretasi I untuk B Jika Antisenden : (FOR SOME y) (FOR ALL x) q(x, y) bernilai TRUE berdasarkan I maka konsekuen (FOR ALL x) (FOR SOME y) q(x, y) bernilai FALSE berdasarkan I Karena Antisenden bernilai TRUE berdasarkan I, maka (berdasarkan aturan FOR SOME x) Ada elemen d1 di dalam domain D sehingga (FOR ALL x) q(x, y) bernilai TRUE berdasarkan < y d > o I Tepat bila (berdasarkan aturan FOR ALL x) Ada elemen d di dalam domain D sedemikian sehingga untuk setiap elemen d2 di dalam domain D sedemikian sehingga q(x, y) bernilai TRUE berdasarkan < x d2 > o < y d1 > o I …………………….. (1) Karena konsekuen bernilai FALSE berdasarkan I, Maka (berdasarkan aturan FOR ALL x) Ada elemen e di dalam domain D sehingga (FOR SOME y) q(x, y) bernilai FALSE berdasarkan < x e > o I Tepat bila (berdasarkan aturan FOR SOME x) Ada elemen e1 di dalam domain D sedemikian sehingga untuk semua elemen e2 di dalam domain D sedemikian sehingga q(x, y) bernilai FALSE berdasarkan <y e2 > o < x e1 > o I ……………………………(2) Berdasarkan (1) dan (2) kita dapat mengambil nilai elemen d1 sama dengan e2 dan d2 sama dengan e1, sehingga dari (1) diperoleh : q(x, y) bernilai TRUE berdasarkan < x e1 > o < y d1 > o I …………….. (3) dandari (2) diperoleh q(x, y) bernilai FALSE berdasarkan <y d1 > o < x e1 > o I ……………(2) Karena variabel x dan y berbeda, maka interpretasi < x e1 > o < y d1 > o I dan < y d1 > o < x e1 > o I adalah identik, sehingga terlihat bahwa (3) dan (4) saling berkontradiksi. Berari asumsi bahwa B tidak valid adalah tidak benar, sehingga B VALID

Page 63: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 63

4.11 SOAL LATIHAN 1. Diberikan ekspresi sebagai berikut : E : if (FOR SOME x) (FOR ALL y) p(x,y) Then q(a, f(a)) Else q(a,x)

a. Apakah E adalah Kalimat atau Term ?. Berikan alasannya ! b. Tuliskan semua SubTerm, SubKalimat, SubEkspresi !

2. Gantilah proposisi-proposisi di bawah ini dengan lambang masing-masing. Huruf yang

dicetak tebal/miring harus dijadikan lambang :

a. Tidak ada gading yang tidak retak b. Ada Gajah yang jantan dan ada yang betina c. Tidak semua pegawai negeri itu manusia korup d. Hanya polisilah pihak yang berwenang mengadakan penyidikan, kalau ada orang

yang melanggar hukum 3. Misalkan I adalah interpretasi dengan domain bilangan integer lebih besar daripada 5 :

Dimana : a = 6 x = 10 b = 17 y = 15 c = 11 f adalah fungsi dua kali dimana fI(d) = 2 * d G adalah relasi ‘lebih baik’ dimana GI(d1, d2) = d1 > d2 Tentukan nilai : a. G(y, f(a)) berdasarkan I b. G(a, f(x) berdasarkan I c. G[if G(x,y) then f(a) else f(b), x] berdasarkan I d. (FOR SOME y) [G(x,y) or G(f(x), y)] e. (FOR ALL y) (FOR SOME x) G(x,y) berdasarkan I

4. Buktikan bahwa kalimat B berikut ini adalah VALID, dengan menggunakan sebarang interpretasi :

B : not (FOR ALL x) G(x) IFF (FOR SOME x) not (G(x))

Page 64: 1.1.1 BAB I PENDAHULUAN TEORI HIMPUNAN … MATEMATIKA INSTITUT TEKNOLOGI TELKOM | 2 2. Notasi khusus himpunan atau simbol standar Dengan simbol-simbol standar yang biasa digunakan

LOGIKA MATEMATIKA

INSTITUT TEKNOLOGI TELKOM | 64

DAFTAR PUSTAKA

[1] Manna, Zohar. The Logical Basis For Computer Programming. Addison Wesley Publishing. 1985

[2] Korfhage, Robert. Logic And Algotrihms. USA. 1966 [3] Diktat Logika Matematika, Jurusan Teknik Informatika ITB [4] Hendrowati, Retno. Hariyanto, Bambang. Logika Matematika, Penerbit Informatika,

Bandung [5] Rossen, Kenneth, Discret Mathematics and it’s Application [6] …., Discret Mathematics