logica matematica discreta

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 objetosCálculo de
predicados

Establecen 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 grabaen la memoria
Px → Qx
Matemática discreta. 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 esfalsa.

• Proposiciones simples o atómicas.
• Proposiciones compuestas 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

Enunciados atómicos

p, q , r , s ,K ∈ Σ

Matemática discreta. Lógica

⊥

Falsedad

TConstantes lógicas

Verdad
6

Cálculo proposicional

Proposiciones compuestas o fó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 ⊥ (¬P ) (P ∧ P ) (P ∨ P ) (P ∨P ) (P → P ) (P ↔ P )
1
1
2
1
2
12
1
2
1
2
Para abreviar se siguen las siguientes directrices:
Omisión de paréntesis externos
Prioridad entre conectivas:

¬, ∧, ∨, ∨, →, ↔

Asociatividad de la implicación: → asocia a laderecha

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 de verdad 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

1
0
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 delas 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...