Unidad I: FUNDAMENTOS DE LALÓGICAEstructuras Discretas

Ing. Nelsymar Millán

Lógica proposicional

Área de la matemática que trata las proposiciones y el razonamiento lógico matemático.

La lógica son reglas que…

• Dan significado a enunciados y sentencias matemáticas.

• Distinguen argumentos validos y no validos.

• Se aplican en la construcción de programas y circuitos de computadores.

Proposición

Verdadero Falso

Pero

No ambos a la vez

Puede ser

Oración declarativa

Simple CompuestaTiene un único valor lógico

Sin

conectivos

lógicos

Con

conectivos

lógicos

Ejemplo:

El Sol es una

estrella

Ejemplo:

El Sol es una

estrella y laTierra

gira alrededordel

Sol

Las oraciones que no son falsas ni

verdaderas, las que son falsas y

verdaderas al mismo tiempo, o lasque

carecen de sentido (o presentanalgún

tipo de imprecisión) no son

consideradas proposiciones. Las

proposiciones se denotan con letras

minúsculas: p, q, r, s.

Ejemplos:• Maracaibo es la capital del Zulia.

• La Tierra gira alrededor delSol.

• El Zulia es la capital deVenezuela.

• 1 + 1 =2

• 2 + 2 =3

No son proposiciones:• ¿Qué hora es?

• ¡Siéntate!

• Lee esto con atención.

• X + 1 = 2

• X + Y = Z

Valor de verdad

Llamaremos valor verdadero o valorde

verdad de una proposición a su

veracidad o falsedad. El valor de

verdad de una proposición verdadera

es verdad (1) y el de una proposición

falsa es falso (0).

Ejemplo: Diga cuáles de las siguientes afirmaciones son proposicionesy determinarelvalordeverdaddeaquellasque losean.

• p: Existe el premio Nobel deInformática.

• q: Teclee ESC para salir de laaplicación.

• r: Cinco más siete esgrande.

Respuestas:

• p es Proposición. Su valor es«Falso».

• q no es proposición. No es Verdadera ni Falsa.

• r no es proposición. Carece de contexto, esambiguo.

Tabla de verdad

Es una tabla que muestra el valor de

verdad de una proposición compuesta, para

cada combinación de verdad que se pueda

asignar.

La tabla de verdad de una proposición

compuesta P enumera todas las posibles

combinaciones de los valores de verdad

para las proposiciones p, q, r, s,…

Tabla de verdadPor ejemplo, si P es una proposición

compuesta por las proposiciones simples p, q y r,

entonces la tabla de verdad de P deberá recoger

los siguientes valores de verdad.

p q r

V V V

V V F

V F V

V F F

F V V

F V F

F F V

F F F

Proposición compuesta

Si las proposiciones p, q, r, s, …se combinan

para formar la proposición P,diremos que Pes una

proposición compuesta de p, q, r, s,…

Ejemplo: Sean los enunciados

p: Estructuras Discretas es mi asignaturapreferida.

q: Mozart fue un grancompositor.

r: Él es inteligente.

s: Él estudia todos los días.

Ejemplos deProposiciones compuestas:

«Estructuras discretas es mi

asignatura preferida y Mozart fue

un gran compositor»

«Él es inteligente o estudia todos

los días»

La propiedad fundamental de una

proposición compuesta es que su valor

de verdad está completamente

determinado por los valores de verdad

de las proposiciones que la componen

junto con la forma en la que están

conectadas.

Proposición compuesta

Operadores y Conectivos Lógicos

OPERADORES:

paraSe aplican a las proposiciones

generar proposiciones nuevas.

CONECTIVOSLÓGICOS:

Operadores lógicos que se usan para

formar nuevas proposiciones a partir de dos

o másproposiciones existentes.

TIPOS DE OPERADORESLÓGICOS

NEGACIÓN

Sea p una proposición, el enunciado es otra proposición llamada

“Negación de p”. Se denota: ¬p y selee

. Su tabla de verdades:

p ¬p

1 0

0 1

NEGACIÓN.Ejemplo:

p: «El Pentium es un microprocesador.»

¬p: «El Pentium no es un microprocesador.»

¬p: «Es falso que el Pentium sea un

microprocesador.»

q: « 2 + 2 = 5 »

¬q: «Es falso que 2 + 2 =5»

¬q: « 2 + 2 ≠ 5 »

CONJUNCIÓNSean p y q proposiciones. La proposición >, denotada por p q, es la proposición

que es verdadera cuando tanto p como q son

verdaderas y falsa en cualquier otro caso. Su

tabla de verdades:

p q p q

0 0 0

0 1 0

1 0 0

1 1 1

p: «Hoy esviernes.»

q: «Hoy llueve.»

p q: «Hoy es viernes y hoy llueve.»

VERDADERA: Los viernes con lluvia.

FALSA: Cualquier día diferente de

viernes y los viernes que no llueve.

CONJUNCIÓN.Ejemplo:

DISYUNCIÓN

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

falsa cuando tanto p como q son falsas y

verdadera en cualquier otro caso. Su tabla de

verdad es:

p q p q

0 0 0

0 1 1

1 0 1

1 1 1

DISYUNCIÓN.Ejemplo:

p: «Hoy esviernes.»

q: «Hoy llueve.»

p q: «Hoy es viernes u hoy llueve.»

VERDADERA: Cualquier día que sea viernes o llueva, incluyendo losviernes con lluvia.

FALSA: Los días que ni son viernes, ni llueve.

DISYUNCIÓNEXCLUYENTESean p y q proposiciones. La proposición >, denotada por p q, es la

proposición que es verdadera cuando solo una de

las dos proposiciones p y q es verdadera; y es falsa

cuando ambas son verdaderas o ambas son falsas.

Su tabla de verdades:

p q p q

0 0 0

0 1 1

1 0 1

1 1 0

DISYUNCIÓNEXCLUYENTE.Ejemplo:p: «Hoy esviernes.»

q: «Hoy llueve.»

p q: «Hoy es viernes u hoy llueve.»

VERDADERA: Cualquier día que sea viernes o llueva, pero noambos.

FALSA: Los viernes con lluvia, y los otros días que no llueve.

IMPLICACIÓN OCONDICIONALSean p y q proposiciones. La implicación pq es

la proposición que es falsa cuando p es verdadera

y qesfalsa; y esverdadera en cualquier otro caso.

pq(Hipótesis o Causa) (Conclusión o Consecuencia)

p q pq

0 0 1

0 1 1

1 0 0

1 1 1

FORMAS DE EXPRESAR EL CONDICIONAL

EN LENGUAJENATURAL:

• «Si p, entonces q»

• «p implica q»

• «q si p»

• «p solo si q»

• «p siempre que q»

IMPLICACIÓN OCONDICIONAL

IMPLICACIÓN O CONDICIONAL.Ejemplo:p: «Soy elegido como Presidente.»

q: «Bajaré los impuestos.»

p q: «Si soy elegido como Presidente,

entonces bajaré los impuestos.»

Si el político es elegido (p es verdadera) y

no baja los impuestos (q es falsa), las

expectativas son falsas.

BICONDICIONAL O DOBLE IMPLICACIÓN

Sean p y q proposiciones, el Bicondicional o

Doble Implicación, p q es la proposición que es

verdadera cuando p y q tienen los mismosvalores

de verdad y falsa en los otros casos.

Su tabla de verdades:

p q pq

0 0 1

0 1 0

1 0 0

1 1 1

FORMAS DE EXPRESAR EL BICONDICIONAL

EN LENGUAJENATURAL:

• «p si, y solo si q»

• «p es necesario y suficiente para q»

• «p sii q»

BICONDICIONAL O DOBLE IMPLICACIÓN

BICONDICIONAL O DOBLE IMPLICACIÓN.Ejemplo:p: «Puedes tomar el vuelo.»

q: «Compras un pasaje.»

p q: «Puedes tomar el vuelo si,y

solo si, compras un pasaje»

Esta expresión es verdadera si p y q son

ambas verdaderas o ambas falsas.

Precedencia deOperadores Lógicos.

Orden Operador Nombre

1 ¬ Negación

2 Conjunción

3 Disyunción

4 Implicación

5 Bicondicional

Formalización

alumno del primer período.»

Consiste en pasar del lenguaje natural al lenguaje formal.

Ejemplo:

p

«Puedes acceder a internet desde el LC1 solo si estudias Computación o no eres

qr

p q ¬r)

Equivalencias Proposicionales

Dos formulas son lógicamente

equivalentes si tienen los mismos

valores de verdad en todos los

casos. También se dice que p y q

son lógicamente equivalentes sip

q es una tautología y se denota

por p q.

Tautologías y Contradicciones

Sea P una proposición compuesta de las

proposiciones simples p, q, r,…

P es una Tautología si es verdadera para todos

los valores de verdad que se asignen a p, q, r, …

P es una Contradicciónsi es falsa para todos los

valores de verdad que se asignen a p, q, r,…

Una proposición P que no es tautología ni

contradicción se llama, usualmente,

Contingencia.

Tautologías y Contradicciones

Tautología Contradicción

p ¬p p¬p p¬p

1 0 1 0

0 1 1 0

Ejercicios:• ¿Cuál es la negación de cada uno de los siguientes

enunciados?

a) Hoy esmartes.

b) No hay contaminación en CiudadOjeda.

c) 2 + 1 = 3.

d) El clima en Mérida es cálido y soleado.

• Sean los enunciados p: «Tienes fiebre», q: «Suspendes el

examen final» y r: «Apruebas el curso». Expresa cada una

de las siguientes fórmulas en lenguaje natural.

a) p q

b) ¬p r

c) q ¬r

d) p q r

e) (p ¬r) q ¬r)

• Sean p y q los enunciados «Conduces a mas de 100 Km. por

hora» y «Te multan por exceso de velocidad», respectivamente.

Escribe los siguientes enunciados 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 multaran por exceso de velocidad si conduces a más de

100 Km. Por hora.

d) Si no conduces a mas de 100 Km. por hora no te multarán

por exceso de velocidad.

• Determina si las siguientes implicaciones son verdaderas o 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.

• Sean las proposiciones p: «Tienes fiebre», q: «No

suspendes el examen final» y r: «Apruebas la

asignatura», expresa en lenguaje natural la

expresión:

((pq) (pr))

• Simboliza las siguientes proposiciones:

a) No vi la película pero leí lanovela.

b) Ni vi la película ni leí lanovela.

c) No es cierto que viese la película y leyese la

novela.

d) Vi la película aunque no leí lanovela.

• Sean p, q y r las proposiciones «El número N es par», «La salida va a la pantalla» y «Los resultados se dirigen a la impresora», respectivamente. Enunciar en Lenguaje Natural las siguientes proposiciones:

a) q p

b) ¬ q r

c) r p q)

• Tomando en cuenta las proposiciones del ejercicio anterior, escribir, usando conectivos lógicos, una proposición que simbolice cada una de las siguientes afirmaciones:

a) Si el número N es par, los resultados se dirigen a la impresora y la salida va a la pantalla.

b) La salida va a la pantalla si, y solo si, los resultados se dirigen a la impresora.

c) No es cierto que el número N sea par o la salida no va alapantalla.

d) Si el número N es par, la salida va a la pantalla y los resultados se dirigen a la impresora, pero no ambas cosas a la vez.