Approfondissements de lycée/Logique

Approfondissements de lycée

Introduction

La logique est l'étude de la manière dont nous, humains, raisonnons. Dans ce chapitre, nous nous focaliserons sur les méthodes du raisonnement logique, c.a.d. la logique digitale, le calcul de prédicats, l'application au démonstrations et les puzzles logiques amusants.

Algèbre booléenne

Dans le monde noir et blanc des idéaux, il existe la vérité absolue. C'est-à-dire tout est soit vrai ou faux. Avec cet arrière-plan philosophique, nous pouvons considérer les exemples suivants :

"Un plus un égale deux." Vrai ou faux ?

C'est (sans aucun doute) vrai !

"1 + 1 = 2 ET 2 + 2 = 4." Vrai ou faux ?

C'est vrai également.

Mais qu'en est-il de :

"1 + 1 = 3 OU Sydney est en Australie" Vrai ou faux ?

C'est vrai ! Bien que 1 + 1 = 3 ne soit pas vrai, le OU dans l'énoncé fait que si une des parties de l'énoncé est vraie alors l'énoncé entier est vrai.

Maintenant, considérons un exemple un peu plus assemblé

"2 + 2 = 4 OU 1 + 1 = 3 ET 1 - 3 = -1" Vrai ou faux ?

La vérité ou la fausseté des énoncés dépendent de l'ordre dans lequel vous évaluez l'énoncé. Si vous évaluez "2 + 2 = 4 OU 1 + 1 = 3" d'abord, l'énoncé est faux, et autrement vrai. Comme dans l'algèbre ordinaire, il est nécessaire que nous définissions certaines règles pour gouverner l'ordre de l'évaluation, ainsi il n'y aura pas d'ambigüité.

Avant de décider dans quel ordre nous évalons les énoncés, nous allons faire ce que la plupart des mathématiciens aiment faire -- remplacer les phrases par des symboles.
Soit x représente la véracité ou la fausseté de l'énoncé 2 + 2 = 4.
Soit y représente la véracité ou la fausseté de l'énoncé 1 + 1 = 3.
Soit z représente la véracité ou la fausseté de l'énoncé 1 - 3 = -1.

Ainsi, l'exemple ci-dessus peut être réécrit d'une manière plus compacte :

x OU y ET z

Pour aller une étape plus loin, les mathématiciens remplacent aussi OU par + et ET par x, les énoncés deviennent :

$x+y\times z$

Maintenant l'ordre de préférence est clair. Nous évaluons yz (y ET z) d'abord, puis OU avec x. L'énoncé "x + yz" est vrai, ou symboliquement

x + yz = 1

où le nombre 1 représente "vrai".

Il existe une bonne raison de choisir le signe multiplicatif pour l'opération ET. Comme nous le verrons plus tard, nous pouvons faire certains parallèles entre la multiplication et l'opération ET.

L'algèbre booléenne, que nous sommes en train d'étudier a été nommée ainsi en l'honneur du mathématicien britannique George Boole. L'algèbre booléenne traite de deux choses -- le "vrai" ou le "faux" qui sont souvent représentés par les nombres 1 et 0 respectivement. Quelque fois, on peut rencontrer aussi V et F.

L'algèbre booléenne possède les opérations (ET et OU) analogues à l'algèbre ordinaire que nous connaissons et que nous aimons.

Tables de vérité de base

Nous avons tous eu à mémoriser la table de multiplication et maintenant, nous la connaissons par cœur. En algèbre booléenne, l'idée de table de vérité a quelque chose de similaire.

Considérons l'opération ET qui est analogue à la multiplication. Nous voulons considérer :

x ET y

où et x et y représentent chacun un énoncé vrai ou faux (par exemple : il est en train de pleuvoir aujourd'hui). Il est vrai si et seulement si x et y tous les deux sont vrais, dans la table :

La fonction ET
x	y	x ET y
F	F	F
F	V	F
V	F	F
V	V	V

Nous utiliserons 1 à la place de V et 0 à la place de F à partir de maintenant.

La fonction ET
x	y	x ET y
0	0	0
0	1	0
1	0	0
1	1	1

Maintenant, nous devrions être capable de voir pourquoi nous disons que ET est analogue à la multiplication, nous remplacerons le ET par x, ainsi x ET y devient x x y (ou simplement xy). À partir de la table de vérité, nous avons :

0 x 0 = 0

0 x 1 = 0

1 x 0 = 0

1 x 1 = 1

Pour l'opération OU. x OU y est FAUX si et seulement si x et y sont tous les deux faux. Dans la table :

La fonction OU
x	y	x OU y
0	0	0
0	1	1
1	0	1
1	1	1

L'opération OU est presque analogue à l'addition. Nous illustrerons ceci en remplaçant OU par + :

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1 (comme 1 OU 1 est 1)

L'opération NON n'est pas une opération binaire, à la différence de ET et OU. NON x est vrai si x est faux et faux si x est vrai. Dans la table :

La fonction NON
x	NON x
0	1
1	0

En notation symbolique, NON x est noté x' (ou par une barre sur le sommet du x).

Notations alternatives :

$x\times y=x\wedge y$

et

$x+y=x\vee y$

Composition des tables de vérité

Les trois tables de vérité présentées ci-dessus sont les tables de vérité les plus basiques et servent comme blocs pour contruire les tables plus compliquées. Supposons que nous voulions une table de vérité pour xy + z (i.e. x ET y OU z). Notons que cette table implique trois variables (x, y et z), donc nous voulons l'exprimer dans une plus grande que celles précédentes.

Pour construire une table de vérité, d'abord nous écrivons toutes les combinaisons possibles des trois variables :

x	y	z
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Ceci est un motif de manière d'écriture des combinaisons. Nous commençons toujours avec 000 et nous finissons avec 111.

Puis nous completons la table par calcul à la main, pour obtenir la valeur de chaque combinaison donnée par l'expression xy + z. Par exemple :

000

x = 0, y = 0 et z = 0

xy + z = 0

001

x = 0, y = 0 et z = 1

xy + z = 1

Nous continuons de cette manière jusqu'à ce que la table entière soit remplie.

x	y	z	xy OU z
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

La procédure que nous suivons pour produire les tables de vérité est maintenant claire. Voici quelques exemples supplémentaires de tables de vérité.

Exemple 1 -- x + y + z

x	y	z	x + y + z
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Exemple 2 -- (x + yz)'

Lorsqu'une expression est difficile à calculer, nous pouvons d'abord calculer les résultats intermédiaires, puis le résultat final.

x	y	z	x + yz	(x + yz)'
0	0	0	0	1
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	1	0
1	0	1	1	0
1	1	0	1	0
1	1	1	1	0

Exemple 3 -- (x + yz')w

x	y	z	w	(x + yz')w
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	1
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	0
1	1	1	1	1

Exercices

Produire les tables de vérité pour les opérations suivantes :

1. NAND : x NAND y = NON (x ET y)
2. NOR : x NOR OU y = NON (x OU y)
3. XOR : x XOR y est vrai si et SEULEMENT si soit x ou y est vrai.

Produire les tables de vérité pour :

1. xyz
2. x'y'z'
3. xyz + xy'z
4. xz
5. (x + y)'
6. x'y'
7. (xy)'
8. x' + y'

Lois de l'algèbre booléenne

En algèbre ordinaire, deux expressions peuvent être équivalentes l'une avec l'autre, c.a.d. xz + yz = (x + y)z. La même chose peut être dit pour l'algèbre booléenne. Construisons les tables de vérité pour :

xz + yz

(x + y)z

xz + yz

x	y	z	xz + yz
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

(x + y)z

x	y	z	(x + y)z
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

En comparant les deux tables, vous noterez que les sorties (i.e. la dernière colonne) des deux tables sont les mêmes !

Définition

Nous dirons que deux expressions booléennes sont équivalentes si la sortie de leurs tables de vérité sont les mêmes.

Nous faisons la liste de quelques expressions qui sont équivalentes l'une avec l'autre

$x+0=x\,$

$x\times 1=x\,$

$xz+yz=(x+y)z\,$

$x+x'=1\,$

$x\times x'=0\,$

$x\times x=x\,$

$x+yz=(x+y)(x+z)\,$

Prenez quelques moments pour réfléchir pourquoi chacune de ces lois peuvent être vraies.

La dernière loi n'est pas évidente mais nous pouvons démontrer qu'elle est vraie en utilisant les autres lois :

${\begin{matrix}(x+y)(x+z)&=&x(x+z)+y(x+z)\\&=&xx+xz+xy+yz\\&=&x+xz+xy+yz\\&=&x(1+z+y)+yz\\&=&x+yz\end{matrix}}$

Comme le D

Clés dichotomiques : {{{1}}}
Règne : [[clés dichotomiques : {{{2}}}|{{{3}}}]]

Kuo Tzee-Char, lecteur honoraire de mathématiques de l'Université de Sydney, qui aime à dire : "La seule chose à se rappeler en mathématiques est qu'il n'y a rien à se rappeler. Rappelez-vous cela !". Vous ne devez pas essayer de vous encombrer la mémoire avec les lois ainsi établies, parceque certaines d'entre elles sont vraiment évidentes une fois que vous êtes familier avec les opérations ET, OU et NON. Vous devez seulement essayer de vous rappeler de choses plus simples, une fois que vous aurez développé un haut degré de familiarité, vous serez d'accord avec le fait qu'il n'y a vraiment rien à se rappeler.

Simplification

Une fois que nous avons ces lois, nous voulons simplifier les expressions booléennes comme nous le faisons avec l'algèbre ordinaire. Nous pouvons simplifier l'exemple avec facilité :

${\begin{matrix}xyzw'+xyzw&=&xyz(w+w')\\&=&xyz\end{matrix}}$

La même chose peut être dite à propos de :

${\begin{matrix}(x+y)(x'+y')&=&x(x'+y')+y(x'+y')\\&=&xx'+xy'+yx'+yy'\\&=&0+xy'+yx'+0\\&=&xy'+yx'\end{matrix}}$

À partir de ces deux exemples, nous pouvons voir que les expressions qui semblent complexes peuvent être réduites très significativement. Les expressions de la forme somme de produit ont un intérêt particulier, par exemple :

xyz + xyz' + xy'z + x'yz + x'y'z' + x'y'z

Nous pouvons factoriser et simplifier l'expression comme suit

$xyz+xyz'+xy'z+x'yz+x'y'z'+x'y'z$

$=\ xy(z+z')+xy'z+x'yz+x'y'(z'+z)$

$=\ xy+xy'z+x'yz+x'y'$

$=\ x(y+y'z)+x'(yz+y')$

C'est un peu plus difficile d'aller plus loin, mais nous le pouvons. Nous utilisons l'identité :

x + yz = (x + y)(x + z)

Si l'étape suivante n'est pas claire, essayer de construire des tables de vérité comme une aide à la compréhension.

${\begin{matrix}&=&\ x(y+z)+x'(z+y')\\&=&\ xy+xz+x'z+x'y'\\&=&\ xy+(x+x')z+x'y'\\&=&\ xy+z+x'y'\end{matrix}}$

Et ceci est le plus loin que nous pouvons aller en utilisant l'approche algébrique (ou par tout autre approche). L'approche algébrique pour la simplication est liée au principe d'élimination. Considérons en algèbre ordinaire :

x + y - x

Nous simplifions par le réarrangement de l'expression comme suit

(x - x) + y = y

Bien que nous faisons seulement le processus par la pensée, l'idée est claire : nous mettons ensemble les termes qui s'annulent eux-mêmes et ainsi, l'expression est simplifiée.

Théorèmes de De Morgan

Jusque là, nous n'avons seulement traité que les expressions de la forme somme de produits c.a.d. xyz + x'z + y'z'. Les théorèmes de De Morgan nous aident avec un autre type d'expressions booléennes. Nous revisitons les tables de vérité ET et OU :

x	y	x X y	x + y
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

Vous auriez raison de soupçonner que les deux opérations sont connectées d'une façon ou d'une autre en raison des ressemblances entre les deux tables. En fait, si vous inversez l'opération ET, i.e. vous exécutez l'opération NON sur x ET y. Les sorties des deux opérations sont presque les mêmes :

x	y	(x X y)'	x + y
0	0	1	0
0	1	1	1
1	0	1	1
1	1	0	1

La connexion entre ET, OU et NON est révélée par la réciprocité de la sortie x + y en la remplaçant par x' + y'.

x	y	(x X y)'	x' + y'
0	0	1	1
0	1	1	1
1	0	1	1
1	1	0	0

Maintenant, les deux sorties coïncident et ainsi, nous pouvons les égaliser :

(xy)' = x' + y'

ceci est une des lois de De Morgan. L'autre qui peut être dérivée en utilisant un procédé similaire est :

(x + y)' = x'y'

Nous pouvons appliquer ces deux lois pour simplifier les équations:

Exemple 1
Exprimer x sous la forme de somme de produit

${\begin{matrix}x&=&(ab'+c)'\\&=&(ab')'c'\\&=&(a'+b)c'\\&=&a'c'+bc'\end{matrix}}$

Exemple 2
Exprimer x sous la forme de somme de produit

${\begin{matrix}x&=&(a+b+c)'\\&=&(a+b)'c'\\&=&a'b'c'\\\end{matrix}}$Ceci indique une extension possible des lois de De Morgan pour 3 variables ou plus.

Exemple 3
Exprimer x sous la forme de somme de produit

${\begin{matrix}x&=&[(a'+c)\cdot (b+d')]'\\&=&(a'+c)'+(b+d')'\\&=&ac'+b'd\\\end{matrix}}$

Exemple 4
Exprimer x sous la forme de somme de produit

${\begin{matrix}x&=&[(a+bc)\cdot (d+ef)]'\\&=&(a+bc)'+(d+ef)'\\&=&a'(bc)'+d'(ef)'\\&=&a'(b'+c')+d'(e'+f')\\&=&a'b'+a'c'+d'e'+d'f'\\\end{matrix}}$

Une autre chose intéressante que nous avons apprise est que nous pouvons renverser la table de vérité de n'importe quelle expression en remplaçant chacune de ses variables par son opposée, i.e. remplacer x par x' et y' par y etc. Ce résultat ne devrait pas être une surprise, essayez quelques exemples vous-mêmes.

Lois de De Morgan

$(x+y)'=x'y'$

$(xy)'=x'+y'$

Exercice

1. Exprimer sous la forme somme de produit simplifiée :
   1. z = ab'c' + ab'c + abc
   2. z = ab(c + d)
   3. z = (a + b)(c + d + f)
   4. z = a'c(a'bd)' + a'bc'd' + ab'c
   5. z = (a' + b)(a + b + d)d'
2. Montrer que x + yz est équivalent à (x + y)(x + z)

Propositions

Nous nous sommes occupés de propositions depuis le début de ce chapitre, bien que nous n'ayons pas dit que cela en était. Une proposition est simplement un énoncé (ou une phrase) qui est soit VRAIE ou FAUSSE. Nous pouvons utiliser l'algèbre booléenne pour manipuler les propositions.

Il existe deux types spéciaux de propositions -- les tautologies et les contradictions. Une tautologie est une proposition qui est toujours VRAIE, c.a.d. "1 + 1 = 2". Une contradiction est l'opposée d'une tautologie, c'est une proposition qui est toujours FAUSSE, c.a.d. "1 + 1 = 3". Comme d'habitude, nous utilisons 1 pour représenter VRAI et 0 pour représenter FAUX. Notez s'il vous plaît que les opinions ne sont pas des propositions, c.a.d. "George W. Bush a débuté la guerre en Irak pour son pétrole." est simplement une opinion, sa véracité ou sa fausseté n'est pas universelle, voulant dire que certains pensent que c'est vrai, certains non.

Exemples
"Il pleut aujourd'hui" est une proposition.

"Sydney est en Australie" est une proposition

"1 + 2 + 3 + 4 + 5 = 16" est une proposition

"La Terre est une sphère parfaite" est une proposition

"Comment allez-vous ?" n'est pas une proposition - c'est une question.

"Nettoie ta chambre !" n'est pas une proposition - c'est un ordre.

"Les martiens existent" est une proposition

Puisque chaque proposition ne peut seulement prendre que deux valeurs (VRAI ou FAUX), nous pouvons représenter chacune d'elles par une variable et décider si les propositions composées sont vraies en utilisant l'algèbre booléenne, comme ce que nous avons fait. Par exemple "Il fait toujours chaud en Antarctique OU 1 + 1 = 2" sera évaluée comme vraie.

Implications

Les propostitions du type si quelque chose quelque chose alors quelquechose quelque chose sont appelées des implications. La logique des implications est largement applicable en mathématiques, informatique et dans le sens commun général de tous les jours ! Commençons avec un exemple simple

"Si 1 + 1 = 2 Alors 2 - 1 = 1"

est un exemple d'implication, il dit simplement que 2 - 1 = 1 est une conséquence de 1 + 1 = 2. Il y a un lien de cause à effet. Considérons cet exemple :

Marc dit : "Si je deviens millionnaire, Alors je donnerai 500 000 € à la Croix Rouge."

Il y a quatre situations :

1. Marc devient millionnaire et donne 500 000 € à la Croix Rouge
2. Marc devient millionnaire et ne donne pas 500 000 € à la Croix Rouge
3. Marc ne devient pas millionnaire et donne 500 000 € à la Croix Rouge
4. Marc ne devient pas millionnaire et ne donne pas 500 000 € à la Croix Rouge

Dans lequel des quatre cas Marc ne remplit-il pas sa promesse ? Clairement, si et seulement si la seconde situation se produit. Donc, nous disons que la proposition est FAUSSE si et seulement si Marc devient millionnaire et ne donne pas. Si Marc ne devient pas millionnaire alors il ne se dédit pas, puisque le préalable n'est pas réalisé, par conséquent cela doit être évalué comme VRAI.

Si x et y sont deux propositions, x implique y (si x alors y), ou symboliquement

$x\Rightarrow y$

possède la table de vérité suivante :

x	y	$x\Rightarrow y$
0	0	1
0	1	1
1	0	0
1	1	1

$x\Rightarrow y$ est FAUX si et seulement si x est vrai et y faux. Si x est FAUX, il n'y a pas de problème sur la valeur prise par y, la proposition est automatiquement VRAIE. Les deux propostions x et y n'ont pas besoin d'avoir quelque chose à voir l'une avec l'autre, c.a.d. "1 + 1 = 2 implique L'Australie est dans l'hémisphère Sud" est évaluée comme VRAI !

Si

$(x\Rightarrow y)\ {\mbox{ET}}\ (y\Rightarrow x)$

alors nous exprimons ceci symboliquement comme

$x\Leftrightarrow y$.

C'est une implication à deux sens qui traduit x est VRAI si et seulement si y est vrai. Autrement dit, si correspond à l'implication $(x\Rightarrow y)\,$, seulement si à l'implication $(y\Rightarrow x)\,$. L'opération si et seulement si possède la table de vérité suivante :

x	y	$x\Leftrightarrow y$
0	0	1
0	1	0
1	0	0
1	1	1

Les deux nouvelles opérations que nous avons introduites ne sont pas réellement nouvelles, elles sont simplement des combinaisons de ET, OU et NON. Par exemple :

$x\Rightarrow y=x'+y$

Vérifier ceci avec une table de vérité. Comme nous pouvons exprimer l'opération d'implication en termes de ET, OU et NON, nous pouvons dorénavant la manipuler avec l'algèbre booléenne et les loi de De Morgan.

Exemple 1
La proposition suivante est-elle une tautologie ? (une proposition qui est toujours vraie)

$[(x\Rightarrow y)(y\Rightarrow z)]\Rightarrow (x\Rightarrow z)$

Solution 1

$=\ [(x\Rightarrow y)(y\Rightarrow z)]\Rightarrow (x\Rightarrow z)$

$=\ [(x'+y)(y'+z)]'+(x'+z)$

$=\ (x'+y)'+(y'+z)'+x'+z$

$=\ xy'+yz'+x'+z$

$=\ y'+y+x'+z$

$=\ 1$

Par conséquent, c'est une tautologie.

Solution 2
Une solution plus facile est d'établir une table de vérité de la proposition, et noter que la colonne des sorties n'a que des 1. Par conséquent, la proposition est une tautologie, parceque la sortie est 1 indépendamment des entrées (i.e. x, y et z).

Exemple 2
Montrer que la propostion z est une contradiction (une proposition qui est toujours fausse) :

z = xy(x + y)'

Solution

${\begin{matrix}z&=&xy(x+y)'\\&=&xy(x'y')\\&=&0\\\end{matrix}}$

Par conséquent, c'est une contradiction.

Revenons à l'exemple 1, :$[(x\Rightarrow y)(y\Rightarrow z)]\Rightarrow (x\Rightarrow z)$. Ceci n'est pas simplement un assemblage de symboles, vous devriez être capable de traduire ceci en langage de tous les jours et comprendre intuitivement pourquoi cela est vrai.

Exercices

1. Décider si les propositions suivantes sont vraies ou fausses :
   1. Si 1 + 2 = 3, alors 2 + 2 = 5
   2. Si 1 + 1 = 3, alors le poisson ne peut pas nager
2. Monter que la paire de propositions suivante est équivalente
   1. $x\Rightarrow y$ : $y'\Rightarrow x'$

Quantificateurs

Quelques fois, nous avons besoins de propositions qui impliquent une certaine description d'une quantité globale, c.a.d. "Quel que soient les entiers impairs x, x² est aussi impair". La locution quel que soit est une description de quantité. Une autre locution il existe est utilisée.

Deux symboles spéciaux sont utilisés pour décrire les quantités "tous" et "il existe un"

$\forall$ veut dire "Quel que soit", c'est le quantifieur universel.

$\exists$ veut dire "Il existe", c'est le quantifieur existentiel.

Exemple 1
La proposition :

Quels que soient les entiers pairs x, x² est aussi pair.

peut être exprimée symboliquement par :

$(\forall x)(x{\mbox{ est pair}}\Rightarrow x^{2}{\mbox{ est pair}})$

Exemple 2
La proposition :

Il existe des entiers impairs x, tels que x² est pair.

peut être exprimée symboliquement par :

$(\exists x)(x{\mbox{ est impair}}\Rightarrow x^{2}{\mbox{ est pair}})$

ou encore: $\exists x\ /\ x{\mbox{ est impair}}\Rightarrow x^{2}{\mbox{ est pair}}$

Cette proposition est fausse.

Exemple 3
Considérons la proposition concernant (z = x'y' + xy) :

Pour toute valeur de x, il existe une valeur pour y, tel que z = 1.

peut être exprimée symboliquement par :

$(\forall x)(\exists y)(z=1)$

ou encore: $\forall x,\exists y\ /\ z=1$

Cette proposition est vraie.

On notera aussi l'utilisation de "$\exists !$", signifiant: il existe un unique.

Négation

Négation est simplement un mot pour l'opposition, c.a.d. la négation de "Toutes celles qui sont nommées Britney peuvent chanter" est "Il existe une nommée Britney qui ne peut pas chanter". Ceci indique un contre-exemple que toutes les personnes nommées Britney peuvent chanter, nous avons seulement besoin d'en trouver une, nommée Britney, qui ne peut pas chanter. Pour l'exprimer symboliquement :

Soit p représentant une personne nommée Britney

$[(\forall p)(p{\mbox{ peut chanter}})]'=(\exists p)(p{\mbox{ ne peut pas chanter}})$

De manière similaire, pour réfuter

$(\forall x)(x{\mbox{ est impair}}\Rightarrow x^{2}{\mbox{ est pair}})$

nous avons seulement besoin de trouver un nombre impair qui ne satisfait pas à la condition. 3 est impair, mais 3 x 3 = 9 est aussi impair, par conséquent, la proposition est FAUSSE et

$(\exists x)(x{\mbox{ est impair}}\Rightarrow x^{2}{\mbox{ est impair}})$

est VRAIE.

En résumé, pour obtenir la négation d'une proposition impliquant un quantificateur, vous remplacez le quantificateur par son opposé (c.a.d. $\forall$ avec $\exists$) et la proposition quantifiée (c.a.d. "x est pair") par sa négation (c.a.d. "x est impair").

Exemple 1

$(\forall x)(\exists y)(x(x+1)(x+2)(x+3)+1=y^{2})$

est un énoncé vrai. Sa négation est

$(\exists x)(\forall y)(x(x+1)(x+2)(x+3)+1\neq y^{2})$

Contraposition

La proposition "Si x² est impair alors x est aussi impair" est plus difficile à démontrer que "Si x est pair alors x² est aussi pair", alors qu'elles veulent dire la même chose. Plus généralement en construisant des démonstrations pour les propositions du type

$p\Rightarrow q$

il est quelquefois plus facile de démontrer à la place

$q'\Rightarrow p'$

Comment pouvons-nous dire cela ? Nous avons besoin de vérifier que

$p\Rightarrow q\equiv q'\Rightarrow p'$

(à effectuer par le lecteur).

Ce type de technique de démonstration est appelé démonstration par contraposition.

Puzzles logiques

Puzzle est un mot que tout le monde comprend, il fait référence à quelquechose d'évident qu'il est nécessaire de résoudre. Voici une collection de puzzles logiques que nous pouvons résoudre en utilisant l'algèbre booléenne.

Exemple 1

Nous avons deux types de personnes -- les chevaliers et les valets. Un chevalier dit toujours la vérité et un valet ment toujours.

Deux personnes, Alex et Barbara, sont en train de discuter. Alex dit :"Nous sommes tous les deux des valets"

Qui est qui ?

Nous pouvons probablement déduire qu' Alex est un valet, mais l'approche algébrique pour déterminer l'identité d' Alex est la suivante :

Soit A VRAIE si Alex est un chevalier

Soit B VRAIE si Barbara est un chevalier

Il y a deux situations, soit :

Alex est un chevalier et ce qu'il dit est VRAI, OU

il n'est PAS un chevalier et ce qu'il dit est FAUX.

Si nous traduisons cela en symboles :

A(A'B') + A'[(A'B')'] = 1

Nous simplifions :

(AA')B' + A'[A + B] = 1

A'A + A'B = 1

A'B = 1

Par conséquent A est FAUX et B est VRAI. Par conséquent Alex est un valet et Barbara un chevalier.

Exemple 2

Il y a trois hommes d'affaire, nommés Albert, Bernard et Charles, qui commandent des martinis ensemble chaque semaine en suivant les règles suivantes :

1. Si A commande un martini, alors B le fait.
2. Soit B ou C commandent toujours un martini, mais jamais au même repas.
3. Soit A ou C commandent toujours un martini (ou les deux)
4. Si C commande un martini, alors A le fait.

1. $A\Rightarrow B$ ou $AB+A'B'=1\,$
2. $B'C+BC'=1\,$
3. $A+C=1\,$
4. $C\Rightarrow A$ ou $CA+C'A'=1\,$

En mettant tout cela dans une formule et en simplifiant :

${\begin{matrix}1&=&(AB+A'B')(B'C+BC')(A+C)(CA+C'A)\\&=&(AB+A'B')(B'C+BC')(A+C)(C+C')A\\&=&(AB+A'B')(B'C+BC')(A+C)1A\\&=&(AB+A'B')(B'C+BC')(A+C)A\\&&{\mbox{Maintenant que nous savons cela }}A=1{\mbox{ nous pouvons substituer cela dans :}}\\&=&(1B+0B')(B'C+BC')(1+C)1\\&=&(B)(B'C+BC')\\&&{\mbox{Maintenant que nous savons cela }}B=1{\mbox{ nous pouvons substituer cela dans :}}\\&=&(1)(0C+1C')\\&=&C'\\&&{\mbox{Si }}1=C'{\mbox{ alors }}C=0\\&&ABC'=1\end{matrix}}$

Ensemble de problèmes

1. Décider si les propositions suivantes sont équivalentes :

$x'\Rightarrow y'$

$y\Rightarrow x$

2. Exprimer sous la forme la plus simple "somme de produits" la proposition suivante :

$(x\Leftrightarrow y)\Rightarrow z$

3. Traduire les phrases suivantes sous forme symbolique et décider si elles sont vraies :

a. Pour tous les x, si x² = 9 alors x² - 6x - 3 = 0

b. Nous pouvons trouver un x, tel que x² = 9 et x² - 6x - 3 = 0 sont toutes les deux vraies.

4. NAND est une opération binaire :

x NAND y = (xy)'

Trouver une proposition qui est constituée seulement d'opérateurs NAND, équivalente à :

(x + y)w + z

5. Faites de même avec les opérateurs NOR. Rappelez-vous que x NOR y = (x + y)'