PDF de programación - Tema 1 - 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 1
Tema 1

oo Título

Título: Cálculo proposicional
: Cálculo proposicional
•• Nociones básicas de lógica
Nociones básicas de lógica
Unidades de contenido
oo Unidades de contenido
•• Evaluación de proposiciones
Evaluación de proposiciones
Proposiciones como conjuntos de estados
•• Proposiciones como conjuntos de estados
•• Leyes de equivalencia
Leyes de equivalencia

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 1: Cálculo proposicional
Tema 1: Cálculo proposicional

Bloque didáctico I:

Introducción

Proposición: Expresión lógica o booleana
oo Proposición: Expresión lógica o booleana
Gramática
oo Gramática
•• Operandos con valores T o F
Operandos con valores T o F
•• Operadores
Operadores
•• Paréntesis:
Paréntesis:
 Orden de evaluación
Orden de evaluación

Operadores
Operadores

Negación

Conjunción

Disyunción

Implicación

Igualdad

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

not a
and b
or b
imp b

equals b

a ⇒⇒⇒⇒ b
= b

33

Bloque didáctico I:

Introducción

Tema 1: Cálculo proposicional
Tema 1: Cálculo proposicional

oo Partimos de un conjunto de identificadores,
oo Partimos de un conjunto de identificadores,

Partimos de un conjunto de identificadores, IDID
Partimos de un conjunto de identificadores, IDID
•• Ej: Ej: IDID ={x={x, p, r, c
•• Ej: Ej: IDID ={x={x, p, r, c
, p, r, c}}
, p, r, c}}

o Proposición: Cualquiera de las expresiones
o Proposición: Cualquiera de las expresiones

• T, F, p,
• T, F, p,

, a
, a

, a
, a

, a ⇒ b
, a ⇒ b

, a = b y (a )
, a = b y (a )

siendo p un identificador y a
siendo p un identificador y a

• Ejemplos: F, ( T), (T F), (a
• Ejemplos: F, ( T), (T F), (a
• No son: FF, TF, (d
• No son: FF, TF, (d
(b ), l +a
(b ), l +a

, b proposiciones
, b proposiciones
), ((
), ((

)
)

(b ⇒ a ))
(b ⇒ a ))

o Precedencia de operadores:
o Precedencia de operadores:

,
,

,
,

, ⇒, =
, ⇒, =

• Operadores binarios, de izquierda a derecha
• Operadores binarios, de izquierda a derecha

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

44

2

a
a
a



a
a
a
a
a
a
a
a
b
b
b
a
a
a
a



b
b
b
b
a
a
a
a
b
b
b
a
a
a
a



b
b
b
b
a
a
a
a
b
b
b
a
a
a
b
b
b
a
a
a
a
b
b
b
a
a
a
a
b
b
b
a

b

b

b
a

a

b

b

b
a

Tema 1: Cálculo proposicional
Tema 1: Cálculo proposicional

Bloque didáctico I:

Introducción

oo Semántica
Semántica
Función que hace corresponder a cada proposición del
•• Función que hace corresponder a cada proposición del
lenguaje un elemento del conjunto {T, F}
lenguaje un elemento del conjunto {T, F}

oo Evaluación de proposiciones constantes
Evaluación de proposiciones constantes
•• Proposiciones sin operadores
Proposiciones sin operadores

 T es T y F es F
T es T y F es F

•• Proposiciones con un operador
Proposiciones con un operador

), (), (a
a ⇒⇒ b

) y (a
) y (

= = b

siendo a
) ) siendo

y y b

T o T o FF

((a



), (), (a

 Los valores de estas proposiciones vienen dados por la tabla
Los valores de estas proposiciones vienen dados por la tabla

de verdad de la Transparencia 6
de verdad de la Transparencia 6

•• Proposiciones con más de un operador
Proposiciones con más de un operador

 Aplicar el caso anterior sustituyendo cada

Aplicar el caso anterior sustituyendo cada subproposición
valor
valor

subproposición por su
por su

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

55

Tema 1: Cálculo proposicional
Tema 1: Cálculo proposicional

Bloque didáctico I:

Introducción

•• Proposiciones con un solo operador
Proposiciones con un solo operador

(

) (a

b ) (a

b ) (a

a ⇒⇒⇒⇒ b

b ) (a

F F

F T

T F

T T

T

T

F

F

F

F

F

T

F

T

T

T

T

T

F

T

= b

b )

T

F

F

T

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


b
b
a


b
b
b
a
b
a
b
a
a
a
a
b
b
b
b
a

a

a

a
a
a
a



b
b
b
a
a
a



b
b
b
a
a
b
b
a
a
a
b
b
Tema 1: Cálculo proposicional
Tema 1: Cálculo proposicional

Bloque didáctico I:

Introducción

= F= F

) siendo a
) ) ⇒⇒ b
= T y b
= T y
) siendo
F) = (T ⇒⇒ F) = F
T) T) ⇒⇒ F) = (T
F) = F
) siendo a
) siendo
= T= T
T) = (T
T) = (T

= F y b
= F y
T) = T
T) = T

••

oo Ejemplos
Ejemplos
••

((((a
((T
 ((T
((((
))
 ((((
oo NOTA:
NOTA:
•• Tablas de verdad
•• oror dentota

F) F)

Tablas de verdad ⇒⇒ Valores finitos
Valores finitos
T) = T
T) = T

or inclusivo ⇒⇒ (T (T

dentota or inclusivo

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

77

Tema 1: Cálculo proposicional
Tema 1: Cálculo proposicional

Bloque didáctico I:

Introducción

estado ss es una función del tipo s:

es una función del tipo s: IDID fi

Definición
oo Definición
•• Un Un estado
Se puede representar como un conjunto de pares
•• Se puede representar como un conjunto de pares
(id, valor)
(id, valor)
Ejemplo: si s={(a, T), (bcbc, F), (y1, T)} entonces
, F), (y1, T)} entonces
s(a) = T, s(
s(a) = T, s(bcbc)=F y s(y1)

•• Ejemplo: si s={(a, T), (

)=F y s(y1) = T= T

{T, F}
{T, F}

Definición
oo Definición
proposición a
•• Una Una proposición

está
está bien definida

bien definida en el estado
en el estado ss

si y sólo si para todo identificador pp en en a
si y sólo si para todo identificador
(p, v) ˛
(p, v)

ss

, existe
, existe

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


a
a
b
a
b

a

a

b
b
a
b



fi
a
a
˛
Tema 1: Cálculo proposicional
Tema 1: Cálculo proposicional

Bloque didáctico I:

Introducción

Definición
oo Definición
•• Sea Sea aa una proposición bien definida en el estado

una proposición bien definida en el estado ss. El

valor de aa
. El valor de
, es el valor obtenido al reemplazar todos los identificadores
en en ss, es el valor obtenido al reemplazar todos los identificadores
de de aa por su valor y evaluar la proposición constante resultante
por su valor y evaluar la proposición constante resultante

oo Ejemplo
Ejemplo

Evaluar s(((
 Evaluar s(((

) )

)) en el estado s={(b
)) en el estado s={(

, T), (d
, T), (

, F)}
, F)}

oo Definición
Definición
•• Una Una tautología

que esté bien definida, ss((a
que esté bien definida,

) = T) = T

es cualquier proposición a
tautología es cualquier proposición

tal que, para todo
tal que, para todo ss en en

oo Ejemplos
Ejemplos
 T, p T, p

p, b
p, b

c c

d d ⇒⇒ (d (d ⇒⇒ b)b)

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

99

Tema 1: Cálculo proposicional
Tema 1: Cálculo proposicional

Bloque didáctico I:

Introducción

es una tautología
es una tautología

no es una tautología
no es una tautología
Encontrar un contraejemplo
contraejemplo

Probar que a
oo Probar que
•• Demostrar que es cierta en todos los estados
Demostrar que es cierta en todos los estados
Probar que a
oo Probar que
•• Encontrar un
oo Utilidad
Utilidad
•• Una proposición representa un conjunto de estados,
Una proposición representa un conjunto de estados,
EST(EST(aa ), que la hacen cierta
{s | s(aa ) = T}
{s | s(
) = T}
), que la hacen cierta
•• A partir de un conjunto de estados con identificadores
A partir de un conjunto de estados con identificadores
asociados a T o F, se puede derivar una proposición
asociados a T o F, se puede derivar una proposición

aa

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

1010

5

b

b

d
d
b
d
a
a



a
a
fi
fi
Tema 1: Cálculo proposicional
Tema 1: Cálculo proposicional

Bloque didáctico I:

Introducción

oo Definición
Definición
que b
es más fuerte
fuerte que
es más
••
EST(EST(b
))

EST(EST(a
En ese caso b
•• En ese caso
es más débil
es más
a más fuerte impone

oo Una Una a

) ) ˝

si si a
a ⇒⇒ b

más fuerte impone más restricciones

que a
débil que
más restricciones en la
en la

, es decir
, es decir

combinación de valores con los que sus
combinación de valores con los que sus
identificadores están asociados
identificadores están asociados
¿Cuál es la proposición más débil?
•• ¿Cuál es la proposición más débil?
•• ¿ y cuál la más fuerte?
¿ y cuál la más fuerte?

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

1111

Tema 1: Cálculo proposicional
Tema 1: Cálculo