La logique des propositions et des prédicats

Pour faire de la logique comme on en aura besoin par la suite, il s’agit d’abord de définir ce qu’est une proposition : c’est simplement un énoncé qui est soit vrai, soit faux, sans ambiguïté. Par exemple, les phrases suivantes sont des propositions :

• « Jules César est mort » (proposition vraie) ;
• « Mon chat est violet » (proposition à priori fausse, mais il suffit de le regarder pour en être sûr) ;
• « 2 + 2 = 5 » (c’est une proposition, bien entendu fausse) .

Par contre, les phrases suivantes ne sont pas des propositions :

• « Assieds-toi » ;
• « T’as du feu ? » (ce n’est pas une proposition, c’est une question) ;
• « $x + 3 = z$ » (la valeur de vérité de cette phrase dépend de $x$ et $z$, ce n’est pas une proposition).

La dernière phrase est en fait un prédicat : la valeur de vérité dépend des variables qu’elle contient (en l’occurrence $x$ et $z$). Si cet exemple parait un peu trop mathématique, un autre exemple de prédicat serait la phrase « votre pays se situe en Europe », dont la vérité dépend de « votre pays ». Ainsi, pour les lecteurs européens, ce prédicat sera vrai, tandis qu’il sera faux pour les autres.

Évidement, dans un souci d’abstraction, plutôt que de travailler avec des phrases, on travaille avec des variables propositionnelles, dont la valeur ne peut être que vrai ou faux. On peut utiliser différent symboles pour exprimer la valeur de vérité ou de fausseté (vert/rouge, oui/non, V/F, allumé/éteint, et j’en passe), mais on choisira pour la suite de représenter vrai en notant $1$ et faux en notant $0$. C’est une notation commune, qui rappelle le binaire qu’on aura l’occasion de rencontrer par la suite.

Ainsi, si $p$ représente la proposition « hier, à 15h, il pleuvait à Paris », alors $p=1$ s’il pleuvait hier, à l’heure sus-mentionnée, là-bas, 0 sinon. Un prédicat tel que « le lecteur vit en Allemagne » pourrait alors s’écrire $q(x)$, où $x$ est la nationalité du lecteur (oui, vous ), et $q(x)=1$ si vous vivez en Allemagne, $0$ sinon.

Évidement, dans une conversation, on débite un nombre impressionnant de propositions ou de prédicats, dont la valeur de vérité est d’ailleurs parfois laissée à l’appréciation des interlocuteurs. Or, nous ordonnons naturellement ces propositions en utilisant ce qu’on appelle des connecteurs.

Par exemple, dans la phrase « je n’aime ni courir, ni jouer au tennis », on peut constater l’usage de deux propositions « j’aime courir » ($p$, qui peut être soit vraie soit fausse) et « j’aime jouer au tennis » ($q$), toute deux niées (puisque je dis que je n’aime PAS ça), et assemblées par un connecteur « et » (puisque je dis que je n’aime pas courir ET que je n’aime pas jouer au tennis). On constate également que le langage humain n’exprime pas toujours clairement les choses.

Cet ensemble de propositions, rassemblées par des connecteurs logiques, s’appelle une formule.

Les connecteurs de base

Dans l’exemple précédent, on a déjà rencontré deux des trois connecteurs que j’appellerai de base. En effet, le premier des trois est la négation : soit une proposition $p$, sa négation peut s’écrire « $\lnot p$ ».

Afin de décrire les différentes situations, on utilise ce qu’on appelle une table de vérité : pour chacune des variables propositionnelles, on écrit les différentes valeurs qu’elles peuvent prendre, puis on écrit le résultat de la formule. Ainsi, $p$ peut prendre deux valeurs, qui sont $1$ et $0$. On a donc la table de vérité suivante :

On voit que, de manière assez logique, si $p=1$, $\lnot p = 0$, et inversement.

On a ensuite le connecteur ET (qu’on appelle aussi connecteur de conjonction), qui relie deux variables propositionnelles. Ici, la table de vérité comporte 4 lignes, car il existe 4 possibilités: soit $p$ et $q$ sont toute deux vraies ou fausses, soit elles ont des valeurs opposées. Et on obtient la table suivante :

On constate que le ET peut s’écrire $\land$ et que la formule $p \land q = 1$ seulement si $p=q=1$.

Finalement, le dernier connecteur de base qu’on a pas encore rencontré est le connecteur OU, encore appelé connecteur de disjonction. La table de vérité de ce connecteur est la suivante:

On constate que le OU peut s’écrire $\lor$ et que la formule $p\lor q =0$ seulement si $p=q=0$. Il s’agit en fait du ou non-exclusif, qu’on traduirait en français par « ou » de manière un peu ambiguë (on devrait écrire « et/ou », mais cela porterait à confusion), comme dans la phrase « le magasin est fermé les jours fériés ou durant nuit » (puisque s’il ne s’agissait pas d’un ou non-exclusif, le magasin devrait être ouvert la nuit des jours fériés).

Vérité d’une formule

Pour déterminer la vérité d’une formule, on doit déterminer la valeur de vérité pour les différentes valeurs des variables propositionnelles qui la composent. Par exemple, soit la formule $f(a,b,c) = a\land (b\lor c)$. Il est cette fois nécessaire de construire une table de vérité à 8 lignes (de manière générale, s’il y a $n$ variables propositionnelles, il y a aura $2^n$ lignes dans la table de vérité) :

On peut constater plusieurs choses dans cet exemple :

• On peut tout à fait réaliser la table de vérité pour des morceaux de la formule (ici $b\lor c$) avant de calculer la valeur de vérité de la formule elle même. Ici, il suffit ensuite de faire un ET entre la quatrième ($b\lor c)$ et la première colonne pour connaître la valeur de vérité de la formule complète.
• Remarquez la manière de remplir la table pour les variables $a$, $b$ et $c$ : quatre « 0 » suivit de 4 « 1 » pour la première colonne, une alternance de 2 « 0 » et 2 « 1 » pour la deuxième et une alternance de « 0 » et de « 1 » pour la troisième. En procédant comme cela, vous êtes sûr de couvrir les 8 cas de figure possible.
• On voit ici que $f(a,b,c)$ ne peut être vraie que si $a=1$. Cela provient de ce qu’on a observé précédemment : $a\land b=1$ si $a=b=1$.

D’autres connecteurs

On retrouve ensuite une série de connecteurs définis à partir des trois connecteurs de base¹ qu’on a vu plus haut.

L’implication

On utilise souvent, sous différentes formes, la phrase « $p$ implique $q$ », même si c’est plus souvent sous la forme « si … alors … », par exemple « s’il pleut, alors je reste à la maison » ou encore « $n=0 \Rightarrow n+1 > 0$ ». La table de vérité de cet opérateur est la suivante :

On peut constater que:

• L’opérateur d’implication peut s’écrire $\Rightarrow$ ;
• $p\Rightarrow q$ est équivalent à $\lnot p \lor q$ (dernière colonne) ;
• La formule est fausse lorsque $p=1$ et $q=0$, ce qui permet de lire $p \Rightarrow q$ comme « $p$ seulement si $q$ ». Autrement dit, « du vrai n’implique jamais du faux » et « du faux implique n’importe quoi ».
• On peut encore dire « $p$ suffit à $q$ » ou encore « $q$ est nécessaire pour $p$ ». Si je reprends l’exemple « $n=0 \Rightarrow n+1 > 0$ », alors on obtient « que $n=0$ suffit pour que $n+1>0$ », et « $n+1>0$ est nécessaire pour que $n=0$ »;
• Dans $p \Rightarrow q$ , $p$ est aussi nommé l’antécédent (ou l’hypothèse) et $q$ est nommé le conséquent (ou la thèse).

À noter que si on a $p\Rightarrow q$, on peut retrouver

• Sa réciproque, qui s’écrit $q\Rightarrow p$ ;
• Sa contraposée, qui s’écrit $\lnot q \Rightarrow \lnot p$ ;
• Son inverse, qui s’écrit $\lnot p \Rightarrow \lnot q$.

Néanmoins, ce n’est pas parce qu’une implication est vraie que sa réciproque ou son inverse l’est également ! Ainsi si je reprends l’implication $n=0 \Rightarrow n+1 > 0$ est vraie, mais sa récriproque, $n+1>0 \Rightarrow n=0$ n’est pas vraie (du vrai n’implique jamais du faux) ! De même, son inverse, $n\neq 0 \Rightarrow n+1 \leq 0$ n’est pas vraie non plus (pour la même raison). Par contre, et on le verra plus loin, la contraposée d’une implication est toujours de même valeur de vérité que l’implication elle-même, et dans notre cas l’implication $n+1\leq 0 \Rightarrow n\neq 0$ est bel et bien vraie aussi.

L’équivalence

Second connecteur relativement important, l’équivalence. Sa table de vérité est la suivante:

On constate, assez logiquement, que:

• $p \Leftrightarrow q$ est vrai si $p=q$ ;
• $p \Leftrightarrow q$ équivaut à ce que $p \Rightarrow q$ et sa réciproque soient toutes deux vraies (ce n’est pas forcément le cas, je le répète une fois encore). Autrement dit, « $p$ implique $q$ et $q$ implique $p$ », ou encore « $p$ est une condition nécessaire et suffisante à $q$ » ou encore « $p$ si et seulement si $q$ » ;
• On retrouve parfois ce connecteur écrit $p\equiv q$ (littéralement, $p=q$).

Ce connecteur est très employé en mathématiques, dans les démonstrations.

… Et d’autres

On retrouve finalement trois connecteurs logiques ayant leur utilité en électronique (voir plus loin) ou en informatique.

• NAND (« NON ET ») et NOR (« NON OU »), respectivement $p \uparrow q$ et $p \downarrow q$ ;
• XOR (le ou exclusif ou disjonction exclusive), qu’on écrit souvent $p\oplus q$ (ou encore $p\neq q$).

Les tables de vérités de ces connecteurs sont :

On peut par ailleurs en déduire que

• $p\uparrow q \Leftrightarrow \lnot (p\land q) \Leftrightarrow \lnot p \lor \lnot q$ ;
• $p\downarrow q \Leftrightarrow \lnot (p\lor q) \Leftrightarrow \lnot p \land \lnot q$ ;
• $p \oplus q \Leftrightarrow \lnot (p \Leftrightarrow q)$ ;

Tautologies

Une tautologie est une formule qui est toujours vraie quelle que soit la valeur des variables qui la compose. Ainsi, les trois dernières définitions du paragraphe précédent sont des tautologies. On peut le vérifier par tables de vérité.

Pour vous entraîner, vous pouvez vérifier que $\vDash\lnot (p\land q) \Leftrightarrow \lnot p \lor \lnot q$ (le symbole $\vDash$ permet d’indiquer qu’il s’agit d’une tautologie).

Vous pouvez également vérifier que $\vDash p\Rightarrow q \Leftrightarrow \lnot q \Rightarrow \lnot p$:

Il est tout à fait possible de faire des tables de vérités avec des prédicats, comme on l’a fait pour les propositions : ce n’est pas parce que la valeur de $p(x)$ change avec $x$ que $p(x)$ ne peut pas être vrai ou faux.

Par contre, si on rajoute un quantificateur devant un prédicat qui caractérise la (ou les) variable(s) de ce prédicat, alors on obtient une proposition. Et on va distinguer 3 quantificateurs :

• Le quantificateur universel, représenté par $\forall$. Ainsi, $\forall x: p(x)$ est une proposition vraie si pour tout $x$, $p(x)=1$. On le retrouve en général en mathématique, par exemple dans la proposition $\forall x\in\mathbb{N}:x\geq 0$ (aka « tout nombre appartenant à l’ensemble¹ des naturels est positif »).
• Le quantificateur existentiel, représenté par $\exists$. Ainsi la proposition $\exists x: p(x)$ est vraie s’il existe au moins un $x$ tel que $p(x)=1$. Une version plus dure de ce quantificateur est celui de stricte existentialité, $\exists !$, la proposition $\exists ! x : p(x)$, n’étant alors vraie que s’il existe un et un seul $x$ tel que $p(x)=1$.

À noter qu’un quantificateur a une priorité absolue, ce qui signifie qu’il s’applique sur tout ce qui suit :

$\forall a, \underbrace{\forall b: \underbrace{p(a,b)}_{\text{portée de }\forall b}}_{\text{portée de }\forall a}.$

Ainsi, l’ordre des quantificateurs a de l’importance. Dès lors, les deux propositions suivantes ne sont pas équivalentes :

1. $\forall x \in\mathbb{R}, \exists y \in \mathbb{R}: x^2+y<0$ (pour tout réel $x$, il existe un réel $y$ tel que $x^2+y<0$) ;
2. $\exists y \in \mathbb{R}, \forall x \in\mathbb{R}: x^2+y<0$ (il existe un réel $y$ tel que pour tout réel $x$, $x^2+y<0$).

La première proposition est vraie (il suffit de prendre $y=-x^2-1$) alors que la seconde est bien entendu fausse (il n’existe pas de réel $y$ qui satisfera le prédicat pour tout les $x$ possibles parmi les réels).