Tujuan:

Menulis sebuah program lengkap atau fungsi yang mengambil rumus di logika proposisional (selanjutnya disebut sebagai ekspresi logika atau ekspresi ) dan output yang formula dalam bentuk normal penghubung . Ada dua konstanta, ⊤dan ⊥mewakili benar dan salah, operator unary ¬yang mewakili negasi, dan operator biner ⇒, ⇔, ∧, dan ∨mewakili implikasi, kesetaraan, hubungannya, dan disjungsi, masing-masing yang taat semua operasi logis biasa ( hukum DeMorgan , ganda negasi eliminasi , dll.).

Bentuk normal konjungtif didefinisikan sebagai berikut:

1. Ekspresi atom apa pun (termasuk ⊤dan ⊥) dalam bentuk normal konjungtif.
2. Peniadaan ekspresi yang dikonstruksikan sebelumnya dalam bentuk konjungtif normal.
3. Disjungsi dari dua ekspresi yang dibangun sebelumnya adalah dalam bentuk normal konjungtif.
4. Konjungsi dari dua ekspresi yang dibangun sebelumnya adalah dalam bentuk normal konjungtif.
5. Ekspresi lain apa pun tidak dalam bentuk normal konjungtif.

Ekspresi logis apa pun dapat dikonversi (non-unik) menjadi ekspresi yang setara secara logis dalam bentuk normal konjungtif (lihat algoritma ini ). Anda tidak perlu menggunakan algoritma khusus itu.

Memasukkan:

Anda dapat mengambil input dalam format apa pun yang mudah; misalnya, ekspresi logis simbolis (jika bahasa Anda mendukungnya), string, beberapa struktur data lainnya. Anda tidak perlu menggunakan simbol yang sama untuk operator yang benar, salah, dan logis seperti yang saya lakukan di sini, tetapi pilihan Anda harus konsisten dan Anda harus menjelaskan pilihan Anda dalam jawaban Anda jika tidak jelas. Anda tidak boleh menerima input lain atau menyandikan informasi tambahan apa pun dalam format input Anda. Anda harus memiliki beberapa cara untuk mengekspresikan sejumlah ekspresi atom; misalnya bilangan bulat, karakter, string, dll.

Keluaran:

Rumus dalam bentuk normal konjungtif, lagi dalam format yang mudah. Tidak harus dalam format yang sama dengan input Anda, tetapi Anda harus menjelaskan jika ada perbedaan.

Kasus uji:

P ∧ (P ⇒ R) -> P ∧ R
P ⇔ (¬ P) -> ⊥
(¬ P) ∨ (Q ⇔ (P ∧ R)) -> ((¬ P) ∨ ((¬ Q) ∨ R)) ∧ ((¬ P) ∨ (Q ∨ (¬ R)))

Catatan:

1. Jika ekspresi input adalah tautologi, ⊤akan menjadi output yang valid. Demikian pula, jika ekspresi input adalah kontradiksi, ⊥akan menjadi output yang valid.
2. Baik format input dan output Anda harus memiliki urutan operasi yang terdefinisi dengan baik yang mampu mengekspresikan semua ekspresi logis yang mungkin. Anda mungkin membutuhkan semacam tanda kurung.
3. Anda dapat menggunakan pilihan notasi infiks, awalan, atau postfix yang didefinisikan dengan baik untuk operasi logis. Jika pilihan Anda berbeda dari standar (negasi adalah awalan, sisanya adalah infix), tolong jelaskan itu dalam jawaban Anda.
4. Bentuk normal konjungtif tidak unik pada umumnya (bahkan tidak untuk pemesanan ulang). Anda hanya perlu output suatu bentuk yang valid.
5. Bagaimanapun Anda merepresentasikan ekspresi atom, mereka harus berbeda dari konstanta logis, operator, dan simbol pengelompokan (jika Anda memilikinya).
6. Built-in yang menghitung bentuk normal konjungtif diizinkan.
7. Celah standar dilarang.
8. Ini adalah kode-golf ; jawaban terpendek (dalam byte) menang.

Maksima, 4 byte

pcnf

Cobalah secara Online!

Anda dapat menggunakan implies, eq, and, or operator untuk implikasi, kesetaraan, hubungannya, dan disjungsi masing-masing.

Anda akan membenci saya ....

Mathematica, 23 byte

#~BooleanConvert~"CNF"&

Input akan menggunakan Truedan Falsebukannya ⊤dan ⊥, tetapi sebaliknya akan terlihat sangat mirip dengan notasi dari pertanyaan: semua karakter ¬, ⇒, ⇔, ∧, dan ∨diakui dalam Mathematica (ketika input dengan karakter UTF-8 00AC, F523, 29E6, 2227 , dan 2228, masing-masing), dan tanda kurung bertindak seperti yang Anda harapkan.

Secara default, output akan menggunakan simbol yang disukai Mathematica: misalnya, test case terakhir akan menghasilkan (! P || ! Q || R) && (! P || Q || ! R)bukannya ((¬ P) ∨ ((¬ Q) ∨ R)) ∧ ((¬ P) ∨ (Q ∨ (¬ R))). Namun, mengubah fungsinya menjadi

TraditionalForm[#~BooleanConvert~"CNF"]&

akan membuat output terlihat cantik dan sesuai dengan simbol yang biasa ini:

JavaScript (ES6), 127 byte

f=(s,t='',p=s.match(/[A-Z]/),r=RegExp(p,'g'))=>p?'('+f(s.replace(r,1),t+'|'+p)+')&('+f(s.replace(r,0),t+'|!'+p)+')':eval(s)?1:0+t

Format I / O adalah sebagai berikut (dalam urutan diutamakan):

• (: (
• ): )
• ⊤: 1
• ⊥: 0
• ¬: !
• ⇒: <=
• ⇔: ==
• ∧: &
• ∨: |

Contoh:

P&(P<=R) -> ((1)&(0|P|!R))&((0|!P|R)&(0|!P|!R))
P==(!P) -> (0|P)&(0|!P)
(!P)|(Q==(P&R)) -> (((1)&(0|P|Q|!R))&((0|P|!Q|R)&(1)))&(((1)&(1))&((1)&(1)))

Fungsi ini ditulis ulang secara sepele untuk menghasilkan bentuk normal disjungtif:

f=(s,t='',p=s.match(/[A-Z]/),r=RegExp(p,'g'))=>p?'('f(s.replace(r,1),t+'&'+p)+')|('+f(s.replace(r,0),t+'&!'+p)+')':eval(s)?1+t:0

8 byte dapat disimpan dari versi ini jika saya diizinkan untuk menganggap prioritas di atas pada output juga, yang akan menghapus semua tanda kurung dari contoh output:

P&(P<=R) -> ((1&P&R)|(0))|((0)|(0))
P==(!P) -> (0)|(0)
(!P)|(Q==(P&R)) -> (((1&P&Q&R)|(0))|((0)|(1&P&!Q&!R)))|(((1&!P&Q&R)|(1&!P&Q&!R))|((1&!P&!Q&R)|(1&!P&!Q&!R)))