20 Alfabeto y reglas de formacion de formulas

Definición 20.1 (Alfabeto de la logica de predicados).

A≔{p1,p2,p3,…}∪{⊤,⟂,¬,∨,∧,→,↔,(,)}∪{c1,c2,…}∪{P1,P2,…}∪{x1,x2,…}∪{=}∪{,}\displaystyle A\coloneqq\{p_{1},p_{2},p_{3},\ldots\}\cup\{\top,\perp,\neg,\vee% ,\wedge,\rightarrow,\leftrightarrow,(,)\}\cup\{c_{1},c_{2},\ldots\}\cup\{P_{1}% ,P_{2},\ldots\}\cup\{x_{1},x_{2},\ldots\}\cup\{=\}\cup\{,\}.

Nombre Símbolo Tipo Aridad
Constante ci\displaystyle c_{i} Función 0
Función de aridad n≥1\displaystyle n\geq 1 fi\displaystyle f_{i} n≥1\displaystyle n\geq 1
Proposición atómica pi\displaystyle p_{i} Predicado 0
Predicado de aridad n≥1\displaystyle n\geq 1 Pi\displaystyle P_{i} n≥1\displaystyle n\geq 1
Variable xi\displaystyle x_{i} Variable -
Nombre Símbolo Tipo Aridad
Verdadero ⊤\displaystyle\top Conectiva 0
Falso ⟂\displaystyle\perp
Negación ¬\displaystyle\neg 1
Conjunción ∧\displaystyle\wedge 2
Disyunción ∨\displaystyle\vee
Implicación →\displaystyle\rightarrow
Doble implicación ↔\displaystyle\leftrightarrow
Igualdad = Igualdad 2
Para todo ∀\displaystyle\forall Cuantificador -
Existe ∃\displaystyle\exists
Paréntesis izquierdo ( Auxiliar -
Paréntesis derecho )
Coma ,

Vamos a definir de manera recursiva dos lenguajes sobre A\displaystyle A:

  •  
    ​

    El conjunto 𝒯\displaystyle\mathcal{{T}} de los terminos de la logica de predicados (que representaran elementos del dominio).

  •  
    ​

    El conjunto ℱ1\displaystyle\mathcal{{F}}_{1} de las formulas de la logica de predicados (que representaran enunciados).

Definición 20.2 (Recursiva de termino).
  1. 1.
    ​

    Terminos atomicos:

    •  
      ​

      Si c\displaystyle c es un simbolo constante ⇒c\displaystyle\Rightarrow c es un termino.

    •  
      ​

      Si x\displaystyle x es un simbolo de variable ⇒x\displaystyle\Rightarrow x es un termino.

  2. 2.
    ​

    Si f\displaystyle f es un simbolo de funcion de aridad n≥1\displaystyle n\geq 1 y t1,t2,…,tn\displaystyle t_{1},t_{2},\ldots,t_{n} son terminos entonces f⁢(t1,t2,…,tn)\displaystyle f(t_{1},t_{2},\ldots,t_{n}) es un termino.

  3. 3.
    ​

    Cualquier palabra que no se pueda obtener con la aplicacion de las reglas anteriores no es un termino.

Definición 20.3 (Recursiva de formula de la logica de primer orden).
  1. 1.
    ​

    Formulas atomicas:

    •  
      ​

      Si p\displaystyle p es un simbolo de proposicion atomica ⇒p\displaystyle\Rightarrow p es una formula.

    •  
      ​

      ⊤\displaystyle\top es una formula.

    •  
      ​

      ⟂\displaystyle\perp es una formula.

    •  
      ​

      Si P\displaystyle P es un simbolo de predicado de aridad n≥1\displaystyle n\geq 1 y t1,t2,…,tn\displaystyle t_{1},t_{2},\ldots,t_{n} son terminos, entonces P(t1,t2,…,tn\displaystyle P(t_{1},t_{2},\ldots,t_{n} es una formula.

    •  
      ​

      Si t1,t2\displaystyle t_{1},t_{2} son terminos, entonces (t1=t2)\displaystyle(t_{1}=t_{2}) es una formula.

  2. 2.
    ​

    Si φ\displaystyle\varphi es una formula ⇒¬⁢φ\displaystyle\Rightarrow\neg\varphi es una formula.

  3. 3.
    ​

    Si φ,ψ\displaystyle\varphi,\psi son formulas y ∘∈{∧,∨,→,↔}\displaystyle\circ\in\{\wedge,\vee,\rightarrow,\leftrightarrow\} entonces (φ∘ψ)\displaystyle(\varphi\circ\psi) es una formula.

  4. 4.
    ​

    Si x\displaystyle x es un simbolo de variable y φ\displaystyle\varphi es una formula, entonces:

    •  
      ​

      ∀x⁢φ\displaystyle\forall x\varphi es una formula.

    •  
      ​

      ∃x⁢φ\displaystyle\exists x\varphi es una formula.

  5. 5.
    ​

    Cualquier palabra que no se pueda obtener con la aplicacion de las reglas anteriores no esu na formula.

Observación.

Se aplican los mismos criterios para abreviar formulas mediante eliminacion de parentesis que vimos en logica proposicional.