Logique Élémentaire

Propositions et assertions

Definition

Une proposition, ou assertion, est une phrase qui peut être vraie ou fausse.

Remarque

Les propositions peuvent être mathématiques, ou plus générales.
Nous utiliserons les lettres capitales A, B etc. pour désigner des assertions mathématiques. On peut noter qu'un phrase en langue naturelle peut être vraie ou fausse, mais peut aussi ne pas avoir de valeur de vérité bien définie.

Tautologie

Definition

Une tautologie est une assertion qui est vraie du fait de sa construction.

Opérations sur les assertions

Définitions

• La négation d'une assertion $A$, notée $\neg A$, est l'assertion qui est vraie si $A$ et fausse, et fausse si $A$ est vraie.

• La conjonction de deux assertions $A$ et $B$, notée $A \wedge B$, est l'assertion qui est vraie si et seulement si $A$ et vraie et $B$ est vraie. On la lit “et”.

• La disjonction de deux assertions $A$ et $B$, est l'assertion $A \vee B$ qui est vraie si et seulement si $A$ est vraie ou $B$ est vraie. On la lit “ou”.

Remarque

Dans une expression composée, la négation prend la priorité sur $\vee$ et $\wedge$.

Propositions atomiques, assertions atomiques, variables proportionnelles

Definition

Les assertions atomiques, sont des assertions qui ne sont pas obtenues comme composition d'autres assertions.

Table de vérité

Les tables de vérité sont un moyen efficace pour analyser une proposition composée C à partir de plusieurs assertions atomiques $A$, $B$, ... Ce sont des tableaux ayant une ligne pour chaque valeur possible des assertions $A$, $B$, ... qui apparaissent dans $C$, et on met dans les cases correspondantes les valeurs de $C$. Ces valeurs sont obtenues à partir des valeurs des variables propositionnelles en utilisant les tables de vérités qui définissent les opérations $\wedge$, $\vee$ et $\neg$, et en utilisant les règles de priorités sur les opérations. On représente habituellement la valeur “vrai” par $1$ et “faux” par $0$, et on parle de valeurs de vérités.

L'algèbre de Boole

Propriétés

• Associativité de $\wedge$

  $$ A \wedge \left( B \wedge C \right) = \left( A \wedge B \right) \wedge C $$

• Associativité de $\vee$

  $$ A \vee \left( B \vee C \right) = \left( A \vee B \right) \vee C $$

• Commutativité de $\wedge $

  $$ A \wedge B = B \wedge A $$

• Commutativité de $\vee $

  $$ A \vee B = B \vee A $$

• Distributivité de $\wedge$ par rapport à $\vee$

  $$ A \wedge (B \vee C) = (A \wedge B) \vee (A \wedge C) $$

• L'assertion vraie 1 est élément neutre pour $\wedge$ et
  l'assertion fausse 0 est élément neutre pour $\vee$.

  $$ A \wedge 1 = A $$ $$ A \vee 0 = A $$

• Distributivité de $\vee$ par rapport à $\wedge$

  $$ A \vee (B \wedge C) = (A \vee B) \wedge (A \vee C) $$

• Double négation

  $$ \neg (\neg A) = A $$

• Loi de Morgan

  $$ \neg ( A \vee B ) = (\neg A) \wedge (\neg B) $$

• Loi de Morgan

  $$ \neg ( A \wedge B ) = (\neg A) \vee (\neg B) $$
• $$ (\neg A) \wedge A = 0 $$
• $$ (\neg A) \vee A = 1 $$

• Loi d'absorption

  • $$ (A \wedge B) \vee B = B $$
  • $$ (A \vee B) \wedge B = B $$

Implication et équivalence

A partir des opérateurs $\neg$, $\wedge$ et $\vee$, on peut introduire d'autres opérateurs logiques utiles.

Définition

On note $\Rightarrow $ l'opérateur "Implication" défini pour deux assertions $A$ et $B$ quelconques par:

$$ (A \Rightarrow B) = (\neg A) \vee B$$

Remarque

On dira que $A$ implique $B$ si l'assertion $A \Rightarrow B$ est vraie. On dit que $A$ est l'antécédent, et que $B$ est le conséquent, de l'implication $A \Rightarrow B$.

Définition

L'implication $B \Rightarrow A$ est appelée réciproque de l'implication $A \Rightarrow B$.

Conséquence

• Il suit de la définition que $A \Rightarrow B$ est vraie sauf dans le cas où $A$ est vraie et $B$ est fausse. Ceci correspond à l'implication qu'on utilise dans le langage courant.

• On note aussi $\Leftarrow$ l'implication dans le sens inverse, c'est-à-dire que $B \Leftarrow A$ est équivalent à $A \Leftarrow B$.

Définition

L'implication $(\neg B) \Rightarrow (\neg A)$ est appelée contraposée de l'implication $A \Rightarrow B$.

Proposition

Une implication est équivalente à sa contraposée.

Démonstration

On veut montrer que $A \Rightarrow B$ est vraie si et seulement si $(\neg A) \Rightarrow (\neg B)$. Or $A \Rightarrow B$ est fausse si et seulement si $A$ est vraie et $B$ et fausse. Mais $(\neg B) \Rightarrow (\neg A)$ est fausse si et seulement si $(\neg B)$ est vraie et $(\neg A)$ est fausse, donc si et seulement si A est vraie et B est fausse. Les deux assertions ont donc exactement les mêmes valeurs de vérité, elles sont donc équivalentes.

$$ \left( A\Rightarrow B\right) =\left( \left( \neg A\right) \vee B\right) $$ $$ =((\neg A) \vee (\neg(\neg B))) $$ $$ =( (\neg(\neg B)) \vee (\neg A) ) $$ $$ (\neg B) \Rightarrow (\neg A) $$

cqfd.