PDF de programación - Bloque II: Tema 1 - sintaxis de la lógica proposicional

BLOQUE II:

Tema 1

SINTAXIS DE LA LÓGICA PROPOSICIONAL

Lógica

Grado en Ingeniería Informática

Alessandra Gallinari

URJC

Contenido

Alfabeto del lenguaje formal de la lógica proposicional

Definición recursiva de las expresiones bien construidas: fórmulas

El principio de inducción estructural para fórmulas proposicionales
(demostración de propiedades)

Representación de las fórmulas bien construidas

Fórmulas en forma usual y abreviada
Fórmulas en forma de árbol estructural
El principio de recursión estructural para fórmulas proposicionales
(definición de funciones)

Formalización del lenguaje natural

1

2

Definiciones generales

Definiciones generales

Como ya comentamos en el capítulo de introducción, la sintaxis es la
definición axiomática de los elementos básicos del lenguaje y de las reglas
que permiten obtener nuevas expresiones correctas a partir de aquellos,
las fórmulas.
Recordamos que se puede fijar el origen de la lógica matemática (y de la
lógica proposicional) al final del siglo XIX, coincidiendo con la aparición
de las obras de G. Boole (1815-1864) y de G. Frege (1848-1925).
El objetivo de este capítulo es el estudio de la sintaxis de la lógica
proposicional que nos permite analizar las fórmulas proposicionales
construidas a partir de fórmulas atómicas (proposiciones declarativas
simples) y conectivos lógicos.

Un alfabeto A es un conjunto de símbolos.
Una palabra sobre el alfabeto A es una secuencia finita de

símbolos de A. Al conjunto de todas las posibles palabras se le suele
denotar como A∗.

Un lenguaje sobre el alfabeto A es un cualquier subconjunto de

A∗.

Las reglas de formación son las reglas que permiten obtener

nuevas expresiones de un lenguaje a partir de expresiones básicas.

3

4

Definiciones generales

Alfabeto de la lógica proposicional

Así, por ejemplo, si A es el alfabeto del idioma español, “aytzco” es una
palabra sobre A.
Un lenguaje es el conjunto de las palabras del diccionario de español y la
gramática española define las reglas de formación de expresiones
correctas.
A continuación vamos a definir el lenguaje de la lógica de proposiciones
por medio de su alfabeto y sus reglas de formación.

Los elementos básicos del alfabeto del la lógica proposicional son:
Las proposiciones atómicas (enunciados simples o variables
proposicionales): son proposiciones (oraciones declarativas a las
cuales se pueden asociar valores de verdad) que no pueden
descomponerse en otras proposiciones más simples.
Para representar las proposiciones atómicas se suelen usar los
símbolos p, q, r , s, t, . . . El conjunto de estos símbolos se suele
denominar signatura.

Ejemplos
Los siguientes son ejemplos de proposiciones simples:
p = la raíz cuadrada de 2 es irracional,
q = hoy me siento feliz,
t = los gatos son felinos.

5

6

Conectivos

Conectivos

Los conectivos lógicos:

constantes (de aridad 0): (verdadero) y ⊥ (falso)
conectivos unarios (de aridad 1): ¬ (negación)
conectivos binarios (de aridad 2):

∧ (y: la conjunción),
∨ (ó: la disyunción),
→ (la implicación o condicional),
↔ (la doble implicación o coimplicación).
NOTACIÓN: El símbolo ◦ se usará para representar un conectivo
binario cualquiera.

Ejemplo
Siendo q = hoy me siento feliz, aplicando la negación se obtiene ¬(q) =
hoy no me siento feliz.
Ejemplos
1) La frase “Hoy llueve, sin embargo no hace frío” se escribe como
(p ∧ ¬(q)), donde p = hoy llueve y q = hace frío.
2) La frase “Los lápices de mi hermana son rojos o negros” se escribe
como (p ∨ q), donde p = los lápices de mi hermana son rojos y q = los
lápices de mi hermana son negros.
3) La frase “La luna es de papel si y sólo si Carlos lee muchos libros” se
escribe como (p ↔ q), donde p = la luna es de papel y q = Carlos lee
muchos libros.

7

8

Tabla de los conectivos

Símbolos de puntuación

Conectiva lingüística

Conectivo lógico

verdadero

falso
no p
p y q
p ó q

si p entonces q

Constante (de aridad 0)
Constante (de aridad 0)

Negación (unario)
Conjunción (binario)
Disyunción (binario)
Implicación (binario)

p si y sólo si q

Coimplicación (binario)

Símbolo


⊥
¬
∧
∨
→
↔

Fórmula


⊥
¬(p)
(p ∧ q)
(p ∨ q)
(p → q)
(p ↔ q)

o

(p → q) ∧ (q → p)

Los símbolos de puntuación (o símbolos auxiliares): paréntesis

abiertos y cerrados.

Ejemplo
La frase “Si n es un número primo y mayor que 2, entonces n es impar”
se escribe como ((p ∧ q) → r ), donde p = n es primo, q = n es mayor
que 2 y r = n es impar.

Cuadro: Los conectivos de la lógica proposicional

9

10

Definiciones recursivas

Definiciones recursivas

Los elementos básicos de un lenguaje permiten definir cadenas finitas de
símbolos arbitrarias (palabras). Así, por ejemplo, la palabra
()¬p ∧ ∨)q →) se puede formar a partir del alfabeto de la lógica de
proposiciones.
De todas las posibles palabras, nos interesa definir aquellas que se
obtienen a partir del alfabeto dado sólo por medio de la reglas de
formación de nuestro lenguaje.
En matemáticas y en la ciencia de la computación a menudo se usan
definiciones recursivas de conjuntos, funciones o algoritmos, como en
los siguientes ejemplos:

Ejemplos
1) Para definir el conjunto N = {1, 2, 3, 4, . . .} de los números naturales
se puede dar un símbolo inicial 1 y unas reglas de formación, que nos
permiten hallar el resto de los elementos del conjunto.
Axiomas de Peano (siglo XIX):

En N hay un elemento distinguido que denominamos 1.
Para cada n ∈ N se define de manera única el siguiente de n. El
siguiente de n se denota s(n) = n + 1 y es un elemento de N para
cada n ∈ N.

No existe ningún número natural n tal que s(n) = 1.
Si s(n) = s(m) entonces n = m.
Principio de inducción: si un conjunto de números naturales
contiene al 1 y a los sucesores de cada uno de sus elementos,
entonces contiene a todos los números naturales.

11

12

Definiciones recursivas

Definiciones recursivas

Ejemplos
2) Otro ejemplo muy conocido es la definición recursiva de la sucesión
{fn}n∈N de Fibonacci (hacia 1175 − 1250), que fue definida para estudiar
la reproducción de los conejos. Sus primeros dos términos son f1 = 1 y
f2 = 1. Si n ≥ 3, entonces el valor fn se deduce de los valores fn−1 y fn−2
según la fórmula fn = fn−1 + fn−2. Se sigue que
{fn} = {1, 1, 2, 3, 5, 8, 13,···}.
3) El factorial de un número natural n,

n! = n · (n − 1) · (n − 2) · . . . · 2 · 1,

se puede definir también de forma recursiva:



n! =

1
n(n − 1)!

si n = 1,
si n > 1.

13

Ejemplos
4) El algoritmo de búsqueda binaria es un ejemplo de algoritmo de tipo
“divide y vencerás,” que se define de forma recursiva. El problema que se
quiere resolver es de determinar si un cierto número x pertenece a una
dada lista (finita) ordenada de números l . El algoritmo de búsqueda
binaria divide primero la lista l en dos mitades y compara x con un
elemento central. Si el elemento central es distinto de x, determina a
cuál de las mitades puede pertenecer x. Seleccionada esta nueva lista,
vuelve a comparar x con su elemento central y a seleccionar aquella
mitad de la nueva lista que puede contener x. Estas particiones se
repiten hasta llegar a una lista de un sólo elemento, que puede ser o no
ser igual a x.

14

Definición recursiva de las fórmulas proposicionales

Subfórmulas

Definición
Una fórmula proposicional (fórmula bien construida, fbc) es una
palabra sobre el alfabeto de la lógica proposicional que puede construirse
en un número finito de pasos mediante las reglas de formación que vamos
a definir a continuación:
1. (At): Los símbolos y ⊥ y toda proposición atómica son una

fórmula.

2. (¬): Si ϕ es una fórmula entonces ¬ϕ es una fórmula.
3. (◦): Si ϕ y ψ son dos fórmulas entonces (ϕ ◦ ψ) es una fórmula.
4. Si una palabra no se obtiene mediante las tres reglas anteriores

entonces no es una fórmula.

NOTACIÓN: Para representar las fórmulas se suelen usar las letras del
alfabeto griego ϕ, ψ, χ, . . . (ver la tabla del alfabeto griego).

Definición
Dadas dos fórmulas ϕ y ψ, se dice que ψ es una subfórmula de ϕ si
ψ consiste de símbolos consecutivos de ϕ. En particular, cada fórmula
es una subfórmula de sí misma.
Ejemplo
La palabra ((p ∧ q) → r ), del ejemplo (2) es una fórmula bien construida
ya que:
1. p, q, r , son fórmulas atómicas (aplicando (At)),
2. (p ∧ q) es una fórmula proposicional (aplicando (◦)),
3. ((p ∧ q) → r ) es una fórmula proposicional (aplicando (◦)).
Además, (p ∧ q) y r son subfórmulas de ((p ∧ q) → r ).

15

16

Inducción estructural: demostración de propiedades

Inducción sobre N

Para poder estudiar propiedades de las fórmulas proposicionales una de
las técnicas más adecuadas es el principio de inducción estructural
para fórmulas proposicionales, que es una versión generalizada (y más
compleja) del razonamiento de inducción definido a partir de los axiomas
de Peano de los números naturales.
Antes de enunciar el principio de inducción estructural para fórmulas
proposicionales, recordamos la definición de razonamiento por inducción
sobre los números naturales:

Sea P(n) una propiedad para números naturales. Supongamos que se
pueda probar que:

1. Base de inducción: se verifica P(1),
2. Paso de inducción: si se verifica P(n) (hipótesis de inducción),

entonces se verifica P(n + 1).

Bajo las hipótesis anteriores, se sigue que se verifica P(n) para todo
número natural n.
La demostración de la validez del razonamiento de inducción se obtiene
aplicando el principio de inducción al conjunto
A = {n ∈ N : P(n) se verifica}.

17

18

Inducción sobre N

Inducción estructural

Ejemplo
Vamos a demostrar por inducción que para todo n ∈ N,

2n ≤ (n + 1)!

Base de inducción: P(1) es verdadera, siendo (2 ≤ 2).
Paso de inducción: si 2n ≤ (n + 1)! (si se verifica P(n)), entonces
2n+1 = 2 2n ≤ 2 (n + 1)! ≤ (n + 2) (n + 1)! = (n + 2)!.

Por tanto, 2n ≤ (n + 1)! se verifica para todo número natural n.

El principio de inducción estructural generaliza el método de
demostración por inducción.