Dénombrement

[nadia]

Bonjour,
Je n'arrive pas vraiment à répondre à cet exercice, pourriez-vous m'aider s'il vous plait:
Soit E l'ensemble formé par 3 propositions p,q,r ainsi que par les propositions qu'on peut former à l'aide des connecteurs logues : et, ou, non( négation de proposition), ....sachant que E ne peut contenir 2 propositions équivalentes.
Quel est le nombre maximal d'éléments que peut contenir l'ensemble E?
Merci beaucoup.

[mathelot]

Soit le référentiel (l'ensemble qui contient les autres)




transpose les prédicats que l'on peut écrire en diagramme de Venn (patatoïdes)
Les différentes composantes connexes du diagramme te donneront le nombre de prédicats cherché

https://fr.wikipedia.org/wiki/Diagramme_de_Venn

[Ben314]

Salut,
Pour entièrement déterminer une proposition A formée avec les proposition P, Q et R, il suffit de connaître la valeur de vérité (Vrai ou Fausse) de A en fonction des valeurs de vérité de P, Q et R.
En général, on fait un tableau avec 4 colonnes P, Q, R et A et autant de ligne qu'il y a de possibilité pour P,Q et R donc 2^3=8 lignes (PQR = VVV ; VVF ; VFV ; VFF ; FVV ; FVF ; FFV ; FFF) et dans chacune de ces 8 lignes, la dernière case correspondant à A peut être soit V soit F. Ca donne donc 2^8=256 tableaux différents correspondant à 256 propositions A qui sont évidement différentes et il est clair que toute proposition est équivalente une de celle correspondant à un des 256 tableau (vu que le tableau de la proposition en question, ben c'est forcément un des 256 tableau possibles).

Reste à expliquer pourquoi ces 256 tableaux sont effectivement réalisable à l'aide de proposition formées de P, Q , R et des connecteur logiques classiques. Est ce que tu voit pourquoi ?

[nadia]

Salut,
J'ai bien compris les 256 propositions différentes , mais je ne vois pas encore pourquoi elles seraient celles réalisables avec p,q,r et les connecteurs logiques. merci de m'éclairer encore .

[Ben314]

Essaye de trouver toute seule à l'aide d'un exemple.
Par exemple, comment écrire une proposition A qui soit vraie lorsque PQR = VVF ou bien PQR = VFV ou bien PQR = FFF, et qui soit fausse dans les 5 autres cas ?

[nadia]

Oui , je vois comment trouver des propositions en fonction de p,q et r et des connecteurs logiques qui répondent à ce que vous avez donné comme exemple, et donc chaque proposition ainsi construite sera parmi les 256 .
Merci beaucoup pour votre assistance.

[VieuxCrouton]

Une autre manière de raisonner est de rappeler (c'est facile à démontrer) que toute fonction logique peut s'écrire de manière unique sous la forme d'une somme de produits. Toute fonction de 3 variables s'écrit donc de manière unique sous la forme f(p, q, r) =
a_1 . p . q . r + a_2 . p . q . ¬r
+ a_3 . p . ¬q . r + a_4 . p . ¬q . ¬r
+ a_5 . ¬p . q . r + a_6 . ¬p . q . ¬r
+ a_7 . ¬p . ¬q . r + a_8 . ¬p . ¬q . ¬r

Les constantes a_1 à a_8 ayant deux valeurs possibles, il y a 2^8 expressions possibles pour la fonction f.

Note : On peut aussi dire que le nombre binaire à 8 chiffres (a_1 , a_2 , a_3 ... a_8) est compris entre 0 et 255, ce qui donne 256 expressions différentes pour f.