Logica

MATEDISCRETAS
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 losobjetos Cá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 graba enla 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 es falsa.

•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 Constantes lógicas
Enunciados atómicos

p, q , r , s ,K ∈ Σ

⊥ T

Falsedad Verdad
6

Matemática discreta. Lógica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
para evitar ambigüedades
7

Símbolos auxiliares ( , )
Matemática discreta. Lógica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 1 2 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 la derecha
8

Matemática discreta. Lógica

Cálculoproposicional

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

p → ((¬q) ∧ r ) p ∧ (q ↔ r )

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

( p → (q → r ))

Matemática discreta. Lógica

9

Cálculo proposicional

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

α: Σ → β π: LΣ → β

β = {0,1}

• Valor veritativo

• A cada símbolo primitivo se le asigna un valorbooleano 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 valoresveritativos de las fórmulas básicas.

p 0 0 1 1

q 0 1 0 1

¬p ¬q p∧ q p∨ q p∨q p→q p↔ q
1 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 0 1

Matemática discreta. Lógica

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
Matemática discreta. Lógica

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
12

Cálculo proposicional

Valores veritativos
π(p)= α(p) π(⊥)=0 π(T)=1 ¬ π( P)= f ¬ ( π(P)) π(P ∧ Q)= f ∧ (...