logica matematica discreta
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
10Cá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...
Regístrate para leer el documento completo.