Objectif:

Écrivez un programme ou une fonction complète qui prend une formule en logique propositionnelle (désormais appelée expression ou expression logique ) et produit cette formule sous une forme normale conjonctive . Il y a deux constantes, ⊤et ⊥représentant vrai et faux, un opérateur unaire ¬représentant la négation, et les opérateurs binaires ⇒, ⇔, ∧et ∨représentant l' implication, l' équivalence, la conjonction et disjonction, respectivement , qui obéissent à toutes les opérations logiques habituelles ( la loi de De Morgan , l' élimination double négation , etc.).

La forme normale conjonctive est définie comme suit:

1. Toute expression atomique (y compris ⊤et ⊥) est sous forme normale conjonctive.
2. La négation de toute expression précédemment construite se présente sous une forme normale conjonctive.
3. La disjonction de deux expressions précédemment construites est sous forme normale conjonctive.
4. La conjonction de deux expressions précédemment construites est sous forme normale conjonctive.
5. Toute autre expression n'est pas sous forme normale conjonctive.

Toute expression logique peut être convertie (de manière non unique) en une expression logiquement équivalente sous forme normale conjonctive (voir cet algorithme ). Vous n'avez pas besoin d'utiliser cet algorithme particulier.

Contribution:

Vous pouvez prendre des entrées dans n'importe quel format pratique; par exemple, une expression logique symbolique (si votre langue le prend en charge), une chaîne, une autre structure de données. Vous n'avez pas besoin d'utiliser les mêmes symboles pour vrai, faux et les opérateurs logiques que je fais ici, mais votre choix doit être cohérent et vous devez expliquer vos choix dans votre réponse si ce n'est pas clair. Vous ne pouvez accepter aucune autre entrée ou encoder des informations supplémentaires dans votre format d'entrée. Vous devriez avoir un moyen d'exprimer un nombre arbitraire d'expressions atomiques; par exemple des entiers, des caractères, des chaînes, etc.

Production:

La formule sous forme normale conjonctive, encore une fois dans n'importe quel format pratique. Il n'est pas nécessaire qu'elle soit dans le même format que votre entrée, mais vous devez expliquer s'il y a des différences.

Cas de test:

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

Remarques:

1. Si l'expression d'entrée est une tautologie, ⊤serait une sortie valide. De même, si l'expression d'entrée est une contradiction, ⊥serait une sortie valide.
2. Vos formats d'entrée et de sortie doivent avoir un ordre d'opérations bien défini capable d'exprimer toutes les expressions logiques possibles. Vous pourriez avoir besoin de parenthèses.
3. Vous pouvez utiliser n'importe quel choix bien défini d'infixation, de préfixe ou de postfixation pour les opérations logiques. Si votre choix diffère de la norme (la négation est un préfixe, le reste est un infixe), veuillez l'expliquer dans votre réponse.
4. La forme normale conjonctive n'est pas unique en général (pas même jusqu'à la réorganisation). Il vous suffit de sortir un formulaire valide.
5. Quelle que soit la manière dont vous représentez les expressions atomiques, elles doivent être distinctes des constantes logiques, des opérateurs et des symboles de regroupement (si vous en avez).
6. Les fonctions intégrées qui calculent la forme normale conjonctive sont autorisées.
7. Les failles standard sont interdites.
8. C'est du code-golf ; la réponse la plus courte (en octets) l'emporte.

Maxima, 4 octets

pcnf

Essayez-le en ligne!

Vous pouvez utiliser implies, eq, and, or opérateurs pour l' implication, l' équivalence, la conjonction, et respectivement disjonction.

Tu vas me détester ...

Mathematica, 23 octets

#~BooleanConvert~"CNF"&

L'entrée utilisera Trueet au Falselieu de ⊤et ⊥, mais sinon sera très similaire à la notation de la question: tous les personnages ¬, ⇒, ⇔, ∧et ∨sont reconnus dans Mathematica (lorsque l' entrée avec UTF-8 caractères 00AC, F523, 29E6, 2227 et 2228, respectivement) et les parenthèses agissent comme vous vous en doutez.

Par défaut, la sortie utilisera les symboles préférés de Mathematica: par exemple, le dernier cas de test sortira à la (! P || ! Q || R) && (! P || Q || ! R)place de ((¬ P) ∨ ((¬ Q) ∨ R)) ∧ ((¬ P) ∨ (Q ∨ (¬ R))). Cependant, changer la fonction en

TraditionalForm[#~BooleanConvert~"CNF"]&

rendra la sortie jolie et conforme à ces symboles habituels:

JavaScript (ES6), 127 octets

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

Le format d'E / S est le suivant (par ordre de priorité):

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

Exemples:

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

La fonction est trivialement réécrite pour produire une forme normale disjonctive:

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 octets pourraient être enregistrés à partir de cette version si j'étais autorisé à assumer également la priorité ci-dessus sur la sortie, ce qui supprimerait toutes les parenthèses des exemples de sortie:

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