¿Por qué es ?

22

Me gustaría saber si hay una regla para probar esto. Por ejemplo, si uso la ley distributiva solo obtendré .(AA)(A¬B)

usuario78333
fuente
2
¡Bienvenido a Computer Science! Que has intentado ¿Dónde te quedaste atascado? No queremos simplemente darle la solución; Queremos que entiendas. Sin embargo, dado que no sabemos cuál es su problema subyacente, no podemos comenzar a ayudarlo. Vea aquí consejos para hacer preguntas sobre problemas de ejercicio. Si no está seguro de cómo mejorar su pregunta, ¿por qué no preguntar en Computer Science Chat ?
Rafael
Un ser verdadero es necesario en ambas condiciones y es suficiente para el de la izquierda.
Millie Smith

Respuestas:

55

Creo que las imágenes son excelentes para cualquier cosa lo suficientemente simple como para usarlas, que es esto.

Diagrama rendido

Recuerda:

Y significa el área ocupada por ambas cosas. Entonces, el del medio es lo que se toma fuera de B, pero también dentro de A. Su unión no se cuenta porque está dentro de A pero no fuera de B.

O significa que está cubierto por uno o ambos. Ambos cubren la parte de A que está fuera de B, y la unión está cubierta por A (primera imagen), por lo que también se cuenta. Con todo, solo tienes A otra vez.

Lo siento si esto es demasiado simplista, no estoy seguro de en qué nivel estás.

Irlanda
fuente
Para completar, podría ser bueno mostrar el caso donde B y A son disjuntos y otro caso donde B es A.
Eric Duminil
11
@EricDuminil No estoy de acuerdo. Lo mejor de este trabajo de diagrama de Venn es que es válido si alguna de las regiones está vacía o no.
Mark S.
3
+1 a la respuesta de Mark S. Lo que pasa con los diagramas de Venn, y la razón por la que todavía (¡espero!) Que se enseñan en las clases de matemáticas de la escuela intermedia, es que realmente funcionan . Si usted (Eric) se pregunta "pero ¿qué pasa si B y A son disjuntos? ...", entonces todavía no ha entendido qué representa realmente un diagrama de Venn. Representa las cuatro posibilidades lógicas como cuatro regiones geométricas: (A&B) [la cuña del medio], (A y ~ B) [media luna izquierda], (~ A y B) [media luna derecha] y (~ A y ~ B) [el resto de la página]. Colorearlos como lo hizo Erin nos ayuda a visualizar un problema lógico como un problema geométrico .
Quuxplusone
@EricDuminil (destinado a cualquiera que lea esto en el futuro) si son disjuntos, el del medio será A (sin parte de A en el interior de B) para que tenga A o A = A, y si A = B, el medio estará vacío (ninguna parte de A está fuera de B), por lo que tendrá A o nada = A
Erin
1
@djechlin: estaba cansado. Si A es B, puede ignorar las partes izquierda y derecha.
Eric Duminil
48

Hay muchas formas de ver esto. Una es una tabla de verdad. Otra es usar la regla distributiva:

A(A¬B)=(A)(A¬B)=A(¬B)=A=A.
Yuval Filmus
fuente
En el segundo paso, ¿no debería ese signo igual significar relación de equivalencia?
KumarAnkit
Estoy usando = en su significado habitual, como en 2 + 2 = 4.
Yuval Filmus
ok, ¿puedes explicar la transición del segundo paso al tercer paso?
KumarAnkit
9

Usaría mi regla de inferencia menos favorita: Eliminación de disyunción . Básicamente, dice que si sigue de , y sigue de , entonces debe ser verdadero si :P R Q R P Q ( P R ) , ( Q R ) , ( P Q ) RRPRQRPQ

(PR),(QR),(PQ)R

Así que supongamos que . Establezca , , y aplique la regla:P = A Q = A ¬ B R = AA(A¬B)P=AQ=A¬BR=A

  • Si ( ) hemos terminado.= AP=A
  • Si entonces (por eliminación de conjunción, )A S T SQ=A¬BASTS
  • Por eliminación de la disyunción .A(A¬B)A

Lo inverso es trivial: suponga , luego por una de las variantes de introducción de conjunción ( para cualquier ) .S S T T A A ( )ASSTTAA()

Aquí hay un diagrama de esta prueba:

Prueba rendida

CompuChip
fuente
44
Lo siento, ¿cómo dibujaste ese diagrama? Huelo el más leve olor a Coq.
Tobia Tesan
1
@TobiaTesan Yo fui quien "dibujó" el diagrama. Utilicé un software llamado pizarra para hacerlo.
Sriotchilism O'Zaic
1
@EpsilonNeighborhoodWatch: muchas gracias. Disculpe por abusar aún más de su paciencia, pero ¿se puede obtener ese software de alguna manera? El enlace en el encabezado (www.cogsci.rpi.edu/slate) parece estar muerto
Tobia Tesan
@TobiaTesan Microsoft Visio también se puede utilizar para dibujar diagramas como ese. Si está afiliado a una universidad o gran empresa que ofrece software de Microsoft a estudiantes / empleados, o si tiene una suscripción a MSDN, es posible que ya tenga acceso pagado.
Nat
@Nat Sure (o puede ayudarlo y hacerlo en TikZ: P), pero tenía la impresión de que la cosa utilizada por EpsilonNeighborhoodWatch tenía funciones de asistente de prueba, de ahí mi interés :) FWIW Proof General puede hacer algo como esto, pero La visualización del árbol de pruebas es mucho más fea.
Tobia Tesan
5

CDCD=DDCD

C=A¬BD=A

chi
fuente
3

Un aspecto más intuitivo:

Asiempre es cierto cuando Aes cierto.

A & -Bsolo es cierto cuando Aes cierto.

Intuitivamente, aplicar OR a estos dos produciría un resultado Cque siempre es verdadero cuando Aes verdadero. Como tal, Csiempre es cierto cuando Aes cierto.

(Deja de leer aquí si esta explicación te funciona).

Así es como pienso sobre este problema. Sin embargo, esta explicación no está completa ya que todo lo que hemos mostrado es eso A -> Cy no A <-> C.

Entonces, también demostremos eso C -> A.

Asiempre es falso cuando Aes falso.

A & -Bsiempre es falso cuando Aes falso.

Intuitivamente, aplicar OR a estos dos produciría un resultado Cque siempre es falso cuando Aes falso. Como tal, Csiempre es falso cuando Aes falso; -A -> -C, que es lo mismo que C -> A.

Así A -> Cy C -> Aasí A <-> C.

Quelklef
fuente
3

A veces, las letras confunden a las personas. A la gente le gusta la comida, porque es fácil pensar en ella.

Imagine que le pido que tire una moneda para elegir entre una O la otra de las siguientes dos opciones:

  • Una manzana, O ...
  • Una manzana, y definitivamente no un plátano.

[El primero es igual a "A", el segundo "A y no B". Pero no pienses en las letras. Piensa en la manzana y en si también obtienes una banana.]

El primero realmente significa "una manzana fersure, y tal vez obtendrás un plátano".

Entonces, dejar algo afuera es lo mismo que decir "tal vez".

Mirándolos como un par, lo que sea que obtengas, definitivamente habrá una Apple involucrada. Hurra. Y si su monedero elige el correcto, es posible que obtenga un plátano.

¿Pero no es lo mismo que decir "tal vez obtendrás un plátano"? ¿Solo, con la mitad de probabilidad?

Entonces, todo lo que definitivamente puedes decir lógicamente es que obtendrás una Apple. No puedes decir nada sobre si obtendrás un plátano.

Dewi Morgan
fuente
3

Similar a la respuesta de Yuval Filmus. Usando álgebra booleana, en ingeniería de notación, y factorizando (o factorizando) en A.

A+AB¯=A(1+B¯)=A1=A

Onur
fuente
3

Parece que nadie lo mencionó todavía, así que seguiré adelante.

La ley para tratar este tipo de problemas es la ley de absorción que establece que pv (p ^ q) = p y también que p ^ (pvq) = p. Si intenta utilizar la ley distributiva sobre esto, lo mantendrá en círculos para siempre:

(A v A) ^ (A v ~ B) = A ^ (A v ~ B) = (A ^ A) v (A ^ ~ B) = A v (A ^ ~ B) = (A v A) ^ (A v ~ B)

Usé el símbolo incorrecto para no e igual, pero el punto aquí es que cuando vas en círculos / cuando hay una y / o falta de coincidencia, por lo general, debes observar la ley de abstención.

B es irrelevante para el resultado, como notará si coloca esto en una tabla de verdad.

Arturo
fuente
Esto va bien con la respuesta de manzana y plátano
Erin
1
@Erin +1 Además, proporciona una regla, mientras que la respuesta de manzana y plátano solo apelaba a la intuición, y el OP pidió una regla, no la intuición.
Rosie F
2

Otra forma intuitiva de ver esto:

Si A es un conjunto, entonces podemos decir que cualquier objeto dado es (en A) o (no en A).

Ahora mire S = A o (A y no B) :

  • Si un objeto está en A, entonces "A o cualquier cosa" contiene todos los elementos en A, por lo que el objeto también estará en S.

  • Si un objeto no está en A, entonces "A y cualquier cosa" excluye todos los elementos que no están en A, por lo que el objeto no está en A ni en (A y no B), por lo que no está en S.

Entonces, el resultado es que cualquier objeto en A está en S, y cualquier objeto que no esté en A no está en S. Entonces, intuitivamente, los objetos en S deben ser exactamente los de A, y no otros objetos.

Cuando dos conjuntos tienen elementos idénticos, se definen como el mismo conjunto. Por lo tanto A = S.

Stilez
fuente
2

Un método simple que siempre puede usar si está atascado es el análisis de casos.

A

A

A

Juan Doe el justo
fuente
0
lets consider: 
  1) A as 1 and B as 0. 
  2) A as 0 and B as 1. 
  3) A as 1 and B as 1.
  4) A as 0 and B as 0.

using the first scenario : A or (A and !B) => 1 or ( 1 and 1) => 1 0r 1 => 1
using the second scenario: A or (A and !B) => 0 or ( 0 and 0) => 0 or 0 => 0
using the third scenario : A or (A and !B) => 1 or ( 1 and 0) => 1 or 0 => 1
using the fourth scenario: A or (A and !B) => 0 or ( 0 and 1) => 0 or 0 => 0

From the above four cases, the result always depends on A not on B, so the result is A.
Prudhvi seeramreddi
fuente