On peut créer une infinité d’énoncés à l’aide des différents connecteurs logiques. Mais pour un nombre de variables propositionnelles donné, il n’existe qu’un nombre fini de combinaisons des valeurs de vérité de ces variables. Par exemple, avec deux variables \(p,q\text{,}\) on peut former les combinaisons \(V\text{-}V, V\text{-}F,F\text{-}V,F\text{-}F\text{.}\) Pour chacune de ces possibilités, la proposition moléculaire étudiée a deux possibilités, vraie ou fausse. C’est donc dire qu’il n’existe que \(16\) propositions distinctes qui utilisent deux variables propositionnelles.
Il existe donc une forme d’équivalence entre certaines propositions. On cherchera à établir des outils qui permettront d’établir ces équivalences. La table de vérité en est un, mais on verra qu’en pratique, elle n’est pas toujours une bonne option. On continuera aussi à voir un certain parallèle entre la logique mathématique et la théorie des ensembles.
Dans cette section, on définit les notions de tautologie, de contradiction et d’équivalence logique. On établit différentes règles de simplification, dont les lois de De Morgan. Finalement, on définit la forme normale conjonctive.
Parmi toutes les propositions qui existent, peu importe les valeurs assignées aux variables propositionnelles, il y en a une qui est toujours vraie et une qui est toujours fausse. Le cas le plus simple d’une proposition toujours vraie est \(p\vee \neg p\) et la plus simple proposition toujours fausse est \(p\wedge \neg p\text{.}\)
Une proposition qui est toujours vraie peu importe la valeur de vérité des morceaux qui la composent est appelée une tautologie. Une proposition qui est toujours fausse quant à elle est appelée une contradiction.
Soit \(p,q\) deux propositions. On dit que \(p\) est équivalente à \(q\text{,}\) et on écrit \(p\equiv q\text{,}\) si \(p\leftrightarrow q\) est une tautologie.
On utilise la définition pour montrer que la négation d’une disjonction est la conjonction des négations. Cette propriété est l’une des deux lois de De Morgan pour la logique, analogues à celles de la théorie des ensembles.
Dans l’exercice 2.1.5.6, on a montré que la proposition \(\neg(p\vee q)\) était équivalente à \(\neg p \wedge \neg q\text{.}\) On montre que c’est le cas en exhibant la tautologie.
On peut établir l’autre loi de De Morgan, ainsi que d’autres équivalences simples avec les opérateurs logiques. Elles sont données dans la liste ci-dessous. Noter la ressemblance avec les propriétés des opérations sur les ensembles.
En particulier, les lois de De Morgan sont utiles pour déterminer la négation d’expressions complexes, autant en symboles logiques qu’en expressions courantes.
On cherche à écrire la négation des propositions suivantes en s’assurant que le symbole \(\neg\) ne soit que directement collé à une variable et sans double négation.
Pour des propositions complexes, il peut être utile de les décomposer en morceaux avec d’appliquer une règle ou une propriété sur chacun des morceaux et d’ensuite réécrire. Les solutions suivantes illustrent cela.
On pose \(P=(\neg p \vee q)\) et \(Q=p\wedge \neg r\text{.}\) La proposition à nier est équivalente à \(P\wedge Q\text{.}\) Selon la loi de De Morgan pour la conjonction, on a
D’une manière similaire, on pose \(P=\neg (p\wedge q)\) et \(Q=r\vee q\) de sorte \(\neg (p\wedge q)\vee (r\vee q)=P\vee Q\text{.}\) Selon la loi de De Morgan pour la conjonction, on a
Pour cette proposition, on commence par définir des variables. On pose
\begin{gather*}
s=\text{Je vais prendre des sushis au saumon.}\\
t=\text{Je vais prendre des sushis au thon.}\\
p=\text{Je vais prendre un bol poke.}\\
r=\text{Je vais prendre un rouleau de printemps.}
\end{gather*}
Individuellement, on peut traduire la négation des quatre propositions initiales par
\begin{align*}
\neg s&\equiv\text{Je ne prendrai pas de sushis au saumon.}\\
\neg t&\equiv\text{Je ne prendrai pas de sushis au thon.}\\
\neg p&\equiv\text{Je ne prendrai pas de bol poke.}\\
\neg r&\equiv\text{Je ne prendrai pas de rouleau de printemps.}
\end{align*}
Au final, la négation de la proposition serait “Je ne prendrai pas de sushis au saumon ou au thon et je ne prendrai pas de bol poke ou de rouleau de printemps.”; ce à quoi l’auteur répondrait de considérer de changer de restaurant!
On a choisi de considérer le “ou” comme étant inclusif ici, d’une part parce que cela simplifie le problème en fonction de ce qui a été vu et d’autre part, il n’est pas déraisonnable qu’une personne commande à la fois des sushis et un bol poke ou un rouleau de printemps.
À l’exercice 2.1.5.11, on a montré comment on pouvait démontrer l’égalité de deux ensembles à l’aide de l’écriture logique. On regarde un autre exemple ci-dessous.
On cherche le complément de cet ensemble, et donc la négation de la proposition \(x\in A\wedge x\notin B\text{.}\) On a
\begin{align*}
(A-B)^c&=\{x~|~ \neg(x\in A\wedge x\notin B)\}\\
&=\{x~|~ \neg(x\in A)\vee \neg (x\notin B)&& \text{Selon De Morgan} \knowl{./knowl/xref/li-oplogDeMorgan.html}{\text{2.2.5:9}}\\
&=\{x~|~ x\notin A \vee x\in B\} && \text{La négation de la relation d'appartenance est la non appartenance et vice-versa}\\
&= A^c\cup B&&\text{Définition de l'union et du complément}\text{.}
\end{align*}
Jusqu’à maintenant, on a défini la notion de négation ainsi que les connecteurs de disjonction, conjonction et implication. Avec l’implication, on a aussi établi la double implication à l’aide d’une conjonction. On peut réécrire les implications simple et double en n’utilisant que les symboles \(\neg, \vee\) et \(\wedge\text{.}\) On pourra aussi faire la même chose avec le “ou exclusif” (voir l’exercice 2.2.4.6).
On considère la proposition \(p\rightarrow q\text{.}\) On veut la réécrire en n’utilisant que des symboles parmi \(\neg,\vee, \wedge\text{.}\) Pour cela, on s’inspire de sa négation obtenue à l’exercice 2.1.5.7.
Toute proposition logique peut s’écrire en utilisant uniquement les symboles \(\neg, \vee,\wedge\text{.}\) Une proposition ainsi écrite sera dite sous forme normale. On distinguera deux formes particulières.
On exige dans un premier temps que toute négation affecte seulement une variable, quitte à utiliser les lois de De Morgan si nécessaire. Par la suite, la forme normale disjonctive est écrite comme un certain nombre de conjonctions (\(\wedge\)) connectées par des disjonctions (\(\vee\)), alors que la forme normale conjonctive est écrite comme un certain nombre de disjonctions connectées par des conjonctions. Par exemple,
n’en sont pas. La première possède une négation qui affecte plus d’une variable, alors que la seconde contient une parenthèse ayant à la fois une conjonction et une disjonction.
Pour la seconde proposition, il faut distribuer la disjonction dans l’expression \((p\wedge q)\vee r\text{.}\) En utilisant la distributivité, on obtient
Pour obtenir les formes normales, on peut utiliser les différentes propriétés des connecteurs logiques jusqu’à l’obtention de la forme souhaitée, comme à l’exemple 2.2.9, ou utiliser une table de vérité. La table de vérité est particulièrement utile pour trouver la forme normale disjonctive d’une proposition.
En effet, la forme normale disjonctive est un ensemble de sous-propositions connectées par des \(\vee\text{.}\) À partir de la table de vérité d’une proposition, il suffit donc de connecter ensemble les lignes qui rendent la proposition vraie. Ceci est illustré à l’exemple suivant.
Exemple2.2.10.Forme normale disjonctive à partir de la table de vérité.
On reprend la proposition \(((p\wedge q)\vee r)\wedge (q\vee \neg r)\text{,}\) dont une forme normale conjonctive a été trouvée à l’exemple 2.2.9. La table de vérité de cette proposition est donnée ci-dessous.
En regardant la table de vérité, on cible les lignes qui rendent la proposition vraie. Il y a lorsque \(p,q\) et \(\neg r\) sont vraies, de même que lorsque \(\neg p, q\) et \(\neg r\text{.}\) La proposition peut donc s’écrire de manière équivalente comme
Pour obtenir la forme normale conjonctive à partir de la table de vérité, il faut travailler un peu plus fort. On utilise le fait que De Morgan transforme les \(\wedge\) en \(\vee\) et vice-versa par le biais de la négation. En prenant la forme disjonctive de la négation d’une proposition et en la niant à son tour, on obtiendra la forme conjonctive de la proposition originale.
Exemple2.2.12.Forme normale conjonctive à partir de la table de vérité.
On reprend la proposition \(\neg (p\vee q)\vee (r\wedge \neg q)\text{,}\) dont une forme normale disjonctive a été trouvée à l’exemple 2.2.9. La table de vérité de cette proposition est donnée ci-dessous.
On considère la négation de la proposition initiale. Cette négation est vraie aux lignes \(1,2,4,5,6\) de la table de vérité. On peut, à la manière de l’exemple 2.2.10 dire que
En adoptant une convention, une équipe de programmeurs peut tirer avantage d’avoir des expressions sous forme normale. En particulier cela peut faciliter la mise à jour du code, car tout est uniforme.
Déterminer si \(p\rightarrow (q\vee r)\) est équivalent à \((p\rightarrow q)\vee (p\rightarrow r)\text{,}\) à savoir si l’implication se distribue sur la disjonction.
Soit \(p,q,r\) des variables propositionnelles. Donner une proposition moléculaire formée à partir de \(p,q,r\) qui est vraie quand exactement deux variables sont vraies et fausse dans les autres cas.
Transformer l’expression \((\neg p \wedge q) \vee \neg (\neg r \vee q)\) en l’une des formes normales en utilisant les propriétés (pas de table de vérité).
Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.
Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
On montre que cette proposition est une contradiction. En effet, on a montré, à l’exemple 2.2.8, que \(p\rightarrow q \equiv \neg p \vee q \text{.}\) Ainsi,
\begin{align*}
p \wedge \neg(q\rightarrow p) &\equiv p\wedge \neg(\neg q \vee p)\\
&\equiv p \wedge (\neg\neg q \wedge \neg p)&& \text{ par De Morgan.}\\
&\equiv p \wedge q\wedge \neg p &&\text{ par la négation et l'associativité.}\\
&\equiv p \wedge \neg p \wedge q &&\text{ par commutativité.}\\
&\equiv F \wedge q \equiv F &&\text{ par la négation et la domination.}
\end{align*}
On veut montrer que cette proposition est une tautologie à l’aide des propriétés. On a
\begin{align*}
(p\wedge (p\rightarrow q))\rightarrow q &\equiv \neg(p\wedge (\neg p\vee q))\vee q\\
&\equiv \neg((p\wedge\neg p) \vee (p\wedge q) )\vee q &&\text{par distributivité.}\\
&\equiv \neg( F \vee (p\wedge q) )\vee q &&\text{par les propriétés de la négation.}\\
& \equiv \neg( p\wedge q )\vee q &&\text{par la propriété de l'identité.}\\
&\equiv \neg p \vee (\neg q \vee q) &&\text{par De Morgan et associativité.}\\
&\equiv \neg p \vee V &&\text{par les propriétés de la négation.}\\
&\equiv V &&\text{par domination.}
\end{align*}
Ainsi, cette proposition est toujours vraie, et donc est une tautologie.
Déterminer si \(p\rightarrow (q\wedge r)\) est équivalent à \((p\rightarrow q)\wedge (p\rightarrow r)\text{,}\) à savoir si l’implication se distribue sur la conjonction.
Batman a capturé le Sphynx et lui demande d’avouer ses plus récents crimes. Le sphynx étant ce qu’il est, il propose au chevalier noir l’énigme suivante. Il lui dit:
J’ai capturé la fille du commissaire Gordon ou posé la bombe dans la banque de Gotham. De plus si j’ai piraté les archives du palais de justice, alors j’ai donné un pot-de-vin à un procureur. Par contre je n’ai pas donné de pot-de-vin ni incendié l’hôpital.
Connaissant bien le Sphynx, Batman sait que tout ce qu’il vient d’affirmer est faux. Il réussit à déterminer les deux crimes commis par le Sphynx. Que sont-ils?
Sachant que l’énoncé “J’ai capturé la fille du commissaire Gordon ou posé la bombe dans la banque de Gotham.” est fausse, on sait que le Sphynx n’a ni capturé la fille du commissaire Gordon ni posé la bombe dans la banque de Gotham.
Sachant que l’énoncé “Si j’ai piraté les archives du palais de justice, alors j’ai donné un pot-de-vin à un procureur.” est fausse, on sait que le Sphynx a piraté les archives du palais de justice, mais il n’a pas donné un pot-de-vin à un procureur.
Sachant que l’énocné “Je n’ai pas donné de pot-de-vin ni incendié l’hôpital” est fausse. alors soit il a donné un pot-de-vin, soit il a incendié l’hôpital. On sait déjà qu’il n’a pas donné de pot-de-vin, on sait qu’il doit avoir incendié l’hôpital.
\(\neg(\neg s \wedge \neg t)\equiv s \vee t\text{,}\) et donc on sait que soit \(s\) est vraie ou bien \(t\) est vraie. Par la partie précédente, on sait que \(s\) est fausse, et donc \(t\) doit être vraie.
D’autre part, la proposition \(\neg(p \oplus q)\) est vraie uniquement lorsque \(p\) et \(q\) sont vraies, ou \(p\) et \(q\) sont fausses. Ainsi, \(\neg(p \oplus q)\equiv (p \wedge q)\vee(\neg p \wedge \neg q)\text{.}\) En prennant la négation de cette proposition, on obtient:
\begin{align*}
p \oplus q \equiv \neg(\neg(p \oplus q))&\equiv \neg ( (p \wedge q)\vee(\neg p \wedge \neg q) )\\
&\equiv \neg (p \wedge q)\wedge\neg(\neg p \wedge \neg q) \\
&\equiv (\neg p \vee \neg q)\wedge(\neg\neg p \vee \neg\neg q) \\
&\equiv (\neg p \vee \neg q)\wedge(p \vee q)
\end{align*}
Voici la table de vérité abrégée de l’expression \((\neg p \wedge q) \vee \neg (\neg r \vee \neg q)\text{.}\) On laisse au lecteur le soin de vérifier les étapes intermédiaires.
\((\neg p \wedge q) \vee \neg (\neg r \vee \neg q)\)
V
V
V
V
V
V
F
F
V
F
V
F
V
F
F
F
F
V
V
V
F
V
F
V
F
F
V
F
F
F
F
F
Ainsi, une forme normale disjonctive de la proposition est \((\neg p \wedge q) \vee \neg (\neg r \vee \neg q)\) est \((p\wedge q\wedge r)\vee(\neg p\wedge q\wedge r)\vee(\neg p\wedge q\wedge \neg r)\)
Remarque: Il est possible de simplifier cette expression et obtenir \((r\wedge q)\vee(\neg p \wedge q \wedge \neg r)\text{.}\) On laisse en exercice au lecteur le soin d’utiliser les propriétés 2.2.5 pour vérifier cette simplification.
Cette proposition est toujours vraie, et donc on peut écrire \((p\leftrightarrow q)\oplus(\neg p\leftrightarrow q)\equiv V \text{,}\) qui est par défaut une forme normale conjonctive et disjonctive.
On reconnait la table de vérité de l’implication \(p\rightarrow q\text{.}\) On sait qu’elle peut s’écrire \(p\wedge \neg q\text{,}\) mais cela est une forme normale conjonctive. En regardant les lignes rendant la proposition vraie dans la table, on trouve
On a vu qu’on pouvait réduire le nombre d’opérateurs nécessaires pour décrire des propositions à trois, en utilisant la conjonction, la disjonction et la négation. Pour cela, on a pu réécrire les implications simple et double et le ou exclusif avec ces trois opérateurs. Il existe un opérateur particulier qui possède la propriété que tous les autres opérateurs peuvent s’écrire uniquement avec cet opérateur. On l’appelle la barre de Sheffer, définie comme suit:
Démontrer à nouveau les équivalences de l’exercice 2.2.4.14 en utilisant la définition de la barre de Sheffer et les propriétés des opérateurs logiques.
En vertu de la partie précédente, on sait que \(p\uparrow p\equiv \not (p\wedge p)\text{.}\) En simplifiant, ceci devient \(\neg p\vee \neg p\equiv \neg p\text{.}\)
On procède en simplifiant l’expression à l’aide des propriétés des opérateurs logique.
\begin{align*}
(p\uparrow q)\uparrow(p\uparrow q)&\equiv \neg(p\wedge q)\uparrow \neg(p\wedge q) && \text{ selon } \knowl{./knowl/xref/exo-NAND.html}{\text{2.2.4.14.a}}\\
&\equiv \neg (\neg(p\wedge q)\wedge \neg (p \wedge q)) && \text{ toujours selon } \knowl{./knowl/xref/exo-NAND.html}{\text{2.2.4.14.a}}\\
&\equiv (p\wedge q)\vee (p\wedge q) & &\text{ par De Morgan et la négation de la négation} \\
& \equi p\wedge q && \text{par l'idempotence du «ou»}
\end{align*}
Cette fois, on part du côté droit pour arriver à \(p\vee q\text{.}\) Par la partie 2.2.4.14.a, on peut conclure que \(\neg (p\uparrow q)\equiv p\wedge q\text{.}\) On a ainsi
