Logika Informatika

Rabu, 16 Desember 2015

Konversi SOP dan POS

konversi ke bentuk Sum Of Product (SOP)

Cara konversi ke bentuk SOP adalah sebagai berikut :

Nyatakan fungsi boolean F = A +B'C dalam SOP

Jawab : (cara:)

a) harus dilengkapai dahulu literal untum tiap suku agar sama

- suku ke -1 A = A(B+B')

=AB+AB'

Lengkapi literal untuk tiap suku

Suku ke -1-1 :AB =AB (C+C')

=ABC + ABC'

Suku ke-1-2 : AB' = AB'(C+C')

= AB'C + AB'C'

Sehingga suku ke -1 menjadi :

ABC + ABC' +AB'C +AB'C'

-SUKU KE -2 : B'C = B'C (A+A')

= AB'C + A'B'C

b) jumlah semua suku dengan literal yang lengkap ,sehingga :

F = ABC + ABC' + AB'C + AB'C' + AB'C + A'B'C

c) sederhanakan agar tidak ada suku yang sama,sehingga :

F = ABC + ABC' + AB'C +AB'C' + A'B'C

bentuk SOP tersebut adalah F =m1+m4+m5+m6+m7 atau dapat ditulis dengan notasi :

F(A,B,C) = £(1,4,5,6,7)

(notasi ini adalah notasi umum untuk menyatakan bentuk kanonik untuk fungsi bookean F)

Konversi ke bentuk Product Of Sum (POS)

Cara konversi kebentuk POS adalah sebagai berikut :

Nyatakan fungsi boolean F = xy +xz' dalam POS

Jawab :

A) bentuk fungsi dalam POS

F = xy + x'z

= (xy + x') (xy+z) (distributif)

= (x+x') (y+x') (x+z) (y+z)

= (x'+y) (x+z) (y+z)

B) lengkapi literal tiap suku :

suku ke-1 x'y = x' +y +zz'

= (x'y + z) (x'+ y +z')

Suku ke-2 x+z = x+z +yy'

= (x+y+z) (x+y'z)

Suku ke -3 y+z = y+z+xx'

= (x+y+z) (x'+y+z)

C) jumlah unuk semua suku dengan literal yang lengkap :

F = (x+y+z) (x+y'+z) (x'y+z) (x'+y+z')

= M0M2M4M5

konversi ke bentuk Sum Of Produc (SOP)

Cara konversi ke bentuk SOP adalah sebagai berikut :

Nyatakan fungsi boolean F = A +B'C dalam SOP

Jawab : (cara:)

a) harus dilengkapai dahulu literal untum tiap suku agar sama

- suku ke -1 A = A(B+B')

=AB+AB'

Lengkapi literal untuk tiap suku

Suku ke -1-1 :AB =AB (C+C')

=ABC + ABC'

Suku ke-1-2 : AB' = AB'(C+C')

= AB'C + AB'C'

Sehingga suku ke -1 menjadi :

ABC + ABC' +AB'C +AB'C'

-SUKU KE -2 : B'C = B'C (A+A')

= AB'C + A'B'C

b) jumlah semua suku dengan literal yang lengkap ,sehingga :

F = ABC + ABC' + AB'C + AB'C' + AB'C + A'B'C

c) sederhanakan agar tidak ada suku yang sama,sehingga :

F = ABC + ABC' + AB'C +AB'C' + A'B'C

bentuk SOP tersebut adalah F =m1+m4+m5+m6+m7 atau dapat ditulis dengan notasi :

F(A,B,C) = £(1,4,5,6,7)

(notasi ini adalah notasi umum untuk menyatakan bentuk kanonik untuk fungsi bookean F)

Konversi ke bentuk Product Of Sum (POS)

Cara konversi kebentuk POS adalah sebagai berikut :

Nyatakan fungsi boolean F = xy +xz' dalam POS

Jawab :

A) bentuk fungsi dalam POS

F = xy + x'z

= (xy + x') (xy+z) (distributif)

= (x+x') (y+x') (x+z) (y+z)

= (x'+y) (x+z) (y+z)

B) lengkapi literal tiap suku :

suku ke-1 x'y = x' +y +zz'

= (x'y + z) (x'+ y +z')

Suku ke-2 x+z = x+z +yy'

= (x+y+z) (x+y'z)

Suku ke -3 y+z = y+z+xx'

= (x+y+z) (x'+y+z)

C) jumlah unuk semua suku dengan literal yang lengkap :

F = (x+y+z) (x+y'+z) (x'y+z) (x'+y+z')

= M0M2M4M5

Teori Himpunan

1. Himpunan

Konsep “Himpunan” merupakan konsep dasar dalam matematika. Himpunan adalah kumpulan objek yang didefinisikan secara jelas, Objek-objek itu disebut elemen-elemen atau anggota-anggota himpuan.

a. Himpunan

Koleksi objek yang didefiniskan secar jelas dalam sembarang urutan (tak diperhatikan keberurutan objek-objek anggotanya).

b. Anggota Himpunan

objek Milik himpunan disebut anggota atau elemen himpunan. Jika P milik himpunan A, ditulis pEA, dibaca “p adalah anggota Himpunan A” atau “p milik himpunan A”. Jika objek q bukan milik himpunan A, ditulis qE A.

c. Himpunan Hingga dan Takhingga (Finite and Infinite Set)

Himpunan hingga (finite set) jika himpunan berisi sejumlah hingga elemen berbeda. selain itu disebut himpunan tak hingga (infinite set).

Notasi dan Definisi

Notasi Himpunan

Himpunan dinyatakan dengan huruf besar : A, B, C, ... Elemen-Elemen dalam himpunan dinyatakan dengan huruf kecil : a, b, c, ...........

Contoh

1. Himpunan A terdiri atas bilangan 1,3,5,7, maka dapat dituliskan sebagai :

A = {1,3,5,7}; 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

Terdapat tiga cara penulisan himpunan, yaitu :

a. Pendaftaran (List), mendaftarkan semua anggota himpunan.

A = {1, 2, 3, 4, 5, 6, 7, 8, 9 }

b. Deskripsi (Rule atau Predikat), mendefinisikan suatu aturan atau predikat yang merupakan batasan bagi anggota-anggota himpunan.

A = { x | P(x) }

misalnya : A = { x | x<10 dan x E bilangan asli }

Definisi-definisi

Definisi-definisi pada teori himpunan :

a. Himpunan bagian (subset)

A $\subseteq$ B ; A himpunan bagian dari B bila tiap elemen A adalah elemen B

A $\subseteq$ B ; A himpunan bagian asli dari B bila tiap elemen A adalah elemen B. tapi himpunan A tidak sama dengan B atau bila A $\subseteq$ B dan A ≠ B A = B bila A $\subseteq$ B dan B $\subseteq$ A

b. Himpunan kosong

Himpunan kosong adalah himpunan yang tidak mempunyai elemen. Himpunan kosong selalu merupakan salah satu himpunan bagiannya.

Komplemen fungsi

a. Definisi

Fungsi komplemen dari suatu fungsi F, yaitu F’ dapat dengan menukarkan nilai 0 menjadi 1, dan nilai 1 menjadi 0. Terdapat dua cara untuk memperoleh funsi komplemen, yaitu :

1. Penerapan Hukum De Morgan yang diperluas.

2. Penerpapan prinsisp dualitas.

b. Penerapan Hukum De Morgan Yang Diperluas

Kita dapat memperoleh fungsi komplemen dengan penerapan Hukum De Morgan yang di perluas.

Hukum De Morgan Yang Diperluas :

( A + B + C )’ = (A+X)’, Misal B+C = X

= A’X’

= A’ . (B+C)’

= A’. (B’C’

= A’B’C’

c. Rumus Umum Hukum De Morgan Diperluas

(A+B+C+......+ H)’ = A’B’C’ ............H’ dan

(A B C D .........H)’ = A’ + B’ + C’ +.......H’

CONTOH

F1 = x (y’ z’ + yz)

F1 = [x (y’z’ + yz)]’

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

= x’ + (y’z’)’ . (yz)’

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

d. Penerapan Prinsip Dualitas

Penerapan prinsip dualitas dalam pencarian fungsi komplemen

adalah sebagai berikut:

1. Terapkan prinsip dualitas, yaitu carilah bentuk dualnya

2. Lakukan mengkoplemenkan terhadap tiap literal

CONTOH

1. Diketahui F1 = x (y’z’ + y z).

Pertanyaan : Tentukan F1’!

Jawab:

- Cari dual F1 = x + (y’ + z’) (y + z)

- Komplemenkan tiap literal = x’ + (y+z) (y’ + z’) = F1’

2. F(A,B,C) = Σ(1,4,5,6,7). S

Pertanyaan: Tentukan F’ (A,B,C)!

Jawab:

- F’(A,B,C) = Σ(0,2,3) = m0 + m2 + m3

3. Diketahui: F1 = x(y’z’ + yz)

Pertanyaan : Tentukan F1’ !

Jawab

- Cari dualnya F1, yaitu x + (y’ + z’) (y + z)

- Komplemenkan tiap literalnya : x’ + (y+z) (y’ + z’)

Selasa, 15 Desember 2015

Defiinisi dan Aksioma Aljabar Boolean

1. Definisi

Definisi 2.1 :
Aljabar Boolean adalah sistem aljabar yang berisi set S dngan dua operasi penjumlahan (+) dan perkalian (.) yang di definisikan pada set itu sehingga memenuhi ketentuan berikut :
1. Aturan A1 sampai A5, M1 sampai M3, M5, D1, dan D2.
2. Setiap elemen adalah "idempotent", yaitu if a E S, maka a.a = a

Definisi 2.2 :
Aljabar Boolean adalah sistem aljabar yang berisi set S dengan dua operasi + dan . yang didefinisikan pada set, sehinga stiap elemen a, b, dan c dari S mempunyai sifat-sift atau aksioma-aksioma berikut :

A1.	a + b E S	<closure>
M1.	a.b E S	<closure>
A2.	A + (b + c) = (a + b) + c	<asosiatif>
M2.	a.(b.c) = (a.b).c	<asosiatif>
A3.	Jika 0 E S maka untuk setiap a E S, adalah a + 0 = 0 + a = a	<identitas>
M3.	Jika 1 E S maka untuk setiap a E 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 E S, dan a’ E 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 aa = a

Teorema 2.2

Untuk setiap elemen a, berlaku : a + 1 = 1 dan a.0 = 0

Teorema 2.3

Untuk setiap elemen a dan b, berlaku : a + a.b = a dan a(a + b) = a (disebut dengan hukum Penyerepan)

Teorema 2.4

Untuk setiap elemen a dan b, berlaku : (a.b)’ = a’ + b’ dan (a + b)’ = a’b’ (disebut dengan Hukum de Morgan)

Teorema 2.5

0’ = 1 dan 1’ = 0

Teorema 2.6

Jika suatu aljabar Boolean berisi paling sedikit dua elemen berbeda, maka 0 = 1 . Pembuktian rumus dualitas diakukan berdasar aksioma d sifat dari aljabar Boolean, yaitu :

1a. Pernyataan : a + a = a

Bukti

a + a = (a + a) (1) identitas

(a + a) (a + a’) komplemen

a + (a.a’) distributif

a + 0 komplemen

a identitas

1b. Pernyataan : a.a = a

Bukti

a. a = a.a + 0 identitas (dual dari 1a)

a.a + a.a’ komplemen

a (a.a’) distributif

a.1 komplemen

a identitas

2a. Pernyataan : a + 1 = a

Bukti

a + 1 = a + (a + a’) komplemen

(a + a) + a’ asosiatif

a + a’ teorema (1a)

1 komplemen

2b. Pernyataan : a.0 = a

Bukti

a.0 = a.(a.a’) komplemen (dual dari 2)

(a.a).a’ asosiatif

a.a’ idempoten

0 komplemen

3a. Pernyataan : a + ab = a

Bukti

a + ab = a.1 + a.b identitas

a(1 + b) distributif

a + 1 teorema (2a)

a identitas

3b. Pernyataan : a.(a + b) = a

Bukti

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

4a. Pernyataan : (a.b)’ = a

Bukti

(a.b)’ = a’ + b’

diketahui : (ab) (ab)’ = 0

diperlihatkan : (ab) (a’ + b’) = 0

Bukti

(ab) (a’ + b’) = aba’ + abb’ distributif

0.b + a.0 komplemen

0 + 0 teorema (2b)

0 identitas

4b. Pernyataan : (a.b) = a

Bukti

(a = b)’ = a’b’

diketahui : (ab) + (ab)’ = 1

diperlihatkan : ab + a’ + b’ = 1

Bukti

ab + (a’ + b’) = (a + a’ + b) (b + a’ + b) distributif

(1 + b’) (1 + a’) komplemen

1.1 teorema (2a)

1 identitas

2.3 Aturan <= (Lebih Kecil Daripada)

Definisi 2.3

x dan y adalah elemen-elemen ari 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 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

Teorema 2.8

Jika x, y, dan z adalah elemen-elemen dari aljabar Boolean, maka <= mempunyai sifat-sifat berikut :

· 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 penyelesaian Konversi (x’)’ = x