Review Algoritma

PERTEMUAN 1 (TEORI 1)

Apasih algoritma itu ?

Algoritma adalah kumpulan instruksi/perintah/langkah yang berhingga jumlahnya, dituliskan secara sistematis, dan digunakan untuk menyelesaikan masalah/persoalan logika dan matematika dengan bantuan komputer.

Proposisi (Propositions)

Proposisi (pernyataan) adalah komponen dasar pembentuk kalimat logika (sentence) dalam logika proposional. Proposisi dalam kalimat logika dinyatakan dengan symbol-simbol proposisi : 

          

● Simbol atau nilai kebenaran (truth value) yaitu true dan false

● Simbol-simbol proposisional (propositional symbols) yaitu huruf-huruf p,q,r,s,t,….

Notasi (Notation)

Notasi Englishlike	Notasi Konvesional
not	~
and	ʌ
or	v
if-then	→
if-and-only-if	↔
if-then-else	Tidak ada

Sematic Rule

Sematic Rule adalah suatu aturan yang digunakan untuk menentukan arti atau nilai kebenaran dari suatu kalimat logika.

1.      Negative Rule (Aturan Not) 

p	~p
true	false
false	true

2.     Conjunction Rule (Aturan And)

p	~p	p ʌ q
true	true	true
true	false	false
false	true	false
false	false	false

Konjungsi bernilai benar (true) apabila kedua proposisi penyusunnya bernilai benar (true). Apabila salah satu proposisi penyusunnya bernilai salah, atau bahkan keduanya bernilai salah, maka konjungsi bernilai salah (false).

3.     Disjunction Rule (Aturan Or)

p	q	p v q
true	true	true
true	false	true
false	true	true
false	false	false

Disjungsi bernilai salah (false) apabila kedua proposisi penyusunnya bernilai salah (false). Apabila salah satu proposisi penyusunnya bernilai benar, atau bahkan keduanya bernilai benar, maka disjungsi bernilai benar (true).

4.     Implication Rule (Aturan If-Then)

p	q	p → q
true	true	true
true	false	false
false	true	true
false	false	true

Implikasi bernilai false bila anteseden true dan konsekuennya bernilai false.

5.   Equivalence Rule (Aturan If-And-Only-If)

p	q	p ↔ q
true	true	true
true	false	false
false	true	false
false	false	true

Ekuivalen atau biimplikasi bernilai true jika nilai kebenaran dari proposisi penyusunnya adalah sama.

6.  Conditional Rule (Aturan If-Then-Else)

p	q	r	If p then q else r
true	true	true	true
true	true	false	true
true	false	true	false
true	false	false	false
false	true	true	true
false	true	false	false
false	false	true	true
false	false	false	false

Contoh:

Diberikan kalimat logika sebagai berikut:

not (p and(notp)) or q 

diubah dalam bentuk notasi konvesional 

~(p ʌ ~p) v q

Tentukan nilai kebenaran dari kalimat tersebut.

Tabel kebenarannya:

p	q	~p	p ʌ ~p	~(p ʌ (~p))	~(p ʌ ~p) v q
T	T	F	F	T	T
T	F	F	F	T	T
F	T	T	T	F	T
F	F	T	F	T	T

Sumber:

Sismoro, Heri., Pengantar Logika Informatika, Algoritma, dan Pemrograman Komputer, Penerbit ANDI, Yogyakarta, 2005