tema 2 logica proposicional

17
Docente: Eva Patricia Vásquez Gómez Lógica Proposicional 1 CAPITULO I 1.1 LOGICA Las reglas de la lógica le dan un significado preciso a los enunciados matemáticos o sentencias matemáticas. Estas reglas se usan para distinguir entre argumentos válidos y no válidos. Además de su importancia en el razonamiento matemático, la lógica tiene numerosas aplicaciones en ciencias de la computación. Las reglas de la lógica se usan en el diseño de circuitos de computador, la construcción de programas informáticos, la verificación de que un programa está bien construido y en muchas otras aplicaciones. Cada una de ellas las iremos viendo a lo largo del semestre. PROPOSICIONES Comenzaremos con una introducción a la construcción de los bloques básicos de la lógica: las proposiciones. Una proposición es una oración declarativa que es correcta o falsa, pero no ambas a la vez. EJEMPLO 1 Todas las siguientes oraciones declarativas son proposiciones: 1. Bogotá es la capital de Colombia. 2. Nueva York es la capital de Estados Unidos. 3. 1+1=2 4. 2+2=3 Las proposiciones 1 y 3 son correctas, mientras que la 2 y 4 son falsas. EJEMPLO 2 Considera las siguientes oraciones: 1. Que hora es? 2. Lee esto con atención 3. X+1=2 4. X+y=z Las frases 1 y 2 no son proposiciones porque no son declarativas. Las frases 3 y 4 no son proposiciones porque no son ni verdaderas ni falsas, ya que no se les han asignado valores a las variables.

Upload: eva-vasquez

Post on 12-Jun-2015

2.933 views

Category:

Documents


1 download

DESCRIPTION

Bibliografia: Matemáticas discretas y sus aplicaciones - Kenneth H. Rosen

TRANSCRIPT

Page 1: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

1

CAPITULO I

1.1 LOGICA

Las reglas de la lógica le dan un significado preciso a los enunciados matemáticos o sentencias

matemáticas. Estas reglas se usan para distinguir entre argumentos válidos y no válidos.

Además de su importancia en el razonamiento matemático, la lógica tiene numerosas aplicaciones

en ciencias de la computación. Las reglas de la lógica se usan en el diseño de circuitos de

computador, la construcción de programas informáticos, la verificación de que un programa está

bien construido y en muchas otras aplicaciones. Cada una de ellas las iremos viendo a lo largo del

semestre.

PROPOSICIONES

Comenzaremos con una introducción a la construcción de los bloques básicos de la lógica: las

proposiciones. Una proposición es una oración declarativa que es correcta o falsa, pero no ambas

a la vez.

EJEMPLO 1 Todas las siguientes oraciones declarativas son proposiciones:

1. Bogotá es la capital de Colombia.

2. Nueva York es la capital de Estados Unidos.

3. 1+1=2

4. 2+2=3

Las proposiciones 1 y 3 son correctas, mientras que la 2 y 4 son falsas.

EJEMPLO 2 Considera las siguientes oraciones:

1. Que hora es?

2. Lee esto con atención

3. X+1=2

4. X+y=z

Las frases 1 y 2 no son proposiciones porque no son declarativas. Las frases 3 y 4 no son

proposiciones porque no son ni verdaderas ni falsas, ya que no se les han asignado valores a las

variables.

Page 2: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

2

Para denotar proposiciones usamos letras, al igual que usamos letras para denotar variables. Por

convenio, las letras que se utilizan para denotar proposiciones son p, q, r, s, … El valor de verdad

de una proposición es verdadero, y se denota por V, si es una proposición verdadera, o falso,

denotado por F, si es una proposición falsa.

El área de la lógica que trata de proposiciones se llama cálculo proposicional o lógica

proposicional. Fue desarrollada por primera vez por el filósofo griego Aristóteles hace más de dos

mil trescientos años.

Podemos producir proposiciones nuevas a partir de las ya existentes. Las nuevas proposiciones,

llamadas fórmulas o proposiciones compuestas, se forman a partir de la existentes usando

operadores lógicos.

DEFINICIÓN 1

Sea p una proposición, El enunciado

“No se cumple p”

Es otra proposición, llamada negación de p. La negación de p se denota mediante ¬p. La

proposición ¬p se lee “no p”.

EJEMPLO 3 Obtén la negación del enunciado “Hoy es sábado” y exprésala del modo más simple

posible.

Solución: La negación es

“No se cumple que hoy es Sábado”.

Esta negación se puede expresar más simplemente por

“Hoy no es Sábado” o “No es sábado hoy”.

Una tabla de verdad muestra las relaciones entre los valores de verdad de proposiciones. Las

tablas de verdad son especialmente valiosas a la hora de determinar los valores de verdad de

proposiciones construidas a partir de proposiciones más simples. La Tabla 1 muestra los dos

posibles valores de verdad de una proposición p y los correspondientes valores de verdad de su

negación ¬p.

Tabla 1.La tabla de verdad para la negación de una

proposición

P ¬p

Page 3: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

3

V

F

F

V

La negación de una proposición se puede considerar como el resultado de aplicar el operador

negación sobre una proposición. El operador negación construye una nueva proposición a partir

de la proposición individual existente. Ahora veremos los operadores lógicos que se usan para

formar nuevas proposiciones a partir de dos o más proposiciones ya creadas. Esos operadores

lógicos se llaman también conectivos lógicos.

DEFINICIÓN 2

Sean p y q proposiciones. La proposición «p y q», denotada por p Λ q, es la proposición que es

verdadera cuando tanto p como q son verdaderas y falsa en cualquier otro caso. La proposición p

Λ q se llama conjunción de p y q.

La tabla de verdad para p Λ q se muestra en la Tabla 2. Observa que hay cuatro filas en esta tabla

de verdad, una fila por cada posible combinación de valores de verdad para las proposiciones p y

q.

Tabla 2. Tabla de verdad de la conjunción de dos proposiciones.

p q p Λ q

V V V

V F F

F V F

F F F

EJEMPLO 4 Obtén la conjunción de las proposiciones p y q en el caso en que p es el enunciado

“Hoy es Sábado” y q es “Hoy llueve”.

Solución: La conjunción de estas proposiciones, p Λ q, es el enunciado “Hoy es sábado y hoy

llueve”. La proposición es verdadera los viernes con lluvia y es falsa cualquier día que no sea

viernes y los viernes que no llueve.

DEFINICION 3

Page 4: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

4

Sean p y q proposiciones. La proposición “p o q”, denotada por p v q, es la proposición que es falsa

cuando tanto p como q son falsas y verdadera en cualquier otro caso. La proposición p v q se llama

disyunción de p y q.

La tabla de verdad para p v q se muestra en la tabla 3.

Tabla 3. Tabla de verdad de la disyunción de dos proposiciones.

p q p v q

V V V

V F V

F V V

F F F

El uso del conectivo lógico o en una disyunción se asocia al significado en sentido inclusivo de la

palabra o*. Una disyunción es verdadera cuando al menos una de las dos proposiciones es

verdadera. Por ejemplo, el o en sentido inclusivo se emplea en el enunciado:

“ Los estudiantes que hayan cursado cálculo o lógica pueden matricularse en esta clase.”

Con esta frase se quiere decir que los estudiantes que han cursado bien cálculo o bien lógica

pueden matricularse en la clase, así como los estudiantes que ha cursado ambas asignaturas. Por

otra parte, estamos usando el o exclusivo cuando decimos:

“Los estudiantes que hayan cursado cálculo o lógica, pero no ambos, pueden matricularse en esta

clase”.

Ahora se quiere expresar que aquellos que hayan cursado tanto cálculo como lógica no pueden

matricularse. Sólo pueden hacerlo aquellos que hayan cursado exactamente una de las dos

asignaturas.

De forma similar, cuan en un menú de restaurante vemos “se sirve sopa o ensalada como

entrante”, casi siempre se quiere decir que los clientes pueden tomar bien sopa o bien ensalada,

pero no ambos. Por tanto, éste es un uso exclusivo no inclusivo de la disyunción o.

EJEMPLO 5 Cual es la disyunción de las proposiciones p y q en el caso en que p y q sean las

proposiciones del ejemplo 4?

Solución: la disyunción de p y q, p v q, es el enunciado

Page 5: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

5

“Hoy es viernes u hoy llueve”

Esta proposición es verdadera cualquier día que sea viernes o llueva (incluido los viernes que

llueve). Es sólo falsa los días que ni son viernes ni llueve.

Una disyunción es verdadera cuando al menos una de las dos proposiciones en ella es verdadera.

A veces usamos el o en sentido exclusivo. Cuando se usa el o en sentido exclusivo para conectar

dos proposiciones p y q, obtenemos la proposición “p o q (pero no ambos)”. Esta proposición es

verdadera cuando p es verdadera y q falsa y cuando p es falsa y q verdadera. Es falsa cuando tanto

p como q son falsas y cuando ambas son verdaderas.

DEFINICION 4

Sean p y q proposiciones. El conectivo lógico o exclusivo de p y q, denotada por p ⊕ q, es la

proposición que es verdadera cuando exactamente una de las dos proposiciones p y q es

verdadera y es falsa en cualquier otro caso.

Tabla 4. Tabla de verdad para el o exlusivo de dos proposiciones.

p q p ⊕ q

V V F

V F V

F V V

F F F

IMPLICACIONES

DEFINICION 5

Sean p y q proposiciones. La implicación p → q es la proposición que es falsa cuando p es

verdadera y q es falsa y verdadera en cualquier otro caso. En esta implicación p se llama hipótesis

(o antecedente o premisa) y q se llama tesis o conclusión (o consecuencia).

Page 6: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

6

Tabla 5. Tabla de verdad de la implicación p → q

p q p → q

V V V

V F F

F V V

F F V

La implicación a veces se denomina declaración condicional.

Expresiones de p → q:

“si p, entonces q”

“si p, q”

“p es suficiente para q”

“q si p”

“p sólo si q” …

La implicación p → q es falsa sólo en el caso de que p sea verdadera y q sea falsa. Es verdadero

cuando tanto p como q son verdaderas y cuando p es falsa (no importa el valor de verdad de q).

Una forma útil de entender el valor de verdad de una implicación es pensar en una obligación o en

un contrato. Por ejemplo, la promesa que muchos políticos hacen por ser votados es:

“si soy elegido, bajaré los impuestos”.

Si el político es elegido, los votantes esperarían del político que bajara los impuestos. Pero si el

político no es elegido, entonces los votantes no esperaran que esa persona baje los impuestos,

aunque puede influir lo suficiente para conseguir que los que ostentan el cargo correspondiente

baje los impuestos. Sólo cuando el político es elegido y no baja los impuestos, pueden decir los

votantes que el políticos ha roto su promesa electoral. El último escenario corresponde al caso en

que p es verdadera, pero q es falsa; por tanto p → q es falsa.

De forma parecida, considera una afirmación en la que el profesor dice:

Page 7: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

7

“Si consigues el ciento por ciento de la puntuación en el último parcial, sacarás un 5.0”.

Si consigues completar correctamente el ciento por ciento de las preguntas, entonces podrías

esperar sacar un 5.0. Si no consigues el ciento por ciento, puedes o no sacar un 5.0 dependiendo

de otros factores. En cualquier caso si completas el ciento por ciento, pero el profesor no te pone

un 5.0 te sentiras engañado.

“Si hoy hace sol, entonces iremos a la playa”

Es una implicación usada comúnmente, ya que hay una relación entre la hipótesis y la conclusión.

Además, esta implicación se considera válida, a no ser que precisamente hoy haga sol, pero que no

vayamos a la playa.

Nuestra definición de implicación específica los valores de verdad; no se basa en el uso del

lenguaje.

La construcción si-entonces se usa en muchos lenguajes de programación de forma diferente que

en lógica. La mayoría de los lenguajes de programación contienen sentencias como if p then S,

donde p es una proposición y S un segmento de programa (una o más sentencias sintácticamente

bien construidas que deben ser ejecutadas). Cuando la ejecución del programa encuentra tal

sentencia, se ejecuta S si p es verdadera, pero S no se ejecuta si p es falsa, como se ilustra en el

siguiente ejemplo.

EJEMPLO 6 Cuál es el valor de la variable x tras la sentencia

If 2 + 2 = 4 then x:= x+1

Si x = 0 antes de llegar a la sentencia? (El símbolo := corresponde a la asignación. La sentencia

x:=x+1 significa que a x se le asigna el valor x + 1).

Solución: Como 2+2=4 es verdadera, se ejecuta la sentencia de asignación x:=x+1. Por tanto, x

toma el valor 0+1=1 tras la sentencia.

RECIPROCA, CONTRARRECIPROCA E INVERSA

Hay algunas implicaciones relacionadas con p → q que pueden formarse a partir de ella. La

proposición q → p se llama recíproca de p → q. La contrarrecíproca de p → q es ¬q → ¬p. la

proposición ¬p → ¬q es la inversa de p → q.

EJEMPLO 7 Cuáles son las contrarrecíproca, recíproca e inversa de la implicación?

“El equipo local gana siempre que llueve”.

Page 8: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

8

Solución: Como “q siempre que p” es una forma de expresar la implicación p → q, la afirmación

original se puede reescribir como

“Si llueve, entonces el equipo local gana”.

La contrarrecíproca de esta implicación es

“Si el equipo local no gana, no llueve”.

La recíproca es

“Si el equipo local gana, entonces llueve”.

La inversa es

“Si no llueve, entonces el equipo local no gana”.

DEFINICION 6 sean p y q proposiciones. La bicondicional, o doble implicación, p↔q es la

proposición que es verdadera cuando p y q tienen los mismos valores de verdad y falsa en los

otros casos.

Tabla 6. Tabla de verdad de la bicondicional p ↔ q

p q p ↔ q

V V V

V F F

F V F

F F V

La doble implicación es verdadera precisamente cuando las implicaciones p → q y q → p son

verdaderas. Debido a esto la terminología

“p si, y sólo si, q”

EJEMPLO 8 Sea p la afirmación “ Puedes tomar el vuelo” y sea q la afirmación “Compras un

tiquete”. Entonces p ↔ q es el enunciado

“Puedes tomar el vuelo si, y sólo si, compras el billete”.

Page 9: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

9

Esta afirmación es verdadera si p y q son ambas verdaderas o ambas falsas, esto es, si compras un

tiquete y puedes tomar el vuelo o si no compras el billete y no puedes tomar el vuelo. Es falsa

cuando p y q tienen valores de verdad opuestos, es decir, cuando no compras el tiquete, pero

puedes tomar el vuelo, y cuando compras el tiquete y no puedes tomar el vuelo.

PRECEDENCIA DE OPERADORES LOGICOS

Podemos construir fórmulas usando el operador negación y los operadores lógicos definidos hasta

el momento. Generalmente, utilizaremos paréntesis para especificar el orden en el que deben

aplicarse los operadores lógicos en una fórmula. Por ejemplo, (p v q) Λ (¬r) es la conjunción de p v

q y ¬r. Sin embargo, para reducir el número de paréntesis, especificamos que el operador de

negación se aplica antes que los operadores lógicos. Esto significa que el operador negación ¬p Λ q

es la conjunción de ¬p Λ q, es decir, (¬p )Λ q, no la negación de la conjunción de p y q, es decir ¬(p

Λ q).

Otra regla general de precedencia es que el operador conjunción precede siempre al operador

disyunción, de tal forma que p Λ q v r significa (p Λ q) v r y no p Λ (q v r). Debido a que esta regla

es difícil de recordar seguiremos usando paréntesis para que quede claro el orden utilizado en los

operadores conjunción y disyunción.

Finalmente, es una regla aceptada que los operadores condicional → y bicondicional ↔ tienen

precedencia inferior que los operadores de conjunción y disyunción, consecuentemente p v q → r

es lo mismo que (p v q) → r.

Tabla 7. Precedencia de los operadores lógicos.

Operador Precedencia

¬ 1

Λ

V

2

3

4

5

TRADUCCIÓN DE FRASES DEL LENGUAJE NATURAL

Page 10: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

10

Hay muchas razones para traducir del lenguaje natural a expresiones con variables proposicionales

y conectivos lógicos. Todos los lenguajes son ambiguos. Trasladar frases a expresiones lógicas trae

consigo evitar esas ambigüedades. Una vez que hemos traducido frases del lenguaje natural a

expresiones lógicas, podemos analizar estas expresiones lógicas para determinar sus valores de

verdad, las podemos manipular y podemos usar las reglas de inferencia (que veremos en otra

clase). El paso del lenguaje natural al lenguaje formal se conoce como formalización.

EJEMPLO 9 Cuál es la formalización de la siguiente frase?

“Puedes acceder a Internet desde el campus sólo si estudias Ingeniería de Sistemas o no eres

alumno de primer semestre”.

Solución: Hay muchas formas de formalizar esta frase. Aunque es posible representar la frase

mediante una variable proposicional simple, como p, no sería útil para analizar su significado o

razonar con ella. Así, utilizaremos variables proposicionales para representar cada parte de la

oración y determinar los conectivos lógicos apropiados entre ellas. En particular, representaremos

las frases “Puedes acceder a Internet desde el Campus”, “Estudias Ingenieria de sistemas” y “eres

alumno de primer semestre” por a, c y f, respectivamente. Considerando que “solo si” es una

forma de expresar una implicación, la frase se puede representar como

a →(c v ¬f)

EJEMPLO 10 Como se puede formalizar la siguiente frase?

“No puedes montar en la montaña rusa si mides menos de 1,20 cms, a no ser que seas mayor de

16 años”.

ESPECIFICACIONES DE SISTEMA

Traducir oraciones del lenguaje natural, como el español, a expresiones lógicas es una parte

esencial de la especificación tanto de sistemas hardware como software. Los ingenieros de

sistemas reciben los requerimientos en lenguaje natural y producen especificaciones precisas y sin

ambigüedades que pueden usarse como base para desarrollo de sistemas.

EJEMPLO 11 expresa la especificación “La respuesta automatizada no se puede enviar cuando el

sistema de archivos está lleno”.

Solución: Una forma posible de traducir esto es denotar como p a “La respuesta automatizada se

puede enviar” y como q a “El sistema de archivos está lleno”, Entonces, ¬p representa a “ no se

cumple que la respuesta automatizada no se puede enviar”, lo que se puede expresar como “La

Page 11: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

11

respuesta automatizada no se puede enviar”. Consecuentemente, nuestra especificación se puede

representar mediante la implicación q → ¬p.

Las especificaciones de sistema no deberían contener requerimientos que puedan entrar en

conflicto. Si así fuese, no habría forma de desarrollar un sistema que cumpliese todas las

especificaciones. Por tanto, las expresiones proposicionales que representan esas especificaciones

necesitan ser consistentes.

Page 12: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

12

EJERCICIOS CLASE 1

1. ¿Cuáles de estas frases son proposiciones? ¿Cuál es el valor de verdad de aquellas que son

proposiciones?

a. Medellín es la capital del Atlántico.

b. Buenos Aires es la capital de Argentina.

c. 2 + 3 = 5.

d. 5 + 7 = 10.

e. X + 2 = 11.

f. Responde a esta pregunta.

g. X + y = y + x para todo par de números reales x e y.

2. ¿Cuál es la negación de cada uno de estos enunciados?

a. Hoy es Jueves.

b. No hay polución en Bogotá.

c. 2 + 1 = 3.

d. El verano de Europa es cálido y soleado.

3. Sean p y q los enunciados “Está permitido nadar en la costa de Cartagena” y “Se han

divisado tiburones cerca de la costa”, respectivamente. Expresa cada una de las siguientes

fórmulas en lenguaje natural.

a. ¬q

b. p Λ ¬q

c. ¬p V q

d. p → ¬q

e. ¬q → p

f. ¬p → ¬q

g. P ↔ ¬q

Page 13: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

13

h. ¬p Λ (p V q)

4. Sean p y q los enunciados

P: Estamos bajo cero.

q: Nieva.

Escribe los enunciados siguientes usando p, q y conectivos lógicos:

a. Estamos bajo cero y nieva.

b. Estamos bajo cero, pero no nieva.

c. No estamos bajo cero y no nieva.

d. Bien estamos bajo cero o bien nieva (o ambas cosas).

e. Si estamos bajo cero, entonces también nieva.

f. Estamos bajo cero o nieva, pero no nieva si estamos bajo cero.

g. Que estemos bajo cero es necesario y suficiente para que nieve.

5. Sean p y q los enunciados

P: Conduces a más de 100 Km por hora.

q: Te multan por exceso de velocidad.

Escribe los enunciados siguientes usando p, q y conectivos lógicos.

a. No conduces a más de 100 Km por hora.

b. Conduces a más de 100 Km por hora, pero no te multan por exceso de velocidad.

c. Te multarán por exceso de velocidad si conduces a más de 100 km por hora.

d. Si no conduces a más de 100 km por hora no te multarán por exceso de velocidad.

e. Conducir a más de 100 km por hora es suficiente para que te multen por exceso de

velocidad.

f. Te multan por exceso de velocidad, pero no conduces a más de 100 km por hora.

g. Siempre que te multen por exceso de velocidad conduces a más de 100 km por hora.

Page 14: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

14

6. Sean p, q y r los enunciados

p: Se han visto perros salvajes por la zona.

q: Es seguro caminar por el sendero.

r: Las frutas del sendero están maduras.

Expresa estos enunciados usando p, q, r y conectivos lógicos.

a. Las frutas del sendero están maduras, pero no se han visto perros salvajes por la zona.

b. No se han visto perros salvajes por la zona y es seguro caminar por el sendero, pero

las frutas del sendero, pero las frutas del sendero están maduras.

c. Si las frutas del sendero están maduras, es seguro caminar por el sendero si, y sólo si,

no se han visto perros salvajes por la zona.

d. No es seguro caminar por el sendero, pero no se han visto perros salvajes por la zona y

las frutas del sendero están maduras.

e. Para que sea seguro caminar por el sendero, es necesario, pero no suficiente, que las

frutas del sendero no estén maduras y que no se hayan visto perros salvajes por la

zona.

f. No es seguro caminar por el sendero cuando se han visto perros salvajes por la zona y

las frutas del sendero están maduras.

7. Determina si estas implicaciones son verdaderas y falsas.

a. Si 1 + 1 = 2, entonces 2 + 2 = 5.

b. Si 1 + 1 = 3, entonces 2 + 2 = 4.

c. Si 1 + 1 = 3, entonces 2 + 2 = 5.

d. Si los cerdos vuelan, entonces 1 + 1 = 3.

e. Si 1 + 1 = 3, entonces Dios existe.

f. Si 1 + 1 = 3, entonces los cerdos vuelan.

g. Si 1 + 1 = 2, entonces los cerdos vuelan.

Page 15: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

15

h. Si 2 + 2 = 4, entonces 1 + 2 = 3.

8. Di qué significan cada una de estas frases en los casos en que el o es inclusivo o bien

exclusivo. ¿Cuál crees que el significado que se quiere expresar realmente en cada caso?

a. Para matricularte en matemática discreta debes hacer cursado una asignatura de

cálculo o alguna asignatura de informática.

b. Cuando te compras un vehículo de marca Acme, te devuelven $4,000.000 en efectivo

o el 2% del préstamos solicitado.

c. La cena para dos incluye dos platos de la columna A o tres de la columna B.

9. Escribe cada uno de estos enunciados de la forma “si p, entonces q”.

a. El manzano florecerá si el tiempo se mantiene cálido durante una semana.

b. Que Millonarios gane el partido implica que vencieron a Santafé.

c. Es necesario andar 12 km para llegar a la cima del pico.

d. Para ser profesor fijo es suficiente con ser mundialmente famoso.

e. Tu garantía es válida sólo si compraste el reproductor mp3 hace menos de 90 días.

10. Escribe cada uno de estos enunciados de la forma “p si, y sólo si, q”.

a. Si hace calor fuera, te compras un helado, y si te compras un helado, hace calor fuera.

b. Para ganar el concurso es necesario y suficiente tener el número ganador.

c. Ascenderás sólo si tienes contactos, y tienes contactos sólo si asciendes.

d. Si ves televisión, tu mente se empobrecerá, y recíprocamente.

e. El bus llega con retraso exactamente aquellos días que tengo que tomarlo.

11. Enuncia la recíproca,, contrarrecíproca e inversa de cada una de estas implicaciones.

a. Si llueve esta noche, me quedaré en casa.

b. Voy a la playa siempre que el día amanezca soleado.

c. Cuando me acuesto tarde, es necesario que duerma hasta mediodía.

12. Construye las tablas de verdad para cada una de estas fórmulas.

Page 16: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

16

a. p → ¬p

b. p V ¬p

c. (p V ¬q) → q

d. (p V q) → (p Λ q)

e. (p → q) ↔ (¬q →¬p)

f. (p → q) → (q →p)

13. Construye las tablas de verdad de cada una de estas fórmulas.

a. (p V q) → (p q)

b. (p q) → (p Λ q)

c. (p V q) (p Λ q)

d. (p ↔ q) (¬p ↔ q)

e. (p ↔ q) ⊕ (¬p ↔ ¬r)

f. (p q) → (p ¬q)

14. Construye la tabla de verdad de la fórmula ((p → q) → r) → s.

15. ¿Cuál es el valor de x tras ejecutar las siguientes sentencias en computador si x = 1 antes

de que se llegase a ella?

a. If 1 + 2 = 3 then x := x + 1.

b. If (1 + 1 = 3) OR (2 + 2 = 3) then x := x + 1

c. If(2 + 3 = 5) AND (3 + 4 = 7) then x := x + 1

d. If(1 + 1 = 2) XOR (1 + 2 = 3) then x:= x + 1

e. If x < 2 then x := x + 1

16. Expresa las siguientes especificaciones de sistema utilizando las proposiciones p, “El

mensaje es revisado para buscar algún virus”, y q, “El mensaje fue enviado desde un

sistema desconocido”, junto con conectivos lógicos.

Page 17: Tema 2 logica proposicional

Docente: Eva Patricia Vásquez Gómez

Lógica Proposicional

17

a. “El mensaje se revisa para buscar algún virus siempre que haya sido enviado desde un

sistema desconocido”.

b. “El mensaje fue enviado desde un sistema desconocido, pero no se revisó para buscar

ningún virus”.

c. “Es necesario revisar el mensaje para buscar algún virus siempre que haya sido

enviado desde un sistema desconocido”.

d. “Cuando el mensaje no sea enviado desde un sistema desconocido no se revisa para

buscar ningún virus”.

17. ¿Son consistentes las siguientes especificaciones de sistema? “El sistema está en estado

multiusuario si, y sólo si, está operando normalmente. Si el sistema está operando

normalmente, el kernel está funcionando. El kernel no está funcionando o el sistema está

en modo de interrupción. Si el sistema no está en estado multiusuario, entonces está en

modo de interrupción”.

18. ¿Son consistentes las siguientes especificaciones de sistema? “El router puede enviar

paquetes al sistema remoto sólo si soporta el nuevo espacio de direcciones. Para que el

router soporte el nuevo espacio de direcciones es necesario que se haya instalado la

última actualización del software. El router puede enviar paquetes al sistema más remoto

si se ha instalado la última actualización del software. El router no soporta el nuevo

espacio de direcciones”.