Logique des propositions

Pimond · April 2019

Bonjour,

J'ai eu il y a peu de temps un premier cours sur la logique propositionnelle, et quelque chose reste flou dans mon esprit:
je n'ai pas compris la différence entre une valuation et une interprétation
(je vous joins le cours afin que vous puissiez suivre mon explication).

Ce que je crois avoir compris est qu'une valuation est une fonction qui attribue à chaque variable booléenne une valeur dans {0,1},

et qu'une interprétation est une fonction qui à tout couple (formule, valuation) associe une valeur dans {0,1}.

Sur la diapo 9, on définit ce qu'est une tautologie, une antilogie, ...
Les choses deviennent moins claires avec cette phrase: "une formule est une tautologie ssi pour toute interprétation et toute valuation, I(F,delta) = 1 ", je ne vois pas comment quelque soit l'interprétation on peut avoir la valeur 1.

En réalité l'ensemble de ces notions est un peu trouble, quelqu'un pourrait-il m'éclairer ?

Je vous remercie par avance pour vos réponses,

Pimond

Maxtimax · April 2019

C'est un peu bizarre de dire "pour toute interprétation" puisqu'il n'y a qu'une interprétation : $I(F,\delta)$ ne dépend que de $F,\delta$... Pareil pour "dans l'interprétation $I$", c'est une formulation très bizarre.

Ce qu'il faut comprendre : une valuation $\delta$ est une fonction des variables vers $\{0,1\}$; et (via la définition de $I$ donnée) toute valuation peut s'étendre sur l'ensemble des formules grâce à des règles comme par exemple $\delta (p$ et $q) = \delta(p)$ et $\delta(q)$ (ce que le cours note $I(F,\delta)$) etc.

Une fois qu'on a étendu ça, on peut dire "$\delta$ satisfait $F$, noté $\delta\models F$ si et seulement si $\delta(F)=1$". Une tautologie est alors une formule $F$ telle que $\delta(F)=1$ quel que soit $\delta$.
Maintenant c'est peut-être plus clair comment une tautologie peut exister : la fonction $\delta$ étendue n'est pas n'importe quelle fonction sur l'ensemble des formules, elle vient d'une fonction sur l'ensemble des variables qui a été étendue.
Ainsi, tu peux vérifier facilement que si $v$ est une variable, la formule $v\implies v$ est une tautologie, et la formule $v\land \neg v$ est une "antilogie" (on dit plus contradiction d'habitude) où j'ai noté $\land$ pour "et" et $\neg$ pour "non"

Pimond · April 2019

D'accord, c'est parfaitement clair expliqué comme ça ...

Mais il y aurait donc une erreur dans le cours, puisque si on peut inventer n'importe quelle interprétation qui associe une valeur dans {0,1} à une formule alors le concept de tautologie ou d'antilogie ne peut pas exister non ?

Et un modèle est donc simplement une valuation qui satisfait une formule ?

Merci pour cette première réponse.

Maxtimax · April 2019

Il n'y a pas d'erreur dans le cours (en tout cas à ce niveau), il est juste formulé extrêmement bizarrement : si tu regardes bien la première fois que "interprétation" est mentionnée, on nous dit "l'interprétation est la fonction" et après on nous donne une construction de $I$ qui la détermine uniquement; et après on nous dit "pour toute interprétation", et on fait dépendre des trucs de $I$, alors que $I$ est unique !

On a bien le droit de faire ça (j'ai le droit de dire "Pour tout $x$ tel que $x=1$ je définis $f(x)=30x$" - simplement je n'aurais pas une fonction affine, juste une fonction constante égale à $30$ sur un singleton), mais c'est bizarre.

Encore plus bizarre est la première définition d'interprétation, où on nous dit "l'interprétation d'une formule $F$ est la fonction $I$ qui..." : $I$ dépendrait de $F$ ? N'importe quoi.

Oui pour modèle d'une formule/d'un ensemble de formules.

Au vu de ça, si tu en as la possibilité, je te conseillerais de regarder d'autres cours plutôt que celui-ci (qui introduit les algèbres de Boole sans même les mentionner après :-S )

christophe c · April 2019

Ce que je crois avoir compris est qu'une valuation est une fonction qui attribue à chaque variable booléenne une valeur dans {0,1},

Oui, mais il vaut bien dire: $<<f $ est une valuation$>>$ est une abréviation de $<<f$ estune fonction définie sur l'ensemble des variables à valeurs dans $\{vrai; faux\}>>$ (ou $V:=\{0;1\}$ si l'auteur a fait ce choix)

et qu'une interprétation est une fonction qui à tout couple (formule, valuation) associe une valeur dans {0,1}.

Non, ça c'est un peu du grand nawak. Je te donne une définition précise. $<<$ être prémodèle$>>$ est synonyme de $<<$ être une fonction définie sur l'ensemble des formules à valeurs dans $V>>$

$<<m$ est un modèle$>>$ abrège $<<m$ est un modèle et en plus vérifie $m(A\wedge

= m(A) \times m(B)$ et $m(A\vee

= 1- (1-m(A))(1-m(B))$ et etc $>>$

Il se trouve (c'est un théorème) que la fonction $m\mapsto m_{|Variables}$ qui va $Modeles\to Valuations$ est une bijection et que son inverse $\phi$ est généralement nommé par un nom ou un autre dans ce genre de cours (et apparemment, dans le tien, c'est "interprétation")

Sur la diapo 9, on définit ce qu'est une tautologie, une antilogie, ...
Les choses deviennent moins claires avec cette phrase: "une formule est une tautologie ssi pour toute interprétation et toute valuation, I(F,delta) = 1 ", je ne vois pas comment quelque soit l'interprétation on peut avoir la valeur 1.

$<<A$ est une tautologie$>>$ abrège juste $<<$ pour tout modèle $m: m(A)=1>>$, etc

Dans ton fichier, l'auteur utilise maldroitement une virgule. Si tu as une valauation $f$, et bien $\phi(f)$, qui est un modèle va envoyer une formule $A$ dans $V:=\{0;1\}$ et c'est tout. Donc en parlant proprement, il vaut mieux parler de :

$$ \phi(f)(A)$$

et même de

$$ ( \phi(f)) (A) $$

Par Curryfication (en googlant ce mot, tu t'enrichiras), l'auteur remplace ça par :

$$ I(f,A)$$

Mais c'est bof bof comme approche. (En plus peut-être, je ne pas regardé, et flemme de retélécharger, il inverse et par de $I(A,f)$)