Discussion :

[UiYuki]

Bonjour à tous,

Après un long mois d'études de TD sur la logique élémentaire (Boole, Karnaugh, de Morgan, Beth, etc...), nous entamons enfin les ensembles en maths.

Seulement, je me pose une question vis à vis d'un devoir :

La consigne est la suivante : "Simplifiez chacune des expressions suivantes sachant que E est un ensemble et A, B et C trois sous ensembles de E".

La forme qu'on nous propose est la suivante : http://www.imagup.com/imgs/1224096578.html

Or, je trouve qu'elle ressemble beaucoup aux précédentes formes logiques, c'est à dire : http://www.imagup.com/imgs/1224096614.html ou http://www.imagup.com/imgs/1224096631.html ...

Y aurait-il en effet un rapport ?
Si oui, comment pourrais-je simplifier cette forme? En utilisant les mêmes techniques qu'en logique ?

Merci d'avance !

[pseudocode]

Tu parles des lois fondatamentales des ensembles algebriques ?

http://en.wikipedia.org/wiki/Algebra...of_set_algebra

[Alp]

Peut-être ceci pourrait t'aider : http://gilles-dubois.developpez.com/Bases/Ensembles/

[Garulfo]

[...]
Y aurait-il en effet un rapport ?
Si oui, comment pourrais-je simplifier cette forme? En utilisant les mêmes techniques qu'en logique ?

Oui il y a un rapport.

Toutes ces syntaxes (ces langages comme on dirait en logique) sont isomorphiques et pour toutes les lois (théorème) de l'une il y a une loi équivalente dans une autre.

[pseudocode]

Oui il y a un rapport.

Toutes ces syntaxes (ces langages comme on dirait en logique) sont isomorphiques et pour toutes les lois (théorème) de l'une il y a une loi équivalente dans une autre.

heu... non, pas tout a fait. Comme le dit wikipedia:

Notice that the analogy between unions and intersections of sets, and addition and multiplication of numbers, is quite striking. Like addition and multiplication, the operations of union and intersection are commutative and associative, and intersection distributes over unions. However, unlike addition and multiplication, union also distributes over intersection.

[UiYuki]

Merci de vos réponses

[Garulfo]

heu... non, pas tout a fait. Comme le dit wikipedia:

Je me sens plus compétent que Wikipédia Je suis un peu logicien quand même. C'est simplement qu'il manque une information. La discussion du wiki sur la somme et la multiplication prenait probablement le corps R comme référence avec les opérations usuelles. Sauf que pour un isomorphisme en logique tu n'utilises pas R. Si tu travailles sur l'algèbre de boole ({0,1},+,.), tu as un isomorphisme avec ({F,V},ou,et).
Alors (x.y)+z ≅ (x et y) ou z ⇔ (x ou z) et (y ou z) ≅ (x+z).(y+z)
On a la distributivité de l'addition sur la multiplication.
Dans une algèbre de Boole, 1+1 = 1.

N'est-ce pas ce qu'ils ont vu en classe ? Je me trompe peut-être mais je suppose qu'on leur a fait utiliser ça.

Donc je réitère, il existe un isomorphisme canonique entre chacun de ces langages.

[pseudocode]

Sauf que pour un isomorphisme en logique tu n'utilises pas R. Si tu travailles sur l'algèbre de boole ({0,1},+,.), tu as un isomorphisme avec ({F,V},ou,et).
Alors (x.y)+z ≅ (x et y) ou z ⇔ (x ou z) et (y ou z) ≅ (x+z).(y+z)
On a la distributivité de l'addition sur la multiplication.
Dans une algèbre de Boole, 1+1 = 1.

Ah... si tu rédifinis l'addtion et la multiplication de cette façon, alors Ok.


PS: j'ai quand même du mal à me représenter un anneau dans lequel "1+1=1". Ça voudrait dire que "1" n'a pas d'opposé. Mais bon, je vois ce que tu veux dire et j'arrête mon chipotage de peur de repartir dans un débat a rallonge.

[Garulfo]

Ah... si tu rédifinis l'addtion et la multiplication de cette façon, alors Ok.

PS: j'ai quand même du mal à me représenter un anneau dans lequel "1+1=1". Ça voudrait dire que "1" n'a pas d'opposé. Mais bon, je vois ce que tu veux dire et j'arrête mon chipotage de peur de repartir dans un débat a rallonge.

Si tu n'as plus 1+1=1, tu n'as plus une algèbre de Boole
Une algèbre de Boole est en fait un treillis borné, distributif et doté d'un complémentaire. C'est le principe d'idempotence qui impose 1+1=1. Je n'ai jamais su pourquoi il avait appelé ça une algèbre, puisque comme tu l'a fait remarqué, il n'y a pas d'opposé à 1.

[pseudocode]

Je n'ai jamais su pourquoi il avait appelé ça une algèbre, puisque comme tu l'a fait remarqué, il n'y a pas d'opposé à 1.

Boole ({0,1},+,*) c'est une algèbre, mais ce n'est pas un anneau (du moins avec la définition usuelle de l'addition).

C'est pour cela que je trouve qu'il est dur de faire un parallèle entre les ensembles et les entiers. On a tendance a supposer un isomorphisme entre les anneaux alors qu'il y a juste un isomorphisme entre les structures algébriques.

PS: mince, j'avais promis de ne pas continuer.

[Zavonen]

c'est une algèbre, mais ce n'est pas un anneau

Plus précisément ce n'est pas un anneau unitaire. La définition exige que l'élément neutre de la multiplication soit différent de celui de l'addition.

[pseudocode]

Plus précisément ce n'est pas un anneau unitaire. La définition exige que l'élément neutre de la multiplication soit différent de celui de l'addition.

Heu... moi je dirais ce n'est pas un anneau "tout court" car l'élément "1" n'a pas d'opposé avec la loi "+". Non ?

[Zavonen]

Heu... moi je dirais ce n'est pas un anneau "tout court" car l'élément "1" n'a pas d'opposé avec la loi "+". Non ?

D'accord.

[Garulfo]

Après discussion avec un de mes collègues, c'est uniquement parce qu'on peut parler d'algèbre généralisée (surtout en informatique théorique) comme une structure composée d'un ensemble et de deux opérations internes. Le reste est en plus.

C'est dans ce sens où Boole a utilisé le terme algèbre.

@pseudocode tu remarqueras que je n'ai pas parlé d'anneau dans mon message d'origine ou celui qui suit. A fortiori donc, je n'ai pas parlé d'isomorphisme d'anneau. Donc on a un isomorphisme de structure algébrique. CE qui sous-entend que les ensembles, l'intersection et l'union ne forme pas un anneau non plus. Il n'y a pas d'opposé dans l'union je te ferais remarqué. Ta phrase « On a tendance a supposer un isomorphisme entre les anneaux alors qu'il y a juste un isomorphisme entre les structures algébriques. » n'a pas vraiment de sens donc. Car un isomorphisme entre les structures algébriques dont l'un est un anneau est un isomorphisme entre anneaux, puisque l'anneau est une structure algébrique.

En tout cas, là j'admet qu'on commence à sortir du sujet, mais le reste ne me paraît pas HS ^_^

[pseudocode]

On est entierement d'accord : il y a un isomorphisme de structure algébrique et sans doute entre les anneaux engendrés.

Ma remarque était juste que utiliser les symboles "+" et "." en definissant "1+1=1" crée une confusion avec les operations d'addition et multilication des nombres (réels). Auquel cas on n'est plus dans l'anneau de réels et les règles de calculs usuels ne s'appliquent plus. En particulier, je ne vois pas le morphisme entre ({0,1},+,.) et (Z/2Z,+,*).

[Garulfo]

On est entierement d'accord : il y a un isomorphisme de structure algébrique et sans doute entre les anneaux engendrés.
[...]
En particulier, je ne vois pas le morphisme entre ({0,1},+,.) et (Z/2Z,+,*).

Si ton ({0,1},+,.) est une algèbre de Boole, alors il n'y a pas de morphisme, car comme tu l'as dit ce n'est pas un anneau.

Ce qui compte, il me semble, c'est que le + est utilisé dans le contexte de la logique, et dans les cours suivis par UiYuki, comme on utilise le « ou » logique ou le « union ». Il y a donc isomorphisme entre les structures dont UiYuki parlait. Par conséquent, il y a une « équivalence » entre les théorèmes.

[pseudocode]

Si ton ({0,1},+,.) est une algèbre de Boole, alors il n'y a pas de morphisme, car comme tu l'as dit ce n'est pas un anneau.

Tout a fait. L'anneau engendré par l'algebre de Boole serait plutot ({0,1},XOR,AND) qui lui est serait "equivalent" a (Z/2Z,+,*).

Ce qui compte, il me semble, c'est que le + est utilisé dans le contexte de la logique, et dans les cours suivis par UiYuki, comme on utilise le « ou » logique ou le « union ».

completement d'accord.

[MatheuxNoviceEnProg]

Dans une algèbre de Boole, 1+1 = 1.

on a jamais 1+1=1 dans un anneau non nul
car ça entraîne 1=0 et puis a=a.1=a.(0)=a(1-1)=a-a=0 pour tout a, et donc l'anneau n'a qu'un élément ("anneau nul"), ce qui limite les calculs^^

Heu... moi je dirais ce n'est pas un anneau "tout court" car l'élément "1" n'a pas d'opposé avec la loi "+". Non ?

Si il est son propre opposé ! on a 1+1=0 (et pas 1^^)

Après discussion avec un de mes collègues, c'est uniquement parce qu'on peut parler d'algèbre généralisée (surtout en informatique théorique) comme une structure composée d'un ensemble et de deux opérations internes. Le reste est en plus.

C'est dans ce sens où Boole a utilisé le terme algèbre.

@pseudocode tu remarqueras que je n'ai pas parlé d'anneau dans mon message d'origine ou celui qui suit. A fortiori donc, je n'ai pas parlé d'isomorphisme d'anneau. Donc on a un isomorphisme de structure algébrique. CE qui sous-entend que les ensembles, l'intersection et l'union ne forme pas un anneau non plus. Il n'y a pas d'opposé dans l'union je te ferais remarqué.

une algèbre de Boole est une algèbre et donc un anneau.
Dans le cas du calcul propositionnel le "et" est la multiplication , distributive par rapport au "ou exclusif" (i.e. le "ou bien") , le 1 est la tautologie et le 0, ce qui est toujours faux ("et" est aussi distributive par rapport au "ou inclusif", mais là on a effectivement pas un anneau, mais on gagne par contre la distributivité réciproque!)
dans le cas de l'ensemble des parties d'un ensemble donné la multiplication est l'intersection et l'addition est la différence symétrique (le complémentaire de l'intersection dans la réunion) le 1 est l'ensemble de base et le zero est l'ensemble vide.

Les additions vérifient a+a=0 pour tout a ( a "ou bien" a est toujours faux!) et chaque élément est son propre opposé...

Ta phrase « On a tendance a supposer un isomorphisme entre les anneaux alors qu'il y a juste un isomorphisme entre les structures algébriques. » n'a pas vraiment de sens donc. Car un isomorphisme entre les structures algébriques dont l'un est un anneau est un isomorphisme entre anneaux, puisque l'anneau est une structure algébrique.

ça ressemble a un sophisme^^, et c'est faux, on peut avoir deux structures algébriques isomorphes en tant que groupe (par exemple) mais pas et tant qu'anneau!
Z l'ensemble des entiers et 2Z, l'ensemble des entiers pairs, sont deux groupes isomorphes, mais l'un est un anneau et l'autre pas!