Exercice de terminale C

Bonjour Dido
Une table de vérité sous forme de table de Karnaugh est un carré 2x2, avec (par exemple) A sur le côté valant 0 (1ère ligne) ou 1 (2ème ligne) et B au dessus valant 0 (1ère colonne) et 1 (2ème colonne).
Chaque case vaut 1 si la proposition est vraie et 0 sinon.
On doit donc obtenir quatre tables identiques.
Alain

Je vais prendre la deuxième proposition.

$\begin{matrix}
A & B & || & A & \cap & B & = & A \\
== & == & == & == & == & == & == & == \\
F & F & || & F & F & F & V & F \\
F & V & || & F & F & V & V & F \\
V & F & || & V & F & F & V & F \\
V & V & || & V & V & V & V & V
\end{matrix}$

Ceux qui comptent sont les V sous le dernier opérateur calculé, ici l’égalité.
$A \subset B$ s’écrit $B \implies A$.

Bonsoir

Ev m'a devancé, fort heureusement. Je vois mal comment l'on peut affecter une valeur de vérité à un ensemble. A la rigueur, l'affecter à un énoncé du style $x\in{}A$ ne m'aurait pas choqué du tout. Enfin, $A\subset{}B\Leftrightarrow(\forall\,x)(x\in{}A\Rightarrow{}x\in{}B)$.

Bonne soirée.

Thierry

Si A est inclus dans B, cela veut dire que si B est vraie alors A aussi. Plus précisément, cela veut dire que le cas A faux et B vrai est… faux. Les trois autres cas restent possibles, c’est bien l’implication voulue.
Comme tu as utilisé les notations ensemblistes, j’ai proposé les notations de Venn. Si tu préfères, tu peux traduire les notations ensemblistes mot à mot et remplaçant $\cup$ par OU, $\cap$ par ET, $=$ par équivalent, etc.

On parle de logique booléenne puisque dès le message d’ouverture, dido parle de propositions.

René Cori a co-écrit le document et c’est loin d’être une buse en logique.

Le problème de tous ces documents est qu'ils escamotent typage et variables liées sous prétexte de pédagogie et donc on mélange tout.

Cet exo est un exo d'algèbres de Boole déguisé.

Faisons un topo rapide.

1°) Une algèbre de Boole $(A,+,\times)$ est un anneau dans lequel $x^2=x$ pour tout $x\in A$. Cela équivaut (on ne va pas le prouver ici mais c'est pour donner la motivation derrière le concept) à ce qu'il existe un ensemble $I$ tel que $(A,+,\times)$ est isomorphe à un sous-anneau de l'anneau produit $(\Z/2\Z)^I$.
Notamment, $A$ est commutatif est de caractéristique $2$ (c'est un exo connu, traitable directement à partir de la définition; on va admettre ses conclusions dans le reste de ce qui suit mais si vous ne l'avez jamais vu, je vous le recommande).

2°) Bien évidemment, $(\Z/2\Z,+,\times)$ est une algèbre de Boole, la plus simple de toutes (on emploie parfois les notations $"faux":=0$ et $"vrai":=1$).
Citons aussi (c'est l'exemple du présent fil) $(\mathcal P(E),\Delta, \cap)$ où $X\Delta Y := (X \cup Y) \backslash (X \cap Y)$, l'isomorphisme entre $\mathcal P(E)$ étant donné par l'application qui à $A\in \mathcal P(E)$ fait correspondre sa fonction caractéristique (si vous ne voyez pas ou ne savez plus à quoi correspond la mystérieuse opération "$\Delta$", dite "différence symétrique", pensez à cet isomorphisme).

3° ) Dans une algèbre de Boole $(A,+,\times)$, les opérations qui importent ne sont pas $+$ et $\times$ mais plutôt $\vee$, $\times$ (et $\times $ est renommé en $\wedge$) où $x\vee y:= x+y + (x \times y)$ (à nouveau songez à la différence symétrique) et $\neg$ donnée par $\neg z := 1-z$ pour tout $z\in A$.
Bien sûr d'autres opérations dérivées de ces opérations sont définissables, par exemple:
$x \Rightarrow y:=(\neg x) \vee y$
$x \Leftrightarrow y := (x \Rightarrow y) \wedge (y \Rightarrow x)$.
$x|y:= \neg (x \wedge y)$. ("nand")

4°) Noter qu'on aurait pu définir "$+$" à partir de $\wedge,\vee,\neg$, via $a+b:=(a \vee b) \wedge \neg (a \wedge b)$ pour tous $a,b$ (le lecteur peut vérifier cette égalité; on retrouve la définition de la différence symétrique plus haut comme cas particulier). Cependant définir les algèbres de Boole avec des axiomes portant sur $\wedge,\vee,\neg$ est plus délicat, j'ai choisi cette présentation pour que ça aille vite (encore que voir plus bas).

Maintenant que nous avons les opérations basiques internes à $A$, définissons sur $A$ une relation binaire qui s'avèrera être une relation d'ordre.

5°) On pose pour tous $x,y\in A$, $x \leq y:= x = xy$. C'est-à-dire qu'on décrète que "$x$ est plus petit que $y$" si $x=xy = x \wedge y$.

On vérifie qu'il s'agit d'un ordre (exercice routinier), qui est précisément l'inclusion lorsque $A$ est un sous anneau de $\mathcal P(E)$.

L'exo dont le fil est l'objet se traduit intégralement dans ce formalisme.

-Une valeur de vérité est un morphisme d'anneau entre une algèbre de Boole et $\Z/2\Z$ (pourquoi? expliquer)

###########################

BONUS: Algèbres de Heyting.

6°) On appelle algèbre de Heyting un ensemble ordonné $(H,\leq)$ pour lequel:
(i) Toute partie finie (même vide) de $H$ possède une borne supérieure et une borne inférieure dans $H$ (pour tous $x,y\in H$, les notations $x\vee y:= \sup \{x,y\}$ et $x \wedge y:= \inf \{x,y\}$ sont couramment employées).
(ii) Pour tous $a,b\in H$, l'ensemble des $x\in H$ tels que $a\wedge x\leq b$ possède un plus grand élément noté $a\Rightarrow b$.

Il se trouve que les algèbres de Heyting généralisent les algèbres de Boole:
7°) montrer (exo) qu'avec l'ordre défini au paragraphe précédent, tout algèbre de Boole est une algèbre de Heyting (avec les mêmes notations).

La réciproque est fausse: pour tout espace topologique $X$, l'ensemble des ouverts de $X$ ordonné par l'inclusion est une algèbre de Heyting (exo) mais n'est pas une algèbre de Boole en général ($\R$ fournit déjà un contre exemple).

Cependant:
8°) Toute algèbre de Heyting $(H,\leq)$ est aussi une algèbre de Boole si et seulement si $(x \Rightarrow y) \Rightarrow y = x \vee y$ pour tous $x,y$ (ce n'est pas vraiment immédiat avec les seuls résultats évoquées dans ce message).
Il y a d'autres caractérisations.