Naturalismo

Introducci´n a los Algoritmos - 1er. cuatrimestre 2011
o

Gu´ 4: C´lculo Proposicional y Aplicaciones
ıa
a
Docentes: Araceli Acosta, Carlos Areces, Mariana Badano, Luciana Benotti,
Javier Blanco, Paula Estrella, Pedro S´nchez Terraf, Mauricio Tellechea,
a
El objetivo principal de esta gu´ es lograr un buen entrenamiento de las habilidades necesarias para realizar
ıa
una demostraci´nformal en este sistema l´gico sencillo, que resulta un pilar fundamental para otros c´lculos
o
o
a
mas complejos y potentes.
En esta pr´ctica, como en el resto de las pr´cticas de esta materia, los ejercicios marcados como (!) son
a
a
algo m´s complejos que el resto; y son modelos de los ejercicios que se tomar´n en los parciales. Los ejercicios
a
a
marcados como son para las almasinquietas que quieren explorar m´s alla de los contenidos que veremos en
a
la materia.
C´lculo Proposicional
a
A partir de esta secci´n, comenzamos a trabajar con demostraciones con el C´lculo Proposicional.
o
a
Una demostraci´n en el C´lculo Proposicional que veremos en este curso consiste en probar la validez de
o
a
una f´rmula del estilo P ≡ Q. Para ello podemos seguir dos estrategias:aplicar sucesivos pasos transformando
o
la expresi´n completa en True , o bien partir de la subexpresi´n P y transformarla en la subexpresi´n Q (o
o
o
o
viceversa). En ambos casos, cada paso de “transformaci´n” consiste en “reescribir” la expresi´n en cuesti´n (o
o
o
o
una subexpresi´n) en otra equivalente dada por uno de los Axiomas o Teoremas b´sicos.
o
a
Cada axioma o teorema noshabilita a reescribir una expresi´n de diversas maneras. Por ejemplo la Regla
o
Dorada, cuya formulaci´n es P ∧ Q ≡ P ≡ Q ≡ P ∨ Q, nos permite reescribir la expresi´n P ∧ Q por P ≡ Q ≡
o
o
P ∨ Q, pero tambi´n:
e
P ∧Q≡P
Q≡P ∨Q
P ∧Q≡P ∨Q
P ∧Q≡Q≡P ∨Q
P ≡P ∨Q
etc . . .

por
por
por
por
por

Q≡P ∨Q
P ∧Q≡P
P ≡Q
Q
P ∧Q≡Q

Not´ adem´s que el lugar de las variables P, Q y R en unaxioma o teorema puede ser ocupado por cualquier
a
a
f´rmula que involucre variables proposicionales, como p, p ∧ q , p ⇒ q ∨ r, etc, o incluso f´rmulas m´s concretas
o
o
a
como 2 ∗ 2 = 4, x 0, etc. T´
ıpicamente un paso de una demostraci´n ser´ como el siguiente:
o
a
(x m´d 2 = 0) ∧ (x 0) ≡ (x m´d 2 = 0)
o
o
≡ { (Regla Dorada)(P, Q := x m´d 2 = 0, x 0) }
o
(x 0) ≡ (x m´d 2 = 0) ∨ (x0)
o

Los siguientes ejercicios nos introducen gradualmente en las demostraciones de la l´gica proposicional, en las
o
diferentes formas de utilizar un axioma o teorema, primero resolviendo un paso deductivo sencillo, para luego
avanzar en la tarea de hacer una demostraci´n completa.
o
1. Encontr´ el axioma o teorema utilizado para transformar una expresi´n en la otra, en cada una de las
ao
siguientes demostraciones que consta de un solo paso deductivo. Por ejemplo, el siguiente paso:
q≡p
≡{

}
p≡q

nos dice que (q ≡ p) ≡ (p ≡ q ), es decir, que no importa el “orden” de los operandos del ≡ (not´ que se
a
pueden sacar los par´ntesis). Esta es una forma particular de utilizar el axioma de Conmutatividad de la
e
equivalencia (cuya formulaci´n es P ≡ Q ≡ Q ≡ P ):reescribimos Q ≡ P con P ≡ Q, (cuando p ocupa el
o
lugar de P , y q el lugar de Q, o m´s sint´ticamente P, Q := p, q ).
a
e
1

p ≡ False

a)
≡{

p ∨ (q ≡ r)

d)
}

≡{

¬p
p⇒q

b)
≡{

p ∨ False

e)
}

≡{

p∨q ≡q
≡{

}
p

q ≡p∨q

c)

}
p∨q ≡p∨r

True ≡ p

f)
}

≡{

p∧q ≡p

}
p

2. Encontr´ las inc´gnitas E , F y G de forma que la sustituci´n (P, Q, R:= E , F , G ) justifique c´mo fue
a
o
o
o
aplicado cada axioma o teorema para transformar una expresi´n en la otra, en cada una de las siguientes
o
demostraciones. En todos los casos enunci´ la formula cuya validez se demuestra. Por ejemplo, el siguiente
a
paso deductivo:
Por ejemplo, el siguiente paso deductivo:
¬(p ⇒ q ≡ p)
≡ { (Definici´n de negaci´n)(P, Q := E , F ) }
o
o
¬(p...