Edición de «Práctica 1: Lógica Proposicional y Tipos Básicos (Algoritmos I)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 7: | Línea 7: | ||
b) True (Bool)<br> | b) True (Bool)<br> | ||
c) y·y (<math> \mathbb{R}</math>) <br> | c) y·y (<math> \mathbb{R}</math>) <br> | ||
'''d) (z <math>\ | '''d) (z <math>\lor \ \neg</math>z) (Bool)'''<br> | ||
e) x==6 (Bool)<br> | e) x==6 (Bool)<br> | ||
f) x==y (Bool)<br> | f) x==y (Bool)<br> | ||
g) <math>\pi</math>==3 (Bool)<br> | g) <math>\pi</math>==3 (Bool)<br> | ||
h) x + y·2 (<math> \mathbb{R}</math>) <br> | h) x + y·2 (<math> \mathbb{R}</math>) <br> | ||
i) z <math> \ | i) z <math> \land </math> 0==1 (No tiene tipo: faltan los paréntesis)<br> | ||
j) <math>\pi</math>+x (<math> \mathbb{R}</math>) <br> | j) <math>\pi</math>+x (<math> \mathbb{R}</math>) <br> | ||
<br> | <br> | ||
Línea 23: | Línea 23: | ||
a) <math>\pi</math>+1 (Sí)<br> | a) <math>\pi</math>+1 (Sí)<br> | ||
b) z + x (Sí)<br> | b) z + x (Sí)<br> | ||
c) (1==0)<math>\ | c) (1==0)<math>\lor</math>(x==z) (No, faltan los paréntesis)<br> | ||
d) (x+10)==y (Sí)<br> | d) (x+10)==y (Sí)<br> | ||
e) <math>\pi</math>+x (Sí)<br> | e) <math>\pi</math>+x (Sí)<br> | ||
f) (x<math>\ | f) (x<math>\lor</math>y) (No, el operador <math>\lor</math> se aplica a dos bool)<br> | ||
g) <math>\pi</math>==3 (Sí)<br> | g) <math>\pi</math>==3 (Sí)<br> | ||
h) z==(x==y) (Sí, z toma el mismo valor de verdad que x==y)<br> | h) z==(x==y) (Sí, z toma el mismo valor de verdad que x==y)<br> | ||
Línea 34: | Línea 34: | ||
===Ejercicio 3=== | ===Ejercicio 3=== | ||
''' La expresión (3 + 7 == <math>\pi</math> | ''' La expresión (3 + 7 == <math>\pi</math> | ||
− 8) <math>\ | − 8) <math>\land</math> True tiene tipo Bool. Justifique informal, pero detalladamente, el porqué.<br><br> | ||
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<math>\ | 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<math>\land</math>q ), donde p y q son de tipo Bool, es una fórmula bien formada, pero no es válido para p<math>\land</math>q. | ||
El enunciado puede ser reemplazado por este: | El enunciado puede ser reemplazado por este: | ||
''' La expresión ((3 + 7 == <math>\pi</math> | ''' La expresión ((3 + 7 == <math>\pi</math> | ||
− 8) <math>\ | − 8) <math>\land</math> True) tiene tipo Bool. Justifique informal, pero detalladamente, el porqué.<br><br> | ||
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 <math>\ | 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 <math>\land</math> puede aplicarse a dos Bool, y devuelve un tercero. En conclusión: tipa bien y es un Bool. | ||
==Semántica proposicional clásica== | ==Semántica proposicional clásica== | ||
Línea 50: | Línea 50: | ||
a) (p<math>\neg</math>q) (No, el conectivo <math>\neg</math> es unario)<br> | a) (p<math>\neg</math>q) (No, el conectivo <math>\neg</math> es unario)<br> | ||
b) p <math>\ | b) p <math>\lor</math> q <math>\land</math> True (No, el <math>\lor</math> y el <math>\land</math> están bien formados sólo usando paréntesis)<br> | ||
c) (p <math>\rightarrow \neg</math> p <math>\rightarrow</math> 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.)<br> | c) (p <math>\rightarrow \neg</math> p <math>\rightarrow</math> 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.)<br> | ||
d) <math>\neg</math>(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.)<br> | d) <math>\neg</math>(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.)<br> | ||
e) (p <math>\ | e) (p <math>\lor \neg</math>p <math>\land</math> q) (No, los incisos de fórmulas bien formadas no dicen nada respecto de la combinación de <math>\lor</math> y <math>\land</math>. Por lo tanto no está bien formada.)<br> | ||
f)(True <math>\ | f)(True <math>\land</math> True <math>\land</math> True <math>\land \dots</math>) (No, pero sí valdría si fueran FINITOS)<br> | ||
g) (<math>\neg</math>p) (No, ídem d)<br> | g) (<math>\neg</math>p) (No, ídem d)<br> | ||
h) (p <math>\ | h) (p <math>\lor</math> False) (Sí, cumple las reglas de bienformación)<br> | ||
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.)<br><br> | 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.)<br><br> | ||
Línea 63: | Línea 63: | ||
'''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.<br><br> | '''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.<br><br> | ||
a) (<math>\neg</math>a <math>\ | a) (<math>\neg</math>a <math>\lor</math> b) (True)<br> | ||
b) (c <math>\ | b) (c <math>\lor</math> (y <math>\land</math> x) <math>\lor</math> b) (True)<br> | ||
c) <math>\neg</math>(c <math>\ | c) <math>\neg</math>(c <math>\lor</math>y) (False)<br> | ||
d) (<math>\neg</math>(c <math>\ | d) (<math>\neg</math>(c <math>\lor</math>y) <math>\leftrightarrow</math> (<math>\neg</math>c <math>\land \neg</math> y)) (True)<br> | ||
e) ((c <math>\ | e) ((c <math>\lor</math> y) <math>\land</math> (x <math>\lor</math> b)) (True)<br> | ||
f) (((c <math>\ | f) (((c <math>\lor</math> y) <math>\land</math> (x <math>\lor</math> b)) <math>\leftrightarrow </math>(c <math>\lor</math> (y <math>\land</math> x) <math>\lor</math> b)) (True) <br> | ||
g) (<math>\neg</math>c <math>\ | g) (<math>\neg</math>c <math>\land \neg</math>b) (False) <br><br> | ||
===Ejercicio 6=== | ===Ejercicio 6=== | ||
'''Determinar, utilizando tablas de verdad, si las siguientes fórmulas son tautologías, contradicciones o contingencias.<br><br> | '''Determinar, utilizando tablas de verdad, si las siguientes fórmulas son tautologías, contradicciones o contingencias.<br><br> | ||
a) (p <math>\ | a) (p <math>\lor \neg</math>p) (Tautología) <br> | ||
b) (p <math>\ | b) (p <math>\land \neg</math>p) (Contradicción) <br> | ||
c) ((<math>\neg</math>p <math>\ | c) ((<math>\neg</math>p <math>\lor</math> q) <math>\leftrightarrow</math> (p <math>\rightarrow</math> q)) (Tautología) <br> | ||
d) ((p <math>\ | d) ((p <math>\lor</math> q) <math>\rightarrow</math> p) (Contingencia)<br> | ||
e) (<math>\neg</math>(p <math>\ | e) (<math>\neg</math>(p <math>\land</math> q) <math>\leftrightarrow</math> (<math>\neg</math>p <math>\lor \neg</math>q)) (Tautología) <br> | ||
f) (p <math>\rightarrow</math> p) (Tautología) <br> | f) (p <math>\rightarrow</math> p) (Tautología) <br> | ||
g) ((p <math>\ | g) ((p <math>\land</math> q) <math>\rightarrow</math> p) (Tautología) <br> | ||
h) (( p <math>\rightarrow</math> (q <math>\rightarrow</math> r)) <math>\rightarrow</math> ((p <math>\rightarrow</math> q) <math>\rightarrow</math> (p <math>\rightarrow</math> r))) (Tautología) <br> | h) (( p <math>\rightarrow</math> (q <math>\rightarrow</math> r)) <math>\rightarrow</math> ((p <math>\rightarrow</math> q) <math>\rightarrow</math> (p <math>\rightarrow</math> r))) (Tautología) <br> | ||
i) ((p <math>\ | i) ((p <math>\land</math> (q <math>\lor</math> r)) <math>\leftrightarrow</math> ((p <math>\land</math> q)<math>\lor</math> (p <math>\land</math>r))) (Tautología) <br><br> | ||
===Ejercicio 7=== | ===Ejercicio 7=== | ||
Línea 89: | Línea 89: | ||
a) True, False (es más fuerte False)<br> | a) True, False (es más fuerte False)<br> | ||
b) (p <math>\ | b) (p <math>\land</math> q), (p <math>\lor</math> q) (es más fuerte la primera)<br> | ||
c) True, True (son igualmente fuertes)<br> | c) True, True (son igualmente fuertes)<br> | ||
d) p, (p<math>\ | d) p, (p<math>\land</math>q) (es más fuerte la segunda)<br> | ||
e) False, False (son igualmente fuertes)<br> | e) False, False (son igualmente fuertes)<br> | ||
f) p, (p <math>\ | f) p, (p <math>\lor</math> q) (es más fuerte p)<br> | ||
g) p,q (ninguno es más fuerte que otro ya que es contingencia)<br> | g) p,q (ninguno es más fuerte que otro ya que es contingencia)<br> | ||
h) p, (p <math>\rightarrow</math> q) (ídem) <br> | h) p, (p <math>\rightarrow</math> q) (ídem) <br> | ||
Línea 100: | Línea 100: | ||
===Ejercicio 8=== | ===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 <math>\ | '''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 <math>\lor</math> q) tiene la misma tabla de verdad que: (<math>\neg</math>p <math>\land \neg</math>q). | ||
Mostrar que cualquier fórmula de la lógica proposicional que utilice los conectivos: <math>\neg</math> (negación), <math>\ | Mostrar que cualquier fórmula de la lógica proposicional que utilice los conectivos: <math>\neg</math> (negación), <math>\land</math> (conjunción), <math>\lor</math> (disyunción), <math>\rightarrow</math> (implicación), <math>\leftrightarrow</math> (equivalencia) puede reescribirse utilizando sólo los conectivos <math>\neg</math> y <math>\lor</math>.<br><br> | ||
Si logramos escribir la tabla de verdad de cada conectivo usando <math>\neg</math> y <math>\ | Si logramos escribir la tabla de verdad de cada conectivo usando <math>\neg</math> y <math>\lor</math>, entonces cualquier fórmula que use cualquiera de esos conectivos podrá escribirse en función de ellos.<br> | ||
Conjunción: | Conjunción: | ||
(p <math>\ | (p <math>\land</math> q) puede escribirse como <math>\neg</math>(<math>\neg</math>p <math>\lor \neg</math> q)<br> | ||
Esto se prueba fácilmente haciendo la tabla de verdad de cada una y viendo que son iguales, o haciendo la de ((p <math>\ | Esto se prueba fácilmente haciendo la tabla de verdad de cada una y viendo que son iguales, o haciendo la de ((p <math>\land</math> q) <math>\leftrightarrow</math> <math>\neg</math>(<math>\neg</math>p <math>\lor \neg</math> q) y viendo que es tautología.<br> | ||
Implicación: | Implicación: | ||
(p <math>\rightarrow</math> q) puede escribirse como (<math>\neg</math>p <math>\ | (p <math>\rightarrow</math> q) puede escribirse como (<math>\neg</math>p <math>\lor</math> q)<br> | ||
Equivalencia: | Equivalencia: | ||
( p <math>\leftrightarrow</math> q) puede escribirse como <math>\neg</math>(<math>\neg</math>(<math>\neg</math> p <math>\ | ( p <math>\leftrightarrow</math> q) puede escribirse como <math>\neg</math>(<math>\neg</math>(<math>\neg</math> p <math>\lor</math> q) <math>\lor \neg</math> (<math>\neg</math>q <math>\lor</math> p))<br> | ||
Pueden probarse todos de la misma manera, lo dejamos como ejercicio. | Pueden probarse todos de la misma manera, lo dejamos como ejercicio. | ||
Línea 122: | Línea 122: | ||
'''a) Escribir usando lógica proposicional las siguientes oraciones:''' | '''a) Escribir usando lógica proposicional las siguientes oraciones:''' | ||
# "Si es fin de semana, Juan estudia o escucha música, pero no ambas cosas":<br> (<math>f \Rightarrow ((e \ | # "Si es fin de semana, Juan estudia o escucha música, pero no ambas cosas":<br> (<math>f \Rightarrow ((e \lor m) \land \neg(e \land m))</math>) | ||
# "Si no es fin de semana, entonces Juan no estudia":<br>(<math>\neg f \Rightarrow \neg e</math>) | # "Si no es fin de semana, entonces Juan no estudia":<br>(<math>\neg f \Rightarrow \neg e</math>) | ||
# "Cuando Juan estudia los fines de semana, lo hace escuchando música":<br>((<math>e \ | # "Cuando Juan estudia los fines de semana, lo hace escuchando música":<br>((<math>e \land f) \Rightarrow m</math>) | ||
'''b) Asumiendo que valen las tres proposiciones anteriores se puede deducir que Juan no estudia? Justificar usando argumentos de la logica proposicional.''' | '''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 <math>\ | Probar que bajo esas hipótesis Juan no estudia, significa probar que ((1 <math>\land</math> 2 <math>\land</math> 3) <math>\leftrightarrow \neg</math>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. | Dejamos la tabla de verdad como tarea para el dulce hogar. | ||
Línea 152: | Línea 152: | ||
Esto es: probar que (((j <math>\rightarrow</math> c) <math>\ | Esto es: probar que (((j <math>\rightarrow</math> c) <math>\land</math> (j <math>\rightarrow</math> (c <math>\rightarrow</math> g))) <math>\rightarrow</math> (j <math>\rightarrow</math> g)) es verdadero para cualquier valor de j, c y g (otra vez: probar que es tautología). | ||
Va a ser verdadero. | Va a ser verdadero. | ||
Línea 210: | Línea 210: | ||
a) (<math>\neg</math>a <math>\ | a) (<math>\neg</math>a <math>\lor</math> b)<br> | ||
'''Indefinido''' (porque si se llega a evaluar un indefinido se indefine todo)<br> | '''Indefinido''' (porque si se llega a evaluar un indefinido se indefine todo)<br> | ||
b) (c <math>\ | b) (c <math>\lor</math> (y <math>\land</math> x) <math>\lor</math> b)<br> '''Verdadero''' (la semántica de cortocircuito nos permite decidir que una disyunción es verdadera al encontrar el primer valor verdadero)<br> | ||
c) <math>\neg</math>(c <math>\ | c) <math>\neg</math>(c <math>\lor</math>y)<br> '''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)<br> | ||
d) (<math>\neg</math>(c <math>\ | d) (<math>\neg</math>(c <math>\lor</math>y) <math>\leftrightarrow</math> (<math>\neg</math>c <math>\land \neg</math> y)) <br> '''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)<br> | ||
e) ((c <math>\ | e) ((c <math>\lor</math> y) <math>\land</math> (x <math>\lor</math> b)) <br> '''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!)<br> | ||
f) (((c <math>\ | f) (((c <math>\lor</math> y) <math>\land</math> (x <math>\lor</math> b)) <math>\leftrightarrow </math>(c <math>\lor</math> (y <math>\land</math> x) <math>\lor</math> b)) <br> '''Falso''' (la evaluación no se indefine y el resultado que da es Falso)<br> | ||
g) (<math>\neg</math>c <math>\ | g) (<math>\neg</math>c <math>\land \neg</math>b)<br> '''Falso''' (nuevamente podemos asegurar que la conjunción es falsa sin evaluar el término que se indefine)<br> | ||
<br> | <br> | ||
Línea 228: | Línea 228: | ||
===Ejercicio 16=== | ===Ejercicio 16=== | ||
'''A diferencia de lo que sucede en la lógica proposicional clásica, en general no vale que (p<math>\ | '''A diferencia de lo que sucede en la lógica proposicional clásica, en general no vale que (p<math>\land</math>q) es equivalente a (q<math>\land</math>p) cuando admitimos a <math>\bot</math> como valor de verdad. Mostrar que sin embargo (p <math>\leftrightarrow</math> q), ((p <math>\rightarrow</math> q)<math>\land</math>(q <math>\rightarrow</math> p)) y ((q <math>\rightarrow</math> p)<math>\land</math>(p <math>\rightarrow</math> q)) siguen siendo equivalentes.''' | ||
Línea 284: | Línea 284: | ||
! colspan="1"|(p <math>\rightarrow</math> q) | ! colspan="1"|(p <math>\rightarrow</math> q) | ||
! colspan="1"|(q <math>\rightarrow</math> p) | ! colspan="1"|(q <math>\rightarrow</math> p) | ||
! colspan="1"|((p <math>\rightarrow</math> q)<math>\ | ! colspan="1"|((p <math>\rightarrow</math> q)<math>\land</math>(q <math>\rightarrow</math> p)) | ||
|- align="center" | |- align="center" | ||
| colspan="1"|0 | | colspan="1"|0 | ||
Línea 350: | Línea 350: | ||
! colspan="1"|(p <math>\rightarrow</math> q) | ! colspan="1"|(p <math>\rightarrow</math> q) | ||
! colspan="1"|(q <math>\rightarrow</math> p) | ! colspan="1"|(q <math>\rightarrow</math> p) | ||
! colspan="1"|((q <math>\rightarrow</math> p)<math>\ | ! colspan="1"|((q <math>\rightarrow</math> p)<math>\land</math>(p <math>\rightarrow</math> q)) | ||
|- align="center" | |- align="center" | ||
| colspan="1"|0 | | colspan="1"|0 | ||
Línea 432: | Línea 432: | ||
a) Al menos una de las variables es verdadera.<br> | a) Al menos una de las variables es verdadera.<br> | ||
(p <math>\ | (p <math>\lor</math> q <math>\lor</math> r) | ||
Si p es verdadera, podemos asegurar que todo es verdadero. | Si p es verdadera, podemos asegurar que todo es verdadero. | ||
Línea 448: | Línea 448: | ||
Una fórmula que se hace True con estos valores de p q y r es: | Una fórmula que se hace True con estos valores de p q y r es: | ||
(<math>\neg</math>p <math>\ | (<math>\neg</math>p <math>\land \neg</math> q <math>\land \neg</math> r) | ||
c) Exactamente una de las tres es verdadera.<br> | c) Exactamente una de las tres es verdadera.<br> | ||
Línea 465: | Línea 465: | ||
Proponemos esta fórmula: | Proponemos esta fórmula: | ||
((p <math>\rightarrow \neg</math>q )<math>\ | ((p <math>\rightarrow \neg</math>q )<math>\land</math> (q <math>\rightarrow \neg</math>p) <math>\land</math> (r <math>\rightarrow \neg</math>p)) | ||
Notese que es verdadera sii una sola de las variables es True. | Notese que es verdadera sii una sola de las variables es True. | ||
Línea 473: | Línea 473: | ||
Si q es verdaderas, r se indefine. Por lo tanto podríamos usar la siguiente fórmula: | Si q es verdaderas, r se indefine. Por lo tanto podríamos usar la siguiente fórmula: | ||
((p <math>\ | ((p <math>\lor</math> r) <math>\land</math> (q <math>\lor</math> r)) | ||
Línea 480: | Línea 480: | ||
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: | 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 <math>\ | ((p <math>\lor \neg</math>p) <math>\land</math> (q <math>\lor \neg</math>q) <math>\land</math> 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. | 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. | ||
Línea 489: | Línea 489: | ||
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 <math>\rightarrow</math>p): | 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 <math>\rightarrow</math>p): | ||
(r <math>\ | (r <math>\land \neg</math>q <math>\land</math> (p <math>\rightarrow</math>p)) |