Propositions, connecteurs et tables de vérité

Une proposition logique est un énoncé qui est soit vrai, soit faux, jamais les deux. Les connecteurs logiques (non, et, ou, ou exclusif) combinent des propositions pour en former de nouvelles, et une table de vérité donne la valeur du résultat pour chaque combinaison possible de valeurs. Ce chapitre pose ces trois outils, sur lesquels repose tout le reste du cours.

C'est quoi une proposition logique ?

Une proposition est une phrase déclarative dont on peut dire, sans ambiguïté, si elle est vraie ou fausse. Cette réponse s'appelle sa valeur de vérité : V (vrai) ou F (faux). En informatique et dans la suite du cours, on écrit aussi 1 pour vrai et 0 pour faux.

La dernière ligne est importante. « x > 5 » n'est ni vrai ni faux tant qu'on ne sait pas ce que vaut x : c'est un prédicat, une phrase à trou qui devient une proposition dès qu'on remplace x par une valeur (« 7 > 5 » est vraie, « 2 > 5 » est fausse). Les prédicats ont leur propre chapitre : calcul des prédicats et quantificateurs.

Le calcul propositionnel repose sur deux principes que tu appliques sans y penser :

• non-contradiction : une proposition n'est jamais vraie et fausse à la fois ;
• tiers exclu : une proposition est toujours vraie ou fausse, il n'y a pas de troisième valeur.

On désigne une proposition quelconque par une lettre majuscule : P, Q, R. Ces lettres sont des variables propositionnelles : chacune peut valoir V ou F, et le but du calcul est de savoir ce que vaut une formule pour chaque cas.

La négation : non P

La négation de P, notée non P, ¬P ou P̅ (P surmonté d'une barre), est vraie quand P est fausse et fausse quand P est vraie.

Nier une proposition, c'est écrire son contraire exact, pas son opposé intuitif.

• La négation de « le disque est plein » est « le disque n'est pas plein », pas « le disque est vide ».
• La négation de « x > 5 » est « x ≤ 5 », pas « x < 5 » : le cas x = 5 doit rester couvert.
• La négation de « le mot de passe fait au moins 12 caractères » est « le mot de passe fait au plus 11 caractères ».

La conjonction : P et Q

La conjonction de P et Q, notée P et Q ou P ∧ Q, est vraie seulement quand P et Q sont vraies toutes les deux.

Exemple : un compte peut se connecter si « le mot de passe est correct » et « le compte n'est pas verrouillé ». Une seule condition fausse suffit à refuser la connexion.

La disjonction : P ou Q

La disjonction de P et Q, notée P ou Q ou P ∨ Q, est vraie dès qu'au moins une des deux propositions est vraie. Elle n'est fausse que si P et Q sont fausses toutes les deux.

Ce « ou » est inclusif : il accepte le cas où les deux sont vraies. C'est celui des mathématiques et de tous les langages de programmation. Quand le site d'un hébergeur annonce « paiement par carte ou par virement », rien ne t'interdit d'avoir les deux moyens de paiement.

Le ou exclusif (XOR)

En français courant, « ou » est parfois exclusif : « fromage ou dessert » sur un menu veut dire l'un ou l'autre, pas les deux. Le ou exclusif, noté P ⊕ Q (en anglais XOR, exclusive or), est vrai quand exactement une des deux propositions est vraie.

Le ou exclusif n'est pas un connecteur de base : il s'écrit avec les autres. « Exactement un des deux » se dit « l'un ou l'autre, mais pas les deux » :

P ⊕ Q ≡ (P ∨ Q) ∧ ¬(P ∧ Q)

Il sert énormément en informatique : chiffrement, contrôle de parité, RAID 5. Ses propriétés sont détaillées au chapitre portes logiques, XOR, NAND et NOR.

Récapitulatif des notations

Chaque discipline a ses notations. Le programme du BTS demande de reconnaître les principales ; dans les sujets d'E3, la notation booléenne (dernière colonne mathématique) est la plus fréquente.

Construire une table de vérité pas à pas

Une formule est une combinaison de variables et de connecteurs, comme ¬P ∨ (P ∧ Q). Sa table de vérité donne sa valeur pour chaque combinaison de valeurs des variables. La méthode ne change jamais :

1. Compter les lignes. Avec n variables, il y a 2ⁿ combinaisons : 4 lignes pour 2 variables, 8 pour 3, 16 pour 4. Chaque variable double le nombre de cas.
2. Remplir les colonnes des variables dans un ordre systématique, pour n'oublier aucun cas. La méthode la plus sûre : compter en binaire de 000 à 111. La dernière variable alterne une ligne sur deux, l'avant-dernière deux lignes sur deux, la précédente quatre lignes sur quatre.
3. Ajouter une colonne par sous-formule, de l'intérieur vers l'extérieur : d'abord les négations des variables, puis les parenthèses, puis la formule entière.
4. Calculer colonne par colonne, en appliquant la table du connecteur à deux colonnes déjà remplies.

Exemple à deux variables : ¬P ∨ (P ∧ Q). Deux variables, donc quatre lignes. On calcule ¬P, puis P ∧ Q, puis la disjonction des deux colonnes obtenues.

La formule n'est fausse que sur la ligne P = V, Q = F. C'est exactement la table de l'implication P ⇒ Q, que tu verras au chapitre suivant : deux formules différentes peuvent avoir la même table.

Exemple à trois variables : (P ∨ Q) ∧ ¬R. Trois variables, donc huit lignes.

La formule est vraie sur trois lignes : celles où R est faux et où P ou Q est vrai.

Priorité des connecteurs

Comme × passe avant + en arithmétique, les connecteurs ont un ordre de priorité :

1. la négation ¬ s'applique d'abord, à ce qui la suit immédiatement ;
2. la conjonction ∧ ensuite ;
3. la disjonction ∨ en dernier (et ⊕, ⇒, ⇔ après elle).

Ainsi ¬P ∧ Q se lit (¬P) ∧ Q, et P ∨ Q ∧ R se lit P ∨ (Q ∧ R). Ce n'est pas un détail : avec P vraie, Q fausse et R fausse, P ∨ (Q ∧ R) vaut V alors que (P ∨ Q) ∧ R vaut F.

Les langages de programmation suivent la même règle (not avant and avant or en Python, ! avant && avant || en C#, Java, JavaScript et PHP), comme SQL (NOT avant AND avant OR). Le piège classique en SQL :

-- Faux : se lit statut = 'ouvert' OR (statut = 'en cours' AND priorite = 'haute')
SELECT * FROM ticket WHERE statut = 'ouvert' OR statut = 'en cours' AND priorite = 'haute';

-- Juste : les tickets ouverts ou en cours, de priorité haute
SELECT * FROM ticket WHERE (statut = 'ouvert' OR statut = 'en cours') AND priorite = 'haute';

Tautologie, contradiction et formules équivalentes

Certaines formules ont une table de vérité particulière.

• Une tautologie est vraie sur toutes les lignes, quelles que soient les valeurs des variables. Exemple : P ∨ ¬P (« le serveur répond ou il ne répond pas »).
• Une contradiction (ou antilogie) est fausse sur toutes les lignes. Exemple : P ∧ ¬P.
• Une formule ni toujours vraie ni toujours fausse est dite contingente : c'est le cas de la plupart des formules, comme P ∧ Q.

Deux formules sont logiquement équivalentes quand elles ont la même valeur de vérité sur chaque ligne de leur table. On le note avec ≡ (ou ⇔ entre les deux formules). Tu viens d'en voir un exemple : ¬P ∨ (P ∧ Q) ≡ P ⇒ Q. Démontrer une équivalence par une table de vérité est la méthode la plus sûre : tu calcules les deux colonnes et tu vérifies qu'elles sont identiques ligne par ligne.

Exercices