MATEMÁTICA DISCRETA

UNIDAD 1

PROPOSICIONES LÓGICAS
OPERACIONES LÓGICAS
TABLAS DE VERDAD
FUNCIONES PROPOSICIONALES
RAZONAMIENTOS

Autor: Ing. María Alicia Piñeiro

LÓGICA
Proposición lógica: es todo enunciado susceptible de ser verdadero o falso.

Las proposiciones lógicas se denotan con letras minúsculas.

Ejemplos:
p : "Cuatro es un número impar" v(p)=F (valor de verdad de p es Falso)
q : "París es la capital de Francia" v(q)=V (valor de verdad de q es Verdadero)

Ejercicio: Indica si los siguientes enunciados son o no proposiciones lógicas:

El cielo es verde. Si NO
¿Qué hora es? Si NO
2+3=5 Si NO
¡ Hola ! Si NO
x es un número entero Si NO
Esta materia es muy útil. Si NO

De las que son proposiciones lógicas, indica el valor de verdad, es decir si son
verdaderas o falsas.
PROPOSICIONES SIMPLES Y COMPUESTAS

Proposiciones Proposiciones
simples SE COMBINAN Y FORMAN compuestas

OPERACIONES
LÓGICAS

Ejemplo: p : "Cuatro es un número impar" q : "París es la capital de Francia"

p  q : “Cuatro es un número impar y París es la capital de Francia”

¿Cuál es el valor de verdad de esta proposición compuesta? ..............

Para mostrar todas las posibilidades de valores de verdad de las

proposiciones simples, utilizamos las TABLAS DE VERDAD.
 OPERACIONES LÓGICAS

CONJUNCIÓN

La conjunción únicamente es VERDADERA cuando ambas proposiciones

simples lo son. Con una conjunción se da a entender la simultaneidad de
las dos proposiciones. Si bien el nexo conjuntivo mas común es la “y”, hay
otras formas de indicar conjunciones.

Ejemplos:

1) Estamos en invierno pero hace calor.

2) Esta tarde debo estudiar, además no me gusta jugar al football.
3) Tu prima es muy bonita, también es inteligente.
 Veamos la siguiente operación:

DISYUNCIÓN

La disyunción expresa la posibilidad de una de las dos proposiciones o

ambas, ya que es inclusiva.
Solamente una disyunción es FALSA cuando las dos proposiciones que la
forman lo son. El nexo mas común que expresa disyunción es la “o”.

Ejemplos:

1) Debemos presentar documento o credencial para rendir el examen.

2) Le puedo cobrar en efectivo o bien con tarjeta de débito.
 Hay otro tipo de disyunción:
Hay otro tipo de disyunción:

DISYUNCIÓN
EXCLUYENTE

En este caso, como la disyunción es excluyente, significa que solo una de

las proposiciones debe ser verdadera. Es decir, solamente una disyunción
excluyente es verdadera cuando los valores de verdad de las
proposiciones simples que la forman son distintos. En el lenguaje
coloquial debe expresarse explícitamente el sentido excluyente.

Ejemplos:

1) Pueden recuperar el primer parcial o el segundo pero no ambos.

2) Nos iremos a la playa o bien a las sierras, a uno de los dos.
 La siguiente operación:

CONDICIONAL

La estructura condicional, indica que si se cumple una determinada

condición (p), entonces se debe cumplir la otra (q). Por eso, la única forma
en que un condicional sea falso, es partiendo de una proposición verdadera
y que la otra sea falsa. En los tres casos restantes, el condicional es
verdadero.
Si bien, la forma mas común de indicar un condicional es “si….entonces….”,
hay otras maneras, como mostramos en los ejemplos.

Ejemplos:

1) Si una matriz es ortogonal entonces es inversible.

2) El cuadrado de todo número par es par.
3) Es necesario ser mayor de edad para ingresar al casino.
 EJEMPLO PARA COMPRENDER LA TABLA DEL CONDICIONAL:

Alicia le dice a Juan:

Si apruebas
el examen,
te regalo
una tablet

Hay cuatro situaciones que pueden darse:

1) Juan aprueba el examen y Alicia le regala la tablet.
2) Juan aprueba el examen y Alicia NO le regala la tablet.
3) Juan NO aprueba el examen y Alicia le regala la tablet.
4) Juan NO aprueba el examen y Alicia NO le regala la tablet.
 Cada una de esas situaciones representa un
renglón de la tabla de verdad.

Analicemos cada una para ver si podemos

confiar en lo que promete Alicia:

En la 1), Juan hizo lo que debía y Alicia cumplió su promesa, o sea el

condicional se ha cumplido.

En la 2), Juan hizo lo que debía pero Alicia NO cumplió su parte, por lo
cual tenemos toda la razón en reprocharle que no ha cumplido su
promesa.

Pero tanto en la 3) como en la 4), Juan no aprueba el examen. Y Alicia

solo prometió lo que iba a hacer si Juan aprobaba. No dijo nada en caso
de que no aprobara. Por lo tanto, si le regala igual la tablet o no, no está
faltando a su promesa. Nosotros, si ocurre alguno de estos casos, no
tenemos elementos suficientes para condenar a Alicia por incumplidora.
Por eso, al igual que en un juicio cuando no hay pruebas se declara
inocente al acusado, el CONDICIONAL es VERDADERO.
Seguimos con la próxima operación:

BICONDICIONAL

En este caso, al ser bicondicional, los valores de verdad de ambas

proposiciones deben tener el mismo valor de verdad.

Los bicondicionales verdaderos indican una equivalencia lógica.

Ejemplos:

1) Una matriz cuadrada es inversible si y solo si su determinante no es

nulo.
2) Solamente si aprueban los parciales y el TP firman la materia.
3) Es necesario y suficiente ser socio para obtener el descuento.
 Y la última operación lógica es una operación unaria (no binaria
como las anteriores):

NEGACIÓN

La negación cambia el valor de verdad de la proposición a la que se le

aplica. Si bien se lee como “no”, hay varias maneras de indicar una
negación.

Ejemplos: 1) El tres no es un número par.

2) No es cierto que hoy es domingo.
3) Es falso que la división es cerrada en Reales.

Si en una proposición compuesta hay n proposiciones simples, la

tabla de verdad tiene 2n renglones.

PRECEDENCIA DE OPERADORES
1 
Cuando no hay paréntesis, corchetes o
llaves se deben interpretar las 2 
operaciones lógicas en el siguiente orden: 3 
4 
5 
Ejemplo:

Cómo se interpreta: pqr

[ p  (q  r ) ] [ ( p)  q ]  r

[ (p  q)  r ] ( p)  (q  r)

La respuesta correcta es la 3)
 Ejemplo:
Teniendo en cuenta los conectivos lógicos, construiremos la
tabla de verdad de las siguientes proposiciones compuestas:

1) q  (  p  q )

q p p q  p  q q  (  p  q )
V V F F F F
V F V F V V
F V F V V F
F F V V V F

CONTINGENCIA
2) p  p  q

p q pq ppq
V V V V
V F V V
F V V V
F F F V

3) p  p

p p p  p
V F F
F V F
 TAUTOLOGIAS, CONTRADICCIONES
Y CONTINGENCIAS:

 Una proposición compuesta que es siempre verdadera

independientemente de los valores de verdad de las proposiciones
TAUTOLOGIA
simples que la forman, se llama: .....................

 Una proposición compuesta que es siempre falsa indepen-

dientemente de los valores de verdad de las proposiciones
CONTRADICCION
simples que la forman, se llama: ...............................

 Una proposición compuesta que en algunos casos es verdadera y

en otros falsa dependiendo de los valores de verdad de las propo-
CONTINGENCIA
siciones simples que la forman, se llama: .............................
CONDICIONALES

pq
ANTECEDENTE CONSECUENTE

HIPOTESIS TESIS

CONDICION CONDICION
SUFICIENTE NECESARIA

Ejemplo: “Si llueve, hay nubes en el cielo”

“Es necesario que haya nubes para que llueva”

CONDICIONALES ASOCIADOS A UNO DADO:

pq

qp qp
recíproco contrarrecíproco
pq
contrario
 Ejercicio: Hagamos la tabla de verdad de  q   p

p q q p qp
V V F F V
V F V F F
F V F V V
F F V V V
Compárala con la tabla de p  q ¿Cómo son?

Las proposiciones que tienen idénticas tablas de verdad se

llaman EQUIVALENTES.
 Ejemplo: Hagamos la tabla de verdad de p  q

p q p p  q
V V F V
V F F F
F V V V
F F V V
Esta también es equivalente a p  q.

p  q  p  q
( El símbolo  significa EQUIVALENTES )
 LEYES LÓGICAS
1 Involución (p)  p
2 Conmutatividad pqqp pqqp
3 Asociatividad p ( q  r )  ( p  q )  r p(qr) (pq)r
4 Distributividad p(qr) (pq)(pr)
p(qr) (pq)(pr)
5 Idempotencia pp p pp p
6 De Morgan  ( p  q )  (p)  (q)  ( p  q )  (p)  (q)
7 Absorción p(pq)  p p(pq)  p
8 Identidad pVp p Fp
9 Dominación pVV pFF
10 Bicondicional p  q  ( p  q)  (q  p)
11 Condicional p  q  (p)  q
12 Tercero excluido p  (p)  V
13 Simplificación pqpV
14 Adición p pqV

Todas se demuestran haciendo la TABLA DE VERDAD

........................................de cada una.
¿Para qué utilizaremos las leyes lógicas?
Las podemos utilizar para simplificar proposiciones compuestas.

Ejemplo:

Dada la siguiente proposición: p  ~ [ (~ p  q )  ~ (~p  r )]

Apliquemos equivalencia del condicional en (~ p  q ) y al mismo
tiempo apliquemos De Morgan en la otra parte: ~ (~p  r ).
Obtenemos: p  ~ [ (~(~p)  q )  [~(~p)  (~ r)] ]

Ahora apliquemos la ley involutiva en ~ (~ p) :

p  ~ [ ( p  q )  [ p  (~ r)] ]

Distributiva de  respecto de  : p  ~ [ p  ( q  ~ r) ]

Equivalencia del condicional: ~ p  ~ [ p  ( q  ~ r) ]

Apliquemos nuevamente De Morgan: ~ p  [~ p  ~( q  ~ r) ]

Finalmente, por absorción: ~p

Llegamos a la expresión mas simple!!!!

FUNCIÓN PROPOSICIONAL
( PROPOSICIÓN ABIERTA O PREDICADO)

p (x) : " x es un número par "

¿Es una proposición lógica? Si NO ¿Por qué?

¿Y éstas? “8 es un número par”

p (8)

“Todos los números enteros son pares”  x  Z: p (x)

Sea A un conjunto no vacío, llamamos predicado o función

proposicional con dominio en A a toda expresión p(x) tal que
para cualquier elemento “a” del conjunto A se verifica que p(a)
es proposición.
 FUNCION PROPOSICION
PROPOSICIONAL se transforma en LOGICA

1) Asignando valores a las 2) Cuantificándolas.

variables. Ejemplo:
Ejemplo: “todos los números son pares”
“3 es un número par”
Cuantificadores

Universal: Existencial:

 
 Ejemplo:

Sean los conjuntos: A = { 10, 15, 20 } B = { 3, 6, 9, 12 }

y las funciones proposicionales:
P(x) : “x es múltiplo de 5” Q(x) : “x es par”

“Todos los elementos del conjunto A son múltiplos de 5” se escribe:

 x  A : P(x)

“Algunos elementos del conjunto B son pares” se escribe:

 x  B : Q(x)
“ Algunos elementos del conjunto A son pares y múltiplos de 5”

 x  A : [ P(x)  Q(x) ]
 Ejercicio:

Analiza el valor de verdad de las siguientes proposiciones con cuantificadores:

xZ:x• 2=7 xR:yR: x+y=5

 x  R : x2 > -1 xR:yR: x•y=y

VARIABLES LIBRES Y VARIABLES ACOTADAS:

Si las variables de una función proposicional están afectadas por un
cuantificador, ya sea universal o existencial; diremos entonces que son
variables acotadas. En cambio, las variables que no están afectadas por
un cuantificador, son variables libres.

Ejemplo:

 x: x + y < 5 la “x” es acotada , la “y” es libre

 ¿ Es lo mismo  x:  y : p(x,y) que  y :  x : p(x,y) ?

La pregunta se puede formular diciendo si los cuantificadores

conmutan o no, es decir si se los puede cambiar de lugar, sin que
afecten a la proposición. ¿Qué te parece?

Ejemplo:

Considera el siguiente ejemplo , supongamos que x son las

mujeres solteras, y son los varones solteros y la propiedad p(x,y)
significa x e y son novios. La primera proposición dice que para
todas las mujeres solteras x existe un varón y que es el novio. La
segunda proposición, en cambio, dice que existe un varón y, tal
que todas las mujeres x del mundo son sus novias!!!

Diferente, no???
NEGACIÓN DE PROPOSICIONES CON CUANTIFICADORES.

Ejemplo:

Supongamos que María dice: “ Todos los alumnos de este curso

aprobaron el parcial”
Y Hernán le responde: “Eso no es verdad. Aquí hay un alumno que no
aprobó”

¿Es suficiente la justificación que da Hernán?

En otra ocasión, María dice: “Algún alumno de este curso aprobó el

parcial” Y nuevamente Hernán está en desacuerdo.

¿Qué debería hacer ahora para justificar su posición?

NEGACIÓN DE PROPOSICIONES CON CUANTIFICADORES.

 [  x : p(x) ]   x :  p(x)

 [  x : p(x) ]   x :  p(x)
Ejemplo:

Escribimos la negación de cada una de las siguientes proposiciones:

p:  x  R : x2 > 0  p:  x  R : x2  0

q:  x  R : ( x + 3 = 8  x > 4 )

 q:  x  R : ( x + 3  8  x  4 )

r:  x  R:  y  R : x • y = y
 r:  x  R :  y  R : x • y  y

s:  x  R: ( x > 0 → x + 2 > 3 )
 s:  x  R : x > 0  x + 2  3
 ¿Qué es un RAZONAMIENTO?

Es un conjunto de proposiciones en el cual una de ellas, llamada

CONCLUSION, se afirma sobre la base de las demás llamadas PREMISAS.

PREMISA 1

PREMISA 2

PREMISA N

 CONCLUSION
 Ejemplo:

“El ladrón tenía llave de la puerta o entró por la ventana. Si entró por la
ventana, pisoteó las macetas. Las macetas no están pisoteadas. Por lo
tanto, el ladrón tenía llave de la puerta.”

PREMISAS

P1: “El ladrón tenía llave de la puerta o entró por la ventana”.

P2: “Si entró por la ventana, pisoteó las macetas”.

P3: “Las macetas no están pisoteadas”.

CONCLUSION

“el ladrón tenía llave de la puerta.”

“El ladrón tenía llave de la puerta o entró por la ventana. Si entró por la
ventana, pisoteó las macetas. Las macetas no están pisoteadas. Por lo
tanto, el ladrón tenía llave de la puerta.”

Si consideramos el siguiente diccionario:

p: “El ladrón tenía llave de la puerta”
v: “El ladrón entró por la ventana”
m: “El ladrón pisoteó las macetas”

El razonamiento en forma simbólica queda:

p  v ; v  m ; m  p
 Ejercicio:

Escribe en forma simbólica el siguiente razonamiento previa identificación de

las proposiciones lógicas y definición de un diccionario:

Para bajar de peso debo hacer dieta o ir al gimnasio. Si voy al gimnasio gasto
dinero. Quiero bajar de peso sin gastar dinero. Entonces voy a hacer dieta.

¿Cuándo es válido un razonamiento?

Cuando de premisas VERDADERAS, NO pueda extraerse conclusión FALSA.

Ejemplo: pq;~pr ~q

Si consideramos v(p) = F , v(q) = V , v(r) = V , resultan
ser las premisas verdaderas pero la conclusión falsa, por lo
cual este razonamiento es INVÁLIDO.
 MÉTODOS PARA PROBAR LA VALIDEZ DE UN RAZONAMIENTO

1. Directo

Métodos 2. Condicional asociado

3. Demostrativo

1. MÉTODO DIRECTO
Partiendo de la verdad de las premisas, se va trabajando
con ellas hasta llegar a la conclusión

Ejemplo: p  v ; v  m ; m  p

Como v(m) = V por ser premisa entonces v(m) = F

Luego, como v(v  m) = V por ser premisa, y v(m) = F entonces v(v) = F

Por último, como v(p  v) = V por ser premisa, y v(v) =F entonces v(p) = V
Y esta es la conclusión que resulta ser necesariamente verdadera.
 2. MÉTODO DEL CONDICIONAL ASOCIADO

Consiste en armar un condicional cuyo antecedente es la conjunción de

todas las premisas, y su consecuente es la conclusión. Luego debe
demostrarse que dicho condicional es verdadero. Si lo es, el
razonamiento será válido.

Ejemplo:

[ (p  v)  (v  m)  (m) ]  p

En este caso deberíamos hacer la tabla de verdad de 8 renglones (pues

hay 3 proposiciones simples distintas), y ver que sea una tautología.

(si quieres puedes hacerla y comprobarlo, sino pasa a la próxima página)

Para no tener que hacer toda la tabla de verdad del condicional, podemos
tratar de ver si existe algún renglón de dicha tabla cuyo valor de verdad
sea FALSO. Para ello se necesita que las premisas sean todas verdaderas y
al mismo tiempo la conclusión sea falsa. Si al suponer eso, nos
encontramos con una contradicción (que una misma proposición debe ser
por un lado Verdadera y por otro Falsa), significa que nunca el condicional
va a ser falso, y por lo tanto el razonamiento es VALIDO.

Ejemplo:

[ (p  v)  (v  m)  (m) ]  p

F V F F F

V V V F

V
 3. METODO DEMOSTRATIVO

Es un método más formal y ordenado, que elabora una lista numerada

de proposiciones lógicas con el objetivo de llegar a tener en algún
elemento de la lista a la conclusión del razonamiento.

CONCLUSION

Las proposiciones se pueden incorporar a la lista sólo por tres motivos:

a) ser premisas
b) ser equivalencias lógicas de otras proposiciones anteriores de la lista

c) obtenerse a partir de otras proposiciones anteriores de la lista a través

de reglas de inferencia.
❖ En cada renglón, debe justificarse a la derecha de dónde provino
señalando el o los renglones que se han utilizado. El objetivo es llegar en
algún renglón a obtener la conclusión. Si se llega, significa que el
razonamiento es válido.

❖ Las reglas de inferencia son pequeños razonamientos que ya se sabe

que son válidos, y sirven para probar la validez de razonamientos mas
complejos. Cada una de ellas, tiene un nombre que la identifica y dos
siglas.

Las principales reglas de inferencia son:

Modus Ponens (M.P.) AB ;A B

Modus Tollens (M.T.) A  B ; B  A
Silogismo hipotético (S.H.) AB ;BC AC
Silogismo disyuntivo (S.D.) A  B ; A B
Ley de Combinación (L.C.) A;B AB
Ejemplo 1: p  v ; v  m ; m  p

vm premisa
m premisa
v M.T. (1 y 2)

pv premisa

p S.D. (4 y 3)

Ejemplo 2: pqr ;qt;~t  ~pr

p qr premisa
q t premisa
~t premisa

~q M.T. (2,3)

~ p  ( q  r) Equivalencia condicional (1)

(~ p  r )  q Asociativa y conmutativa (5)

~pr S.D. (6,4)
 PARA PENSAR:

Consideremos el siguiente razonamiento:

Todos los hombres son mortales. Sócrates es un hombre.

Por lo tanto Sócrates es mortal.

¿Te parece que es un razonamiento válido?

Lo escribimos en forma simbólica:

 x : ( h(x)  m(x) ) ; h(Sócrates)  m(Sócrates)

Siendo las funciones proposicionales usadas:

h(x) : “x es hombre” m(x) : “x es mortal”

¿Cómo lo demostramos?
REGLAS DE INFERENCIA PARA RAZONAMIENTOS
CATEGÓRICOS (CON CUANTIFICADORES) :

Estas reglas son las que nos permiten “poner” o “sacar” los
cuantificadores:

Particularización universal (P.U.)  x: p(x)  p(a)

Generalización universal (G.U.) p(a)   x: p(x)

Nota: si a es genérico

Particularización existencial (P.E.)  x: p(x)  p(a)

Generalización existencial (G.E.) p(a)  x: p(x)
 Ejemplo:

Con las nuevas reglas demostremos el ejemplo de Sócrates:

 x : ( h(x)  m(x) ) ; h(Sócrates)  m(Sócrates)

1.  x: [ h(x)  m(x) ] premisa

2. h(Sócrates)  m(Sócrates) P.U.(1)

3. h(Sócrates) premisa

4. m(Sócrates) M.P. (2,3)

IMPORTANTE:

❖ Las particularizaciones hay que usarlas siempre antes de utilizar otras

reglas de inferencia (Modus Ponens, Tollens, silogismos, etc.) ya que no
se pueden usar estas otras si hay cuantificadores.

❖ Si tenemos proposiciones existenciales, al particularizar en un

elemento “a”, éste no es genérico. En cambio si particularizamos una
proposición universal (con  ), el elemento es genérico.
 Ejemplo:

x: [ p(x)  q(x) ]

1. x : ( p(x)  q(x) ) premisa
x: [ q(x)  r(x) ]
2. x: ( q(x)  r(x) ) premisa
  x: [ p(x)  r(x) ] 3. p(a)  q(a) P.E. (1)
4. q(a)  r(a) P.U. (2)
5.  p(a)  q(a) equiv. condic (3)
6.  p(a)  r(a) S.H. (5,4)
7. p(a)  r(a) equiv. cond. (6)
8.  x : ( p(x)  r(x) ) G.E. (7)

¿Hubiese sido lo mismo cambiar de lugar los pasos 3 y 4?

¿Por qué?
 Ejercicio propuesto:

Dado el siguiente razonamiento:

Todos los invitados a la cena son ingenieros o abogados. Los que son
ingenieros estudiaron en la UTN. Ariel, uno de los invitados, no estudió
en la UTN. Por lo tanto, al menos un invitado es abogado.

Define el diccionario:

Prueba por método demostrativo:

.
 RAZONAMIENTOS CATEGORICOS INVÁLIDOS:

Para justificar que un razonamiento categórico es INVÁLIDO, la forma

correcta es dando una interpretación concreta que lo invalide, es decir
definiendo un conjunto y dando funciones proposicionales que hagan
las premisas verdaderas y la conclusión falsa.

Ejemplo:
 x: (a(x) →  b(x)) ; c(m)  b(m) ;  c(m)   x:  a(x)

Consideremos el conjunto: U = { 3, 4, 6 } , el valor de m=6

a(x) : “ x es entero” b(x) : “x es par” c(x) : “x es múltiplo de 4”

 x: (a(x) →  b(x)) es verdadera pues se cumple con x=3

c(6)  b(6) es verdadera pues se cumple b(6)

 c(6) también es verdadera

Pero la conclusión:  x:  a(x) es FALSA

 Ejercicio propuesto:

Analiza si el siguiente razonamiento es o no válido:

Algunos sillones están tapizados. Algunos sillones son blancos. Todos

los sillones blancos tienen almohadones. Por lo tanto, algunos sillones
están tapizados y tienen almohadones.

Y si cambiamos la primera palabra, ¿este nuevo razonamiento es

válido?

TODOS los sillones están tapizados. Algunos sillones son blancos.

Todos los sillones blancos tienen almohadones. Por lo tanto, algunos
sillones están tapizados y tienen almohadones.
INTERPRETACIÓN CONJUNTISTA DE ALGUNOS RAZONAMIENTOS

Una forma de interpretar algunos razonamientos categóricos es

relacionando con Teoría de Conjuntos. Te recomendamos que luego de
ver ese tema en la Unidad 2, regreses aquí para poder comprender esta
parte:

¿Recuerdas el razonamiento de Sócrates?

 x : ( h(x)  m(x) ) ; h(Sócrates)  m(Sócrates)

Podemos definir dos conjuntos (uno por cada función proposicional,

serian los conjuntos de verdad de cada una de las funciones
proposicionales):

H = { x  U / h(x) es verdadera } = { x  U / x es hombre }

M = { x  U / m(x) es verdadera } = { x  U / x es mortal }
 Ahora se observamos la primera premisa,
vemos que coincide con la definición de inclusión.
Podemos reescribirla en términos de conjuntos: HM

Con esto podemos hacer un diagrama de Venn, en el cual

graficamos el conjunto H incluido en el M.

La segunda premisa es equivalente a decir:

Sócrates  H
Entonces ubicamos a Sócrates (s) en el diagrama:

Y ahora si observamos el diagrama que hicimos, analizamos si se

cumple la conclusión: Sócrates  M

La cual es verdadera, con lo que se comprueba la validez del razonamiento.