Formalisation et complexité combinatoire - équivalence

• L'égalité est transitive.
• Son utilisation est donc conjonctive.
• \(a = b = c\) se lit \((a = b) \wedge (b = c)\)
• L'équivalence est l'égalité entre valeurs booléennes.
• Nous la notons \(a \equiv b\).
• L'équivalence est associative.
• \(p \equiv q \equiv r\) doit se lire :
  • \((p \equiv q) \equiv r\), mais également
  • \(p \equiv (q \equiv r)\).
• Nous adoptons la convention de lire associativement l'équivalence (i.e., on privilégie l'associativité de l'équivalence sur sa transitivité).
• Les différentes lectures possibles permettent de compresser plusieurs interprétation en une seule inscription.

• \(pair(m + n) \equiv pair(m) \equiv pair(n)\)
• \(pair(m + n) \; \equiv \; (pair(m) \equiv pair(n))\) : la somme est paire ssi les opérandes sont de même parité. Autrement dit, le prédicat "pair" distribue sur l'addition.
• \((pair(m + n) \equiv pair(m)) \; \equiv \; pair(n)\) : ajouter \(n\) à \(m\) ne change pas sa parité ssi \(n\) est pair.

• Soient deux coffrets. L'un est en argent, l'autre est en or. L'un des deux contient le portrait de Portia.
• Sur le coffret en or, nous lisons : (O) "Je ne contiens pas le portrait.".
• Sur le coffret en argent, nous lisons : (A) "L'une seulement de ces deux inscriptions est vraie.".
• Quel est le coffret qui contient le portrait ?

\begin{equation*} \begin{aligned} & true \\ \equiv \quad &\{\text{Déf. } A\} \\ & A \equiv (A \equiv \neg O) \\ \equiv \quad &\{\text{Associativité de } \equiv\} \\ & (A \equiv A) \equiv \neg O \\ \equiv \quad &\{\text{Réflexivité de } \equiv\} \\ & true \equiv \neg O \\ \equiv \quad &\{\text{Unité de } \equiv\} \\ & \neg O \\ \equiv \quad &\{\text{Déf. } O\} \\ & \text{Le portrait est dans le coffret en or.} \end{aligned} \end{equation*}

• Les purs disent toujours la vérité.
• Les pires mentent toujours.
• On notera \(A\) l'assertion : "\(A\) est un pur".
• "A affirme S" \(\equiv\) \(A \equiv S\)

Par exemple :

\begin{equation*} \begin{aligned} & A \text{ dit : "Je suis un pur."} \\ \equiv \quad &\{\text{Par déf.}\} \\ & A \equiv A \\ \equiv \quad &\{\text{Réfl. équiv.}\} \\ & true \end{aligned} \end{equation*}

Autrement dit, nous n'apprenons rien. Un autre exemple :

\begin{equation*} \begin{aligned} & A \text{ dit : "Je suis un pire."} \\ \equiv \quad &\{\text{Par déf.}\} \\ & A \equiv \neg A \\ \equiv \quad &\{\text{Réfl. équiv. et Comm. négation}\} \\ & false \end{aligned} \end{equation*}

Autrement dit, jamais un habitant de l'île ne dira cette phrase. Un autre exemple :

\begin{equation*} \begin{aligned} & A \text{ dit : "Je suis comme B."} \\ \equiv \quad &\{\text{Par déf.}\} \\ & A \equiv (A \equiv B) \\ \equiv \quad &\{\text{Réfl. Assoc. Unité équiv.}\} \\ & B \end{aligned} \end{equation*}

Autrement dit, nous apprenons que B est un pur. Mais nous ne savons rien sur A.