Al 3 Ho

Sintaxis Semántica Sistemas de demostración

Sintaxis Semántica Sistemas de demostración
Proposiciones atómicas y compuestas

Sintaxis
La sintaxis del cálculo de proposiciones es muy simple. Por un lado, tenemos
el conjunto
PA = {p, q, r, p0 , . . . }

ANÁLISIS LÓGICO
CÁLCULO DE PROPOSICIONES

de proposiciones atómicas y, por otro lado, las conectivas lógicas usuales:
Francisco Hernández Quiroz¬, ∨, ∧, ⇒, ⇔ .
O en notación de Backus-Naur:

Departamento de Matemáticas
Facultad de Ciencias, UNAM
E-mail: fhq@ciencias.unam.mx
Página Web: www.matematicas.unam.mx/fhq

α ::= PA | ¬α | (α ∨ α) | (α ∧ α) | (α ⇒ α) | (α ⇔ α)
donde

Facultad de Ciencias

PA ::= p | q | r | pN | qN | rN ,
donde N es un número natural.

Francisco Hernández Quiroz

Análisis Lógico

Cálculo de proposiciones

1 / 25Francisco Hernández Quiroz

Análisis Lógico

Sintaxis Semántica Sistemas de demostración

Sintaxis Semántica Sistemas de demostración

Funciones booleanas Interdefinibilidad Consecuencia lógica

Funciones booleanas Interdefinibilidad Consecuencia lógica

Semántica

2 / 25

Cálculo de proposiciones

4 / 25

Funciones boolenas

La semántica del cálculo de proposiciones se expresa en términos devalores de verdad (generalmente).

Funciones de 0 argumentos

Los valores de verdad más utilizados son los valores booleanos
B = {V , F }.

Funciones de un argumento

V 0 y F 0.

Una evaluación es una fúnción e : PA → B.
Esta función se puede extender a proposiciones compuestas cuando se
combina con funciones booleanas asociadas a cada una de las
conectivas.

Francisco Hernández Quiroz

Cálculo deproposiciones

Análisis Lógico

Cálculo de proposiciones

V
F

3 / 25

id / π11
V
F

V1
V
V

Francisco Hernández Quiroz

F1
F
F

¬
F
V

Análisis Lógico

Sintaxis Semántica Sistemas de demostración

Sintaxis Semántica Sistemas de demostración

Funciones booleanas Interdefinibilidad Consecuencia lógica

Funciones booleanas Interdefinibilidad Consecuencia lógica

Funciones boolenas binarias
V
V
F
F

V
FV
F

π1
V
V
F
F

π2
V
F
V
F

V2
V
V
V
V

F2
F
F
F
F

∧
V
F
F
F

π1 es la proyección 1
V 2 es la constante verdadero
∧ es la conjunción
⇒ es la implicación
≡ es el o exclusivo
↓ es la negación alternativa
las 4 siguientes no tienen
un nombre estándar
Francisco Hernández Quiroz

Interdefinibilidad

∨
V
V
V
F

⇒
V
F
V
V

⇔
V
F
F
V

≡
F
V
V
F

↑
F
F
F
V

↓
F
V
V
V

⇐
V
V
F
V

F
V
F
V

F
F
V
V

F
V
FF

F
F
V
F

π2 es la proyección del 2
F 2 es la constante falso
∨ es la disyunción
⇔ es doble implicación
↑ es la negación conjunta
⇐ es la contraimplicación

Análisis Lógico

Cálculo de proposiciones

Teorema
Todas las conectivas se pueden definir en términos de
1
¬ y una de las siguientes
1
2
3

5 / 25

2

↑;

3

↓.

∨;
∧;
⇒;

Francisco Hernández Quiroz

Análisis Lógico

Sintaxis SemánticaSistemas de demostración

Sintaxis Semántica Sistemas de demostración

Funciones booleanas Interdefinibilidad Consecuencia lógica

Funciones booleanas Interdefinibilidad Consecuencia lógica

Bastan las conectivas binarias para todo

Cálculo de proposiciones

6 / 25

Demostración
Por inducción en el número de argumentos de la función, con una
salvedad:
Los casos básicos son las constantes, las conectivasunarias y las
binarias.
La hipótesis inductiva es:
Para toda k < n, toda función booleana f : {V , F }k → {V , F } se
puede definir con alguna de las opciones del teorema.
Caso inductivo: toda función booleana g : {V , F }n → {V , F } se
puede definir con alguna de las opciones del teorema.
Sugerencia: g se puede expresar como una combinación de una
función
h : {V , F }n−1 → {V , F }

El teoremaanterior parece referirse sólo a las conectivas binarias o
unarias.
Sin embargo, se aplica a las funciones boolenas de cualquier número
de argumentos.
Por ejemplo, la conectiva ternaria siguiente se puede definir en
términos de dos binarias:
if p then q else r ≡def (p ⇒ q) ∧ (¬p ⇒ r)

Y esto se puede generalizar a cualquier valor de n.

y una función
b : {V , F }2 → {V , F }.
Francisco...