Práctica 1: Lógica Proposicional y Tipos Básicos (Algoritmos I)

Sintaxis

Ejercicio 1

Sean x : $\mathbb {Z}$, y : $\mathbb {R}$ y z: Bool tres variables ¿Qué tipo tienen las siguientes expresiones?

a) 3 + 7 ($\mathbb {Z}$)
b) True (Bool)
c) y·y ($\mathbb {R}$)
d) (z $\vee \ \neg$z) (Bool)
e) x==6 (Bool)
f) x==y (Bool)
g) $\pi$==3 (Bool)
h) x + y·2 ($\mathbb {R}$)
i) z $\wedge$ 0==1 (No tiene tipo: faltan los paréntesis)
j) $\pi$+x ($\mathbb {R}$)

Ejercicio 2

Sean x : $\mathbb {Z}$, y : $\mathbb {R}$ y z: Bool tres variables ¿Cuáles de las siguientes expresiones pueden tiparse correctamente?

a) $\pi$+1 (Sí)
b) z + x (Sí)
c) (1==0)$\vee$(x==z) (No, faltan los paréntesis)
d) (x+10)==y (Sí)
e) $\pi$+x (Sí)
f) (x$\vee$y) (No, el operador $\vee$ se aplica a dos bool)
g) $\pi$==3 (Sí)
h) z==(x==y) (Sí, z toma el mismo valor de verdad que x==y)
i) z==(x==$\pi$) (Sí, ídem)
j) y·y<0 (Sí)

Ejercicio 3

La expresión (3 + 7 == $\pi$ − 8) $\wedge$ True tiene tipo Bool. Justifique informal, pero detalladamente, el porqué.

En realidad este enunciado tiene un pequeño error: esa expresión no es de tipo Bool, no tiene ningún tipo, ya que le faltan los paréntesis que encierren toda la expresión. Estos paréntesis son necesarios, ya que (p$\wedge$q ), donde p y q son de tipo Bool, es una fórmula bien formada, pero no es válido para p$\wedge$q.

El enunciado puede ser reemplazado por este:

La expresión ((3 + 7 == $\pi$ − 8) $\wedge$ True) tiene tipo Bool. Justifique informal, pero detalladamente, el porqué.

Justificación: el operador + puede aplicarse a dos elementos de tipo numérico, y representa otro elemento numérico. A su vez el operador ==, cada vez que se le aplica a dos elementos de igual tipo, nos representa un Bool. El operador $\wedge$ puede aplicarse a dos Bool, y devuelve un tercero. En conclusión: tipa bien y es un Bool.

Semántica proposicional clásica

Ejercicio 4

Sean p y q variables proposicionales ¿Cuáles de las siguientes expresiones son fórmulas bien formadas?

a) (p$\neg$q) (No, el conectivo $\neg$ es unario)
b) p $\vee$ q $\wedge$ True (No, el $\vee$ y el $\wedge$ están bien formados sólo usando paréntesis)
c) (p $\rightarrow \neg$ p $\rightarrow$ q) (No, los paréntesis no deben encerrar a toda la fórmula, sino a cada subfórmula que tenga un conectivo binario. Lo cual no sucede en este caso.)
d) $\neg$(p) (No. Los paréntesis se usan sólo cómo está explicito en las reglas de fórmulas bien formadas. A pesar de que es claro lo que representa, las reglas de "bienformación" de formulas no admite ese uso de los paréntesis.)
e) (p $\vee \neg$p $\wedge$ q) (No, los incisos de fórmulas bien formadas no dicen nada respecto de la combinación de $\vee$ y $\wedge$. Por lo tanto no está bien formada.)
f)(True $\wedge$ True $\wedge$ True $\wedge \dots$) (No, pero sí valdría si fueran FINITOS)
g) ($\neg$p) (No, ídem d)
h) (p $\vee$ False) (Sí, cumple las reglas de bienformación)
i) (p==q) (No, == no es un conectivo, sino un operador. Esta operación tiene valor Bool. Algo de tipo Bool NO necesita paréntesis, ya que representa un valor de verdad en sí mismo.)

Ejercicio 5

Determinar el valor de verdad de las siguientes proposiciones, si el valor de verdad de a, b y c es verdadero, mientras que el de x e y es falso.

a) ($\neg$a $\vee$ b) (True)
b) (c $\vee$ (y $\wedge$ x) $\vee$ b) (True)
c) $\neg$(c $\vee$y) (False)
d) ($\neg$(c $\vee$y) $\leftrightarrow$ ($\neg$c $\wedge \neg$ y)) (True)
e) ((c $\vee$ y) $\wedge$ (x $\vee$ b)) (True)
f) (((c $\vee$ y) $\wedge$ (x $\vee$ b)) $\leftrightarrow$(c $\vee$ (y $\wedge$ x) $\vee$ b)) (True)
g) ($\neg$c $\wedge \neg$b) (False)

Ejercicio 6

Determinar, utilizando tablas de verdad, si las siguientes fórmulas son tautologías, contradicciones o contingencias.

a) (p $\vee \neg$p) (Tautología)
b) (p $\wedge \neg$p) (Contradicción)
c) (($\neg$p $\vee$ q) $\leftrightarrow$ (p $\rightarrow$ q)) (Tautología)
d) ((p $\vee$ q) $\rightarrow$ p) (Contingencia)
e) ($\neg$(p $\wedge$ q) $\leftrightarrow$ ($\neg$p $\vee \neg$q)) (Tautología)
f) (p $\rightarrow$ p) (Tautología)
g) ((p $\wedge$ q) $\rightarrow$ p) (Tautología)
h) (( p $\rightarrow$ (q $\rightarrow$ r)) $\rightarrow$ ((p $\rightarrow$ q) $\rightarrow$ (p $\rightarrow$ r))) (Tautología)
i) ((p $\wedge$ (q $\vee$ r)) $\leftrightarrow$ ((p $\wedge$ q)$\vee$ (p $\wedge$r))) (Tautología)

Ejercicio 7

Dadas las proposiciones lógicas a y b, se dice que a es más fuerte que b si y sólo si a $\rightarrow$ b es una tautología. En este caso, también decimos que b es más débil que a. Determinar la relación de fuerza de los siguientes pares de fórmulas:

a) True, False (es más fuerte False)
b) (p $\wedge$ q), (p $\vee$ q) (es más fuerte la primera)
c) True, True (son igualmente fuertes)
d) p, (p$\wedge$q) (es más fuerte la segunda)
e) False, False (son igualmente fuertes)
f) p, (p $\vee$ q) (es más fuerte p)
g) p,q (ninguno es más fuerte que otro ya que es contingencia)
h) p, (p $\rightarrow$ q) (ídem)
La proposición más débil que aparece en el ejercicio es True (ya que cualquier cosa implica True), y la más fuerte False (False implica cualquier cosa)

Ejercicio 8

Decimos que un conectivo es expresable mediante otros si es posible escribir una fórmula utilizando exclusivamente estos últimos y que tenga la misma tabla de verdad que el primero (es decir, son equivalentes). Por ejemplo, la disyunción es expresable mediante la conjunción mmás la negación, ya que (p $\vee$ q) tiene la misma tabla de verdad que: ($\neg$p $\wedge \neg$q). Mostrar que cualquier fórmula de la lógica proposicional que utilice los conectivos: $\neg$ (negación), $\wedge$ (conjunción), $\vee$ (disyunción), $\rightarrow$ (implicación), $\leftrightarrow$ (equivalencia) puede reescribirse utilizando sólo los conectivos $\neg$ y $\vee$.

Si logramos escribir la tabla de verdad de cada conectivo usando $\neg$ y $\vee$, entonces cualquier fórmula que use cualquiera de esos conectivos podrá escribirse en función de ellos.

Conjunción: (p $\wedge$ q) puede escribirse como $\neg$($\neg$p $\vee \neg$ q)
Esto se prueba fácilmente haciendo la tabla de verdad de cada una y viendo que son iguales, o haciendo la de ((p $\wedge$ q) $\leftrightarrow$ $\neg$($\neg$p $\vee \neg$ q) y viendo que es tautología.

Implicación: (p $\rightarrow$ q) puede escribirse como ($\neg$p $\vee$ q)

Equivalencia: ( p $\leftrightarrow$ q) puede escribirse como $\neg$($\neg$($\neg$ p $\vee$ q) $\vee \neg$ ($\neg$q $\vee$ p))

Pueden probarse todos de la misma manera, lo dejamos como ejercicio.

Ejercicio 9

Sean las variables proposicionales f, e y m con los siguientes significados:
f$\equiv$"es fin de semana", e $\equiv$ "Juan estudia" y m$\equiv$"Juan escucha música".

a) Escribir usando lógica proposicional las siguientes oraciones:

1. "Si es fin de semana, Juan estudia o escucha música, pero no ambas cosas":
   ($f\Rightarrow ((e\vee m)\wedge \neg (e\wedge m))$)
2. "Si no es fin de semana, entonces Juan no estudia":
   ($\neg f\Rightarrow \neg e$)
3. "Cuando Juan estudia los fines de semana, lo hace escuchando música":
   (($e\wedge f)\Rightarrow m$)

b) Asumiendo que valen las tres proposiciones anteriores se puede deducir que Juan no estudia? Justificar usando argumentos de la logica proposicional.

Probar que bajo esas hipótesis Juan no estudia, significa probar que ((1 $\wedge$ 2 $\wedge$ 3) $\leftrightarrow \neg$e) se cumple cualesquiera sean los valores que tomen f, e y m (es decir es tautología). Dejamos la tabla de verdad como tarea para el dulce hogar.

Ejercicio 10

En la salita verde de un jardín se sabe que las siguientes circunstancias son ciertas:

a)Si todos conocen a Juan entonces todos conocen a Camila (podemos pensar que esto se debe a que siempre caminan juntos).

b) Si todos conocen a Juan, entonces que todos conozcan a Camila implica que todos conocen a Gonzalo.

La pregunta entonces es: ¿Es cierto que si todos conocen a Juan entonces todos conocen a Gonzalo? Justificar.

Pasemos todo a lenguaje lógico:

• j$\equiv$"Todos conocen a Juan"
• c$\equiv$"Todos conocen a Camila"
• g$\equiv$"Todos conocen a Gonzalo"

Entonces a) y b) son: (j $\rightarrow$ c) y (j $\rightarrow$ (c $\rightarrow$ g)).

Queremos ver si de esas hipótesis se desprende (j $\rightarrow$ g).

Esto es: probar que (((j $\rightarrow$ c) $\wedge$ (j $\rightarrow$ (c $\rightarrow$ g))) $\rightarrow$ (j $\rightarrow$ g)) es verdadero para cualquier valor de j, c y g (otra vez: probar que es tautología).

Va a ser verdadero.

Ejercicio 11

Siempre que Haroldo se pelea con sus compañeritos, vuelve a casa con un ojo morado. Si un día lo viéramos llegar con el ojo destrozado, podríamos sentirnos inclinados a concluir que se ha tomado a golpes de puño y cabezazos con los otros niñitos. ¿Puede identificar el error en el razonamiento anterior? Pista: Es conocido como falacia de afirrmar el consecuente.

Como lo dice el enunciado es la famosa falacia de afirmación del consecuente. Analicemos este razonamiento erróneo:

• Si vale (p $\rightarrow$ q) y p es verdadero, entonces q es verdadero.
• Si vale (p $\rightarrow$ q) y q es verdadero ¿Puedo deducir algo? No.

Ejemplos:

• "Si un alumno aprueba la materia, aprobó los trabajos prácticos". Un alumno aprobó los trabajos prácticos, entonces aprobó la materia (MENTIRA! Pudo haber reprobado terriblemente los parciales y los recuperatorios)

• "Todas las novias de Leonel están buenas". Ayer ví una chica que estaba buena, entonces es novia de Leonel.

Semántica de Cortocircuito

Ejercicio 12

Asignar un valor de verdad (verdadero, falso o indefinido) a cada una de las siguientes expresiones aritméticas en los reales.

Recordemos antes que todas las operaciones numéricas son estrictas: esto es si se indefine algún operando se indefine toda la operación.

a) 5 > 0 (Verdadero)

b) 1 $\leq$ 1 (Verdadero)

c) $(5+3-8)^{-1}$ (Indefinido)

d) 0 $\geq$ 5 (Falso)

e) ${\frac {1}{0}}=={\frac {1}{0}}$ (Indefinido)

f) $0>\log _{2}{2^{2^{0}-1}-1}$ (Indefinido)

g) $0\cdot (-1)^{\frac {1}{2}}==0$ (Indefinido)

h) $(-1)^{\frac {1}{2}}\cdot 0==0$ (Indefinido)

i) $\tan {\frac {\pi }{2}}==\tan {\pi }-\tan {2}$ (Indefinido)

Ejercicio 13

La semántica de cortocircuito se basa en una forma particular de evaluar las expresiones booleanas. ¿Puede identificarla? ¿Cuál es su motivación?.

La semántica de cortocircuito se basa en evaluar de izquierda a derecha las expresiones booleanas, con el objetivo de resolver expresiones más rápidamente y de evitar indefiniciones. En este sentido, es tan efectivo evaluar de izquierda a derecha como evaluarlas de derecha a izquierda, según del modo en el que esten armadas las expresiones, sin embargo la semántica de cortocicuito utiliza la evaluación de izquierda a derecha.

Ejercicio 14

Determinar los valores de verdad de las proposiciones del ejercicio 5 cuando el valor de verdad de b y c es verdadero, el de x es falso y el de a e y es indefinido

a) ($\neg$a $\vee$ b)
Indefinido (porque si se llega a evaluar un indefinido se indefine todo)
b) (c $\vee$ (y $\wedge$ x) $\vee$ b)
Verdadero (la semántica de cortocircuito nos permite decidir que una disyunción es verdadera al encontrar el primer valor verdadero)
c) $\neg$(c $\vee$y)
Falso (por lo mismo que antes podemos afirmar que la disyunción es verdadera sin evaluar el indefinido, y al negarla todo se vuelve falso)
d) ($\neg$(c $\vee$y) $\leftrightarrow$ ($\neg$c $\wedge \neg$ y))
Indefinido (no podemos aprovechar la semántica de cortocircuito en este caso, ya que no podemos evitar evaluar la indefinición, por lo cual se indefine todo)
e) ((c $\vee$ y) $\wedge$ (x $\vee$ b))
Falso (nuevamente aprovechando la semántica de cortocircuito podemos escapar de evaluar la indefinición. Recordemos que si evaluamos una indefinición se indefine TODO!)
f) (((c $\vee$ y) $\wedge$ (x $\vee$ b)) $\leftrightarrow$(c $\vee$ (y $\wedge$ x) $\vee$ b))
Falso (la evaluación no se indefine y el resultado que da es Falso)
g) ($\neg$c $\wedge \neg$b)
Falso (nuevamente podemos asegurar que la conjunción es falsa sin evaluar el término que se indefine)

Ejercicio 15

Construir las tablas de verdad de las fórmulas del ejercicio 6, teniendo en cuenta los tres valores de verdad (verdadero, falso e indefinido).

Debido a lo dificultoso de compartir tablas de verdad por este medio, momentáneamente, lo dejamos como tarea para el dulce hogar.

Ejercicio 16

A diferencia de lo que sucede en la lógica proposicional clásica, en general no vale que (p$\wedge$q) es equivalente a (q$\wedge$p) cuando admitimos a $\bot$ como valor de verdad. Mostrar que sin embargo (p $\leftrightarrow$ q), ((p $\rightarrow$ q)$\wedge$(q $\rightarrow$ p)) y ((q $\rightarrow$ p)$\wedge$(p $\rightarrow$ q)) siguen siendo equivalentes.

Veamos las tablas de verdad de cada una, con la lógica trivaluada, y veamos que efectivamente son equivalentes (es decir, las tres fórmulas tienen la misma tabla de verdad)

p	q	(p $\leftrightarrow$ q)
0	0	1
0	1	0
0	$\bot$	$\bot$
1	0	0
1	1	1
1	$\bot$	$\bot$
$\bot$	0	$\bot$
$\bot$	1	$\bot$
$\bot$	$\bot$	$\bot$

p	q	(p $\rightarrow$ q)	(q $\rightarrow$ p)	((p $\rightarrow$ q)$\wedge$(q $\rightarrow$ p))
0	0	1	1	1
0	1	1	0	0
0	$\bot$	1	$\bot$	$\bot$
1	0	0	1	0
1	1	1	1	1
1	$\bot$	$\bot$	$\bot$	$\bot$
$\bot$	0	$\bot$	1	$\bot$
$\bot$	1	$\bot$	$\bot$	$\bot$
$\bot$	$\bot$	$\bot$	$\bot$	$\bot$

p	q	(p $\rightarrow$ q)	(q $\rightarrow$ p)	((q $\rightarrow$ p)$\wedge$(p $\rightarrow$ q))
0	0	1	1	1
0	1	1	0	0
0	$\bot$	1	$\bot$	$\bot$
1	0	0	1	0
1	1	1	1	1
1	$\bot$	$\bot$	$\bot$	$\bot$
$\bot$	0	$\bot$	1	$\bot$
$\bot$	1	$\bot$	$\bot$	$\bot$
$\bot$	$\bot$	$\bot$	$\bot$	$\bot$

Es claro que tienen las mismas tablas de verdad.

Ejercicio 17

Sean p, q y r tres variables de las que se sabe que:

• p y q nunca están indefinidas
• r se indefine sii q es verdadera

Proponer una fórmula que nunca se indefina, utilizando siempre las tres variables y que sea verdadera si se cumple que:

a) Al menos una de las variables es verdadera.
b) Ninguna es verdadera.
c) Exactamente una de las tres es verdadera.
d) Solo p y q son verdaderas
e) No todas al mismo tiempo son verdaderas.
f) r es verdadera.

a) Al menos una de las variables es verdadera.

(p $\vee$ q $\vee$ r)

Si p es verdadera, podemos asegurar que todo es verdadero. Si q lo es, r se indefine, pero antes de llegar a evaluarla se define la fórmula con valor verdadero. Si r es verdadero, llega a r sin ningún problema porque p y q nunca se indefinen, y la disyunción toma valor verdadero.

b) Ninguna es verdadera
Primero pensemos cuáles son los valores posibles que pueden tomar las variables. Recordemos que que en la lógica trivaluada lo que no es True no necesariamente es False (podría ser indefinido). Como p y q no se indefinen (porque nos dijeron en el enunciado) tenemos que valen False. A su vez sabemos que r se indefine sii q es True. Pero q es False, por lo anterior, entonces r no se indefine. Si r no se indefine el hecho de que r no sea True significa que r toma valor False

Por lo tanto bajo ESTAS hipótesis si ninguno es True es porque son todos False. Una fórmula que se hace True con estos valores de p q y r es:

($\neg$p $\wedge \neg$ q $\wedge \neg$ r)

c) Exactamente una de las tres es verdadera.
Analicemos de vuelta cuáles son los valores posibles que pueden tomar las variables: Caso 1: p es True Si el que es True es p, el resto NO es True (recordemos que eso no es lo mismo que ser False). La variable q nunca se indefine, entonces, como no es verdadera ni se indefine, sólo puede suceder que sea False. Además r se indefine sii q es verdadero. Pero q es false, entonces r no se indefine. Y además r no era True (porque el que era True es p), por lo tanto sólo es posible que r sea False. Entonces, si p es True el resto es False.

Caso 2: q es True Si q es True, el resto NO es True. Como p no se indefine, entonces es False. Y r se indefine en caso de que q sea True. Por lo tanto: si q es True, p es False y r se indefine.

Caso 3: r es True Si r es True, el resto NO es True. Pero sabemos que q y p no se indefinen. Entonces toman valor False. si r es True, el resto es False.

Proponemos esta fórmula: ((p $\rightarrow \neg$q )$\wedge$ (q $\rightarrow \neg$p) $\wedge$ (r $\rightarrow \neg$p))

Notese que es verdadera sii una sola de las variables es True.

d) Solo p y q son verdaderas Si q es verdaderas, r se indefine. Por lo tanto podríamos usar la siguiente fórmula:

((p $\vee$ r) $\wedge$ (q $\vee$ r))

e) No todas al mismo tiempo son verdaderas ¿Cuáles son las combinaciones de valores para p q y r que cumplen esto? Todas. Ya que nunca pueden ser todas verdaderas, porque si q es verdadera r se indefine. Por lo tanto cualquier fórmula que sea True funciona. Por ejemplo:

((p $\vee \neg$p) $\wedge$ (q $\vee \neg$q) $\wedge$ r)

Es claro que nunca se llega a evaluar ni el segundo ni el tercer término. Pero el enunciado pide explícitamente que se usen todas las variables.

f) r es verdadero Si r es verdadero, entonces no está indefinido. Por lo tanto q es falso. Sobre p no sabemos que puede pasar, así que nombremos cualquier cosa siempre verdadera sobre p como (p $\rightarrow$p):

(r $\wedge \neg$q $\wedge$ (p $\rightarrow$p))