Formule propositionnelle

Dans le calcul des propositions, les propositions de base sont simples ou atomiques (on ne peut pas les décomposer)[2]. Les propositions atomiques sont liées par des connecteurs propositionnels, les plus courants sont «ET», «OU», «SI ... ALORS ...», «ni ... ni ...», « ... EST ÉQUIVALENT À ...» . En langue vernaculaire des mathématiciens, le point-virgule « ; » et le conjonctif « MAIS » sont considérés comme des expressions de « ET ». Une suite de propositions sont considérées comme liées par des conjonctions, et l'analyse formelle applique une « règle de parenthèses » récursive.

Les propositions simples sont de nature déclarative, elles affirment quelque chose au sujet de l'état du monde, par exemple « Cette vache est bleue », « Il y a un coyote! », « ce triangle est isocèle », « 3 ≥ 5 ».

Un système formel est un ensemble de symboles, appelés variables, un ensemble de symboles appelés connecteurs (*, +, ~ , &, V, =, ≡, ⋀, ¬) et un système de règles pour manipuler les symboles.

Les formules propositionnelles sont construites à partir des variables propositionnelles en utilisant des connecteurs propositionnels, par exemple

• Le connecteur unaire de la négation. Si ${\displaystyle \alpha }$ est une formule, alors ${\displaystyle \lnot \alpha }$ est une formule.
• Les connecteurs binaires ${\displaystyle \land ,\lor ,\to ,\leftrightarrow ,\leftrightarrow }$. Ainsi, par exemple, si ${\displaystyle \alpha }$ et ${\displaystyle \beta }$ sont des formules propositionnelles, alors ${\displaystyle (\alpha \to \beta )}$ est une formule propositionnelle.
• Des connecteurs binaires, tels que NON-ET, NON-OU, et XOR.
• Le connecteur ternaire SI ... ALORS ... SINON ...
• Les connecteurs nullaires ⊤ et ⊥

Connecteurs de rhétorique, de philosophie et de mathématiques

Voici les connecteurs communs à la rhétorique, philosophie et aux mathématiques, ainsi que leurs tables de vérité. Les symboles utilisés varient d'un auteur à un autre et entre les domaines d'activité. En général, les abréviations «V» et «F» représentent l'évaluation des variables de la formule propositionnelle (par exemple, l'affirmation: « Cette vache est bleue » aura la valeur de vérité « V » pour Vrai ou « F » pour Faux, dans le cas contraire.)

Les connecteurs s'énoncent de nombreuses façons, par exemple « a IMPLIQUE b » se dit également « SI a ALORS b ». Certains d'entre eux sont présentés dans le tableau ci-dessous.

						b only if a
						b EST SUFFISANT POUR a
						a EST NÉCESSAIRE POUR b	b SI ET SEULEMENT SI a; b SSI a
					OU inclusif	SI b ALORS a	b EST NÉCESSAIRE ET SUFFISANT POUR a
		négation	négation	conjonction	disjonction	implication	biconditionel
variable	variable	NON b	NON a	b ET a	b OU a	b IMPLIQUE a	b EST logiquement équivalent À a	f EST UNE tautologie	NI a NI b	b barre a	OU exclusif
b	a	${\displaystyle \lnot }$(b)	${\displaystyle \lnot }$(a)	(b ${\displaystyle \land }$ a)	(b ${\displaystyle \lor }$ a)	(b ${\displaystyle \to }$ a)	(b ${\displaystyle \leftrightarrow }$ a)	(f = formule)	(a NON-OU b)	(b|a)	varie
F	F	V	V	F	F	V	V	V	V	V	F
F	V	V	F	F	V	V	F	V	F	V	V
V	F	F	V	F	V	F	F	V	F	V	V
V	V	F	F	V	V	V	V	V	F	F	F

Comme indiqué ci-dessus, le connecteur SI c ALORS b SINON a est construit, soit à partir de connecteurs à 2 arguments SI ... ALORS ... et ET, soit de OU et ET et le connecteur unaire NON. Les connecteurs tels que l'argument n-aire ET (a & b & c & ... & n), OU (V b V c V ... V n) sont construits à partir des chaînes des deux arguments ET et OU et écrits sous forme abrégée sans parenthèses. Ceux-ci, et d'autres connecteurs, peuvent alors servir de blocs de construction pour former encore d'autres connecteurs. Les rhéteurs, philosophes et mathématiciens utilisent des tables de vérité et les divers théorèmes d'analyse dans le but de simplifier leurs formules.

La présentation classique de la logique propositionnelle (voir Enderton 2002) utilise les connecteurs ${\displaystyle \lnot ,\land ,\lor ,\to ,\leftrightarrow }$. L'ensemble des formules sur un ensemble donné de variables propositionnelles est inductivement défini comme le plus petit ensemble d'expressions telles que :

• Chaque variable propositionnelle contenue dans l'ensemble est une formule,
• ${\displaystyle (\lnot \alpha )}$ est une formule quand ${\displaystyle \alpha }$ en est une, et
• ${\displaystyle (\alpha \,\Box \,\beta )}$ est une formule quand ${\displaystyle \alpha }$ et ${\displaystyle \beta }$ sont des formules et ${\displaystyle \Box }$ est l'un des connecteurs logiques binaires ${\displaystyle \land ,\lor ,\to ,\leftrightarrow }$.

Cette définition inductive peut être facilement étendue pour couvrir des connecteurs supplémentaires.

La définition inductive peut également être reformulée sous forme d'opération de clôture (Enderton, 2002). Soit V un ensemble de variables propositionnelles et X_V désignent l'ensemble de toutes les chaînes à partir d'un alphabet, y compris les symboles de V, les parenthèses de gauche et de droite, et tous les connecteurs logiques nécessaires. Chaque connecteur logique correspond à une opération de construction de formule, une fonction de XX_V à XX_V:

• Étant donné une chaîne z, l'opération ${\displaystyle {\mathcal {E}}_{\lnot }(z)}$ retourne ${\displaystyle (\lnot z)}$.
• Étant donné une chaîne z, l'opération ${\displaystyle {\mathcal {E}}_{\land }(y,z)}$ retourne ${\displaystyle (y\land x)}$. Il existe des opérations similaires ${\displaystyle {\mathcal {E}}_{\lor }}$, ${\displaystyle {\mathcal {E}}_{\to }}$, et ${\displaystyle {\mathcal {E}}_{\leftrightarrow }}$ correspondant aux autres connecteurs binaires.

Les « principes » (ou « lois ») suivants du calcul propositionnel sont utilisés pour « réduire » les formules complexes[5]. Les « principes » peuvent être facilement vérifiés avec des tables de vérité. Pour chaque principe, le connecteur principal est associé à l'équivalence logique ≡ ou à l'identité =. Une analyse complète des  2ⁿ valeurs de vérité pour ses n variables distinctes se traduira par une colonne de 1 sous ce connecteur. Cette constatation fait de chaque principe, par définition, une tautologie. Et, pour un principe donné, puisque sa formule à gauche et à droite sont équivalentes (ou identiques), peuvent être remplacés par un autre.

Exemple : La table de vérité suivante est la loi de De Morgan portant sur le NON sur OU: ~(a V b) ≡ (~a & ~b). À gauche du connecteur principal ≡  (colonne jaune « taut ») la formule ~(b V a) évaluée à (1, 0, 0, 0) dans la colonne « P». Sur la droite de « taut » la formule (~(b) V ~(a)) est aussi évaluée à (1, 0, 0, 0) dans la colonne « Q ». Comme les deux colonnes possèdent des évaluations équivalentes, l'équivalence logique ≡ sous « taut » est évaluée à (1, 1, 1, 1), i.e. P ≡ Q. 

Notez que si les symboles 1 et 0 (ou T et F) sont utilisés dans un système axiomatique, ils sont considérés comme des fbfs et obéiront donc aux mêmes règles que celles des variables : ancienneté Connective (symbole rang).

Telles qu'elles ont été présentées, ces formules peuvent être analysées de manière unique pour déterminer leur structure en termes de variables propositionnelles et de connecteurs logiques. Lorsque les formules sont écrites en notation infixe, comme ci-dessus, la désambiguïsation est assurée grâce à une utilisation appropriée de parenthèse. Alternativement, les formules peuvent être écrites en notation polonaise ou en notation polonaise inverse, ce qui élimine le besoin de parenthèses. Elles peuvent aussi être décrites par un arbre syntaxique.

La définition inductive des formules infixes dans la section précédente peut être convertie en une grammaire formelle sous la forme de Backus-Naur :

<formule> ::= <variable propositionnelle>

| ( ${\displaystyle \lnot }$ <formule> )

| ( <formule> ${\displaystyle \land }$ <formule>)

| ( <formule> ${\displaystyle \lor }$ <formule> )

| ( <formule> ${\displaystyle \to }$ <formule> )

| ( <formule> ${\displaystyle \leftrightarrow }$ <formule> )

On peut montrer que toute expression appariée par la grammaire a le même nombre de parenthèses à gauche qu'à droite, et toute partie initiale non vide d'une formule a plus de parenthèses à gauche qu'à droite[8]. Ce fait peut être utilisé pour donner un algorithme pour l'analyse syntaxique des formules. Cette idée peut être utilisée pour générer un analyseur de descente pour les formules récursives.

Exemple de comptage de parenthèses:

Cette méthode localise « 1 » comme le connectif principal[9]. Il localise aussi le connecteur le plus interne, où l'on commencerait l'évaluation de la formule sans l'utilisation d'une table de vérité, par exemple au « niveau 6 ».

Le symbole d'ingénierie pour le connecteur NAND (NON-ET° (la «barre») peut être utilisé pour construire une formule propositionnelle. L'idée que la vérité (1) et le faux (0) peuvent être définis en termes de ce connecteur est montré dans la suite de NON-ET sur la gauche, et les dérivations des quatre évaluations d'un NON-ET b sont présentées en bas du document. La méthode la plus courante consiste à utiliser la table de vérité du NON-ET.

Un ensemble de connecteurs logiques est dit complet si chaque formule propositionnelle est tautologiquement équivalente à une formule avec seulement les connecteurs de cet ensemble. Il y a beaucoup d'ensembles complets de connecteurs, y compris ${\displaystyle \{\land ,\lnot \}}$, ${\displaystyle \{\lor ,\lnot \}}$, et ${\displaystyle \{\to ,\lnot \}}$[10]. Certaines paires ne sont pas complètes, par exemple ${\displaystyle \{\land ,\lor \}}$.

Une formule propositionnelle arbitraire peut avoir une structure très compliquée. Il est souvent commode de travailler avec des formules qui ont des formes plus simples, connus sous le nom de formes normales. Certaines formes normales courantes comprennent la forme normale conjonctive et la forme normale disjonctive. Toute formule propositionnelle peut être réduite à sa forme normale conjonctive ou disjonctive.

Réduction à la forme normale

Une table de vérité contiendra 2ⁿ rangées, où n est le nombre de variable (e.g. trois variables « p », « d », « c » produit 2³ rangées). Chaque ligne représente une minterm. Chaque minterm peut être trouvée dans le diagramme de Hasse, le diagramme de Veitch, et dans la table de Karnaugh. (Les évaluations de « p » montrées dans la table de vérité ne sont pas représentées dans les diagrammes de Hasse, Veitch et Karnaugh.)

La réduction à la forme normale est relativement simple une fois la table de vérité de la formule concernée prête. Mais de nouvelles tentatives pour réduire au minimum le nombre de littéraux (voir ci-dessous) nécessitent quelques outils : la réduction par les lois de De Morgan et des tables de vérité peut être difficile à réaliser, mais les tables de Karnaugh sont très appropriées pour étudier un petit nombre de variables (5 ou moins). Certaines méthodes tabulaires sophistiquées ; pour plus de détails, voir la méthode de Quine-Mc Cluskey.

Bertrand Russell (1912:74) énumère trois lois de la pensée dérivées d'Aristote : (1) Le principe d'identité : « Tout ce qui est, est », (2) Le principe de la non-contradiction : « Rien ne peut pas à la fois être et ne pas être » et (3) Le principe du tiers exclu : « Tout doit être ou ne pas être ».

Exemple : Ici O est une expression autour d'un objet :

(1) Principe d'identité: O = O

(2) Principe de non-contradiction: ~(O & ~(O))

(3) Principe du tiers exclu: (O V ~(O))

Bien qu'un calcul propositionnel soit né avec Aristote, la notion d'une algèbre appliquée à des propositions a dû attendre le début du XIX^e siècle. Dans une réaction (défavorable) à la tradition de 2000 ans des syllogismes d'Aristote, l'Essai sur l'entendement humain de John Locke (1690) a utilisé le mot sémiotique (théorie de l'utilisation de symboles). En 1826, Richard Whately a fait une analyse critique de la logique syllogistique avec une sympathie envers la sémiotique de Locke. Le travail de George Bentham (1827) a donné lieu à la notion de « quantification du prédicat » (1827) (aujourd'hui symbolisée par ∀ ≡ « pour tout »). Une « ligne » lancée par William Hamilton sur un conflit de priorité avec Auguste De Morgan « a inspiré George Boole pour écrire ses idées sur la logique, et de les publier en tant AML [Analyse Mathématique de la Logique] en 1847 » (Grattin-Guinness et Bornet 1997 : xxviii).

À propos de leur contribution, Grattin-Guinness et Bornet commentent :

« La principale innovation de Boole était [le] principe [ xⁿ = x ] pour la logique : celui-ci déclare que les actes mentaux de choisir la propriété x et en choisissant à nouveau x et encore est le même que le choix de x fois ... a comme conséquence la formation des équations x•(1-x)=0 et x+(1-x)=1 qui, pour lui, expriment respectivement le principe de non-contradiction et le principe du tiers exclu » (p. xxviiff). Pour Boole « 1 » était l'univers du discours et « 0 » n'était rien.

L'œuvre massive de Gottlob Frege (1879) a donné lieu à un calcul formel des propositions, mais son symbolisme est si décourageant qu'il a eu peu d'influence à l'exception d'une seule personne : Bertrand Russell. Tout d'abord comme élève d'Alfred North Whitehead, il étudia le travail de Frege et suggéra une correction (célèbre et notoire en 1904) autour du problème d'une antinomie qu'il a découvert dans le traitement de Frege (cf. paradoxe de Russell). Le travail de Russell a conduit à une collaboration avec Whitehead qui, dans l'année 1912, a produit le premier volume des Principia Mathematica (PM). Cet ouvrage est le précurseur à ce que nous considérons aujourd'hui la logique propositionnelle «moderne». En particulier, les PM introduisent le NON, le OU et l'affirmation ⊦ comme primitifs. Exprimée à l'aide de ces notions, l'IMPLICATION →  est ainsi définie (def. *1.01: ~p V q), puis le ET (def. *3.01: ~(~p V ~q)), et enfin, l'ÉQUIVALENCE p ←→ q (*4.01: (p → q) & (q → p)).

• Henry M. Sheffer (1921) et Jean Nicod démontrent que seulement un connecteur, la « barre » | est suffisant pour exprimer toutes les formules propositionnelles.
• Emil Post (1921) développe la méthode de table de vérité d'analyse dans son « Introduction à une théorie générale des propositions élémentaires ». Il prend note de la barre de Nicod | .
• Whitehead et Russell ajoutent une introduction à leur re-publication des Principia Mathematica, en 1927, ajoutant un traitement, en partie, favorable à la « barre ».

Calcul et logique commutative:

• George Stibitz (1937) invente l'additionneur binaire en utilisant des relais mécaniques. Il construisit cela sur sa table de cuisine.
• Alan Turing construit un multiplicateur utilisant des relais (1937-1938).
• Les manuels sur les « circuits de commutation » apparaissent au début des années 1950.
• Willard Quine 1952 et 1955, E. W. Veitch 1952, et M. Karnaugh (1953) développent des méthodes de tables pour simplifier les fonctions propositionnelles.
• George H. Mealy (1955) et Edward F. Moore (1956) abordent la théorie des « machines » séquentielles (par exemple, la commutation de circuit).
• E. J. McCluskey et H. Shorr développent une méthode pour simplifier les circuits (de commutation) propositionnels (1962).

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Propositional formula » (voir la liste des auteurs).
• Bender, Edward A. and Williamson, S. Gill, 2005, A Short Course in Discrete Mathematics, Dover Publications, Mineola NY, (ISBN 0-486-43946-1).
• Enderton, H. B., 2002, A Mathematical Introduction to Logic. Harcourt/Academic Press. (ISBN 0-12-238452-0)
• Goodstein, R. L., (Pergamon Press 1963), 1966, (Dover edition 2007), Boolean Algebra, Dover Publications, Inc. Minola, New York, (ISBN 0-486-45894-6). pp. 76–93.
• Ivor Grattan-Guinness et Gérard Bornet 1997, George Boole: Selected Manuscripts on Logic and its Philosophy, Birkhäuser Verlag, Basil, (ISBN 978-0-8176-5456-6) (Boston).
• A. G. Hamilton 1978, Logic for Mathematicians, Cambridge University Press, Cambridge UK, (ISBN 0-521-21838-1).
• E. J. Edward J. McCluskey 1965, Introduction to the Theory of Switching Circuits, McGraw-Hill Book Company, New York. No ISBN. Library of Congress Catalog Card Number 65-17394. McCluskey était un étudiant de Willard Quine et développé quelques théorèmes notables avec Quine.
• Marvin L. Minsky 1967, Computation: Finite and Infinite Machines, Prentice-Hall, Inc, Englewood Cliffs, N.J.. No ISBN. Library of Congress Catalog Card Number 67-12342.
• Paul C. Rosenbloom 1950, Dover edition 2005, The Elements of Mathematical Logic, Dover Publications, Inc., Mineola, New York, (ISBN 0-486-44617-4).
• Joel W. Robbin 1969, 1997, Mathematical Logic: A First Course, Dover Publications, Inc., Mineola, New York, (ISBN 0-486-45018-X) (pbk.).
• Patrick Suppes 1957 (1999 Dover edition), Introduction to Logic, Dover Publications, Inc., Mineola, New York. (ISBN 0-486-40687-3) (pbk.). This book is in print and readily available.
• E. V. Huntington, "Sets of Independent Postulates for the Algebra of Logic", Transactions of the American Mathematical Society, Vol. 5 91904) pp. 288-309.
• Alfred Tarski 1941 (1995 Dover edition), Introduction to Logic and to the Methodology of Deductive Sciences, Dover Publications, Inc., Mineola, New York. (ISBN 0-486-28462-X) (pbk.).
• Jean van Heijenoort 1967, 3rd printing with emendations 1976, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, Harvard University Press, Cambridge, Massachusetts. (ISBN 0-674-32449-8) (pbk.), lettres de Russell à Frege (1902) et lettres de Frege à Russell (1902), Paradoxe de Richard (1905), Post (1921).
• Alfred North Whitehead and Bertrand Russell 1927 2nd edition, paperback edition to *53 1962, Principia Mathematica, Cambridge University Press.
• William E. Wickes 1968, Logic Design with Integrated Circuits, John Wiley & Sons, Inc., New York. (p. 18ff).

• Portail de la logique
• Portail de l’algèbre
• Portail de l'informatique théorique