TD5 – Logique Booléenne

Équivalences remarquables

On dit que deux formules propositionnelles sont équivalentes si elles ont la même table de vérité. Montrer l’équivalence des formules suivantes :

$˥ (p ∧ q)$ et $˥p ∨ ˥q$ ,
$˥ (p ∨ q)$ et $˥p ∧ ˥q$ (lois de Morgan) ;
$p ⇒ q$ et $˥p ∨ q$  ;
$p ⇒ q$ et $˥q ⇒ ˥p$ (contraposée) ;
$(p ∧ (p ⇒ q)) ⇒ q$ (modus ponens) et $( ˥q ∧ (p ⇒ q)) ⇒ ˥p$ (modus tolens) ;
$p ⇒ (q ⇒ r)$ et $(p ∧ q) ⇒ r$ (exportation ou curryfication).

Propositions en arithmétique

Quelle est la valeur de vérité de chacune des formules suivantes ?

Suggestion : Écrivez des formules booléenne représentant ces phrases, puis, en utilisant les équivalences vues plus haut, réduisez-les à des évidences.

$(5$ est un entier positif $) ∨ ( 2 < 3)$  ;
$(5$ est un entier positif $) ∨ (2 ≥ 3)$  ;
$( 3 > 2) ∧ ( 2 + 3 = 4)$  ;
$( 3 ≤ 2) ∧ ( 2 + 3 = 5)$  ;
$( 3 ≤ 2) ⇒ ( 4 = 5 + 3)$  ;
Soit $4$ ne divise pas $n$ , soit $n$ est pair ;
Soit $n$ est impair, soit $4$ divise $n$  ;
$a \le 0$ et $a \ge 0$ impliquent que $a=0$  ;
Si $a\le 0$ implique que $a\ge 0$ , alors $a \ge 0$  ;
Si $n$ est pair, alors $1+1=2$  ;
Si $1+1=3$ , alors les nombres premiers sont en quantité finie.

Modéliser la langue parlée

Du français au calcul des propositions…

Pour chacun des énoncés suivants, représenter les propositions élémentaires par une formule atomique (une lettre de l’alphabet) et montrer quelle est la forme logique de l’énoncé.

Ou ce n’est pas Sophia, ou bien elle a beaucoup changé.
Si c’est Sophia, elle a beaucoup changé.
Karpov doit sacrifier une tour ou Kasparov fera mat en trois coups.
Si Karpov ne sacrifie pas une tour, Kasparov fera mat en trois coups.
Ni Paul ni Maurice n’ont réussi.
Paul et Maurice ne réussiront pas tous les deux.
Si Maurice réussit, Paul réussira, sinon aucun des deux ne réussira.

… et retour

Soient $p$ et $s$ les propositions signifiant respectivement « Paul aime Sophie » et « Sophie aime Paul ». Pour chacune des formules suivantes, trouver un énoncé en français (cohérent et simple) qui lui corresponde.

$(\neg p) \wedge s$ ,
$\neg(p\wedge s)$ ,
$\neg(p\vee s)$ ,
$p \leftrightarrow s$ ,
$\neg(p \to s)$ .

Implication

Écrire la réciproque et la contraposée des implications suivantes :
- Si 2 + 2 = 3 alors je suis le roi de Prusse.
- S’il fait bon et si je ne suis pas trop fatigué alors je vais me promener.
- Si je gagne au LOTO alors je sable le champagne et je pars aux Bahamas.
Soient les propositions $p$ et $q$  :
- $p$  : «  $x$ est un entier pair »,
- $q$  : «  $x$ est divisible par 4 ».
Le prédicat $p$ est-il une condition suffisante de $q$  ? Une condition nécessaire ?
Un logicien dit à son fils : « si tu ne manges pas ta soupe, tu ne regarderas pas la télévision ». Le fils mange sa soupe et son dîner, et il est envoyé au lit tout de suite après. Quelle erreur avait faite le fils en pensant regarder la télé après le dîner ?
On interroge un logicien qui dit toujours la vérité sur sa vie sentimentale et il énonce les deux affirmations suivantes :
- J’aime Marie ou j’aime Anne,
- Si j’aime Marie alors j’aime Anne,
Que peut-on en conclure ?
Si le même logicien, avait répondu (sans donner les deux affirmations précédentes) à la question : « Est-il vrai que si vous aimez Marie alors vous aimez Anne » par :

« Si c’est vrai alors j’aime Marie, et si j’aime Marie alors c’est vrai. »

Qu’aurait-on pu conclure ?

Contradictions et vérité

Un logicien fait un cauchemar. Il erre dans un labyrinthe et il arrive à un endroit où le chemin se sépare en deux. Deux diables (A et B) sont à la croisée. Quand le logicien demande le chemin de la sortie, les diables répondent :
- A : « B n’est pas un menteur et la sortie est à gauche » ;
- B : « A est un menteur et la sortie est à gauche ».
Quel chemin prend le logicien pour sortir ?
Le lendemain, le logicien refait un cauchemar similaire. Il repose la même question.
- A : « B n’est pas un menteur et la sortie est à gauche » ;
- B : « A est un menteur ou la sortie est à droite ».
Quel est cette fois le chemin de la sortie ?