Matemáticas discretas - Lógica de predicados
Predicate Logic trata con predicados, que son proposiciones que contienen variables.
Lógica de predicados - Definición
Un predicado es una expresión de una o más variables definidas en algún dominio específico. Un predicado con variables puede convertirse en una proposición asignando un valor a la variable o cuantificándola.
Los siguientes son algunos ejemplos de predicados:
- Deje E (x, y) denotar "x = y"
- Sea X (a, b, c) "a + b + c = 0"
- Sea M (x, y) "x está casada con y"
Fórmula bien formada
La fórmula bien formada (wff) es un predicado que contiene cualquiera de los siguientes:
Todas las constantes proposicionales y variables proposicionales son wffs
Si x es una variable e Y es una wff, $ \ forall x Y $ y $ \ existe x Y $ también son wff
El valor de verdad y los valores falsos son wffs
Cada fórmula atómica es un wff
Todos los conectivos que conectan wffs son wffs
Cuantificadores
La variable de predicados se cuantifica mediante cuantificadores. Hay dos tipos de cuantificadores en la lógica de predicados: el cuantificador universal y el cuantificador existencial.
Cuantificador universal
El cuantificador universal establece que las declaraciones dentro de su alcance son verdaderas para cada valor de la variable específica. Se denota con el símbolo $ \ forall $.
$ \ forall x P (x) $ se lee como para cada valor de x, P (x) es verdadero.
Example - "El hombre es mortal" se puede transformar en la forma proposicional $ \ para todos x P (x) $ donde P (x) es el predicado que denota que x es mortal y el universo del discurso son todos los hombres.
Cuantificador existencial
El cuantificador existencial establece que las afirmaciones dentro de su alcance son verdaderas para algunos valores de la variable específica. Se denota con el símbolo $ \ existe $.
$ \ existe x P (x) $ se lee como para algunos valores de x, P (x) es verdadero.
Example - "Algunas personas son deshonestas" se puede transformar en la forma proposicional $ \ existe x P (x) $ donde P (x) es el predicado que denota que x es deshonesto y el universo del discurso son algunas personas.
Cuantificadores anidados
Si usamos un cuantificador que aparece dentro del alcance de otro cuantificador, se llama cuantificador anidado.
Example
$ \ para todos \ a \: \ existe b \: P (x, y) $ donde $ P (a, b) $ denota $ a + b = 0 $
$ \ forall \ a \: \ forall \: b \: \ forall \: c \: P (a, b, c) $ donde $ P (a, b) $ denota $ a + (b + c) = ( a + b) + c $
Note - $ \ para todos \: a \: \ existe b \: P (x, y) \ ne \ existe a \: \ para todos b \: P (x, y) $