Tous les termes employés par la calculatrice, les guides et les exercices, définis au même endroit.
Cherchez un terme, voyez sa notation et ouvrez l'exemple dans la calculatrice pour l'observer à l'œuvre. Les termes définis ici sont mis en évidence à leur première apparition dans un guide.
Les 62 termes
L'étude des conclusions qui découlent réellement de telles hypothèses.
La logique étudie la forme du raisonnement plutôt que son contenu. La logique formelle remplace les phrases par des symboles, si bien que la question de savoir si une conclusion découle des prémisses se règle par la seule forme de l'argument, et se vérifie mécaniquement.
Un énoncé qui est vrai ou faux, mais pas les deux.
Une proposition est un énoncé déclaratif doté d'exactement une valeur de vérité. « Il pleut » est une proposition ; une question ou un ordre n'en est pas une, car il n'y a rien en eux qui puisse être vrai ou faux.
L'une des deux valeurs qu'une proposition peut prendre : vrai ou faux.
La logique classique attribue à chaque proposition exactement une de deux valeurs de vérité, notées ⊤ et ⊥ (ou 1 et 0). Chaque ligne d'une table de vérité est une attribution de valeurs aux variables, et la valeur que la formule y prend.
Une proposition qui ne contient aucun connecteur.
Une proposition atomique ne se décompose pas en propositions plus petites : elle ne contient ni négation, ni conjonction, ni aucun autre connecteur. Tout le reste est composé, construit à partir d'atomes, et sa valeur de vérité découle de la leur.
Une lettre comme p ou A tenant lieu d'une proposition quelconque.
Une variable propositionnelle représente n'importe quelle proposition. La calculatrice accepte les lettres seules comme variables et donne à chacune une colonne de la table de vérité, avec une ligne par combinaison de valeurs possibles.
Dans la calculatricep → qUne suite de symboles que la grammaire du langage autorise vraiment.
Une formule bien formée se construit selon les règles : une variable en est une, et toute formule obtenue à partir de formules plus petites par un connecteur aussi. « p ∧ ∨ q » n'en est pas une, et c'est pourquoi la calculatrice signale une erreur au lieu de deviner.
Une attribution de valeurs de vérité à toutes les variables d'une formule.
Une interprétation dit ce que vaut chaque variable et fixe donc la valeur de la formule entière. Une formule à n variables possède 2ⁿ interprétations, qui sont exactement les lignes de sa table de vérité.
Un ensemble de prémisses avancées à l'appui d'une conclusion.
Un argument affirme que sa conclusion découle de ses prémisses. Saisissez-en un dans la calculatrice avec un taquet — prémisses avant, conclusion après — et chaque ligne sera examinée pour trouver un cas où les prémisses tiennent et la conclusion échoue.
Dans la calculatricep → q, p ⊨ qUn énoncé qu'un argument suppose pour atteindre sa conclusion.
Les prémisses sont le point de départ d'un argument. La validité demande seulement si la conclusion tient partout où toutes les prémisses tiennent ; savoir si celles-ci sont vraies est une autre question, celle qu'ajoute la solidité.
Dans la calculatricep → q, p ⊨ qL'énoncé qu'un argument cherche à établir.
La conclusion est ce que les prémisses soutiennent. Dans la calculatrice, c'est l'expression qui suit le taquet, et un argument est valide quand aucune interprétation ne rend les prémisses vraies tout en rendant la conclusion fausse.
Dans la calculatricep → q, p ⊨ qUn symbole qui construit une proposition composée à partir d'autres.
Un connecteur tel que ¬, ∧, ∨, → ou ↔ combine des propositions en une plus grande dont la valeur de vérité ne dépend que des leurs. C'est cette dépendance qu'enregistre une table de vérité, une ligne par combinaison d'entrées.
Inverse une valeur de vérité : ¬p est vraie exactement quand p est fausse.
La négation est le seul connecteur unaire de la logique propositionnelle. Notée ¬p, ~p ou !p, elle change le vrai en faux et le faux en vrai, de sorte que nier deux fois redonne la proposition de départ.
Dans la calculatrice¬pVraie seulement quand ses deux parties sont vraies : p ∧ q.
Une conjonction affirme ses deux parties, appelées conjoints. Elle est vraie dans exactement une ligne de sa table de vérité — celle où les deux conjoints sont vrais — ce qui en fait le plus strict des connecteurs binaires.
Dans la calculatricep ∧ qVraie quand au moins une partie est vraie : p ∨ q.
En logique, la disjonction est inclusive : p ∨ q est vraie quand p est vraie, quand q est vraie et quand les deux le sont. La lecture exclusive de « ou », vraie seulement si les parties diffèrent, est un connecteur distinct.
Dans la calculatricep ∨ qVraie quand exactement une des deux propositions est vraie.
La disjonction exclusive, notée ⊕ ou XOR, tient quand ses parties diffèrent et échoue quand elles s'accordent. C'est la négation du biconditionnel, et elle s'écrit aussi (p ∨ q) ∧ ¬(p ∧ q).
Dans la calculatrice(p ∨ q) ∧ ¬(p ∧ q)p → q, faux seulement quand p est vrai et q faux.
Le conditionnel matériel ne dit rien de plus que « il n'arrive pas que l'antécédent soit vrai et le conséquent faux », si bien qu'il tient automatiquement dès que l'antécédent échoue. C'est pourquoi p → q équivaut à ¬p ∨ q.
Dans la calculatricep → qp ↔ q, vrai quand les deux parties ont la même valeur de vérité.
Le biconditionnel affirme chaque côté sous la condition de l'autre : il est vrai quand les deux parties sont vraies et quand toutes deux sont fausses. Un biconditionnel qui est une tautologie exprime exactement une équivalence logique.
Dans la calculatricep ↔ qLa partie « si » d'un conditionnel : le p de p → q.
L'antécédent est la condition dont dépend un conditionnel. Quand il est faux, le conditionnel entier est vrai quel que soit le conséquent, ce qui explique la plupart des surprises de la table de →.
Dans la calculatricep → qLa partie « alors » d'un conditionnel : le q de p → q.
Le conséquent est ce qu'un conditionnel affirme devoir suivre si son antécédent tient. Un conséquent vrai rend le conditionnel vrai, mais ne rend pas l'antécédent vrai : l'inférer est une erreur formelle.
Dans la calculatricep → qLe conditionnel dont les deux parties sont échangées : q → p.
La réciproque de p → q est q → p, et les deux ne sont pas équivalentes : la calculatrice trouve une ligne où l'une tient et l'autre échoue. Les traiter comme interchangeables, c'est affirmer le conséquent.
Dans la calculatriceq → p¬q → ¬p, qui a toujours la même valeur de vérité que p → q.
La contraposée nie les deux parties d'un conditionnel et les échange. Contrairement à la réciproque, elle est réellement équivalente à l'original, ce qui rend la démonstration par contraposition légitime en mathématiques.
Dans la calculatrice(p → q) ≡ (¬q → ¬p)La négation d'une conjonction : vraie sauf si les deux entrées sont vraies.
NON-ET, noté ↑, est ¬(p ∧ q). Il est fonctionnellement complet : tout autre connecteur peut se construire à partir de lui seul, ce qui en fait un pilier de la conception des circuits numériques.
Dans la calculatrice¬(p ∧ q)La négation d'une disjonction : vraie seulement si les deux entrées sont fausses.
NON-OU, noté ↓, est ¬(p ∨ q). Comme NON-ET, il est fonctionnellement complet à lui seul, si bien qu'un circuit peut être construit entièrement de portes NOR.
Dans la calculatrice¬(p ∨ q)Quel connecteur s'applique en premier quand les parenthèses manquent.
La négation lie le plus fort, puis la conjonction, la disjonction, le conditionnel et enfin le biconditionnel. Ainsi ¬p ∧ q ∨ r se lit ((¬p) ∧ q) ∨ r ; les parenthèses changent cet ordre dès que la lecture voulue diffère.
Dans la calculatrice¬p ∧ q ∨ rUne ligne par attribution de valeurs, avec la valeur de la formule.
Une table de vérité énumère les 2ⁿ interprétations des n variables d'une formule et calcule sa valeur dans chacune. Étant exhaustive, elle règle toute question sémantique de la logique propositionnelle : équivalence, validité, satisfaisabilité et le reste.
Dans la calculatricep → qUne formule vraie sous toute interprétation.
Une tautologie est vraie dans chaque ligne de sa table de vérité et ne dit donc rien du monde : p ∨ ¬p est vraie quoi que vaille p. Deux formules sont équivalentes exactement quand le biconditionnel entre elles est une tautologie.
Dans la calculatricep ∨ ¬pUne formule fausse sous toute interprétation.
Une contradiction comme p ∧ ¬p est fausse dans chaque ligne de sa table de vérité. En dériver une d'un ensemble d'hypothèses montre qu'elles ne peuvent pas toutes tenir, ce qui est le moteur du raisonnement par l'absurde.
Dans la calculatricep ∧ ¬pUne formule vraie sous certaines interprétations et fausse sous d'autres.
Une formule contingente n'est ni une tautologie ni une contradiction : sa table de vérité a au moins une ligne vraie et au moins une ligne fausse. La plupart des formules que l'on écrit sont contingentes, et c'est ce qui les rend informatives.
Dans la calculatricep ∧ qLe fait qu'une interprétation au moins rende la formule vraie.
Une formule est satisfaisable quand au moins une ligne de sa table de vérité est vraie, et cette ligne en est un modèle. Décider la satisfaisabilité est le problème central des solveurs SAT et, à travers eux, d'une grande part du raisonnement automatique.
Dans la calculatricep ∧ (p → q)Deux formules ayant des tables de vérité identiques.
Des formules équivalentes s'accordent sous toute interprétation : l'une peut remplacer l'autre partout sans changer ce qui est dit. Placez un signe égal entre deux expressions et la calculatrice comparera leurs colonnes ligne à ligne.
Dans la calculatrice(p → q) ≡ (¬p ∨ q)La conclusion tient dans toute interprétation où les prémisses tiennent.
Notée Γ ⊨ φ, la conséquence logique est ce que revendique un argument valide. On la vérifie en cherchant un contre-exemple : une interprétation rendant toutes les prémisses vraies et la conclusion fausse. S'il n'en existe aucun, la conséquence tient.
Dans la calculatricep → q, p ⊨ qAucune interprétation ne rend les prémisses vraies et la conclusion fausse.
La validité est une propriété de la forme de l'argument, non des faits : un argument valide peut avoir des prémisses fausses et une conclusion fausse. Ce qu'il ne peut pas avoir, ce sont des prémisses vraies avec une conclusion fausse.
Dans la calculatricep → q, p ⊨ qUn argument valide dont les prémisses sont en outre vraies.
La solidité ajoute une affirmation factuelle à une affirmation formelle : l'argument est valide et ses prémisses tiennent. La logique seule règle la première moitié ; la seconde relève du sujet dont traite l'argument.
Une interprétation rendant les prémisses vraies et la conclusion fausse.
Un contre-modèle prouve qu'un argument est invalide : une ligne suffit. La calculatrice affiche celle qu'elle trouve, ce qui transforme « cela ne suit pas » en une attribution concrète que l'on peut vérifier à la main.
Dans la calculatricep → q ⊨ q → pUne interprétation rend vrais tous les énoncés de l'ensemble à la fois.
Un ensemble de prémisses est consistant quand elles peuvent toutes tenir ensemble. Des prémisses inconsistantes impliquent absolument tout, si bien qu'un argument bâti sur elles est techniquement valide et ne vaut rien.
Dans la calculatricep → q, ¬q ⊨ ¬pUne variable ou sa négation, comme p ou ¬p.
Les littéraux sont les atomes des formes normales : une clause est une disjonction de littéraux et un mintermes une conjonction d'entre eux. Un littéral est positif quand la variable est nue et négatif quand elle est niée.
Dans la calculatrice¬pUne disjonction de littéraux, comme p ∨ ¬q ∨ r.
Une clause est l'un des groupes entre parenthèses dont est faite une forme normale conjonctive. Comme une conjonction n'est vraie que si chaque partie l'est, une formule en FNC tient exactement quand toutes ses clauses tiennent.
Dans la calculatricep ∨ ¬q ∨ rUn OU de ET : une disjonction de conjonctions de littéraux.
Toute formule possède une forme normale disjonctive, et elle se lit directement dans la table de vérité : une conjonction par ligne vraie, reliées par ∨. La calculatrice donne aussi une FND minimisée, qui dit la même chose avec moins de littéraux.
Dans la calculatrice(p ∧ q) ∨ (¬p ∧ r)Un ET de OU : une conjonction de clauses.
La forme normale conjonctive se lit dans les lignes fausses de la table de vérité, une clause par ligne. C'est le format d'entrée attendu par les solveurs SAT, ce qui fait de la conversion en FNC une étape de routine du raisonnement automatique.
Dans la calculatrice(p ∨ q) ∧ (¬p ∨ r)Une conjonction qui désigne exactement une ligne de la table de vérité.
Un minterme mentionne chaque variable une fois, niée ou non, de sorte qu'une seule interprétation le satisfait. Rassembler les mintermes des lignes vraies et les relier par ∨ donne la forme normale disjonctive de la formule.
Dans la calculatricep ∧ ¬q ∧ rUne disjonction qui exclut exactement une ligne de la table de vérité.
Un maxterme mentionne chaque variable une fois et n'est faux que dans une seule interprétation. Prendre le maxterme de chaque ligne fausse et les relier par ∧ donne la forme normale conjonctive de la formule.
Dans la calculatricep ∨ ¬q ∨ rLa négation change ∧ en ∨ et ∨ en ∧ : ¬(p ∧ q) ≡ ¬p ∨ ¬q.
Les lois de De Morgan poussent une négation vers l'intérieur d'une conjonction ou d'une disjonction, en inversant le connecteur au passage. C'est ainsi qu'une formule est menée vers une forme normale, et que les négations se simplifient dans le code comme dans les circuits.
Dans la calculatrice¬(p ∧ q) ≡ ¬p ∨ ¬qNier deux fois redonne l'original : ¬¬p ≡ p.
La double négation vaut en logique classique dans les deux sens, si bien que ¬¬p et p sont toujours interchangeables. La logique intuitionniste ne garde que le sens de p vers ¬¬p, et c'est là que les deux systèmes se séparent.
Dans la calculatrice¬¬p ≡ pL'algèbre à deux valeurs, avec ∧, ∨ et ¬ pour opérations.
L'algèbre de Boole est la logique propositionnelle écrite comme une arithmétique sur 0 et 1, avec des lois — commutativité, distributivité, absorption, De Morgan — qui permettent de réécrire et de simplifier les expressions. C'est la mathématique dans laquelle on conçoit les circuits numériques.
Dans la calculatrice(p ∧ q) ∨ (p ∧ ¬q) ≡ pUne grille de la table de vérité qui rend les simplifications visibles.
Un tableau de Karnaugh dispose les lignes de sorte que les cases voisines ne diffèrent que d'une variable, et les bords se rejoignent. On l'écrit aussi K-map ou kmap. Les groupes rectangulaires de 1 adjacents de taille 1, 2, 4 ou 8 se lisent alors comme les termes d'une expression minimale.
Dans la calculatrice(p ∧ q) ∨ (p ∧ ¬r)Un groupe du tableau qui ne peut plus être agrandi.
Un impliquant est une conjonction de littéraux qui force la formule à être vraie ; il est premier quand lui retirer un littéral le lui ferait perdre. Sur un tableau de Karnaugh, les impliquants premiers sont les rectangles maximaux de 1.
Le seul impliquant premier couvrant un 1 donné.
Quand un 1 du tableau n'appartient qu'à un seul groupe maximal, ce groupe doit figurer dans toute couverture minimale : on le prend donc d'abord. Ce qui reste est la part de la couverture qu'il faut réellement chercher.
Un élément de circuit calculant un connecteur sur ses entrées.
Les portes ET, OU, NON, NON-ET, NON-OU et OU exclusif sont la contrepartie matérielle des connecteurs. Une formule et un circuit sont le même objet dessiné deux fois, et c'est pourquoi la calculatrice peut afficher une expression sous forme de schéma de portes.
Dans la calculatrice(p ∧ q) ∨ ¬rUn pas autorisé de formules déjà obtenues vers une nouvelle.
Une règle d'inférence est un schéma comme le modus ponens, applicable dès que l'on dispose de formules de la bonne forme. Les systèmes de démonstration se bâtissent sur une poignée d'entre elles, choisies pour que seules des conclusions qui découlent puissent être dérivées.
De p → q et p, on infère q.
Le modus ponens est la règle de base du conditionnel : étant donné un conditionnel et son antécédent, le conséquent suit. Sa validité se voit dans la table de vérité : la seule ligne où les deux prémisses sont vraies a aussi la conclusion vraie.
Dans la calculatricep → q, p ⊨ qDe p → q et ¬q, on infère ¬p.
Le modus tollens parcourt un conditionnel à l'envers : si le conséquent échoue, l'antécédent ne peut pas avoir tenu. C'est la contraposée à l'œuvre, et la forme de tout argument qui réfute une hypothèse en éprouvant ses prédictions.
Dans la calculatricep → q, ¬q ⊨ ¬pDe p → q et q → r, on infère p → r.
Le syllogisme hypothétique enchaîne les conditionnels, ce qui rend possibles les longues dérivations : chaque maillon porte l'argument un pas plus loin sans qu'aucune prémisse soit affirmée.
Dans la calculatricep → q, q → r ⊨ p → rDe p ∨ q et ¬p, on infère q.
Le syllogisme disjonctif élimine l'option écartée : si l'une de deux possibilités tient et que la première échoue, la seconde doit tenir. C'est la règle derrière le raisonnement par élimination.
Dans la calculatricep ∨ q, ¬p ⊨ qDémontrer une conclusion en appliquant des règles pas à pas.
La déduction naturelle dérive une conclusion de prémisses au moyen de règles d'introduction et d'élimination pour chaque connecteur, en permettant des hypothèses temporaires que l'on décharge ensuite. Elle démontre ce qu'une table de vérité vérifie, mais sans parcourir chaque ligne.
Supposer le contraire, dériver une contradiction, conclure l'original.
Pour démontrer φ, on suppose ¬φ et l'on dérive quelque chose de la forme ψ ∧ ¬ψ. Comme aucune interprétation ne rend une contradiction vraie, l'hypothèse ne peut tenir et φ suit. C'est ainsi que procèdent d'ordinaire les preuves d'irrationalité et d'infinité.
Dans la calculatricep ∧ ¬pLe pas invalide de p → q et q vers p.
Un conséquent vrai n'établit pas l'antécédent : autre chose a pu le produire. La calculatrice exhibe le contre-modèle — p faux, q vrai — qui est la ligne séparant ceci du modus ponens.
Dans la calculatricep → q, q ⊨ pLe pas invalide de p → q et ¬p vers ¬q.
Un conditionnel ne dit rien de ce qui arrive quand son antécédent échoue : écarter l'antécédent laisse donc le conséquent ouvert. Le contre-modèle est la ligne où p est faux et q vrai.
Dans la calculatricep → q, ¬p ⊨ ¬qUne logique qui regarde à l'intérieur des propositions, objets et propriétés.
La logique des prédicats ajoute prédicats, termes et quantificateurs, si bien que « tout nombre premier supérieur à deux est impair » devient une formule et non une simple lettre. Elle est strictement plus expressive que la logique propositionnelle, et aucune table de vérité ne peut la décider.
Un symbole disant de combien d'objets un prédicat est vrai.
Les deux quantificateurs classiques sont ∀ (tous) et ∃ (au moins un), et chacun est la négation de l'autre appliquée à un corps nié. La variable qu'un quantificateur lie est ce qui distingue la logique des prédicats de la logique propositionnelle.
∀x φ : φ vaut de chaque objet du domaine.
Une affirmation universelle est réfutée par un seul contre-exemple et tient de manière vide sur un domaine vide. ∀x φ équivaut à ¬∃x ¬φ, ce qui est la contrepartie des lois de De Morgan pour les quantificateurs.
∃x φ : φ vaut d'au moins un objet du domaine.
Une affirmation existentielle s'établit en produisant un témoin. ∃x φ équivaut à ¬∀x ¬φ, si bien que chaque quantificateur se définit à partir de l'autre et de la négation.
Une logique étendue par « nécessairement » (□) et « possiblement » (◇).
La logique modale évalue les formules dans des mondes possibles plutôt que dans une seule interprétation : □φ tient quand φ tient dans tout monde accessible, ◇φ quand elle tient dans l'un d'eux. Faire varier le sens d'« accessible » donne les différents systèmes modaux.
