De Morgan reglas explicadas

Question

Podría explicar las reglas De Morgan forma más sencilla posible (por ejemplo, a alguien sólo con un fondo matemáticas de la escuela secundaria)?

Answer 1

Tenemos dos valores: T y F

.

Podemos combinar estos valores de tres maneras:. NOT, AND y OR

NOT es el más simple:

• NOT T = F
• NOT F = T

podemos escribir esto como un tabla de verdad

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

En la concisión

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

Piense en NOT como el complemento , que es, resulta un valor en el otro.

AND trabaja en dos valores:

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

AND es T solamente cuando tanto su argumentos (los valores de x y y en la tabla de verdad) son T -. F y de lo contrario

OR es T cuando al menos uno de sus argumentos es T:

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

Podemos definir combinaciones más complejas. Por ejemplo, podemos escribir una tabla de verdad para x AND (y OR z), y la primera fila está abajo.

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

Una vez que sabemos cómo evaluar x AND (y OR z), podemos llenar el resto de la mesa.

A evaluar la combinación, evaluar las piezas y trabajar desde allí. Los paréntesis indican qué partes para evaluar en primer lugar. Lo que se sabe de la aritmética ordinaria le ayudará a trabajar hacia fuera. Digamos que tiene 10 - (3 + 5). En primer lugar se evalúa la parte de paréntesis, a get

10 - 8

y evaluar que como de costumbre para obtener la respuesta, 2.

La evaluación de estos Las expresiones funciona de manera similar. Sabemos cómo funciona OR desde arriba, por lo que podemos ampliar nuestra mesa un poco:

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

Ahora es casi como estamos de vuelta a la mesa x AND y. Simplemente sustituimos el valor de y OR z y evaluamos. En la primera fila, tenemos

T AND (T OR T)

que es el mismo que

T AND T

que es simplemente T.

repetir el mismo proceso para los 8 valores posibles de x, y y z (2 valores posibles de tiempos x 2 valores posibles de tiempos y 2 valores posibles de z) para obtener

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

Algunas expresiones pueden ser más complejos de lo que necesitan ser. Por ejemplo,

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

En otras palabras, es NOT (NOT x) equivalente a solo x.

reglas de DeMorgan son trucos útiles que nos permiten convertir entre expresiones equivalentes que se ajustan a ciertos patrones:

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

(Se podría pensar en esto como la forma distribuye a través de simples expresiones NOT AND y OR.)

Su sentido común probablemente ya entiende estas reglas! Por ejemplo, pensar en el poco de la sabiduría popular de que "no se puede estar en dos lugares a la vez." Podríamos hacerlo encajar la primera parte de la primera regla:

NOT (here AND there)

La aplicación de la regla, que es otra forma de decir "no estás aquí o usted no está allí."

Ejercicio:? ¿Cómo se podría expresar la segunda regla en la llanura Inglés

En la primera regla, echemos un vistazo a la tabla de verdad para la expresión en el lado izquierdo del signo igual.

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

Ahora el lado derecho:

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

Los valores finales son los mismos en ambas tablas. Esto demuestra que las expresiones son equivalentes.

Ejercicio:. Demostrar que las expresiones NOT (x OR y) y (NOT x) AND (NOT y) son equivalentes

Answer 2

Mirando por encima de algunas de las respuestas, creo que puedo explicarlo mejor mediante el uso de condiciones que realmente están relacionados entre sí.

ley de DeMorgan se refiere al hecho de que hay dos formas idénticas para escribir cualquier combinación de dos condiciones - específicamente, la combinación AND (ambos deben cumplir las condiciones), y la combinación OR (ya sea uno puede ser verdad). Ejemplos son:

Parte 1 de la Ley de De Morgan

Declaración:. Alice tiene un hermano
Condiciones:. Alice tiene un hermano OR Alice tiene una hermana
Frente: Alice es un hijo único (no NOT tiene un hermano)
. Condiciones:. Alicia no NOT tiene un hermano, AND ella no NOT tener una hermana

En otras palabras: NOT [A OR B] = [NOT A] AND [NOT B]

Parte 2 de la Ley de De Morgan

Declaración: Bob es un Conductor de coche de. Condiciones:. Bob tiene un coche AND Bob tiene una licencia
Frente: Bob es un NOT Conductor de coche de. Condiciones:. Bob no NOT tiene un coche, OR Bob hace NOT tiene una licencia

En otras palabras:. NOT [A AND B] = [NOT A] OR [NOT B]

creo que esto sería un poco menos confuso para un niño de 12 años de edad. Es ciertamente menos confuso que toda esa tontería de las tablas de verdad (incluso me estoy confundido mirando todas esas).

Answer 3

Es sólo una forma de declaraciones de la verdad RESTATE, que pueden proporcionar formas más sencillas de escribir condicionales a hacer lo mismo.

En la llanura Inglés:
Cuando algo no es esto o aquello, sino que también no es esto y no aquello.
Cuando algo no está presente y que, también, no es esto o no eso.

Nota:. Dada la imprecisión del lenguaje Inglés en la palabra 'o' lo estoy usando para referirse a una licencia no exclusiva o en el ejemplo anterior

Por ejemplo el siguiente pseudo-código es equivalente:
Si NO (A o B) ...
IF (NO A) Y (NO B) ....

SI NO (A y B) ...
SI NO (A) o no (B) ...

Answer 4

Si usted es un oficial de policía en busca de bebedores menores de edad, se puede hacer una de las siguientes, y la ley de De Morgan dice que equivalen a lo mismo:

Formulación 1 (A y B)

  

Si son en la edad   limitar y beber un alcohólica   bebida, arrestarlos.

Formulación 2 (NOT (NO A O NO B))

  

Si son más   el límite de edad o beber una    no alcohólica de bebidas, que se vayan.

Esto, por cierto, no es mi ejemplo. Por lo que yo sé, fue parte de un experimento científico en el que la misma regla se expresa de diferentes maneras para averiguar cuánto de una diferencia que hizo en la capacidad de las personas para comprenderlos.

Answer 5

"Él no tiene ya sea un coche o un autobús." significa lo mismo que "El no tener un coche, y él no tiene un autobús."

"Él no tiene un coche y un autobús." medios lo mismo que "Él, o bien no tienen un coche, o no tiene un autobús, no estoy seguro de lo que, tal vez él no tiene ni."

Por supuesto, en la llanura Inglés "Él no tiene un coche y un autobús." tiene una fuerte implicación de que tiene al menos una de esas dos cosas. Pero, en rigor, desde un punto de vista lógica de la declaración también es cierto si él no tiene ninguno de ellos.

Formalmente:

• no (coche o autobús) = (no coche) y (no bus)
• no (coche y autobús) = (no coche) o (no bus)

En Inglés, 'o' tiende a significar una elección, que no tiene ambas cosas. En lógica, 'o' siempre significa lo mismo que 'y / o' en Inglés.

Aquí hay una tabla de verdad que muestra cómo funciona esto:

Primer caso: no (cor o autobús) = (no coche) y (no autobuses)

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

Segundo caso: no (coche y autobús) = (no coche) o (no 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

Dibuje un simple diagrama de Venn, dos círculos que se intersecan. Un puesto en el izquierdo y B en la derecha. Ahora (A y B) es, obviamente, el bit de intersección. Así NO (A y B) es todo lo que no está en la intersección de bits, el resto de los dos círculos. Color que en.

dibujar otro dos círculos como antes, A y B, de intersección. Ahora NO (A) es todo lo que está en el círculo de la derecha (B), pero no la intersección, porque eso es, obviamente, A, así como B. Color de esto en. Del mismo modo NO (B) es todo en el círculo de la izquierda, pero no la intersección, porque eso es B, así como A. color en esta.

Dos dibujos tienen el mismo aspecto. Has demostrado que NO (A y B) = NO (A) o NO (B). T'other caso se deja como ejercicio para el estudiante.

Answer 7

La ley de De Morgan permite a usted establecer una serie de operaciones lógicas de diferentes maneras. Se aplica a la lógica y la teoría de conjuntos, donde en teoría de conjuntos se utiliza para el complemento no, la intersección de y, y la unión de o.

La ley de De Morgan le permite simplificar una expresión lógica, la realización de una operación que es bastante similar a la propiedad distributiva de la multiplicación.

Por lo tanto, si usted tiene la siguiente en un C-como el lenguaje

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

Es lógicamente equivalente a:

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

También funciona de esta manera:

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

se convierte en

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

Y usted puede, por supuesto, ir a la inversa.

La equivalencia de estos estados es fácil ver el uso de algo que se llama una tabla de verdad. En una tabla de verdad, sólo tiene que jalonan sus variables (x, y, z) y la lista de todas las combinaciones de entradas para estas variables. A continuación, tiene columnas para cada predicado o expresión lógica, y se determina para las entradas dadas, el valor de la expresión. Cualquier plan de estudios de la universidad de ciencias de la computación, ingeniería informática, ingeniería eléctrica o es probable que conduzca loco con el número y tamaño de las tablas de verdad se debe construir.

Entonces, ¿por ellos aprender? Creo que la razón más importante en la informática es que puede mejorar la legibilidad de las expresiones lógicas más grandes. Algunas personas no les gusta usar lógico no ! frente a las expresiones, ya que creo que puede confundir a alguien si se lo pierden. El impacto del uso de la ley de De Morgan en el nivel de la puerta de los chips es útil, sin embargo, debido a que ciertos tipos de puertas son más rápidos, más barato, o si ya está utilizando un circuito integrado todo para ellos por lo que puede reducir el número de paquetes de chips necesarios para la resultado.

Answer 8

No sé por qué he mantenido este todos estos años, pero ha demostrado ser útil en un número de ocasiones. Gracias al Sr. Bailey, mi grado 10 profesor de matemáticas. Lo llamó de De Morgan Teorema.

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

Cuando se mueve la negación en o fuera de los soportes, el operador lógico (AND, OR) cambia.