Question sur de la logique propositionnelle

[risocs]

Bonjour, j'aimerais votre aide quand a une question en logique propositionnelle.
Existe t-il une formule mathematique permettant de transformer un ou exclusif de n terme (P1 ou_exclusif P2 ou_exclusif ... PN) sous une forme normal conjonctive.
Merci pour votre aide.

PS : en esperant que la formule soit simple et que la transformation necessite un algorithme asymtotiquement polynomial sur N et non pas exponentiel.
-----

[Médiat]

Bonjour,

Sauf erreur de ma part, une disjonction exclusive de N termes nécessite 2^N termes en FNC.

[Médiat]

Correction : 2^(N-1)

[risocs]

Je m'en doutais merci pour votre reponse

[A voir en vidéo sur Futura]

[choom]

Bonjour,

Sauf erreur de ma part, une disjonction exclusive de N termes nécessite 2^N termes en FNC.

Bonjour.
J’ignore le cadre formel derrière l’acronyme FNC. La notation indicée suivante n’y est sans doute pas admise pour exprimer le sens demandé ?
«*Il existe un et un seul i parmi 1,...,n tel que Pi*»
Bien cordialement.

[Médiat]

Bonjour,

Effectivement une telle écriture n'a pas de sens formel, de plus ce que vous proposez serait faux (essayez avec 3 propositions).

FNC = Forme Normale Conjonctive

[choom]

Bonjour,

Effectivement une telle écriture n'a pas de sens formel, de plus ce que vous proposez serait faux (essayez avec 3 propositions).

FNC = Forme Normale Conjonctive

Bonjour Mediat. Pour le manque de sens formel je vous suis. Mais je ne comprends pas la fausseté de ma proposition, avec 3 ou plus de propositions, à moins que mes souvenirs en Logique me trahissent.
Question : le OU EXCLUSIF répété sans parenthèse entre P1, ..., Pn
ne revient-il pas au même sens que "soit P1, soit P2, ..., soit Pn" ?

A vous lire..
Choom.

[Médiat]

Bonjour,

Comme je le disais dans le message que vous citez : essayez avec 3 propositions.

Par "essayez" je voulais dire "faites la table de vérité" (ou toute autre technique) en le faisant tout deviendra clair.

[choom]

Bonjour,

Comme je le disais dans le message que vous citez : essayez avec 3 propositions.

Par "essayez" je voulais dire "faites la table de vérité" (ou toute autre technique) en le faisant tout deviendra clair.

Re-bonjour.



J’ai mis la colonne 4 pour vérifier que j’interprète bien le OU exclusif.
Où serait la fausseté = la différence entre la colonne 5 et la colonne 6 ?

[erik]

J'ai peur de dire une bétise, mais je me lance quand même :

Dernière ligne :
P1 XOR P2 : 0
P3 :1

(P1 XOR P2) XOR P3 : 1

Comme disais l'autre : étonnant non ?

[Médiat]

Bonjour,

erik a raison.

Vous avez fait votre calcul de la colonne 5 sans parenthèses (contrairement à erik) vous l'avez donc, sans doute calculée avec votre définition en tête et non la table de vérité, du coup, pas étonnant que vous trouviez ce que vous attendiez

Merci à erik pour son allusion à Pierre

[choom]

Bonjour,

erik a raison.

Vous avez fait votre calcul de la colonne 5 sans parenthèses (contrairement à erik) vous l'avez donc, sans doute calculée avec votre définition en tête et non la table de vérité, du coup, pas étonnant que vous trouviez ce que vous attendiez

Merci à erik pour son allusion à Pierre

Merci à Erik.

@Mediat,
dans mon message 7 j’écris clairement que j’avais compris «*sans parenthèses*».

Si vous l’aviez lu plutôt que de suggérer de manière condescendante et publique dans votre message 8 que je n’avais pas lu le votre ni appliqué vos conseils avisé avant de répondre.....

Bon, le débat annexe quant à ma question est clos pour moi. Je sors.
Choom

[choom]

Je reviens quant même. Car une fois encore je trouve votre attitude pédante fort de café !
Mediat, où avez-vous vu des parenthèses dans le message du primoposteur ?

[Médiat]

Si vous l’aviez lu plutôt que de suggérer de manière condescendante et publique dans votre message 8 que je n’avais pas lu le votre ni appliqué vos conseils avisé avant de répondre.....

Merci de me donner publiquement raison.

[ansset]

J'ai peur de dire une bétise, mais je me lance quand même :

Dernière ligne :
P1 XOR P2 : 0
P3 :1

(P1 XOR P2) XOR P3 : 1

Comme disais l'autre : étonnant non ?

je viens de voir ce fil et j'allais faire la même remarque.
en appliquant les parenthèses on obtient simplement une réponse "vrai" ssi la somme des "vrais" est impaire.

[choom]

En fait, la réponse qui m’eut évité de me fourvoyer est tout simplement le rappel 43 ans après mes cours, que l’opérateur logique OU EXCLUSIF n’existe QUE sous la forme à 2 opérandes,
et que donc, sans parenthèses, il s’applique successivement comme AVEC les parenthèses telles que l’a interprété Erik,
Le résultat étant une table de vérité évidemment différente.
Ce qui amène au constat démontrable qu’il est associatif et que dès lors les parenthèses n’ont plus d’importance. Cfr wiki..
Encore merci à Erik.
Choom

[Médiat]

l’opérateur logique OU EXCLUSIF n’existe QUE sous la forme à 2 opérandes,

Pouvez-vous nous rappeler quels sont les opérateurs logiques qui existent sous plusieurs formes quant au nombre d'opérandes ...