2.6: Resumen de la lógica de primer orden

16. Resumen de la lógica de primer orden

16.1 Elementos de la lengua

• Los términos simbólicos son nombres, nombres indefinidos, variables o términos arbitrarios.
  • Nombres: a, b, c, d, e...
  • Nombres indefinidos: p, q, r...
  • Variables: x, y, z...
  • Términos arbitrarios: x ′, y ′, z ′...
• Cada predicado tiene una arity, que es el número de términos simbólicos requeridos por ese predicado para formar una fórmula bien formada. Los predicados de nuestro lenguaje son: F, G, H, I...
• Cada función tiene una arity, que es el número de términos simbólicos que requiere la función para que forme un término simbólico. Las funciones de nuestro lenguaje son: f, g, h, i...
• Hay dos cuantificadores.
  • α, el cuantificador universal.
  • , el cuantificador existencial.
• Los conectivos son los mismos que los de la lógica proposicional.

16.2 Sintaxis del lenguaje

• Una función arity n combinada con n términos simbólicos es un término simbólico.
• Un predicado arity n combinado con n términos simbólicos es una fórmula bien formada.
• Si Φ y ψ son fórmulas bien formadas, entonces las siguientes también son fórmulas bien formadas. (Y si Φ y ψ son oraciones, entonces las siguientes también son oraciones).
  • ¬ Φ
  • (Φ → ψ)
  • (Φ ^ ψ)
  • (Φ v ψ)
  • (Φ ↔ ψ)
• Escribimos Φ (α) para significar Φ es una fórmula bien formada en la que aparece el término simbólico α.
• Si no hay cuantificadores en Φ (x) entonces x es una variable libre en Φ. (Los nombres nunca se describen como libres.) Si para esa fórmula Φ escribimos µ xΦ (x) o xΦ (x), decimos que x ahora está enlazado en Φ. Una variable enlazada no es libre.
• Una fórmula bien formada sin variables libres es una oración.

16.3 Semántica de la lengua

• La semántica de nombres, predicados y cuantificadores seguirá siendo intuitiva para nosotros. Se requiere lógica avanzada (con teoría de conjuntos) para hacerlos más precisos. Nosotros decimos:
  • El dominio del discurso es la colección de objetos de los que trata nuestro lenguaje.
  • Un nombre se refiere exactamente a un objeto de nuestro dominio del discurso.
  • Un predicado de arity n describe una propiedad o relación de n objetos.
  • A x Φ (x) significa que cualquier objeto en nuestro dominio del discurso tiene propiedad Φ.
  • x Φ (x) significa que al menos un objeto en nuestro dominio del discurso tiene propiedad Φ.
• Si Φ y ψ son oraciones, entonces los significados de los conectivos están completamente dados por sus tablas de verdad. Estas tablas de verdad que definen semánticas son:

Φ	¬Φ
T	F
F	T

Φ	ψ	(Φ → ψ)
T	T	T
T	F	F
F	T	T
F	F	T

Φ	ψ	(Φ ^ ψ)
T	T	T
T	F	F
F	T	F
F	F	F

Φ	ψ	(Φ v ψ)
T	T	T
T	F	T
F	T	T
F	F	F

Φ	ψ	(Φ ↔ ψ)
T	T	T
T	F	F
F	T	F
F	F	T

• Cada oración debe ser verdadera o falsa, nunca ambas, nunca tampoco.
• Una frase que debe ser verdadera es lógicamente cierta. (Sentencias de nuestra lógica que tienen la misma forma que las tautologías de la lógica proposicional que todavía podemos llamar “tautologías”. No obstante, hay algunas frases de la lógica de primer orden que deben ser ciertas pero que no tienen la forma de tautologías de la lógica proposicional. Los ejemplos incluirían [alpha] x (F x → F x) y [F x] x (F x v ¬ F x).)
• Una sentencia que debe ser falsa es una sentencia contradictoria.
• Una frase que podría ser verdadera o que podría ser falsa es una oración contingente.
• Dos oraciones Φ y ψ son “equivalentes” o “lógicamente equivalentes” cuando (Φ ↔ ψ) es un teorema.

16.4 Razonamiento con el Lenguaje

• Un argumento es una lista ordenada de oraciones, una frase de la que llamamos la “conclusión” y las otras de las que llamamos las “premisas”.
• Un argumento válido es un argumento en el que: necesariamente, si las premisas son verdaderas, entonces la conclusión es verdadera.
• Un argumento sólido es un argumento válido con verdaderas premisas.
• Las reglas de inferencia nos permiten anotar una oración que debe ser cierta, asumiendo que ciertas otras oraciones deben ser ciertas. Decimos que la oración se deriva de esas otras oraciones que utilizan la regla de inferencia.
• Esquemáticamente, podemos escribir las reglas de inferencia de la siguiente manera (piense en estas como diciendo, si ha escrito la (s) oración (s) encima de la línea, entonces puede anotar la oración debajo de la línea; también, el orden de las oraciones por encima de la línea, si hay varias, no importa):

Modus ponens	Modus tollens	Doble negación	Doble negación
(Φ → ψ) Φ _____ ψ	(Φ → ψ) ¬ψ _____ ¬Φ	Φ _____ ¬¬Φ	¬¬Φ _____ Φ
Adición	Adición	Modus tollendo ponens	Modus tollendo ponens
Φ _____ (Φ v ψ)	ψ _____ (Φ v ψ)	(Φ v ψ) ¬Φ _____ ψ	(Φ v ψ) ¬ψ _____ Φ
Adjunción	Simplificación	Simplificación	Bicondición
Φ ψ _____ (Φ ^ ψ)	(Φ ^ ψ) _____ Φ	(Φ ^ ψ) _____ ψ	(Φ → ψ) (ψ → Φ) _____ (Φ ↔ ψ)
Equivalencia	Equivalencia	Equivalencia	Equivalencia
(Φ ↔ ψ) Φ _____ ψ	(Φ ↔ ψ) ψ _____ Φ	(Φ ↔ ψ) ¬Φ _____ ¬ψ	(Φ ↔ ψ) ¬ψ _____ ¬Φ
Repetir	Instanciación universal	Generalización existencial	Instanciación existencial
Φ _____ Φ	αΦ (α) _____ Φ (β)	Φ (β) _____ αΦ (α)	αΦ (α) _____ Φ (χ)
	donde β es cualquier término simbólico	donde β es cualquier término simbólico	donde χ es un nombre indefinido que no aparece arriba en ninguna prueba abierta

• Una prueba (o derivación) es un método sintáctico para mostrar que un argumento es válido. Nuestro sistema cuenta con cuatro tipos de prueba (o derivación): directa, condicional, indirecta y universal.
• Una prueba directa (o derivación directa) es una lista ordenada de oraciones en la que cada oración es una premisa o se deriva de líneas anteriores usando una regla de inferencia. La última línea de la prueba es la conclusión.
• Una prueba condicional (o derivación condicional) es una lista ordenada de oraciones en la que cada oración es una premisa, es la suposición especial para la derivación condicional, o se deriva de líneas anteriores usando una regla de inferencia. Si la suposición para la derivación condicional es Φ, y derivamos como algún paso en la prueba ψ, entonces podemos escribir después de esto (Φ → ψ) como nuestra conclusión.
• Una prueba indirecta (o derivación indirecta, y también conocida como reductio ad absurdum) es: una lista ordenada de oraciones en la que cada oración es 1) una premisa, 2) la suposición especial para la derivación indirecta (también llamada a veces la “suposición para reductio”), o 3) derivada de anteriores líneas usando una regla de inferencia. Si nuestra suposición para la derivación indirecta es ¬ Φ, y derivamos como algún paso en la prueba ψ y también como algún paso de nuestra prueba ¬ ψ, entonces concluimos que Φ.
• Una prueba universal (o derivación universal) es una lista ordenada de oraciones en la que cada oración es una premisa o se deriva de líneas anteriores (no dentro de una subprueba completada) usando una regla de inferencia. Si somos capaces de probar Φ (x ′) donde x ′ no aparece libre en ninguna línea por encima de la derivación universal, entonces concluimos que α x Φ (x).

• La forma esquemática de los métodos de prueba directa, condicional e indirecta sigue siendo la misma que para la lógica proposicional. Podemos usar barras Fitch para escribir este cuarto esquema de prueba de la siguiente manera:

\ [\ fitchctx {\ boxedsubproof [] {\ alpha '} {} {} {\ elipsesline\\ pline {\ phi (\ alpha')}}\ pline {\ lall\ alpha\ phi (\ alpha)}}\]” class="ql-img-ecuación presentada-quicklatex-auto-formato” height="142" title="Rendido por Quicklatex.com” widthex.com” widthex.com ="71" src=” https://human.libretexts.org/@api/deki/files/155767/ Images/quicklatex.com-A42fc18dd775dee41fd61f76123cbcd1_l3.png” />

• Una frase que podemos probar sin premisas es un teorema.

16.5 Algunos consejos sobre traducciones usando cuantificadores

La mayoría de las frases en inglés que queremos traducir a nuestra lógica de primer orden son de las siguientes formas.

Todo es Φ f x Φ (x)	Algo es Φ x Φ (x)
Nada es Φ ¬x Φ (x)	Algo no es Φ x ¬ Φ (x)
Todos Φ son ψ p x (Φ (x) → ψ (x))	Algunos Φ son ψ x (Φ (x) ^ Y (x))
No Φ son ψ ¬x (Φ (x) ^ ψ (x))	Algunos Φ no son ψ x (Φ (x) ^ ¬ ψ (x))
Solo Φ son ψ p x (ψ (x) → Φ (x))	Todos y solo Φ son ψ µ x (Φ (x) ↔ ψ (x))