Forme normale négative

En logique mathématique, une formule est dite être en forme normale négative (abrégé FNN) si l'opérateur de la négation (${\displaystyle \lnot }$, non) est appliqué uniquement aux variables, et les seuls opérateurs booléens autorisés sont la conjonction (${\displaystyle \land }$, et) et la disjonction (${\displaystyle \lor }$, ou).

La forme normale négative n'est pas une forme canonique, par exemple, ${\displaystyle a\land (b\lor \lnot c)}$ et ${\displaystyle (a\land b)\lor (a\land \lnot c)}$ sont équivalentes, et sont toutes deux en forme normale négative.

En logique classique et beaucoup de logiques modales, chaque formule peut être représentée dans cette forme, par le remplacement des implications et des équivalences par leurs définitions, en utilisant les lois de De Morgan, et en éliminant les doubles négations. Ce processus peut être représenté en utilisant les règles de réécriture suivantes (Handbook of Automated Reasoning 1, p. 204.):

${\displaystyle A\Rightarrow B\to \lnot A\lor B}$

${\displaystyle \lnot (A\lor B)\to \lnot A\land \lnot B}$

${\displaystyle \lnot (A\land B)\to \lnot A\lor \lnot B}$

${\displaystyle \lnot \lnot A\to A}$

${\displaystyle \lnot \exists xA\to \forall x\lnot A}$

${\displaystyle \lnot \forall xA\to \exists x\lnot A}$

Une formule en forme normale négative peut être mise sous la forme normale conjonctive ou en forme normale disjonctive en appliquant la distributivité.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.