Logique booléenne

[invited193331a]

J'ai un petit problème à vous soumettre :

Soit n variables booléennes V_1, V_2 ... V_n. Et soit V = f(V_1, V_2 ... V_n) une variable donné par une combinaison booléenne de de ces n variables.

Par exemple : V = V_1 . V_2 + V_1 . notV_3 + V_3 . V_4.

Le "." représente l'opérateur ET et le "+" représente l'opérateur OU.

Voici ce que je pense (mais je n'en sus pas sûr et je ne sais pas le justifier) :

----- Si n > 1 , quelle que soit l'expression booléenne f , il est impossible de trouver une expression g telle que V_1 = f(V, V_2 ... V_n) -----

Une idée ?

Pierre
-----

[azizovsky]

J'ai un petit problème à vous soumettre :

Soit n variables booléennes V_1, V_2 ... V_n. Et soit V = f(V_1, V_2 ... V_n) une variable donné par une combinaison booléenne de de ces n variables.

Par exemple : V = V_1 . V_2 + V_1 . notV_3 + V_3 . V_4.

Le "." représente l'opérateur ET et le "+" représente l'opérateur OU.

Voici ce que je pense (mais je n'en sus pas sûr et je ne sais pas le justifier) :

----- Si n > 1 , quelle que soit l'expression booléenne f , il est impossible de trouver une expression g telle que V_1 = f(V, V_2 ... V_n) -----

Une idée ?

Pierre

Salut, quel est l'interêt de ce circuit, n etrées, mais une seul sortie, c'est mieux de déconnecter les autres. .

[pierre_18]

Salut, quel est l'interêt de ce circuit, n etrées, mais une seul sortie, c'est mieux de déconnecter les autres. .

Il me semble qu'en électronique on rencontre souvent des montages avec plusieurs entrées et une seule sortie ? On peut en tous cas en imaginer. Mais de toutes façons mon application ne concerne pas les montages électroniques, si cela t'intéresse tu trouveras mon application ici.
En algèbre ordinaire (sur Q) si tu as une équation du style V = V_1 . V_2 - V_1 . V_3 + V_3 . V_4 tu arrives assez facilement à tirer V_1 en fonction de V , V_2 et V_3.

En algèbre de Boole par contre cela paraît impossible. Si tu as par exemple V = V_1 & V_2 tu ne peux pas extraire V_1 en fonction de V et V_2. Et cela semble vrai quelle que soit l'expression et quelle que soit le nombre de variables.

[pierre_18]

----- Si n > 1 , quelle que soit l'expression booléenne f , il est impossible de trouver une expression g telle que V_1 = f(V, V_2 ... V_n) -----

Je me suis trompé dans cet énoncé il faut lire : une expression g telle que V_1 = g(V, V_2 ... V_n)

[A voir en vidéo sur Futura]

[azizovsky]

Je me suis trompé dans cet énoncé il faut lire : une expression g telle que V_1 = g(V, V_2 ... V_n)

fait une table de vérité dans laquelle est une condition et un résultat, par exemple : condition condition, et résultat

ça fait un bail avec ce domaine, je n'est jamais vu ça, encodeur, décodeur, éguillage,....

[Médiat]

Bonjour,

Votre proposition est fausse :

qui n'est pas réductible (sinon c'est trop facile)
alors

[pierre_18]

Bonjour,

Votre proposition est fausse :

qui n'est pas réductible (sinon c'est trop facile)
alors

Merci beaucoup Médiat c'est super. Cela répond tout à fait à ma question. Je n'avais pas trouvé de contre exemple.
On ne peut donc pas tirer de conclusion générale quant à l'existence ou non de la fonction g ?

Pierre

[pierre_18]

Merci beaucoup Médiat c'est super. Cela répond tout à fait à ma question. Je n'avais pas trouvé de contre exemple.
On ne peut donc pas tirer de conclusion générale quant à l'existence ou non de la fonction g ?

J'ai inclus ton exemple dans mon site car c'est un point qui manquait.

Merci encore.
Pierre

[NicoEnac]

Bonjour,

Intéressante question !

En essayant votre exemple, j'ai bêtement construit la table de vérité V en fonction de V1, V2, V3 et V4 puis simplement "échangé" les colonnes V et V1 comme si V était une entrée et V1 la sortie.

Et là, on s'aperçoit qu'il manque certaines combinaisons des entrées V, V2, V3 et V4 et certaines autres sont en double.
Par exemple, la combinaison V=0, V2=0, V3=1 et V4=1 n'apparait pas tandis que V=1, V2=0, V3=1 et V4=1 apparait 2 fois.
Pire ! Pour la seconde, V1 peut valoir 0 ou 1.

La raison ? V vaut toujours 1 lorsque V3=1 et V4=1, entrainant le fait que dans ce cas, on ne peut pas deviner la valeur de V1 à partir de V.

Voilà comment je comprends intuitivement votre problème : pour un j tel que 1<= j <= n, s'il existe une combinaison des Vk, k=1 à n, k différent de j tel que la valeur de V soit indépendant de la valeur de Vj, alors il n'existe pas de fonction g telle que Vj = g(V, {Vk}), k différent de j.

EDIT : il me semble ainsi que si on écrit V comme "somme" (au sens où vous définissez l'addition) de termes, Vj ou Not(Vj) doit intervenir dans chacun des termes de la somme pour que g existe.