Logica formal

Lógica Formal (Curso 0607)
1. Lenguajes de Primer Orden
a) Símbolos no lógicos: Símbolos de función 0-aria (constantes): a, e, ... Símbolos de predicado 0-ario (proposiciones): p,q, ... b) Símbolos lógicos: Símbolos de variable: x,y,z, ... Símbolos de cuantificadores: ∃ Símbolos de conectivas: v , ¬ Símbolo de igualdad: =

(versión 1/07)

Símbolos de función con n argumentos: f, g, h, ...Símbolos de predicado con n argumentos: p, q, r ..

(dependiendo de la bibliografía, el predicado de igualdad (=) puede no estar incluido entre los símbolos lógicos y las variables pueden no considerarse símbolos lógicos)

Definición de término
1. Todo símbolo de constante es un término 2. Todo símbolo de variable es un término 3. Si a1, ..., an son términos y f es un símbolo de función n-ariaentonces f(a1, ..., an) es un término 4. No hay más términos que los definidos por los puntos anteriores.

Definición de fórmula
1. Si p es un símbolo de predicado n-ario y a1, ..., an son términos entonces p(a1, ..., an) es una fórmula, denominada fórmula atómica, (a= b) es una fórmula atómica. (si p es 0-ario entonces es una proposición) 2. Si F es una fórmula entonces (¬F) es una fórmula 3.Si F y G son fórmulas entonces (F v G), (F ∧ G), (F → G) (F ↔ G)∧∨→↔son una fórmulas 4. Si F es una fórmula entonces (∃x F) (∀x F) son una fórmulas. 5. No hay más fórmulas que las definidas por los puntos anteriores. Un lenguaje de Primer Orden puede construirse con dos conectivas y con un cuantificador (lenguaje mínimo), pero para mayor expresividad suelen utilizarse las cinco conectivas de lalógica clásica y los dos cuantificadores. A partir de un conjunto mínimo { ¬, v , ∃ }, se definen como abreviaciones: Implicación: (A → B) abreviatura de (¬ A ∨ B) Conjunción: (A ∧ B) abreviatura de (¬ ( ¬A ∨ ¬B)) Doble implicación: (A ↔ B) abreviatura de ((A → B) ∧ (B → A)) Cuantificador Universal: ∀x F abreviatura de (¬ (∃x (¬ F))) Para evitar el abuso de paréntesis se asume por convenio lasiguiente prioridad entre conectivas y cuantificadores: nivel 1: ¬, ∃, ∀, nivel 2: ∨, ∧, nivel 3: →, ↔

Definiciones
Las subfórmulas de una fórmula son ella misma o cualquier subexpresión que sea una fórmula. Los subtérminos de un término son él mismo o cualquier subexpresión que sea un término. La longitud de una fórmula (o de un término) es el número total de símbolos que aparecen en ella (sin teneren cuenta los símbolos de puntuación, ni los paréntesis). El tamaño de una fórmula es el número de símbolos lógicos que contiene (salvo las variables). El ámbito de un cuantificador en una fórmula, es la subfórmula a la que afecta (entre paréntesis, salvo si es atómica). Se llama ocurrencia de una variable a cada una de sus apariciones en una fórmula. Una variable x es ligada en una fórmula siaparece en la subfórmula B de una fórmula de la forma ∃x B (aparece en el ámbito de un cuantificador). Es una variable libre en otro caso.

Definición
Una variable x libre en la fórmula A, es sustituible por el término t si para toda variable z que aparezca en el término t se tiene que ninguna subexpresión de A de la forma ∃z B contiene a x. Ana García Serrano (Curso 0607)

NOTACIÓN
∃x F esuna fórmula, con o sin apariciones libres de x en F. Con la notación ∃xF(x) se indica a la fórmula cuantificación existencial de una fórmula en la que al menos aparece una ocurrencia libre de la variable x. Sea A un esquema de fórmula, x una variable y t un término. Ax[t] denota la formula obtenida a partir de A sustituyendo cada ocurrencia libre de la variable x por el término t. Análogamentesx[t] para cualquier término (s). Ax1, ..., xn[a1, ..., an] denota a la fórmula obtenida al sustituir cada aparición de las variables libres (todas distintas) x1, .. xn por los términos a1, ..., an.

2. Semántica de una Teoría de Primer Orden
Definición
El significado de las conectivas se define mediante la tabla de verdad (o función significado (sig)).

Definición
Una estructura M para un...