A.

Aljabar Boolean
1. Sejarah Aljabar Boolean
Konsep dasar aljabar Boolean atau aljabar Boolean pertama kali diperkenalkan pada
tahun 1854 oleh seorang ahli matematika asal Inggris bernama George Boole. Boole
menyadari bahwa logika himpunan dan logika proposisional memiliki sifat yang serupa dan
pertama kali mendefinisikan istilah tersebut sebagai bagian dari sistem logika. Dalam
bukunya “The Laws of Thought” Boole memaparkan aturan-aturan dasar logika yang
membentuk struktur matematika yang disebut dengan aljabar boolean. Akan tetapi, konsep
tersebut membutuhkan waktu yang cukup lama untuk disadari kegunaannya.
Pada tahun 1938, pakar komunikasi Claude Shannon menggunakan dan
menyempurnakan konsep aljabar Boolean. Teori ini memainkan peran yang sangat penting
tidak hanya dalam teori logika tetapi juga dalam bidang-bidang seperti teori probabilitas,
teori informasi, dan teori himpunan. Teori ini diterapkan dalam berbagai bidang, termasuk
desain sirkuit, sirkuit digital, dan desain sirkuit IC (rangkaian terpadu). Teori ini juga
digunakan dalam desain komputer elektronik yang kita gunakan saat ini.
2. Konsep Aljabar Boolean
Aljabar Boolean hanya memiliki dua keadaan/nilai yaitu 0 (False) dan 1 (True).
Aljabar boolean memiliki dua operasi biner yaitu OR/Penjumlahan(+) dan AND/Perkalian(.)
juga operasi uner ('). Operasi OR akan akan menghasilkan 0 jika kedua operannya 0,
sedangkan operasi AND akan menghasilkan 1 jika kedua operannya 1.Operasi uner(') akan
membalikkan nilai operan, yang awalnya bernilai 1 menjadi 0 begitu juga sebaliknya. Dalam
artikel “Definisi dan Aksioma Aljabar Boolean”, Aljabar Boolean adalah sistem aljabar yang
berisi set S dengan dua operasi biner yakni penjumlahan (+) dan perkalian (.) yang
didefinisikan pada set itu sehingga memenuhi ketentuan berikut:
 Tertutup terhadap operasi penjumlahan dan perkalian, ada unsur identitas
penjumlahan dan perkalian, memenuhi sifat komutatif penjumlahan dan perkalian,
memenuhi sifat distributif perkalian terhadap penjumlahan, memenuhi sifat distributif
penjumlahan terhadap perkalian, untuk setiap unsur S mempunyai komplemen
terhadap operasi penjumlahan dan perkalian, dan memenuhi sifat asosiatif
penjumlahan dan perkalian.
 Setiap unsur S adalah ’idempotent’, yaitu jika a S, maka a.a = a dan a + a = a. Secara
definisi aljabar boolean yaitu,
Defenisi, Misalkan B adalah himpunan yang didefinisikan pada dua operator biner, +
dan ., dan sebuah operator uner,’. Misalkan 0 dan 1 adalah dua elemen yang berbeda dari
B. Maka, tupel

<B, +, ., ’, 0,1>

Disebut aljabar Boolean jika untuk setiap a,b,c ∈ B berlaku aksioma berikut:

a. Identitas
( i ) a+0=a
( ii ) a .1=a

b. Komutatif
( i ) a+b=b+ a
( ii ) a . b=b . a

c. Distributif
( i ) a .(b+ c)=(a . b)+(a . c) ( ii ) a+ ( b . c ) =( a+b ) .(a+ c)
d. Komplemen
Untuk setiap a ∈ B terdapat elemen unik a’ ∈ B sehingga
( i ) a+a '=1 ( ii ) a . a' =0

Dari definisi diatas, Elemen-elemen himpunan B tidak ditentukan nilainya.

Maka dari itu akan ada banyak sekali aljabar boolean. Dari definisi tersebut, bisa
dikatakan bahwa Aljabar himpunan dan Aljabar Proposisi juga termasuk ke dalam
aljabar boolean karena memenuhi keempat aksioma diatas. Dengan kata lain, aljabar
proposisi dan aljabar himpunan adalah himpunan bagian atau subset dari aljabar
boolean
3. Aljabar Boolean Dua-Nilai
Aljabar Boolean yang terkenal dan memiliki terapan yang luas adalah aljabar
Boolean dua-nilai (two-valued Boolean algebra). Aljabar Boolean dua-nilai
didefinisikan pada sebuah himpunan B dengan dua buah elemen 0 dan 1 (sering
dinamakan bit – singkatan dari binary digit), yaitu B = {0, 1}, operator biner, + dan .
operator uner, ‘. Kaidah untuk operator biner dan operator uner ditunjukkan pada
Tabel di bawah ini.
Tabel 3.1 Kaidah Operasi
A b a.b
 0 0 0
0 1 0
1 0 0
1 1 1

Tabel 3.2 Kaidah Operasi +

A b a+b
0 0 0
0 1 0
1 0 0
1 1 1

Tabel 3.3 Kaidah Operasi ‘

a a’
0 1
1 0

Dari penjelasan diatas, bisa dikatakan bahwa aljabar boolean 2 nilai telah memenuhi
keempat aksioma aljabar boolean. Maka dari itu, aljabar boolean 2 nilai juga
memenuhi hukum hukum aljabar boolean.

4. Prinsip Dualitas
Di dalam ajabar Boolean banyak ditemukan kesamaan (quality) yang dapat diperoleh dari
kesamaan lainnya, misalnya pada dua aksioma distributif yang sudah disebutkan dalam
defenisi:

( i ) a ( b+c )=ab+ac

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

Aksioma yang kedua diperoleh dari aksioma pertama dengan cara mengganti dengan + dan
mengganti + dengan (.). Prinsip ini dikenal dengan prinsip dualitas, prinsip yang juga kita
temukan di dalam teori himpunan maupun logika. Defenisi prinsip dualitas di dalam aljabar
Boolean adalah sebagai berikut:
 Defenisi 7.3. Misalkan S adalah himpunan (identity) di dalam aljabar Boolean yang melibatkan
operator +, . , dan komplemen, maka jika pernyataan S* diperoleh dari S dengan cara
mengganti
. dengan +
+ dengan .
0 dengan 1
1 dengan 0
Dan membiarkan operator komplemen tetap apa adanya, maka kesamaan S* juga benar. S*
disebut dual dari S.
5. Hukum – Hukum Aljabar Boolean
Ada banyak hukum di dalam aljabar boolean 2 nilai telah memenuhi keempat
aksioma aljabar boolean. Maka dari itu, aljabar. Beberapa literatur bervariasi dalam
mengungkapkan jumlah hukum pada aljabar Boolean, tetapi hukum – hukum yang
paling penting ditampilkan pada tabel berikut.

Tabel 5.1 hukum – hukum aljabar Boolean

1. Hukum identitas: 2. Hukum idempoten:
(i) a + 0 = a (i) a + a = a
(ii) a  1 = a (ii) a  a = a

3. Hukum komplemen: 4. Hukum dominansi:

(i) a + a’ = 1 (i) a  0 = 0
(ii) aa’ = 0 (ii) a + 1 = 1
5. Hukum involusi: 6. Hukum penyerapan:
(i) (a’)’ = a (i) a + ab = a
(ii) a(a + b) = a
7. Hukum komutatif: 8. Hukum asosiatif:
(i) a + b = b + a (i) a + (b + c) = (a + b) + c
(ii) ab = ba (ii) a (b c) = (a b) c

9. Hukum distributif: 10. Hukum De Morgan:

(i) a + (b c) = (a + b) (a + c) (i) (a + b)’ = a’b’
(ii) a (b + c) = a b + a c (ii) (ab)’ = a’ + b’

11. Hukum 0/1

(i) 0’ = 1
(ii) 1’ = 0
 Perhatikanlah bahwa hukum yang ke-(ii) dari setiap hukum di atas merupakan dual
dari hukum yang ke-(i). Sebagai contoh,

Hukum komutatif : a+b=b+a

dualnya : a.b=b.a

Hukum asosiatif : a + (b + c) = (a + b) + c

dualnya : a . (b . c) = (a . b) . c

Hukum distributif : a + (b . c) = (a + b) . (a + c)
dualnya : a . (b + c) = (a . b) + (a . c)
6. Fungsi Boolean
Defenisi, Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan dari B" ke B melalui
ekspresi Boolean, kita menuliskannya sebagai
n
f :B →B

yang dalam hal ini B adalah himpunan yang beranggotakan pasangan terurut ganda-n
(ordered n-tuple) di dalam daerah asal B.

Misalkan ekspresi Boolean dengan n peubah adalah E( x 1 , x 2 ,… , x n ). Menurut Definisi ini,

setiap pemberian nilai-nilai kepada peubah x 1 , x 2 ,… , x n merupakan suatu pasangan terurut
ganda-n di dalam daerah asal B" dan nilai ekspresi tersebut adalah bayangannya di dalam
daerah hasil B [LIU85]. Dengan kata lain, setiap ekspresi Boolean tidak lain merupakan
fungsi Boolean. 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}. Contoh
pasangan terurut ganda-3 misalnya (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 .

Contoh-contoh fungsi Boolean:

1. f(x) = x
2. f(x, y) = x’y + xy’+ y'
3. f(x, y)=x’y'
4. f(x,y)=(x+y)'
5. f(x, y, z)=xyz’
Setiap peubah di dalam fungsi Boolean, termasuk dalam bentuk komplemennya, disebut
literal. Fungsi h(x, y, z) = xyz' pada contoh di atas terdiri dari 3 buah literal, yaitu x, y, dan
z'. Fungsi tersebut berharga 1 jika x = 1, y = 1, z = 0 sebab

h(1, 1, 0) = 1 . 1 . 0’ = (1 . 1) . 1 = 1 . 1 = 1

dan berharga 0 untuk harga x, y, dan z lainnya.

Selain secara aljabar, fungsi Boolean juga dapat dinyatakan dengan tabel kebenaran dan
dengan rangkaian logika. Tabel kebenaran berisi nilai-nilai fungsi untuk semua kombinasi
nilai-nilai peubahnya.

Jika fungsi Boolean dinyatakan dengan tabel kebenaran, maka untuk fungsi Boolean dengan
buah peubah, kombinasi dari nilai peubah-peubahnya adalah sebanyak 2n. Ini berarti
terdapat 2n baris yang berbeda di dalam tabel kebenaran tersebut. Misalkan n = 3 maka akan
terdapat 23 = 8 baris tabel. Cara yang praktis membuat semua kombinasi tersebut adalah
sebagai berikut:

1. Untuk peubah pertama, isi 4 baris pertama pada kolom pertama dengan sebuah 0 dan
4 baris selanjutnya dengan sebuah 1 berturut-turut.
2. Untuk peubah kedua, isi 2 baris pertama pada kolom kedua dengan 0 dan 2 baris
berikutnya dengan 1, 2 baris berikutnya dengan 0 lagi, dan 2 baris terakhir dengan 1.
3. Untuk peubah ketiga, isi kolom ketiga secara berselang-seling dengan 0 dan 1 mulai
baris pertama sampai baris terakhir.

Contoh Soal & Pembahasan Ekspresi Boolean

1. Buktikan bahwa untuk sembarang elemen a dan b dari aljabar Boolean maka kesamaaan
berikut:
a+ a’b = a + b dan a(a’ + b) = ab adalah benar.
Penyelesaian:
(i) a + a’b = (a + ab) + a’b (Hukum Penyerapan)

= a + (ab + a’b) (Hukum Asosiatif)

= a + (a + a’)b (Hukum Distributif)

=a+1.b (Hukum Komplemen)

 =a+b (Hukum Identitas)

(ii) a (a’ + b) = a a’ + ab (Hukum Distributif)

= 0 + ab (Hukum Komplemen)

= ab (Hukum Identitas)

2. Buktikan dengan menggunakan hukum-hukum aljabar boolean dan tabel kebenaran,

bahwa :
A’(BC + AB + BA’) = A’B
Penyelesaian:
Pembuktian dengan hukum-hukum aljabar boolean,

A’(BC + AB + BA’) = A’(B(C+A+A’)) -> Hk. Distibutif

= A’(B(C+1)) -> Hk. Komplemen
= A’(B(1)) -> Hk. Dominasi
= A’(B) -> Hk. Identitas
= A’B (terbukti)
Pembuktian dengan tabel kebenaran,

A B C B A A BA BC+AB+BA A’(BC+AB+BA’ A’
C B ’ ’ ’ ) B
1 1 1 1 1 0 0 1 0 0
1 1 0 0 1 0 0 1 0 0
1 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0
0 1 1 1 0 1 1 1 1 1
0 0 1 0 0 1 0 0 0 0
0 1 0 0 0 1 1 1 1 1
0 0 0 0 0 1 0 0 0 0
 Terbukti !

3. Sederhanakanlah fungsi di bawah ini :

F(X,Y) = X + X’Y

Penyelesaian:

F(X,Y) = X + X’Y
= (X+X’)(X+Y) -> Hk. Distributif

= 1 . (X+Y) -> Hk. Komplemen

=X+Y -> HK. Identitas

4. Misalkan B = {1, 2, 5, 7, 10, 14, 35, 70} adalah pembagi dari 70. Tunjukkan cara
membentuk B menjadi sebuah aljabar Boolean.
Penyelesaian:
Elemen-elemen himpunan B sudah didefinisikan. Sekarang kita tentukan kaidah operasi
untuk operator,, dan. Misalkan kita definisikan
a + b = KPK (a, b) = kelipatan persekutuan terkecil

a . b = PBB (a, b) = pembagi bersama terbesar

a' = 70/a

Maka sekarang kita tunjukkan apakah B bersama-sama dengan kedua operator biner dan
operator uner memenuhi ekempat aksioma yang disebutkan di dalam Definisi.

a. Identitas: 1 adalah elemen identitas untuk operasi penjumlahan (1 sebagai elemen zero)
dan 70 adalah elemen identitas untuk operasi perkalian (70 sebagai elemen unit), karena

(i) a + 1 = KPK(a, 1) = a
(ii) a * 70 = PBB(a, 70) = a
b. Komutatif: jelas berlaku karena
(i) a+b=b+a = KPK(a, b)
(ii) a.b=b.a = PBB(a, b)
c. Distributif: jelas berlaku karena (ditunjukkan dengan contoh)
(i) 10. (5 + 7) = PBB(10, KPK(5, 7)) = PBB(10, 35) = 5

(10.5)+(10-7)KPK(PBB(10, 5), PBB(10, 7)) = KPK(5, 1) = 5

 (ii) 10 + (5 . 7) = KPK(10, PBB(5, 7)) = KPK(10, 1) = 10

(10 + 5)(10 + 7) = PBB(KPK(10, 5), KPK(10, 7)) = PBB(10, 70) = 10

d. Komplemen: jelas berlaku karena

(i) a + a' = KPK(a, 70 / a) = 70
(ii) a . a' = PBB(a, 70 / a) = 1
Oleh karena semua aksioma di dalam Definisi dipenuhi, maka B (1, 2, 5, 7, 10, 14, 35, 70)
yang didefinisikan pada operator biner + dan . dan operator komplemen adalah sebuah aljabar
Boolean. Dengan kata lain, <B, +, . , ‘, 1, 70> adalah sebuah aljabar Boolean.

5. Tentukan dual dari

(i) a + 0 = a
(ii) (a1)(0+a') = 0
(iii) a(a ^ 6 + b) = ab
Penyelesaian:

(i) a * 1 = a
(ii) (a + 0) + (1 * a') = 1
(iii) a + a'b = a + b

6. Buktikan bahwa untuk sembarang elemen a dan b dari aljabar Boolean maka kesamaaan
berikut

a+a^ * b = a + b dan a(a+b) = ab adalah benar.

Penyelesaian:

(i) a + a’b = (a + ab) + a'b (Hukum Penyerapan)

= a + (ab + a' b) (Hukum Asosiatif)

=a+(a+a')b (Hukum Distributif)

= a + 1.b (Hukum Komplemen)

=a+b (Hukum Identitas)

(ii) a (a' + b) = a.a' + ab (Hukum Distributif)

 = 0+ ab (Hukum Komplemen)

= ab (Hukum Identitas)

Kesamaan aljabar Boolean (termasuk hukum-hukum aljabar Boolean) juga dapat

diperlihatkan benar dengan menggunakan tabel kebenaran

7. Tuliskan dual dari setiap persamaan boolean berikut

(a*1)*(0+a')=0

Penyelesaian:

Untuk mencari dual dari persamaan di atas maka:

 Pada (a.1), ubah menjadi + dan 1 menjadi 0

 Ubah pada (a*1)*(0+a') menjadi +
 Pada (0+a'), ubah 0 menjadi 1 dan menjadi *
 Komplemen pada a' tidak berubah

Sehingga secara keseluruhan dualnya adalah:

(a*1)* (0+a')=0

(a+0) + (1*a')=1 dual

8. Perlihatkan bahwa a + a' b = a + b

Penyelesaian:
Tabel kebenaran untuk kesamaan a + a' b = a + b. Karena nilai- nilai pada kolom a + a' b
sama dengan nilai-nilai pada kolom a + b maka a + a' b = a + b

a b a’ a’b a+a’b a+b

0 0 1 0 0 0
0 1 1 1 1 1
1 0 0 0 1 1
1 1 0 0 1 1
9. Dengan menggunakan hukum-hukum aljabar Boolean, tentukan bentuk komplemen dari
fungsi Boolean f(x,y,z) = x'y(x + z + yz’)
Penyelesaian:
f'(x,y,z) = (x’y (x + z + yz’))’
= (x’y)’+ (x + z + yz’)’ (Hukum De Morgan)
= (x + y’) + x’z'(yz')' (Hukum De Morgan)
= x + y’ + x’z’(y’ + z) (Hukum De Morgan)
= x + y’+ x’y’z’ + x’z’z (Hukum Distributif)
= x + y’+ x’yz’ + 0
= x + y’+ x’y’z

10. Nyatakan fungsi Boolean f(x,y,z) = x’(x + y’ + z’) hanya dengan menggunakan
operator + dan komplemen (‘) saja.
Penyelesaian:
f(x,y) = x’(x+y’+z’)
= x’x + x’y’ + x’z’
= 0 + x’y’ + x’z’
= x’y’ + x’z’
= (x+y)’ + (x+z)’

B. Logika Matematika
1. Pengertian Logika Matematika
Logika Matematika/Logika Simbol ialah Logika yang menggunakan bahasa
Matematika, yaitu dengan menggunakan lambang-lambang atau simbol- simbol.
Keuntungan/ kekuatan bahasa simbol adalah: ringkas, univalent/bermakna tunggal, dan
universal/dapat dipakai dimana-mana. Logika mempelajari cara penalaran manusia,
sedangkan penalaran seseorang diungkapkan dalam bahasa berupa kalimat-kalimat. Dengan
demikian logika mempelajari kalimat-kalimat yang mengungkapkan atau merumuskan
penalaran manusia.
2. Kalimat, Pernyataan, dan Tabel Kebenaran
Kalimat dibedakan menjadi 2 macam, yaitu : (1) kalimat deklaratif/pernyataan, dan
(2) kalimat non deklaratif.
a. Kalimat Deklaratif (pernyataan)

Kalimat deklaratif atau pernyataan adalah kalimat berarti yuang mempunyai nilai logika
BENAR atau SALAH, tetapi tidak kedua-duanya dalam saat bersamaan. Kalimat pernyataan
dikatakan bernilai logik BENAR apabila pernyataan itu berlaku secara umum dan atau sesuai
dengan keadaan sebenarnya (faktual).

Benar atau salahnya suatu pernyataan dapat ditunjukkan dengan bukti. Apabila untuk
menentukan benar atau salahnya suatu pernyataan harus mengadakan observasi
(penyelidikan) maka pernyataan yang demikian disebut faktual.

Contoh :

Jakarta adalah Ibukota Negara dan kota metropolitan. (benar secara faktual)

Daffa ingin naik kelas. (benar secara umum)

Nugraha sedang sakit panas. (benar secara faktual)

b. Kalimat non-Dekalratif (bukan pernyataan) Kalimat non-deklaratif adalah kalimat

berarti yang tidak atau belum mempunyai nilai logik. Biasanya berupa kalimat tanya,
kalimat perintah atau kalimat terbuka.

Contoh :

Kemana saja kamu selama ini ? (tidak mempunyai nilai logik, karena kalimat tanya)

Hapuslah air matamu ! (tidak mempunyai nilai logik, karena kalimat perintah) X 2 −25=0
(tidak mempunyai nilai logik, karena kalimat terbuka)

c. Kalimat Terbuka dan Tertutup

Kalimat terbuka adalah kalimat yang memuat variabel. Jika variabelnya diganti oleh suatu
konstanta, kalimat tersebut akan berubah menjadi suatu pernyataan. Konstanta yang
menggantikan variabel suatu kalimat terbuka menjadi pernyataan yang benar disebut
penyelesaian dari kalimat terbuka itu. Contoh :

8x – 70 = - 6. Jika x diganti dengan 2 maka menjadi pernyataan yang salah, tetapi jika x
diganti dengan 8 maka menjadi pernyataan yang benar. Pada kalimat di atas 8 disebut
penyelesaian. Sebuah kalimat matematika yang tidak memuat variabel dan dapat dinyatakan
benar/salah tetapi tidak keduaduanya disebut kalimat tertutup.

Contoh :

7 + 5 = 12 ( benar )

14 – 12 = 20 ( salah )
 d. Kalimat Majemuk
i) Konjungsi

Jika dua pernyataan digabungkan dengan kata “dan” maka pernyataan itu disebut konjungsi.
Penulisan kata gabung “dan “ pada konjungsi dilambangkan dengan tanda : “ “. Sedangkan
tabel kebenaran pernyataan-pernyataan konjungsi disampaikan dalam bentuk tabel sebagai
berikut :

P Q P Q P Q PQ
B B B 1 1 1
B S S atau 1 0 0
S B S 0 1 0
S S S 0 0 0
Pernyataan majemuk P  Q dikatakan benar jika kedua-duanya benar dalam hal lain
dikatakan salah.

ii) Disjungsi
Jika dua pernyataan digabungkan dengan kata “ atau “ maka pernyataan majemuk ini disebut
disjungsi.
Lambang disjungsi adalah “  “ dan tabel kebenarannya sebagai berikut.
P Q PQ P Q PQ
B B B 1 1 1
B S B atau 1 0 1
S B B 0 1 1
S S S 0 0 0
Pernyatan majemuk P  Q dikatakan salah jika kedua-duanya salah, dalam hal lain
dikatakan benar.
iii) Implikasi (kondisional)

Pernyataan majemuk yang berbentuk “ jika P maka Q “ disebut implikasi atau kondisional.
Lambang penulisan implikasi sebagai berikut :
“ P -> Q “

Pernyataan majemuk “ P -> Q “ akan dikatakan bernilai salah jika P benar dan Q salah,
dalam hal lain dikatakan benar.
Tabel kebenaran dari implikasi sebagai berikut :
 P Q P -> Q P Q P -> Q
B B B 1 1 1
B S S atau 1 0 0
S B B 0 1 1
S S B 0 1

iv) Bi-Implikasi
Pernyataan majemuk yang berbentuk “ P jika dan hanya jika Q “ disebut Bi-implikasi.
Penulisan Bi-implikasi menggunakan lambang “ P Q atau P <-> Q “. Lambang di atas
bermakna :
1. P jika dan hanya jika Q.

2. P ekuivalen Q.

3. P syarat yang perlu dan cukup untuk Q.

Jika P dan Q dua pernyataan yang tersusun sebagai “P <-> Q “ maka tabel kebenarannya
sebagai berikut :

P Q P <-> Q P Q P <-> Q
B B B 1 1 1
B S S atau 1 0 0
S B S 0 1 0
S S B 0 0 1
Pernyataan P Q akan dikatakan bernilai benar jika P dan Q jika P dan Q bernilai sama,
dalam hal lain dikatakan salah .

(v) Negasi
Negasi atau ingkaran adalah penolakan dari pernyataan yang ada. Jika sebuah pernyataan
bernilai salah maka negasinya bernilai benar dan jika pernyataan bernilai benar maka
negasinya bernilai salah. Penulisan lambang negasi P adalah “ ~ P “. Untuk menentukan
ingkaran atau negasi dari sebuah pernyataan maka penulisan ditambah kata “ tidak , tidak
benar bahwa, atau bukan“ di depan pernyataan. Tabel kebenaran dari negasi adalah sebagai
berikut :
 P ~P P ~P
B S 1 0
S B 0 1

Negasi dari pernyataan ekuivalen dengan disjungsi dari masing-masing konjungsinya dan
begitu sebaliknya. Bentuk kesetaraan di atas disebut juga dengan dalil De-Morgan, yaitu :
~(P Q)≡~P~Q
~(PQ)≡~P~Q

Selain dalil De-Morgan masih banyak kesetaraan yang lain, misalnya

~ ( P -> Q ) ≡ P  ~ Q

~ ( P <-> Q ) ≡ ( P  ~ Q )  ( Q  ~ P )

3. Hukum-hukum Logika Proposisi

Proposisi, dalam kerangka hubungan ekivalensi logika, memenuhi sifat-sifat yang dinyatakan
dalam sejumlah hukum logika Beberapa hukum tersebut mirip dengan hukum aljabar pada
sistem bilangan riil, misalnya a(b+c) = ab + bc, yaitu hukum distributif, sehingga kadang-
kadang hukum logika proposisi dinamakan juga hukum-hukum aljabar proposisi
 Tabel 3.1 Hukum-hukum logika atau hukum-hukum aljabar proposisi

Hukum-hukum logika di atas bermanfaat untuk membuktikan keekivalenan dua buah

proposisi. Selain menggunakan tabel kebenaran, keekivalenan dapat dibuktikan dengan
hukum-hukum logika, khususnya pada proposisi majemuk yang mempunyai banyak proposisi
atomik. Bila suatu proposisi majemuk mempunyai buah porposisi atomik, maka tabel
kebenarannya terdiri dari 2n baris. Untuk n yang besar jelas tidak praktis menggunakan tabel
kebenaran, misalnya untuk n = 10 terdapat 21 baris di dalam tabel kebenarannya

4. Negasi Pernyataan Kuantor

Dua buah pernyataan (proposisi) dikatakan ekivalen (berekivalensi logis) jika kedua
pernyataan itu memiliki nilai kebenaran yang sama. Perhatikan dua pernyataan berikut. 𝑝:
Guru pahlawan bangsa 𝑞: Tidak benar bahwa guru bukan pahlawan bangsa Kedua pernyataan
ini akan memiliki nilai kebenaran yang sama, tidak peduli bagaimana nlai kebenaran dari
pernyataan semula. Dengan demikian, 𝒑 ekivalen dengan 𝒒 dan dapat ditulis 𝒑 ≡ 𝒒.

Berdasarkan definisi di atas, sifat-sifat pernyataan-pernyataan yang ekivalen (berekivalensi

logis) adalah:

a. 𝑝 ≡ 𝑞
b. Jika 𝑝 ≡ 𝑞 maka 𝑞 ≡ 𝑝

c. Jika 𝑝 ≡ 𝑞 dan 𝑞≡ 𝑟 maka 𝑝 ≡ 𝑟

Sifat pertama berarti bahwa setiap pernyataan selalu ekivalen (memiliki nilai kebenaran yang
sama) dengan pernyataan itu sendiri. Sifat kedua berarti bahwa jika suatu pernyataan
mempunyai nilai kebenaran yang sama dengan pernyataan lain, maka berlaku sebaliknya.
Sedangkan sifat ketiga berarti bahwa jika pernyataan pertama mempunyai nilai kebenaran
yang sama dengan pernyataan kedua dan pernyataan kedua mempunyai nilai kebenaran yang
sama dengan pernyataan ketiga maka nilai kebenaran pernyataan pertama dan ketiga akan
sama.

5. Tautologi dan Kontradiksi

Tautologi
Pernyataan majemuk yang selalu bernilai benar untuk setiap substitusi pernyataan
tunggalnya dinamakan tautologi. Dengan kata lain, tautologi merupakan pernyataan yang
selalu bernilai benar dalam kondisi apapun. Tautologi digunakan sebagai dasar dalam
pengambilan keputusan atau pembuktian matematis.
Pernyataan majemuk yang selalu bernilai B untuk setiap nilai kebenaran dari pernyataan-
pernyataan tunggalnya seperti itu disebut tautologi.

Kontradiksi
Jika tautologi adalah pernyataan yang selalu bernilai benar, maka sebaliknya kontradiksi
adalah pernyataan yang selalu bernilai salah untuk setiap substitusi nilai kebenaran
pernyataan tunggalnya.
Contoh Soal & Pembahasan Logika Matematika

1. Wawan rajin belajar maka naik kelas Wawan

dapat hadiah atau tidak naik kelas
Wawan rajin belajar
Buatlah kesimpulan yang benar!
Penyelesaian:
Misalkan
𝑝: Wawan rajin belajar.
𝑞: Wawan naik kelas.
𝑟: Wawan dapat hadiah.
Jadi diperoleh
P1: 𝑝 ⟹ 𝑞
P2: 𝑟 ∨ ~𝑞 ≅ (~𝑟 ⟹ ~𝑞) ≅ 𝑞 ⟹ 𝑟
P3: 𝑝
Perhatikan bahwa 𝑝 ⟹ 𝑞 dan dilain pihak, 𝑟 ∨ ~𝑞 ≅ (~𝑟 ⟹ ~𝑞) ≅ 𝑞 ⟹ 𝑟 Jadi diperoleh 𝑝
⟹ 𝑞 dan 𝑞 ⟹ 𝑟, dengan demikian berdasarkan silogisme haruslah 𝑝 ⟹ 𝑟 jadi kesimpulan
jawabannya adalah wawan dapat hadiah.

2. Diketahui premis-premis sebagai berikut :

Premis I : “Jika Anto lulus ujian maka saya diajak kebandung.”
Premis II :” Saya tidak diajak kebandung.”
Kesimpulan yang sah dari premis-premis tersebut adalah…..
Penyelesaian:
𝑝: Anto lulus ujian.
𝑞: Saya diajak kebandung.
Jadi diperoleh
P1: 𝑝 ⟹ 𝑞
P2: ~𝑞
Dengan demikian, berdasarkan Modus Tollens, kesimpulannya haruslah ~𝑝 yaitu Anto
tidak lulus ujian.
3. Jika p, q, dan r adalah proposisi. Bentuklah tabel kebenaran dari ekspresi logika
 (p ∧ q) ⋁ (- q ∧ r) .
Penyelesaian:
Ada 3 buah proposisi atomik di dalam ekspresi logika dan setiap proposisi hanya
mempunyai 2 kemungkinan nilai, sehingga jumlah kombinasi dari semua proposisi tersebut
adalah 2 × 2 × 2 = 8 buah. Tabel kebenaran dari proposisi ditunjukkan pada tabel dibawah
ini
p q r p∧ -q -q∧r (p ∧ q) ⋁ (- q ∧ r)
q
T T T T F F T
T T F T F F T
T F T F T T T
T F F F T F F
F T T F F F F
F T F F F F F
F F T F T T T
F F F F T F F

4. Tunjukkan bahwa p ∽( p ⋁ q) dan p ⋁ ∽ q keduanya ekivalen secara logika.

Penyelesaian:
P ⋁ ∽ (p ⋁ q ¿ ↔ p ⋁ (∽ p ⋀ ∽q) (Hukum De Mogran)
↔( p ⋁ ∽ p) ⋀ ( p ⋁ ∽ q) (Hukum distributif)
↔T ⋀ ( p ⋁∽q) (Hukum negasi)
↔ p ⋁∽q (Hukum identitas)

5. Buktikan hukum penyerapan: p ∧ (p ∨ q) ↔ p

Penyelesaian:
p ∧ (p ∨ q) ↔ (p ∨ F ¿∧ (p ∨ q) (Hukum Identitas)
↔p ∨ (F ∧ q) (Hukum distributif)
↔p ∨ F (Hukum Null)
↔p (Hukum Identitas)
6.Misalkan
x: Anda berusia 17 tahun.
y: Anda dapat memperoleh SIM
Nyatakan preposisi berikut ke dalam notasi implikasi:
 (a) Hanya jika anda berusia 17 tahun maka anda dapat memperoleh SIM.

(b) Syarat cukup agar anda dapat memperoleh SIM adalah anda berusia 17 tahun.
(c) Syarat perlu agar anda dapat memperoleh SIM adalah anda berusia 17 tahun.
Penyelesaian:
(a) Pernyataan yang diberikan ekivalen dengan "Anda dapat memperoleh SIM hanya jika
anda berusia 17 tahun". Ingat kembali bahwa p -> q bisa dibaca "p hanya jika q". Jadi,
pernyataan yang diberikan dilambangkan dengan y -> x.
(b) Pernyataan yang diberikan ekivalen dengan "Anda berusia 17 tahun adalah syarat
cukup untuk dapat memperoleh SIM". Ingat kembali bahwa p -> q bisa dibaca "p
syarat cukup untuk q". Jadi, pernyataan yang diberikan dilambangkan dengan x ->
zeta .
(c) Pernyataan yang diberikan ekivalen dengan "Anda berusia 17 tahun adalah syarat
perlu untuk dapat memperoleh SIM". Ingat kembali bahwa p -> q bisa dibaca "q
syarat perlu untuk q". Jadi, pernyataan yang diberikan dilambangkan dengan y -> x

7. Tunjukkan bahwa p → q ekivalen secara logika dengan ∽ p ∨q

Penyelesaian:
p q ∽p p→q ∽ p ∨q
T T F T T
T F F F F
F T T T T
F F T T T

Berdasarkan tabel kebenaran tersebut, memperlihatkan bahwa memang benar p → q

ekivalen secara logika dengan ∽ p ∨q Dengan kata lain, pernyataan "Jika p maka q"
ekivalen secara logika q".

8. Tentukan ingkaran (negasi) dari p → q

Penyelesaian:
Dari Contoh soal nomor 8 sudah ditunjukkan bahwa p → q ekivalen secara logika dengan
∽ p ∨q . Gunakan hukum DeMorgan untuk menentukan ingkaran dari p -> q
 ∽ ( p → q ) ↔ ( p ∨q ) ↔ ( p¿∧ q ) ↔ p ∧ q

9. Dua pedagang barang kelontong mengeluarkan moto jitu untuk menarik pembeli.
Pedagang pertama mengumbar moto "Barang bagus tidak murah" sedangkan pedagang
kedua mempunyai moto "Barang murah tidak bagus". Apakah kedua moto pedagang
tersebut menyatakan hal yang sama?

Penyelesaian:

Untuk memeriksa apakah kedua moto tersebut sama, kita perlu membandingkan tabel
kebenaran keduanya. Misalkan p menyatakan proposisi "Barang itu bagus" sedangkan q
menyatakan "Barang itu murah". Maka, moto pedagang pertama dapat ditulis sebagai
"Jika barang itu bagus maka barang itu tidak murah" atau p → q sedangkan moto kedua
dapat ditulis sebagai "Jika barang itu murah maka barang itu tidak bagus" atau q →~p.
Tabel kebenaran untuk proposisi p→~q dan proposisi q →~p ditunjukkan pada Tabel
kebenaran berikut. Dari tabel tersebut dapat dilihat ternyata nilai kebenaran proposisi p →
~q dan proposisi q →~p sama, dengan kata lain p→~q ↔ q →~p Jadi kita dapat
menyimpulkan bahwa kedua moto tersebut menyatakan hal yang sama.

p q ~p ~q p→~q q →~p
T T F F F F
T F F T T T
F T T F T T
F F T T T T

10. Sebagian besar orang percaya bahwa harimau Jawa sudah lama punah. Tetapi, pada suatu
hari Amir membuat pernyataan-pernyataan kontroversial sebagai berikut:
(a) Saya melihat harimau di hutan.
(b) Jika saya melihat harimau di hutan, maka saya juga melihat srigala..
Misalkan kita diberitahu bahwa Amir kadang-kadang suka berbohong dan kadang-kadang
jujur. Gunakan tabel kebenaran untuk memeriksa apakah Amir benar-benar melihat
harimau di hutan?
Penyelesaian:
Misalkan:
p: Amir melihat harimau di hutan
 q: Amir melihat srigala
Pernyataan untuk soal (a) adalah p sedangkan pernyataan untuk (b) adalah p → q. Tabel
kebenaran untuk p dan p → q. ditunjukkan pada Tabel kebenaran berikut ini:

p q p→q
T T T
T F F
F T T
F F T

Bila Amir dianggap berbohong, maka apa yang dikatakan Amir itu keduanya salah, atau
bila dia dianggap jujur maka apa yang dikatakan Amir itu keduanya benar. Tabel
kebenaran di atas menunjukkan bahwa mungkin bagi q dan p → q benar, tetapi tidak
mungkin keduanya salah. Ini berarti Amir mengatakan yang sejujurnya, dan kita
menyimpulkan bahwa Amir memang benar melihat harimau di hutan.

Anda juga dapat menjawab soal ini tanpa menggunakan tabel kebenaran. Tinjau dua
kasus. Kasus pertama, Amir berbohong, maka apa yang dikatakan Amir itu keduanya
salah. Ini berarti p salah, dengan demikian implikasi p → q pasti benar apa pun nilai
kebenaran pernyataan q. Ini jelas kontradiksi. Jadi, pastilah Amir benar (kasus kedua),
yang berarti Amir memang benar melihat harimau di hutan.
 Daftar Pustaka

Munir , Rinaldi.2014. Matematika Diskrit. Bandung: Informatika Bandung.

Krishna, A.N. (2017). Penerapan Aljabar Boolean pada Rangkaian Pensaklaran.