1.
Tentukan nilai kebenaran dari setiap pernyataan berikut : a. Jika 7 < dari 2 maka –2 < -7 b. 2 + 2 = 5 jika dan hanya jika 4 + 4 = 10 c. Jika 1 + 1 = 2 maka 2 + 3 = 6 d. 1 + 1 = 2 jika dan hanya jika 4 + 4 = 10 Jawaban : a. Benar karena kedua pernyataan adalah salah b. Benar karena kedua pernyataan adalah salah c. Salah karena pernyataan yang pertama benar tetapi yang ke dua salah d. Salah karena pernyataan-pernyataannya mempunyai nilai kebenaran yang berbeda
2.
Tunjukan bahwa proposisi ~ (p ∧ q) dan ~p v ~q adalah ekuivalen. Jawaban :
p T T F F 3.
q T F T F
p∧q T F F F
~(p∧q) F T T T
p T T F F
q T F T F
~p F F T T
~q F T F T
~pv ~q F T T T
Misalkan p adalah Sam orang kaya dan q adalah Sam bahagia. Tuliskan dalam pernyataan simbolik dari pernyataan di bawah ini : a. Sam orang miskin tetapi bahagia b. Sam tidak kaya maupun bahagia c. Sam orang kaya atau tidak bahagia d. Sam orang miskin atau juga dia orang kaya dan tidak bahagia Jawaban : a. ~ p ∧ q
b. c. d. 4.
~p ∧ ~q p ∨ ~q ~p ∨ (p ∧ ~q)
Tentukan banyak m proposisi P(p,q) yang tidak ekuivalen dalam variabel p dan q. Jawaban :
Tabel kebenaran dari P(p,q) akan memuat 22 = 4 baris. Dalam setiap muncul seperti pada gambar dibawah ini, sehingga m =24 = 16. p q P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 T T T T T T T T T T F F F F T F T T T T F F F F T T T T F T T T F F T T F F T T F F F F T F T F T F T F T F T F
5.
baris, T atau F dapat P13 F F T T
P14 F F T F
P15 F F F T
P16 F F F F
Definisikan sebuah tautologi dan sebauh kontradikasi dan berikan contoh. Penyelesaian: Sebuah preposisi P(p,q,…) adalah sebauh tautologi jika kolom terakhir pada table kebenarannya hanya memuat T, jika P adalah benar untuk setiap nilai kebenaran dari variable-variabelnya. P(p,q,…) adalah sebuah kontradiksi jika kolom terakhir pada table kebenarannya hanya memuat F, yaitu jika P adalah salah untuk setiap nilai kebenaran dari variable-variabelnya. Contoh, preposisi “p atau bukan p” , yaitu p v ~ p adalah sebuah tautologi dan preposisi “p dan bukan p” yaitu p ∧ ~ p adalah sebuah kontradiksi. Tabel di bawah ini membuktikannya:
Soal Logika Informatika Pra-S2 Kelas A/2006 - 1
6.
p ~p pv~p p ~p p∧~p T F T T F F F T T F T F Tentukan nilai kebenaran dari masing-masing pernyataan berikut : a. Salah bahwa 2 + 2 = 4 dan 1 + 1 = 5 b. Salah bahwa 2 + 2 = 4 atau london ada di Prancis Jawaban : a. Pernyataan 2 + 2 = 4 dan 1 + 1 = 5 adalah salah karena salah satu sub pernyataannya, 1 + 1 = 5 adalah salah. Dengan demikian negasinya, pernyataan yang diberikan adalah benar. b. Pernyataan bahwa 2 + 2 = 4 atau london ada di Prancis adalah benar karena salah satu sub pernyataanya 2 + 2 = 4 adalah benar. Dengan demikian negasinya, pernyataan yang diberikan adalah salah
7.
Buktikan bahwa operasi disjungsi dapat ditulis dalam hal operasi konjungsi dan negasi. Khusus nya p ∨ q = ~ (~ p ∨ ~ q ). Jawaban : P Q T T T T T F T F F T F T F F F F
P∧Q T T F F F F F F
R T F T F T F T F
(P∧Q) ∧ R T F F F F F F F
Q ∧R T F F F T F F F
P∧(Q∧R) T F F F F F F F
8.
Gunakan hukum-hukum aljabar proposisi untuk menunjukkan bahwa : (~p v q) v (~p ∧ q) ≡ ~p Jawab : (1) (~p v q) v (~p ∧ q) ≡ (~p ∧ ~q) v (~p ∧ q) (1) Hukum Demorgan (2) ≡ ~p ∧ (~q v q) (2) Hukum Distributif (3) ≡ ~p ∧ t (3) Hukum Komplemen (4) ≡ ~p (4) Hukum Identitas
9.
Tentukan tabel kebenaran dari ~(p v ~q). Jawaban :
p T T F F
q T F T F
~q F T F T
p v ~q T T F T
~(p v ~q) F T T F
10. Tentukan nilai kebenaran dari setiap pernyataan : a. 3 + 3 = 7 b. Salah bahwa 3 + 3 = 7. c. 3 + 3 <> 7 Jawab : a. Salah b. Benar
Soal Logika Informatika Pra-S2 Kelas A/2006 - 2
c.
Benar
11. Dengan menggunakan definisi alternatif untuk dualiti tuliskan dual daripada : p ∧ ¬q v q ∧ r ∧ ¬s ∧ (¬p v q) dan ekspresikan dual tersebut dalam BNDP jawab: p ∧ ¬q v q ∧ r ∧ ¬s ∧ (¬p v q) = (p ∧ ¬q) v ((q ∧ r) ∧ ¬s) ∧ (¬p v q) p
q
r
s
(p
∧
¬q)
v
((q
∧
r)
∧
¬s)
∧
(¬p
v
q)
T T T T T T T T F F F F F F F F
T T T T F F F F T T T T F F F F
T T F F T T F F T T F F T T F F
T F T F T F T F T F T F T F T F
T T T T T T T T F F F F F F F F
F F F F T T T T F F F F F F F F
F F F F T T T T F F F F T T T T
F F F F T T T T F T F F F F F F
T T T T F F F F T T T T F F F F
T F F F F F F F T T F F F F F F
T T F F T T F F T T F F T T F F
F F F F F F F F F T F F F F F F
F T F T F T F T F T F T F T F T
F F F F F F F F F T F F F F F F
F F F F F F F F T T T T T T T T
T T T T F F F F T T T T T T T T
T T T T F F F F T T T T F F F F
BNDP : (p ∧ ¬q ∧ r ∧ s) v (p ∧ ¬q ∧ r ∧ ¬s) v (p ∧ ¬q ∧ ¬r ∧ s) v (p ∧ ¬q ∧ ¬r ∧ ¬s) v (¬p ∧ q ∧ r ∧ ¬s) 12. Misalkan E adalah ekspresi Boolean yang diberikan pada peta Karnough berikut: zt
zt’
xy xy’ x’y’ x’y
√ √
√ √
z’t’
z’t
√
√
√
a) Tuliskan E dalam bentuk sum of product lengkapnya. b) Tuliskan bentuk minimal untuk E Penyelesaian: a) E = xyz’t’ + xyz’t + xy’zt + xy’zt’ + x’y’zt + x’y’zt’+ x’yz’t’ b) E = y’z + xyz’ + yz’t’
13. Tunjukkan bahwa p ∨ (p ∧ q) = p mengikuti hukum-hukum pada tabel kebenaran. Jwb. (1). (2). (3). (4).
Pernyataan p ∨ (p ∧q) = p ∨ (p ∧q) = p ∨ (p ∧q) = p ∨ (p ∧q) =
Alasan (p ∧ t) ∨ (p ∧ q) (1).Hukum identitas p ∧ ( t ∨ q) (2). Hukum Distributif p∧t (3). Hukum Identitas p (4). Hukum Identitas
14. Tunjukkan bagaiman setiap pasangan barisan bit-bit berikut diproses oleh sebuah gerbang OR :
Soal Logika Informatika Pra-S2 Kelas A/2006 - 3
(a) 110001 (b) 10001111 (c) 101100111000 101101 00111100 000111001101 Jawab : a. 111101 b. 10111111 c. 101111111101 15. Misalkan A = {1, 2, 3, 4, 5 } tentukan nilai kebenaran dari setiap pernyataan berikut : a) ( ∃x ∈ A ) ( x + 3 = 10 ) b) ( ∀x ∈ A ) ( x + 3 < 10 ) c) ( ∃x ∈ A ) ( x + 3 < 5 ) d) ( ∀x ∈ A ) ( x + 3 ≤ 7 ) Jawab : a) Salah. Tidak ada bilangan di A yang merupakan solusi untuk x + 3 = 10 b) Benar. Setiap bilangan di A memenuhi x + 3 < 10 c) Benar. Jika x0 = 1 maka x0 + 3 < 5, sehingga 1 adalah sebuah solusi.
d)
Salah. Jika x0 = 5 maka x0 + 3 ≤ 7. dengan kata lain, 5 bukan solusi
16. Definisikan kebenaran dari pernyataan majemuk p→q, yaitu, “Jika p maka q” Jawab : Pernyataan tersebut adalah benar kecuali dalam kasus p benar dan q salah. Seperti ditunjukkan pada tabel kebenaran berikut : P T T F F
q T F T F
p → q F F T F
17. Misalkan p menyatakan “ Dia Orang Kaya” dan misalkan q menyatakan “Dia bahagia”. Tuliskan setiap pernyataan berikut dalam bentuk simbolik menggunakan p dan q (Asumsikan “ Dia orang Miskin” Ekuivalen dengan ~ p) a) Jika dia orang kaya maka dia tidak bahagia b) Dia tidak kaya maupun bahagia c) Perlu menjadi miskin agar bahagia d) Menjadi miskin berarti tidak bahagia Jawab : a) p → ~ q b) ~ p ∧ ~ q c) q → ~ p d) ~ p ↔ ~ q 18. Tunjukkan bahwa argumen berikut adalah palsu : p -> q, ~p |-- ~ q Jawab : Buatlah tabel kebenaran untuk [p -> q ^ ~p] -> ~ q. Karena bukan sebuah tautologii maka argumennya adalah sebuah fallasy. Terdapat pada baris ke 3 dimana p -> q dan ~p benar tetapi ~q salah p T T F F
q T F T F
p -> q T F T T
~p F F T T
( p -> q ) ^ ~ p F F T T
~q F T F T
[p -> q ^ ~p] -> ~ q T T F T
19. Negasikan ∀x∃y ( p(x) v q(y) ) Jawab : ~ [∀ x ∃y ( p(x) v q(y) )] ≡ ∃ x ∀y ~ ( p(x) v q(y) ) ≡ ∃x ∀y (~ p (x) ∧ ~ q (x,y)). 20. Tuliskan negasi dari setiap pernyataan berikut sesederhana mungkin. a. dia tidak kaya maupun bahagia b. dia kehilangan pekerjaannya atau dia tidak pergi bekerja hari ini. Jawab : a. Gunakan ~(~p^ ~ q ) ≡ pvq untuk mendapatkan “ dia kaya atau bahagia”
Soal Logika Informatika Pra-S2 Kelas A/2006 - 4
b.
Gunakan ~(pv~q) ≡ ~p ^ q untuk mendapatkan “dia tidak kehilangan pekerjaannya dan dia berangkat bekerja hari ini”
21. Tentukan dan sederhanakan a. Kontraposisi dari kontraposisi p → q . b. kontraposisi dari konvers p → q . c. kontraposisi dari invers p → q . Jawab: a. Kontraposisi dari p → q adalah ~q → ~p.jadi. kontraposisi ~q →~p adalah ~ ~p→ ~ ~q yang merupakan proposisi conditional awal. b. Konver dari p→ q adalah q→ p. Sehingga kontraposisi dari q → p adalah ~p → ~ q yang merupakan invers dari p→ q. c. Invers dari p → q adalah ~p→ ~q. Sehingga kontraposisi dari ~ p → ~ q adalah ~ ~ q → ~ p ≡ q → p yang merupakan konvers dari p → q . Dengan kata lain , invers dan konvers saling kontraposisi satu sama lain, dan kondisional dan kontraposisi saling kontraposisi satu sama lain. 22. Tentukan expresi boolean Y=E(A,B,C) untuk sirkuit logika pada gambar berikut:
Jawab :Y=A.B.C + B.C + A. B
23. Buatlah Tabel Kebenaran dari ( p q ) (p Λ q) Jawab: P T T F F
q
P q
pΛq
( p q ) (p Λ q)
T F T F
T F T T
T F F F
T T F F
24. Buktikan dengan tabel kebenaran bahwa negasi dari conditional dan biconditional adalah sebagai berikut: a. ~ (p q) ≡ p Λ ~ q b. ~ (p ↔ q) ≡ p ↔ ~ q ≡ ~ p ↔ q Jawab: a.) P T T F F b.) P T T
q T F T F
Q T F
pq T F T T
p↔q T F
~ (p q) F T F F
~ (p ↔ q) F T
~q F T F T
~p F F
p Λ~ q F T F F
~p ↔ q F T
~q F T
p↔~q F T
Soal Logika Informatika Pra-S2 Kelas A/2006 - 5
F F
T F
F T
T F
T T
T F
F T
T F
Karena pq ≡ p Λ ~ q maka kita dapat menggunakan hukum DeMorgan untuk menunjukan pernyataan a. sebagai berikut : ~ (p q) ≡ ~ (~ p V q) ≡ ~ ~ p Λ ~ q ≡ p Λ ~ q
25. Gunakan Pemetaan Karnaugh untuk menentukan prime implicant dan bentuk minimal untuk setiap ekspresi boolean sum of product lengkap berikut: a. b. c.
E1 = xyz + xyz ' + x ' yz ' + x ' y ' z E2 = xyz + xyz ' + xy ' z + x ' yz + x ' y ' z E3 = xyz + xyz ' + x ' yz + x ' y ' z ' + x ' y ' z
Jawab: yz x
√
X’
yz’
y’z’ y’z
√ √
√
(a) E1 yz
yz’
x
√
√
X’
√
y’z’ y’z √ √
(b) E2
x X’
yz
yz’
√
√
y’z’ y’z
√
√
√
(c) E3 (a).
E1 Mempunyai tiga prime implicant (persegi utama maksimal), yang dilingkari; bagian ini adalah xy, xz’ dan x’ y’ z semuanya diperlukan untuk menutupi E1; Sehingga penjumlahan minimal untuk E1 adalah
E1 = xy + yz ' + x ' y ' z (b).
E2 Mempunyai dua prime implicant, yang dilingkari. Salah satunya adalah dua square adjacent yang mewakili xy, dan yang lainnya adalah square two-by-two (edge teridentifikasi yang merentang) yang mewakili z. Keduannya diperlukan untuk menutupi E2, jadi penjumlahan minimal untuk E2 adalah
E2 = xy + z
(c).
E3 Mempunyai 4 prime implicant, xy, yz’, x’z’, dan x’ y’. Tetapi, hanya satu dari dua bagian yang bergaris putus-putus, yaitu, salah satu dari yz’ atau x’ z’, yang diperlukan dalam minimal cover untuk E3, sehingga E3 mempunyai dua penjumlahan minimal:
E3 = xy + yz ' + x ' y ' = xy + x ' z ' + x ' y '
Soal Logika Informatika Pra-S2 Kelas A/2006 - 6
26. Tentukan nilai kebenaran dari setiap pernyataan berikut ini : a. Jika 2 + 2 = 4, maka 3 + 3 = 5 dan 1 + 1 = 2 b. Jika 2 + 2 = 4, maka 3 + 3 = 7 jika dan hanya jika 1 + 1 = 4 Jawab : a. Salah, karena pernyataan “jika” adalah benar, tetapi pernyataan “maka“ adalah salah.
b.
Benar, karena pernyataan “jika” adalah benar, dan pernyataan “maka“ juga benar.
27. Buktikanlah dengan menggunakan table kebenaran bahwa : a. ∼ ( p ∧ q ) ≡ ∼ p ∨ ∼ q b.
∼ ( p ∨ q) ≡ ∼ p ∧ ∼ q
Jawab : a. Bukti bahwa : ∼ ( p ∧ p
q
T T F F
T F T F
b. Bukti bahwa : p
q
T T F F
T F T F
q) ≡ ∼ p ∨ ∼ q p∧ q ∼ ( p ∧ q)
T F F F
F T T T
∼ ( p ∨ q) ≡ ∼ p ∧ ∼ q p∨ q ∼ ( p ∨ q) T T T F
F F F T
∼ p F F T T
∼ p F F T T
∼q F T F T
∼ p∨ ∼ q F T T T
∼q F T F T
∼ p∧ ∼ q F F F T
28. Misalkan
p adalah “hari ini dingin” dan q adalah “Hari ini hujan”. Berikan sebuah kalimat verbal sederhana yang menggambarkan pernyataan berikut : a. ~ p ^ ~ q, b. ~ ( ~ q). jawab: a. Hari ini tidak dingin dan hari ini tidak hujan,” atau, dengan kata lain, “Hari ini tidak dingin maupun hujan.” b. “Tidak benar bahwa hari ini tidak hujan”, atau, dengan kata lain, “Salah bahwa hari ini tidak hujan”.
29. Tentukan nilai kebenaran dari masing-masing pernyataan berikut : a. Kopenhagen ad di Denmark, dan 1 + 1 = 5 atau 2 + 2 = 4. b. Paris ada di Inggris, atau 1 + 1 = 2 dan 3 + 3 = 7. Jawab: a. Pernyataan “1 + 1 = 5 atau 2 + 2 = 4” adalah benar karena salah satu subpernyataannya adalah benar karena ini adalah konjungsi dari dua pernyataan yang benar, “Kopenhagen ada di Denmark” dan “1 + 1 = 5 atau 2 + 2 = 4”. b. Pernyataan “1 + 1 = 2 dan 3 + 3 = 7” adalah salah karena salah satu sub-pernyataannya, “3 + 3 = 7”, adalah salah. Sehingga, pernyataan yang diberikan adalah salah karena ini adalah disjungsi dari dua pernyataan salah.
30. Tentukan banyaknya
m preposisi yang tidak ekuivalen dalam : a. Tiga variable p, q dan r; b. n variable p1, p2, …. pn. Jawab: a. Tabel kebenaran dari P (p, q, r) akan memuat 23 = 8 baris. Dalam setiap baris, T atau F dapat muncul; sehingga m = 28 = 256.
Soal Logika Informatika Pra-S2 Kelas A/2006 - 7
b.
Tabel kebenaran dari P (p1, p2,…, pn) akan memuat 2n baris; sehingga seperti di atas , m = 22n.
31. Tentukan Y = A + B dimana: a. A = 11000110, B = 10010101, dan b. A = 00001100, B = 11000000. Jawab: Penjumlahan akan menghasilkan 0 hanya bilamana kedua input adalah 0; sehingga, (a) Y = 11010111, (b) Y = 11001100. 32. Tentukan apakah kalimat G dibawah ini termasuk valid, kontrakdiksi ataukah satisfiabel dengan menggunakan tabel kebenaran : G : if ( if P then Q ) then ( if ( not P ) then ( not Q )) Jawab : P q not p not q if p then q True True False False True True False False True False False True True False True False False True True True Karena kalimat G tidak selalu bernilai benar dan tidak diatas termasuk satisfiabel. 33. Tuliskan : a. Tabel kebenaran b. Bentuk minimal _ _ Dari fungsi boole F = ABC + ABC + AC Jawab : a) Tabel kebenaran _ _ A B C ABC C A 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 1 b) Bentuk Minimal _ _ F = ABC + ABC + AC _ _ = AB ( C + C ) + AC _ = AB + AC =B+C
_ ABC 0 1 0 0 0 0 0 0
_ AC 0 0 0 0 1 0 1 0
if(not p) then (not q) True True False True selalu bernilai salah maka
g True True False true kalimat G
_ _ ABC+ABC+AC 1 1 0 0 1 0 1 0
34. Diketahui rangkaian sekuensial dengan input A, B, C, D dan output F , yang wataknya dideskripsikan dengan tabel kebenaran berikut : Tentukan persamaan boole-nya dalam bentuk paling sederhana dengan peta karnough A 0 0 0 0 0 0
B 0 0 0 0 1 1
C 0 0 1 1 0 0
D 0 1 0 1 0 1
F 0 1 1 1 0 0
Soal Logika Informatika Pra-S2 Kelas A/2006 - 8
0 0 1 1 1 1 1 1 1 1
1 1 0 0 0 0 1 1 1 1
1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1
__
1 0 1 1 1 0 1 1 1 0
_ CD
_ CD
CD
CD
__ AB
0
1
1
1
_ AB
0
0
0
1
AB
1
1
0
1
_ AB
1
1
0
1
Ekspresi Boole dari gambar di atas adalah : __ Kelompok pasangan menghasilkan : F = ABD _ Kelompok kuad(1) menghasilkan : F = A C _ Kelompok kuad(2) menghasilkan : F = C D Bentuk ekspresi boole selengkapnya adalah : __ _ _ F = ABD + AC + CD 35. Jelaskan sebuah circuit AND-OR dan berikan sebuah contoh : Jawab : Sebuah circuit AND-OR, yang berhubungan dengan ekspresi sum-of-product boolean, mempunyai beberapa input, dengan komplemennya diberikan dalam setiap gerbang AND. Output dari semua gerbang AND diberikan dalam sebuah gerbang OR tunggal yang merupakan output untuk circuit. Gambar dibawah ini merupakan jenis circuit AND-OR dengan input A, B dan C. A B C
AND
AND
OR
Y
AND
36. “Jika p mengakibatkan q dan q mengakibatkan r, maka p mengakibatkan r” Sehingga argument berikut adalah valid: p q, q r |-- p r Buktikan pernyataan diatas adalah valid. Jawab: p
q
r
[(p
q)
∧
(q
r) ]
(p
r)
Soal Logika Informatika Pra-S2 Kelas A/2006 - 9
T T T T F F F F
T T F F T T F F
T F T F T F T F
T T T T F F F F
T T F F T T T T
T T F F T T T T
T F F F T F T T
T T F F T T F F
T F T T T F T T
T F T F T F T F
T T T T T T T T
T T T T F F F F
T F T F T T T T
T F T F T F T F
37. Buktikan argumen berikut adalah valid: P ~q, r q, r |-- ~ p. Jawab: p q r p~q rq ~p T T T F T F T T F F T F T F T T F F T F F T T F F T T T T T F T F T T T F F T T F T F F F T T T p ~ q, r q dan r adalah benar secara bersama-sama hanya pada baris yang diarsir, dimana ~ p juga benar; sehingga argumen yang diberikan adalah benar. 38. Tentukan penjumlahan minimal untuk ekspresi Boolean E yang diwakili oleh pemetaan Karnaugh di bawah ini:
zt
zt’
z’ t’
z’ t
√
xy
√
x y’
√
√
√
√
x’ y’
x’ y
√
√
Jawab: Terdapat lima prime implicant, ditunjukkan oleh empat loop dan lingkaran putus-putus. Tetapi lingkaran putus-putus tidak diperlukan untuk menutupi semua square, sedangkan keempat loop diperlukan. Sehingga keempat loop memberikan penjumlahan minimal untuk E = xzt’ + xy ‘z’ + x’y’z + x’z’t’.
39. Tuliskan
pernyataan dalam Notasi Polandia berikut ini dengan menggunakan Λ dan ~ dari pada A dan N : a. NAANpqr b. ANpAqNr Jawab :
a. NAANpqr
= NAA (~ p) qr = NA (~ p Λ q ) r
Soal Logika Informatika Pra-S2 Kelas A/2006 - 10
b.
ANpAqNr
= N [ (~ p Λ q ) Λ r ] =~[(~pΛq)Λ r] = ANpAq ( ~ r ) = ANp ( q Λ ~ r) = A ( ~p ) (q Λ ~r) = ~p Λ ( q Λ ~r)
40. Tunjukan bahwa proposisi (pΛ ~q) V ~(pΛ~q) adalah tautology Jawab : (pΛ ~q) V ~(pΛ~q) ekuivalen dengan P V ~P, dimana PV~P menurut Hk. Negasi adalah suatu Tautologi.
41. Buktikan bahwa proposisi ( p Λ q) Λ ~(p V q) adalah sebuah kontradiksi. Jawab : Buatlah table kebenaran dari notasi tersebut seperti di bawah ini : p q PΛq qVq ~ (p V q) ( p Λ q) Λ ~ (p V q) T T T T F F Kontradiksi T F F T F F F T F T F F F F F F T F Karena ( p Λ q) Λ ~ (p V q) mempunyai nilai kebenaran F, maka nilai proporsinya adalah sebuah Kontradiksi. 42. Buktikan bahwa operasi conditional distributive terhadap konjungsi; yaitu : p ( q Λ r) ≅ (p q) Λ ( p r ) Jawab : dari pernyataan tersebut dapat dibuat table kebenarannya p T T T T F F F F
q T T F F T T F F
R T F T F T F T F
qΛr T F F F T F F F
p ( q Λ r) T F F F T T T T
pq T T F F T T T T
pr T F T F T T T T
( p q) Λ (p r) T F F F T T T T
Terbukti Mempunyai table kebenaran yang sama
43. Tentukan keabsahan kesimpulan C yang diturunkan secara logika dari H1 dan H2 serta H3: H1 : p→q p T T F F
q T F T F
H2 : ¬p p→q T F T T
C:q ¬p F F T T
Tidak Sah
q T F T F
44. Tuliskan negasi dari setiap pernyataan dengan sebuah kalimat yang sesederhana mungkin. a. Jika hari dingin maka ia memakai baju dingin tetapi bukan sweater. b. Jika dia belajar maka ia akan pergi ke kampus atau sekolah seni.
Soal Logika Informatika Pra-S2 Kelas A/2006 - 11
Jawab : a. Misalkan p adalah “Hari ini dingin”, q adalah “Dia memakai baju dingin”, da r adalah “Dia memakai sweater”. Maka pernyataan yang diberikan dapat dituliskan sebagai P(q^~r) ≡p^~(q^~r)≡p^(~qVr) Pernyataan Negasinya adalah : Hari ini dingin dan ia memakai sweater atau bukan baju dingin b. Pernyataan yang diberikan berbentuk p ( q V r ). Tetapi ~ [ p ( ( q V r ) ] ≡ p ^ ~ ( q V r ) ≡ p ^ ~ q ^ ~ r pernyataan negasinya adalah : Dia belajar dan dia tidak pergi ke kampus maupun sekolah seni. 45. Tentukan kontraposisi dari pernyataan berikut : a. Jika dia berani maka ia akan menang b. Perlu kuat untuk menjadi seorang pelayar c. Hanya jika ia tidak lelah ia akan menang d. Cukup sebuah empat persegi untuk menjadi sebuah segitiga Jawab : a. jika ia tidak menang maka ia tidak mempunai keberanian b. Jika ia tidak kuat maka ia bukan seorang pelayar c. Jika ia lelah maka ia tidak akan menang d. Jika ia bukan segitiga maka ia bukan sebuah empat persegi.
46. Diberikan persamaan : p q ^ r (q ⇔ ¬r ⇔ (r ↑ p)) a. b. c.
Tuliskan tabel kebenarannya Sebutkan apakah ia tatutologi, absurditi, atau formula tercampur.! Ekspresikan dalam BNDP dan BNKP
Jawab: a. Tabel kebenarannya adalah sebagai berikut:
p
q
r
p
q
^
r
(q
⇔
¬
r
⇔
(r
↑
p))
T T T T F F F F
T T F F T T F F
T F T F T F T F
T T T T F F F F
T F F F T T T T
T T F F T T F F
T F F F T F F F
T F T F T F T F
T T T T F T T F
T T F F T T F F
F T T F F T T F
F T F T F T F T
T F T F T F T F
T T F F F T T F
T F T F T F T F
F T F T T T T T
T T T T F F F F
b. Hasilnya adalah formula tercampur. c. Ekspresi BNDP dan BNKP BNDP : (p ^q ^ r) v (p ^q ^¬r) v (p ^¬q ^r) v (p ^¬q ^¬r) v (¬p ^q^¬r) v (¬p ^¬q ^¬r) BNKP : (¬p v q v r) ∧ (¬p v ¬q v r) 47. Untuk E = xy + y ’ t + x ‘ yz ’ + xy ‘ zt ‘ a. Selesaikan dengan Metode Konsensus untuk E = xy + y ‘ t + x ‘ yz ‘ + xy ‘ zt ‘ + xzt ‘ b. Tentukan sebagai penjumlahan minimal untuk soal di atas. Dengan Algoritma berikut ini, Tuliskan setiap prime implicant dalam bentuk sum-of product lengkap Hapus salah satunya dengan satu yang merupakan superfluous.
Soal Logika Informatika Pra-S2 Kelas A/2006 - 12
Jawab : a. Metode Konsensus E = xy + y ’ t + x ‘ yz ‘ + xy ‘ zt ‘ + xzt ‘ ( konsensus dari xy dan xy ‘ zt ‘ ) = xy + y ‘ t + x ‘ yz ‘ + xz ‘ t ( xy ‘ zt ‘ memuat xzt ‘ ) = xy + y ‘ t + x ‘ yz ’ + xzt ‘ + yz ( konsensus dari xy dan x ‘ yz ‘ ) = xy + y ‘ t + xzt ‘ + yz ‘ ( x ‘ yz ‘ memuat yz ‘ ) = xy + y ‘ t + xz ‘ t + yz ’ + xt ( konsensus dari xy dan y ‘ t ) = xy + y ‘ t + xz ‘ t + yz ‘ + xt + xz ( konsensus dari xz ‘ t dan xt ) = xy + y ‘ t + yz ‘ + xt + xz ( xzt ’ memuat xz ) = xy + y ‘ t + yz ‘ + xt + xz + z ‘ t ( konsensus dari y ‘ t dan yz ) b. E = y ‘ t + xz + yz ‘
48. Gunakan pemetaan Karnaugh untuk menentukan penjumlahan minimal untuk E = xy ‘ + xyz + x ‘ y ‘ z ‘ + x ‘ yzt ‘ Periksa semua Square yang mewakili setiap fundamental product. Yaitu periksa keempat square yang mewakili xy ‘ , dua square yang mewakili xyz, dua square yang mewakili x‘ y‘ z‘, dan satu square yang mewakili x ‘ yzt’ , sehingga E = xz + y ’ z ‘ + yzt ‘ merupakan penjumlahan minimal untuk E. Gambarkan ! Jawab : zt xy xy’ x’y’ x’y
√ √
zt ‘ √ √
z’t’ √ √
√
z‘t √ √
49. Tuliskan negasi dari setiap pernyataan berikut sesederhana mungkin. A. Dia tinggi tetapi tampan B. Dia berambut pirang atau bermata biru Jawab : A. p = Tinggi ; q = Tampan (p Λ q) Negasinya adalah ~(pΛq) ≡ ~p V ~q yang berarti Dia tidak tinggi atau tidak tampan B. p = Pirang ; q = Mata Biru (pVq) Negasinya adalah ~(pVq) ≡ ~p Λ ~q yang berarti Dia Tidak pirang dan tidak bermata biru
50. Negasikan ∃y ∃x ( p(x) Λ ~q(y) ) Jawab : ~[∃y ∃x ( p(x) Λ ~q(y) )] ≡
A A y
x ~( p(x) Λ ~q(y) ) ≡
A A y
x ( ~p(x) V q(y) )
51. Transformasikan E = ((ab)’c)’ ((a’+c)(b’+c’))’ ke dalam bentuk sum of product. Jawab : E:= ((ab)’’ + c’) ((a’+c)’+(b’+c’)’) = (ab+c’) (ac’+bc) E:= abac’+abbc+ac’c’+bcc’ E:= abc’+abc+ac’ + 0 = ac’ + abc
Soal Logika Informatika Pra-S2 Kelas A/2006 - 13
