Matematika Logika Bab I

7/22/2019 Matematika Logika Bab I

1/34

Matematika Diskrit01-LOGIKA


2/34

Komputer (dijital) beroperasi secara diskritdengan unit terkecil yg disebut bit.

Dengan demikian, baik

Struktur (rangkaian) dan juga Operasi (eksekusi algoritma)

Dapat dijelaskan dengan matematika diskrit

Matematika Diskrit Kuliah-1 2

Mengapa matematika diskrit ?


3/34

Perangkat yang berguna dalam matematika diskrit:

Logika Matematika (Logic)

Teori Himpunan (Set Theory)

Fungsi (Functions)

Deretan (Sequences)


Perangkat Matematika


4/34

Berguna untuk melakukan penalaran matematika Digunakan dalam mendesain rangkaian elektronik.

Logika adalah suatu sistem yang didasarkan padaproposisi.

Suatu proposisi adalah sebuah pernyataan yang bisabernilai benar (true/T)atau salah(false/F) tetapi tidaksekaligus keduanya.

Kita katakan bahwa nilai kebenaran(truth value)darisebuah proposisi adalah benaratau salah.

Dalam rangkaian dijital, nilai ini dinyatakan sebagai 1dan 0


Logika


5/34

Gajah lebih besar daripada tikus.


Proposisi atau Pernyataan

Apakah ini sebuah pernyataan? YA

Apakah ini sebuah proposisi? YA

Apakah nilai kebenarandari proposisi ini?

BENAR


6/34

520 < 111






SALAH


7/34

y > 5



Nilai kebenaran dari pernyataan tersebut

bergantung pada y, tapi nilainya belum

ditentukan.


Apakah ini sebuah proposisi? TIDAK

Pernyataan jenis ini kita sebut sebagai fungsiproposisiatau kalimat terbuka.


8/34

Sekarang tahun 2004 dan 99 < 5.






SALAH


9/34

Tolong untuk tidak tidur selama kuliah



TIDAK

TIDAK

Hanya pernyataanlah yang bisa menjadi

proposisi.

Ini adalah sebuah permintaan.

Apakah ini sebuah pernyataan?

Apakah ini sebuah proposisi?


10/34

x < y jika dan hanya jika y > x.



Apakah ini pernyataan ? YA

Apakah ini proposisi ? YA

Apakah nilai kebenaran

dari proposisi ini ? BENAR

karena nilai kebenarannya

tidak bergantung harga

spesifik x maupun y.


11/34

Beberapa contoh terdahulu menunjukkanbahwa beberapa proposisi dapat digabungmenjadi sebuah proposisi gabungan.

Hal ini kita formal-kan dengan melambangkanproposisi sebagai huruf-huruf; seperti p, q, r, s;

dan memperkenalkan operator-operator logika.


Penggabung Proposisi


12/34

Kita akan membahas operator-operator berikut:

Negasi (NOT)

Konjungsi (AND)

Disjungsi (OR)

Eksklusif OR (XOR) Implikasi (jika maka)

Bikondisional (jika dan hanya jika)

Tabel logika (tabel kebenaran/ truth table) dapatdipakai untuk menunjukkan bagaimana operator-operator tsb diatas menggabungkan beberapa proposisimenjadi satu proposisi gabungan.


Operator logika


13/34

Operator Uner, Lambang:


Negasi (NOT)

P PBenar Salah

Salah Benar


14/34

Operator Biner, Lambang:


Konjungsi (AND)

P Q PQ

Benar Benar Benar

Benar Salah Salah

Salah Benar SalahSalah Salah Salah


15/34



Disjungsi (OR)

P Q PQBenar Benar Benar

Benar Salah Benar

Salah Benar BenarSalah Salah Salah


16/34



Eksklusif Or (XOR)

P Q PQBenar Benar Salah

Benar Salah Benar

Salah Benar BenarSalah Salah Salah


17/34



Implikasi (jika - maka)


Benar Salah Salah

Salah Benar BenarSalah Salah Benar


18/34



Bikondisional (jika dan hanya jika)


Benar Salah Salah

Salah Benar SalahSalah Salah Benar


19/34

Pernyataan-pernyataan dan operator-operator dapatdigabungkan menjadi suatu pernyataan baru.


Pernyataan dan Operasi

P Q P Q (P)(Q)

Benar Benar Salah Salah Salah

Benar Salah Salah Benar Benar

Salah Benar Benar Salah Benar

Salah Salah Benar Benar Benar


20/34


Pernyataan dan Operasi

P Q PQ (PQ) (P)(Q)

Benar Benar Benar Salah Salah

Benar Salah Salah Benar Benar

Salah Benar Salah Benar Benar

Salah Salah Salah Benar Benar

Pernyataan-pernyataan dan operator-operator dapat

digabungkan menjadi suatu pernyataan baru.


21/34

Pernyatan(PQ) dan (P)(Q) adalah ekivalen secara logis,

karena(PQ)(P)(Q) selalu benar.


Pernyataan-pernyataan yang ekivalen

P Q (PQ) (P)(Q) (PQ)(P)(Q)Benar Benar Salah Salah Benar

Benar Salah Benar Benar Benar

Salah Benar Benar Benar Benar

Salah Salah Benar Benar Benar


22/34

Suatu tautologiadalah pernyataan yang selalubernilai benar

Contoh:

R(R)(PQ)(P)(Q)

Jika ST sebuah tautologi, kita tulis S T. JIka ST sebuah tautologi, kita tulis S T.


Tautologi dan Kontradiksi


23/34

Suatu kontradiksiadalah pernyataan yang selalubernilai salah.

Contoh:

R(R)((PQ)(P)(Q)) Negasi dari sebarang tautologi adalah sebuah

kontradiksi, sebaliknya, negasi dari sebuahkontradiksi adalah sebuah tautologi.


Kontradiksi


24/34

Kita tahu tautologi berikut:

(PQ)(P)(Q)

Latihan di kelas :Tunjukkan bahwa(PQ)(P)(Q).

Kedua tautologi ini disebut sebagai hukum DeMorgan


Latihan


25/34

Fungsi proposisi (kalimat terbuka) :

Pernyataan yang mengandung satu buah variabel atau lebih.

Contoh : x- 3 > 5.

Misalkan kita sebut fungsi proposisi ini sebagai P(x), dimana Padalah predikat dan xadalah variabel.


Proposisi dan Fungsi

Apakah nilai kebenaran dari P(2) ? Salah

Salah

Benar

Apakah nilai kebenaran dari P(8) ?

Apakah nilai kebenaran dari P(9) ?


26/34

Tinjau fungsi proposisi Q(x, y, z) yg didefinisikan:

x + y = z.

Disini, Q adalah predikat dan x, y, and z adalah

variabel.


Fungsi Proposisi

Apakah nilai kebenaran dari Q(2, 3, 5) ? Benar

Apakah nilai kebenaran dari Q(0, 1, 2) ?Apakah nilai kebenaran dari Q(9, -9, 0) ?

SalahBenar


27/34

Mis. P(x) suatu fungsi proposisi.

Kalimat yg dikuantifikasi secara universal :

Untuk semua x dalam semesta pembicaraan, P(x) adalahbenar.

Dengan kuantifier universal:

x P(x) untuk semua x P(x) atau

untuk setiap x P(x)

(Catatan:x P(x) bisa benar atau salah, jadi merupakan sebuah proposisi,bukan fungsi proposisi.)


Kuantifikasi Universal


28/34

Contoh :S(x): x adalah seorang mahasiswa TI

G(x): x adalah seorang yang pandai.

Apakah arti dari x (S(x)G(x)) ?Jika x adalah mahasiswa TI, maka x adalah seorangyang pandai

atauSemua mahasiswa TI pandai.


Kuantifikasi Universal


29/34

Kalimat yang di-kuantifikasi secara eksistensial:

Ada x di dalam semesta pembicaraan dimana P(x) benar.

Dengan peng-kuantifikasi eksistensial :

x P(x) Ada sebuah x sedemikian hingga P(x). Ada sedikitnya sebuah x sedemikian

hingga P(x).

(Catatan: x P(x) bisa benar atau salah, jadi merupakansebuah proposisi, tapi bukan fungsi proposisi.)


Kuantifikasi Eksistensial


30/34

Contoh :P(x): x adalah seorang dosen TI.G(x): x adalah seorang yang pandai.

Apakah arti x (P(x) G(x)) ?Ada x sedemikian hingga x adalah seorang dosen ITdan x adalah seorang yang pandai.atau

Sedikitnya satu orang dosen IT adalah seorang yangpandai.


Kuantifikasi Eksistensial


31/34

Contoh lain :Misalkan semesta pembicaraan adalah bilangan riil.

Apakah arti dari xy (x + y = 320)?

Untuk setiap xada ysehingga x + y = 320.


Kuantifikasi

Apakah pernyataan ini benar ?

Apakah ini benar untuk bilangan cacah?

Ya

Tidak


32/34

Counterexampledari

x P(x) adalah sebuah objek csehingga P(c) salah.

Pernyataan seperti x (P(x)Q(x)) dapat di-disproofsecara sederhana dengan memberikancounterexample-nya.


Disproofdengan counterexample

Pernyataan: Semua burung bisa terbang.

Disproofed dengancounterexample: Penguin.


33/34

(x P(x)) ekivalen scr logis dengan x (P(x)).

(x P(x)) ekivalen scr logis dengan x (P(x)).

Lihat Table 3 dalam Section 1.3.

Latihan soal pada Exercises 5 dan 9, Section 1.3.


Negasi


34/34

Kerjakan Soal : Nomor 1

Nomor 2

Nomor 3

Halaman 27 dan 28, Pada materi Matematika Diskrit.

SELAMAT BELAJAR.....


TUGAS

Matematika Logika Bab I

Documents

Transcript of Matematika Logika Bab I