« Approfondissements de lycée/Logique » : différence entre les versions

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
Weft (discussion | contributions)
Ligne 48 : Ligne 48 :
Considérons l'opération ET qui est analogue à la multiplication. Nous voulons considérer :
Considérons l'opération ET qui est analogue à la multiplication. Nous voulons considérer :
:x ET y
: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, dasn la table :
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 :


<table border="1" cellpadding="3">
<table border="1" cellpadding="3">

Version du 28 mai 2005 à 15:14

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 partie 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 :

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 pourquoi nous choisissons 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 à é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 coeur. En algèbre booléenne, l'idée de table de vérité à 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). A 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 :

et

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 impliqu 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

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 :

Comme le Dr 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é :

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

A 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

C'est un peu plus difficile d'aller plus avant, 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.

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éront en algebre 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

Exemple 2
Exprimer x sous la forme de somme de produit

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

Example 4
Exprimer x sous la forme de somme de produit

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

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

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

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

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

alors nous exprimons ceci symboliquement comme

.

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

x 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 :

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)

Solution 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

Par conséquent, c'est une contradiction.

Revenons à l'exemple 1, :. 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.  :

Quantificateurs

Sometimes we need propositions that involve some description of rough quantity, e.g. "For all odd integers x, x2 is also odd". The word all is a description of quantity. The word "some" is also used to describe quantity.

Two special symbols are used to describe the quanties "all" and "some"

means "for all" or "for any"
means "there are some" or "there exists"

Example 1
The proposition:

For all even integers x, x2 is also even.

can be expressed symbolically as:

Example 2
The proposition:

There are some odd integers x, such that x2 is even.

can be expressed symbolically as:

This proposition is false.

Example 3
Consider the proposition concerning (z = x'y' + xy):

For any value of x, there exist a value for y, such that z = 1.

can be expressed symbolically as:

This proposition is true.

Négation

Negation is just a fancy word for the opposite, e.g. The negation of "All named Britney can sing" is "Some named Britney can't sing". What this says is that to disprove that all people named Britney can sing, we only need to find one named Britney who can't sing. To express symbolically:

Let p represent a person named Britney

Similarly, to disprove

we only need to find one odd number that doesn't satisfy the condition. Three is odd, but 3×3 = 9 is also odd, therefore the proposition is FALSE and

is TRUE

In summary, to obtain the negation of a proposition involving a quantifier, you replace the quantifier by its opposite (e.g. with ) and the quantified proposition (e.g. "x is even") by its negation (e.g. "x is odd").

Exemple 1

is a true statement. Its negation is

Contraposition

The proposition "If x2 is odd then x is also odd" is harder to prove than "if x even then x2 is also even", although they mean the same thing. More generally in constructing proofs for propositions of the type

it is sometimes easier to prove instead

How can we say that? We need to verify that

(to be done by the reader).

This type of proving technique is called proof by contrapositive.

Puzzles logiques

Puzzle is an all-encompassing word, it refers to anything trivial that requires solving. Here is a collection of logic puzzles that we can solve using Boolean algebra.


Exemple 1

We have two type of people -- knights or knaves. A knight always tell the truth but the knaves always lie.

Two people, Alex and Barbara, are chatting. Alex says :"We are both knaves"

Who is who?

We can probably work out that Alex is a knave in our heads, but the algebraic approach to determine Alex 's identity is as follows:

Let A be TRUE if Alex is a knight
Let B be TRUE if Barbara is a knight
There are two situations, either:
Alex is a knight and what he says is TRUE, OR
he is NOT a knight and what he says it FALSE.
There we have it, we only need to translate it into symbols:
A(A'B') + A'[(A'B')'] = 1

we simplify:

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

Therefore A is FALSE and B is TRUE. Therefore Alex is a knave and Barbara a knight.

Exemple 2

There are three businessmen, conveniently named Abner, Bill and Charley, who order martinis together every weekend according to the following rules:

  1. If A orders a martini, so does B.
  2. Either B or C always order a martini, but never at the same lunch.
  3. Either A or C always order a martini (or both)
  4. If C orders a martini, so does A.
  1. or
  2. or

Putting all these into one formula and simplifying:

Problem Set

1. Decide whether the following propositions are equivalent:


2. Express in simplest sum-of-product form the following proposition:

3. Translate the following sentences into symbolic form and decide if it's true:

a. For all x, if x2 = 9 then x2 - 6x - 3 = 0
b. We can find a x, such that x2 = 9 and x2 - 6x - 3 = 0 are both true.

4. NAND is a binary operation:

x NAND y = (xy)'

Find a proposition that consists of only NAND operators, equivalent to:

(x + y)w + z

5. Do the same with NOR operators. Recall that x NOR y = (x + y)'