En logique mathématique une proposition, ou formule propositionnelle, ou expression propositionnelle est une expression construite à partir de connecteurs et de variables propositionnelles.
En logique propositionnelle classiqueEn logique intuitioniste, les modèles ne sont pas à base de valeurs de vérité., une formule propositionnelle, ou expression propositionnelle, est une formule bien formée qui possède une valeur de vérité. Si les valeurs de toutes les variables propositionnelles dans une formule propositionnelle sont données, une unique valeur de vérité peut être déterminée.
Une formule propositionnelle est construite à partir de propositions simples, telles que « cinq est supérieur à trois », ou de variables propositionnelles telles que P et Q, en utilisant des connecteurs logiques tels que NON, ET, OU et IMPLIQUE ; par exemple : (P ET NON Q) IMPLIQUE (P OU Q).
Propositions Dans le calcul des propositions, les propositions de base sont simples ou atomiques (on ne peut pas les décomposer)Hamilton 1978:1. 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 ». .
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 ».
Le calcul propositionnel comme système formel 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.
Utilité des formules propositionnelles Analyse : Dans le raisonnement déductif, les philosophes, rhéteurs et mathématiciens réduisent les arguments à des formules, puis les étudient pour vérifier leur exactitude. « Étant donné que la conscience est suffisante pour une intelligence artificielle, et que seules les entités conscientes peuvent passer le test de Turing, avant que nous puissions conclure qu'un robot est une intelligence artificielle, le robot doit d'abord passer le test de Turing. » Les ingénieurs analysent les fonctions logiques qu'ils ont conçues en utilisant des techniques de synthèse, puis appliquent diverses techniques de réduction et de minimisation afin de simplifier leurs conceptions.
Synthèse : Les ingénieurs synthétisent en particulier les formules propositionnelles (qui finissent par se retrouver sous forme de circuits de symboles) des tables de vérité. Par exemple, on pourrait créer une table de vérité pour savoir comment l'addition binaire doit se comporter étant donné l'ajout de variables « b », « a », « carry_in » (transposé dans) « ci », et les résultats « carry_out » (transposé hors) « co » et la « somme » Σ : Exemple : dans la , ( (b+a) + ci ) = ( (1+0) + 1 ) = le nombre «2». Écrit en nombre binaire, il est égal à 102, où «co»=1 et Σ=0, comme écrit dans le tableau ci-dessous. rangée b atd (b+a)+cico Σ 0 0 0 0 0 0 0 1 0 0 1 1 0 1 2 0 1 0 1 0 1 3 0 1 1 2 1 0 4 1 0 0 1 0 1 5 1 0 1 2 1 0 6 1 1 0 2 1 0 7 1 1 1 3 1 1
Variables propositionnelles Le type le plus simple de formule propositionnelle est une variable propositionnelle. Les propositions qui sont simples (atomique) telles que les expressions symboliques sont souvent désignées par des variables nommées a, b, ou A, B, etc. Une variable propositionnelle est destinée à représenter une proposition atomique (assertion), telle que « on est samedi » = a (ici le symbole = signifie « ... est attribué la variable nommée ... ») ou « Je ne vais au cinéma que le lundi » = b.
Affectation de valeur de vérité, évaluations de formule (en logique classique) En logique propositionnelle classique l’évaluation d'une formule propositionnelle commence par l'affectation d'une valeur de vérité à chaque variable.
Connecteurs logiques propositionnels Les formules propositionnelles sont construites à partir des variables propositionnelles en utilisant des connecteurs propositionnels, par exemple Le connecteur unaire de la négation. Si est une formule, alors est une formule. Les connecteurs binaires . Ainsi, par exemple, si et sont des formules propositionnelles, alors 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 (b) (a) (b a) (b a) (b a) (b 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
Connecteur : SI ... ALORS ... SINON ... si ... alors ... sinon ... est un connecteur ternaire. En logique classiqueDans la logique intuitionniste, tous les connecteurs sont indépendants., tous les autres connecteurs peuvent être construits à partir de ce connecteur et des constantes ⊥ (pour le « faux ») et T (pour le « vrai ») ; si A alors B sinon C équivaut à (A ∧ B) ∨ (¬A ∧ C) ou encore à (A → B) ∧ (¬A → C).
Formules plus complexes 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.
Définitions Une définition crée un nouveau symbole ainsi que son comportement, souvent dans le but de l’abréviation. Une fois que la définition est présentée, soit sous forme de symboles soit de formule équivalente, elle peut être utilisée. Le symbole suivant =Df fait partie de la convention de ReichenbachReichenbach p. 20-22 et suit les conventions des Principia Mathematica. Le symbole =Df est dans le métalangage et n'est pas un symbole formel avec la signification suivante : « le symbole ' s ' à avoir la même signification que la formule '(c & d)' ».. Quelques exemples de définitions pratiques tirées de l'ensemble de symbole { ~, &, (,) }. Chaque définition est la création d'une formule logiquement équivalente et peut être utilisée pour la substitution ou pour le remplacement. définition d'une nouvelle variable : (c & d) =Df s OU : ~(~a & ~b) =Df (a V b) IMPLICATION : (~a V b) =Df (a → b) XOR : (~a & b) V (a & ~b) =Df (a ⊕ b) ÉQUIVALENCE LOGIQUE : ( (a → b) & (b → a) ) =Df ( a ≡ b )
Substitution opposée à remplacement Substitution : La variable ou la sous-formule pouvant être substituées à une autre variable, une constante ou sous-formule doit être remplacée tout au long de la formule générale. Exemple : (c & d) V (p & ~(c & ~d)), mais (q1 & ~q2) ≡ d. Maintenant, chaque fois que la variable « d » se produit, substitut (q1 & ~q2) : (c & (q1 & ~q2)) V (p & ~(c & ~(q1 & ~q2))) Remplacement : (i) la formule à remplacer doit être logiquement équivalente (reliée par ≡ ou ↔) à la formule qui le remplace, et (ii) à la différence de la substitution, le remplacement ne se produit que dans un seul endroit. Exemple : Utilisez cet ensemble de formules équivalentes : 1 : ( (a V 0) ≡ a ). 2 : ( (a & ~a) ≡ 0 ). 3 : ( (~a V b) =Df (a → b) ). 6. ( ~(~a) ≡ a ) débuter avec « a » : a Utiliser 1 pour remplacer « a » avec (a V 0) : (a V 0) Utiliser la notion de « schéma » pour substituer b de a dans 2 : ( (a & ~a) ≡ 0 ) Utiliser 2 pour remplacer 0 avec (b & ~b) : ( a V (b & ~b) ) (voir ci-dessous pour comment distribuer « un V » sur (b & ~b), etc.
Définition inductive Une présentation simple de la logique propositionnelle (voir 2002) utilise les connecteurs . Les formules sur un ensemble donné de variables propositionnelles sont inductivement définies ainsi : Chaque variable propositionnelle est une formule, est une formule quand est une formule, et est une formule quand et sont des formules et est l'un des connecteurs logiques binaires . Cette définition inductive peut être étendue pour couvrir des connecteurs supplémentaires.
Une définition alternative peut se faire par clôture (Enderton, 2002). Soit V un ensemble de variables propositionnelles et l'ensemble des symboles de base. est le monoïde libre sur , autrement dit l'ensemble des mots sur . Chaque connecteur logique correspond à une propriété de stabilité. Si x appartient à V, x appartient à . Si un mot z sur appartient à , appartient à . Si deux mots y et z appartiennent à , appartient à . L'ensemble des formules est le plus petit ensemble de mots qui est stable au sens ci-dessus.
Définition par induction des sous-formules L'ensemble des sous-formules de , est défini par induction sur la structure d'une formule par
L'ensemble des sous-formule stricte d'une formule est l'ensemble des sous-formules de qui ne sont pas elle-même.
Autrement dit,
Définition par induction de la taille des formules On définit la taille d'une formule , notée , par induction sur la structure d'une formule par
On a alors la relation
Décomposition analytique de formules en logique classique
Les « principes » (ou « lois ») suivants du calcul propositionnel classique sont utilisés pour « réduire » les formules complexesLes concept de réduction et de complexité doivent être pris au sens de mise en forme normale, car, par ce mécanisme, la taille et en un certain sens la complexité des formules augmentent de façon exponentielle.. 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 2n 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.