Lógica

Lógica
Matemática discreta

Matemática discreta. Lógica

1

Lógica:
• rama de las matemáticas
– instrumento para representar el lenguaje
natural
– proporciona un mecanismo de deducción

Matemática discreta. Lógica

2

Cálculo proposicional y de
predicados
Razonamientos
Cálculo
Sentencias que expresan relaciones entre
proposicional atributos y cualidades de los objetos
Cálculo de
predicadosEstablecen propiedades de individuos y
relaciones entre estos

Matemática discreta. Lógica

3

ejemplo
"si el dato es de entrada o de salida y el dato no es de entrada,
entonces es de salida"
p = el dato es de salida
q = el dato es de entrada
{p V q , ¬ p} → q
"si x es de entrada, entonces x se graba en la memoria"
Px = x es un dato de entrada
Qx = x se graba en la memoria
Px → Qx
Matemáticadiscreta. Lógica

4

Cálculo proposicional

Cálculo proposcional
Proposición o enunciado: es toda afirmación u oración
declarativa que expresa algo sobre lo que se pueda
decir si es verdadero o falso.
–
–
–
–
–

Todos los procedimientos se han ejecutado correctamente.
¿Qué hora es?.
(x-y)2=x2-2xy+y2.
¡Menudo rollo de película!.
Esta frase es falsa.

• Proposiciones simples o atómicas.
• Proposicionescompuestas o fórmulas.
Matemática discreta. Lógica

5

Cálculo proposicional

Proposiciones simples o atómicas
• No pueden reducirse a otras más sencillas
• Símbolos primitivos Σ = {T, ⊥, p, q, r , s,K}
Símbolos de proposición
Constantes lógicas

Matemática discreta. Lógica

Enunciados atómicos

p, q , r , s ,K ∈ Σ

⊥

Falsedad

T

Verdad
6

Cálculo proposicional

Proposiciones compuestas ofórmulas
• Enunciados bien formados a partir de símbolos
primitivos unidos mediante conectivas.

LΣ = {P, Q, R, S ,K}
¬ Negación
∧ Conjunción
∨ Disyunción (“o” inclusivo)
Conectivas
∨ Disyunción (“o” exclusivo)
→ Implicación
↔ Doble implicación

Símbolos auxiliares ( , )
Matemática discreta. Lógica

para evitar ambigüedades
7

Cálculo proposicional

Regla de formación de fórmulas
P, P1 , P2 ∈ LΣ

p∈Σ

P::= p T ⊥ (¬P1) (P1 ∧ P2 ) (P1 ∨ P2 ) (P1∨P2 ) (P1 → P2 ) (P1 ↔ P2 )
Para abreviar se siguen las siguientes directrices:
Omisión de paréntesis externos
Prioridad entre conectivas:

¬, ∧, ∨, ∨, →, ↔

Asociatividad de la implicación: → asocia a la derecha

Matemática discreta. Lógica

8

Cálculo proposicional

ejemplos
( p ∨ (q ↔ r )) lo escribimos p ∨ (q ↔ r )
p → ¬q ∧ r

es

p → ((¬q) ∧ r )

p ∧q ↔ r es distinto de
p→q→r

Matemática discreta. Lógica

es

p ∧ (q ↔ r )

( p → (q → r ))

9

Cálculo proposicional

Semántica del cálculo proposicional
• Valoración

α: Σ → β

• Valor veritativo

π: LΣ → β

β = {0,1}

• A cada símbolo primitivo se le asigna un valor
booleano de verdad o falsedad: 0 falso, 1 verdad.
• A cada fórmula se le asigna un valor veritativo
dependiendo de los valores deverdad de los
símbolos primitivos que la componen.
En general, y abusando de la notación, hablaremos de valoración
y de valor veritativo indistintamente.
Matemática discreta. Lógica

10

Cálculo proposicional

Tablas de verdad
Representan todos los posibles valores veritativos de las
fórmulas básicas.

p

q

¬p ¬q p∧ q p∨ q p∨q p→q p↔ q

0
0
1
1

0
1
0
1

1
1
0
0

Matemática discreta. Lógica

10
1
0

0
0
0
1

0
1
1
1

0
1
1
0

1
1
0
1

1
0
0
1

11

Cálculo proposicional

Las tablas de verdad son una representación de las funciones

f ¬:β → β
f ¬(0) =1
f ¬(1) = 0

f ∧ :β × β → β
f ∧(0,0) = 0
f ∧(0,1) = 0
f ∧(1,0) = 0
f ∧(1,1) =1

f ∨ :β × β → β
f ∨(0,0) = 0
f ∨(0,1) =1
f ∨(1,0) =1
f ∨(1,1) =1

f ∨ :β × β → β
f ∨(0,0) = 0
f (0,1) =1
∨
f ∨(1,0) =1
f ∨(1,1) = 0

f →:β × β → β
f →(0,0) =1
f→(0,1) =1
f →(1,0) = 0
f →(1,1) =1

f ↔ :β × β → β
f ↔(0,0) =1
f ↔(0,1) = 0
f ↔(1,0) = 0
f ↔(1,1) =1

Matemática discreta. Lógica

12

Cálculo proposicional

Valores veritativos
π(p)= α(p)
π(⊥)=0
π(T)=1
π(¬P)= f ¬ ( π(P))
π(P ∧ Q)= f ∧ ( π(P), π(Q))
π(P ∨ Q)= f ∨ ( π(P), π(Q))
π( P∨Q )= f ∨ ( π(P), π(Q))
π(P → Q )= f → ( π(P), π(Q))
π(P ↔ Q)= f ↔ ( π(P), π(Q))
Matemática discreta. Lógica

13...