Licence CC BY-NC

La logique des propositions et des prédicats

Publié :

Dans ce premier chapitre, nous allons découvrir les bases de la logique combinatoire. Même si ce mot peu faire peur, il désigne en fait quelque chose d’assez simple :)

C'est quoi, une proposition ?

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=zx + 3 = z » (la valeur de vérité de cette phrase dépend de xx et zz, 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 xx et zz). 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 11 et faux en notant 00. C’est une notation commune, qui rappelle le binaire qu’on aura l’occasion de rencontrer par la suite.

Ainsi, si pp représente la proposition « hier, à 15h, il pleuvait à Paris », alors p=1p=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)q(x), où xx est la nationalité du lecteur (oui, vous ;) ), et q(x)=1q(x)=1 si vous vivez en Allemagne, 00 sinon.

Pour être plus formel, on admet en fait les 2 axiomes (règles) suivants, qu’on a en fait déjà énoncés :

  • Le principe du tiers-exclu : une proposition est vraie ou fausse, pas autre chose ;
  • Le principe de non-contradiction : une proposition ne peut être vraie et fausse en même temps, autrement dit une variable propositionnelle ou un prédicat vaut soit « 0 », soit « 1 ». C’est pour ça que j’ai commencé par dire que la valeur d’une proposition devait être déterminée de manière non-ambiguë.

Il existe d’autres formes de logiques, qui n’admettent pas l’un ou l’autre de ces axiomes, par exemple la logique floue, qui définit qu’une variable propositionnelle peut valoir n’importe quel réel entre 0 et 1. Bien que ce soit très intéressant, ce n’est pas le sujet ici :)

Assembler des propositions avec les connecteurs

É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 » (pp, qui peut être soit vraie soit fausse) et « j’aime jouer au tennis » (qq), 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 pp, sa négation peut s’écrire « ¬p\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, pp peut prendre deux valeurs, qui sont 11 et 00. On a donc la table de vérité suivante :

pp ¬p\lnot p
1 0
0 1

On voit que, de manière assez logique, si p=1p=1, ¬p=0\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 pp et qq sont toute deux vraies ou fausses, soit elles ont des valeurs opposées. Et on obtient la table suivante :

pp qq pqp \land q
0 0 0
0 1 0
1 0 0
1 1 1

On constate que le ET peut s’écrire \land et que la formule pq=1p \land q = 1 seulement si p=q=1p=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:

pp qq pqp \lor q
0 0 0
0 1 1
1 0 1
1 1 1

On constate que le OU peut s’écrire \lor et que la formule pq=0p\lor q =0 seulement si p=q=0p=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).

Entre autres propriétés qu’on verra au chapitre prochain, ET et OU sont commutatifs (pq=qpp\land q=q\land p, par exemple) et associatifs [c’est-à-dire que p(qr)=(pq)rp\land (q\land r)= (p\land q)\land r, par exemple]. Les parenthèses gardent leur sens ici (on effectue d’abord l’opération entre parenthèse).

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(bc)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 nn variables propositionnelles, il y a aura 2n2^n lignes dans la table de vérité) :

aa bb cc bcb\lor c f(a,b,c)=a(bc)f(a,b,c) =a\land( b\lor c)
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 1 0
1 0 0 0 0
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1

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 bcb\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 (bc)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 aa, bb et cc : 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)f(a,b,c) ne peut être vraie que si a=1a=1. Cela provient de ce qu’on a observé précédemment : ab=1a\land b=1 si a=b=1a=b=1.

D’autres connecteurs

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

L’implication

On utilise souvent, sous différentes formes, la phrase « pp implique qq », 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=0n+1>0n=0 \Rightarrow n+1 > 0 ». La table de vérité de cet opérateur est la suivante :

pp qq pqp \Rightarrow q ¬pq\lnot p \lor q
0 0 1 1
0 1 1 1
1 0 0 0
1 1 1 1

On peut constater que:

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

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

  • Sa réciproque, qui s’écrit qpq\Rightarrow p ;
  • Sa contraposée, qui s’écrit ¬q¬p\lnot q \Rightarrow \lnot p ;
  • Son inverse, qui s’écrit ¬p¬q\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=0n+1>0n=0 \Rightarrow n+1 > 0 est vraie, mais sa récriproque, n+1>0n=0n+1>0 \Rightarrow n=0 n’est pas vraie (du vrai n’implique jamais du faux) ! De même, son inverse, n0n+10n\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+10n0n+1\leq 0 \Rightarrow n\neq 0 est bel et bien vraie aussi.

Attention à la négation des propositions mathématiques. Si pp est la proposition n=0n=0 et qq est la proposition n<0n < 0, ¬p\lnot p équivaut à n0n \neq 0, mais ¬q\lnot q correspond à n0n \geq 0 (si ce n’est pas strictement plus petit que 0, c’est soit égal à 0, soit supérieur) !

L’équivalence

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

pp qq pqp \Leftrightarrow q (pq)(qp)(p \Rightarrow q) \land (q \Rightarrow p)
0 0 1 1
0 1 0 0
1 0 0 0
1 1 1 1

On constate, assez logiquement, que:

  • pqp \Leftrightarrow q est vrai si p=qp=q ;
  • pqp \Leftrightarrow q équivaut à ce que pqp \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, « pp implique qq et qq implique pp », ou encore « pp est une condition nécessaire et suffisante à qq » ou encore « pp si et seulement si qq » ;
  • On retrouve parfois ce connecteur écrit pqp\equiv q (littéralement, p=qp=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 pqp \uparrow q et pqp \downarrow q ;
  • XOR (le ou exclusif ou disjonction exclusive), qu’on écrit souvent pqp\oplus q (ou encore pqp\neq q).

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

pp qq pqp \uparrow q pqp\downarrow q pqp\oplus q
0 0 1 1 0
0 1 1 0 1
1 0 1 0 1
1 1 0 0 0

On peut par ailleurs en déduire que

  • pq¬(pq)¬p¬qp\uparrow q \Leftrightarrow \lnot (p\land q) \Leftrightarrow \lnot p \lor \lnot q ;
  • pq¬(pq)¬p¬qp\downarrow q \Leftrightarrow \lnot (p\lor q) \Leftrightarrow \lnot p \land \lnot q ;
  • pq¬(pq)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 ¬(pq)¬p¬q\vDash\lnot (p\land q) \Leftrightarrow \lnot p \lor \lnot q (le symbole \vDash permet d’indiquer qu’il s’agit d’une tautologie).

pp qq pqp \land q ¬(pq)\lnot (p\land q) ¬p¬q\lnot p \lor \lnot q
0 0 0 1 1
0 1 0 1 1
1 0 0 1 1
1 1 1 0 0

On voit bien que les deux dernières colonnes sont équivalentes, donc la tautologie ¬(pq)¬p¬q\vDash\lnot (p\land q) \Leftrightarrow \lnot p \lor \lnot q est respectée. Cette tautologie est d’ailleurs une des deux lois de De Morgan qu’on verra au prochain chapitre.

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

pp qq pqp \Rightarrow q ¬q\lnot q ¬p\lnot p ¬q¬p\lnot q \Rightarrow \lnot p
0 0 1 1 1 1
0 1 1 0 1 1
1 0 0 1 0 0
1 1 1 0 0 1

On voit que la troisième et la dernière colonne sont équivalentes, il s’agit donc bien d’une tautologie, une implication et sa contraposée sont bien équivalentes.


  1. On peut en fait très bien définir « ET » à partir de « OU » et de la négation, ou « OU » à partir de « ET » et de la négation. Mais vous verrez par la suite pourquoi j’insiste sur ces 3 connecteurs.

C'est toujours utile: les prédicats et les quantificateurs

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

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

a:b:p(a,b)porte de eˊbporte de eˊa.\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. xR:yR:x2+y<0\forall x \in\mathbb{R}: \exists y \in \mathbb{R}: x^2+y<0 (pour tout réel xx, il existe un réel yy tel que x2+y<0x^2+y<0) ;
  2. yR:xR:x2+y<0\exists y \in \mathbb{R}: \forall x \in\mathbb{R}: x^2+y<0 (il existe un réel yy tel que pour tout réel xx, x2+y<0x^2+y<0).

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


  1. Je ne vais pas m’étendre sur la notion d’ensemble, qui a déjà été abordée par c_page, mais je vous rappelle qu’il s’agit d’un « paquet » d’objets mathématiques quelconques (un ensemble de valeurs possibles, pour le dire autrement).


Dans ce premier chapitre, on a donc vu qu’il existait des propositions (et des prédicats) que l’on pouvait représenter en utilisant des variables propositionnelles, qu’on pouvait associer en formules grâce à des connecteurs logiques, dont les principaux sont le ET, le OU et la négation (même si on a pu ensuite en dériver d’autre). Je ne souhaitais, ceci dit, pas trop m’appesantir là-dessus, car le prochain chapitre va présenter les choses de manière un peu plus systématique.

À tout de suite :)