Predicados y Cuantificadores Flashcards
¿Qué es la Lógica de Predicados o Lógica de Primer Orden (POL o FOL)?
Es una extensión de Lógica Proposicional.
Las equivalencias y reglas de inferencia vistas en la lógica proposicional siguen siendo válidas en:
la lógica de predicados.
La diferencia entre la lógica proposicional y la lógica de predicados:
El concepto de predicado y el de cuantificador.
Un predicado es:
una sentencia declarativa que contiene un número definido de variables y que se vuelve en una proposición cuando las variables son sustituidas por valores.
El dominio de un predicado es
el conjunto de todos los valores que pueden ser sustituidos en las variables.
Sea Q(x) un predicado y D el dominio de Q. Una afirmación universal es una declaración de la forma:
∀x ∈ D,Q(x)
Una afirmación universal es definida a ser verdadera si y sólo si:
Q(x) es verdadera para todo elemento x que está en el dominio D.
La afirmación ∀x ∈ D,Q(x) es falsa si y sólo si:
Q(x) es falsa al menos para un elemento x del dominio.
Un elemento x para el cual Q(x) es falsa se llama:
contraejemplo a la afirmación universal.
∀ se traduce en una conjunción. Si por ejemplo D = {1, a, e} entonces
∀ x ∈ D, Q(x) ≡ Q(1) ∧ Q(a) ∧ Q(e)
Sea Q(x) un predicado con dominio D. Una afirmación existencial es una declaración de la forma:
∃x ∈ D, Q(x)
Una afirmación existencial es definida a ser verdadera si y sólo si:
existe en el dominio D al menos un valor de x para el cual Q(x) es verdadera.
La afirmación ∃x ∈ D, Q(x) es falsa si y sólo si:
para toda x en el dominio, Q(x) es falsa.
∃ se traduce en una disyunción: Si por ejemplo D = {1, a, e} entonces
∃ x ∈ D, Q(x) ≡ Q(1) ∨ Q(a) ∨ Q(e)
La negación de una declaración universal de la forma ∀ x ∈ D, Q(x) ocurre cuando:
no es cierto que para todo x de D, P(x) es verdadera. Es decir, cuando existe al menos un elemento de D para el cual P es falsa.
La negación de una declaración universal es la proposición:
∃ x ∈ D, ¬Q(x)
La equivalencia de ∃ x ∈ D, ¬Q(x)
es:
¬ (∀ x ∈ D, Q(x)) ≡ ∃ x ∈ D, ¬Q(x)
La negación de una declaración existencial de la forma ∃ x ∈ D, Q(x )ocurre cuando:
no es cierto que exista un elemento de D para el cual P es cierta. Es decir, cuando P es falsa para todos los elemento de D.
La negación de una declaración existencial es la proposición:
∀ x ∈ D, ¬Q(x)
La equivalencia de ∀ x ∈ D, ¬Q(x) es:
¬ (∃ x ∈ D, Q(x)) ≡ ∀ x ∈ D, ¬Q(x)
La CONTRAPOSITIVA de una declaración de la forma ∀ x ∈ D, si P(x) entonces Q(x). es la afirmación:
∀ x ∈ D, si ¬Q(x) entonces ¬P(x).
La RECÍPROCA de una declaración de la forma ∀ x ∈ D, si P(x) entonces Q(x). es la afirmación:
∀ x ∈ D, si Q(x) entonces P(x).
La INVERSA de una declaración de la forma ∀ x ∈ D, si P(x) entonces Q(x). es la afirmación:
∀ x ∈ D, si ¬P(x) entonces ¬Q(x).
∀x ∈ D, r(x) es CONDICIÓN SUFICIENTE para s(x)
significa:
∀x ∈ D, r(x) → s(x)
∀x ∈ D, r(x) es CONDICIÓN NECESARIA para s(x)
significa:
∀x ∈ D, s(x) → r(x)
∀x ∈ D, r(x) SÓLO SI s(x) significa:
∀x ∈ D, r(x) → s(x)
En Lógica las afirmaciones sólo pueden ser:
verdaderas o falsas.
En Lógica las afirmaciones sólo pueden ser verdaderas o falsas. Su negación por consiguiente solo puede ser:
falsa o verdadera; contrariamente a lo que es la afirmación.
Una afirmación es VERDADERA cuando su negación es:
FALSA
Este hecho simple es la base de la prueba por vacuidad:
Una afirmación es verdadera cuando su negación es falsa.
Una afirmación universal es verdadera si:
no existe ejemplo que haga verdadera su negación.
∀x ∈ D, Q(x) es verdadera si:
∃x ∈ D, ¬ Q(x) es falsa.
Las expresiones con varios cuantificadores son muy comunes. Las principales dificultades se presentan en expresiones donde:
aparecen cuantificadores diferentes.
∀x∃y
Si se quiere establecer la verdad de la
declaración:
Para cada x en A, existe un y en B tal que es verdadero P(x, y)
∀x∃y
Lo que debe hacerse es:
Permitirle a cualquiera escoger un elemento x cualquiera de A y probar que para tal x existe un elemento y de B para el cual P(x, y) es verdadero.
La afirmación ∀x ∃y, P(x, y) es falsa si:
existe una x para el cual sin importar cual sea y, P(x, y) es falso.
∃x∀y
Si se quiere establecer la verdad de la
declaración:
Existe una x en A tal que para cualquier y en B se tiene verdadero P(x, y)
∃x∀y
Lo que debe hacerse es:
Encontrar un elemento de A tal que para cualquiera que sea el elemento y de B se tiene que P(x, y) es verdadero.
La afirmación ∃x ∀y, P(x, y) es falsa si:
para toda x hay un valor de y para el cual P(x, y) es falso.
∀x∀y, P(x, y) ≡ ∀y∀x, P(x, y)
∃x∃y, P(x, y) ≡ ∃y∃x, P(x, y)
Son hechos en la Lógica de Predicados
¡Ojo!
Cuidado con el orden de los cuantificadores en:
∀x∃y, P(x,y)
∃y∀x, P(x,y)
