Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Licence Maths 1e ann LogiqueTopics traitant de logique [tout]Lister tous les topics de mathématiques
Niveau Licence Maths 1e ann
Partager :

Relation d'ordre et algèbre de Boole

Posté par
sief 04-05-17 à 01:22

Bonjour,
J'ai deux questions si vous pouvez m'aider.
Merci.

Soit $X=\left\{ 1,2 \right\}$ .On considère l'ensemble $E={{X}^{3}}$ des triplets d'éléments de $X$. On définit la relation  $\mathcal{R}$ sur $E$ de la façon suivante : pour tout $\left( a,b,c \right)\in E$ et pour tout $\left( x,y,z \right)\in E$ , on a  $\left( a,b,c \right)\mathcal{R}\left( x,y,z \right)$ si et seulement si $a\le x$ et $b\le y$ et $c\le z$ . Par exemple, on a $\left( 1,2,1 \right)$ est en relation avec $\left( 2,2,1 \right)$.

1) Dessiner le diagramme de Hasse de l'ensemble $E$ ordonne par $\mathcal{R}$

2) Est-ce que l'ensemble  $E$ ordonne par $\mathcal{R}$ est une algèbre de Boole ?

Pour le diagramme j'ai fait, mais  pour l'algèbre de Boole normalement un Treillis distributif et complémenté c'est une algèbre de Boole.
Je pense qu'il s'agit bien d'un treillis, c'est cela ma question est qu'il faut passer par tous les triplets pour vérifier si c'est distributif et complémenté ?

Posté par
jsvdbre : Relation d'ordre et algèbre de Boole 04-05-17 à 09:27

Bonjour sief

Qui dit Algèbre de Boole dit deux lois de composition interne.
Qui dit relation d'ordre trouve deux lois internes naturelles à vocation à faire une algèbre de Boole.

Explicite ces deux lois et trouve leur expression en fonction des composantes des éléments de E.

Posté par
siefre : Relation d'ordre et algèbre de Boole 04-05-17 à 20:32

Bonsoir ,
J'ai donné la définition que j'ai dans mon cours , personne ici ne peut m'aider ?

Posté par
jsvdbre : Relation d'ordre et algèbre de Boole 04-05-17 à 22:14

Non, tu as donné la définition de la relation d'ordre sur E, pas des lois internes qui font de E un treillis ! Quelles sont ces deux lois ? Elles sont définies naturellement à partir de la relation d'ordre !

a \land b = ...

a \lor b = ...

Posté par
siefre : Relation d'ordre et algèbre de Boole 05-05-17 à 02:00

bonsoir ,
Non je n'ai pas donner la définition de la relation d'ordre.
Relation d'ordre est une relation réflexive, antisymétrique et transitive.
Un ensemble ordonné A est un treillis si :
Pour tout x et y dans A :
1-$x\vee y=\sup \left( x,y \right)$ : le plus petit élément de l'ensemble des majorants commun à x et y

2- $x\wedge y=\inf \left( x,y \right)$ : le plus grand élément de l'ensemble des minorants commun à x et y.

Algèbre de Boole est un treillis à la fois distributif et complémenté

Posté par
siefre : Relation d'ordre et algèbre de Boole 05-05-17 à 02:01

moi je cherche a montrer que l'ensemble E est une algèbre de Boole

Posté par
jsvdbre : Relation d'ordre et algèbre de Boole 05-05-17 à 02:35

Alors maintenant, décortiquons ceci :

Z= x\vee y=\sup \left( x,y \right) est un élément qui existe puisque E muni de sa relation d'ordre a un plus grand élément.

Si x=(x_1,x_2,x_3) et y=(y_1,y_2,y_3) peux-tu expliciter Z=(Z_1,Z_2,Z_3) ?

Tu fais de même pour  z=x\wedge y=\inf \left( x,y \right) : peux-tu expliciter z=(z_1,z_2,z_3) ?

Si tu trouves les Z_i et les z_i alors il te sera facile de montrer que ton treillis est distributif et complémenté et tu n'auras pas besoin de "passer par tous les triplets".

Posté par
siefre : Relation d'ordre et algèbre de Boole 05-05-17 à 02:57

Comment va-t-on les trouver si l'on ne passe pas par tous les triplets ?

Posté par
siefre : Relation d'ordre et algèbre de Boole 05-05-17 à 03:00

par absurde !

Posté par
jsvdbre : Relation d'ordre et algèbre de Boole 05-05-17 à 13:32

Il n'y a aucun raisonnement par l'absurde à tenir ici.
Sauf erreur de ma part on a ceci :

Z= x\vee y=\sup \left( x,y \right) = (\sup(x_1,y_1);\sup(x_2,y_2);\sup(x_3,y_3))

z=x\wedge y=\inf \left( x,y \right) = (\inf(x_1,y_1);\inf(x_2,y_2);\inf(x_3,y_3))

où, bien entendu : x_i,y_i \in X et X est muni d'un ordre total. Là est la clé de la distributivité et de la complémentation qui fera que tu n'auras pas besoin d'éplucher tous les triplets.

Ensuite, comme E est distributif et complémenté, le complément d'un élément est unique (Bourbaki E III.72 Exercice 17 Qb)

Posté par
jsvdbre : Relation d'ordre et algèbre de Boole 05-05-17 à 14:03

Bourbaki E III.72 Exercice 16 : Relations d'ordre

Posté par
siefre : Relation d'ordre et algèbre de Boole 05-05-17 à 15:11

bonjour

Pourquoi la clé de la distributivité et de la complémenté ? Est que tu as écrit, c'est juste qu'il s'agit d'un treillis, la définition de la distributivité et de la complémenté, c'est autre chose.

Posté par
jsvdbre : Relation d'ordre et algèbre de Boole 05-05-17 à 16:27

La distributivité de ton ensemble E découlera de celle de X qui est un ensemble totalement ordonné. Alors écris concrètement la démonstration :

x \lor (y \land t) = \cdots = (x \lor t) \land (x \lor t) avec x,y,t \in E

Posté par
siefre : Relation d'ordre et algèbre de Boole 05-05-17 à 22:48

bonsoir

c'est cela est ce que je cherche a démontrer depuis le début , mais j'arrive pas

Posté par
jsvdbre : Relation d'ordre et algèbre de Boole 05-05-17 à 23:01

On va le faire ensemble.
Commence déjà par écrire explicitement la formule en commençant par la gauche :

x \lor (y \land t) = \sup(x,\inf(y,t)) = \cdots à toi

Posté par
siefre : Relation d'ordre et algèbre de Boole 06-05-17 à 00:48

voila est que je sais faire :

$\left( x\vee y \right)\wedge \left( x\vee t \right)=\inf \left( \sup \left( x,y \right),\sup \left( x,t \right) \right)=\inf \left( Z,{Z}' \right)$

$x\vee \left( y\wedge t \right)=\sup \left( x,\inf \left( y,t \right) \right)=\sup \left( x,z \right)$

Posté par
jsvdbre : Relation d'ordre et algèbre de Boole 06-05-17 à 01:19

Okay, je continue :

\begin {aligned}x \lor (y \land t) &= {\blue \sup(x,\inf(y,t))} \text { par définition} \\ &={\blue \sup(x,(\inf(y_1,t_1),\inf(y_2,t_2),\inf(y_3,t_3)))} \text { par définition}\\&={\blue (\sup(x_1,\inf(y_1,t_1)),\sup(x_2,\inf(y_2,t_2)),\sup(x_3,\inf(y_3,t_3)))}\text { par définition}\\ &\text{    comme X est totalement ordonné, il est distributif, donc on distribue dans chaque coordonnée : }\\&=(\inf(\sup(x_1,y_1),\sup(x_1,t_1)),\inf(\sup(x_2,y_2),\sup(x_2,t_2)),\inf(\sup(x_3,y_3),\sup(x_3,t_3)))\\&={\blue(\sup(x_1,y_1),\sup(x_2,y_2),\sup(x_3,y_3))\land(\sup(x_1,t_1),\sup(x_2,t_2),\sup(x_3,t_3))}\text { par définition}\\&={\blue (x\lor y)\land (x \lor t)}\text { par définition} \\& \text {   CQFD   par fierté} \end{aligned}

Quant à la complémentation : le complément de (x,y,z) est (3-x,3-y,3-z). Donc si X avait eu trois éléments, il n'eut pas été complémentable.

Et voilà ton algèbre de Boole en bonne et due forme.

Posté par
siefre : Relation d'ordre et algèbre de Boole 06-05-17 à 12:09

Bonjour

J'ai compris maintenant , le truc que X est distributif c'est ça que je n'ai pas bien avant , mais je pense que c'est bon.
Le complément de (x,y,z) est (3-x,3-y,3-z)
on peut donc dire que si Card(X)=n
le complément de (x,y,z) de E est (n+1-x,n+1-y,n+1-z) ?
Si c'est vrai pourquoi le prof n'a pas signalé cela dans son cours ?

autre chose J'ai un exercice sur les circuits logiques et la table de table de karnaugh , j'ai essayé de résoudre, j'aimerais savoir si c'est possible  de le mettre ici sur le forum ?

je vous remercie .

Posté par
jsvdbre : Relation d'ordre et algèbre de Boole 06-05-17 à 14:01

sief @ 06-05-2017 à 12:09

on peut donc dire que si Card(X)=n
le complément de (x,y,z) de E est (n+1-x,n+1-y,n+1-z) ?

Certainement pas, par exemple avec n = 3, X = {1,2,3}, alors tu vas avoir du mal à trouver un complément à l'élément (2,2,2).

sief @ 06-05-2017 à 12:09

autre chose J'ai un exercice sur les circuits logiques et la table de table de karnaugh , j'ai essayé de résoudre, j'aimerais savoir si c'est possible  de le mettre ici sur le forum ?

Je pense que oui, mais dans un autre sujet

Posté par
siefre : Relation d'ordre et algèbre de Boole 07-05-17 à 12:18

bonjour,
ok merci je vais mettre un nouveau sujet alors


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !