Matemáticas | predicados y cuantificadores | conjunto 2

Prerrequisito : Predicados y cuantificadores Conjunto 1 , Equivalencias proposicionales

Equivalencias lógicas que involucran cuantificadores
Dos enunciados lógicos que involucran predicados y cuantificadores se consideran equivalentes si y solo si tienen el mismo valor de verdad, sin importar qué predicados se sustituyan en estos enunciados, independientemente del dominio utilizado para las variables en las proposiciones.
Hay dos equivalencias muy importantes que involucran cuantificadores, que se dan a continuación:

1.  

2.

Uno se ve obligado a pensar si las equivalencias se mantendrían si la conjunción se reemplaza por la disyunción en (1) y la disyunción se reemplaza por la conjunción en (2). La respuesta puede parecer Sí, pero pensándolo bien, te darás cuenta de que la respuesta es No.

Para probar por qué no son equivalentes, debemos entender qué hace que dos declaraciones sean equivalentes. Como se explicó en el artículo anterior Equivalencias Proposicionales dos enunciados $PAGS$ y $q$ son equivalentes si-

, which can also be restated as .

Si son equivalentes entonces,
$\forall x(P(x)\vee Q(x)) \Leftrightarrow \forall xP(x) \vee \forall xQ(x)$ y,
$\existe x(P(x)\cuña Q(x)) \Leftrightarrow \existe xP(x) \cuña \existe xQ(x)$
ambos deben ser verdaderos.

Comprobemos primero por $\forall x(P(x)\vee Q(x)) \Leftrightarrow \forall xP(x) \vee \forall xQ(x)$ .
¿Es $\forall x(P(x)\vee Q(x)) \Rightarrow \forall xP(x) \vee \forall xQ(x)$ verdad?
No.

Prueba – Supongamos que la Hipótesis $\forall x(P(x)\vee Q(x))$ es verdadera. Eso quiere decir que hay ciertas $x$ para las que $P(x)$ es verdad y otras para las que $Q(x)$ es verdad.
También es posible que para algunos $x$ ambos $P(x)$ y $Q(x)$ sean verdaderos. Pero en cualquier caso, todos $x$ deben satisfacer $P(x)$ o $Q(x)$ ambos, ya que la hipótesis es verdadera.
La conclusión (RHS) es verdadera cuando la disyunción es verdadera. Como se desprende del razonamiento anterior, esto $P(x)$ es cierto para algunos valores de $x$ y $Q(x)$ para algunos.
Por lo tanto, ambos $\forall xP(x)$ y $\forall xQ(x)$ son falsos, ya que ninguno de ellos es verdadero para todos los valores de $x$ .
En el caso donde $P(x)$ y $Q(x)$ mantenga para todos $x$ entonces esta equivalencia es verdadera, pero por lo demás es falsa.

Entonces, $\forall xP(x) \vee \forall xQ(x) \equiv F$ . Según nuestra suposición, la hipótesis es verdadera, pero nuestra conclusión resultó ser falsa. Esto no puede ser cierto para un condicional, por lo tanto, el condicional
$\forall x(P(x)\vee Q(x)) \Rightarrow \forall xP(x) \vee \forall xQ(x)$ es falso.

Since one conditional is false, the complete biconditional is false.
Hence, .

De manera similar, también se puede demostrar que,
$\exists x(P(x)\wedge Q(x)) \not\equiv \exists xP(x) \wedge \exists xQ(x)$

Como ejercicio, pruebe la no equivalencia anterior y también las equivalencias que involucran los cuantificadores mencionados anteriormente. Recuerda probar el bicondicional y no solo un condicional.

Negar afirmaciones cuantificadas
Considere la afirmación «Todos los graduados en ciencias de la computación han tomado un curso de matemáticas discretas».
La declaración anterior es una cuantificación universal, $xP(x)$
donde $P(x)$ está la declaración «x ha tomado un curso en Matemáticas Discretas» y el dominio de $x$ es todos los Licenciados en Ciencias de la Computación.
La negación de esta afirmación es “No se da el caso de que todo licenciado en informática haya hecho un curso de Matemática Discreta” o simplemente “Hay un licenciado en informática que no haya hecho un curso de Matemática Discreta”.
La afirmación anterior se puede expresar mediante una cuantificación existencial.
$\exists x \neg P(x)$
Por lo tanto, obtenemos la siguiente equivalencia lógica-
$\neg \forall xP(x) \equiv \exists x \neg P(x)$
De manera similar,
$\neg \exists xP(x) \equiv \forall x \neg P(x)$
Estas equivalencias no son más que reglas para la negación de cuantificadores. También se conocen como leyes de De Morgans para cuantificadores.

In summary,

Cuantificadores anidados
Es posible utilizar dos cuantificadores de forma que uno de ellos esté dentro del alcance del otro. En tales casos se dice que los cuantificadores están anidados.
Por ejemplo, $\forall x \exists y (x + y = 0)$
la afirmación anterior se lee como “Para todo $x$ , existe $y$ tal que $x + y = 0$ .

Nota: El orden relativo en el que se colocan los cuantificadores es importante a menos que todos los cuantificadores sean del mismo tipo, es decir, todos son cuantificadores universales o todos son cuantificadores existenciales.

In summary,

Preguntas de GATE CS Corner

Practicar las siguientes preguntas te ayudará a poner a prueba tus conocimientos. Todas las preguntas se han hecho en GATE en años anteriores o en pruebas simuladas de GATE. Es muy recomendable que los practiques.
1. GATE CS 2012, Pregunta 17
2. GATE CS 2013, Pregunta 27
3. GATE CS 2013, Pregunta 47
4. GATE CS 2010, Pregunta 30
5. GATE CS 2009, Pregunta 26
6. GATE CS 2005, Pregunta 36
7. GATE CS 2016 Conjunto-2, pregunta 37
La mayoría de las preguntas formuladas en GATE de Matemáticas discretas se centran en la lógica de predicados. Casi todos ellos implican cuantificadores.

Este artículo es una contribución de Chirag Manwani . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta