Calcul des propositions
Le calcul des propositions est à la base de l'électronique numérique.
| Sommaire |
Analyse des propositions
Description
Grâce au langage, nous pouvons décrire des choses, nous pouvons exprimer des ordres, des souhaits, des normes, des émotions, et nous pouvons également obtenir des énoncés à partir d'autres énoncés : c'est ce qu'on appelle un raisonnement.
Un raisonnement est donc un discours du type : proposition (prémisse) + donc + proposition (conséquence, conclusion). L'obtention d'un énoncé par des prémisses est appelée déduction. Ainsi, d'une manière un peu plus formelle, on peut dire que la déduction est un passage de prémisses à des conséquences sans recours à des éléments étrangers aux prémisses en exploitant seulement ce qui est dans les prémisses.
Les propositions au sens logique peuvent être exprimées par les énoncés du langage ordinaire, mais ne leur sont pas identiques. C'est ainsi que deux énoncés, tels que « il pleut » et « it's raining » correspondent à la même proposition, quoiqu'il s'agisse de deux énoncés distincts.
Il est difficile de donner une définition consensuelle du concept de « proposition ». Dans une première approximation, on peut dire qu'il s'agit d'entités abstraites se référant à des états de chose ou des événements.
D'un point de vue strictement formel, on peut se contenter de considérer comme proposition n'importe quelle entité, (voire, dans une interprétation radicale, n'importe quel symbole) qui satisfasse l'une ou l'autre axiomatique du calcul des propositions.
Éléments premiers de la logique des propositions
En dégageant la forme d'un raisonnement, on rend le contenu des propositions indifférent en admettant l'invariance des conjonctions (par exemple donc). Le raisonnement se décompose alors en trois éléments :
- éléments invariables : conjonctions constantes (donc, et, mais, ou, etc.), ou éléments donnés (Socrate par exemple) ;
- éléments à différents contenus : des variables (x, y, etc.) dans un ensemble, dans un domaine de variation ;
- éléments de ponctuation : par exemple, des parenthèses.
Ces éléments sont indispensables pour bien former des formules, c'est pourquoi on parle d'énoncé bien formé : ebf. Mais la formulation doit se faire selon des règles données par des axiomes.
Un raisonnement est dit correct ou incorrect, concluant ou non-concluant, valide ou invalide, etc. Il est important de distinguer la validité ou l'invalidité d'un raisonnement de la vérité ou de la fausseté des propositions, qui renvoient à un contenu. Vérité et fausseté sont notées : V et F ; validité et invalidité : 1 et 0.
À partir de cette distinction, on peut définir la logique comme la discipline qui traite de manière stricte de la validité ou de l'invalidité des raisonnements.
Les énoncés sont simples ou complexes.
Comme la plupart des théories logico-mathématiques, il est possible de considérer le calcul des propositions d'un point de vue syntaxique ou sémantique :
- aspects syntaxiques : ensemble de signes agencés conventionnellement et non interprétés. C'est ce que l'on écrit, la langue objet ;
- sémantique : l'énoncé lui-même en tant qu'on lui rapporte un contenu : par exemple : ~ = non. C'est la métalangue, langue de l'observateur.
Vocabulaire fondamental
- valeur : qualifications rapportables aux propositions (0,1) ;
- logique bivalente : logique qui admet deux valeurs rapportables aux propositions ;
- logique monovalente : il n'y a qu'une valeur, tout est vrai ou tout est faux ;
- logique plurivalente : logique à plus de deux valeurs ;
- proposition : une proposition, en calcul des propositions, est un énoncé déclaratif auquel on peut attribuer en droit, sans rien y ajouter, la qualification vrai ou la qualification faux ; et par extension, une qualification pensée comme du même ordre que vrai et faux ;
- proposition atomique : une proposition non décomposable en proposition, par exemple : il pleut ;
- proposition moléculaire : proposition décomposable, par exemple : il pleut et il fait froid ;
- molécule :
- mono atomique : qui ne contient qu'un seul atome (il ne pleut pas, par exemple) ;
- pluri atomique : qui contient plusieurs atome.
- fonction de vérité : toute molécule pour laquelle il suffit de connaître la valeur des atomes constituant pour déterminer la sienne. Exemple : non p (~p) ;
- opérateur propositionnel : locution qui, complétée par une ou plusieurs propositions selon sa nature, forme encore une proposition (~,. par exemple);
- opérande ; ce sur quoi porte un opérateur (p, q, etc.) ; pour 3 + 6 = 9 + est l'opérateur alors que 3 et 6 sont les opérandes.
Le nombre d'opérandes d'un opérateur est appelé son arité. En fonction de leur arité, les opérations sont classées comme nulaire, unaire, binaire, etc.
- argument d'une fonction : une variable dont dépend le résultat de la fonction.
- foncteur : opérateur introduisant une fonction de vérité (et, non, etc.).
La logique des propositions traite de ces foncteurs.
Les foncteurs logiques
Description et évaluation
Il existe des foncteurs unaires (qui n'opèrent que sur une proposition), foncteurs binaires (sur 2), ternaires, etc.
L'évaluation des foncteurs se fait notamment au moyen de tables de vérité. Lorsque le résultat n'est constitué que de 1, c'est une loi logique ou tautologie ; quand il n'y a que des 0, c'est une antilogie, qui est la négation de la tautologie ; antilogie et tautologie sont des formules analytiques. S'il y a au moins un 1 et au moins un 0, c'est une formule synthétique.
Seules les formules tautologiques sont valides ; les formules synthétiques et les antilogies sont invalides.
Les tautologies et les formules synthétiques sont réalisables, i.e. elles possèdent un cas au moins où elles sont vraies ; l'antilogie est non réalisable.
En conséquence, on peut énoncer les théorèmes suivants :
- la négation d'une formule valide est une formule invalide ;
- la négation d'une formule synthétique est synthétique ;
- la négation d'une formule invalide est réalisable;
- etc.
Dénombrement des fonctions de vérité
Pour dénombrer des foncteurs, il faut connaître :
- la valence de la logique : 1, 2, 3, etc. valeurs ;
- le nombre de variables d'un foncteur ;
Foncteurs unaires
Il existe quatre foncteurs unaires en logique bivalente :
- le premier est la tautologie (Vrai) (ou fonction verum de p) ;
- le second est l'affirmation (Oui) (ou l'identité) ;
- le troisième est la négation (Non), notée ¬, ~ ;
- le dernier est la contradiction (Faux) (falsum de p).
Table de vérité
| p | °p | +p | ¬p | *p |
| 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
Foncteurs binaires
Les foncteurs binaires sont tirés en partie des opérateur du langage courant : et, ou, etc. Voici la liste des seize existants (2 exposant 2 exposant 2):
- 1 est la tautologie,
- 16 la contradiction,
- 2 est la disjonction (le ou noté ∨),
- 15 est sa négation (le rejet, ou nor),
- 8 est la conjonction (le et noté ∧),
- le 9 est sa négation (l'incompatibilité, ou nand noté |),
- 7 est l'équivalence (notée ≡)
- et 10 est sa négation (ou exclusif, noté w).
- 5 est l'implication (notée ⊃),
- 12 est sa négation,
- 3 est l'implication converse (notée ⊂)
- et 14 est sa négation.
- 4 et 6 conservent p et q respectivement,
- 13 et 11 sont leurs négations, elles n'ont pas de nom particulier.
Table de vérité de tous les foncteurs binaires
| p | q | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| V | V | V | V | V | V | V | V | V | V | F | F | F | F | F | F | F | F |
| V | F | V | V | V | V | F | F | F | F | V | V | V | V | F | F | F | F |
| F | V | V | V | F | F | V | V | F | F | V | V | F | F | V | V | F | F |
| F | F | V | F | V | F | V | F | V | F | V | F | V | F | V | F | V | F |
Propriétés remarquables
(« x » symbolise un foncteur)
- associativité : si et seulement si ((pxq)xm)≡(px(qxm)).
- commutativité : si et seulement si (pxq)≡(qxp).
- transitivité : si et seulement si ((pxq)∧(qxm))⊃(pxm).
- réflexivité : si et seulement si pxp.
- idempotence
- dualité
- distributivité
Le problème de l'implication
Pour le problème de l'implication dans la logique stoïcienne : Stoïcisme
Les Stoïciens semblent être les premiers logiciens à s'être posés le problème de l'implication. Ce problème a reçu plusieurs solutions dans l'Antiquité : pour les Stoïciens, le faux ne peut pas découler du vrai, l'implication est dont invalide dans ce cas et seulement. En revanche le faux peut impliquer le faux.
Choix de connecteurs primitifs
Quand un système primitif peut définir tous ses foncteurs par rapport au système primitif ou prototype, c'est un système complet.
On remarque que tous ces connecteurs peuvent se déduire d'un nombre plus restreint de connecteurs. Ainsi, Whitehead et Russell construisent leur logique sur le « ou » et la « négation », Frege sur l'implication et la négation. On peut aussi utiliser l'incompatibilité (ou le rejet), mais les calculs deviennent vite lourds.
Ainsi la totalité des foncteurs peut être exprimée par les trois foncteurs suivants : « et », « ou », « non », soit le système prototype :
- (p≡q)=df ((p∧q)∨(~p∧~q)) (« =df » se lit : est égal par définition)
Exemples :
On a le système prototype ∧,~,∨ (et, non, ou), fonctionnellement complet ; pour ∧,~, on remplace le « ∨ » :
- (p∨q)=df ~(~p∧~q)
En conséquence :
- (p≡q)=df ((p∧q)∨(~p∧~q))
- soit : (p≡q)=df ~(~(p∧q)∧~(~p∧~q))
Méthodes de notation
Il existe plusieurs systèmes de notation. Le logicien polonais Lukasiewicz a conçu un système préfixé, qui permet l'économie des parenthèses :
- Exemples de notation :
- N pour le « non » ¬
- C pour l'implication ⊃
- A pour pour le « ou »
- E pour l'équivalence
Exemples :
- CpAqm : p⊃(qvm)
- ACpqm : (p⊃q)vm
Méthode pour faire un calcul
- Point de départ : un énoncé d'un raisonnement
- Transcription en langage symbolique
- Application d'un algorithme
- Conclusion : valide ou invalide
- Exemple : Si Dieu existe, il est bon et il a créé un monde juste ; mais le monde est injuste, donc Dieu n'existe pas.
- p : Dieu existe
- q : Dieu est bon
- r : Dieu a créé le monde
- s : le monde est juste
- Transcription : ((p⊃(q∧r∧s))∧¬s)⊃¬p
- Conclusion : il y a plusieurs méthodes d'évaluation. En voici une première :
- On donne par hypothèse la valeur 0 au foncteur principal « ⊃ ». Le 0 sera noté sous ce dernier symbole. Puis on cherche à quelles valeurs des atomes la déduction est invalide. Si ces valeurs existent, la déduction est invalide ; si elles n'existent pas, elle est valide. Pour que notre déduction soit invalide il faut que la valeur de « ((p⊃(q∧r∧s)) » soit 1, et de « ¬p » 0. On note les valeurs sous les symboles et on continue.
- Au final, la formule est invalide quand la valeur de p = 1, la valeur de s = 0, et, dans ce cas, indépendamment des valeurs de q et r.
Théorèmes du calcul propositionnel
| A ∨ ¬A | principe du tiers exclu |
| ¬(A ∧ ¬A) | loi de non-contradiction |
| ¬(¬A) ≡ A | double négation |
| ¬(A ∧ B) ≡ (¬A ∨ ¬B) | lois de De Morgan |
| ¬(A ∨ B) ≡ (¬A ∧ ¬B) | |
| (A ⊃ B) ⊃ (¬B ⊃ ¬A) | règle de contraposition |
| ((A ⊃ B) ∧ A)⊃ B | règle du modus ponens |
| ((A ⊃ B) ∧ ¬B) ⊃ ¬A | règle du modus tollens |
| ((A ⊃ B) ∧ (B ⊃ C)) ⊃ (A ⊃ C) | règle du modus barbara |
| (A ∧ (B ∨ C)) ≡ ((A ∧ B) ∨ (A ∧ C)) | règles de distributivité |
| (A ∨ (B ∧ C)) ≡ ((A ∨ B) ∧ (A ∨ C)) |
À lire
- Introduction à la logique contemporaine, Robert Blanché
- Logique élémentaire, Quine
Voir aussi
- Gottfried Leibniz - George Boole - Auguste De Morgan - Gottlob Frege - Bertrand Russell - Ludwig Wittgenstein
- Logique (mathématiques)
- Logique plurivalente
- Logique modale
- Fonction logique ~ Porte logique