Accueil |

Calcul des propositions

Le calcul des propositions, version moderne de la logique stoà¯cienne, est une théorie formelle axiomatico-déductive, branche de la logique, visant à  déterminer les lois de la déduction (ou dérivation) de propositions à  partir d'autres propositions.

Le calcul des propositions est à  la base de l'électronique numérique.

Sommaire
1 Analyse des propositions
2 Les foncteurs logiques
3 Méthodes de notation
4 Méthode pour faire un calcul
5 Théorèmes du calcul propositionnel
6 A lire
7 Voir aussi

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 optenir 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'ils s'agissent 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.

Elé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 conjonction (par exemple donc). Le raisonnement se décompose alors en trois éléments :

Ces éléments sont indispensables pour bien former des formules, c'est pourquoi on parle d'énoncé bien formée : 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.

A 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 :

Vocabulaire fondamental

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 (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 sunthé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ède un cas au mons ou elles sont vraies ; l'antilogie est non réalisable.

En conséquence, on peut énoncer les théorèmes suivants :

Dénombrement des fonctions de vérité

Pour dénombrer des foncteurs, il faut connaître :

Foncteurs unaires

Il existe quatre foncteurs unaires en logique bivalente :

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):

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)

Le problème de l'implication

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é :

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 :

Exemples :

On a le système prototype ∧,~,∨ (et, non, ou), fonctionnellement complet ; pour ∧,~, on remplace le "∨" :

En conséquence :

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 :

Méthode pour faire un calcul

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))


A lire

Voir aussi