Programación 1 - Práctica 7, segunda parte
1 Jugando al solitario
Entre clase y clase, Francisco suele jugar al solitario nada en su lugar. Este juego se juega con un mazo de N cartas, numeradas del 1 al N. Por ejemplo, para N = 7:
El juego es muy simple. Se mezclan las cartas y se van sacando de a una. Si alguna carta sale en la posición que indica su número, pierde. Por ejemplo, si las cartas salen en el siguiente orden
podemos ver que es un juego perdido, dado que la carta con el número 5 ocupa el quinto lugar en la secuencia. En cambio, la siguiente secuencia es ganadora:
Apasionados por lo entretenido del juego, sus compañeros comienzan a hacer apuestas sobre si Francisco ganará o no la siguiente partida. "Te apuesto un desayuno en el comedor a que Francisco gana", le dice Lautaro a Rocío. Esta, criteriosa, prefiere hacer algunas cuentas antes de decidir si acepta o no la apuesta. Le gustaría conocer si la probabilidad de ganar es mayor a la de perder, para así saber si sería prudente aceptar.
Como Francisco juega con un mazo grande (N = 40), no es razonable analizar una por una todas las posibles ordenaciones del mazo para así saber la proporción exacta de "mazos ganadores" sobre el total. Hay 815915283247897734345611269596115894272000000000 posibles permutaciones de un mazo de 40 cartas. Por otro lado, tratar de encontrar una fórmula exacta para el resultado es un problema combinatorio complicado. Para peor, se están terminando los desayunos en el comedor y hay que tomar una decisión en pocos minutos.
Por suerte para Rocío, ella recuerda que hay un método estadístico que la puede ayudar: El método de Montecarlo. A fin de cuentas, si se llama como un casino, algo de utilidad para juegos debe tener. "Si en pocos segundos yo pudiese jugar miles de veces a este juego, podría aproximar la probabilidad de ganar razonablemente", piensa. Sin más, pone manos en el teclado y escribe un programa que juega miles de partidas del Nada en su lugar, las clasifica en ganadoras o perdedoras, y calcula la proporción de ganadoras sobre el total. Obviamente, lo hace de forma tal que haya una constante N que represente la cantidad de cartas en el mazo, y que si cambiamos el valor de esta constante, obtenemos el resultado para un mazo de N cartas.
Haga como ella, y escriba su propio programa para este problema ¿Le conviene o no aceptar la apuesta de Lautaro?
2 Algo de lógica proposicional
En la lógica clásica, una proposición es un enunciado sobre el que, bajo ciertas reglas preestablecidas, es posible asignarle un valor de verdad: verdadero o falso. Por ejemplo "LCC es una carrera de tres años", "Las naranjas son frutas" y "Santa Fe tiene 19 departamentos" son ejemplos de proposiciones. A partir de proposiciones simples o atómicas se pueden construir, utilizando los conectivos lógicos, nuevas proposiciones más complejas. Por ejemplo "Si Santa Fe tiene 19 departamentos, entonces las naranjas son frutas".
Los operadores lógicos más usados son la
conjunción (
),
disyunción (
),
negación (
),
implicancia (
)
y equivalencia (
).
Cuando trabajamos en lógica clásica, el significado de estos operadorados queda totalmente determinado a partir de su Tabla de verdad. Una tabla de verdad nos dice, para cada posible valor de verdad de las proposiciones más simples, cuál es el valor de verdad de la proposición. Ya vimos algunas tablas de verdad en la práctica 0, tanto para la conjunción (and), disyunción (or) y negación (not). Las siguientes tablas de verdad se corresponden con la implicancia y la equivalencia:
p | q | (p |
#true | #true | #true |
#true | #false | #false |
#false | #true | #true |
#false | #false | #true |
p | q | (p |
#true | #true | #true |
#true | #false | #false |
#false | #true | #false |
#false | #false | #true |
Ejercicio 1. Para comenzar, se pide diseñar dos funciones implica y equivalente, que dados
dos valores booleanos se comporten como la tabla de verdad de los operadores
y , respectivamente.
Cada fila de la tabla de verdad representa una valuación.
Esto es, una posible asignación de
valores de verdad para las variables involucradas en la fórmula.
Observemos que si una fórmula tiene n variables, entonces la tabla de verdad tendrá 
filas.
una tautología, si es verdadera para todas las posibles valuaciones;
una contradicción, si es falsa para todas las posibles valuaciones;
satisfactible, si es verdadera para al menos una valuación;
Consideremos las siguientes fórmulas proposicionales:
No es difícil observar que estas fórmulas son una tautología, una fórmula satisfactible y una contradicción, respectivamente. Sin embargo, como todos sabemos, es mejor verlo a que te lo cuenten: Sería bueno que en este punto se detenga y haga con lápiz y papel la tabla de verdad de cada una de ellas.
Estamos interesados en diseñar los predicados tautología?, contradicción? y satisfactible?, que nos permitan clasificar fórmulas proposicionales. Haremos esto evaluando una fórmula en todas las posibles valuaciones. Es decir, el mismo método que siguen las tablas de verdad.
Para esto, deberíamos ser capaces de:
Poder representar valuaciones
Poder representar fórmulas proposicionales
Poder evaluar una fórmula en una valuación
Representando valuaciones
Para representar una valuación, podemos usar listas de booleanos. Por ejemplo, para la fórmula A, la lista (list #t #f #t) es una valuación posible. Si evaluamos la proposición en esta lista, obtenemos #t.
La lista (list #t #t) es una valuación posible para la fórmula C. Para esta valuación obtendremos #f como resultado.
Cada valuación representa una fila en la tabla de verdad de la proposición.
Ejercicio 2. Diseñe una función que, dado un número natural n, genere todas las posibles valuaciones que existen con n variables proposicionales. Por ejemplo, para n=3 debería devolver:
(list (list #false #false #false) (list #false #false #true) (list #false #true #false) (list #false #true #true) (list #true #false #false) (list #true #false #true) (list #true #true #false) (list #true #true #true))
Representando y evaluando fórmulas
La fórmula proposicional A puede pensarse como una función que, dados
tres valores booleanos a ,b ,c, devuelve el valor booleano que
resulta de sustituir 
por a, 
por b, y
por c.
Es decir, A podría representarse mediante una función de tres argumentos booleanos. Sin embargo, C debería representarse como una función de dos argumentos, puesto que sólo involucra dos variables proposicionales. Para hacer más uniforme la representación, utilizaremos listas de booleanos como argumentos de las fórmulas, y de esta manera podremos representar funciones proposicionales con cualquier cantidad de variables.
Usaremos la siguiente signatura para fórmulas:
List (Boolean) -> Boolean.
Con esta idea, podemos representar la fórmula A como sigue:
; A : List(Boolean) -> Boolean (define (A l) (equivalente (and (implica (first l) (third l)) (implica (second l) (third l))) (implica (or (first l) (second l)) (third l))))
; A : List(Boolean) -> Boolean (define (A l) (let ([p1 (first l)] [p2 (second l)] [p3 (third l)]) (equivalente (and (implica p1 p3) (implica p2 p3)) (implica (or p1 p2) p3))))
Las expresiones let nos permiten asociar uno o más nombres (por ejemplo, p1) a una o más expresiones (por ejemplo, (first l)). Para el ejemplo, los nombres p1, p2 y p3 sólo pueden usarse dentro de la definición de A.
Con esta definición, podemos evaluar:
(A (list #t #t #f)) > #t
Ejercicio 3. Defina funciones B y C para las otras dos fórmulas que aparecen en los ejemplos. Evalúen cada una de ellas en un ejemplo concreto de valuación.
Ejercicio 4. Utlizando los ejercicios anteriores, defina una función evaluar que,
dada una fórmula proposicional P : List (Boolean) -> Boolean y la cantidad
de variables n que utiliza P, devuelva una lista con
booleanos, que son el resultado de evaluar P
en cada una de las posibles valuaciones. Es decir, que devuelva una lista con la última columna de
la tabla de verdad de P.
Ejercicio 5. Diseñe los predicados tautología?, contradicción? y satisfactible?.