4 Definicion de formula

Definition 4.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^{*}.

Example 4.2.

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 }.\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\}

Example 4.3.

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⇒w⁢v∈Lw\in L,v\in L\Rightarrow wv\in L (cerrado por concatenacion).

  3. 3.
    ​

    w∈L⇒w⁢1∈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).

Definition 4.4 (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 )
Definition 4.5.

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}.

Remark 4.6.

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

Remark 4.7.

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\}