Slides TD Parcial1-11-20

Vista previa del material en texto

Otras funciones:
∑
,
∏
, β
I
∑M
i=N E (i) (sumatoria) sobre índices i de tipo int.
I E es alguna expresión de i y es de tipo int o float
I su valor será del mismo tipo que E ;
I se inde�ne si alguno de los términos de la sumatoria es inde�nido.
I Su valor es 0 si el rango de iteración es vacío (N > M)
I
∏M
i=N E (i) (productoria); mismas reglas que la sumatoria.
I Su valor es 1 si el rango de iteración es vacío (N > M)
I β(F ): (de tipo int) vale 1 si la fórmula F es Verdadera y 0 si F es
Falsa; notar que su valor será Inde�nido si F se inde�ne.
N∑
i=1
β(i mód 2 = 0)
Cuenta cuántos números entre 1 y N son pares
1−
M∏
i=N
β(¬esPrimo(i))
Vale 1 si algún número entre N y M es primo
13
Otras funciones: if − then − else − fi
if cond then E1 else E2 fi : equivale al operador ternario de C++:
I E1 y E2 son expresiones de un mismo tipo T
I la expresión vale E1 si cond = Verdadero, E2 si cond = Falso o
Indefinido si la cond se inde�ne;
I si la expresión elegida (E1 o E2) se inde�ne el valor �nal también
será inde�nido.
M∑
i=N
if esPrimo(i) then i2 else 0 �
Calcula la sumatoria de los cuadrados de los primos entre N y M
14
Ejemplos de predicados
Conjetura de Goldbach: Todo número par mayor que 2 se puede
escribir como la suma de dos números primos
(∀n : int) (n > 2 ∧ n mód 2 = 0 =⇒ esSumaDeDosPrimos(n))
El entero n se puede escribir como la suma de dos números primos
esSumaDeDosPrimos(n : int) ≡
(∃p, q : int) esPrimo(p) ∧ esPrimo(q) ∧ n = p + q
El entero n es primo
esPrimo(n : int) ≡ n > 1 ∧ (∀p : int) p ≥ 1 ∧ n mód p = 0 =⇒
p = 1 ∨ p = n
15
Contratos: Pasaje de parámetros
En C++ tenemos pasaje por copia y por referencia. Al escribir contratos
podremos especi�car el valor �nal de cada parámetro pasado por
referencia no constante.
Dada una fracción por su numerador N y su denominador D enteros,
minimizarla, actualizando N y D.
void minimizar_fraccion(int & N, int & D)
Pre: N = N0 ∧ D = D0 ∧ D > 0
Post: (∃M : int) esMCD(M,N0,D0) ∧ N = N0/M ∧ D = D0/M
• N0 y D0 son metavariables: una �foto� del valor inicial de N y D.
• esMCD(A,B,C ) es un predicado auxiliar que será verdadero si A
es el máximo común divisor entre B y C.
Notar que esta especi�cación no dice con qué algoritmo se minimizará la
fracción, sólo dice qué condiciones debe cumplir la salida ND para ser una
minimización correcta de la entrada N0D0 .
16
Expresiones inde�nidas
I La semántica estándar de la Lógica de Primer Orden asume que los
predicados sólo tomarán un valor de verdad Verdadero o Falso.
I Al introducir otros tipos de datos al lenguaje, nos encontraremos con
que ciertas expresiones van a estar inde�nidas:
[1] n > 1 ∧ (∀p : int) n mód p = 0 =⇒ p = 1 ∨ p = n
I En este caso, para p = 0 el predicado se inde�ne.
I Supongamos que quisiéramos arreglarlo así:
[2] n > 1 ∧ (∀p : int) p ≥ 1 ∧ n mód p = 0 =⇒ p = 1 ∨ p = n
I El problema es que, para p = 0, el predicado se sigue inde�niendo,
con lo que no podemos determinar el valor de verdad total.½Pero
queremos poder escribir algo así y determinar su valor de verdad!
Entra en escena la lógica trivaluada.
17
Lógica trivaluada
Para escribir propiedades como [2] de la slide anterior, necesitamos
I introducir en la semántica de la lógica el valor de verdad
indeterminado (lo notamos ⊥, bottom) y
I extender la semántica de los conectivos lógicos para poder razonar
sobre ellos.
x y x ∧ y
V V V
V F F
F V F
F F F
V ⊥ ⊥
F ⊥ F
⊥ ... ⊥
Y lógico
x y x ∨ y
V V V
V F V
F V V
F F F
V ⊥ V
F ⊥ ⊥
⊥ ... ⊥
O lógico
x y x =⇒ y
V V V
V F F
F V V
F F V
V ⊥ ⊥
F ⊥ V
⊥ ... ⊥
Implicación lógica (≡ ¬x ∨ y)
Esta nueva semántica permite escribir, con recaudos, expresiones lógicas
(como [2]) que no se inde�nen si están correctamente escritas.
El nuevo comportamiento se llama �lógica secuencial� y coincide con el
de los operadores &&, ||, and, or del tipo bool de C++. 18
Ejercicios
Especi�car los siguientes problemas:
I Dado un número N positivo, expresarlo como el producto de otros
dos números P y Q.
I Dado un número N, dar un vector con su factorización en números
primos.
I Dado dos vector<char> s1, s2, devolver la cantidad de posiciones
que tienen el mismo caracter en s1 y en s2;
I Dado un vector<int>, modi�carlo sumandole 1 a cada uno de sus
elementos.
19
Entendiendo cuantificadores
I (∀x : int) P(x)
−∞ . . . y P(−2) y P(−1) y P(0) y P(1) y P(2) y . . . ∞
I Si algún P(x) se indefine entonces toda la fórmula se indefine.
I Si la fórmula no se indefine, alcanza con un único int n que cumpla
P(n) ≡ Falso para que toda la fórmula sea Falsa.
I (∃x : int) P(x)
−∞ . . . ó P(−2) ó P(−1) ó P(0) ó P(1) ó P(2) ó . . . ∞
I Si algún P(x) se indefine entonces toda la fórmula se indefine.
I Si la fórmula no se indefine, alcanza con un único int n que cumpla
P(n) ≡ Verdadero para que toda la fórmula sea Verdadera.
2
Entendiendo cuantificadores: ∀
I (∀i : int) (0 ≤ i < |v | =⇒ v [i ] = 2)
I Significa que todas las siguientes fórmulas tienen que ser Verdaderas:
−∞
...
(0 ≤ −2 < |v | =⇒ v [−2] = 2)
(0 ≤ −1 < |v | =⇒ v [−1] = 2)
(0 ≤ 0 < |v | =⇒ v [0] = 2)
(0 ≤ 1 < |v | =⇒ v [1] = 2)
...
(0 ≤ |v | − 2 < |v | =⇒ v [|v | − 2] = 2)
(0 ≤ |v | − 1 < |v | =⇒ v [|v | − 1] = 2)
(0 ≤ |v | < |v | =⇒ v [|v |] = 2)
(0 ≤ |v |+ 1 < |v | =⇒ v [|v |+ 1] = 2)
...
∞ 3
Entendiendo cuantificadores: ∀
I (∀i : int) (0 ≤ i < |v | =⇒ v [i ] = 2)
I Significa que todas las siguientes fórmulas tienen que ser Verdaderas:
−∞
...
Verdadero
Verdadero
v [0] = 2
v [1] = 2
...
v [|v | − 2] = 2
v [|v | − 1] = 2
Verdadero
Verdadero
...
∞ 3