PDF de programación - Tema 2 - Tecnología de la Programación

UNIVERSIDAD DE A CORUÑA
FACULTAD DE INFORMÁTICA

DEPARTAMENTO DE COMPUTACIÓN

Tecnología de la Programación
Tecnología de la Programación

Ingeniería Técnica en Informática de Sistemas
Ingeniería Técnica en Informática de Sistemas

Elena Mª Hernández Pereira
Elena Mª Hernández Pereira

Óscar Fontenla Romero
Óscar Fontenla Romero

Bloque didáctico I: Introducción
Bloque didáctico I: Introducción

Tema 2
Tema 2

oo Título

Título: Predicados
: Predicados
•• Ampliación del concepto de proposición
Ampliación del concepto de proposición
Unidades de contenido
oo Unidades de contenido
•• Extensión del rango de estado
Extensión del rango de estado
Cuantificadores
•• Cuantificadores
Identificadores libres y ligados
Identificadores libres y ligados
••
•• Sustitución textual
Sustitución textual

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

22

1

Tema 2: Predicados
Tema 2: Predicados

Sintaxis
Sintaxis

Bloque didáctico I:

Introducción

, , "

, , N

Generalización de una proposición:
oo Generalización de una proposición:
Se incluyen como identificadores expresiones relacionales o
•• Se incluyen como identificadores expresiones relacionales o
aritméticas
aritméticas
Se incluyen cuantificadores: $
•• Se incluyen cuantificadores:
Predicados: Expresiones resultantes de la generalización
oo Predicados: Expresiones resultantes de la generalización
, , £
Predicados binarios: ‡
, , <<, , >>, , ==, , „
•• Predicados binarios:
, *, /
•• Funciones binarias: +,
Funciones binarias: +, --, *, /
Función unaria: --
•• Función unaria:
•• Constantes: 0, 1, 2,
Constantes: 0, 1, 2, --1, T, F
1, T, F
Precedencia de operadores habitual
oo Precedencia de operadores habitual
•• Todos tienen mayor prioridad que los operadores lógicos
Todos tienen mayor prioridad que los operadores lógicos

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

33

Tema 2: Predicados
Tema 2: Predicados

Semántica
Semántica

Bloque didáctico I:

Introducción

Ej: Valores ={0,1,2,--1,1,--2,T, F, ...}
2,T, F, ...}

oo Cada ID tiene un tipo

Partimos de un conjunto de valores constantes
oo Partimos de un conjunto de valores constantes
•• Ej: Valores ={0,1,2,
Cada ID tiene un tipo ⇒⇒ Conjunto de valores a los que
Conjunto de valores a los que
está asociado
está asociado ⇒⇒ Rango
Rango
def
••
def
def

i : boolean rango(i)={T, F}
i : boolean rango(i)={T, F}
i : natural rango(i)={0, 1, 2, ...}
i : natural rango(i)={0, 1, 2, ...}
i : integer rango(i)={..., --2, 2, --1, 0, 1, 2, ...}
i : integer rango(i)={...,
1, 0, 1, 2, ...}

••
oo Definición
Definición
•• Un Un estado
•• Se puede representar como un conjunto de pares

s: ID fifi
, es una función del tipo s: ID

Se puede representar como un conjunto de pares (i, v)
modo que v v ˛˛
modo que

estado ss, es una función del tipo

rango(i)
rango(i)

••

Valores
Valores

(i, v) de de

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

44

2

$
"
N
‡
£
„
Tema 2: Predicados
Tema 2: Predicados

Semántica
Semántica

Bloque didáctico I:

Introducción

rango(x) = {0, 1, 2}
rango(x) = {0, 1, 2}
s={(x, 0), (y, --3), (b, F)}
3), (b, F)}

oo Ejemplo
Ejemplo
••
•• s={(x, 0), (y,
oo Definición
Definición
•• Una Una expresión atómica

y: integer
y: integer

b: boolean
b: boolean

expresión atómica es cualquier expresión aritmética
es cualquier expresión aritmética

relacional o función (matemática) conocida, que devuelve T o F
relacional o función (matemática) conocida, que devuelve T o F

Definición
oo Definición
•• Un Un predicado

predicado es el resultado de reemplazar cualquier
es el resultado de reemplazar cualquier

identificador por una expresión atómica en una proposición
identificador por una expresión atómica en una proposición

oo Ejemplos de predicados:
Ejemplos de predicados:
(x + y < z)
(x + y < z)
••

(x (x £
(x (x £

y y
y y

(y < z))
(y < z))
y < z)
y < z)

••

x + y < z
x + y < z

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

55

Tema 2: Predicados
Tema 2: Predicados

Semántica
Semántica

Bloque didáctico I:

Introducción

oo Definición:

Definición: Evaluación de un predicado
Evaluación de un predicado
•• Sea Sea aa una función proposicional bien definida en el estado

una función proposicional bien definida en el estado s, s,
por s(x) y
por s(x) y

reemplazando todo x de a
se obtiene reemplazando todo x de

entonces s(s(aa ) ) se obtiene
entonces
aplicando las operaciones predefinidas
aplicando las operaciones predefinidas

oo Ejemplo
Ejemplo

 Siendo s = {(x, 0), (y,
s(b s(b

Siendo s = {(x, 0), (y, --3), (b, F)} evaluar
3), (b, F)} evaluar
s(x > y
s(x > y
s(x s(x „
0 0

y/x = 2)
y/x = 2)

b)b)

x+y = --3 3 ⇒⇒ y+3 = 2 * x)
x+y =
y+3 = 2 * x)

oo

¿Cómo se resuelve --3/0?3/0?

Problema: La expresión debería ser F pero
oo Problema: La expresión debería ser F pero
•• ¿Cómo se resuelve
Introducimos un nuevo valor: U (“undefined”)
Introducimos un nuevo valor:
U (“undefined”)
•• Para cualquier
En las tablas de operadores vistas, si un término es U, el
oo En las tablas de operadores vistas, si un término es U, el
resultado también es U
resultado también es U

Para cualquier kk, s(k / 0) = U
, s(k / 0) = U

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

66

3

£


£


a



„

Tema 2: Predicados
Tema 2: Predicados

Semántica
Semántica

Bloque didáctico I:

Introducción

cand Conditional and
Conditional and

Incorporamos dos nuevos operadores
oo Incorporamos dos nuevos operadores
•• cand
•• cor cor Conditional or
Conditional or
cand b
oo a
cand
cor cor b
oo a
oo NOTANOTA

entonces T, en otro caso b
entonces T, en otro caso

si si a

si si a

entonces b
entonces

, en otro caso F
, en otro caso F

••

representa la equivalencia, no se usará dentro
representa la equivalencia, no se usará dentro

de los programas
de los programas
cand y y corcor no son conmutativos
no son conmutativos

•• cand

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

77

Tema 2: Predicados
Tema 2: Predicados

Semántica
Semántica

Bloque didáctico I:

Introducción

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

88

4

a
b
”
”
a
b
a
b
”
”
a
b
a
a
”
”
b
b
Tema 2: Predicados
Tema 2: Predicados

Semántica
Semántica

Bloque didáctico I:

Introducción

cor cor l

)) )) ”
((((a

cand (b
cand (
cor (b
cor (

Leyes de equivalencia
oo Leyes de equivalencia
•• Leyes asociativas
Leyes asociativas
cand l
 ((a
cand
 ((a
)) )) ”
•• Leyes distributivas
Leyes distributivas
)) )) ”
 ((a
((((a
 ((a
)) )) ”
((((a
•• Leyes de De Morgan
Leyes de De Morgan
cor cor
cand
cand

cand b
cand
cor cor b
) ) ”

cor (b
cor (
cand (b
cand (

cand l
cand
cor cor l

((a
((a

) ) ”





((((a
cor cor b

cand b
cand

) cand l
) cand

) cor l
) cor

) )

cor cor b
cand b
cand

) cand (a
) cand (
) cor (a
) cor (

) )

))))

cor cor l
cand l
cand

))))

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

99

Tema 2: Predicados
Tema 2: Predicados

Semántica
Semántica

Bloque didáctico I:

Introducción

oo Leyes de equivalencia
Leyes de equivalencia
•• Ley del medio excluido
Ley del medio excluido
 Si Si a
Ley de contradicción
•• Ley de contradicción
 Si Si a
Leyes de simplificación del corcor

))„
„ U), U), a
•• Leyes de simplificación del

está bien definida (s(a
está bien definida (s(

está bien definida (s(a
está bien definida (s(

))„
„ U), U), a

cor cor a
cor T ”
cor T
cor F ”
cor F
cor (a
cor (









T (si a
T (si

está bien definida)
está bien definida)

cand b
cand

) ) ”

cor cor

TT

cand
cand

FF

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

1010

5

a
b
l
”
a
b
l
a
b
l
”
a
b
l
a
b
l
”
a
b
a
l
a
b
l
”
a
b
a
l


a
b
”

a

a
b

b


a
b
”

a

a
b

b
a
a
a
a

a
”
”
a
a
a
a

a
”
”
a
a
a
”
”
a
a
a
a
”
a
a
a
”
a
a
a
a
a
b
”
a
a
Tema 2: Predicados
Tema 2: Predicados

Semántica
Semántica

Bloque didáctico I:

Introducción

Leyes de equivalencia
oo Leyes de equivalencia
•• Leyes de simplificación del

Leyes de simplificación del cand
cand

cand a
cand
cand T ”
cand T
cand F ”
cand F
cand (a
cand (









F (si a
F (si
) ) ”

cor cor b

está bien definida)
está bien definida)

oo Es posible derivar nuevas leyes
Es posible derivar nuevas leyes
cand b
Ejemplo: a
•• Ejemplo:
cand

cand (b
cand (

) ) ”

((a

) )

((a

cand g
cand

))

Tecnología de la programación -- Elena Hernández & Oscar Fontenla
Tecnología de la programación
Elena Hernández & Oscar Fontenla

1111

Tema 2: Predicados
Tema 2: Predicados

Cuantificadores
Cuantificadores

Bloque didáctico I:

Introducción

Cuantificador existencial
oo Cuantificador existencial
Sean m, n expresiones enteras con m £
•• Sean m, n expresiones enteras con m
mm
••
se puede expresar como
se puede expresar como

… …

donde cada a
nn--1 1 donde cada
I I ˛

m+1m+1
I: m £
(($
I: m

I < n: a
I < n:

(($

II))
•• Rango del identificador
Rango del identific