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) $