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 :
C'est (sans aucun doute) vrai !
C'est vrai également.
Mais qu'en est-il de :
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é
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 :
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
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 :
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 :
Nous utiliserons 1 à la place de V et 0 à la place de F à partir de maintenant.
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 :
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 :
L'opération OU est presque analogue à l'addition. Nous illustrerons ceci en remplaçant OU par + :
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 :
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 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 :
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 :
Nous continuons de cette manière jusqu'à ce que la table entière soit remplie.
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 2 -- (x + yz)'.
Lorsqu'une expression est difficile à calculer, nous pouvons d'abord calculer les résultats intermédiaires, puis le résultat final.
Exercices.
Produire les tables de vérité pour les opérations suivantes :
Produire les tables de vérité pour :
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
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 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 D 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 :
À 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 :
Nous pouvons factoriser et simplifier l'expression comme suit
C'est un peu plus difficile d'aller plus loin, mais nous le pouvons. Nous utilisons l'identité :
"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érons en algèbre ordinaire :
Nous simplifions par le réarrangement de l'expression comme suit
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 :
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 :
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'.
Maintenant, les deux sorties coïncident et ainsi, nous pouvons les égaliser :
ceci est une des lois de De Morgan. L'autre qui peut être dérivée en utilisant un procédé similaire est :
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"
Exemple 3
Exprimer "x" sous la forme de "somme de produit"
Exemple 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
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
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 :
Il y a quatre situations :
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 :
formula_25 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 formula_29, seulement si à l'implication formula_30. L'opération "si et seulement si" possède la table de vérité suivante :
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) :
Solution
Par conséquent, c'est une contradiction.
Revenons à l'exemple 1, :formula_32. 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.
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, x2 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"
Exemple 1
La proposition :
peut être exprimée symboliquement par :
Exemple 2
La proposition :
peut être exprimée symboliquement par :
Cette proposition est fausse.
Exemple 3
Considérons la proposition concernant (z = x'y' + xy) :
peut être exprimée symboliquement par :
Cette proposition est vraie.
On notera aussi l'utilisation de "formula_50", 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 :
De manière similaire, pour réfuter
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
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. formula_43 avec formula_55) et la "proposition quantifiée" (c.a.d. "x est pair") par sa négation (c.a.d. "x est impair").
Exemple 1
est un énoncé vrai.
Sa négation est
Contraposition.
La proposition "Si "x"2 est impair alors "x" est aussi impair" est plus difficile à démontrer que "Si "x" est pair alors "x"2 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
il est quelquefois plus facile de démontrer à la place
Comment pouvons-nous dire cela ? Nous avons besoin de vérifier que
(à 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 :
Nous simplifions :
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 :
En mettant tout cela dans une formule et en simplifiant :
formula_67
Ensemble de problèmes.
1. Décider si les propositions suivantes sont équivalentes :
2. Exprimer sous la forme la plus simple "somme de produits" la proposition suivante :
3. Traduire les phrases suivantes sous forme symbolique et décider si elles sont vraies :
4. NAND est une opération binaire :
Trouver une proposition qui est constituée seulement d'opérateurs NAND, équivalente à :
5. Faites de même avec les opérateurs NOR. Rappelez-vous que x NOR y = (x + y)'