Équivalence logique - Logical equivalence

En logique et en mathématiques , les énoncés et sont dits logiquement équivalents s'ils sont prouvables les uns des autres sous un ensemble d'axiomes, ou ont la même valeur de vérité dans chaque modèle . L'équivalence logique de et est parfois exprimée par , , , ou , selon la notation utilisée. Cependant, ces symboles sont également utilisés pour l' équivalence matérielle , donc une interprétation correcte dépendrait du contexte. L'équivalence logique est différente de l'équivalence matérielle, bien que les deux concepts soient intrinsèquement liés. ${\style d'affichage p}$${\style d'affichage q}$${\style d'affichage p}$${\style d'affichage q}$${\style d'affichage p\équiv q}$${\style d'affichage p::q}$${\displaystyle {\textsf {E}}pq}$${\style d'affichage p\iff q}$

Équivalences logiques

En logique, de nombreuses équivalences logiques communes existent et sont souvent répertoriées comme des lois ou des propriétés. Les tableaux suivants en illustrent quelques-uns.

Équivalences logiques générales

Équivalence	Nom
${\displaystyle p\wedge \top \equiv p}$ ${\displaystyle p\vee \bot \equiv p}$	Lois identitaires
${\displaystyle p\vee \top \equiv \top }$ ${\displaystyle p\wedge \bot \equiv \bot }$	Lois de domination
${\displaystyle p\vee p\equiv p}$ ${\displaystyle p\wedge p\equiv p}$	Lois idempotentes ou tautologies
${\displaystyle \neg (\neg p)\équiv p}$	Loi de la double négation
${\displaystyle p\vee q\équiv q\vee p}$ ${\displaystyle p\wedge q\équiv q\wedge p}$	Lois commutatives
${\displaystyle (p\vee q)\vee r\equiv p\vee (q\vee r)}$ ${\displaystyle (p\wedge q)\wedge r\equiv p\wedge (q\wedge r)}$	Lois associatives
${\displaystyle p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)}$ ${\displaystyle p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)}$	Lois distributives
${\displaystyle \neg (p\wedge q)\equiv \neg p\vee \neg q}$ ${\displaystyle \neg (p\vee q)\equiv \neg p\wedge \neg q}$	Les lois de De Morgan
${\displaystyle p\vee (p\wedge q)\équiv p}$ ${\displaystyle p\wedge (p\vee q)\équiv p}$	Lois d'absorption
${\displaystyle p\vee \neg p\equiv \top }$ ${\displaystyle p\wedge \neg p\equiv \bot }$	Lois de négation

Équivalences logiques impliquant des instructions conditionnelles

1. ${\displaystyle p\implies q\equiv \neg p\vee q}$
2. ${\displaystyle p\implies q\equiv \neg q\implies \neg p}$
3. ${\displaystyle p\vee q\equiv \neg p\implies q}$
4. ${\displaystyle p\wedge q\equiv \neg (p\implique \neg q)}$
5. ${\displaystyle \neg (p\implique q)\equiv p\wedge \neg q}$
6. ${\displaystyle (p\implies q)\wedge (p\implies r)\equiv p\implies (q\wedge r)}$
7. ${\displaystyle (p\implies q)\vee (p\implies r)\equiv p\implies (q\vee r)}$
8. ${\displaystyle (p\implies r)\wedge (q\implies r)\equiv (p\vee q)\implies r}$
9. ${\displaystyle (p\implies r)\vee (q\implies r)\equiv (p\wedge q)\implies r}$

Équivalences logiques impliquant des biconditionnels

1. ${\displaystyle p\iff q\equiv (p\implique q)\wedge (q\implique p)}$
2. ${\displaystyle p\iff q\équiv \neg p\iff \neg q}$
3. ${\displaystyle p\iff q\equiv (p\wedge q)\vee (\neg p\wedge \neg q)}$
4. ${\displaystyle \neg (p\iff q)\équiv p\iff \neg q}$

Exemples

En logique

Les déclarations suivantes sont logiquement équivalentes :

1. Si Lisa est au Danemark , alors elle est en Europe (une déclaration de la forme ).${\displaystyle d\implique e}$
2. Si Lisa n'est pas en Europe, alors elle n'est pas au Danemark (une déclaration de la forme ).${\displaystyle \neg e\implies \neg d}$

Syntaxiquement, (1) et (2) sont dérivables l'un de l'autre via les règles de contraposition et de double négation . Sémantiquement, (1) et (2) sont vrais dans exactement les mêmes modèles (interprétations, valorisations) ; à savoir, ceux dans lesquels Lisa est au Danemark est faux ou Lisa est en Europe est vrai.

(Notez que dans cet exemple, la logique classique est supposée. Certaines logiques non classiques ne considèrent pas (1) et (2) comme étant logiquement équivalents.)

En mathématiques

En mathématiques, deux déclarations et sont souvent dits logiquement équivalentes, si elles sont démontrables les uns des autres étant donné un ensemble d'axiomes et de présuppositions. Par exemple, l'énoncé « est divisible par 6 » peut être considéré comme équivalent à l'énoncé « est divisible par 2 et 3 », puisqu'on peut prouver le premier à partir du second (et vice versa) en utilisant certaines connaissances de la théorie des nombres de base . ${\style d'affichage p}$${\style d'affichage q}$${\style d'affichage n}$${\style d'affichage n}$

Relation avec l'équivalence matérielle

L'équivalence logique est différente de l'équivalence matérielle. Les formules et sont logiquement équivalentes si et seulement si l'énoncé de leur équivalence matérielle ( ) est une tautologie. ${\style d'affichage p}$${\style d'affichage q}$${\style d'affichage p\iff q}$

L'équivalence matérielle de et (souvent écrit comme ) est elle-même une autre déclaration dans le même langage objet que et . Cette déclaration exprime l'idée "' si et seulement si '". En particulier, la valeur de vérité de peut changer d'un modèle à l'autre. ${\style d'affichage p}$${\style d'affichage q}$${\displaystyle p\leftrightarrow q}$${\style d'affichage p}$${\style d'affichage q}$${\style d'affichage p}$${\style d'affichage q}$${\displaystyle p\leftrightarrow q}$

D'autre part, l'affirmation selon laquelle deux formules sont logiquement équivalentes est une déclaration en métalangage , qui exprime une relation entre deux déclarations et . Les énoncés sont logiquement équivalents si, dans chaque modèle, ils ont la même valeur de vérité. ${\style d'affichage p}$${\style d'affichage q}$

Voir également

• Implication
• Équisatisfiabilité
• Si et seulement si
• Biconditionnel logique
• Égalité logique
• ≡ le symbole iff (U+2261 IDENTIQUE À )
• ∷ l' un est à b comme c est d symbole (U + 2237 PROPORTION )
• ⇔ le double frappé biconditionnel (U+21D4 GAUCHE DROITE DOUBLE FLÈCHE )
• ↔ la flèche bidirectionnelle (U+2194 FLÈCHE GAUCHE DROITE )

Les références