LÓGICA PRIMER PARCIAL UB

Introducci´n a la L´gica
o
o
Curso 2013–2014. Grupo A2
C. Badesa

Resumen esquem´tico de L´gica Proposicional
a
o
1.

Sintaxis
El alfabeto de un lenguaje L de la l´gica proposicional consta de los siguientes s´
o
ımbolos:
1. Un conjunto de letras proposicionales a las que nos referiremos con las letras “p”, “q”, “r”, “s”
y “t” (con o sin sub´
ındices).
2. Conectivas: negaci´n:¬, que leeremos “no”
o
conjunci´n: ∧, que leeremos “y”
o
disyunci´n: ∨, que leeremos “o”
o
condicional: →, que leeremos “si..., entonces”
bicondicional: ↔, que leeremos “si y s´lo si”
o
3. Par´ntesis.
e

Las conectivas son los s´
ımbolos l´gicos del lenguaje y los par´ntesis los s´
o
e
ımbolos auxiliares. La
negaci´n es una conectiva monaria y las restantes son binarias.
o
Unaf´rmula de un lenguaje proposicional L o, simplemente, una f´rmula es una sucesi´n de
o
o
o
s´
ımbolos generada por un n´mero finito de aplicaciones de las siguientes reglas:
u
1. Toda letra proposicional de L es una f´rmula.
o
2. Si α es una f´rmula, ¬α es una f´rmula.
o
o
3. Si α y β son f´rmulas, (α ∧ β), (α ∨ β), (α → β) y (α ↔ β) son f´rmulas.
o
o
Las letras proposicionales sonf´rmulas at´micas y todas las restantes son f´rmulas compuestas.
o
o
o
Cada f´rmula compuesta tiene una conectiva principal, aquella que introduce la ultima regla que se
o
´
aplica al construir la f´rmula. La conectiva principal de ¬α es la negaci´n, y si ∗ es una conectiva
o
o
distinta de la negaci´n, entonces ∗ es la conectiva principal de (α ∗ β). Es habitual referirse gen´ricao
e
mentea las f´rmulas que tienen la misma conectiva principal con el nombre de dicha conectiva. As´
o
ı,
una f´rmula de la forma ¬α es una negaci´n, una de la forma (α ∧ β) es una conjunci´n, etc. En un
o
o
o
condicional (α → β) decimos que α es el antecedente y que β es el consecuente.
Subf´rmulas
o
El ´rbol geneal´gico de una f´rmula compuesta α se construye por el siguiente procedimiento: sea
o
o
analiza (se descompone) α en las f´rmulas m´s simples que la componen, se analizan ´stas del mismo
o
a
e
modo y se prosigue este an´lisis hasta llegar a las letras proposicionales, que no son analizables en
a
f´rmulas m´s simples. Las subf´rmulas de una f´rmula α son ella misma y todas las f´rmulas a las
o
a
o
o
o
que se llega mediante este proceso de an´lisis; esto es, lassubf´rmulas de una f´rmula α son todas las
a
o
o
f´rmulas que aparecen en su ´rbol de geneal´gico (incluida ella misma).
o
a
o
Observemos que: 1) no hay dos f´rmulas distintas que tengan las mismas subf´rmulas y 2) si una
o
o
f´rmula γ es una subf´rmula de una f´rmula β y ´sta es una subf´rmula de α, la f´rmula γ tambi´n
o
o
o
e
o
o
e
es una subf´rmula de la f´rmula α.
o
o
1Omisi´n de par´ntesis
o
e
En lo sucesivo, omitiremos los par´ntesis exteriores de las f´rmulas (una vez construidas) siempre
e
o
que lo creamos conveniente. As´ en lugar de escribir ((p∨q) → (p∧r)) podemos escribir (p∨q) → (p∧r),
ı,
pero no podemos eliminar ning´n otro par´ntesis.
u
e

2.

Sem´ntica
a

2.1.

Verdad con una asignaci´n
o

Una asignaci´n es una funci´n queasigna a cada una de las letras proposicionales del lenguaje
o
o
el valor verdadero o el valor falso. A estos valores los llamamos valores de verdad. Para abreviar, nos
referiremos a ellos con las letras “V ”y “F ”, respectivamente, y diremos que una asignaci´n atribuye o
o
asigna a cada letra proposicional el valor V o el valor F . Para referirnos a las asignaciones usaremos
la letra “v”(con sub´
ındices, cuando sea necesario). La expresi´n
o
v(p) = V
significa entonces que la asignaci´n v atribuye el valor V a la letra proposicional p o, dicho de otro
o
modo, que p es verdadera con la asignaci´n v. Si en lugar del valor V es el valor F , esto es, si v(p) = F,
o
decimos que p es falsa con la asignaci´n v.
o
S´lo hay 2 (= 21 ) asignaciones en el caso de un lenguaje con...