logika proposisi (kalkulus proposisi) - telkom...

Logika Proposisi (Kalkulus Proposisi)Kuliah (Pengantar) Metode Formal Semester Ganjil 2015-2016

M. Arzaki

Fakultas InformatikaTelkom University

FIF Tel-U

September 2015

MZI (FIF Tel-U) Logika Proposisi (Kalkulus Proposisi) September 2015 1 / 95

Acknowledgements

Slide ini disusun berdasarkan materi yang terdapat pada sumber-sumber berikut:

Buku:

1 Logic in Computer Science: Modelling and Reasoning about Systems, Edisi 2,2004, oleh M. Huth dan M. Ryan (acuan utama).

2 Mathematical Logic for Computer Science, Edisi 2, 2000, oleh M. Ben-Ari.3 The Essence of Logic, 1997, oleh J. Kelly.4 Discrete Mathematics and Its Applications, Edisi 7, 2012, oleh K. H. Rosen.


Slide kuliah:

1 Slide kuliah Metode Formal dan Topik dalam Logika Komputasional diFasilkom UI oleh B. H. Widjaja.

2 Slide kuliah Metode Formal di University of Bozen-Bolzano oleh EnricoFranconi.

3 Slide kuliah Metode Formal dari Verified Software Systems.4 Slide kuliah Introduction to Computational Logic di Academia Sinica olehBow-Yaw Wang.

5 Slide kuliah Computational Logic di TU Dresden.

Beberapa gambar dapat diambil dari sumber-sumber di atas. Slide ini ditujukanuntuk keperluan akademis di lingkungan FIF Telkom University. Jika Andamemiliki saran/ pendapat/ pertanyaan terkait materi dalam slide ini, silakan kirimemail ke <pleasedontspam>@telkomuniversity.ac.id.


mailto:[email protected]

Bahasan

1 Beberapa Notasi Alfabet Yunani

2 Sintaks Logika Proposisi

3 Semantik Logika Proposisi

4 Konsistensi Spesifikasi Sistem

5 Bentuk Normal Negasi

6 Bentuk Normal Konjungtif dan Disjungtif


Bahasan








Notasi Alfabet Yunani

Dalam metode formal dan logika komputasional, kita akan menyatakan formuladan himpunan formula dengan alfabet yunani. Alfabet kecil digunakan untukmenyatakan formula dan alfabet kapital digunakan untuk menyatakan himpunanformula. Alfabet Yunani yang akan sering dipakai dan nama-namanya adalah

Alfabet kecil (lowercase), menyatakan formula:α (alfa), β (beta), γ (gamma), δ (delta), ε (epsilon), η (eta), θ (theta), λ(lambda), µ (mu), π (pi), ρ (rho), σ (sigma), τ (tau), φ (phi), χ (chi), ψ (psi), ω(omega).

Alfabet kapital (uppercase), menyatakan himpunan atau multiset formula:Γ (gamma), ∆ (delta), Φ (phi), Ψ (psi)


Bahasan








Operator Logika Proposisi

Diperkuliahan Logika Matematika, Anda telah diperkenalkan dengan operatorlogika proposisi. Berdasarkan banyaknya operand yang dioperasikan, operatorlogika proposisi yang umum dipakai dapat dibagi menjadi dua kategori, yaituoperator uner dan biner.

Operator uner (unary) merupakan operator yang hanya memerlukan satuoperand saja, contohnya adalah negasi (¬ atau ∼).Operator biner (binary) merupakan operator yang memerlukan dua operand,contohnya adalah konjungsi (∧), disjungsi (∨), disjungsi ekskulisif (⊕),implikasi (→), dan biimplikasi (↔).

Selain operator-operator di atas, dalam logika komputasional juga dikenalbeberapa operator biner lain (yang tidak terlalu sering dipakai), yaitu: operatornand (↑ atau |), operator nor (↓), operator implikasi-balik/ reverse-implication(←), operator negasi implikasi (6→), dan operator negasi implikasi-balik ( 6←).


Sintaks Logika Proposisi

Formula Logika ProposisiFormula (atau kalimat) logika proposisi dibentuk dari:

1 konstanta proposisi: > (benar) dan ⊥ (salah)2 variabel proposisi atom: p, q, r, p1, p2, p2, . . .3 operator logika proposisi: ¬,∧,∨,⊕,→,↔, (termasuk operator biner lain biladiperlukan)

dengan aturan sebagai berikut:

1 setiap proposisi (atom) merupakan formula logika proposisi,2 apabila φ dan ψ adalah dua formula logika proposisi, maka ¬φ, φ ∧ ψ, φ ∨ ψ,φ⊕ ψ, φ→ ψ, φ↔ ψ, (dan formula yang dihubungkan oleh operator binerlain bila diperlukan) masing-masing juga merupakan formula logika proposisi.


Subformula

Subformula1 Sebuah formula φ adalah subformula dari φ itu sendiri.2 Jika φ dan ψ adalah dua formula logika proposisi yang dipakai untukmembangun formula η yang lebih kompleks, maka φ dan ψ dikatakansubformula sejati (atau subformula murni) dari η.

3 Subformula bersifat transitif: jika φ subformula dari ψ dan ψ subformula dariη, maka φ subformula dari η.


Formula yang Terbentuk dengan Baik (Well-FormedFormula, WFF)

PermasalahanDari definisi tentang formula sebelumnya, apakah ekspresi p1 ∧ p2 ∧ p3 ∧ · · ·merupakan formula logika proposisi? Bagaimana dengan p1 ∨ p2 ∨ p3 ∨ · · · .

Definisi (Formula yang terbentuk dengan baik (well-formed formula,WFF))

Suatu formula φ dikatakan sebagai formula yang terbentuk dengan baik(well-formed formula) bila φ dapat dikonstruksi dengan berhingga langkah (finitestep) melalui aturan konstruksi formula logika proposisi yang telah dijelaskansebelumnya.

CatatanUntuk selanjutnya, istilah formula akan selalu berarti well-formed formula, kecualibila disebutkan selain itu.


Formula yang Terbentuk dengan Baik (Well-FormedFormula, WFF)

PermasalahanDari definisi tentang formula sebelumnya, apakah ekspresi p1 ∧ p2 ∧ p3 ∧ · · ·merupakan formula logika proposisi? Bagaimana dengan p1 ∨ p2 ∨ p3 ∨ · · · .

Definisi (Formula yang terbentuk dengan baik (well-formed formula,WFF))Suatu formula φ dikatakan sebagai formula yang terbentuk dengan baik(well-formed formula) bila φ dapat dikonstruksi dengan berhingga langkah (finitestep) melalui aturan konstruksi formula logika proposisi yang telah dijelaskansebelumnya.

CatatanUntuk selanjutnya, istilah formula akan selalu berarti well-formed formula, kecualibila disebutkan selain itu.


BNF untuk Formula Logika Proposisi

BNF (Backus Naur Form) untuk Formula Logika ProposisiMisalkan AP menyatakan himpunan proposisi atom yang ditinjau. Jika φ adalahsuatu formula logika proposisi, maka φ dibangkitkan oleh Backus Naur Form(BNF) berikut:

φ ::= p | ¬φ | φ ∧ φ | φ ∨ φ | φ⊕ φ | φ→ φ | φ↔ φ

Kita akan menulis > sebagai ringkasan dari φ ∨ ¬φ atau ¬φ ∨ φ. Kemudian kitajuga akan menulis ⊥ sebagai ringkasan dari φ ∧ ¬φ atau ¬φ ∧ φ.

CatatanPenulisan > dan ⊥ biasanya hanya digunakan ketika kita meninjau formula logikaproposisi secara sintaks saja. Jika kita meninjau formula logika proposisi secarasematik, maka kita akan menggunakan notasi T dan F, B dan S, atau 0 dan 1.


Konjungsi, Disjungsi, dan Xor yang Diperumum

Misalkan φ1, φ2, . . . , φn adalah formula logika proposisi, maka kita dapat menulis

φ1 ∧ φ2 ∧ · · · ∧ φn =

n∧i=1

φi

φ1 ∨ φ2 ∨ · · · ∨ φn =

n∨i=1

φi

φ1 ⊕ φ2 ⊕ · · · ⊕ φn =

n⊕i=1

φi


Presedens Operator Logika Proposisi

Presedens operator logika memberikan suatu aturan operator mana yang haruslebih dulu dioperasikan (dikenakan pada suatu operand).

Dari kuliah Logika Matematika, tabel urutan pengerjaan (presendens) operatorlogika adalah

Operator Urutan¬ 1∧ 2∨ 3⊕ 4→ 5↔ 6

Kita dapat menggunakan tanda kurung “(”dan “)”untuk memperjelas operasiyang harus didahulukan.


Presedens untuk Operator Logika Proposisi Lain

CatatanTidak ada konvensi secara umum yang menjelaskan presedens (hirarki) operatorlogika proposisi yang tidak terlalu sering dipakai, seperti ↑, ↓, ←, 6→, dan 6←.Untuk memperjelas urutan pengerjaan operator dan operand yang melibatkanoperator-operator tersebut kita akan memakai tanda kurung “(”dan “)”.


Fully Parenthesized Expression (FPE)

Definisi (Fully Parenthesized Expression)Suatu formula φ dikatakan dalam fully parenthesized expression (FPE) bila urutanpengerjaan operator dan operand dalam formula tersebut sudah diperjelas denganpemberian tanda kurung.

Sebagai contoh bentuk FPE dari p ∧ q → r ∨ s ∧ t adalah

(p ∧ q)→ (r ∨ (s ∧ t)).Bentuk FPE suatu formula logika proposisi tidak tunggal, sebagai contoh, bentukFPE dari formula p ∧ q ∧ r ada dua, yaitu (p ∧ q) ∧ r dan p ∧ (q ∧ r). Hal yangserupa juga berlaku untuk p ∨ q ∨ r, p⊕ q ⊕ r, dan p↔ q ↔ r.




Sebagai contoh bentuk FPE dari p ∧ q → r ∨ s ∧ t adalah (p ∧ q)→ (r ∨ (s ∧ t)).Bentuk FPE suatu formula logika proposisi tidak tunggal, sebagai contoh, bentukFPE dari formula p ∧ q ∧ r ada dua, yaitu

(p ∧ q) ∧ r dan p ∧ (q ∧ r). Hal yangserupa juga berlaku untuk p ∨ q ∨ r, p⊕ q ⊕ r, dan p↔ q ↔ r.




Sebagai contoh bentuk FPE dari p ∧ q → r ∨ s ∧ t adalah (p ∧ q)→ (r ∨ (s ∧ t)).Bentuk FPE suatu formula logika proposisi tidak tunggal, sebagai contoh, bentukFPE dari formula p ∧ q ∧ r ada dua, yaitu (p ∧ q) ∧ r dan p ∧ (q ∧ r). Hal yangserupa juga berlaku untuk p ∨ q ∨ r, p⊕ q ⊕ r, dan p↔ q ↔ r.


Pohon Urai (Parse Tree)Pohon urai (parse tree) digunakan untuk menggambarkan struktur suatu formulalogika proposisi.Sebagai contoh, pohon urai untuk formula (¬p ∧ q)→ (p ∧ (q ∨ ¬r)) adalah

Operator Utama

Definisi (Operator Utama)Misalkan φ adalah formula logika proposisi dan φ bukan proposisi atom. Operatorutama dari φ adalah operator logika yang terdapat pada akar (root) dari pohonurai yang mendeskripsikan φ. Formula φ dikatakan sebagai formula negasi(beturut-turut: konjungsi, disjungsi, xor, implikasi, biimplikasi) apabila operatorutama dari φ adalah operator negasi (berturut-turut: konjungsi, disjungsi, xor,impliasi, biimplikasi).

Contoh

Formula p ∧ ¬q adalah formula konjungsi, formula ¬ (p ∧ ¬q) adalah formulanegasi, dan formula p ∧ q → r adalah formula implikasi.

TeoremaJika φ adalah formula dalam bentuk FPE, maka φ hanya memiliki satu pohon uraisaja.


Operator Utama


ContohFormula p ∧ ¬q adalah formula konjungsi, formula ¬ (p ∧ ¬q) adalah formulanegasi, dan formula p ∧ q → r adalah formula implikasi.

Teorema

Jika φ adalah formula dalam bentuk FPE, maka φ hanya memiliki satu pohon uraisaja.


Operator Utama


ContohFormula p ∧ ¬q adalah formula konjungsi, formula ¬ (p ∧ ¬q) adalah formulanegasi, dan formula p ∧ q → r adalah formula implikasi.

TeoremaJika φ adalah formula dalam bentuk FPE, maka φ hanya memiliki satu pohon uraisaja.


Tinggi dan Ukuran Formula

Definisi (Tinggi Formula)Diberikan suatu formula φ, tinggi (height) dari φ didefinisikan sebagai 1 ditambahpanjang dari lintasan terjauh dari akar (root) ke suatu anak (child) pada pohonurai representasinya.

Definisi (Ukuran Formula)Diberikan suatu formula φ, ukuran (size) dari φ, dinotasi dengan |φ|, didefinisikansebagai banyaknya operator logika yang muncul di φ (termasuk multiplisitasnya).

ContohMisalkan φ adalah formula ¬ ((q → ¬p) ∧ (p→ r ∨ q)). Tinggi dari φ adalah

1 + 4 = 5 dan |φ| = |¬ ((q → ¬p) ∧ (p→ r ∨ q))| = 6.





ContohMisalkan φ adalah formula ¬ ((q → ¬p) ∧ (p→ r ∨ q)). Tinggi dari φ adalah1 + 4 = 5 dan |φ| =

|¬ ((q → ¬p) ∧ (p→ r ∨ q))| = 6.





ContohMisalkan φ adalah formula ¬ ((q → ¬p) ∧ (p→ r ∨ q)). Tinggi dari φ adalah1 + 4 = 5 dan |φ| = |¬ ((q → ¬p) ∧ (p→ r ∨ q))| = 6.


Bahasan








Semantik Operator ↑

Operator ↑Apabila p dan q merupakan proposisi, maka p ↑ q juga merupakan proposisi.Formula p ↑ q dibaca p nand q. Formula ini bernilai salah tepat ketika p dan qbernilai benar. Tabel kebenaran dari p ↑ q adalah:

p q p ↑ qT T FT F TF T TF F T

CatatanBeberapa buku juga memakai notasi p | q, simbol | disebut sebagai Sheffer stroke.Perhatikan bahwa p ↑ q ≡ ¬ (p ∧ q).





Catatan

Beberapa buku juga memakai notasi p | q, simbol | disebut sebagai Sheffer stroke.Perhatikan bahwa p ↑ q ≡ ¬ (p ∧ q).





CatatanBeberapa buku juga memakai notasi p | q, simbol | disebut sebagai Sheffer stroke.Perhatikan bahwa p ↑ q ≡ ¬ (p ∧ q).


Semantik Operator ↓

Operator ↓Apabila p dan q merupakan proposisi, maka p ↓ q juga merupakan proposisi.Formula p ↓ q dibaca p nor q. Formula ini bernilai benar tepat ketika p dan qbernilai salah. Tabel kebenaran dari p ↓ q adalah:

p q p ↓ qT T FT F FF T FF F T

CatatanSimbol ↓ disebut sebagai Peirce arrow. Perhatikan bahwa p ↓ q ≡ ¬ (p ∨ q).





Catatan

Simbol ↓ disebut sebagai Peirce arrow. Perhatikan bahwa p ↓ q ≡ ¬ (p ∨ q).





CatatanSimbol ↓ disebut sebagai Peirce arrow. Perhatikan bahwa p ↓ q ≡ ¬ (p ∨ q).


Semantik Operator ←

Operator ←Apabila p dan q merupakan proposisi, maka p← q juga merupakan proposisi.Formula p← q dibaca p bila q (p follows from q, p if q). Formula ini bernilaisalah tepat ketika p bernilai salah dan q bernilai benar. Tabel kebenaran darip← q adalah:

p q p← qT T TT F TF T FF F T

CatatanSimbol ← disebut sebagai implikasi-balik (reverse-implication). Perhatikan bahwap← q ≡ q → p.





Catatan

Simbol ← disebut sebagai implikasi-balik (reverse-implication). Perhatikan bahwap← q ≡ q → p.





CatatanSimbol ← disebut sebagai implikasi-balik (reverse-implication). Perhatikan bahwap← q ≡ q → p.


Semantik Operator 6→

Operator 6→Apabila p dan q merupakan proposisi, maka p 6→ q juga merupakan proposisi.Formula p 6→ q dibaca p tidak mengakibatkan q. Formula ini bernilai benar tepatketika p bernilai benar dan q bernilai salah. Tabel kebenaran dari p 6→ q adalah:

p q p 6→ qT T FT F TF T FF F F

CatatanPerhatikan bahwa p 6→ q ≡ ¬ (p→ q).





Catatan

Perhatikan bahwa p 6→ q ≡ ¬ (p→ q).





CatatanPerhatikan bahwa p 6→ q ≡ ¬ (p→ q).


Semantik Operator 6←

Operator 6←Apabila p dan q merupakan proposisi, maka p 6← q juga merupakan proposisi.Formula p 6← q dibaca p tidak diakibatkan oleh q. Formula ini bernilai benar tepatketika p bernilai salah dan q bernilai benar. Tabel kebenaran dari p 6← q adalah:

p q p 6← qT T FT F FF T TF F F

CatatanPerhatikan bahwa p 6← q ≡ ¬ (p← q).





Catatan

Perhatikan bahwa p 6← q ≡ ¬ (p← q).





CatatanPerhatikan bahwa p 6← q ≡ ¬ (p← q).


Interpretasi

InterpretasiInterpretasi dari suatu formula logika proposisi adalah pemberian nilai kebenaranterhadap proposisi tersebut. Proposisi yang ditinjau dapat berupa proposisimajemuk. Untuk proposisi atom, interpretasi merupakan pemetaan antara suatuvariabel proposisi terhadap nilai kebenarannya. Interpretasi dilambangkan dengansimbol I, J , I1, I2, . . . , .

Untuk setiap formula φ, interpretasi dari φ dapat ditulis dengan I (φ) atau φI .Interpretasi dapat dipandang dari himpunan seluruh well-formed formula kehimpunan {T,F}. Misalkan F = {φ : φ adalah well-formed formula}, maka

I : F→ {T,F}: φ 7→ I (φ) .

CatatanKetika meninjau semantik dari formula, biasanya digunakan notasi T dan F, atauB dan S, atau 1 dan 0.


Penentuan Interpretasi/ Semantik untuk Formula MajemukPentuan Interpretasi/ Semantik untuk formula majemuk dapat dilakukan secararekursif/ melalui induksi struktural sebagai berikut.

Aturan Semantik Logika ProposisiMisalkan φ adalah sebuah formula dan I adalah interpretasi yang terdefinisi untuksetiap proposisi atom yang muncul di φ. Interpretasi untuk φ didefinisikan sebagaiberikut

Jika φ = p (suatu proposisi atom), maka I (φ) = I (p), dan nilainya sesuaidengan definisi I untuk proposisi atom p yang bersesuaian.

Jika φ = >, maka I (>) = T = B = 1. Kemudian jika φ = ⊥, makaI (⊥) = F = S = 0.

Jika φ = ¬ψ, untuk suatu formula ψ, makaI (φ) = I (¬ψ) = ¬I (ψ) =

{T, jika I (ψ) = FF, jika I (ψ) = T

Jika φ = ψ ~ η, untuk suatu formula ψ dan η, serta suatu operator biner ~,maka I (φ) = I (ψ ~ η) = I (ψ)~ I (η). Penentukan nilai I (ψ)~ I (η)ditentukan dengan konvensi tabel kebenaran yang telah dijelaskansebelumnya maupun di perkuliahan Logika Matematika.


Operator Uner

PermasalahanDiberikan proposisi p. Ada berapa operator uner • berbeda yang dapatdidefinisikan sehingga •p memberikan hasil yang berbeda?

p •1 •2 •3 •4T T F T FF F T T F

Karena I (p) ∈ {T,F}, maka tabel di atas menyatakan bahwa terdapat 4 operatoruner berbeda yang dapat didefinsikan dalam logika proposisi. Operator •1dinamakan operator identitas, operator •2 dinamakan operator negasi (ditulis ¬atau ∼), operator •3 dinamakan proyeksi ke T, dan operator •4 dinamakanproyeksi ke F.


Operator Uner


p •1 •2 •3 •4T T F T FF F T T F

Karena I (p) ∈ {T,F}, maka tabel di atas menyatakan bahwa terdapat 4 operatoruner berbeda yang dapat didefinsikan dalam logika proposisi.

Operator •1dinamakan operator identitas, operator •2 dinamakan operator negasi (ditulis ¬atau ∼), operator •3 dinamakan proyeksi ke T, dan operator •4 dinamakanproyeksi ke F.


Operator Uner


p •1 •2 •3 •4T T F T FF F T T F

Karena I (p) ∈ {T,F}, maka tabel di atas menyatakan bahwa terdapat 4 operatoruner berbeda yang dapat didefinsikan dalam logika proposisi. Operator •1dinamakan operator identitas, operator •2 dinamakan operator negasi (ditulis ¬atau ∼), operator •3 dinamakan proyeksi ke T, dan operator •4 dinamakanproyeksi ke F.


Operator Biner

PermasalahanDiberikan proposisi p dan q. Ada berapa operator biner ◦ berbeda yang dapatdidefinisikan sehingga p ◦ q memberikan hasil yang berbeda?

p q ◦1 ◦2 ◦3 ◦4 ◦5 ◦6 ◦7 ◦8 ◦9 ◦10 ◦11T T T T T T F T T F T F FT F T T T F T T F F F T TF T T T F T T F F T T F TF F T F T T T F T T F T F

p q ◦12 ◦13 ◦14 ◦15 ◦16T T F F F T FT F F F T F FF T F T F F FF F T F F F F

Perhatikan bahwa ◦2 : ∨, ◦3 :←, ◦4 :→, ◦5 :↑, ◦7 :↔, ◦11 : ⊕, ◦12 :↓, ◦13 :6←,◦14 :6→, ◦15 : ∧.


Operator Biner




Perhatikan bahwa

◦2 : ∨, ◦3 :←, ◦4 :→, ◦5 :↑, ◦7 :↔, ◦11 : ⊕, ◦12 :↓, ◦13 :6←,◦14 :6→, ◦15 : ∧.


Operator Biner




Perhatikan bahwa ◦2 : ∨, ◦3 :←, ◦4 :→, ◦5 :↑, ◦7 :↔, ◦11 : ⊕, ◦12 :↓, ◦13 :6←,◦14 :6→, ◦15 : ∧.


Sifat-sifat Formula Berdasarkan Semantiknya

DefinisiMisalkan φ adalah sebuah formula logika proposisi:

1 formula φ dikatakan absah (valid) atau tautologi apabila φ selalu bernilaibenar untuk setiap interpretasi I

2 formula φ dikatakan terpenuhi (satisfiable) apabila φ dapat bernilai benaruntuk suatu interpretasi I

3 formula φ dikatakan kontradiksi (contradictory) apabila φ selalu bernilaisalah untuk setiap interpretasi I

4 formula φ dikatakan tersalahkan (falsifiable) apabila φ dapat bernilai salahuntuk suatu interpretasi I

5 formula φ dikatakan kontingensi (contingency) apabila φ bukan formula yangbersifat absah dan bukan pula formula yang bersifat kontradiksi.


Koleksi Formula yang KonsistenMisalkan Φ = {φ1, φ2, . . . , φn} adalah suatu koleksi/ kumpulan formula. Koleksiformula Φ dikatakan konsisten (consistent) bila terdapat suatu interpretasi I yangmengakibatkan

I (φ1) = I (φ2) = · · · = I (φn) = T.

Apabila hal di atas dipenuhi, maka kita dapat menuliskan I |= Φ.

Pernyataan bahwa koleksi formula {φ1, φ2, . . . , φn} konsisten setara denganmengatakan bahwa formula yang merupakan konjungsi dari

φ1 ∧ φ2 ∧ · · · ∧ φn

bersifat terpenuhi (satisfiable). Ketika hal ini terjadi, maka kita juga dapatmenuliskan I |= φ1 ∧ φ2 ∧ · · · ∧ φn.


Masalah Keabsahan dan Keterpenuhan

Masalah Keabsahan (Validity Problem)Diberikan suatu formula logika proposisi φ. Apakah φ bersifat absah (valid)?

Masalah Keterpenuhan (Satisfiability Problem)Diberikan suatu formula logika proposisi φ. Apakah φ bersifat terpenuhi(satisfiable)?

Permasalahan

Menurut Anda, mana yang lebih sulit ditentukan, keabsahan atau keterpenuhansuatu formula?


Masalah Keabsahan dan Keterpenuhan

Masalah Keabsahan (Validity Problem)Diberikan suatu formula logika proposisi φ. Apakah φ bersifat absah (valid)?

Masalah Keterpenuhan (Satisfiability Problem)Diberikan suatu formula logika proposisi φ. Apakah φ bersifat terpenuhi(satisfiable)?

PermasalahanMenurut Anda, mana yang lebih sulit ditentukan, keabsahan atau keterpenuhansuatu formula?


Hubungan Valid-Kontradiksi

TeoremaMisalkan φ adalah sebuah formula logika proposisi. Formula φ absah (valid) jikadan hanya jika ¬φ kontradiksi.

Bukti

Perhatikan bahwa

φ absah jikka I (φ) = T untuk setiap interpretasi Ijikka I (¬φ) = F untuk setiap intepretasi Ijikka ¬φ kontradiksi.

�




BuktiPerhatikan bahwa

φ absah jikka I (φ) = T untuk setiap interpretasi I

jikka I (¬φ) = F untuk setiap intepretasi Ijikka ¬φ kontradiksi.

�





φ absah jikka I (φ) = T untuk setiap interpretasi Ijikka I (¬φ) = F untuk setiap intepretasi I

jikka ¬φ kontradiksi.

�





φ absah jikka I (φ) = T untuk setiap interpretasi Ijikka I (¬φ) = F untuk setiap intepretasi Ijikka ¬φ kontradiksi.

�


Hubungan Satisfiable-Falsifiable

TeoremaMisalkan φ adalah sebuah formula logika proposisi. Formula φ terpenuhi(satisfiable) jika dan hanya jika ¬φ tersalahkan (falsifiable).

Bukti

Perhatikan bahwa

φ terpenuhi jikka I (φ) = T untuk suatu interpretasi Ijikka I (¬φ) = F untuk suatu intepretasi I

(interpretasi yang memberikan T untuk φ)jikka ¬φ tersalahkan.

�





φ terpenuhi jikka I (φ) = T untuk suatu interpretasi I

jikka I (¬φ) = F untuk suatu intepretasi I(interpretasi yang memberikan T untuk φ)

jikka ¬φ tersalahkan.

�






(interpretasi yang memberikan T untuk φ)

jikka ¬φ tersalahkan.

�






(interpretasi yang memberikan T untuk φ)jikka ¬φ tersalahkan.

�


Hubungan Valid-Satisfiable

TeoremaMisalkan φ adalah sebuah formula logika proposisi. Formula φ terpenuhi(satisfiable) jika dan hanya jika ¬φ tidak absah (tidak valid).

Bukti

Perhatikan bahwa


(interpretasi yang memberikan T untuk φ)jikka ¬φ tidak absah

�

AkibatMisalkan φ adalah sebuah formula logika proposisi. Formula φ absah (valid) jikadan hanya jika ¬φ tidak terpenuhi.





φ terpenuhi jikka I (φ) = T untuk suatu interpretasi I

jikka I (¬φ) = F untuk suatu intepretasi I(interpretasi yang memberikan T untuk φ)

jikka ¬φ tidak absah

�







(interpretasi yang memberikan T untuk φ)

jikka ¬φ tidak absah

�







(interpretasi yang memberikan T untuk φ)jikka ¬φ tidak absah

�



NP-Completeness dari Satisfiability Problem

PermasalahanDiberikan suatu formula logika proposisi φ, apakah terdapat suatu algoritma yangcukup efisien untuk memeriksa apakah φ bersifat terpenuhi (satisfiable)?

Misalkan φ adalah suatu formula logika proposisi yang memuat n proposisi atomberbeda p1, p2, . . . , pn. Terdapat 2n kombinasi berbeda untuk nilai dariI (p1) , I (p2) , . . . , I (pn). Dalam kasus terburuk, kita harus memeriksa seluruh2n kombinasi ini untuk memeriksa keterpenuhan (satisfiability) dari φ.

NP-Completeness dari Satisfiability ProblemMasalah keterpenuhan (satisfiability problem) adalah masalah NP-Complete.Hingga saat ini belum ditemukan algoritma yang efisien untuk memeriksaketerpenuhan dari φ. Jika ada algoritma yang efisien untuk memeriksaketerpenuhan dari φ (untuk sembarang φ), maka algoritma tersebut secarateoretis dapat dimodifikasi untuk memecahkan masalah NP-Complete lain.

Catatan: Kata “efisien”berarti bahwa kompleksitas running time algoritmatersebut adalah sub-eksponesial.




Misalkan φ adalah suatu formula logika proposisi yang memuat n proposisi atomberbeda p1, p2, . . . , pn. Terdapat 2n kombinasi berbeda untuk nilai dariI (p1) , I (p2) , . . . , I (pn).

Dalam kasus terburuk, kita harus memeriksa seluruh2n kombinasi ini untuk memeriksa keterpenuhan (satisfiability) dari φ.






Misalkan φ adalah suatu formula logika proposisi yang memuat n proposisi atomberbeda p1, p2, . . . , pn. Terdapat 2n kombinasi berbeda untuk nilai dariI (p1) , I (p2) , . . . , I (pn). Dalam kasus terburuk, kita harus memeriksa seluruh2n kombinasi ini untuk memeriksa keterpenuhan (satisfiability) dari φ.




Konsekuensi Logis dan Kesetaraan Logika

DefinisiMisalkan φ dan ψ adalah dua formula logika proposisi:Formula φ dan ψ dikatakan setara atau ekuivalen (logically equivalent) jikaformula

φ↔ ψ

merupakan tautologi. Hal ini dituliskan dengan φ ≡ ψ atau φ⇔ ψ.Formula ψ dikatakan sebagai konsekuensi logis (logical consequence) dari φ jikaformula

φ→ ψ

merupakan tautologi. Hal ini dituliskan dengan φ⇒ ψ.


Adequate Set of Connectives

Adequate Set of ConnectivesAdequate set of connectives (ASC) atau adequate set of operators (ASO) padalogika proposisi adalah himpunan operator logika O yang memenuhi sifat: semuaformula logika proposisi yang menggunakan operator lain dapat dinyatakan hanyadengan memakai operator logika yang terdapat pada O.

Sebagai contoh himpunan O1 = {¬,∧,∨,⊕,→,↔} adalah ASC, demikian pulahalnya dengan O2 = {¬,∧,∨,→} (karena ⊕ dan ↔ dapat dinyatakan hanyadengan memakai operator logika pada O2). Lebih jauh, dengan ekuivalensiφ→ ψ ≡ ¬φ ∨ ψ, maka O3 = {¬,∧,∨} juga merupakan ASC.Himpunan-himpunan operator berikut juga merupakan ASC

{¬,∧} , {¬,∨} , {¬,→}

Permasalahan

Apakah mungkin terdapat ASC yang hanya memuat satu operator saja? Jika ya,operator apakah itu? Apakah operatornya tunggal?


Adequate Set of Connectives

Adequate Set of ConnectivesAdequate set of connectives (ASC) atau adequate set of operators (ASO) padalogika proposisi adalah himpunan operator logika O yang memenuhi sifat: semuaformula logika proposisi yang menggunakan operator lain dapat dinyatakan hanyadengan memakai operator logika yang terdapat pada O.

Sebagai contoh himpunan O1 = {¬,∧,∨,⊕,→,↔} adalah ASC, demikian pulahalnya dengan O2 = {¬,∧,∨,→} (karena ⊕ dan ↔ dapat dinyatakan hanyadengan memakai operator logika pada O2). Lebih jauh, dengan ekuivalensiφ→ ψ ≡ ¬φ ∨ ψ, maka O3 = {¬,∧,∨} juga merupakan ASC.Himpunan-himpunan operator berikut juga merupakan ASC

{¬,∧} , {¬,∨} , {¬,→}

PermasalahanApakah mungkin terdapat ASC yang hanya memuat satu operator saja? Jika ya,operator apakah itu? Apakah operatornya tunggal?


TeoremaMisalkan ~ adalah sembarang operator logika proposisi (operator boolean) unermaupun biner. Operasi yang melibatkan ~ dapat dinyatakan hanya denganmemakai operator ↑ saja atau operator ↓ saja.

Bukti

Latihan, yang harus dicari dan dibuktikan adalah cara menyatakan ¬φ, φ ∧ ψ,φ ∨ ψ, φ⊕ ψ, φ→ ψ, maupun φ↔ ψ dengan memakai operator ↑ saja atauoperator ↓ saja.

TeoremaJika ~ adalah operator logika proposisi (operator boolean) yang dapatmenyatakan semua operasi yang dilakukan semua operator logika proposisi yanglain, maka ~ adalah operator ↑ atau operator ↓.

BuktiLihat Teorema 2.23 di buku Mathematical Logic for Computer Science, M.Ben-Ari.



BuktiLatihan, yang harus dicari dan dibuktikan adalah cara menyatakan ¬φ, φ ∧ ψ,φ ∨ ψ, φ⊕ ψ, φ→ ψ, maupun φ↔ ψ dengan memakai operator ↑ saja atauoperator ↓ saja.

Teorema

Jika ~ adalah operator logika proposisi (operator boolean) yang dapatmenyatakan semua operasi yang dilakukan semua operator logika proposisi yanglain, maka ~ adalah operator ↑ atau operator ↓.




BuktiLatihan, yang harus dicari dan dibuktikan adalah cara menyatakan ¬φ, φ ∧ ψ,φ ∨ ψ, φ⊕ ψ, φ→ ψ, maupun φ↔ ψ dengan memakai operator ↑ saja atauoperator ↓ saja.

TeoremaJika ~ adalah operator logika proposisi (operator boolean) yang dapatmenyatakan semua operasi yang dilakukan semua operator logika proposisi yanglain, maka ~ adalah operator ↑ atau operator ↓.



Algoritma Penentuan Interpretasi untuk Proposisi Majemuk

Algoritma penentuan intepretasi untuk proposisi majemuk dapat dikonstruksisecara rekursif dengan melihat struktur formula yang mungkin. Untukmempersingkat penulisan algoritma penentuan interpretasi ini, kita akanmengasumsikan bahwa masukan (input) dari algoritma berupa formula yanghanya memakai operator ¬, ∧, ∨, dan → saja.

Selanjutnya masukan dari algoritma juga diasumsikan berbentuk FPE. Hal inibertujuan agar intepretasi dari formula yang memakai operator logika yangbersifat asosiatif dapat ditentukan secara deterministik.


Algoritma Penentuan InterpretasiMasukan: φ yang berada dalam bentuk FPE dan hanya memuat operator ¬, ∧,∨, dan → saja.Keluaran: I (φ) yang nilainya hanya dua kemungkinan, yaitu T atau F.function I (φ)1 begin function2 case3 φ is atomic proposition p: return I (p)4 φ is ¬ψ: return NEG (I (ψ))5 φ is ψ1 ∧ ψ2: return CONJ (I (ψ1) , I (ψ2))6 φ is ψ1 ∨ ψ2: return DISJ (I (ψ1) , I (ψ2))7 φ is ψ1 → ψ2: return IMPL (I (ψ1) , I (ψ2))8 end case9 end function

Fungsi NEG, CONJ, DISJ, dan IMPL berturut-turut dikonstruksi berdasarkan aturansemantik untuk ¬, ∧, ∨, dan →.


Fungsi NEGfunction NEG (I (ψ))1 begin function2 if I (ψ) = T then3 return F4 else5 return T6 end function

Fungsi CONJfunction CONJ (I (ψ1) , I (ψ2))1 begin function2 if I (ψ1) = T AND I (ψ2) = T then3 return T4 else5 return F6 end function


Fungsi DISJfunction DISJ (I (ψ1) , I (ψ2))1 begin function2 if I (ψ1) = F AND I (ψ2) = F then3 return F4 else5 return T6 end function

Fungsi IMPLfunction IMPL (I (ψ1) , I (ψ2))1 begin function2 if I (ψ1) = T AND I (ψ2) = F then3 return F4 else5 return T6 end function


Sebagai contoh, langkah-langkah penentuan interprertasi dari formulaφ := ((p ∨ q) ∨ r)→ ((p ∨ q) ∧ ¬s) bila diberikan I (p) = T, I (q) = F,I (r) = T, I (s) = F dengan algoritma yang telah dijelaskan adalah sebagaiberikut

I (φ)

=

I (((p ∨ q) ∨ r)→ ((p ∨ q) ∧ ¬s))= IMPL (I ((p ∨ q) ∨ r) , I ((p ∨ q) ∧ ¬s))= IMPL (DISJ (I (p ∨ q) , I (r)) , CONJ (I (p ∨ q) , I (¬s)))= IMPL (DISJ (DISJ (I (p) , I (q)) , I (r)) , CONJ (DISJ (I (p) , I (q)) , I (¬s)))= IMPL (DISJ (DISJ (I (p) , I (q)) , I (r)) , CONJ (DISJ (I (p) , I (q)) , NEG (I (s))))

= IMPL (DISJ (DISJ (T,F) ,T) , CONJ (DISJ (T,F) ,T))

= IMPL (DISJ (T,T) , CONJ (T,T))

= IMPL (T,T) = T.



I (φ)

= I (((p ∨ q) ∨ r)→ ((p ∨ q) ∧ ¬s))=

IMPL (I ((p ∨ q) ∨ r) , I ((p ∨ q) ∧ ¬s))= IMPL (DISJ (I (p ∨ q) , I (r)) , CONJ (I (p ∨ q) , I (¬s)))= IMPL (DISJ (DISJ (I (p) , I (q)) , I (r)) , CONJ (DISJ (I (p) , I (q)) , I (¬s)))= IMPL (DISJ (DISJ (I (p) , I (q)) , I (r)) , CONJ (DISJ (I (p) , I (q)) , NEG (I (s))))



= IMPL (T,T) = T.



I (φ)

= I (((p ∨ q) ∨ r)→ ((p ∨ q) ∧ ¬s))= IMPL (I ((p ∨ q) ∨ r) , I ((p ∨ q) ∧ ¬s))=

IMPL (DISJ (I (p ∨ q) , I (r)) , CONJ (I (p ∨ q) , I (¬s)))= IMPL (DISJ (DISJ (I (p) , I (q)) , I (r)) , CONJ (DISJ (I (p) , I (q)) , I (¬s)))= IMPL (DISJ (DISJ (I (p) , I (q)) , I (r)) , CONJ (DISJ (I (p) , I (q)) , NEG (I (s))))



= IMPL (T,T) = T.



I (φ)

= I (((p ∨ q) ∨ r)→ ((p ∨ q) ∧ ¬s))= IMPL (I ((p ∨ q) ∨ r) , I ((p ∨ q) ∧ ¬s))= IMPL (DISJ (I (p ∨ q) , I (r)) , CONJ (I (p ∨ q) , I (¬s)))=

IMPL (DISJ (DISJ (I (p) , I (q)) , I (r)) , CONJ (DISJ (I (p) , I (q)) , I (¬s)))= IMPL (DISJ (DISJ (I (p) , I (q)) , I (r)) , CONJ (DISJ (I (p) , I (q)) , NEG (I (s))))



= IMPL (T,T) = T.



I (φ)

= I (((p ∨ q) ∨ r)→ ((p ∨ q) ∧ ¬s))= IMPL (I ((p ∨ q) ∨ r) , I ((p ∨ q) ∧ ¬s))= IMPL (DISJ (I (p ∨ q) , I (r)) , CONJ (I (p ∨ q) , I (¬s)))= IMPL (DISJ (DISJ (I (p) , I (q)) , I (r)) , CONJ (DISJ (I (p) , I (q)) , I (¬s)))=

IMPL (DISJ (DISJ (I (p) , I (q)) , I (r)) , CONJ (DISJ (I (p) , I (q)) , NEG (I (s))))



= IMPL (T,T) = T.



I (φ)

= I (((p ∨ q) ∨ r)→ ((p ∨ q) ∧ ¬s))= IMPL (I ((p ∨ q) ∨ r) , I ((p ∨ q) ∧ ¬s))= IMPL (DISJ (I (p ∨ q) , I (r)) , CONJ (I (p ∨ q) , I (¬s)))= IMPL (DISJ (DISJ (I (p) , I (q)) , I (r)) , CONJ (DISJ (I (p) , I (q)) , I (¬s)))= IMPL (DISJ (DISJ (I (p) , I (q)) , I (r)) , CONJ (DISJ (I (p) , I (q)) , NEG (I (s))))

=

IMPL (DISJ (DISJ (T,F) ,T) , CONJ (DISJ (T,F) ,T))


= IMPL (T,T) = T.



I (φ)



=

IMPL (DISJ (T,T) , CONJ (T,T))

= IMPL (T,T) = T.



I (φ)




=

IMPL (T,T) = T.



I (φ)




= IMPL (T,T) = T.


Kompleksitas Algoritma Penentuan Interpretasi

Lamanya running time algoritma penentuan interpretasi dari suatu formula φdipengaruhi oleh tinggi dan ukuran dari formula tersebut.

Running time algoritma jelas dipengaruhi oleh banyaknya panggilan rekursif untukfunction I. Banyaknya panggilan rekursif untuk function I dipengaruhi olehbanyaknya operator pada φ (termasuk multiplisitasnya).

Kompleksitas running time algoritma penentuan interpretasi dapat diukurberdasarkan ukuran formula yang menjadi masukan (input).

TeoremaUntuk setiap well-formed formula φ dan interpretasi I yang terdefinisi untuksetiap proposisi atom yang muncul pada φ, nilai dari I (φ) dapat ditentukandalam waku T (|φ|) = O (|φ|).

Teorema di atas menyatakan bahwa kompleksitas waktu penentuan interpretasiuntuk suatu formula logika proposisi adalah linier terhadap ukuran formulatersebut.






Teorema

Untuk setiap well-formed formula φ dan interpretasi I yang terdefinisi untuksetiap proposisi atom yang muncul pada φ, nilai dari I (φ) dapat ditentukandalam waku T (|φ|) = O (|φ|).







TeoremaUntuk setiap well-formed formula φ dan interpretasi I yang terdefinisi untuksetiap proposisi atom yang muncul pada φ, nilai dari I (φ) dapat ditentukandalam waku T (|φ|) = O (|φ|).



Bahasan








Konsistensi Spesifikasi Sistem dan Keterpenuhan

Misalkan terdapat suatu sistem dengan n buah spesfikasi yang masing-masingspesifikasinya dapat dinyatakan dalam formula logika proposisi, yaituφ1, φ2, . . . , φn Sistem tersebut konsisten bila

φspec = φ1 ∧ φ2 ∧ · · · ∧ φn =

n∧i=1

φi

merupakan formula yang terpenuhi (satisifiable).

Hal ini berarti terdapat suatuinterpretasi I yang memenuhi

I(φspec

)= T yang setara dengan

I (φi) = T untuk setiap 1 ≤ i ≤ n.

Hal ini juga berarti himpunan Φspec = {φ1, φ2, . . . , φn} bersifat konsisten.


Konsistensi Spesifikasi Sistem dan Keterpenuhan

Misalkan terdapat suatu sistem dengan n buah spesfikasi yang masing-masingspesifikasinya dapat dinyatakan dalam formula logika proposisi, yaituφ1, φ2, . . . , φn Sistem tersebut konsisten bila

φspec = φ1 ∧ φ2 ∧ · · · ∧ φn =

n∧i=1

φi

merupakan formula yang terpenuhi (satisifiable). Hal ini berarti terdapat suatuinterpretasi I yang memenuhi

I(φspec

)= T yang setara dengan

I (φi) = T untuk setiap 1 ≤ i ≤ n.

Hal ini juga berarti himpunan Φspec = {φ1, φ2, . . . , φn} bersifat konsisten.


Contoh 1

Masalah Konsistensi Spesifikasi Sistem 1Apakah spesifikasi sistem berikut konsisten atau tidak:

1 Ketika system software di-upgrade, user tidak dapat mengakses file system;2 Jika user dapat mengakses file system, maka user dapat menyimpan file baru;3 Jika user tidak dapat menyimpan file baru, maka system software tidaksedang di-upgrade.

Misalkan p : “system software sedang di-upgrade”, q : “user dapat mengakses filesystem”, dan r : “user dapat menyimpan file baru”. Spesfikasi sistem adalahφspec = φ1 ∧ φ2 ∧ φ3 dan φ1 := p→ ¬q, φ2 := q → r, dan φ3 := ¬r → s.


Tinjau bahwa dengan memilih I (p) = F, I (q) = F, dan I (r) = T diperoleh

I (φ1) = I (p→ ¬q) = F→ T = T

I (φ2) = I (q → r) = F→ T = T

I (φ3) = I (¬r → ¬p) = F→ T = T

Jadi dapat disimpulkan bahwa spesifikasi sistem bersifat konsisten.


Contoh 2

Masalah Konsistensi Spesifikasi Sistem 2Apakah spesifikasi sistem berikut konsisten atau tidak:

1 Sistem berada dalam state multiuser jika dan hanya jika beroperasi secaranormal;

2 Jika sistem beroperasi secara normal, maka kernel sistem sedang berfungsi;3 Kernel sistem tidak sedang berfungsi atau sistem dalam interrupt mode;4 Sistem tidak berada dalam interrupt mode.

Misalkan p : “sistem berada dalam state multiuser”, q : “sistem beroperasi secaranormal”, r : “kernel sedang berfungsi”, dan s : “sistem dalam interrupt mode”.Spesifikasi sistem adalah φspec = φ1 ∧ φ2 ∧ φ3 ∧ φ4 dengan φ1 := p↔ q,φ2 := q → r, φ3 := ¬r ∨ s, φ4 := ¬s.


Tinjau bahwa dengan memilih I (s) = F, I (r) = F, I (q) = F, dan I (p) = Fdiperoleh

I (φ1) = I (p↔ q) = F↔ F = T

I (φ2) = I (q → r) = F→ F = T

I (φ3) = I (¬r ∨ s) = ¬F ∨ F = T

I (φ4) = I (¬s) = ¬F = T

Jadi dapat disimpulkan bahwa sistem konsisten.


Bahasan








Literal

DefinisiLiteral adalah sebuah proposisi atom atau sebuah negasi dari suatu proposisiatom. Suatu literal dinotasikan dengan λ atau L.

Formula-formula: p, ¬p, q, ¬q adalah contoh-contoh literal. Formula ¬¬p bukanliteral karena bukan merupakan proposisi atom atau negasi dari suatu proposisiatom, meskipun secara semantik ¬¬p ≡ p.


TeoremaDisjungsi literal-literal

∨ni=1 λi = λ1 ∨ λ2 ∨ · · · ∨ λn absah (valid) jikka terdapat

1 ≤ i < j ≤ n yang memenuhi λi ≡ ¬λj .

BuktiLatihan.

TeoremaKonjungsi literal-literal

∧ni=1 λi = λ1 ∧ λ2 ∧ · · · ∧ λn kontradiksi jikka terdapat

1 ≤ i < j ≤ n yang memenuhi λi ≡ ¬λj

BuktiLatihan.


Bentuk Normal Negasi

Bentuk Normal Negasi (Negation Normal Form)Suatu formula φ dikatakan berada dalam bentuk normal negasi (negation normalform, NNF) bila seluruh negasi yang terdapat pada formula tersebut hanya munculdi depan proposisi atom. Biasanya syarat bentuk normal negasi diperkuat denganhanya memperbolehkan operator ¬, ∧, dan ∨ yang muncul pada formula φ.Dalam kondisi ini, BNF untuk NNF dijelaskan sebagai berikut

λ ::= p | ¬pφ ::= λ | φ ∧ φ | φ ∨ φ

Formula-formula p, ¬p, ¬p ∧ q, dan p ∨ ¬q adalah contoh-contoh formula yangberada dalam NNF. Formula ¬ (p ∨ ¬q), ¬¬p ∧ q, dan ¬p ∨ ¬ (q ∧ r) adalahcontoh-contoh formula yang tidak berada dalam NNF.


Konversi ke NNF

Untuk mengkonversi suatu formula ke dalam bentuk NNF, kita dapat melakukanhal-hal berikut:

1 Ubah formula dengan operator ⊕, →, dan ↔ ke dalam formula yang hanyamemakai operator ¬, ∧, dan ∨ saja dengan memanfaatkan ekuivalensiberikut: φ⊕ ψ ≡ (φ ∧ ¬ψ) ∨ (¬φ ∨ ψ), φ→ ψ ≡ ¬φ ∨ ψ, danφ↔ ψ ≡ (¬φ ∨ ψ) ∧ (φ ∨ ¬ψ).

2 Jika menemukan subformula dengan bentuk ¬ (φ ∧ ψ), maka subformulatersebut diubah ke dalam bentuk ¬φ ∨ ¬ψ. Kemudian jika menemukansubformula dengan bentuk ¬ (φ ∨ ψ), maka subformula tersebut diubah kedalam bentuk ¬φ ∧ ¬ψ.

3 Jika menemukan subformula dengan bentuk ¬¬φ, maka subformula tersebutdiubah ke dalam bentuk φ.


Sebagai contoh, formula φ := ¬ (p→ (q ∨ r))→ (p ∨ ¬ (q ∧ s)) dapat diubah kedalam NNF dengan langkah-langkah berikut

φ = ¬ (p→ (q ∨ r))→ (p ∨ ¬ (q ∧ s))≡

¬¬ (p→ (q ∨ r)) ∨ (p ∨ ¬ (q ∧ s))≡ (p→ (q ∨ r)) ∨ (p ∨ ¬ (q ∧ s))≡ (¬p ∨ (q ∨ r)) ∨ (p ∨ (¬q ∨ ¬s))≡ ¬p ∨ q ∨ r ∨ p ∨ ¬q ∨ ¬s≡ ¬p ∨ p ∨ q ∨ ¬q ∨ r ∨ ¬s≡ > ∨> ∨ r ∨ ¬s ≡ r ∨ ¬s.



φ = ¬ (p→ (q ∨ r))→ (p ∨ ¬ (q ∧ s))≡ ¬¬ (p→ (q ∨ r)) ∨ (p ∨ ¬ (q ∧ s))≡ (p→ (q ∨ r)) ∨ (p ∨ ¬ (q ∧ s))≡ (¬p ∨ (q ∨ r)) ∨ (p ∨ (¬q ∨ ¬s))≡ ¬p ∨ q ∨ r ∨ p ∨ ¬q ∨ ¬s≡

¬p ∨ p ∨ q ∨ ¬q ∨ r ∨ ¬s≡ > ∨> ∨ r ∨ ¬s ≡ r ∨ ¬s.



φ = ¬ (p→ (q ∨ r))→ (p ∨ ¬ (q ∧ s))≡ ¬¬ (p→ (q ∨ r)) ∨ (p ∨ ¬ (q ∧ s))≡ (p→ (q ∨ r)) ∨ (p ∨ ¬ (q ∧ s))≡ (¬p ∨ (q ∨ r)) ∨ (p ∨ (¬q ∨ ¬s))≡ ¬p ∨ q ∨ r ∨ p ∨ ¬q ∨ ¬s≡ ¬p ∨ p ∨ q ∨ ¬q ∨ r ∨ ¬s≡

> ∨> ∨ r ∨ ¬s ≡ r ∨ ¬s.



φ = ¬ (p→ (q ∨ r))→ (p ∨ ¬ (q ∧ s))≡ ¬¬ (p→ (q ∨ r)) ∨ (p ∨ ¬ (q ∧ s))≡ (p→ (q ∨ r)) ∨ (p ∨ ¬ (q ∧ s))≡ (¬p ∨ (q ∨ r)) ∨ (p ∨ (¬q ∨ ¬s))≡ ¬p ∨ q ∨ r ∨ p ∨ ¬q ∨ ¬s≡ ¬p ∨ p ∨ q ∨ ¬q ∨ r ∨ ¬s≡ > ∨> ∨ r ∨ ¬s ≡ r ∨ ¬s.


Algoritma Konversi ke NNF

Misalkan φ adalah formula yang hanya memuat operator ¬, ∧, ∨, dan → saja,maka kita dapat mengkonversi φ ke dalam bentuk NNF dengan memanfaatkanekuivalensi berikut:

¬¬φ ≡ φ¬ (φ ∨ ψ) ≡ ¬φ ∧ ψ¬ (φ ∧ ψ) ≡ ¬φ ∨ ¬ψ¬ (φ→ ψ) ≡ ¬ (¬φ ∨ ψ) ≡ φ ∧ ¬ψ

Selanjutnya masukan (input) dari algoritma juga diasumsikan berbentuk FPE. Halini bertujuan agar konversi dari formula yang memakai operator logika yangbersifat asosiatif dapat ditentukan secara deterministik.


Algoritma Konversi Ke NNFMasukan: φ yang berada dalam bentuk FPE dan hanya memuat operator ¬, ∧,∨, dan → saja.Keluaran: NNF (φ) yang berupa formula yang ekuivalen dengan φ dalam bentukNNF.function NNF (φ)1 begin function2 case3 φ is a literal λ: return φ4 φ is ¬¬ψ: return NNF (ψ)5 φ is ψ1 ∧ ψ2: return NNF (ψ1) ∧ NNF (ψ2)6 φ is ψ1 ∨ ψ2: return NNF (ψ1) ∨ NNF (ψ2)7 φ is ψ1 → ψ2: return NNF (ψ1)→ NNF (ψ2)8 φ is ¬ (ψ1 ∧ ψ2): return NNF (¬ψ1) ∨ NNF (¬ψ2)9 φ is ¬ (ψ1 ∨ ψ2): return NNF (¬ψ1) ∧ NNF (¬ψ2)10 φ is ¬ (ψ1 → ψ2): return NNF (ψ1) ∧ NNF (¬ψ2)11 end case12 end function


Sebagai contoh, langkah-langkah konversi ke NNF dari formulaφ := p ∨ ¬ (q ∧ r)→ ¬ (q ∧ r → s) dijelaskan sebagai berikut

NNF (φ)

=

NNF (p ∨ ¬ (q ∧ r)→ ¬ (q ∧ r → s))

= NNF (p ∨ ¬ (q ∧ r))→ NNF (¬ (q ∧ r → s))

= NNF (p) ∨ NNF (¬ (q ∧ r))→ NNF (q ∧ r) ∧ NNF (¬s)= (NNF (p) ∨ (NNF (¬q) ∨ NNF (¬r)))→ (NNF (q) ∧ NNF (r)) ∧ NNF (¬s)= (p ∨ (¬q ∨ ¬r))→ ((q ∧ r) ∧ ¬s)= (p ∨ ¬q ∨ ¬r)→ (q ∧ r ∧ ¬s)



NNF (φ)

= NNF (p ∨ ¬ (q ∧ r)→ ¬ (q ∧ r → s))

=

NNF (p ∨ ¬ (q ∧ r))→ NNF (¬ (q ∧ r → s))




NNF (φ)

= NNF (p ∨ ¬ (q ∧ r)→ ¬ (q ∧ r → s))

= NNF (p ∨ ¬ (q ∧ r))→ NNF (¬ (q ∧ r → s))

=

NNF (p) ∨ NNF (¬ (q ∧ r))→ NNF (q ∧ r) ∧ NNF (¬s)= (NNF (p) ∨ (NNF (¬q) ∨ NNF (¬r)))→ (NNF (q) ∧ NNF (r)) ∧ NNF (¬s)= (p ∨ (¬q ∨ ¬r))→ ((q ∧ r) ∧ ¬s)= (p ∨ ¬q ∨ ¬r)→ (q ∧ r ∧ ¬s)



NNF (φ)

= NNF (p ∨ ¬ (q ∧ r)→ ¬ (q ∧ r → s))

= NNF (p ∨ ¬ (q ∧ r))→ NNF (¬ (q ∧ r → s))

= NNF (p) ∨ NNF (¬ (q ∧ r))→ NNF (q ∧ r) ∧ NNF (¬s)=

(NNF (p) ∨ (NNF (¬q) ∨ NNF (¬r)))→ (NNF (q) ∧ NNF (r)) ∧ NNF (¬s)= (p ∨ (¬q ∨ ¬r))→ ((q ∧ r) ∧ ¬s)= (p ∨ ¬q ∨ ¬r)→ (q ∧ r ∧ ¬s)



NNF (φ)

= NNF (p ∨ ¬ (q ∧ r)→ ¬ (q ∧ r → s))

= NNF (p ∨ ¬ (q ∧ r))→ NNF (¬ (q ∧ r → s))

= NNF (p) ∨ NNF (¬ (q ∧ r))→ NNF (q ∧ r) ∧ NNF (¬s)= (NNF (p) ∨ (NNF (¬q) ∨ NNF (¬r)))→ (NNF (q) ∧ NNF (r)) ∧ NNF (¬s)=

(p ∨ (¬q ∨ ¬r))→ ((q ∧ r) ∧ ¬s)= (p ∨ ¬q ∨ ¬r)→ (q ∧ r ∧ ¬s)



NNF (φ)

= NNF (p ∨ ¬ (q ∧ r)→ ¬ (q ∧ r → s))

= NNF (p ∨ ¬ (q ∧ r))→ NNF (¬ (q ∧ r → s))



Kompleksitas Algoritma Konversi ke NNF

Lamanya running time algoritma konversi ke NNF dari suatu formula φdipengaruhi oleh tinggi dan ukuran dari formula tersebut.

Running time algoritma jelas dipengaruhi oleh banyaknya panggilan rekursif untukfungsi NNF. Banyaknya panggilan rekursif dipengaruhi oleh banyaknya operatorpada φ (termasuk multiplisitasnya).

Kompleksitas running time algoritma konversi ke NNF dapat diukur berdasarkanukuran formula yang menjadi masukan (input).

TeoremaUntuk setiap well-formed formula φ, formula NNF (φ) dapat diperoleh dari φ dalamwaku T (|φ|) = O (|φ|).

Teorema di atas menyatakan bahwa kompleksitas waktu konversi ke bentuk NNFuntuk suatu formula logika proposisi adalah linier terhadap ukuran formulatersebut.






Teorema

Untuk setiap well-formed formula φ, formula NNF (φ) dapat diperoleh dari φ dalamwaku T (|φ|) = O (|φ|).







TeoremaUntuk setiap well-formed formula φ, formula NNF (φ) dapat diperoleh dari φ dalamwaku T (|φ|) = O (|φ|).



Bahasan








Bentuk Normal Konjungtif

Bentuk Normal Konjungtif (Conjunctive Normal Form, CNF)Suatu formula φ dikatakan berada dalam bentuk normal konjungtif (conjunctivenormal form, CNF) apabila φ hanya boleh memuat operator ¬, ∧, dan ∨ saja,serta φ merupakan konjungsi dari satu atau lebih disjungsi literal. BNF untukCNF dijelaskan sebagai berikut:

λ ::= p | ¬pα ::= λ | λ ∨ αφ ::= α | φ ∧ α

Bentuk α (disjungsi dari satu atau lebih literal) biasa diistilahkan sebagai klausa(clause).


BNF dari CNF menyatakan bahwa suatu formula φ yang berada dalam CNFmemiliki bentuk sebagai berikut

φ = α1 ∧ α2 ∧ · · · ∧ αn

dan setiap αi untuk 1 ≤ i ≤ n berbentuk

αi = λi1 ∨ λi2 ∨ · · · ∨ λim

untuk suatu m.

Dengan terminologi yang telah diperkenalkan kita dapat mengatakan bahwa CNFadalah konjungsi dari beberapa klausa.


Contoh Formula dalam CNF

Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 =

α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 =

(p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 =

(¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 =

q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 =

α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 =

p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 =

¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 =

p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q

adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF.

Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p.

Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q.

Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s))

adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF.

Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,

sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam CNF dan bukan CNF)Formula φ1 = (p ∨ ¬q ∨ r) ∧ (¬p ∨ r) ∧ q dan φ2 = (p ∨ r) ∧ (¬p ∨ r) ∧ (p ∨ ¬r)adalah dua contoh formula yang berada dalam bentuk CNF. Pada φ1 kitamemiliki φ1 = α1 ∧ α2 ∧ α3 dengan α1 = (p ∨ ¬q ∨ r), α2 = (¬p ∨ r), danα3 = q. Masing-masing α1, α2, dan α3 adalah disjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = α1 ∧ α2 ∧ α3, dengan α1 = p ∨ r,α2 = ¬p ∨ r, dan α3 = p ∨ ¬r. Masing-masing α1, α2, dan α3 adalah disjungsidari satu atau lebih literal.Formula φ3 = ¬p, φ4 = p ∧ q, dan φ5 = p ∨ q adalah tiga contoh formula yangberada dalam bentuk CNF. Pada φ3 kita memiliki φ3 = α1 = λ11 = ¬p. Formulaφ4 adalah konjungsi α1 ∧ α2 dengan α1 = λ11 = p dan α2 = λ21 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∨ λ12 = p ∨ q.Formula φ6 = ¬ (p ∨ q), φ7 = ¬ (p ∧ q), φ8 = p ∨ (q ∧ r), danφ9 = p ∧ (q ∨ (¬r ∧ s)) adalah empat contoh formula yang tidak berada dalambentuk CNF. Pada φ6 dan φ7, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ8 dan φ9 disjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).


Bentuk Normal Disjungtif

Bentuk Normal Disjungtif (Disjunctive Normal Form, DNF)Suatu formula φ dikatakan berada dalam bentuk normal disjungtif (disjunctivenormal form, DNF) apabila φ hanya boleh memuat operator ¬, ∧, dan ∨ saja,serta φ merupakan disjungsi dari satu atau lebih konjungsi literal. BNF untukDNF dijelaskan sebagai berikut:

λ ::= p | ¬pβ ::= λ | λ ∧ βφ ::= β | φ ∨ β

Bentuk β (konjungsi dari satu atau lebih literal) biasa diistilahkan sebagai term.


BNF dari DNF menyatakan bahwa suatu formula φ yang berada dalam DNFmemiliki bentuk sebagai berikut

φ = β1 ∨ β2 ∨ · · · ∨ βn

dan setiap βi untuk 1 ≤ i ≤ n berbentuk

βi = λi1 ∧ λi2 ∧ · · · ∧ λim

untuk suatu m.

Dengan terminologi yang telah diperkenalkan kita dapat mengatakan bahwa DNFadalah disjungsi dari beberapa term.


Contoh Formula dalam DNF

Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 =

β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 =

(p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 =

(¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 =

q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 =

β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 =

p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 =

¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 =

p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q

adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF.

Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p.

Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q.

Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s))

adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF.

Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,

sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).



Contoh (Formula yang berada dalam DNF dan bukan DNF)Formula φ1 = (p ∧ ¬q ∧ r) ∨ (¬p ∧ r) ∨ q dan φ2 = (p ∧ r) ∨ (¬p ∧ r) ∨ (p ∧ ¬r)adalah dua contoh formula yang berada dalam bentuk DNF. Pada φ1 kitamemiliki φ1 = β1 ∨ β2 ∨ β3 dengan β1 = (p ∧ ¬q ∧ r), β2 = (¬p ∧ r), danβ3 = q. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu atau lebihliteral. Pada φ2 kita memiliki φ2 = β1 ∧ β2 ∧ β3, dengan β1 = p∧ r, β2 = ¬p∧ r,dan β3 = p ∧ ¬r. Masing-masing β1, β2, dan β3 adalah konjungsi dari satu ataulebih literal.Formula φ3 = ¬p, φ4 = p ∨ q, dan φ5 = p ∧ q adalah tiga contoh formula yangberada dalam bentuk DNF. Pada φ3 kita memiliki φ3 = β1 = λ11 = ¬p. Formulaα4 adalah disjungsi β1 ∨ β2 dengan β1 = λ11 = p dan β2 = λ12 = q. Kemudianpada formula φ5 kita memiliki φ5 = α1 = λ11 ∧ λ12 = p ∧ q.Formula φ5 = ¬ (p ∨ q), φ6 = ¬ (p ∧ q), φ7 = p ∧ (q ∨ r), danφ8 = p ∨ (q ∧ (¬r ∨ s)) adalah empat contoh formula yang tidak berada dalambentuk DNF. Pada φ5 dan φ6, negasi tidak berada di depan proposisi atom,sedangkan pada pada φ7 dan φ8 konjungsi tidak dikenakan pada literal (pada φ7subformula q ∧ r bukan literal, sedangkan pada φ8 subformula ¬r ∧ s bukanliteral).


Latihan (Bentuk CNF dan DNF)Periksa apakah formula-formula berikut termasuk dalam bentuk CNF, DNF, ataubukan keduanya.

1 (p ∧ ¬r) ∨ (¬p ∧ q)

DNF, bukan CNF

2 p ∨ (¬p ∧ q)

DNF, bukan CNF

3 (q ∨ ¬r) ∨ (¬p ∧ q)

DNF, bukan CNF

4 (p ∧ ¬p) ∨ (q ∧ ¬q) ∨ (r ∧ ¬r)

DNF, bukan CNF

5 (p ∧ ¬r) ∨ ¬ (¬p ∧ q)

bukan DNF, bukan CNF

6 (p ∧ ¬r) ∨ (p ∧ q ∧ ¬r) ∨ (¬p ∧ q)

DNF, bukan CNF

7 p ∧ ¬r ∨ (¬p ∧ q)

DNF, bukan CNF

8 p ∧ (q ∨ r)

CNF, bukan DNF

9 p ∨ (q ∧ r)

DNF, bukan CNF

10 ¬p

CNF dan DNF

11 p ∧ q ∧ r

CNF dan DNF

12 p ∨ q ∨ r

CNF dan DNF

13 p ∨ (q ∧ (r ∨ s)) ∨ t


14 p ∧ (q ∨ (r ∧ s)) ∧ t


Latihan (Bentuk CNF dan DNF)Periksa apakah formula-formula berikut termasuk dalam bentuk CNF, DNF, ataubukan keduanya.

1 (p ∧ ¬r) ∨ (¬p ∧ q) DNF, bukan CNF2 p ∨ (¬p ∧ q) DNF, bukan CNF3 (q ∨ ¬r) ∨ (¬p ∧ q) DNF, bukan CNF4 (p ∧ ¬p) ∨ (q ∧ ¬q) ∨ (r ∧ ¬r) DNF, bukan CNF5 (p ∧ ¬r) ∨ ¬ (¬p ∧ q) bukan DNF, bukan CNF6 (p ∧ ¬r) ∨ (p ∧ q ∧ ¬r) ∨ (¬p ∧ q) DNF, bukan CNF7 p ∧ ¬r ∨ (¬p ∧ q) DNF, bukan CNF8 p ∧ (q ∨ r) CNF, bukan DNF9 p ∨ (q ∧ r) DNF, bukan CNF10 ¬p CNF dan DNF11 p ∧ q ∧ r CNF dan DNF12 p ∨ q ∨ r CNF dan DNF13 p ∨ (q ∧ (r ∨ s)) ∨ t bukan DNF, bukan CNF14 p ∧ (q ∨ (r ∧ s)) ∧ t bukan DNF, bukan CNF

Hubungan Antara Formula dalam CNF dan DNFMisalkan φ adalah sebuah formula dalam bentuk CNF

φ = α1 ∧ α2 ∧ · · · ∧ αn,

dengan αi =

λi1 ∨ λi2 ∨ · · · ∨ λim, untuk suatu m. Maka

¬φ ≡ ¬ (α1 ∧ α2 · · · ∧ αn)

≡ ¬α1 ∨ ¬α2 ∨ · · · ∨ ¬αn

dan ¬αi ≡ ¬λim ∧ ¬λi2 ∧ · · · ∧ ¬λim, untuk suatu m. Perhatikan bahwa ¬φberada dalam DNF.

ContohMisalkan φ = (p ∨ q) ∧ (¬p ∨ r), jelas bahwa φ dalam CNF. Kita memiliki

¬φ ≡ ¬ ((p ∨ q) ∧ (¬p ∨ r))≡ ¬ (p ∨ q) ∨ ¬ (¬p ∨ r)≡ (¬p ∧ ¬q) ∨ (p ∧ ¬r) .

Jelas bahwa ¬φ dalam DNF.



φ = α1 ∧ α2 ∧ · · · ∧ αn,

dengan αi = λi1 ∨ λi2 ∨ · · · ∨ λim, untuk suatu m. Maka

¬φ ≡ ¬ (α1 ∧ α2 · · · ∧ αn)

≡

¬α1 ∨ ¬α2 ∨ · · · ∨ ¬αn



¬φ ≡ ¬ ((p ∨ q) ∧ (¬p ∨ r))≡ ¬ (p ∨ q) ∨ ¬ (¬p ∨ r)≡ (¬p ∧ ¬q) ∨ (p ∧ ¬r) .




φ = α1 ∧ α2 ∧ · · · ∧ αn,


¬φ ≡ ¬ (α1 ∧ α2 · · · ∧ αn)

≡ ¬α1 ∨ ¬α2 ∨ · · · ∨ ¬αn

dan ¬αi ≡

¬λim ∧ ¬λi2 ∧ · · · ∧ ¬λim, untuk suatu m. Perhatikan bahwa ¬φberada dalam DNF.


¬φ ≡ ¬ ((p ∨ q) ∧ (¬p ∨ r))≡ ¬ (p ∨ q) ∨ ¬ (¬p ∨ r)≡ (¬p ∧ ¬q) ∨ (p ∧ ¬r) .




φ = α1 ∧ α2 ∧ · · · ∧ αn,


¬φ ≡ ¬ (α1 ∧ α2 · · · ∧ αn)

≡ ¬α1 ∨ ¬α2 ∨ · · · ∨ ¬αn

dan ¬αi ≡ ¬λim ∧ ¬λi2 ∧ · · · ∧ ¬λim, untuk suatu m.

Perhatikan bahwa ¬φberada dalam DNF.


¬φ ≡ ¬ ((p ∨ q) ∧ (¬p ∨ r))≡ ¬ (p ∨ q) ∨ ¬ (¬p ∨ r)≡ (¬p ∧ ¬q) ∨ (p ∧ ¬r) .




φ = α1 ∧ α2 ∧ · · · ∧ αn,


¬φ ≡ ¬ (α1 ∧ α2 · · · ∧ αn)

≡ ¬α1 ∨ ¬α2 ∨ · · · ∨ ¬αn


ContohMisalkan φ = (p ∨ q) ∧ (¬p ∨ r),

jelas bahwa φ dalam CNF. Kita memiliki

¬φ ≡ ¬ ((p ∨ q) ∧ (¬p ∨ r))≡ ¬ (p ∨ q) ∨ ¬ (¬p ∨ r)≡ (¬p ∧ ¬q) ∨ (p ∧ ¬r) .




φ = α1 ∧ α2 ∧ · · · ∧ αn,


¬φ ≡ ¬ (α1 ∧ α2 · · · ∧ αn)

≡ ¬α1 ∨ ¬α2 ∨ · · · ∨ ¬αn



¬φ ≡ ¬ ((p ∨ q) ∧ (¬p ∨ r))≡

¬ (p ∨ q) ∨ ¬ (¬p ∨ r)≡ (¬p ∧ ¬q) ∨ (p ∧ ¬r) .




φ = α1 ∧ α2 ∧ · · · ∧ αn,


¬φ ≡ ¬ (α1 ∧ α2 · · · ∧ αn)

≡ ¬α1 ∨ ¬α2 ∨ · · · ∨ ¬αn



¬φ ≡ ¬ ((p ∨ q) ∧ (¬p ∨ r))≡ ¬ (p ∨ q) ∨ ¬ (¬p ∨ r)≡ (¬p ∧ ¬q) ∨ (p ∧ ¬r) .



Kita memiliki teorema berikut

TeoremaMisalkan φ adalah suatu formula logika proposisi, maka φ ekuivalen denganformula ψ1 dan ψ2, dengan ψ1 adalah formula dalam CNF dan ψ2 adalah formuladalam DNF.

BuktiLihat buku teks.


ContohMisalkan φ adalah formula p ∧ q → r. Kita mengetahui bahwa

p ∧ q → r ≡

¬ (p ∧ q) ∨ r ≡ ¬p ∨ ¬q ∨ r

Bentuk ¬p ∨ ¬q ∨ r ekuivalen dengan bentuk awal φ dan merupakan formuladalam CNF dan DNF.Misalkan ψ adalah formula p ∧ (q ∨ r). Jelas bahwa ψ berada dalam CNF. Kitamengetahui bahwa

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) .

Bentuk (p ∧ q) ∨ (p ∧ r) ekuivalen dengan bentuk awal ψ dan merupakan formuladalam DNF.Misalkan η adalah formula (p ∧ q) ∨ (r ∧ s). Jelas bahwa η berada dalam DNF.Kita mengetahui bahwa

(p ∧ q) ∨ (r ∧ s) ≡ (p ∨ (r ∧ s)) ∧ (q ∨ (r ∧ s))≡ (p ∨ r) ∧ (p ∨ s) ∧ (q ∨ r) ∧ (q ∨ s)

Bentuk (p ∨ r) ∧ (p ∨ s) ∧ (q ∨ r) ∧ (q ∨ s) ekuivalen dengan bentuk awal ψ danmerupakan formula dalam CNF.



p ∧ q → r ≡ ¬ (p ∧ q) ∨ r ≡ ¬p ∨ ¬q ∨ r


p ∧ (q ∨ r) ≡

(p ∧ q) ∨ (p ∧ r) .






p ∧ q → r ≡ ¬ (p ∧ q) ∨ r ≡ ¬p ∨ ¬q ∨ r


p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) .


(p ∧ q) ∨ (r ∧ s) ≡

(p ∨ (r ∧ s)) ∧ (q ∨ (r ∧ s))≡ (p ∨ r) ∧ (p ∨ s) ∧ (q ∨ r) ∧ (q ∨ s)




p ∧ q → r ≡ ¬ (p ∧ q) ∨ r ≡ ¬p ∨ ¬q ∨ r


p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) .


(p ∧ q) ∨ (r ∧ s) ≡ (p ∨ (r ∧ s)) ∧ (q ∨ (r ∧ s))≡

(p ∨ r) ∧ (p ∨ s) ∧ (q ∨ r) ∧ (q ∨ s)




p ∧ q → r ≡ ¬ (p ∧ q) ∨ r ≡ ¬p ∨ ¬q ∨ r


p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) .





Keterpenuhan untuk Formula dalam CNF dan DNF

TeoremaMisalkan φ adalah formula dalam CNF dengan φ = α1 ∧ α2 ∧ · · · ∧ αn, αi adalahklausa disjungtif untuk 1 ≤ i ≤ n. Formula φ terpenuhi jikka klausa αi untuksemua 1 ≤ i ≤ n juga terpenuhi.

TeoremaMisalkan φ adalah formula dalam DNF dengan φ = β1 ∨ β2 ∨ · · · ∨ βn, βi adalahterm konjungtif untuk 1 ≤ i ≤ n. Formula φ terpenuhi jikka terdapat suatu termβi untuk suatu 1 ≤ i ≤ n sehingga term βi juga terpenuhi.


Konversi ke CNF dan DNF

Untuk mengkonversi suatu formula ke dalam bentuk CNF atau DNF, kita dapatmelakukan hal-hal berikut:

1 Ubah formula dengan operator selain ¬, ∧, dan ∨ ke dalam formula yanghanya boleh memakai tiga operator tersebut. Sebagai contoh, bila formulayang ditinjau memakai operator ⊕, →, dan ↔ kita dapat memanfaatkanekuivalensi berikut: φ⊕ ψ ≡ (φ ∧ ¬ψ) ∨ (¬φ ∨ ψ), φ→ ψ ≡ ¬φ ∨ ψ, danφ↔ ψ ≡ (¬φ ∨ ψ) ∧ (φ ∨ ¬ψ).

2 Jika menemukan subformula dengan bentuk ¬ (φ ∧ ψ), maka subformulatersebut diubah ke dalam bentuk ¬φ ∨ ¬ψ. Kemudian jika menemukansubformula dengan bentuk ¬ (φ ∨ ψ), maka subformula tersebut diubah kedalam bentuk ¬φ ∧ ¬ψ.

3 Jika menemukan subformula dengan bentuk ¬¬φ, maka subformula tersebutdiubah ke dalam bentuk φ.

4 Gunakan sifat distributif secara tepat dan sesuai.Kita memilikiφ ∧ (ψ ∨ η) ≡ (φ ∧ ψ) ∨ (φ ∧ η) dan φ ∨ (ψ ∧ η) ≡ (φ ∨ ψ) ∧ (φ ∨ η).


Misalkan kita memiliki formula φ := (p ∧ (q → r))→ ¬s. Transformasi φ ke CNFdapat dilakukan sebagai berikut:

φ = (p ∧ (q → r))→ ¬s≡

¬ (p ∧ (q → r)) ∨ ¬s (ekuivalensi implikasi)≡ ¬ (p ∧ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡ (¬p ∨ ¬ (¬q ∨ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (¬¬q ∧ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (q ∧ r)) ∨ ¬s (negasi ganda)≡ ((¬p ∨ q) ∧ (¬p ∨ r)) ∨ ¬s (distributif)≡ ¬s ∨ ((¬p ∨ q) ∧ (¬p ∨ r)) (komutatif)≡ (¬s ∨ (¬p ∨ q)) ∧ (¬s ∨ (¬p ∨ r)) (distributif)≡ ((¬p ∨ q) ∨ ¬s) ∧ ((¬p ∨ r) ∨ ¬s) (komutatif)≡ (¬p ∨ q ∨ ¬s) ∧ (¬p ∨ r ∨ ¬s) (asosiatif)



φ = (p ∧ (q → r))→ ¬s≡ ¬ (p ∧ (q → r)) ∨ ¬s (ekuivalensi implikasi)≡ ¬ (p ∧ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡

(¬p ∨ ¬ (¬q ∨ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (¬¬q ∧ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (q ∧ r)) ∨ ¬s (negasi ganda)≡ ((¬p ∨ q) ∧ (¬p ∨ r)) ∨ ¬s (distributif)≡ ¬s ∨ ((¬p ∨ q) ∧ (¬p ∨ r)) (komutatif)≡ (¬s ∨ (¬p ∨ q)) ∧ (¬s ∨ (¬p ∨ r)) (distributif)≡ ((¬p ∨ q) ∨ ¬s) ∧ ((¬p ∨ r) ∨ ¬s) (komutatif)≡ (¬p ∨ q ∨ ¬s) ∧ (¬p ∨ r ∨ ¬s) (asosiatif)



φ = (p ∧ (q → r))→ ¬s≡ ¬ (p ∧ (q → r)) ∨ ¬s (ekuivalensi implikasi)≡ ¬ (p ∧ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡ (¬p ∨ ¬ (¬q ∨ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (¬¬q ∧ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (q ∧ r)) ∨ ¬s (negasi ganda)≡

((¬p ∨ q) ∧ (¬p ∨ r)) ∨ ¬s (distributif)≡ ¬s ∨ ((¬p ∨ q) ∧ (¬p ∨ r)) (komutatif)≡ (¬s ∨ (¬p ∨ q)) ∧ (¬s ∨ (¬p ∨ r)) (distributif)≡ ((¬p ∨ q) ∨ ¬s) ∧ ((¬p ∨ r) ∨ ¬s) (komutatif)≡ (¬p ∨ q ∨ ¬s) ∧ (¬p ∨ r ∨ ¬s) (asosiatif)



φ = (p ∧ (q → r))→ ¬s≡ ¬ (p ∧ (q → r)) ∨ ¬s (ekuivalensi implikasi)≡ ¬ (p ∧ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡ (¬p ∨ ¬ (¬q ∨ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (¬¬q ∧ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (q ∧ r)) ∨ ¬s (negasi ganda)≡ ((¬p ∨ q) ∧ (¬p ∨ r)) ∨ ¬s (distributif)≡ ¬s ∨ ((¬p ∨ q) ∧ (¬p ∨ r)) (komutatif)≡

(¬s ∨ (¬p ∨ q)) ∧ (¬s ∨ (¬p ∨ r)) (distributif)≡ ((¬p ∨ q) ∨ ¬s) ∧ ((¬p ∨ r) ∨ ¬s) (komutatif)≡ (¬p ∨ q ∨ ¬s) ∧ (¬p ∨ r ∨ ¬s) (asosiatif)



φ = (p ∧ (q → r))→ ¬s≡ ¬ (p ∧ (q → r)) ∨ ¬s (ekuivalensi implikasi)≡ ¬ (p ∧ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡ (¬p ∨ ¬ (¬q ∨ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (¬¬q ∧ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (q ∧ r)) ∨ ¬s (negasi ganda)≡ ((¬p ∨ q) ∧ (¬p ∨ r)) ∨ ¬s (distributif)≡ ¬s ∨ ((¬p ∨ q) ∧ (¬p ∨ r)) (komutatif)≡ (¬s ∨ (¬p ∨ q)) ∧ (¬s ∨ (¬p ∨ r)) (distributif)≡ ((¬p ∨ q) ∨ ¬s) ∧ ((¬p ∨ r) ∨ ¬s) (komutatif)≡

(¬p ∨ q ∨ ¬s) ∧ (¬p ∨ r ∨ ¬s) (asosiatif)



φ = (p ∧ (q → r))→ ¬s≡ ¬ (p ∧ (q → r)) ∨ ¬s (ekuivalensi implikasi)≡ ¬ (p ∧ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡ (¬p ∨ ¬ (¬q ∨ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (¬¬q ∧ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (q ∧ r)) ∨ ¬s (negasi ganda)≡ ((¬p ∨ q) ∧ (¬p ∨ r)) ∨ ¬s (distributif)≡ ¬s ∨ ((¬p ∨ q) ∧ (¬p ∨ r)) (komutatif)≡ (¬s ∨ (¬p ∨ q)) ∧ (¬s ∨ (¬p ∨ r)) (distributif)≡ ((¬p ∨ q) ∨ ¬s) ∧ ((¬p ∨ r) ∨ ¬s) (komutatif)≡ (¬p ∨ q ∨ ¬s) ∧ (¬p ∨ r ∨ ¬s) (asosiatif)


Misalkan kita memiliki formula φ := (p ∧ (q → r))→ ¬s. Transformasi φ ke DNFdapat dilakukan sebagai berikut:

φ = (p ∧ (q → r))→ ¬s≡

¬ (p ∧ (q → r)) ∨ ¬s (ekuivalensi implikasi)≡ ¬ (p ∧ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡ (¬p ∨ ¬ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡ (¬p ∨ (¬¬q ∧ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (q ∧ r)) ∨ ¬s (negasi ganda)≡ ¬p ∨ (q ∧ r) ∨ ¬s (asosiatif)



φ = (p ∧ (q → r))→ ¬s≡ ¬ (p ∧ (q → r)) ∨ ¬s (ekuivalensi implikasi)≡ ¬ (p ∧ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡ (¬p ∨ ¬ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡

(¬p ∨ (¬¬q ∧ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (q ∧ r)) ∨ ¬s (negasi ganda)≡ ¬p ∨ (q ∧ r) ∨ ¬s (asosiatif)



φ = (p ∧ (q → r))→ ¬s≡ ¬ (p ∧ (q → r)) ∨ ¬s (ekuivalensi implikasi)≡ ¬ (p ∧ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡ (¬p ∨ ¬ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡ (¬p ∨ (¬¬q ∧ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (q ∧ r)) ∨ ¬s (negasi ganda)≡

¬p ∨ (q ∧ r) ∨ ¬s (asosiatif)



φ = (p ∧ (q → r))→ ¬s≡ ¬ (p ∧ (q → r)) ∨ ¬s (ekuivalensi implikasi)≡ ¬ (p ∧ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡ (¬p ∨ ¬ (¬q ∨ r)) ∨ ¬s (ekuivalensi implikasi)≡ (¬p ∨ (¬¬q ∧ r)) ∨ ¬s (De Morgan)≡ (¬p ∨ (q ∧ r)) ∨ ¬s (negasi ganda)≡ ¬p ∨ (q ∧ r) ∨ ¬s (asosiatif)


Latihan: Konversi ke CNF dan DNF

LatihanBerikan formula yang ekuivalen dalam bentuk CNF dan DNF

1 p→ (q ∧ r)2 (p ∨ q)→ r

3 (p→ q)→ r

4 p→ (q → r)

5 p↔ q


Konstruksi Formula Dalam CNF dari Tabel KebenaranMisalkan φ adalah sebuah proposisi yang memuat dua proposisi atom, yaitu p danq. Jika diketahui φ memiliki tabel kebenaran berikut:

p q φT T FT F FF T FF F T

maka kita dapat menentukan φ dalam bentuk CNF dengan cara-cara berikut:

1 Tandai baris pada tabel kebenaran yang memberikan entri F. Jika ada n barisyang memberikan entri F, formula adalah φ = α1 ∧ α2 ∧ · · · ∧ αn. Perhatikanbahwa I (φ) = F bila salah satu dari αi untuk 1 ≤ i ≤ n memberikanI (αi) = F.

2 Untuk setiap baris ke-i, formula αi = λi1 ∨ λi2 ∨ · · · ∨ λim, dengan m adalahbanyaknya proposisi atom berbeda pada formula yang ditinjau. JikaI (αi) = F, maka I (λi) = F untuk setiap 1 ≤ i ≤ m. Misalkan pi (untuksuatu 1 ≤ i ≤ m) adalah proposisi atom yang terdapat pada formula φ, maka

kita memiliki λim =

{pi, jika I (pi) = F¬pi, jika I (pi) = T

.


Konstruksi Formula Dalam CNF dari Tabel KebenaranMisalkan φ adalah sebuah proposisi yang memuat dua proposisi atom, yaitu p danq. Jika diketahui φ memiliki tabel kebenaran berikut:


maka kita dapat menentukan φ dalam bentuk CNF dengan cara-cara berikut:1 Tandai baris pada tabel kebenaran yang memberikan entri F. Jika ada n barisyang memberikan entri F, formula adalah φ = α1 ∧ α2 ∧ · · · ∧ αn. Perhatikanbahwa I (φ) = F bila salah satu dari αi untuk 1 ≤ i ≤ n memberikanI (αi) = F.

2 Untuk setiap baris ke-i, formula αi = λi1 ∨ λi2 ∨ · · · ∨ λim, dengan m adalahbanyaknya proposisi atom berbeda pada formula yang ditinjau. JikaI (αi) = F, maka I (λi) = F untuk setiap 1 ≤ i ≤ m. Misalkan pi (untuksuatu 1 ≤ i ≤ m) adalah proposisi atom yang terdapat pada formula φ, maka

kita memiliki λim =

{pi, jika I (pi) = F¬pi, jika I (pi) = T

.


Sebagai contoh bila tabel kebenaran untuk φ adalah


maka φ =

α1 ∧ α2 ∧ α3. Kita memiliki

α1 = λ11 ∨ λ12 = ¬p ∨ ¬qα2 = λ21 ∨ λ22 = ¬p ∨ qα3 = λ31 ∨ λ32 = p ∨ ¬q

Akibatnya φ = (¬p ∨ ¬q) ∧ (¬p ∨ q) ∧ (p ∨ ¬q).




maka φ = α1 ∧ α2 ∧ α3. Kita memiliki

α1 =

λ11 ∨ λ12 = ¬p ∨ ¬qα2 = λ21 ∨ λ22 = ¬p ∨ qα3 = λ31 ∨ λ32 = p ∨ ¬q






α1 = λ11 ∨ λ12 = ¬p ∨ ¬qα2 =

λ21 ∨ λ22 = ¬p ∨ qα3 = λ31 ∨ λ32 = p ∨ ¬q






α1 = λ11 ∨ λ12 = ¬p ∨ ¬qα2 = λ21 ∨ λ22 = ¬p ∨ qα3 =

λ31 ∨ λ32 = p ∨ ¬q







Akibatnya φ =

(¬p ∨ ¬q) ∧ (¬p ∨ q) ∧ (p ∨ ¬q).


Latihan (Mengkonstruksi Formula dari Tabel Kebenaran)Misalakan φ adalah fomula logika proposisi yang hanya memuat proposisi atom p,q, dan r saja. Bila diketahui tabel kebenaran untuk φ adalah

p q r φT T T TT T F FT F T TT F F TF T T FF T F FF F T FF F F T

Tentukan formula φ dalam CNF.

Solusi:

karena terdapat 4 baris sehingga I (φ) = F, maka φ = α1 ∧ α2 ∧ α3 ∧ α4.Dari baris ke-2 kita memiliki α1 = ¬p ∨ ¬q ∨ r, dari baris ke-5 kita memilikiα2 = p ∨ ¬q ∨ ¬r, dari baris ke-6 kita memiliki α3 = p ∨ ¬q ∨ r, dan dari bariske-7 kita memiliki α4 = p ∨ q ∨ ¬r. Akibatnya

φ = (¬p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r) .





Solusi: karena terdapat 4 baris sehingga I (φ) = F, maka φ =

α1 ∧ α2 ∧ α3 ∧ α4.Dari baris ke-2 kita memiliki α1 = ¬p ∨ ¬q ∨ r, dari baris ke-5 kita memilikiα2 = p ∨ ¬q ∨ ¬r, dari baris ke-6 kita memiliki α3 = p ∨ ¬q ∨ r, dan dari bariske-7 kita memiliki α4 = p ∨ q ∨ ¬r. Akibatnya

φ = (¬p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r) .





Solusi: karena terdapat 4 baris sehingga I (φ) = F, maka φ = α1 ∧ α2 ∧ α3 ∧ α4.Dari baris ke-2 kita memiliki α1 =

¬p ∨ ¬q ∨ r, dari baris ke-5 kita memilikiα2 = p ∨ ¬q ∨ ¬r, dari baris ke-6 kita memiliki α3 = p ∨ ¬q ∨ r, dan dari bariske-7 kita memiliki α4 = p ∨ q ∨ ¬r. Akibatnya

φ = (¬p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r) .





Solusi: karena terdapat 4 baris sehingga I (φ) = F, maka φ = α1 ∧ α2 ∧ α3 ∧ α4.Dari baris ke-2 kita memiliki α1 = ¬p ∨ ¬q ∨ r, dari baris ke-5 kita memilikiα2 =

p ∨ ¬q ∨ ¬r, dari baris ke-6 kita memiliki α3 = p ∨ ¬q ∨ r, dan dari bariske-7 kita memiliki α4 = p ∨ q ∨ ¬r. Akibatnya

φ = (¬p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r) .





Solusi: karena terdapat 4 baris sehingga I (φ) = F, maka φ = α1 ∧ α2 ∧ α3 ∧ α4.Dari baris ke-2 kita memiliki α1 = ¬p ∨ ¬q ∨ r, dari baris ke-5 kita memilikiα2 = p ∨ ¬q ∨ ¬r, dari baris ke-6 kita memiliki α3 =

p ∨ ¬q ∨ r, dan dari bariske-7 kita memiliki α4 = p ∨ q ∨ ¬r. Akibatnya

φ = (¬p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r) .





Solusi: karena terdapat 4 baris sehingga I (φ) = F, maka φ = α1 ∧ α2 ∧ α3 ∧ α4.Dari baris ke-2 kita memiliki α1 = ¬p ∨ ¬q ∨ r, dari baris ke-5 kita memilikiα2 = p ∨ ¬q ∨ ¬r, dari baris ke-6 kita memiliki α3 = p ∨ ¬q ∨ r, dan dari bariske-7 kita memiliki α4 =

p ∨ q ∨ ¬r. Akibatnyaφ = (¬p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r) .





Solusi: karena terdapat 4 baris sehingga I (φ) = F, maka φ = α1 ∧ α2 ∧ α3 ∧ α4.Dari baris ke-2 kita memiliki α1 = ¬p ∨ ¬q ∨ r, dari baris ke-5 kita memilikiα2 = p ∨ ¬q ∨ ¬r, dari baris ke-6 kita memiliki α3 = p ∨ ¬q ∨ r, dan dari bariske-7 kita memiliki α4 = p ∨ q ∨ ¬r. Akibatnya

φ =

(¬p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r) .





Solusi: karena terdapat 4 baris sehingga I (φ) = F, maka φ = α1 ∧ α2 ∧ α3 ∧ α4.Dari baris ke-2 kita memiliki α1 = ¬p ∨ ¬q ∨ r, dari baris ke-5 kita memilikiα2 = p ∨ ¬q ∨ ¬r, dari baris ke-6 kita memiliki α3 = p ∨ ¬q ∨ r, dan dari bariske-7 kita memiliki α4 = p ∨ q ∨ ¬r. Akibatnya

φ = (¬p ∨ ¬q ∨ r) ∧ (p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (p ∨ q ∨ ¬r) .MZI (FIF Tel-U) Logika Proposisi (Kalkulus Proposisi) September 2015 82 / 95

Algoritma Konversi Ke CNF

Misalkan φ adalah formula logika proposisi yang hanya memuat operator ¬, ∧, ∨,dan → saja, maka kita dapat mengkonversi φ ke dalam bentuk NNF denganmemanfaatkan ekuivalensi berikut

¬¬φ ≡ φ¬ (φ ∧ ψ) ≡ ¬φ ∨ ¬ψ¬ (φ ∨ ψ) ≡ ¬φ ∧ ¬ψφ→ ψ ≡ ¬φ ∨ ψ

Untuk mempermudah, masukan (input) dari algoritma akan dikonversi terlebihdulu sehingga hanya memakai operator ¬, ∧, dan ∨ saja. Hal ini dapat dilakukandengan membuat fungsi IMPL− FREE yang mentransformasi semua bentukformula dengan dengan operator ¬,∧, ∨, dan → sehingga tidak memuat operator→. Masukan dari fungsi IMPL− FREE adalah formula dalam bentuk FPE yangdapat memuat operator ¬, ∧, ∨, dan →.


Fungsi IMPL-FREEMasukan: φ yang berada dalam bentuk FPE dan hanya memuat operator ¬, ∧,∨, dan → saja.Keluaran: IMPL− FREE (φ) yang berupa formula yang ekuivalen dengan φ dantidak memuat operator →.function IMPL− FREE (φ)1 begin function2 case3 φ is a literal λ: return φ4 φ is ¬ψ: return ¬IMPL− FREE (ψ)5 φ is ψ1 ∧ ψ2: return IMPL− FREE (ψ1) ∧ IMPL− FREE (ψ2)6 φ is ψ1 ∨ ψ2: return IMPL− FREE (ψ1) ∨ IMPL− FREE (ψ2)7 φ is ψ1 → ψ2: return ¬IMPL− FREE (ψ1) ∨ IMPL− FREE (ψ2)8 end case9 end function


Berikut adalah fungsi CNF (φ) yang mentransformasikan formula logika proposisi φmenjadi formula CNF (φ) yang ekuivalen dengan φ dan berada dalam CNF.Masukan (input) algoritma adalah formula yang hanya memuat operator ¬, ∨,atau ∧ saja, serta berada dalam NNF. Ini berarti operator negasi pada φ hanyaboleh berada di depan proposisi atom saja.

Fungsi CNFMasukan: φ yang berada dalam bentuk FPE, hanya memuat operator ¬, ∧, dan∨ saja, serta berada dalam NNF.Keluaran: CNF (φ) yang berupa formula yang ekuivalen dengan φ dan beradadalam CNF.function CNF (φ)1 begin function2 case3 φ is a literal λ: return φ4 φ is ψ1 ∧ ψ2: return CNF (ψ) ∧ CNF (ψ2)5 φ is ψ1 ∨ ψ2: return DISTR (CNF (ψ1) , CNF (ψ2))6 end case7 end function

Subrutin DISTR (CNF (ψ1) , CNF (ψ2)) berfungsi untuk mengkonversi bentukdisjungsi CNF(ψ1) ∨ CNF (ψ2) menjadi bentuk CNF.


Formula yang berupa disjungsi dari bentuk-bentuk CNF dapat diubah menjadiCNF dengan fungsi DISTR (CNF (ψ1) , CNF (ψ2)).

Fungsi DISTRMasukan: φ yang berada dalam bentuk FPE dan CNF.Keluaran: DISTR (CNF (ψ1) , CNF (ψ2)) yang berupa formula yang ekuivalendengan CNF (ψ1) ∨ CNF (ψ2) dan berada dalam CNF.function DISTR (CNF (ψ1) , CNF (ψ2))1 begin function2 case3 ψ1 is ψ11 ∧ ψ12: return DISTR (ψ11, ψ2) ∧ DISTR (ψ12, ψ2)4 ψ2 is ψ21 ∧ ψ22: return DISTR (ψ1, ψ21) ∧ DISTR (ψ1, ψ22)5 otherwise (i.e. no conjunction within disjunction): return ψ1 ∨ ψ26 end case7 end function

Sebagai contoh, kita memiliki

CNF (p ∨ (q ∧ r)) =

DISTR (p, q ∧ r)= DISTR (p, q) ∧ DISTR (p, r)

= (p ∨ q) ∧ (p ∨ r) .





CNF (p ∨ (q ∧ r)) = DISTR (p, q ∧ r)=

DISTR (p, q) ∧ DISTR (p, r)

= (p ∨ q) ∧ (p ∨ r) .





CNF (p ∨ (q ∧ r)) = DISTR (p, q ∧ r)= DISTR (p, q) ∧ DISTR (p, r)

=

(p ∨ q) ∧ (p ∨ r) .





CNF (p ∨ (q ∧ r)) = DISTR (p, q ∧ r)= DISTR (p, q) ∧ DISTR (p, r)

= (p ∨ q) ∧ (p ∨ r) .


Transformasi Formula Ke CNF

Diberikan suatu formula logika proposisi φ, kita dapat mentransformasikan φformula yang ekuivalen dan berada dalam CNF dengan langkah-langkah berikut:

1 Konversi φ sehingga hanya boleh memuat operator logika ¬, ∧, ∨, dan →saja.

2 Konversi φ ke formula yang tidak memuat operator → dengan fungsiIMPL− FREE (φ).

3 Konversi IMPL− FREE (φ) ke NNF dengan fungsi NNF (IMPL− FREE (φ)).4 Konversi NNF (IMPL− FREE (φ)) ke CNF dengan fungsiCNF (NNF (IMPL− FREE (φ))).


ContohMisalkan kita akan menentukan CNF dari ¬p ∧ q → p ∧ (r → q). Pertama akanditentukan IMPL− FREE (φ) terlebih dulu

IMPL− FREE (φ)

= IMPL− FREE (¬p ∧ q → p ∧ (r → q))

=

¬IMPL− FREE (¬p ∧ q) ∨ IMPL− FREE (p ∧ (r → q))

= ¬ (IMPL− FREE (¬p) ∧ IMPL− FREE (q)) ∨(

IMPL− FREE (p)∧IMPL− FREE (r → q)

)= ¬

(¬IMPL− FREE (p)∧IMPL− FREE (q)

)∨(IMPL− FREE (p) ∧

(¬IMPL− FREE (r)∨IMPL− FREE (q)

))= ¬ (¬p ∧ q) ∨ (p ∧ (¬r ∨ q))



IMPL− FREE (φ)

= IMPL− FREE (¬p ∧ q → p ∧ (r → q))

= ¬IMPL− FREE (¬p ∧ q) ∨ IMPL− FREE (p ∧ (r → q))

=

¬ (IMPL− FREE (¬p) ∧ IMPL− FREE (q)) ∨(


)= ¬




))= ¬ (¬p ∧ q) ∨ (p ∧ (¬r ∨ q))



IMPL− FREE (φ)

= IMPL− FREE (¬p ∧ q → p ∧ (r → q))




)=

¬(¬IMPL− FREE (p)∧IMPL− FREE (q)



))= ¬ (¬p ∧ q) ∨ (p ∧ (¬r ∨ q))



IMPL− FREE (φ)

= IMPL− FREE (¬p ∧ q → p ∧ (r → q))




)= ¬




))=

¬ (¬p ∧ q) ∨ (p ∧ (¬r ∨ q))



IMPL− FREE (φ)

= IMPL− FREE (¬p ∧ q → p ∧ (r → q))




)= ¬




))= ¬ (¬p ∧ q) ∨ (p ∧ (¬r ∨ q))


Selanjutnya dilakukan komputasi pencarian NNF (IMPL− FREE (φ))

NNF (IMPL− FREE (φ))

= NNF (¬ (¬p ∧ q) ∨ (p ∧ (¬r ∨ q)))=

NNF (¬ (¬p ∧ q)) ∨ NNF (p ∧ (¬r ∨ q))= (NNF (¬ (¬p)) ∨ NNF (¬q)) ∨ (NNF (p) ∧ NNF (¬r ∨ q))= (NNF (¬¬p) ∨ NNF (¬q)) ∨ (NNF (p) ∧ (NNF (¬r) ∨ NNF (q)))

= (p ∨ ¬q) ∨ (p ∧ (¬r ∨ q))




= NNF (¬ (¬p ∧ q) ∨ (p ∧ (¬r ∨ q)))= NNF (¬ (¬p ∧ q)) ∨ NNF (p ∧ (¬r ∨ q))=

(NNF (¬ (¬p)) ∨ NNF (¬q)) ∨ (NNF (p) ∧ NNF (¬r ∨ q))= (NNF (¬¬p) ∨ NNF (¬q)) ∨ (NNF (p) ∧ (NNF (¬r) ∨ NNF (q)))

= (p ∨ ¬q) ∨ (p ∧ (¬r ∨ q))




= NNF (¬ (¬p ∧ q) ∨ (p ∧ (¬r ∨ q)))= NNF (¬ (¬p ∧ q)) ∨ NNF (p ∧ (¬r ∨ q))= (NNF (¬ (¬p)) ∨ NNF (¬q)) ∨ (NNF (p) ∧ NNF (¬r ∨ q))=

(NNF (¬¬p) ∨ NNF (¬q)) ∨ (NNF (p) ∧ (NNF (¬r) ∨ NNF (q)))

= (p ∨ ¬q) ∨ (p ∧ (¬r ∨ q))




= NNF (¬ (¬p ∧ q) ∨ (p ∧ (¬r ∨ q)))= NNF (¬ (¬p ∧ q)) ∨ NNF (p ∧ (¬r ∨ q))= (NNF (¬ (¬p)) ∨ NNF (¬q)) ∨ (NNF (p) ∧ NNF (¬r ∨ q))= (NNF (¬¬p) ∨ NNF (¬q)) ∨ (NNF (p) ∧ (NNF (¬r) ∨ NNF (q)))

=

(p ∨ ¬q) ∨ (p ∧ (¬r ∨ q))




= NNF (¬ (¬p ∧ q) ∨ (p ∧ (¬r ∨ q)))= NNF (¬ (¬p ∧ q)) ∨ NNF (p ∧ (¬r ∨ q))= (NNF (¬ (¬p)) ∨ NNF (¬q)) ∨ (NNF (p) ∧ NNF (¬r ∨ q))= (NNF (¬¬p) ∨ NNF (¬q)) ∨ (NNF (p) ∧ (NNF (¬r) ∨ NNF (q)))

= (p ∨ ¬q) ∨ (p ∧ (¬r ∨ q))


Komputasi transformasi CNF (NNF (IMPL− FREE (φ))) dilakukan sebagai berikut

CNF (NNF (IMPL− FREE (φ)))

= CNF ((p ∨ ¬q) ∨ (p ∧ (¬r ∨ q)))=

DISTR (CNF (p ∨ ¬q) , CNF (p ∧ (¬r ∨ q)))= DISTR (DISTR (CNF (p) , CNF (¬q)) , CNF (p) ∧ CNF (¬r ∨ q))= DISTR (DISTR (CNF (p) , CNF (¬q)) , CNF (p) ∧ DISTR (CNF (¬r) , CNF (q)))

= DISTR (p ∨ ¬q, p ∧ (¬r ∨ q))= DISTR (p ∨ ¬q, p) ∧ DISTR (p ∨ ¬q, (¬r ∨ q))= ((p ∨ ¬q) ∨ p) ∧ ((p ∨ ¬q) ∨ (¬r ∨ q))= (p ∨ ¬q ∨ p) ∧ (p ∨ ¬q ∨ ¬r ∨ q)

Formula terakhir juga ekuivalen (sama secara semantik) dengan

(p ∨ ¬q) ∧ (p ∨ ¬r)

yang lebih sederhana dan tetap berada di dalam CNF.




= CNF ((p ∨ ¬q) ∨ (p ∧ (¬r ∨ q)))= DISTR (CNF (p ∨ ¬q) , CNF (p ∧ (¬r ∨ q)))=

DISTR (DISTR (CNF (p) , CNF (¬q)) , CNF (p) ∧ CNF (¬r ∨ q))= DISTR (DISTR (CNF (p) , CNF (¬q)) , CNF (p) ∧ DISTR (CNF (¬r) , CNF (q)))



(p ∨ ¬q) ∧ (p ∨ ¬r)





= CNF ((p ∨ ¬q) ∨ (p ∧ (¬r ∨ q)))= DISTR (CNF (p ∨ ¬q) , CNF (p ∧ (¬r ∨ q)))= DISTR (DISTR (CNF (p) , CNF (¬q)) , CNF (p) ∧ CNF (¬r ∨ q))=

DISTR (DISTR (CNF (p) , CNF (¬q)) , CNF (p) ∧ DISTR (CNF (¬r) , CNF (q)))



(p ∨ ¬q) ∧ (p ∨ ¬r)





= CNF ((p ∨ ¬q) ∨ (p ∧ (¬r ∨ q)))= DISTR (CNF (p ∨ ¬q) , CNF (p ∧ (¬r ∨ q)))= DISTR (DISTR (CNF (p) , CNF (¬q)) , CNF (p) ∧ CNF (¬r ∨ q))= DISTR (DISTR (CNF (p) , CNF (¬q)) , CNF (p) ∧ DISTR (CNF (¬r) , CNF (q)))

=

DISTR (p ∨ ¬q, p ∧ (¬r ∨ q))= DISTR (p ∨ ¬q, p) ∧ DISTR (p ∨ ¬q, (¬r ∨ q))= ((p ∨ ¬q) ∨ p) ∧ ((p ∨ ¬q) ∨ (¬r ∨ q))= (p ∨ ¬q ∨ p) ∧ (p ∨ ¬q ∨ ¬r ∨ q)


(p ∨ ¬q) ∧ (p ∨ ¬r)






= DISTR (p ∨ ¬q, p ∧ (¬r ∨ q))=

DISTR (p ∨ ¬q, p) ∧ DISTR (p ∨ ¬q, (¬r ∨ q))= ((p ∨ ¬q) ∨ p) ∧ ((p ∨ ¬q) ∨ (¬r ∨ q))= (p ∨ ¬q ∨ p) ∧ (p ∨ ¬q ∨ ¬r ∨ q)


(p ∨ ¬q) ∧ (p ∨ ¬r)






= DISTR (p ∨ ¬q, p ∧ (¬r ∨ q))= DISTR (p ∨ ¬q, p) ∧ DISTR (p ∨ ¬q, (¬r ∨ q))=

((p ∨ ¬q) ∨ p) ∧ ((p ∨ ¬q) ∨ (¬r ∨ q))= (p ∨ ¬q ∨ p) ∧ (p ∨ ¬q ∨ ¬r ∨ q)


(p ∨ ¬q) ∧ (p ∨ ¬r)






= DISTR (p ∨ ¬q, p ∧ (¬r ∨ q))= DISTR (p ∨ ¬q, p) ∧ DISTR (p ∨ ¬q, (¬r ∨ q))= ((p ∨ ¬q) ∨ p) ∧ ((p ∨ ¬q) ∨ (¬r ∨ q))=

(p ∨ ¬q ∨ p) ∧ (p ∨ ¬q ∨ ¬r ∨ q)


(p ∨ ¬q) ∧ (p ∨ ¬r)








(p ∨ ¬q) ∧ (p ∨ ¬r)



LatihanDiberikan formula logika proposisi φ := r → (s→ (t ∧ s→ r)). Gunakanfungsi-fungsi IMPL− FREE, NNF, dan CNF untuk memperoleh bentuk CNF dari φ.


Exponential Explosion

Kita telah melihat algoritma konversi ke CNF untuk sembarang formula logikaproposisi φ. Sayangnya tidak semua CNF dari formula φ memiliki bentuk yangsederhana.

PermasalahanBagaimana CNF dari formula φ := (p1 ∧ q1) ∨ (p2 ∧ q2) ∨ (p3 ∧ q3)?


Formula φ berada dalam DNF dan belum berbentuk FPE. Untuk mempermudahdalam mencari CNF dari φ, maka pertama φ akan ditulisφ := ((p1 ∧ q1) ∨ (p2 ∧ q2)) ∨ (p3 ∧ q3). Perhatikan bahwa

((p1 ∧ q1) ∨ (p2 ∧ q2)) ∨ (p3 ∧ q3)≡

(((p1 ∧ q1) ∨ p2) ∧ ((p1 ∧ q1) ∨ q2)) ∨ (p3 ∧ q3)≡ ((p1 ∨ p2) ∧ (q1 ∨ p2) ∧ (p1 ∨ q2) ∧ (q1 ∨ q2)) ∨ (p3 ∧ q3)≡ ((p1 ∨ p2) ∨ (p3 ∧ q3)) ∧ ((q1 ∨ p2) ∨ (p3 ∧ q3))∧ ((p1 ∨ q2) ∨ (p3 ∧ q3) ∧ (q1 ∨ q2) ∨ (p3 ∧ q3))

≡ (p1 ∨ p2 ∨ p3) ∧ (p1 ∨ p2 ∨ q3) ∧ (q1 ∨ p2 ∨ p3) ∧ (q1 ∨ p2 ∨ q3)∧ (p1 ∨ q2 ∨ p3) ∧ (p1 ∨ q2 ∨ q3) ∧ (q1 ∨ q2 ∨ p3) ∧ (q1 ∨ q2 ∨ q3)

≡ (p1 ∨ p2 ∨ p3) ∧ (p1 ∨ p2 ∨ q3) ∧ (p1 ∨ q2 ∨ p3) ∧ (q1 ∨ p2 ∨ p3)∧ (p1 ∨ q2 ∨ q3) ∧ (q1 ∨ p2 ∨ q3) ∧ (q1 ∨ q2 ∨ p3) ∧ (q1 ∨ q2 ∨ q3)



((p1 ∧ q1) ∨ (p2 ∧ q2)) ∨ (p3 ∧ q3)≡ (((p1 ∧ q1) ∨ p2) ∧ ((p1 ∧ q1) ∨ q2)) ∨ (p3 ∧ q3)≡

((p1 ∨ p2) ∧ (q1 ∨ p2) ∧ (p1 ∨ q2) ∧ (q1 ∨ q2)) ∨ (p3 ∧ q3)≡ ((p1 ∨ p2) ∨ (p3 ∧ q3)) ∧ ((q1 ∨ p2) ∨ (p3 ∧ q3))∧ ((p1 ∨ q2) ∨ (p3 ∧ q3) ∧ (q1 ∨ q2) ∨ (p3 ∧ q3))





((p1 ∧ q1) ∨ (p2 ∧ q2)) ∨ (p3 ∧ q3)≡ (((p1 ∧ q1) ∨ p2) ∧ ((p1 ∧ q1) ∨ q2)) ∨ (p3 ∧ q3)≡ ((p1 ∨ p2) ∧ (q1 ∨ p2) ∧ (p1 ∨ q2) ∧ (q1 ∨ q2)) ∨ (p3 ∧ q3)≡

((p1 ∨ p2) ∨ (p3 ∧ q3)) ∧ ((q1 ∨ p2) ∨ (p3 ∧ q3))∧ ((p1 ∨ q2) ∨ (p3 ∧ q3) ∧ (q1 ∨ q2) ∨ (p3 ∧ q3))





((p1 ∧ q1) ∨ (p2 ∧ q2)) ∨ (p3 ∧ q3)≡ (((p1 ∧ q1) ∨ p2) ∧ ((p1 ∧ q1) ∨ q2)) ∨ (p3 ∧ q3)≡ ((p1 ∨ p2) ∧ (q1 ∨ p2) ∧ (p1 ∨ q2) ∧ (q1 ∨ q2)) ∨ (p3 ∧ q3)≡ ((p1 ∨ p2) ∨ (p3 ∧ q3)) ∧ ((q1 ∨ p2) ∨ (p3 ∧ q3))∧ ((p1 ∨ q2) ∨ (p3 ∧ q3) ∧ (q1 ∨ q2) ∨ (p3 ∧ q3))

≡

(p1 ∨ p2 ∨ p3) ∧ (p1 ∨ p2 ∨ q3) ∧ (q1 ∨ p2 ∨ p3) ∧ (q1 ∨ p2 ∨ q3)∧ (p1 ∨ q2 ∨ p3) ∧ (p1 ∨ q2 ∨ q3) ∧ (q1 ∨ q2 ∨ p3) ∧ (q1 ∨ q2 ∨ q3)




((p1 ∧ q1) ∨ (p2 ∧ q2)) ∨ (p3 ∧ q3)≡ (((p1 ∧ q1) ∨ p2) ∧ ((p1 ∧ q1) ∨ q2)) ∨ (p3 ∧ q3)≡ ((p1 ∨ p2) ∧ (q1 ∨ p2) ∧ (p1 ∨ q2) ∧ (q1 ∨ q2)) ∨ (p3 ∧ q3)≡ ((p1 ∨ p2) ∨ (p3 ∧ q3)) ∧ ((q1 ∨ p2) ∨ (p3 ∧ q3))∧ ((p1 ∨ q2) ∨ (p3 ∧ q3) ∧ (q1 ∨ q2) ∨ (p3 ∧ q3))




TeoremaMisalkan φ adalah formula (p1 ∧ q1)∨ (p2 ∧ q2)∨ · · · ∨ (pn ∧ qn) =

∨ni=1 (pi ∧ qi),

maka CNF yang ekuivalen dengan φ adalah

(p1 ∨ p2 ∨ · · · ∨ pn) ∧ (q1 ∨ p2 ∨ · · · ∨ pn) ∧ (p1 ∨ q2 ∨ · · · ∨ pn)

∧ (q1 ∨ q2 ∨ · · · ∨ pn) ∧ · · · ∧ (q1 ∧ q2 ∧ · · · ∧ qn) .

Jika CNF (φ) adalah formula yang ekuivalen dengan φ dan berada dalam CNF,maka CNF (φ) memuat 2n klausa, untuk setiap 1 ≤ i ≤ n, masing-masing klausamemuat salah satu dari pi atau qi tetapi tidak keduanya.


Hal serupa juga terjadi pada formula dalam DNF. Misalkan φ adalah formula(p1 ∨ q1) ∧ (p2 ∨ q2) ∧ (p3 ∨ q3). Jelas bahwa φ berada dalam CNF. Denganmemakai sifat distributif, formula yang ekuivalen dengan φ dan berada dalamDNF adalah

(p1 ∧ p2 ∧ p3) ∨ (p1 ∧ p2 ∨ q3) ∨ (p1 ∨ q2 ∨ p3) ∨ (q1 ∨ p2 ∨ p3)∨ (p1 ∧ q2 ∧ q3) ∨ (q1 ∧ p2 ∧ p3) ∨ (q1 ∧ q2 ∧ p3) ∨ (q1 ∧ q2 ∧ q3) .

TeoremaMisalkan φ adalah formula (p1 ∨ q1)∧ (p2 ∨ q2)∧ · · · ∧ (pn ∨ qn) =

∧ni=1 (pi ∨ qi),

maka DNF yang ekuivalen dengan φ adalah

(p1 ∧ p2 ∧ · · · ∧ pn) ∨ (q1 ∧ p2 ∧ · · · ∧ pn) ∨ (p1 ∧ q2 ∧ · · · ∧ pn)

∨ (q1 ∧ q2 ∧ · · · ∧ pn) ∨ · · · ∨ (q1 ∧ q2 ∧ · · · ∧ qn) .

Jika DNF (φ) adalah formula yang ekuivalen dengan φ dan berada dalam DNF,maka DNF (φ) memuat 2n term, untuk setiap 1 ≤ i ≤ n, masing-masing termmemuat salah satu dari pi atau qi tetapi tidak keduanya.




Teorema

Misalkan φ adalah formula (p1 ∨ q1)∧ (p2 ∨ q2)∧ · · · ∧ (pn ∨ qn) =∧ni=1 (pi ∨ qi),


(p1 ∧ p2 ∧ · · · ∧ pn) ∨ (q1 ∧ p2 ∧ · · · ∧ pn) ∨ (p1 ∧ q2 ∧ · · · ∧ pn)

∨ (q1 ∧ q2 ∧ · · · ∧ pn) ∨ · · · ∨ (q1 ∧ q2 ∧ · · · ∧ qn) .





TeoremaMisalkan φ adalah formula (p1 ∨ q1)∧ (p2 ∨ q2)∧ · · · ∧ (pn ∨ qn) =

∧ni=1 (pi ∨ qi),


(p1 ∧ p2 ∧ · · · ∧ pn) ∨ (q1 ∧ p2 ∧ · · · ∧ pn) ∨ (p1 ∧ q2 ∧ · · · ∧ pn)

∨ (q1 ∧ q2 ∧ · · · ∧ pn) ∨ · · · ∨ (q1 ∧ q2 ∧ · · · ∧ qn) .



logika proposisi (kalkulus proposisi) - telkom...

Documents