règles expliquées De Morgan

Question

Pourriez-vous s'il vous plaît expliquer le règles aussi simple De Morgan que possible (par exemple à quelqu'un avec seulement un arrière-plan de mathématiques du secondaire)?

Answer 1

Nous avons deux valeurs: T et F

.

Nous pouvons combiner ces valeurs de trois façons: NOT, AND et OR

.

NOT est la plus simple:

• NOT T = F
• NOT F = T

On peut écrire ceci comme table de vérité :

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

Par souci de concision

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

Pensez à NOT comme complément , qui est, il se 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 que lorsque son arguments (les valeurs de x et y dans la table de vérité) sont T -. Et F autrement

OR est T quand 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

On peut 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 rangée 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 pièces et travailler à partir de là. Les parenthèses indiquent les parties à évaluer en premier. Ce que vous savez de l'arithmétique ordinaire vous aidera à travailler dehors. Disons que vous avez 10 - (3 + 5). Tout d'abord vous évaluez la partie entre parenthèses pour obtenir

10 - 8

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

L'évaluation de ces expressions fonctionne de la même. Nous savons comment OR fonctionne en haut, afin que nous puissions élargir notre table un peu:

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

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

T AND (T OR T)

qui est la même que

T AND T

qui est tout simplement T.

Nous répétons le même processus pour les 8 valeurs possibles de x, y et z (2 valeurs possibles des temps de x 2 valeurs possibles des temps de y 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 que ce qu'ils doivent être. Par exemple,

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

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

Les règles de trucs pratiques sont De Morgan qui nous permettent de convertir 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 à ce que la façon dont NOT distribue grâce à de simples expressions de AND et OR.)

Votre bon sens comprend probablement déjà ces règles! Par exemple, pensez au peu de sagesse populaire que « vous ne pouvez pas être à deux endroits à la fois. » Nous pourrions faire adapter à 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 vous n'êtes pas là. »

Exercice: Comment pouvez-vous exprimer la deuxième règle en anglais simple

Pour la première règle, regardons la table de vérité pour 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é droite:

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

Answer 2

Recherche sur quelques-unes des réponses, je pense que je peux l'expliquer mieux en utilisant des conditions qui sont effectivement liés les uns aux autres.

Droit De Morgan fait référence au fait qu'il existe deux façons identiques d'écrire une combinaison de deux conditions - en particulier, la combinaison de AND (les deux conditions doivent être remplies), et la combinaison de OR (soit un peut être vrai). Les exemples sont:

Partie 1 de la loi de De Morgan

Déclaration: Alice a un frère
. Conditions:. Alice a un frère OR Alice a une soeur
Ci-contre: Alice est un enfant unique (ne NOT un frère)
. Conditions:. Alice fait NOT un frère, elle ne AND NOT une soeur

En d'autres termes: NOT [A OR B] = [NOT A] AND [NOT B]

Partie 2 de la loi de De Morgan

Déclaration: Bob est un conducteur de voiture
. Conditions:. Bob a une AND voiture Bob a une licence
Ci-contre: Bob est NOT un conducteur de voiture
. Conditions:. Bob ne NOT une voiture, OR Bob ne NOT une licence

En d'autres termes:. NOT [A AND B] = [NOT A] OR [NOT B]

Je pense que ce serait un peu moins déroutant pour un enfant de 12 ans. Il est certainement moins confus que tout ce non-sens sur les tables de vérité (même je deviens confus regardant tous ceux).

Answer 3

Il est juste un moyen de retraiter les états de la vérité, qui peut fournir des moyens plus simples de l'écriture pour faire la conditionals même chose.

En clair: Quand quelque chose n'est pas ceci ou cela, il est pas non plus ceci et pas cela.
Quand quelque chose n'est pas ceci et cela, il est également pas ou pas.

Remarque:. Compte tenu de l'imprécision de la langue anglaise sur le mot « ou » je l'utilise pour signifier une licence non exclusive ou dans l'exemple précédent

Par exemple, le pseudo-code suivant est équivalent: Si NOT (A ou B) ...
SI (PAS) ET (NON B) ....

SINON (A et B) ...
SINON (A) OU NON (B) ...

Answer 4

Si vous êtes un agent de police à la recherche pour les buveurs mineurs, vous pouvez faire un des éléments suivants, et la loi de De Morgan dit qu'ils équivaloir à la même chose:

FORMULATION 1 (A et B)

  

S'ils sont sous l'âge   limite et boire un alcoolique   boisson, les arrêter.

FORMULATION 2 (NOT (NOT A OU NON B))

  

S'ils sont sur   la limite d'âge ou une consommation d'alcool    non alcoolisées boisson, laissez-les aller.

, par ailleurs, n'est pas mon exemple. Pour autant que je sache, il faisait partie d'une expérience scientifique où la même règle a été exprimée de différentes façons de savoir combien de différence il a fait dans la capacité des peuples à les comprendre.

Answer 5

« Il n'a pas non plus une voiture ou un bus. » signifie la même chose que « Il n'a pas de voiture, et il ne dispose pas d'un bus. »

« Il n'a pas de voiture et un bus. » signifie la même chose que « Il ne soit pas une voiture, ou ne dispose pas d'un bus, je ne suis pas sûr, peut-être qu'il n'a ni ».

Bien sûr, en anglais simple « Il n'a pas de voiture et un bus. » a une forte implication qu'il a au moins une de ces deux choses. Mais, à proprement parler, d'un point de vue logique de la déclaration est également vrai s'il n'a pas non plus d'entre eux.

Formellement:

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

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

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

Premier cas: non (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: non (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
---+---++---------+---------------++---------+---------+--------------------

Answer 6

Dessine simple diagramme de Venn, deux cercles entrecroisés. Mettez A dans la gauche et B à droite. Maintenant (A et B) est évidemment le bit d'intersection. Donc pas (A et B) est tout ce qui est pas dans le peu d'intersection, le reste des deux cercles. Couleur que.

Dessinez deux autres cercles comme avant, A et B, intersection. Maintenant PAS (A) est tout ce qui est dans le cercle droit (B), mais pas l'intersection, parce que c'est évidemment A, ainsi que B. Couleur cela en. De même pas (B) est tout dans le cercle gauche, mais pas l'intersection, parce que ce B ainsi que A. Couleur ceci dans.

Deux dessins se ressemblent. Vous avez prouvé que NOT (A et B) = NON (A) ou non (B). Cas est laissé te other comme un exercice pour l'étudiant.

Answer 7

Law vous permet de De Morgan énoncez une série d'opérations logiques de différentes manières. Il applique à la logique et la théorie des ensembles, où, dans la théorie des ensembles que vous utilisez pour complément non, intersection et, et de l'union pour ou.

Law vous permet de De Morgan simplifier une expression logique, l'exécution d'une opération qui est assez similaire à la propriété distributive de la multiplication.

Donc, si vous avez les éléments suivants dans un langage C comme

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

Il est logiquement équivalent à:

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

Il fonctionne aussi comme ceci:

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 en utilisant ce qu'on appelle une table de vérité. Dans une table de vérité, vous disposez simplement vos variables (x, y, z) et la liste de toutes les combinaisons d'entrées pour ces variables. Vous avez alors des colonnes pour chaque attribut, ou l'expression logique, et vous déterminez pour les entrées données, la valeur de l'expression. Tout cursus universitaire pour la science informatique, génie informatique, génie électrique ou vous conduira probablement Bonkers avec le nombre et la taille des tables de vérité, vous devez construire.

Alors pourquoi les apprendre? Je pense que la principale raison de l'informatique est qu'il peut améliorer la lisibilité des expressions logiques plus grandes. Certaines personnes n'aiment pas utiliser logique de ne pas ! devant des expressions, car ils pensent qu'il peut confondre une personne si elle manque. L'impact de l'utilisation de la loi de De Morgan au niveau de la porte de puces est utile, cependant, parce que certains types de portes sont plus rapides, moins chers, ou vous utilisez déjà pour eux tout un circuit intégré de sorte que vous pouvez réduire le nombre de paquets de puces nécessaires à la résultat.

Answer 8

Je ne sais pas pourquoi je l'ai retenu cette toutes ces années, mais il est avéré utile à plusieurs reprises. Merci à M. Bailey, ma note 10 professeur de mathématiques. Il l'a appelé le théorème de De Morgan.

!(A || B) <==> (!A && !B)
!(A && B) <==> (!A || !B)

Lorsque vous déplacez la négation ou sur des supports, l'opérateur logique des changements (AND, OR).