Matematika Diskrit - Logika Proposisi
Aturan logika matematika menentukan metode penalaran pernyataan matematika. Filsuf Yunani, Aristoteles, adalah pelopor penalaran logis. Penalaran logis memberikan dasar teoritis untuk banyak bidang matematika dan akibatnya ilmu komputer. Ini memiliki banyak aplikasi praktis dalam ilmu komputer seperti desain mesin komputasi, kecerdasan buatan, definisi struktur data untuk bahasa pemrograman, dll.
Propositional Logicberkaitan dengan pernyataan di mana nilai kebenaran, "benar" dan "salah", dapat ditetapkan. Tujuannya adalah untuk menganalisis pernyataan ini baik secara individu maupun gabungan.
Logika Preposisional - Definisi
Proposisi adalah kumpulan pernyataan deklaratif yang memiliki nilai kebenaran "benar" atau nilai kebenaran "salah". Proposisi terdiri dari variabel proposisional dan penghubung. Kami menunjukkan variabel proposisional dengan huruf kapital (A, B, dll). Penghubung menghubungkan variabel proposisional.
Beberapa contoh Proposisi diberikan di bawah ini -
- "Man is Mortal", ini mengembalikan nilai kebenaran "TRUE"
- "12 + 9 = 3 - 2", ini mengembalikan nilai kebenaran "FALSE"
Berikut ini bukan Proposisi -
"A kurang dari 2". Itu karena kecuali kita memberikan nilai A tertentu, kita tidak dapat mengatakan apakah pernyataan itu benar atau salah.
Connectives
Dalam logika proposisional umumnya kami menggunakan lima penghubung yaitu -
ATAU ($ \ lor $)
DAN ($ \ land $)
Negasi / TIDAK ($ \ lnot $)
Implikasi / if-then ($ \ rightarrow $)
Jika dan hanya jika ($ \ Leftrightarrow $).
OR ($\lor$) - Operasi OR dari dua proposisi A dan B (ditulis sebagai $ A \ lor B $) benar jika setidaknya salah satu variabel proposisional A atau B benar.
Tabel kebenarannya adalah sebagai berikut -
| SEBUAH | B | A ∨ B |
|---|---|---|
| Benar | Benar | Benar |
| Benar | Salah | Benar |
| Salah | Benar | Benar |
| Salah | Salah | Salah |
AND ($\land$) - Operasi AND dari dua proposisi A dan B (ditulis sebagai $ A \ land B $) bernilai benar jika variabel proposisional A dan B bernilai benar.
Tabel kebenarannya adalah sebagai berikut -
| SEBUAH | B | A ∧ B |
|---|---|---|
| Benar | Benar | Benar |
| Benar | Salah | Salah |
| Salah | Benar | Salah |
| Salah | Salah | Salah |
Negation ($\lnot$) - Negasi dari proposisi A (ditulis sebagai $ \ lnot A $) salah jika A benar dan benar ketika A salah.
Tabel kebenarannya adalah sebagai berikut -
| SEBUAH | ¬ A |
|---|---|
| Benar | Salah |
| Salah | Benar |
Implication / if-then ($\rightarrow$)- Implikasi $ A \ rightarrow B $ adalah proposisi “jika A, maka B”. Salah jika A benar dan B salah. Kasus lainnya benar.
Tabel kebenarannya adalah sebagai berikut -
| SEBUAH | B | A → B |
|---|---|---|
| Benar | Benar | Benar |
| Benar | Salah | Salah |
| Salah | Benar | Benar |
| Salah | Salah | Benar |
If and only if ($ \Leftrightarrow $) - $ A \ Leftrightarrow B $ adalah koneksi logika bi-kondisional yang benar jika p dan q sama, yaitu keduanya salah atau keduanya benar.
Tabel kebenarannya adalah sebagai berikut -
| SEBUAH | B | A ⇔ B |
|---|---|---|
| Benar | Benar | Benar |
| Benar | Salah | Salah |
| Salah | Benar | Salah |
| Salah | Salah | Benar |
Tautologi
Tautologi adalah rumus yang selalu benar untuk setiap nilai variabel proposisionalnya.
Example - Buktikan $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ adalah tautologi
Tabel kebenarannya adalah sebagai berikut -
| SEBUAH | B | A → B | (A → B) ∧ A | [(A → B) ∧ A] → B |
|---|---|---|---|---|
| Benar | Benar | Benar | Benar | Benar |
| Benar | Salah | Salah | Salah | Benar |
| Salah | Benar | Benar | Salah | Benar |
| Salah | Salah | Benar | Salah | Benar |
Seperti yang bisa kita lihat setiap nilai $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ adalah "True", ini adalah tautologi.
Kontradiksi
Kontradiksi adalah rumus yang selalu salah untuk setiap nilai variabel proposisionalnya.
Example - Buktikan $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ adalah kontradiksi
Tabel kebenarannya adalah sebagai berikut -
| SEBUAH | B | A ∨ B | ¬ A | ¬ B | (¬ A) ∧ (¬ B) | (A ∨ B) ∧ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| Benar | Benar | Benar | Salah | Salah | Salah | Salah |
| Benar | Salah | Benar | Salah | Benar | Salah | Salah |
| Salah | Benar | Benar | Benar | Salah | Salah | Salah |
| Salah | Salah | Salah | Benar | Benar | Benar | Salah |
Seperti yang bisa kita lihat setiap nilai $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ adalah “False”, itu adalah kontradiksi.
Kemungkinan
Kontingensi adalah rumus yang memiliki nilai benar dan salah untuk setiap nilai variabel proposisionalnya.
Example - Buktikan $ (A \ lor B) \ land (\ lnot A) $ a contingency
Tabel kebenarannya adalah sebagai berikut -
| SEBUAH | B | A ∨ B | ¬ A | (A ∨ B) ∧ (¬ A) |
|---|---|---|---|---|
| Benar | Benar | Benar | Salah | Salah |
| Benar | Salah | Benar | Salah | Salah |
| Salah | Benar | Benar | Benar | Benar |
| Salah | Salah | Salah | Benar | Salah |
Seperti yang bisa kita lihat setiap nilai $ (A \ lor B) \ land (\ lnot A) $ memiliki “True” dan “False”, ini adalah kontingensi.
Persamaan Proposisional
Dua pernyataan X dan Y secara logis setara jika salah satu dari dua kondisi berikut berlaku -
Tabel kebenaran setiap pernyataan memiliki nilai kebenaran yang sama.
Pernyataan dua bersyarat $ X \ Leftrightarrow Y $ adalah sebuah tautologi.
Example - Buktikan $ \ lnot (A \ lor B) dan \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ setara
Pengujian oleh 1 st metode (Matching tabel kebenaran)
| SEBUAH | B | A ∨ B | ¬ (A ∨ B) | ¬ A | ¬ B | [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| Benar | Benar | Benar | Salah | Salah | Salah | Salah |
| Benar | Salah | Benar | Salah | Salah | Benar | Salah |
| Salah | Benar | Benar | Salah | Benar | Salah | Salah |
| Salah | Salah | Salah | Benar | Benar | Benar | Benar |
Di sini, kita dapat melihat nilai kebenaran $ \ lnot (A \ lor B) dan \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ sama, oleh karena itu pernyataannya setara.
Pengujian oleh 2 nd metode (Bi-persyaratan)
| SEBUAH | B | ¬ (A ∨ B) | [(¬ A) ∧ (¬ B)] | [¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|
| Benar | Benar | Salah | Salah | Benar |
| Benar | Salah | Salah | Salah | Benar |
| Salah | Benar | Salah | Salah | Benar |
| Salah | Salah | Benar | Benar | Benar |
Karena $ \ lbrack \ lnot (A \ lor B) \ rbrack \ Leftrightarrow \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ adalah tautologi, pernyataannya setara.
Invers, Converse, dan Contra-positive
Implikasi / if-then $ (\ rightarrow) $ juga disebut pernyataan bersyarat. Ini memiliki dua bagian -
- Hipotesis, hal
- Kesimpulan, q
Seperti disebutkan sebelumnya, ini dilambangkan sebagai $ p \ rightarrow q $.
Example of Conditional Statement- "Jika Anda mengerjakan pekerjaan rumah Anda, Anda tidak akan dihukum." Di sini, "Anda mengerjakan pekerjaan rumah Anda" adalah hipotesisnya, p, dan "Anda tidak akan dihukum" adalah kesimpulannya, q.
Inverse- Kebalikan dari pernyataan bersyarat adalah negasi dari hipotesis dan kesimpulan. Jika pernyataannya adalah “If p, then q”, inversnya menjadi “If not p, then not q”. Jadi kebalikan dari $ p \ rightarrow q $ adalah $ \ lnot p \ rightarrow \ lnot q $.
Example - Kebalikan dari "Jika Anda mengerjakan pekerjaan rumah, Anda tidak akan dihukum" adalah "Jika Anda tidak mengerjakan pekerjaan rumah Anda, Anda akan dihukum."
Converse- Kebalikan dari pernyataan bersyarat dihitung dengan mempertukarkan hipotesis dan kesimpulan. Jika pernyataannya adalah “Jika p, maka q”, kebalikannya adalah “Jika q, maka p”. Kebalikan dari $ p \ rightarrow q $ adalah $ q \ rightarrow p $.
Example - Kebalikan dari "Jika kamu mengerjakan pekerjaan rumah, kamu tidak akan dihukum" adalah "Jika kamu tidak akan dihukum, kamu mengerjakan pekerjaan rumahmu".
Contra-positive- Kontra-positif dari kondisional dihitung dengan mempertukarkan hipotesis dan kesimpulan pernyataan terbalik. Jika pernyataannya adalah “Jika p, maka q”, kontra-positifnya adalah “Jika bukan q, maka bukan p”. Kontra-positif dari $ p \ rightarrow q $ adalah $ \ lnot q \ rightarrow \ lnot p $.
Example - Kontra-positif dari "Jika Anda mengerjakan pekerjaan rumah Anda, Anda tidak akan dihukum" adalah "Jika Anda dihukum, Anda tidak mengerjakan pekerjaan rumah Anda".
Prinsip Dualitas
Prinsip dualitas menyatakan bahwa untuk setiap pernyataan yang benar, pernyataan ganda yang diperoleh dengan menukar serikat menjadi persimpangan (dan sebaliknya) dan menukar himpunan Universal menjadi himpunan Null (dan sebaliknya) juga benar. Jika dua dari pernyataan apapun adalah pernyataan itu sendiri, itu dikatakanself-dual pernyataan.
Example - Kembaran dari $ (A \ cap B) \ cup C $ adalah $ (A \ cup B) \ cap C $
Bentuk Normal
Kita dapat mengubah proposisi apa pun dalam dua bentuk normal -
- Bentuk normal konjungtif
- Bentuk normal terputus
Bentuk Normal Konjungtif
Pernyataan gabungan dalam bentuk normal konjungtif jika diperoleh dengan mengoperasikan AND di antara variabel (negasi variabel yang disertakan) yang terhubung dengan OR. Dalam hal operasi himpunan, ini adalah pernyataan gabungan yang diperoleh dengan Persimpangan antara variabel yang terhubung dengan Serikat.
Examples
$ (A \ lor B) \ land (A \ lor C) \ land (B \ lor C \ lor D) $
$ (P \ cangkir Q) \ cap (Q \ cangkir R) $
Bentuk Normal Pemutusan
Pernyataan majemuk berada dalam bentuk normal disjungtif jika diperoleh dengan mengoperasikan OR di antara variabel (negasi variabel yang disertakan) yang terhubung dengan AND. Dalam hal operasi himpunan, ini adalah pernyataan gabungan yang diperoleh Union di antara variabel yang terhubung dengan Intersections.
Examples
$ (A \ tanah B) \ lor (A \ tanah C) \ lor (B \ tanah C \ tanah D) $
$ (P \ cap Q) \ cup (Q \ cap R) $