4 Definicion de formula

Definición II.1 (Lenguaje, informal).
  • ​

    Llamamos alfabeto a un conjunto AA, cuyos elementos se denominan simbolos.

  • ​

    Una palabra sobre AA es una sucesion finita de simbolos de AA, escritos uno a continuacion de otro.

  • ​

    El conjunto de todas las palabras sobre AA se denota como A∗A^{*}.

  • ​

    Un lenguaje sobre AA es un subconjunto L⊆A∗L\subseteq A^{*}.

Ejemplo II.1.

A≔{letras, mayusculas o minusculas, del alfabeto}A\coloneqq\left\{\text{letras, mayusculas o minusculas, del alfabeto}\right\}

L≔{palabras que aparecen en el diccionario de la RAE .}L\coloneqq\left\{\text{palabras que aparecen en el diccionario de la RAE }% \mathchar 46\relax\right\}

A≔{0,1}A\coloneqq\left\{0,1\right\}

L1≔A∗L_{1}\coloneqq A^{*} (todas las cadenas finitas de bits).

L2≔{x∈A∗∣x consta exactamente de 8 simbolos }L_{2}\coloneqq\left\{x\in A^{*}\mid x\text{ consta exactamente de 8 simbolos }\right\}

Ejemplo II.2.

A≔{0,1}A\coloneqq\left\{0,1\right\}. Reglas que definen LL:

  1. 1.
    ​

    00∈L00\in L.

  2. 2.
    ​

    w∈L,v∈L⇒wv∈Lw\in L,v\in L\Rightarrow wv\in L (cerrado por concatenacion).

  3. 3.
    ​

    w∈L⇒w1∈Lw\in L\Rightarrow w1\in L

  4. 4.
    ​

    Cualquier palabra que no se pueda obtener con la aplicacion de las reglas anteriores, no esta en LL.

Se puede demostrar que LL consiste en todas las cadenas de bits que comienzan por 0000 y que no tienen una cantidad impar de ceros consecutivos.

Ejemplos de palabras que estan en el lenguaje LL: 00∈L(1),0000∈L(2),001∈L(3),00100∈L(2)00\in L(1),0000\in L(2),001\in L(3),00100\in L(2).

Definición II.2 (Alfabeto de la logica proposicional).

A≔{p1,p2,p3,…}∪{⊤,⟂,¬,∧,∨,→,↔,(,)}A\coloneqq\left\{p_{1},p_{2},p_{3},\ldots\right\}\cup\left\{\top,\perp,\neg,% \wedge,\vee,\rightarrow,\leftrightarrow,(,)\right\}

Nombre Simbolo Tipo Aridad
Proposición atómica pip_{i} Proposición atómica -
Verdadero ⊤\top Conectiva 0
Falso ⟂\perp
Negación ¬\neg 1
Conjunción ∨\vee 2
Disyunción ∧\wedge
Implicación →\rightarrow
Doble implicación ↔\leftrightarrow
Paréntesis izquierdo ( Auxiliar -
Paréntesis derecho )
Definición II.3.

Vamos a definir el lenguaje ℱ︀0⊆A∗\mathcal{{F}}_{0}\subseteq A^{*} de las formulas de la logica proposicional mediante las siguientes reglas de formacion:

  1. 1.
    ​

    Formulas atomicas:

    • ​

      Si pp es un simbolo de proposicion atomica ⟹\implies p∈ℱ︀0p\in\mathcal{{F}}_{0}

    • ​

      ⊤∈ℱ︀0\top\in\mathcal{{F}}_{0}

    • ​

      ⟂∈ℱ︀0\perp\in\mathcal{{F}}_{0}

  2. 2.
    ​

    Si φ∈ℱ︀0⇒¬φ∈ℱ︀0\varphi\in\mathcal{{F}}_{0}\Rightarrow\neg\varphi\in\mathcal{{F}}_{0}.

  3. 3.
    ​

    Si φ,ψ∈ℱ︀0\varphi,\psi\in\mathcal{{F}}_{0} entonces:

    • ​

      (φ∧ψ)∈ℱ︀0(\varphi\wedge\psi)\in\mathcal{{F}}_{0}

    • ​

      (φ∨ψ)∈ℱ︀0(\varphi\vee\psi)\in\mathcal{{F}}_{0}

    • ​

      (φ→ψ)∈ℱ︀0(\varphi\rightarrow\psi)\in\mathcal{{F}}_{0}

    • ​

      (φ↔ψ)∈ℱ︀0(\varphi\leftrightarrow\psi)\in\mathcal{{F}}_{0}

  4. 4.
    ​

    Cualquier palabra que no se pueda obtener con la aplicacion de las reglas anteriores, no esta en ℱ︀0\mathcal{{F}}_{0}.

Observación II.1.

Con estas reglas de formacion estrictas que hemos dado en la definicion, p∧qp\wedge q no es una formula.

Observación II.2.

Por economia de escritura, muchas veces escribiremos la tercera regla de la definicion anterior como:

  • ​

    Si φ,ψ∈ℱ︀0\varphi,\psi\in\mathcal{{F}}_{0} entonces (φ∘ψ)∈ℱ︀0(\varphi\circ\psi)\in\mathcal{{F}}_{0}, donde ∘∈{∧,∨,→,↔}\circ\in\left\{\wedge,\vee,\rightarrow,\leftrightarrow\right\}