boolean operations - son - explican las reglas de deMorgan

normas de morgan (8)

"Él no tiene ni un automóvil ni un autobús". significa lo mismo que "Él no tiene un automóvil, y no tiene un autobús".

"No tiene coche ni autobús". significa lo mismo que "O no tiene un automóvil, o no tiene un autobús, no estoy seguro de cuál, tal vez él no tenga ninguno".

Por supuesto, en inglés simple "Él no tiene un automóvil ni un autobús". tiene una fuerte implicación de que tiene al menos una de esas dos cosas. Pero, hablando estrictamente, desde un punto de vista lógico, la afirmación también es cierta si él no tiene ninguno de ellos.

Formalmente:

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

En inglés, ''o'' tiende a significar una elección, que no tienes 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 bus) = (no coche) y (no 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 ---+---++--------+--------------++---------+---------+--------------------

Segundo caso: no (automóvil y autobús) = (no automóvil) o (no autobús)

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

¿Podría por favor explicar las reglas de DeMorgan de la manera más simple posible (por ejemplo, a alguien con un historial de matemáticas en la escuela secundaria)?

Dibuja un diagrama simple de Venn, dos círculos que se intersecan. Ponga A en la izquierda y B en la derecha. Ahora (A y B) es obviamente el bit de intersección. Entonces, NO (A y B) es todo lo que no está en el bit de intersección, el resto de ambos círculos. Colorea eso en.

Dibuja otros dos círculos como antes, A y B, que se cruzan. Ahora NO (A) es todo lo que está en el círculo derecho (B), pero no la intersección, porque eso es obviamente A, así como B. Colorea esto. De manera similar, NO (B) es todo en el círculo izquierdo pero no la intersección, porque eso es B así como A. Colorea esto.

Dos dibujos parecen iguales. Has probado que NO (A y B) = NO (A) o NO (B). El otro caso se deja como ejercicio para el alumno.

Es solo una forma de repetir las declaraciones de verdad, que pueden proporcionar formas más simples de escribir condicionales para hacer lo mismo.

En inglés simple:
Cuando algo no es esto o aquello, tampoco es esto ni lo otro.
Cuando algo no es esto y aquello, tampoco lo es o no lo es.

Nota: Dada la imprecisión del idioma inglés en la palabra ''o'' Lo estoy usando para referirme a un ejemplo no exclusivo o en el ejemplo anterior.

Por ejemplo, el siguiente pseudocódigo es equivalente:
Si NO (A o B) ...
SI (NO A) Y (NO B) ....

SI NO (A y B) ...
SI NO (A) O NO (B) ...

La Ley de DeMorgan le permite establecer una serie de operaciones lógicas de diferentes maneras. Se aplica a la lógica y la teoría de conjuntos, donde en la teoría de conjuntos se usa el complemento para no, la intersección para y, y la unión para o.

La Ley de DeMorgan le permite simplificar una expresión lógica, realizando una operación que es bastante similar a la propiedad distributiva de la multiplicación.

Por lo tanto, si tiene lo siguiente en un lenguaje similar a C

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

Es lógicamente equivalente a:

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

También funciona así:

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

se convierte en

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

Y puedes, por supuesto, ir a la inversa.

La equivalencia de estas afirmaciones es fácil de ver usando algo llamado tabla de verdad. En una tabla de verdad, simplemente coloque sus variables (x, y, z) y enumere todas las combinaciones de entradas para estas variables. Luego tiene columnas para cada predicado, o expresión lógica, y determina para las entradas dadas, el valor de la expresión. Cualquier plan de estudios universitario de ciencias de la computación, ingeniería de computadoras o ingeniería eléctrica probablemente lo volverá loco con el número y tamaño de tablas de verdad que debe construir.

Entonces, ¿por qué aprenderlos? Creo que la razón más importante en la informática es que puede mejorar la legibilidad de expresiones lógicas más grandes. ¡A algunas personas no les gusta usar el lógico no ! En frente de las expresiones, ya que piensan que puede confundir a alguien si lo extrañan. Sin embargo, el impacto de usar la Ley de DeMorgan en el nivel de chips de la puerta es útil, ya que ciertos tipos de puertas son más rápidos, más baratos o ya está utilizando todo un circuito integrado para que pueda reducir la cantidad de paquetes de chips necesarios para el Salir.

No estoy seguro de por qué he conservado esto todos estos años, pero ha resultado útil en varias ocasiones. Gracias al señor Bailey, mi profesor de matemáticas de 10º grado. Él lo llamó Teorema de DeMorgan.

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

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

Revisando algunas de las respuestas, creo que puedo explicarlo mejor usando condiciones que realmente están relacionadas entre sí.

La Ley de DeMorgan se refiere al hecho de que existen dos formas idénticas de escribir una combinación de dos condiciones: específicamente, la combinación AND (ambas condiciones deben ser ciertas) y la combinación OR (cualquiera de las dos puede ser cierta). Algunos ejemplos son:

Parte 1 de la ley de DeMorgan

Declaración: Alice tiene un hermano.
Condiciones: Alice tiene un hermano OR Alice tiene una hermana.
Opuesto: Alice es hija única ( NOT tiene un hermano).
Condiciones: Alice NOT tiene un hermano, AND ella NOT tiene una hermana.

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

Parte 2 de la ley de DeMorgan

Declaración: Bob es un conductor de automóvil.
Condiciones: Bob tiene un auto AND Bob tiene una licencia.
Opuesto: Bob NOT es un conductor de automóvil.
Condiciones: Bob NOT tiene auto, OR Bob NOT tiene 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. Es ciertamente menos confuso que todas estas tonterías sobre las tablas de verdad (incluso me estoy confundiendo al ver todas esas).

Si usted es un oficial de policía que busca bebedores menores de edad, puede hacer uno de los siguientes, y la ley de De Morgan dice que es lo mismo:

FORMULACIÓN 1 (A y B)

Si están por debajo del límite de edad Y beben una bebida alcohólica, arréstenlos.

FORMULACIÓN 2 (NO (NO A O NO B))

Si están por encima del límite de edad O si están tomando una bebida no alcohólica , déjelos ir.

Esto, por cierto, no es mi ejemplo. Que yo sepa, era parte de un experimento científico en el que la misma regla se expresaba de diferentes maneras para descubrir cuánta diferencia había en la capacidad de las personas para entenderlas.

Tenemos dos valores: T y F

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

NOT es el más simple:

NOT T = F
NOT F = T

Podemos escribir esto como una tabla de verdad :

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

Por concisión

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

Piense en NOT como el complemento , es decir, convierte 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 solo cuando ambos argumentos (los valores de x e y en la tabla de verdad) son T - y F caso 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á debajo.

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

Una vez que sepamos cómo evaluar x AND (y OR z) , podemos completar el resto de la tabla.

Para evaluar la combinación, evaluar las piezas y trabajar desde allí. Los paréntesis muestran qué partes evaluar primero. Lo que sabes de la aritmética ordinaria te ayudará a resolverlo. Digamos que tienes 10 - (3 + 5) . Primero evalúas la parte entre paréntesis para obtener

10 - 8

y evalúelo como de costumbre para obtener la respuesta, 2 .

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

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

Ahora es casi como si estuviéramos de nuevo en la tabla 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 lo mismo que

T AND T

que es simplemente T .

Repetimos el mismo proceso para los 8 valores posibles de x , y y z (2 valores posibles de x veces 2 valores posibles de y veces 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 complejas de lo que necesitan ser. Por ejemplo,

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

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

Las reglas de DeMorgan son trucos prácticos 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)

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

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

NOT (here AND there)

Aplicando la regla, esa es otra forma de decir "no estás aquí o no estás allí".

Ejercicio: ¿Cómo podrías expresar la segunda regla en un lenguaje sencillo?

Para la primera regla, veamos 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 prueba que las expresiones son equivalentes.

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