Download PROP

Matemática Discreta y Lógica 1
Material teórico
Lógica proposicional
Comenzaremos el estudio formal de las bases de la lógica: la lógica proposicional. Deberemos, en primera instancia
tener una definición de proposición.
Una proposición es una oración afirmativa de la cual podemos decir que es verdadera o falsa.
Detrás de esta definición está implícito que hay una noción de verdad, las proposiciones son verdaderas o falsas.
Como hemos dicho antes, en lógica queremos estudiar el razonamiento, y por lo tanto no será suficiente con conocer el
valor de verdad de proposiciones concretas, sino que nos centraremos en la noción de consecuencia. Construiremos una
teoría para definir en ella la sintaxis y la semántica de nuestras proposiciones, y veremos mecanismos que nos permitirán
saber cómo a partir del valor de verdad de algunas proposiciones podemos llegar al valor de verdad de otras.
Para formalizar esto, haremos lo siguiente:
•
•
Definiremos inductivamente el lenguaje de las proposiciones lógicas, al que llamaremos
•
PROP
v : PROP → {0,1}
Definiremos funciones por recursión primitiva, de
que llamaremos valuaciones,
PROP
en un conjunto con los valores de verdad, a las
Veremos dos nociones de razonamiento que resultarán equivalentes, una basada en la sintaxis y otra en la
semántica.
El conjunto PROP
*
Como hemos visto, un lenguaje es un subconjunto de Σ , para algún alfabeto
alfabeto (conjunto de símbolos) que utilizaremos en la lógica proposicional.
Σ Prop
•
•
•
Σ.
Comenzaremos definiendo el
contiene:
p0 , p1 , p 2 ,...
Conectivos: ⊥, ¬,∧,∨, →, ↔
Símbolos auxiliares: (, )
Letras de proposición:
Con este alfabeto podemos formar muchas palabras concatenando sus símbolos, por ejemplo,
( p0 → p1 )∈ Σ*Prop y
(∧ → ¬ ∨ )(↔ ) p0 ) ∈ Σ*Prop . Queda claro que no cualquier elemento de Σ*Prop será una frase válida en la lógica
proposicional, y definimos
PROP
de la siguiente manera:
PROP es el conjunto definido inductivamente por las siguientes cláusulas:
i.
pi ∈ PROP, ∀i ∈ N
ii. ⊥∈ PROP
iii. Si α ∈ PROP y β ∈ PROP , entonces (α ∧ β ) ∈ PROP
iv. Si α ∈ PROP y β ∈ PROP , entonces (α ∨ β ) ∈ PROP
v. Si α ∈ PROP y β ∈ PROP , entonces (α → β ) ∈ PROP
vi. Si α ∈ PROP y β ∈ PROP , entonces (α ↔ β ) ∈ PROP
vii. Si α ∈ PROP , entonces (¬α ) ∈ PROP
Página 1 de 2
Matemática Discreta y Lógica 1
Material teórico
Principio de inducción primitiva para PROP
No llamará la atención al lector, el enunciado del principio de inducción primitiva para
Principio de inducción primitiva para
Sea
P
una propiedad sobre
•
•
•
•
•
•
Entonces, se cumple
P(α )
PROP .
PROP
P( pi )∀i ∈ N
P(⊥)
Si P(α ) y P ( β ) , entonces
Si P(α ) y P ( β ) , entonces
Si P(α ) y P ( β ) , entonces
Si P(α ) y P ( β ) , entonces
Si P(α ) , entonces P (¬α )
•
PROP :
que cumple:
P(α ∧ β )
P(α ∨ β )
P(α → β )
P(α ↔ β )
para toda
α ∈ PROP
Secuencia de formación
Una secuencia
αn = α
•
•
•
α 0,α 1 , α 2 ,..., α n
y para todo
k≤n
de elementos de
Σ *Prop
es una secuencia de formación para
se cumple una de las siguientes:
α k ∈ {⊥, p0 , p1 , p 2 ,...}
α k = (α i ⊕ α j ) con ⊕ ∈ {∧,∨, →, ↔} y con i, j < k
α k = (¬α j ) con j < k
Subfórmula
Dadas
•
•
•
α ,ϕ ∈ PROP , diremos que ϕ
es subfórmula de
α =ϕ
α = (ϕ1 ⊕ ϕ 2 ) con ⊕ ∈ {∧,∨, →, ↔} y ϕ
α = (¬ϕ1 ) y ϕ es subfórmula de ϕ1
α
si se cumple alguna de las siguientes:
es subfórmula de
ϕ1 o ϕ 2
Esquema de recursión primitiva para PROP
Una función
•
•
•
•
f : PROP → B
f (⊥) := ...
f ( pi ) := ...
queda definida por las siguientes ecuaciones:
∀i ∈ N
f (α ⊕ β ) := ...α ...β ... f (α )... f ( β )...
f (¬α ) := ...α ... f (α )...
con
⊕ ∈ {∧,∨, →, ↔}
Página 2 de 2
α
si y sólo si