Lógica Proposicional - Sintaxis

Contenido
Introducción .............................................................................................................................. 2
Noción de Lenguaje Formal ...................................................................................................... 3
Lenguaje Formal para Lógica Proposicional .............................................................................. 5
Símbolos ................................................................................................................................. 5
Reglas de sintaxis ................................................................................................................... 6
Árbol de sintaxis ..................................................................................................................... 7
Precedencia y Asociatividad .................................................................................................. 8
La sintaxis de LP en Haskell .................................................................................................... 9
Recursión en LP .................................................................................................................... 10
Sustitución en fórmulas ....................................................................................................... 13
Formalización de enunciados .................................................................................................. 14

1
Introducción
La Lógica Proposicional (LP) es una rama de la lógica que estudia las proposiciones y las
relaciones entre proposiciones, incluyendo la construcción de argumentos formados a partir
de estas.

Una proposición es el contenido lógico de una oración declarativa: esto es cualquier oración
que sea susceptible de considerarse verdadera o falsa. Por ejemplo, las oraciones

• Está lloviendo.
• It’s raining.

están expresadas en diferentes lenguajes naturales, Español e Inglés respectivamente.

Ambas son oraciones declarativas porque tienen un valor de verdad, el cual (asumiendo un
contexto) es posible determinar. Sin embargo, ambas oraciones son la misma proposición.

En particular, en LP se consideran solo dos tipos de proposiciones:

1. Proposiciones simples/atómicas
Son las oraciones declarativas más básicas, no se pueden descomponer.
Ejemplo.
• La nieve es blanca.
• 𝑥=5
2. Proposiciones compuestas/moleculares
Son la composición de las proposiciones atómicas (u otras compuestas) mediante
conectivas lógicas.
Ejemplo.
• La nieve es blanca y está lloviendo.
• Si 𝑥 = 5 entonces 2 ≤ 𝑥

En este curso nos adherimos a la visión de la lógica clásica, con esto nos referimos más o
menos a la lógica como fue concebida inicialmente por Aristóteles. Una característica de la
lógica clásica es el uso del Principio(o Ley) del tercero excluido: para cualquier proposición,
la proposición es verdadera o su negación es verdadera. Como consecuencia de este
principio se tiene la posibilidad de demostrar la verdad de una proposición mostrando que
su negación es falsa, lo que se llama una prueba por contradicción (técnica muy explotada
particularmente en Matemáticas).

La aparente auto evidencia de dicho principio ha hecho que sea adoptado sin objeción
durante un gran periodo de la civilización humana, de ahí viene el adjetivo “clásico”.

2
Noción de Lenguaje Formal
El estudio de la Lógica formal se realiza mediante la formulación y análisis de lenguajes
formales que permiten expresar proposiciones y demostraciones. Esto significa que para
estudiar Lógica Proposicional primero vamos a definir un lenguaje formal apropiado para los
componentes de dicha lógica.

Un lenguaje formal se puede pensar como aquellas expresiones que pueden formarse a
partir de ciertos símbolos (y posiblemente otras palabras formadas previamente) de
acuerdo a ciertas reglas específicas.

Definición (Lenguaje Formal). Un lenguaje formal ℒ consta de:

1. Un conjunto de símbolos, llamado alfabeto, que contiene los símbolos admisibles en
el lenguaje.
2. Un conjunto de reglas de sintaxis, llamado gramática, que describe precisamente
como se forman las expresiones válidas del lenguaje a partir de los símbolos del
alfabeto. Dichas expresiones son llamadas fórmulas bien formadas (o simplemente
fórmulas).

Los lenguajes de programación son un ejemplo evidente de lenguaje formal. Un programa

compilador para un lenguaje de programación conoce el alfabeto y reglas de sintaxis de
dicho lenguaje. Cuando el programador intenta compilar un programa, el compilador puede
rechazarlo si tiene símbolos fuera del alfabeto (error léxico) o no respeta las reglas
sintácticas (error sintactico).

Hay más de una manera para definir precisamente las reglas de sintaxis. Nosotros vamos a
usar principalmente una forma de notación BNF (Backus-Naur Form), este es un lenguaje
que a su vez sirve para describir lenguajes formales. También vamos a ver como representar
esto dentro de Haskell usando tipos inductivos.

Ejemplo. El lenguaje ℒ 𝑎𝑏 de palabras formadas por al menos una 𝒂 seguida por el mismo
número de 𝒃’s:
• Alfabeto: {𝒂, 𝒃}
• Gramática (en BNF): 𝛼 ∷= 𝒂𝒃 | 𝒂 𝛼 𝒃

Notar que la gramática presenta dos casos y el segundo es inductivo. Además, 𝛼 no forma
parte del lenguaje que estamos definiendo, usamos letras griegas minúsculas como meta-
variables que representan fórmulas arbitrarias.

No debería de haber ningún desacuerdo en que las expresiones 𝒂𝒃, 𝒂𝒂𝒃𝒃 y 𝒂𝒂𝒂𝒃𝒃𝒃 son
fórmulas de ℒ 𝑎𝑏 , mientras que las expresiones 𝒂, 𝒂𝒄 y 𝒂𝒃𝒃 no lo son.

3
Para cualquier expresión, podemos determinar mecánicamente si es una fórmula del
lenguaje o no, al descomponer la expresión siguiendo los casos posibles. Para hacer esto a
mano resulta más conveniente reescribir la gramática anterior en la siguiente notación de
regla donde además le damos un nombre a cada una:
𝛼
R1 R2
𝒂𝒃 𝒂𝛼𝒃
Podemos pensar en R1 como un caso base (o axioma) de formación, porque no requiere de
ninguna fórmula previa para justificar que 𝒂𝒃 es una fórmula. Por otro lado, R2 es una regla
recursiva de formación, porque requiere una fórmula previa para producir otra nueva.

Ahora podemos hacer una derivación para justificar que, por ejemplo, 𝒂𝒂𝒂𝒃𝒃𝒃 es una
fórmula de ℒ 𝑎𝑏 :

R1
R2 𝒂𝒃
R2 𝒂𝒂𝒃𝒃
𝒂𝒂𝒂𝒃𝒃𝒃

Por otro lado, es fácil ver que no es posible hacer una derivación para 𝒂𝒃𝒃 :

? 𝒃
𝒂𝒃𝒃
En general, estas derivaciones tienen estructura de árbol, aunque en este ejemplo particular
son de estructura lineal.

Observaciones:
• Aunque hay una cantidad infinita de fórmulas en ℒ 𝑎𝑏 , es habitual asumir que
cualquiera de ellas es de tamaño finito. En otras palabras, cualquier fórmula es el
resultado de una aplicación finita de las reglas de formación sintáctica.
• Es conveniente identificar el lenguaje con el conjunto de todas las fórmulas que se
pueden formar a partir de sus reglas.

4
Lenguaje Formal para Lógica Proposicional
Vamos a definir un lenguaje formal ℒ 𝑃𝑅𝑂𝑃 para LP. Hemos dicho que LP distingue solo dos
tipos de proposiciones: (1) atómicas y (2) aquellas compuestas de otras proposiciones
mediante conectivas lógicas.

Símbolos
Tenemos tres clases de símbolos admisibles:
1. Letras proposicionales
Asumimos que disponemos de un conjunto infinito (contable) de letras que serán
usadas para denotar proposiciones atómicas. Decimos que estas son las fórmulas
atómicas.
𝑉𝑎𝑟 = { 𝑝1 , 𝑝2 , 𝑝3 , . . . , 𝑝𝑛 , 𝑝𝑛+1 , … }
Tradicionalmente, y por conveniencia, preferimos siempre que sea posible limitarnos
al uso de las letras 𝑝, 𝑞, 𝑟, 𝑠. Las letras proposicionales son comúnmente llamadas
también variables proposicionales.
2. Conectivas lógicas
Las conectivas lógicas conectan fórmulas permitiendo construir fórmulas
compuestas. A las conectivas consideradas aquí les llamamos primitivas en nuestro
lenguaje: 1
Conectiva Símbolo Lectura “natural”

Negación ¬ ¬𝑝 “no p”

Disyunción ∨ 𝑝∨𝑞 “p o q”

Conjunción ∧ 𝑝∧𝑞 “p y q”

Condicional ⊃ 𝑝⊃𝑞 “si p entonces q”

Bicondicional ↔ 𝑝 ↔ 𝑞 “p si y solo si q”
Decimos que ∨, ∧, ⊃ y ↔ son conectivas binarias mientras que ¬ es una conectiva
unaria.
3. Puntuación
Usamos paréntesis curvos ( y ) como símbolos auxiliares para agrupar fórmulas.

Hasta aquí, podemos decir que el alfabeto de ℒ 𝑃𝑅𝑂𝑃 consiste de los símbolos en:
𝑉𝑎𝑟 ∪ {¬, ∨, ∧, ⊃, ↔, (, )}

1
Podríamos agregar símbolos para otras conectivas, pero con eso no obtendríamos un lenguaje con mayor expresividad.
Con las conectivas que estamos considerando ya tenemos un conjunto adecuado de conectivas, mediante el cual podemos
expresar el resto de las conectivas posibles.

5
Reglas de sintaxis
Las expresiones validas de ℒ 𝑃𝑅𝑂𝑃 son fórmulas lógicas con las cuales representamos
formalmente proposiciones.

Definición (ℒ 𝑃𝑅𝑂𝑃 en BNF).

𝛼, 𝛽 ∷= 𝑝 | (¬ 𝛼) | (𝛼 ∧ 𝛽) | (𝛼 ∨ 𝛽) | (𝛼 ⊃ 𝛽) | (𝛼 ↔ 𝛽)
donde 𝑝 es una letra proposicional cualquiera de 𝑉𝑎𝑟 y 𝛼, 𝛽 denotan fórmulas arbitrarias.

Ejemplo. Las siguientes expresiones son fórmulas de ℒ 𝑃𝑅𝑂𝑃 :

• (𝑝 ∧ 𝑞 )
• (𝑝 ∧ (𝑞 ⊃ (¬ 𝑟)))
• 𝑝
Las siguientes expresiones no son fórmulas de ℒ 𝑃𝑅𝑂𝑃 :
• 𝑝∧ 𝑞
• (𝑝 ∧ 𝛼 )
• (𝑝 ⊃ )

En algunas ocasiones será conveniente usar una gramática alternativa que nos permite
abstraernos de cuál es la conectiva binaria en particular. Para esto, la idea es agrupar las
conectivas binarias en un solo caso.

Definición (ℒ 𝑃𝑅𝑂𝑃 en BNF, alternativa).

𝛼, 𝛽 ∷= 𝑝 | (¬ 𝛼) | (𝛼 ∘ 𝛽)
∘ ∷= ∧ | ∨ | ⊃ | ↔
donde 𝑝 es una letra proposicional cualquiera de 𝑉𝑎𝑟 y 𝛼, 𝛽 denotan fórmulas arbitrarias.

Es intuitivo ver (y se puede demostrar) que ambas gramáticas describen exactamente el

mismo conjunto de fórmulas ℒ 𝑃𝑅𝑂𝑃 .

6
Árbol de sintaxis
Las fórmulas se pueden representar como árboles sintácticos. La conectiva en la raíz del
árbol corresponde a la conectiva que aparece “más afuera” en la fórmula, le llamamos
la conectiva principal.

Sintaxis Lineal Árbol de sintaxis

((𝑝 ⊃ 𝑞) ⊃ 𝑟) ⊃ 𝑟
⊃
𝑝 𝑞
q

∧
(¬(𝑝 ∧ (¬ 𝑞)))

𝑝 ¬

Dos posibilidades:

∨ ∧
(𝑝 ∧ 𝑞 ∨ 𝑟)
No es una fórmula. La falta de paréntesis ∧ 𝑟 𝑝 ∨
produce ambigüedad. ⋀
𝑝 𝑞 𝑞 𝑟
((𝑝 ∧ 𝑞) ∨ 𝑟) (𝑝 ∧ (𝑞 ∨ 𝑟))

7
Precedencia y Asociatividad
Los paréntesis sirven para evitar la ambigüedad, pero en fórmulas grandes complican la
sintaxis. La solución que adoptamos para ahorrar paréntesis es establecer convenciones de
notación sobre el orden de precedencia entre diferentes conectivas y el orden de
asociatividad entre conectivas iguales, de manera similar a la aritmética donde sabemos por
convención que 𝑥 × 𝑦 + 𝑧 es en realidad ((𝑥 × 𝑦) + 𝑧).

1. Precedencia
De mayor a menor: ¬, ∧, ∨, ⊃, ↔
Ejemplo.
¬𝑝 ∧ 𝑞 ∨ ¬𝑟 ⊃ 𝑠 ≡ ((((¬𝑝) ∧ 𝑞) ∨ (¬𝑟)) ⊃ 𝑠 )

2. Asociatividad
En general, para una conectiva binaria ∘ ∈ {∧, ∨, ⊃, ↔} y formulas 𝛼, 𝛽, 𝛾
cualesquiera la asociatividad es por derecha, es decir:
𝛼 ∘ 𝛽 ∘ 𝛾 ≡ (𝛼 ∘ (𝛽 ∘ 𝛾 ))
Ejemplo.
𝑝 ⊃ 𝑞 ⊃ 𝑟 ⊃ 𝑠 ≡ (𝑝 ⊃ (𝑞 ⊃ (𝑟 ⊃ 𝑠)))

3. Paréntesis exteriores
Los paréntesis de más afuera son totalmente redundantes. En vez de escribir
(𝛼 ∘ 𝛽), lo escribimos simplemente 𝛼 ∘ 𝛽.

De todas maneras, los paréntesis siguen siendo necesarios cuando se quiere establecer un
orden de evaluación diferente al que se asume por convención. Por ejemplo, si escribimos
(𝑝 ⊃ 𝑞) ⊃ 𝑟 tiene que quedar claro que no estamos hablando de la fórmula 𝑝 ⊃ 𝑞 ⊃ 𝑟
la cual es en realidad (𝑝 ⊃ (𝑞 ⊃ 𝑟)).

8
La sintaxis de LP en Haskell
Para codificar en Haskell la sintaxis de LP que hemos presentado, primero necesitamos un
tipo adecuado para representar letras proposicionales. La opción más simple es:

type Var = String

Ahora podemos definir qué son los fórmulas. Para esto una opción es definir un nuevo
tipo inductivo L para representar ℒ 𝑃𝑅𝑂𝑃 con sus reglas en el estilo de Fundamentos de
Computación (requiere agregar la directiva {-# LANGUAGE GADTSyntax #-}):

data L where { V ∷ Var → L; -- Una fórmula atómica

Neg ∷ L → L; -- Negación de una fórmula
And ∷ L → L → L; -- Conjunción de dos fórmulas
Or ∷ L → L → L; -- Disyunción de dos fórmulas
Imp ∷ L → L → L; -- Condicional de dos fórmulas
Iff ∷ L → L → L } -- Bicondicional de dos fórmulas

En este curso, cuando trabajemos con Haskell, preferimos definir los tipos inductivos
usando una forma alternativa equivalente a lo anterior pero más concisa cuya notación
es más cercana a lo visto en BNF (no requiere agregar nada):

data L = V Var
| Neg L
| And L L
| Or L L
| Imp L L
| Iff L L

Ejemplo. La fórmula (𝑝 ⊃ 𝑞) ⊃ 𝑟 de ℒ 𝑃𝑅𝑂𝑃 (sintaxis concreta) la podemos representar

como la siguiente fórmula (sintaxis abstracta) de tipo L:

Imp (Imp (V "p") (V "q")) (V "r")

Sintaxis “concreta” le llamamos a lo que normalmente escribimos en papel/pizarra a

mano alzada, y sintaxis “abstracta” le llamamos a lo que escribimos al trabajar con
Haskell en un laboratorio.

Añadiendo backticks es posible pasar de la posición prefija de las conectivas a la

posición infija más habitual tal como se usa en la sintaxis concreta:

((V "p") `Imp` (V "q")) `Imp` (V "r")

El trabajo de una herramienta de parsing es convertir la sintaxis concreta escrita por el

usuario a la sintaxis abstracta que puede manipular la máquina. Pero esto no es de
nuestro interés en este curso.

9
Recursión en LP

La naturaleza de una definición inductiva permite acompañar con principios de recursión e

inducción apropiados para definir funciones en forma recursiva y poder razonar
inductivamente sobre estas.

Para el tipo L de fórmulas, podemos expresar esquemas de recursión primitiva en dos

estilos:
Estilo “Fundamentos”: lambda y case Usando pattern matching

ℎ ∶ L → 𝐵 ℎ ∶ L → 𝐵
ℎ = 𝜆 𝛼 . case 𝛼 of ℎ (V 𝑝) = 𝑏
V 𝑝 → 𝑏 ℎ (Neg 𝛼) = ⋯ ℎ𝛼 ⋯
Neg 𝛼 → ⋯ ℎ𝛼 ⋯ ℎ (And 𝛼 𝛽) = ⋯ ℎ𝛼 ⋯ ℎ𝛽⋯
And 𝛼 𝛽 → ⋯ ℎ𝛼 ⋯ ℎ𝛽⋯ ℎ (Or 𝛼 𝛽) = ⋯ ℎ𝛼 ⋯ ℎ𝛽⋯
Or 𝛼 𝛽 → ⋯ ℎ𝛼 ⋯ ℎ𝛽⋯ ℎ (Imp 𝛼 𝛽) = ⋯ ℎ𝛼 ⋯ ℎ𝛽⋯
Imp 𝛼 𝛽 → ⋯ ℎ𝛼 ⋯ ℎ𝛽⋯ ℎ (Iff 𝛼 𝛽) = ⋯ ℎ𝛼 ⋯ ℎ𝛽⋯
Iff 𝛼 𝛽 → ⋯ ℎ𝛼 ⋯ ℎ𝛽⋯

donde 𝑏 ∶ 𝐵 donde 𝑏 ∶ 𝐵

En este curso preferimos el uso de pattern matching, donde una función queda bien
definida escribiendo una ecuación para cada regla de formación. Esto aplica a cualquier
tipo inductivo, no solo a nuestras fórmulas. Por ejemplo, comparar la típica función que
devuelve el largo de una lista en ambos estilos:

𝑙𝑒𝑛 ∶ [a] → 𝑁𝑎𝑡 𝑙𝑒𝑛 ∶ [a] → 𝑁𝑎𝑡

𝑙𝑒𝑛 = 𝜆 𝑙 . case 𝑙 of 𝑙𝑒𝑛 [ ] = 0
[] → 0 𝑙𝑒𝑛 (𝑥: 𝑥𝑠) = 𝑙𝑒𝑛 𝑥𝑠 + 1
𝑥: 𝑥𝑠 → 𝑙𝑒𝑛 𝑥𝑠 + 1
Adicionalmente, cuando no estamos trabajamos con Haskell en un laboratorio suele ser
conveniente alivianar la notación usando la sintaxis concreta, por lo que el esquema de
recursión para fórmulas es en general:

ℎ ∶ L → 𝐵
ℎ 𝑝 = 𝑏 donde 𝑏 ∶ 𝐵 y 𝑝 ∶ Var
ℎ (¬ 𝛼) = ⋯ ℎ𝛼 ⋯
(
ℎ 𝛼∧𝛽 = ) ⋯ ℎ𝛼 ⋯ ℎ𝛽⋯
ℎ (𝛼 ∨ 𝛽 ) = ⋯ ℎ𝛼 ⋯ ℎ𝛽⋯
ℎ (𝛼 ⊃ 𝛽 ) = ⋯ ℎ𝛼 ⋯ ℎ𝛽⋯
ℎ (𝛼 ↔ 𝛽) = ⋯ ℎ𝛼 ⋯ ℎ𝛽⋯

10
Ejemplo. Una función que cuenta la cantidad de conectivas unarias (negaciones) en una
fórmula.

𝑛𝑒𝑔𝑠 ∶ L → Nat
𝑛𝑒𝑔𝑠 𝑝 = 0
𝑛𝑒𝑔𝑠 (¬ 𝛼) = 𝑛𝑒𝑔𝑠 𝛼 + 1
𝑛𝑒𝑔𝑠 (𝛼 ∧ 𝛽) = 𝑛𝑒𝑔𝑠 𝛼 + 𝑛𝑒𝑔𝑠 𝛽
𝑛𝑒𝑔𝑠 (𝛼 ∨ 𝛽) = 𝑛𝑒𝑔𝑠 𝛼 + 𝑛𝑒𝑔𝑠 𝛽
𝑛𝑒𝑔𝑠 (𝛼 ⊃ 𝛽) = 𝑛𝑒𝑔𝑠 𝛼 + 𝑛𝑒𝑔𝑠 𝛽
𝑛𝑒𝑔𝑠 (𝛼 ↔ 𝛽) = 𝑛𝑒𝑔𝑠 𝛼 + 𝑛𝑒𝑔𝑠 𝛽

Entonces tenemos que la cantidad de negaciones en ¬(𝑝 ∧ ¬ 𝑞) es 2 porque podemos

computar ese resultado siguiendo la definición de 𝑛𝑒𝑔𝑠 :

𝑛𝑒𝑔𝑠 (¬(𝑝 ∧ ¬ 𝑞)) = 𝑛𝑒𝑔𝑠 (𝑝 ∧ ¬ 𝑞) + 1

= (𝑛𝑒𝑔𝑠 𝑝 + 𝑛𝑒𝑔𝑠 (¬ 𝑞)) + 1
= (0 + 𝑛𝑒𝑔𝑠 (¬ 𝑞)) + 1
= (0 + (𝑛𝑒𝑔𝑠 𝑞 + 1)) + 1
= (0 + (0 + 1)) + 1
= (0 + 1) + 1
=1+1
=2
En este ejemplo es claro que para cualquier conectiva binaria el comportamiento de la
función es idéntico. En otras palabras, es irrelevante saber cuál es la conectiva binaria que
aparece. Partiendo de la gramática alternativa, y adaptando el esquema de recursión
anterior de manera obvia, la definición de 𝑛𝑒𝑔𝑠 se puede hacer más simple:

𝑛𝑒𝑔𝑠 ∶ L → Nat
𝑛𝑒𝑔𝑠 𝑝 = 0
𝑛𝑒𝑔𝑠 (¬ 𝛼) = 𝑛𝑒𝑔𝑠 𝛼 + 1
𝑛𝑒𝑔𝑠 (𝛼 ∘ 𝛽) = 𝑛𝑒𝑔𝑠 𝛼 + 𝑛𝑒𝑔𝑠 𝛽

Siempre que sea conveniente, asumimos que estamos trabajando con la gramática
alternativa. En general, el esquema de recursión correspondiente es:

ℎ ∶ L → 𝐵
ℎ 𝑝 = 𝑏 donde 𝑏 ∶ 𝐵 y 𝑝 ∶ Var
ℎ (¬ 𝛼) = ⋯ ℎ𝛼 ⋯
ℎ (𝛼 ∘ 𝛽 ) = ⋯ ℎ𝛼 ⋯ ℎ𝛽⋯

11
Ejemplo. Una función que devuelve el conjunto de variables proposicionales que aparecen
en una fórmula.

Para esto es posible devolver un resultado de tipo Set Var:

𝑣𝑎𝑟𝑠 ∶ L → Set Var

𝑣𝑎𝑟𝑠 𝑝 = {𝑝} En Haskell: singleton p
𝑣𝑎𝑟𝑠 (¬𝛼) = 𝑣𝑎𝑟𝑠 𝛼
𝑣𝑎𝑟𝑠 (𝛼 ∘ 𝛽) = 𝑣𝑎𝑟𝑠 𝛼 ∪ 𝑣𝑎𝑟𝑠 𝛽 En Haskell: vars α `union` vars β

Hay que tomar en cuenta que en Haskell el concepto de “conjunto” está disponible
mediante la estructura de datos Set (requiere un import de Data.Set), pero la sintaxis de
Haskell no tiene soporte para la notación habitual de conjuntos y operaciones sobre estos
como { }, ∪, ∩, etc.

Para nuestros propósitos en este curso, es más conveniente trabajar con listas y eliminar los
repetidos cuando queremos tratar con conjuntos.

𝑣𝑎𝑟𝑠 ∶ L → [ L ]
𝑣𝑎𝑟𝑠 𝑝 = [𝑝]
𝑣𝑎𝑟𝑠 (¬𝛼) = 𝑣𝑎𝑟𝑠 𝛼
𝑣𝑎𝑟𝑠 (𝛼 ∘ 𝛽) = 𝑛𝑢𝑏 (𝑣𝑎𝑟𝑠 𝛼 + + 𝑣𝑎𝑟𝑠 𝛽)

La función 𝑛𝑢𝑏 ∶ [𝑎] → [𝑎] elimina repetidos de una lista (requiere un import de
Data.List).

12
Sustitución en fórmulas
La sustitución de variables en fórmulas es una operación sintáctica importante porque luego
veremos que tiene consecuencias semánticas interesantes.

Sustitución simple

Decimos que 𝛼[𝑝 ∶= 𝛽] es el resultado de sustituir en 𝛼 todas las ocurrencias de la variable

𝑝 por 𝛽. Esta operación se define por recursión sobre 𝛼:

_[_ ∶= _] ∶ L → Var → L → L
𝛽, si 𝑝 = 𝑞
𝑝[𝑞 ∶= 𝛽] = {
𝑝, si 𝑝 ≠ 𝑞
(¬𝛼)[𝑞 ∶= 𝛽] = ¬(𝛼[𝑞 ∶= 𝛽])
(𝛼1 ∘ 𝛼2 )[𝑞 ∶= 𝛽] = (𝛼1 [𝑞 ∶= 𝛽]) ∘ (𝛼2 [𝑞 ∶= 𝛽])

Ejemplo.

(𝑝 ∧ 𝑞 ⊃ 𝑝)[𝑝 ≔ 𝑟 ∨ 𝑠] = (𝑝 ∧ 𝑞)[𝑝 ≔ 𝑟 ∨ 𝑠] ⊃ 𝑝[𝑝 ≔ 𝑟 ∨ 𝑠]

= (𝑝 ∧ 𝑞)[𝑝 ≔ 𝑟 ∨ 𝑠] ⊃ (𝑟 ∨ 𝑠)
= 𝑝[𝑝 ≔ 𝑟 ∨ 𝑠] ∧ 𝑞[𝑝 ≔ 𝑟 ∨ 𝑠] ⊃ (𝑟 ∨ 𝑠)
= (𝑟 ∨ 𝑠) ∧ 𝑞 ⊃ (𝑟 ∨ 𝑠)

Sustitución múltiple

La sustitución simple se puede generalizar a la sustitución simultánea de múltiples variables.

Decimos que 𝛼[𝑝1 ∶= 𝛽1 , 𝑝2 ∶= 𝛽2 , … , 𝑝𝑛 ∶= 𝛽𝑛 ] es el resultado de sustituir
simultáneamente en 𝛼 todas las ocurrencias de cada variable 𝑝𝑖 por cada 𝛽𝑖 . Esta operación
también se define por recursión sobre 𝛼.

Tomar en cuenta que, en general, nuestra idea de sustitución múltiple no equivale a realizar
una secuencia de sustituciones simples. Es decir, en general:

𝛼[𝑝1 ∶= 𝛽1 , 𝑝2 ∶= 𝛽2 , … , 𝑝𝑛 ∶= 𝛽𝑛 ] ≢ 𝛼 [𝑝1 ∶= 𝛽1 ][𝑝2 ∶= 𝛽2 ] … [𝑝𝑛 ∶= 𝛽𝑛 ]

Ejemplo.

• (𝑝 ∨ 𝑞)[𝑝 ≔ 𝑞, 𝑞 ≔ 𝑝] = 𝑞 ∨ 𝑝
• (𝑝 ∨ 𝑞)[𝑝 ≔ 𝑞][𝑞 ≔ 𝑝] = (𝑞 ∨ 𝑞)[𝑞 ≔ 𝑝] = 𝑝 ∨ 𝑝

13
 Formalización de enunciados
Ahora que tenemos un lenguaje formal para LP, podemos formalizar enunciados del
Español en el lenguaje formal, haciendo precisa su forma lógica. Conviene comenzar
notando cómo los enunciados compuestos más simples y habituales del Español se pueden
formalizar en LP.

Lenguaje natural Lenguaje formal de LP En términos de conjuntos

“no p” 𝑝
¬𝑝
“no es el caso de p”

“p y q”
“p pero q” 𝑞
𝑝∧𝑞 𝑝
“p aunque q”
“p, q”

“p o q” 𝑝 𝑞
𝑝∨𝑞
“p y/o q”

𝑝 ⊕ 𝑞 ≝ (𝑝 ∨ 𝑞) ∧ ¬(𝑝 ∧ 𝑞)
“p o q, pero no ambos” 𝑝 𝑞
Conocido como XOR.

𝑝 ⊽ 𝑞 ≝ ¬(𝑝 ∨ 𝑞)
“ni p ni q” 𝑝 𝑞
“no p ni q”
Conocido como NOR.

Venn:

“si p entonces q”
𝑝 𝑞
“p solo si q”
“q si p”
𝑝⊃𝑞
“q cuando p” Euler:
“p es suficiente para q”
𝑞
“q es necesario para p” 𝑝

“p si y solo si q”
“p cuando y solo cuando q” 𝑝↔𝑞 𝑝 𝑞
“p es suficiente y necesario para q”

14
Observaciones:
• Es evidente que muchas de las conectivas del lenguaje español se corresponden con
las conectivas lógicas primitivas que hemos definido como parte de la sintaxis de LP,
por ejemplo la conjunción “y” es representada por ∧ en nuestro lenguaje formal.
Pero hay conectivas que no tienen correspondiente, como por ejemplo la disyunción
exclusiva. Sin embargo, es posible definir esas otras conectivas como simples
abreviaciones de fórmulas compuestas por nuestras conectivas primitivas. Eso es lo
que hacemos, por ejemplo, al escribir:
𝑝 ⊕ 𝑞 ≝ (𝑝 ∨ 𝑞) ∧ ¬(𝑝 ∧ 𝑞)
• Siguiendo el punto anterior, algunas de nuestras conectivas lógicas primitivas son
redundantes en el sentido de que se pueden definir en términos de otras. Por
ejemplo, no necesitamos tener el bicondicional dentro de nuestro lenguaje porque lo
podemos definir como:
𝑝 ↔ 𝑞 ≝ (𝑝 ⊃ 𝑞) ∧ (𝑞 ⊃ 𝑝)
• El condicional que nosotros simbolizamos por ⊃ es más precisamente llamado el
“condicional material”. Para que un condicional material sea falso, tiene que haber al
menos un caso donde el antecedente es verdadero y el consecuente es falso, dicho
caso constituye un contraejemplo y es lo que permite refutar la verdad del
condicional. Por ejemplo, el enunciado:
Si algo es una fruta entonces es una manzana
es falso, porque lo podemos refutar exhibiendo como contraejemplo una pera ya que
ésta es una fruta (cumple antecedente) pero no es una manzana (no cumple
consecuente).
Por otro lado, el enunciado
Si 1 = 0 entonces la tierra es plana
es verdadero, porque el antecedente es (obviamente) falso. Notar que ni siquiera
importa si la tierra es plana o no. En estos casos se dice que el condicional es
“vacuamente verdadero”, porque no hay nada que lo pueda mostrar falso.
Lo importante a entender de cualquier enunciado formalizado por un condicional
material es que solo garantiza la verdad del consecuente en caso de que el
antecedente sea verdadero. Antecedente y consecuente pueden no estar
relacionados de ninguna forma. En particular, el condicional material no afirma que
hay una relación de causalidad entre el antecedente y el consecuente, eso es algo
mucho más fuerte que no puede ser apropiadamente capturado en la lógica clásica
que nosotros vamos a estudiar.

15
En general, para formalizar enunciados de un lenguaje natural como el español hay que
hacer los siguiente:
1. Identificar las proposiciones atómicas y asignarle letras proposicionales.
2. Identificar las proposiciones compuestas según las conectivas lógicas presentes.

Ejemplo.

Si Martínez es nombrado candidato entonces Gómez o Gutiérrez renunciaran y perderemos

las elecciones.

Las proposiciones atómicas son:

𝑝 = "Martínez es nombrado candidato"
𝑞 = "Gutiérrez renunciará"
𝑟 = "Gómez renunciará"
𝑠 = "perderemos las elecciones"

La formalización es: 𝑝 ⊃ (𝑞 ∨ 𝑟) ∧ 𝑠

Como consejo, a veces puede ser útil resaltar la estructura proposicional del enunciado
reescribiéndolo de otra forma pero asegurándose de conservar el mismo significado. Por
ejemplo, el enunciado anterior es intuitivamente equivalente a:

Si Martínez es nombrado candidato entonces Gómez renunciará o Gutiérrez renunciará y

perderemos las elecciones.

Alternativamente, es también equivalente a:

Gómez renunciará o Gutiérrez renunciará y perderemos las elecciones si Martínez es

nombrado candidato.

16