Cel:

Napisz kompletny program lub funkcję, która przyjmuje formułę w logice zdaniowej (odtąd nazywane wyrażeniem lub wyrażeniem logicznym ) i wypisuje tę formułę w spójnej postaci normalnej . Istnieją dwa stałe, ⊤a ⊥co stanowi prawdziwe i fałszywe, operator jednoargumentowy ¬reprezentujący negację i operatorów binarnych ⇒, ⇔, ∧oraz ∨reprezentujących implikację równoważności koniunkcję i alternatywę, odpowiednio których przestrzegać wszystkich typowych operacji logicznych ( prawo DeMorgan za , eliminacja podwójna negacja itp.).

Łączna postać normalna jest zdefiniowana następująco:

1. Każda ekspresja atomowa (w tym ⊤i ⊥) ma postać łączącą normalną.
2. Negacja jakiegokolwiek wcześniej skonstruowanego wyrażenia jest w spójnej postaci normalnej.
3. Odłączenie dowolnych dwóch wcześniej skonstruowanych wyrażeń ma postać łączącą normalną.
4. Połączenie dowolnych dwóch wcześniej skonstruowanych wyrażeń ma postać łączącą normalną.
5. Każde inne wyrażenie nie jest w spójnej normalnej formie.

Każde wyrażenie logiczne można przekształcić (niejednokrotnie) w logicznie równoważne wyrażenie w spójnej postaci normalnej (patrz ten algorytm ). Nie musisz używać tego konkretnego algorytmu.

Wejście:

Możesz przyjmować dane wejściowe w dowolnym dogodnym formacie; np. symboliczne wyrażenie logiczne (jeśli twój język to obsługuje), ciąg znaków, inna struktura danych. Nie musisz używać tych samych symboli dla prawdy, fałszu i operatorów logicznych, jak ja tutaj, ale twój wybór powinien być spójny i powinieneś wyjaśnić swoje wybory w swojej odpowiedzi, jeśli nie jest to jasne. Nie możesz akceptować żadnych innych danych wejściowych ani kodować żadnych dodatkowych informacji w swoim formacie wejściowym. Powinieneś mieć jakiś sposób na wyrażenie dowolnej liczby wyrażeń atomowych; np. liczby całkowite, znaki, ciągi itp.

Wynik:

Formuła w spójnej normalnej formie, ponownie w dowolnym dogodnym formacie. Nie musi być w tym samym formacie co dane wejściowe, ale powinieneś wyjaśnić, czy są jakieś różnice.

Przypadki testowe:

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

Uwagi:

1. Jeśli wyrażenie wejściowe jest tautologią, ⊤byłoby prawidłowym wyjściem. Podobnie, jeśli wyrażenie wejściowe jest sprzecznością, ⊥byłoby prawidłowym wyjściem.
2. Zarówno formaty wejściowe, jak i wyjściowe powinny mieć dobrze zdefiniowaną kolejność operacji zdolną do wyrażania wszystkich możliwych wyrażeń logicznych. Możesz potrzebować jakiegoś nawiasu.
3. Do operacji logicznych można użyć dowolnego dobrze zdefiniowanego wyboru notacji infix, prefix lub postfiks. Jeśli twój wybór różni się od standardowego (negacja jest przedrostkiem, reszta jest nieoznaczona), wyjaśnij to w swojej odpowiedzi.
4. Łączna postać normalna nie jest ogólnie wyjątkowa (nawet do zmiany kolejności). Musisz tylko do wyjścia z poprawną formę.
5. Bez względu na to, jak reprezentujesz wyrażenia atomowe, muszą one różnić się od stałych logicznych, operatorów i symboli grupujących (jeśli je masz).
6. Dozwolone są wbudowane funkcje obliczające spójną postać normalną.
7. Standardowe luki są zabronione.
8. To jest golf golfowy ; najkrótsza odpowiedź (w bajtach) wygrywa.

Maxima, 4 bajty

pcnf

Wypróbuj online!

Można użyć implies, eq, and, or operatorzy dla implikacji, równoważności, połączeniu i alternatywy odpowiednio.

Nienawidzisz mnie ....

Mathematica, 23 bajty

#~BooleanConvert~"CNF"&

Wejście użyje Truei Falsezamiast ⊤a ⊥, ale w przeciwnym razie będzie wyglądać bardzo podobnie do notacji pytanie: wszystkie znaki ¬, ⇒, ⇔, ∧, i ∨są ujmowane w Mathematica (gdy wejście ze znaków UTF-8 00AC, F523, 29E6, 2227 i 2228), a nawiasy działają zgodnie z oczekiwaniami.

Domyślnie w danych wyjściowych będą używane preferowane symbole Mathematica: na przykład (! P || ! Q || R) && (! P || Q || ! R)zamiast tego zostanie wyświetlony ostatni przypadek testowy ((¬ P) ∨ ((¬ Q) ∨ R)) ∧ ((¬ P) ∨ (Q ∨ (¬ R))). Jednak zmiana funkcji na

TraditionalForm[#~BooleanConvert~"CNF"]&

sprawi, że wynik będzie wyglądał ładnie i będzie zgodny z tymi zwykłymi symbolami:

JavaScript (ES6), 127 bajtów

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 we / wy jest następujący (w kolejności pierwszeństwa):

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

Przykłady:

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

Ta funkcja została w trywialny sposób przepisana, aby uzyskać rozłączną postać normalną:

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 bajtów można by zapisać z tej wersji, gdyby pozwolono mi przyjąć powyższy priorytet również na wyjściu, co usunęłoby wszystkie nawiasy z przykładów wyjściowych:

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