Matemáticas | predicados y cuantificadores | Serie 1

Prerrequisito: Introducción a la Lógica Proposicional

Introducción
Considere el siguiente ejemplo. Necesitamos convertir la siguiente oración en una declaración matemática usando solo lógica proposicional.

"Every person who is 18 years or older, is eligible to vote."

La declaración anterior no puede expresarse adecuadamente utilizando solo la lógica proposicional. El problema al tratar de hacerlo es que la lógica proposicional no es lo suficientemente expresiva para tratar con variables cuantificadas. Hubiera sido más fácil si la declaración se refiriera a una persona específica. Pero como no es el caso y la declaración se aplica a todas las personas mayores de 18 años, estamos atascados.
Por lo tanto, necesitamos un tipo de lógica más poderosa.

Lógica de predicados
La lógica de predicados es una extensión de la lógica proposicional. Agrega el concepto de predicados y cuantificadores para capturar mejor el significado de las declaraciones que no pueden expresarse adecuadamente mediante la lógica proposicional.

¿Qué es un predicado?

Considere la declaración, » Xes mayor que 3″. Tiene dos partes. La primera parte, la variable X, es el sujeto del enunciado. La segunda parte, “es mayor que 3”, es el predicado . Se refiere a una propiedad que puede tener el sujeto del enunciado.
La declaración » Xes mayor que 3″ se puede denotar por P(x)donde PAGSdenota el predicado «es mayor que 3» y Xes la variable.
El predicado PAGSpuede ser considerado como una función. Indica el valor de verdad del enunciado P(x)en X. Una vez que se ha asignado un valor a la variable X, la declaración P(x)se convierte en una proposición y tiene un valor de verdad o falso (tf).
En general, una declaración que involucra n variablesx1, x2, x3,.. , xnse puede denotar por P(x1, x2, x3,.. , xn). Aquí Ptambién se le conoce como predicado de n-lugar o predicado de n-ario .

  • Ejemplo 1: Denotemos P(x)el enunciado “ x> 10″. ¿ Cuáles son los valores de verdad de P(11)y P(5)?

    Solución: P(11) es equivalente al enunciado 11 > 10, que es Verdadero.
    P(5)es equivalente al enunciado 5 > 10, que es Falso.

  • Ejemplo 2: Denotemos R(x,y)el enunciado “ x = y + 1“. ¿ Cuál es el valor de verdad de las proposiciones R(1,3)y R(2,1)?
    Solución: R(1,3) es el enunciado 1 = 3 + 1, que es Falso.
    R(2,1)es el enunciado 2 = 1 + 1, que es Verdadero.

¿Qué son los cuantificadores?

En la lógica de predicados, los predicados se usan junto con los cuantificadores para expresar hasta qué punto un predicado es verdadero en una variedad de elementos. El uso de cuantificadores para crear tales proposiciones se denomina cuantificación .

Hay dos tipos de cuantificación:

1. Cuantificación universal: las declaraciones matemáticas a veces afirman que una propiedad es verdadera para todos los valores de una variable en un dominio particular, llamado dominio del discurso . Tal declaración se expresa utilizando la cuantificación universal.
La cuantificación universal de P(x)para un dominio particular es la proposición que afirma que P(x)es verdadera para todos los valores de xen este dominio. El dominio es muy importante aquí ya que decide los posibles valores de x. El significado de la cuantificación universal de P(x)los cambios cuando se cambia el dominio. El dominio debe especificarse cuando se utiliza una cuantificación universal, ya que sin ella no tiene sentido.

Formally,
The universal quantification of P(x) is the statement
"P(x) for all values of x in the domain"

The notation \forall P(x) denotes the universal quantification of P(x).
Here \forall is called the universal quantifier.
\forall P(x) is read as "for all x P(x)". 
  • Ejemplo 1: Sea P(x)el enunciado “ x + 2 > x“. ¿ Cuál es el valor de verdad del enunciado \forall xP(x)?
    Solución: Como x+2es mayor que xpara cualquier número real, entonces P(x) \equiv Tpara todo xo \forall xP(x) \equiv T.

2. Cuantificación existencial: algunas declaraciones matemáticas afirman que hay un elemento con una determinada propiedad. Tales declaraciones se expresan mediante la cuantificación existencial. La cuantificación existencial se puede usar para formar una proposición que es verdadera si y solo si P(x)es verdadera para al menos un valor de xen el dominio.

Formally,
The existential quantification of P(x) is the statement
"There exists an element x in the domain such that P(x)"

The notation \exists P(x) denotes the existential quantification of P(x).
Here \exists is called the existential quantifier. 
\exists P(x) is read as "There is atleast one such x such that P(x)". 
  • Ejemplo : Sea P(x)el enunciado “ x> 5″. ¿ Cuál es el valor de verdad del enunciado \exists xP(x)?
    Solución:  P(x) es verdadera para todos los números reales mayores que 5 y falsa para todos los números reales menores que 5. Entonces \exists xP(x) \equiv T.

Resumir,

 \begin{tabular}{||c||c||c||} \hline Statement & When True? & When False? \\ \hline \hline \forall P(x) & P(x) is\:true\:for\:all\:x & There\:is\:an\:x\:for\:which\:P(x)\:is\:false \\ \hline \exists P(x) & There\:is\:an\:x\:for\:which\:P(x)\:is\:true & P(x) is\:false\:for\:all\:x \\ \hline \end{tabular} 

Ahora, si tratamos de convertir la declaración, dada al principio de este artículo, en una declaración matemática utilizando la lógica de predicados, obtendríamos algo como:

 \forall P(x) \leftrightarrow Q(x) \\
Here, P(x) is the statement "x is 18 years or older and,
Q(x) is the statement "x is eligible to vote".

Tenga en cuenta que la declaración dada no se menciona como bicondicional y, sin embargo, usamos uno. Esto se debe a que el lenguaje natural a veces es ambiguo y hemos hecho una suposición. Se hizo esta suposición ya que es cierto que una persona puede votar si y solo si tiene 18 años o más. Consulte Introducción a la lógica proposicional para obtener más explicaciones.

Otros cuantificadores:
aunque los cuantificadores universales y existenciales son los más importantes en Matemáticas e Informática, no son los únicos. De hecho, no hay limitación en el número de cuantificadores diferentes que se pueden definir, como “exactamente dos”, “no hay más de tres”, “hay al menos 10”, etc.
De todos los otros cuantificadores posibles, el que se ve con más frecuencia es el cuantificador de unicidad , denotado por \exists !.

The notation \exists !xP(x) states "There exists a unique x such that P(x) is true".

Cuantificadores con dominios restringidos
Como sabemos, los cuantificadores no tienen sentido si las variables que unen no tienen un dominio. La siguiente notación abreviada se usa para restringir el dominio de las variables-
\forall x> 0, x^2> 0.
La declaración anterior restringe el dominio de x, y es una forma abreviada de escribir otra proposición, que dice x > 0, en la declaración.
Si tratamos de reescribir esta declaración usando una implicación, obtendríamos-
\forall x (x> 0\: \rightarrow \: x^2>  0)
De manera similar, una declaración que usa el cuantificador existencial puede reformularse usando la conjunción entre la proposición que restringe el dominio y el predicado real.

  1. La restricción de la cuantificación universal es lo mismo que la cuantificación universal de una declaración condicional.
  2. La restricción de una cuantificación existencial es lo mismo que la cuantificación existencial de la conjunción.

Definiciones a tener en cuenta:

1. Variables vinculantes: una variable cuya ocurrencia está limitada por un cuantificador se denomina
variable vinculada . Las variables que no están limitadas por ningún cuantificador se denominan variables libres .
2. Alcance: la parte de la expresión lógica a la que se aplica un cuantificador se denomina
alcance del cuantificador.

Este tema se ha tratado en dos partes. La segunda parte de este tema se explica en otro artículo – Predicados y cuantificadores – Conjunto 2

Referencias –
Lógica de primer orden –
Cuantificadores de Wikipedia –
Matemáticas discretas de Wikipedia y sus aplicaciones, por Kenneth H Rosen

Este artículo es una contribución de Chirag Manwani . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@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

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *