ALJABAR BOOLEAN

DEFINISI ALJABAR BOOLEAN

Misalkan terdapat

- Dua operator biner: + dan ⋅

 - Sebuah operator uner: ’.

 - B : himpunan yang didefinisikan pada operator +, ⋅, dan ’

 - 0 dan 1 adalah dua elemen yang berbeda dari B.

 Tupel (B, +, ⋅, ’)

disebut aljabar Boolean jika untuk setiap a, b, c ∈ B berlaku aksioma-aksioma atau postulat Huntington berikut:

1.      Closure: (i) a + b ∈ B

(ii) a ⋅ b ∈ B

2.      Identitas: (i) a + 0 = a

 (ii) a ⋅ 1 = a

3.      Komutatif: (i) a + b = b + a

 (ii) a ⋅ b = b . a

4.      Distributif:(i) a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c)

(ii) a + (b ⋅ c) = (a + b) ⋅ (a + c)

5.      Komplemen1: (i) a + a’ = 1

 (ii) a ⋅ a’ = 0

 ALJABAR BOOLEAN DUA-NILAI

Aljabar Boolean dua-nilai:

- B = {0, 1}

 - operator biner, + dan ⋅

 - operator uner, ’

 - Kaidah untuk operator biner dan operator uner:

 

Cek apakah memenuhi postulat Huntington:

1. Closure : jelas berlaku

2. Identitas: jelas berlaku karena dari tabel dapat kita lihat bahwa:

(i) 0 + 1 = 1 + 0 = 1

(ii) 1 ⋅ 0 = 0 ⋅ 1 = 0

3. Komutatif: jelas berlaku dengan melihat simetri tabel operatorbiner

4. Distributif:

(i) a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c) dapat ditunjukkan benar dari tabel operator biner di atas dengan membentuk tabel kebenaran:

(ii) Hukum distributif a + (b ⋅ c) = (a + b) ⋅ (a + c) dapat ditunjukkan benar dengan membuat tabel kebenaran dengancara yang sama seperti (i).

5. Komplemen:

 (i) a + a‘ = 1, karena 0 + 0’= 0 + 1 = 1 dan 1 + 1’= 1 + 0 = 1

(ii) a ⋅ a = 0, karena 0 ⋅ 0’= 0 ⋅ 1 = 0 dan 1 ⋅ 1’ = 1 ⋅ 0 = 0

Karena kelima postulat Huntington dipenuhi, maka terbukti bahwaB = {0, 1} bersama-sama dengan operator biner + dan ⋅operator komplemen ‘ merupakan aljabar Boolean

EKSPRESI BOOLEAN

o   Misalkan (B, +, ⋅, ’) adalah sebuah aljabar Boolean. Suatuekspresi Boolean dalam (B, +, ⋅, ’) adalah: (i) setiap elemen di dalam B, (ii) setiap peubah, (iii) jika e1 dan e2 adalah ekspresi Boolean, maka e1 + e2, e1 ⋅e2, e1’ adalah ekspresi Boolean

Contoh: 0

1

 a

 b

a + b

 a ⋅ b

a’⋅ (b + c)

 a ⋅ b’ + a ⋅ b ⋅ c’ + b’, dan sebagainya

o   Dua ekspresi Boolean dikatakan ekivalen(dilambangkan dengan ‘=’) jika keduanya mempunyai nilai yang sama untuksetiap pemberian nilai-nilai kepada n peubah. Contoh:

 a ⋅ (b + c) = (a . b) + (a ⋅ c)

HUKUM-HUKUM ALJABAR BOOLEAN

FUNGSI BOOLEAN

Fungsi Boolean(disebut juga fungsi biner) adalah pemetaandari Bn ke Bmelalui ekspresi Boolean, kita menuliskannyasebagai f : Bn → B yang dalam hal ini Bnadalah himpunan yang beranggotakanpasangan terurut ganda-n (ordered n-tuple) di dalam daerah asal B.

Setiap ekspresi Boolean tidak lain merupakan fungsiBoolean.

Misalkan sebuah fungsi Boolean adalah f(x, y, z) = xyz + x’y + y’z

 Fungsi f memetakan nilai-nilai pasangan terurut ganda-3 (x, y, z) ke himpunan {0, 1}. Contohnya,

(1, 0, 1) yang berarti x = 1, y = 0, dan z = 1 sehingga f(1, 0, 1) = 1 ⋅ 0 ⋅ 1 + 1’ ⋅ 0 + 0’⋅ 1 = 0 + 0 + 1 = 1 .

BENTUK KANONIK

Ada dua macam bentuk kanonik:

1. Penjumlahan dari hasil kali (sum-of-product atau SOP)

2. Perkalian dari hasil jumlah (product-of-sum atau POS)

 Contoh:

1. f(x, y, z) = x’y’z + xy’z’ + xyz → SOP Setiap suku (term) disebut minterm

2. g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’) (x’ + y + z’)(x’ + y’ + z) → POS Setiap suku (term) disebut maxterm

 Setiap minterm/maxterm mengandung literal lengkap

Contoh :

Nyatakan tabel kebenaran di bawah ini dalam bentuk kanonik SOP dan POS.

Penyelesaian:

(a)    SOP

Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsisama dengan 1 adalah 001, 100, dan 111, maka fungsiBooleannya dalam bentuk kanonik SOP adalah

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

atau

(dengan menggunakan lambang minterm), f(x, y, z) = m1 + m4 + m7 = Σ (1, 4, 7)

(b)   POS

Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsisama dengan 0 adalah 000, 010, 011, 101, dan 110, makafungsi Booleannya dalam bentuk kanonik POS adalah

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

atau dalam bentuk lain,

 f(x, y, z) = M0 M2 M3 M5 M6 = Π(0, 2, 3, 5, 6)

 PENYEDERHANAAN FUNGSI BOOLEAN

Contoh.

 f(x, y) = x’y + xy’ + y’

disederhanakan menjadi

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

 Penyederhanaan fungsi Boolean dapat dilakukan dengan 3 cara:

1. Secara aljabar

2. Menggunakan Peta Karnaugh

3. Menggunakan metode Quine Mc Cluskey (metode Tabulasi)

1. PenyederhanaanSecaraAljabar

Contoh:

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

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

 = 1 ⋅ (x + y )

= x + y

2.      f(x, y, z) = x’y’z + x’yz + xy’

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

 = x’z + xz’

3.      f(x, y, z) = xy + x’z + yz

 = xy + x’z + yz(x + x’)

= xy + x’z + xyz + x’yz

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

 = xy + x’z

2.PetaKarnaugh

a. Peta Karnaugh dengan dua peubah 

b. Peta dengan tiga peubah

c. Peta dengan empat peubah

FUNGSI MATEMATIKA DISKRIT

      Dalam matematika diskrit konsep fungsi sangat penting, dimana fungsi merupakan relasi yang mempunyai syarat setiap anggota dari daerah definisi (domain) mempunyai pasangan tepat satu anggota dari daerah Hasil (codomain).

DEFINISI FUNGSI

Fungsi merupakan jenis khusus dari relasi. fungsi disebut juga sebagai pemetaan atau transformasi.
Diberikan dua himpunan A dan B, relasi biner f dari himpunan A ke B merupakan suatu fungsi jika setiap elemen di dalam himpunan A mempunyai pasangan tepat satu elemen himpunan B.
Apabila f adalah fungsi dari himpunan A ke B maka notasi fungsinya
f : A → B
Himpunan A disebut daerah definisi(domain) dan himpunan B disebut daerah hasil (codomain). Setiap domain tidak boleh mempunyai pasangan ganda. 

Contoh Fungsi :
               

f : A à B                                                                         f : A à B
A : {a,b,c,d}                                                                A : {a,b,c,d}
B : {1,2,3,4,5}                                                             B : {1,2,3}
f : {(a,1),(b,2),(c,4),(d,5)}                                          f : {(a,1),(b,2),(c,2),(d,3)}

Contoh yang buka Fungsi :

                

keduanya bukan merupakan sebuah fungsi karena di daerah domainnya tidak memiliki pasangan ataupun 1 domain memiliki pasangan ganda.

TERAPAN FUNGSI :

1. Formula pengisian nilai dalam bahasa pemrograman dinyatakan dengan assignment
Contoh diberikan rumusan fungsi f(x) = x2 +1 , f(x) = x +1 , apabila tidak didefinisikan secara khusus tentang daerah definisi maka daerah definisi dan daerah hasil adalah himpunan Himpunan bilangan riil misal R.
Dalam himpunan pasangan terurut fungsi didefinisikan sbb:
f = { (x1, x2}/ x ∈ R }

2. Kode program ( source code)

Fungsi yang dispesifikasikan dalam bahasa Pascal
Function abs(x: integer): integer;
Begin
if x < 0 then
abs := -x
else
abs := x;
end;
Relasi f = {(1,a),(2,b),(3,c) }dari himpunan A ke B, {1,2,3} ∈ A dan {a,b,c}∈ B merupa kan fungsi karena Relasi f memasangkan tepat satu anggota himpunan A dengan anggota himpunan B
Keterangan :
f(1) = a, f (2) = b dan f (3) = c
Himpunan A disebut daerah definisi dan himpunan B sebagai daerah hasil.

JENIS FUNGSI

• Fungsi Satu-satu (One-to-one)

Fungsi ini disebut koresponden satu-satu atau juga disebut injektif, jika dan hanya jika f(x)=f(y) , dimana x=y, untuk setiap x, dan y pada domain f. akan tetapi pada fungsi injektif ketika x≠y mengakibatkan f(x)≠f(y).

koresponden bukan satu-satu.

• Fungsi Naik Turun

Fungsi disebut naik ketika fungsi f memiliki nilai domain dan kodomain subhimpunan dari bilangan real, jika f(x) < f(y) ketika x < y , dan nilai y merupakan anggota domain dari f, sedangkan fungsi disebut turun jika f(x) > f(y) , ketika x < y, untuk x,  dan y adalah anggota domain dari f.

• Dipetakan Pada (Onto)

Merupakan fungsi satu-satu maupun onto.
beberapa contoh gambar fungsi.

• Fungsi Identitas

A merupakan sebuah himpunan, lalu fungsi identitas pada A adalah fungsi iA : A àA dan hal itu berlaku ketika i(x) = x, untuk setiap himpunan x є A.

• Fungsi Invers

merupakan fungsi kebalikan, yang asalnya f(a) = b, maka inversnya adalah fˉˈ(b) = a

• Fungsi Komposisi

dimisalkan fungsi g merupakan fungsi dari himpunan A ke B, notasi penulisannya adalah (f o g)(x) = f(g(x))


BEBERAPA FUNGSI KHUSUS

Beberapa fungsi khusus yang sering digunakan dalam bahasa pemrograman seperti fungsi floor, ceiling, modulo, faktorial, perpangkatan dan logaritmik.

1.Fungsi floor dan ceiling

Fungsi ini diperlukan untuk membulatkan ke bawah dan keatas. Fungsi floor diperlukan untuk membulatkan nilai pecahan kebawah, misalkan x bilangan riil maka bilangan floor dilambangkan ⎣x⎦. Fungsi ceiling diperlukan untuk membulatkan nilai pecahan keatas dan dilambangkan ⎡x⎤.

2.Fungsi Modulo

Fungsi modulo adalah fungsi dengan operator mod, misalkan b sembarang bilangan bulat dan m bilangan bulat positip maka b mod memberikan sisa pembagian bilangan bulat apabila b dibagi dengan m .

3.Fungsi hash

Misalkan dipunyai sel-sel pada memori komputer yang diberi indek dari 0 sampai dengan 10.

4.Fungsi faktorial

Untuk sembarang bilangan bulat non negatif n, faktorial dari n dilambangkan dengan n ! yang didefinisikan.
 

Logika Matematika

                                              Logika matematika

Logika matematika adalah cabang logika dan matematika yang mengandung kajian matematis logika dan aplikasi kajian ini pada bidang-bidang lain di luar matematika. Logika matematika berhubungan erat dengan ilmu komputer dan logika filosofis. Tema utama dalam logika matematika antara lain adalah kekuatan ekspresif dari logika formal dan kekuatan deduktif dari sistem pembuktian formal. Logika matematika sering dibagi ke dalam cabang-cabang dari teori himpunan, teori model, teori rekursi, teori pembuktian, serta matematika konstruktif. Bidang-bidang ini memiliki hasil dasar logika yang serupa.

Jelas bahwa tanpa logika, kita sering melakukan kesalahan dalam penarikan kesimpulan.

Dalam kehidupan sehari-hari, sering kali kita di hadapkan pada suatu keadaan yang mengharuskan kita untuk membuat suatu keputusan. Agar keputusan kita itu baik dan benar, maka terlebih dahulu kita harus dapat menarik kesimpulan-kesimpulan dari keadaan yang kita hadapi itu, dan untuk dapat menarik kesimpulan yang tepat diperlukan kemampuan menalar yang baik.

Kemampuan menalar adalah kemampuan untuk menarik kesimpulan yang tepat dari bukti-bukti yang ada dan menurut aturan-aturan tertentu. Lalu apa kaitannya dengan logika?

Logika adalah ilmu untuk berpikir dan menalar dengan benar. Secara bahasa, logika berasal dari kata “logos” (bahasa Yunani), yang artinyakata, ucapan, pikiran. Kemudian pengertian itu berkembang menjadiilmu pengetahuan. Logika dalam pengertian ini adalah berkaitan dengan argumen-argumen, yang mempelajari metode-metode dan prinsip-prinsip untuk ,menunjukkan keabsahan (sah atau tidaknya) suatu argumen, khususnya yang dikembangkan melalui penggunaan metode-metode matematika dan simbol-simbol matematika dengan tujuan untuk menghindari makna ganda dari bahasa yang biasa kita gunakan sehari-hari.

Pengertian Pernyataan dan Bukan Pernyataan

Sebelum membahas pernyataan, terlebih dahulu kita bahas pengertian kalimat. Kalimat adalah rangkaian kata yang disusun menurut aturan bahasa yang mengandung arti.

Pernyataan adalah kalimat yang mempunyai nilai benar atau salah, tetapi tidak sekaligus benar dan salah. (pernyataan disebut juga preposisi, kalimat deklaratif). Benar diartikan ada kesesuaian antara apa yang dinyatakan dengan keadaan yang sebenarnya.

Perhatikan beberapa contoh berikut!

1. Al-Quran adalah sumber hukum pertama umat Islam

2. 4 + 3 = 8

3. Frodo mencintai 1

4. Asep adalah bilangan ganjil

Contoh nomor 1 bernilai benar, sedangkan contoh nomor 2 bernilai salah, dan keduanya adalah pernyataan. Sementara contoh nomor 3 dan 4 adalah kalimat yang tidak mempunyai arti.

Sekarang perhatikan contoh di bawah ini!

1. Rapikan tempat tidurmu!

2. Apakah hari ini akan hujan?

3. Indah benar lukisan ini!

4. Berapa orang yang datang?

Kalimat di atas tidak mempunyai nilai benar atau salah, sehingga bukan pernyataan.

Catatan:

Suatu pernyataan biasa kita simbolkan dengan huruf kecil p,q,r,s, dan sebagainya.

Kalimat Terbuka

Perhatikan contoh berikut ini!

1. yang duduk di bawah pohon itu cantik rupanya

2. seseorang memakai kacamata

3. 2x + 8y > 0

4. x + 2 = 8

Keempat contoh di atas belum tentu bernilai benar atau salah. Kalimat yang demikian itu dinamakan kalimat terbuka. Kalimat terbuka biasanya ditandai dengan adanya variabel (peubah). Jika variabelnya diganti dengan konstanta dalam semesta yang sesuai maka kalimat itu akan menjadi sebuah pernyataan.

Variabel (Peubah) adalah lambang yang menunjukkan anggota yang belum tentu dalam semesta pembicaraan, sedangkan konstanta adalah lambang yang menunjukkan anggota tertentu dalam semesta pembicaraan.

Pengganti variabel yang menyebabkan kalimat terbuka menjadi pernyataan yang bernilai benar, disebut selesaian atau penyelesaian.

Catatan:

“” artinya ekivalen

Contoh:

Buatlah pernyataan yang setara dengan pernyataan: “jika ia benar-benar mencuri, maka pada saat pencurian harus berada di tempat ini.”

Jawab:

Implikasi setara dengan kontraposisi. Maka pernyataan itu dapat diubah menjadi, “jika pada saat pencurian tidak berada di tempat itu, maka ia tidak mencuri.”

Penarikan Kesimpulan (Inferensi)

1) Pengertian Argumen

Argumen adalah serangkaian pernyataan-pernyataan yang mempunyai ungkapan-ungkapan pernyataan “penarikan kesimpulan”

Argumen terdiri dari dua kelompok pernyatan, yaitu premis(pernyataan-pernyataan sebelum kesimpulan) dan sebuah konklusi(kesimpulan).

2) Modus ponens, modus tollens, dan sillogisma

Sekarang kita akan membahas 3 bentuk argumentasi yang sah, yaitu modus ponens, modus tollens, dan sillogisma.

1. Modus ponens

Modus ponens disebut juga kaidah pengasingan.

Bentuknya sebagai berikut:

p --> q (premis 1) berupa implikasi

p          (premis 2) berupa anteseden

——–-

        q  (konklusi)

2. Modus tollens

Modus tollens disebut juga kaidah penolakan.

Bentuknya sebagai berikut:

p --> q (premis 1) berupa implikasi

q         (premis 2) berupa negasi dari konsekuen

———-

p         (konklusi)

3. Silogisma

Bentuknya sebagai berikut:

p --> q (premis 1) berupa implikasi

q --> r  (premis 2) berupa implikasi

———-

p --> r  (konklus)

Contoh Soal :

A.Buktikan bahwa proposisi berikut “TAUTOLOGI” !!

{(pvq)⇒r } ⇔{ (p⇒r)∧(q⇒r) }
{p⇒(q∧r) }⇔{(p⇒q)∧(p⇒r) }
{(p∧q)⇒r}⇔{(p∧ ∼r)⇒∼q)
{(p∧q)⇒r}⇔{(p⇒r) v (q⇒r)}
(p⇒r)⇒{(p∧q)⇒r}∧{p⇒(q∧r) }⇒(p⇒q)

B.Tentukan Konvers, Invers, dan Kontraposisi dari Proposisi berikut,Kemudian tentukan kebenarannya!

Jika x=5 , Maka x^2=25
Jika x^2 bilangan asli, Maka x bilangan asli
Jika ∆ABC sama kaki, Maka ∠A= ∠C

Jawaban

A.Pembuktian “TAUTOLOGI”

{(pvq)⇒r } ⇔{ (p⇒r)∧(q⇒r) }
Jawab :
p q r { ( p v q ) ⇒ r } ⇔ { ( p ⇒r ) ∧ (q ⇒ r ) }
B B B B B B B B B
B B S B S B S S S
B S B B B B B B B
B S S B S B S S B
S B B B B B B B B
S B S B S B B S S
S S B S B B B B B
S S S S B B B B B

Terbukti bahwa proposisi tsb adalah TAUTOLOGI

{p⇒(q∧r) }⇔{(p⇒q)∧(p⇒r) }
Jawab :
p q r { p ⇒ (q ∧ r) } ⇔ { (p ⇒ q) ∧ ( p ⇒r ) }
B B B B B B B B B
B B S S S B B S S
B S B S S B S S B
B S S S S B S S S
S B B B B B B B B
S B S B S B B B B
S S B B S B B B B
S S S B S B B B B

Terbukti bahwa proposisi tsb adalah TAUTOLOGI

{(p∧q)⇒r}⇔{(p∧ ∼r)⇒∼q)}
Jawab :
p q r ∼q ∼r { (p ∧ q ) ⇒ r } ⇔ { (p ∧ ∼r) ⇒∼q )}
B B B S S B B B S B
B B S S B B S B B S
B S B B S S B B S B
B S S B B S B B B B
S B B S S S B B S B
S B S S B S B B S B
S S B B S S B B S B
S S S B B S B B S B

Terbukti bahwa proposisi tsb adalah TAUTOLOGI

{(p∧q)⇒r}⇔{(p⇒r) v (q⇒r) }
Jawab :
p q r {(p ∧ q ) ⇒r } ⇔ {(p ⇒ r) v (q ⇒ r )}
B B B B B B B B B
B B S B S B S S S
B S B S B B B B B
B S S S B B S B B
S B B S B B B B B
S B S S B B B B S
S S B S B B B B B
S S S S B B B B B

Terbukti bahwa proposisi tsb adalah TAUTOLOGI

(p⇒r)⇒{(p∧q)⇒r}∧{p⇒(q∧r) }⇒(p⇒q)
Jawab :
p q r (p⇒r) ⇒ { (p∧q) ⇒ r } ∧ { p ⇒ (q∧r)} ⇒ (p ⇒ q)
B B B B B B B B B B B B
B B S S B B S B S S B B
B S B B B S B B B S B S
B S S S B S B B B S B S
S B B B B S B B B B B B
S B S B B S B B B S B B
S S B B B S B B B S B B
S S S B B S B B B S B B

Terbukti bahwa proposisi tsb adalah TAUTOLOGI

Jawaban

B.Konvers, Invers, Kontraposisi dan Tabel Kebenaran

Jika x=5 , Maka x^2=25
Jawab :

p : x =5
q : x^2=25

konvers (q ⇒p)
Jika x^2=25 , maka x=5

Invers (∼p⇒∼q)
Jika x≠5 , maka x^2≠25

Kontraposisi (∼q⇒∼p)
Jika x^2≠25 , maka x≠5

Negasi (p∧∼q)
x=5 , akan tetapi x^2≠25

Tabel Kebenaran
p q ∼p ∼q Implikasi
( p⇒q) Konvers
(q ⇒p) Invers
(∼p⇒∼q) Kontraposisi
(∼q⇒∼p) Negasi
(p∧∼q)
B B S S B B B B S
B S S B S B B S B
S B B S B S S B S
S S B B B B B B s

Jika x^2 bilangan asli, Maka x bilangan asli
Jawab :

p : x^2 bilangan asli
q : x bilangan asli

konvers (q ⇒p)
Jika x bilangan asli, maka x^2 bilangan asli

Invers (∼p⇒∼q)
Jika x^2 bukan bilangan asli , maka x bukan bilangan asli

Kontraposisi (∼q⇒∼p)
Jika x bukan bilangan asli, maka x^2 bukan bilangan asli

Negasi (p∧∼q)
x^2 bilangan asli, akan tetapi x bukan bilangan asli

Tabel Kebenaran
p q ∼p ∼q Implikasi
( p⇒q) Konvers
(q ⇒p) Invers
(∼p⇒∼q) Kontraposisi
(∼q⇒∼p) Negasi
(p∧∼q)
B B S S B B B B S
B S S B S B B S B
S B B S B S S B S
S S B B B B B B s

Jika ∆ ABC sama kaki, Maka ∠A= ∠C
Jawab :

p : ∆ ABC sama kaki
q : ∠A= ∠C

konvers (q ⇒p)
Jika ∠A= ∠C, maka ∆ ABC sama kaki

Invers (∼p⇒∼q)
Jika ∆ ABC bukan sama kaki , maka ∠A ≠∠C

Kontraposisi (∼q⇒∼p)
Jika ∠A ≠∠C, maka ∆ ABC bukan sama kaki

Negasi (p∧∼q)
∆ ABC sama kaki, akan tetapi ∠A ≠∠C

Tabel Kebenaran
p q ∼p ∼q Implikasi
( p⇒q) Konvers
(q ⇒p) Invers
(∼p⇒∼q) Kontraposisi
(∼q⇒∼p) Negasi
(p∧∼q)
B B S S B B B B S
B S S B S B B S B
S B B S B S S B S
S S B B B B B B s

RETNO INDRIANI

A11.2011.06415

MATEMATIKA DISKRIT (A11.4304)