Ré-écriture en formule conjonctive

nha de Lyon

Bonjour,

Dans le cadre d'une extraction de données dans une base (informatique), je souhaiterais transformer une requête en requête conjonctive (donc sans disjonction mais avec des prédicats positifs ou négatifs).

J'ai (bizarrement) une difficulté à le faire pour la formule suivante :
$F = (p \wedge q) \vee r$ où $p$, $q$ et $r$ sont des prédicats (et les parenthèses caractérisent une priorité d'évaluation bien entendu).

Merci pour votre attention et vos idées.

Cordialement, nha de Lyon.

GG

bonjour,
peut-être

¬(¬(p.q).¬r) ?

nha de Lyon

Re-bonjour,

Désolé pour les puristes : certains termes que j'ai utilisés dans mon message initial ne sont pas du tout appropriés !

La formule F ci-dessus comporte 3 variables propositionnelles (et non des prédicats !). Mon intention est d'aboutir à une expression équivalente de F et ne comportant que des variables parmi les 3 sus-mentionnées, avec éventuellement (et sûrement d'ailleurs) leurs négations, mais sans connecteur de disjonction (cette dernière contrainte est primordiale).

J'indique entre autre que je connais (au moins) un algorithme de réécriture en FNC (forme normale conjonctive). Le souci (du moins : mon souci) est que cet algorithme ne garantit pas que les clauses de la FNC résultante soient exemptes de connecteur disjonctif ; c'est en l'occurrence (et à ma connaissance) tout le contraire. Or pour "ma" requête à transformer toute disjonction est bloquante.

Merci pour vos suggestions.
Cordialement, nha de Lyon.

Roman

Bonjour,

La formule de GG convient, non ?

Bruno

Bonjour nha.

Dans le calcul propositionnel, une forme normale conjonctive de $F$ est :$$(p \vee r) \wedge (q \vee r).$$Après, $p \vee r$ a même valeurs de vérité que $\neg(\neg p \wedge \neg r)$ donc, mécaniquement tu obtiens la forme suivante pour $F$ :$$\neg(\neg p \wedge \neg r) \wedge \neg(\neg q \wedge \neg r).$$"Sauf erreur ou omission".

Bruno

nha de Lyon

Re-bonjour,

GG : merci pour votre réponse-solution.
Roman : la formule de GG répond à ma question initiale en effet.
Bruno : merci pour la généralisation et le rappel.

Bien que dans l'absolu la formule donnée par GG satisfasse à ma question initiale, je dois avouer qu'elle me pose un souci de "traduction" en code (informatique). Cette difficulté n'est cependant plus "mathématique" mais informatique car des contraintes de réécriture, que je n'ai pas formalisées ici (elles ne s'y prêtent pas vraiment d'ailleurs), empêchent une implémentation immédiate d'une telle formule, même dénuée de disjonction.

Si éventuellement il y a une autre ré-écriture possible sous forme de conjonction de variables et sans niveau de parenthésage, je serai preneur. Cela n'est peut-être pas envisageable (je demande la lune, non ?).
Merci encore pour votre promptitude. ;-)
Bien cordialement, nha de Lyon.

Bruno

Salut nha.

On peut toujours supprimer les parenthèses par une notation de Lukasiewicz (écriture douteuse) alias notation préfixée ou encore polonaise directe (voir le mode d'emploi des calculettes H.P. d'il y a vingt ans). Bref : pour reprendre la formule cela donne :$$\wedge\,\neg\,\wedge\,\neg p\,\neg r\, \neg\, \wedge\, \neg q\, \neg r \quad :-)$$

Bruno

nha de Lyon

Re-bonjour,

Bruno : merci pour votre formule qui répond une fois de plus (et on n'en doutait pas) à la question posée.

Etrangement le déchiffrement n'a pas été compliqué, à part le triplet : - ) ... Me confirmez-vous par ailleurs que le 1er connecteur conjonctif (en partant de la gauche) précède le 1er symbole de négation ou est-ce l'inverse dans ce cas ?

Si je pouvais me contenter d'un résultat formel comme celui-là pour la suite, croyez bien que je le ferais. Malheureusement, les parenthèses, même si elles ne sont pas représentées en "mode Lukasiewicz", sont bien présentes : elles déterminent le sens (ou la priorité dans le cas de code) d'évaluation de la formule. De plus, une implémentation récursive n'est pas envisageable dans "mon" contexte. Par contre, une formule conjonctive de termes sans connecteur aurait l'"avantage" d'être évaluable en optant pour n'importe quel ordre de parcours des termes.

Je vais me résoudre à trouver une traduction de code convenable (au moins partiellement) à partir d'une des formules logiques équivalentes données ici. Un grand merci à tous.

nha de Lyon.

Bruno

Je suis parti de la formule :$$\neg(\neg p \wedge \neg r) \wedge \neg(\neg q \wedge \neg r).$$Le connecteur dominant est $\wedge$ situé au milieu du texte. C'est donc lui qu'on retrouve en tête de la forme préfixée.

Bruno

deufeufeu

La réecriture suivante, où $\Box$ est binaire et $\diamond $ unaire, fait passer de la notation infixe à la notation infixe
$$[A \Box B] = \Box [A] $$
$$[\diamond A] = \diamond [A]$$
De même en prenant
$$[A \vee B] = \neg \wedge \neg [A] \neg $$
$$[A \wedge B] = \wedge [A] $$
$$[\neg A] = \neg [A]$$
on passe directement de la forme arborescente à la forme infixe sans disjonction voulue.

deufeufeu

il faut substituer aux bons endroits infixe par prefixe dans mes phrases...

nha de Lyon

Bruno : au temps pour moi... j'avais déchiffré (mal) trop vite.
Deufeufeu : merci pour cette translation généralisée (pas de souci pour les substitutions...).

La difficulté se situe à présent dans l'implémentation. Dans notre contexte, on ne peut malheureusement pas se contenter de SQL. On n'a pas toujours le choix des outils...

Bonne fin de semaine.
nha de Lyon.