Mathématiques discrètes - Logique propositionnelle
Les règles de la logique mathématique spécifient les méthodes de raisonnement des énoncés mathématiques. Le philosophe grec Aristote a été le pionnier du raisonnement logique. Le raisonnement logique fournit la base théorique de nombreux domaines des mathématiques et par conséquent de l'informatique. Il a de nombreuses applications pratiques en informatique comme la conception de machines informatiques, l'intelligence artificielle, la définition de structures de données pour les langages de programmation, etc.
Propositional Logicconcerne les déclarations auxquelles les valeurs de vérité, «vrai» et «faux», peuvent être attribuées. Le but est d'analyser ces déclarations soit individuellement, soit de manière composite.
Logique prépositionnelle - Définition
Une proposition est un ensemble d'énoncés déclaratifs qui ont soit une valeur de vérité «vrai», soit une valeur de vérité «faux». Une proposition est constituée de variables propositionnelles et de connecteurs. Les connecteurs connectent les variables propositionnelles.
Quelques exemples de propositions sont donnés ci-dessous -
- "L'homme est mortel", il renvoie la valeur de vérité "TRUE"
- "12 + 9 = 3 - 2", il renvoie la valeur de vérité "FALSE"
Ce qui suit n'est pas une proposition -
"A est inférieur à 2". C'est parce qu'à moins de donner une valeur spécifique de A, nous ne pouvons pas dire si l'énoncé est vrai ou faux.
Connectifs
Dans la logique propositionnelle, nous utilisons généralement cinq connecteurs qui sont -
OU ($ \ lor $)
ET ($ \ terre $)
Négation / NOT ($ \ lnot $)
Implication / si-alors ($ \ rightarrow $)
Si et seulement si ($ \ Leftrightarrow $).
OR ($\lor$) - L'opération OR de deux propositions A et B (écrites comme $ A \ lor B $) est vraie si au moins l'une des variables propositionnelles A ou B est vraie.
La table de vérité est la suivante -
| UNE | B | A ∨ B |
|---|---|---|
| Vrai | Vrai | Vrai |
| Vrai | Faux | Vrai |
| Faux | Vrai | Vrai |
| Faux | Faux | Faux |
AND ($\land$) - L'opération ET de deux propositions A et B (écrites comme $ A \ land B $) est vraie si les deux variables propositionnelles A et B sont vraies.
La table de vérité est la suivante -
| UNE | B | A ∧ B |
|---|---|---|
| Vrai | Vrai | Vrai |
| Vrai | Faux | Faux |
| Faux | Vrai | Faux |
| Faux | Faux | Faux |
Negation ($\lnot$) - La négation d'une proposition A (écrite comme $ \ lnot A $) est fausse quand A est vraie et est vraie quand A est fausse.
La table de vérité est la suivante -
| UNE | ¬ A |
|---|---|
| Vrai | Faux |
| Faux | Vrai |
Implication / if-then ($\rightarrow$)- Une implication $ A \ rightarrow B $ est la proposition «si A, alors B». Il est faux si A est vrai et B est faux. Les autres cas sont vrais.
La table de vérité est la suivante -
| UNE | B | A → B |
|---|---|---|
| Vrai | Vrai | Vrai |
| Vrai | Faux | Faux |
| Faux | Vrai | Vrai |
| Faux | Faux | Vrai |
If and only if ($ \Leftrightarrow $) - $ A \ Leftrightarrow B $ est un connecteur logique bi-conditionnel qui est vrai lorsque p et q sont identiques, c'est-à-dire que les deux sont faux ou les deux sont vrais.
La table de vérité est la suivante -
| UNE | B | A ⇔ B |
|---|---|---|
| Vrai | Vrai | Vrai |
| Vrai | Faux | Faux |
| Faux | Vrai | Faux |
| Faux | Faux | Vrai |
Tautologies
Une tautologie est une formule qui est toujours vraie pour chaque valeur de ses variables propositionnelles.
Example - Prouver que $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ est une tautologie
La table de vérité est la suivante -
| UNE | B | A → B | (A → B) ∧ A | [(A → B) ∧ A] → B |
|---|---|---|---|---|
| Vrai | Vrai | Vrai | Vrai | Vrai |
| Vrai | Faux | Faux | Faux | Vrai |
| Faux | Vrai | Vrai | Faux | Vrai |
| Faux | Faux | Vrai | Faux | Vrai |
Comme nous pouvons voir que chaque valeur de $ \ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B $ est "True", c'est une tautologie.
Contradictions
Une contradiction est une formule qui est toujours fausse pour chaque valeur de ses variables propositionnelles.
Example - Prouvez que $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ est une contradiction
La table de vérité est la suivante -
| UNE | B | A ∨ B | ¬ A | ¬ B | (¬ A) ∧ (¬ B) | (A ∨ B) ∧ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| Vrai | Vrai | Vrai | Faux | Faux | Faux | Faux |
| Vrai | Faux | Vrai | Faux | Vrai | Faux | Faux |
| Faux | Vrai | Vrai | Vrai | Faux | Faux | Faux |
| Faux | Faux | Faux | Vrai | Vrai | Vrai | Faux |
Comme nous pouvons voir que chaque valeur de $ (A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ est «False», c'est une contradiction.
Contingence
Une contingence est une formule qui a à la fois des valeurs vraies et des valeurs fausses pour chaque valeur de ses variables propositionnelles.
Example - Prouver $ (A \ lor B) \ land (\ lnot A) $ une contingence
La table de vérité est la suivante -
| UNE | B | A ∨ B | ¬ A | (A ∨ B) ∧ (¬ A) |
|---|---|---|---|---|
| Vrai | Vrai | Vrai | Faux | Faux |
| Vrai | Faux | Vrai | Faux | Faux |
| Faux | Vrai | Vrai | Vrai | Vrai |
| Faux | Faux | Faux | Vrai | Faux |
Comme nous pouvons voir que chaque valeur de $ (A \ lor B) \ land (\ lnot A) $ a à la fois «True» et «False», c'est une contingence.
Équivalences propositionnelles
Deux instructions X et Y sont logiquement équivalentes si l'une des deux conditions suivantes est remplie -
Les tables de vérité de chaque déclaration ont les mêmes valeurs de vérité.
L'instruction bi-conditionnelle $ X \ Leftrightarrow Y $ est une tautologie.
Example - Prouvez que $ \ lnot (A \ lor B) et \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ sont équivalents
Test par 1ère méthode (Table de vérité correspondante)
| UNE | B | A ∨ B | ¬ (A ∨ B) | ¬ A | ¬ B | [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|---|---|
| Vrai | Vrai | Vrai | Faux | Faux | Faux | Faux |
| Vrai | Faux | Vrai | Faux | Faux | Vrai | Faux |
| Faux | Vrai | Vrai | Faux | Vrai | Faux | Faux |
| Faux | Faux | Faux | Vrai | Vrai | Vrai | Vrai |
Ici, nous pouvons voir que les valeurs de vérité de $ \ lnot (A \ lor B) et \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ sont identiques, donc les déclarations sont équivalentes.
Test par 2 ème méthode (bi-conditionnalité)
| UNE | B | ¬ (A ∨ B) | [(¬ A) ∧ (¬ B)] | [¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)] |
|---|---|---|---|---|
| Vrai | Vrai | Faux | Faux | Vrai |
| Vrai | Faux | Faux | Faux | Vrai |
| Faux | Vrai | Faux | Faux | Vrai |
| Faux | Faux | Vrai | Vrai | Vrai |
Comme $ \ lbrack \ lnot (A \ lor B) \ rbrack \ Leftrightarrow \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack $ est une tautologie, les déclarations sont équivalentes.
Inverse, Converse et Contra-positif
Implication / if-then $ (\ rightarrow) $ est également appelé une instruction conditionnelle. Il comporte deux parties -
- Hypothèse, p
- Conclusion, q
Comme mentionné précédemment, il est noté $ p \ rightarrow q $.
Example of Conditional Statement- «Si vous faites vos devoirs, vous ne serez pas puni.» Ici, "vous faites vos devoirs" est l'hypothèse, p, et "vous ne serez pas puni" est la conclusion, q.
Inverse- Un inverse de l'énoncé conditionnel est la négation à la fois de l'hypothèse et de la conclusion. Si l'énoncé est «Si p, alors q», l'inverse sera «Sinon p, alors pas q». Ainsi, l'inverse de $ p \ rightarrow q $ est $ \ lnot p \ rightarrow \ lnot q $.
Example - L'inverse de "Si vous faites vos devoirs, vous ne serez pas puni" est "Si vous ne faites pas vos devoirs, vous serez puni."
Converse- L'inverse de l'énoncé conditionnel est calculé en interchangeant l'hypothèse et la conclusion. Si l'instruction est «Si p, alors q», l'inverse sera «Si q, alors p». L'inverse de $ p \ rightarrow q $ est $ q \ rightarrow p $.
Example - Le contraire de "Si vous faites vos devoirs, vous ne serez pas puni" est "Si vous ne serez pas puni, vous faites vos devoirs".
Contra-positive- Le contre-positif du conditionnel est calculé en échangeant l'hypothèse et la conclusion de l'énoncé inverse. Si l'énoncé est «Si p, alors q», la contre-positive sera «Sinon q, alors pas p». La contre-positive de $ p \ rightarrow q $ est $ \ lnot q \ rightarrow \ lnot p $.
Example - Le contre-positif de "Si vous faites vos devoirs, vous ne serez pas puni" est "Si vous êtes puni, vous n'avez pas fait vos devoirs".
Principe de dualité
Le principe de dualité stipule que pour toute déclaration vraie, la déclaration double obtenue en interchangeant les unions en intersections (et vice versa) et en échangeant l'ensemble universel en ensemble nul (et vice versa) est également vraie. Si le double d'une déclaration est la déclaration elle-même, il est ditself-dual déclaration.
Example - Le dual de $ (A \ cap B) \ cup C $ est $ (A \ cup B) \ cap C $
Formes normales
Nous pouvons convertir n'importe quelle proposition sous deux formes normales -
- Forme normale conjonctive
- Forme normale disjonctive
Forme normale conjonctive
Une instruction composée est sous forme normale conjonctive si elle est obtenue en opérant ET parmi des variables (négation des variables incluses) liées à des OR. En termes d'opérations d'ensembles, il s'agit d'une instruction composée obtenue par Intersection entre des variables liées aux Unions.
Examples
$ (A \ lor B) \ land (A \ lor C) \ land (B \ lor C \ lor D) $
$ (P \ cup Q) \ cap (Q \ cup R) $
Forme normale disjonctive
Une instruction composée est sous forme normale disjonctive si elle est obtenue en opérant OU parmi des variables (négation des variables incluses) connectées avec des ET. En termes d'opérations d'ensemble, il s'agit d'un énoncé composé obtenu par Union parmi des variables liées aux Intersections.
Examples
$ (A \ land B) \ lor (A \ land C) \ lor (B \ land C \ land D) $
$ (P \ cap Q) \ tasse (Q \ cap R) $