La logique d'ordre zéro, aussi connue sous le nom de logique propositionnelle, est une forme de logique où chaque proposition est soit vraie, soit fausse. Dans cette logique, il n'y a pas de quantificateurs ou de variables, ce qui la rend plus simple que d'autres formes de logique. Cependant, elle reste un outil puissant pour le raisonnement et la preuve de théorèmes.

I. Logique propositionnelle

I.I Morphologie

Définition : L’ensemble des formules d’ordre 0 est le plus petit ensemble :

$$ F_0 : \nu \subseteq F_0 \\ \phi \in F_0 \Rightarrow \lnot \phi \in F_0 \\ \phi_1 \in F_0 \land \phi_2 \in F_0 \Rightarrow (\phi_1 * \phi_2) \in F_0 $$

Exercice : Reconnaître les objets syntaxiques valides

$(A \Rightarrow (B \Rightarrow ( C \Rightarrow D )))$ — Valide
$((A \lor \lnot B)\Rightarrow \lnot E)$ — Valide
$()$ — Invalide
$\epsilon$ — Invalide
$\lnot\lnot\lnot$ — Invalide
$(A\Rightarrow(B\land))$ — Invalide

Exercice : fonction hauteur d’un arbre