Règles deMorgan expliquées

Nous avons deux valeurs: T et F.

On peut combiner ces valeurs de trois façons: NOTANDet OR.

NOT est le plus simple:

• NOT T = F
• NOT F = T

On peut écrire cela comme un table de vérité:

when given.. | results in...
============================
           T | F
           F | T

Pour la concision

x | NOT x
=========
T | F
F | T

Pense NOT comme le compléterqui est, elle se tourne une valeur dans l'autre.

AND fonctionne sur deux valeurs:

x y | x AND y
=============
T T | T
T F | F
F T | F
F F | F

AND est T seulement lorsque son arguments (les valeurs de x et y dans la table de vérité) sont T — et F autrement.

OR est T lorsqu'au moins l'un de ses arguments est T:

x y | x OR y
=============
T T | T
T F | T
F T | T
F F | F

Nous pouvons définir des combinaisons plus complexes. Par exemple, nous pouvons écrire une table de vérité pour x AND (y OR z)et la première ligne est ci-dessous.

x y z | x AND (y OR z)
======================
T T T | ?

Une fois que nous savons comment évaluer x AND (y OR z)nous pouvons remplir le reste de la table.

À évaluer la combinaison, d'évaluer les morceaux et travailler à partir de là. Les parenthèses montrent quelles sont les parties à évaluer en premier. Ce que vous connaissez de l'arithmétique ordinaire va vous aider à travailler. Disons que vous avez 10 - (3 + 5). Tout d'abord vous évaluer la partie entre parenthèses pour obtenir

10 - 8

et d'évaluer qui, comme d'habitude pour obtenir la réponse, 2.

De l'évaluation de ces expressions fonctionne de la même façon. Nous savons comment OR fonctionne à partir de ci-dessus, de sorte que nous pouvons élargir notre table un peu:

x y z | y OR z | x AND (y OR z)
===============================
T T T | T      | ?

Maintenant c'est presque comme nous sommes de retour à la x AND y table. Nous avons simplement remplacer la valeur de y OR z et d'évaluer. Dans la première ligne, nous avons

T AND (T OR T)

qui est le même que

T AND T

qui est tout simplement T.

Nous répétez le même processus pour tous les 8 valeurs possibles de xyet z (2 valeurs possibles de x fois 2 valeurs possibles de y fois 2 valeurs possibles de z) pour obtenir

x y z | y OR z | x AND (y OR z)
===============================
T T T | T      | T
T T F | T      | T
T F T | T      | T
T F F | F      | F
F T T | T      | F
F T F | T      | F
F F T | T      | F
F F F | F      | F

Certaines expressions peuvent être plus complexes qu'elles ne devraient l'être. Par exemple,

x | NOT (NOT x)
===============
T | T
F | F

En d'autres termes, NOT (NOT x) est équivalent juste x.

DeMorgan règles sont à portée de main des astuces qui nous permettent de convertir des entre des expressions équivalentes qui correspondent à certains modèles:

• NOT (x AND y) = (NOT x) OR (NOT y)
• NOT (x OR y) = (NOT x) AND (NOT y)

(Vous pourriez penser de ce que la façon dont NOT distribue par le biais de simples AND et OR expressions.)

Votre bon sens probablement déjà comprend ces règles! Par exemple, pensez à les bits de la sagesse populaire que "vous ne pouvez pas être à deux endroits à la fois." Nous pourrions le faire rentrer dans la première partie de la première règle:

NOT (here AND there)

L'application de la règle, c'est une autre façon de dire "vous n'êtes pas ici, ou si vous n'êtes pas là."

Exercice: Comment pourriez-vous vous exprimer la deuxième règle de la plaine de l'anglais?

Pour la première règle, regardons la table de vérité de l'expression sur le côté gauche du signe égal.

x y | x AND y | NOT (x AND y)
=============================
T T | T       | F
T F | F       | T
F T | F       | T
F F | F       | T

Maintenant le côté droit:

x y | NOT X | NOT Y | (NOT x) or (NOT y)
========================================
T T | F     | F     | F
T F | F     | T     | T
F T | T     | F     | T
F F | T     | T     | T

Les valeurs finales sont les mêmes dans les deux tables. Cela prouve que les expressions sont équivalentes.

Exercice: Prouver que les expressions NOT (x OR y) et (NOT x) AND (NOT y) sont équivalentes.

C'est juste une façon de réaffirmer la vérité des énoncés, qui peuvent fournir des moyens plus simples de l'écriture des conditions afin de faire la même chose.

En anglais:

Quand quelque chose n'est pas ceci ou Cela, il n'est également pas ceci et pas cela.

Quand quelque chose n'est-ce pas et qu'il n'est pas ceci ou pas cela.

Remarque: compte tenu de l'imprécision de la langue anglaise sur le mot " ou " je l'utilise pour signifier un non-ou exclusif dans l'exemple précédent.

Par exemple le pseudo-code est équivalent:

Si NON(A OU B)...

SI (PAS UN) ET (NON B)....

SI NON(A ET B)...

SI NON(A) OU NON(B)...

"Il n'a pas une voiture ou un bus." signifie la même chose que "Il n'a pas de voiture, et il n'a pas un bus."

"Il n'a pas une voiture et un bus." signifie la même chose que "Il soit, n'a pas une voiture, ou n'a pas un bus, je ne suis pas sûr, il a peut-être aucun des deux."

Bien sûr, dans la plaine de l'anglais ", Il n'a pas une voiture et un bus." a une forte implication qu'il a au moins une de ces deux choses. Mais, à strictement parler, d'un point de vue logique, la déclaration est également vrai si il n'a pas l'un ou l'autre.

Formellement:

• pas (voiture ou bus) = (pas de voiture) et (pas de bus)
• pas (voiture et bus) = (pas de voiture) ou (pas de bus)

En anglais, " ou " tend à signifier un choix, que vous n'avez pas les deux choses. Dans la logique, " ou " veut toujours dire la même chose que 'et/ou' en anglais.

Voici une table de vérité qui montre comment cela fonctionne:

Premier cas: pas (cor ou bus) = (pas de voiture) et (pas de bus)

 c | b || c or b | not (c or b) || (not c) | (not b) | (not c) and (not b)
---+---++--------+--------------++---------+---------+--------------------
 T | T ||    T   |      F       ||    F    |    F    |        F
---+---++--------+--------------++---------+---------+--------------------
 T | F ||    T   |      F       ||    F    |    T    |        F
---+---++--------+--------------++---------+---------+--------------------
 F | T ||    T   |      F       ||    T    |    F    |        F
---+---++--------+--------------++---------+---------+--------------------
 F | F ||    F   |      T       ||    T    |    T    |        T
---+---++--------+--------------++---------+---------+--------------------

Deuxième cas: pas (voiture et bus) = (pas de voiture) ou (pas de bus)

 c | b || c and b | not (c and b) || (not c) | (not b) | (not c) or (not b)
---+---++---------+---------------++---------+---------+--------------------
 T | T ||    T    |       F       ||    F    |    F    |        F
---+---++---------+---------------++---------+---------+--------------------
 T | F ||    F    |       T       ||    F    |    T    |        T
---+---++---------+---------------++---------+---------+--------------------
 F | T ||    F    |       T       ||    T    |    F    |        T
---+---++---------+---------------++---------+---------+--------------------
 F | F ||    F    |       T       ||    T    |    T    |        T
---+---++---------+---------------++---------+---------+--------------------

DeMorgan de la Loi permet à l'état d'une chaîne d'opérations logiques de différentes manières. Il s'applique à la logique et théorie des ensembles, où, dans la théorie des ensembles que vous utilisez en complément pour ne pas, à l'intersection de et de, et de l'union pour ou.

DeMorgan la Loi vous permet de simplifier une expression logique, l'exécution d'une opération qui est assez similaire à la distribution des biens de la multiplication.

Donc, si vous avez de la suite dans un C-comme le langage

if !(x || y || z) { /* do something */}

Il est logiquement équivalent à:

if (!x && !y && !z)

Il travaille également comme suit:

if !(x && !y && z)

se transforme en

if (!x || y || !z)

Et vous pouvez, bien sûr, aller dans le sens inverse.

L'équivalence de ces déclarations est facile de voir à l'aide de quelque chose qui s'appelle une table de vérité. Dans une table de vérité, il vous suffit de disposer vos variables (x, y, z) et la liste de toutes les combinaisons d'entrées pour ces variables. Vous avez ensuite des colonnes pour chaque prédicat, ou une expression logique, et de vous déterminer pour les entrées, la valeur de l'expression. De tout cursus universitaire pour les sciences informatiques, en génie informatique ou en génie électrique sera probablement vous conduire fou avec le nombre et la taille de la table de vérité que vous devez construire.

Alors pourquoi apprendre? Je pense que la principale raison pour laquelle, dans le calcul, c'est qu'il peut améliorer la lisibilité de la plus grande des expressions logiques. Certaines personnes n'aiment pas l'aide de logique de ne pas ! devant expressions, car ils pensent qu'il peut confondre quelqu'un, s'ils le manquer. L'impact de l'utilisation de DeMorgan de la Loi sur la porte au niveau de jetons est utile, toutefois, parce que certains types de porte sont plus rapides, moins chers, ou vous êtes déjà à l'aide d'un ensemble de circuits intégrés pour eux de sorte que vous pouvez réduire le nombre de puce de paquets nécessaires pour le résultat.