LÓGICA Y MATEMÁTICA DISCRETA

Tema 1 Conceptos Básicos

Curso 2021/2022
Mar Angulo Martínez
 Tema 1 Introducción 2

Clasificación de los números. Operaciones

 Número ¿un concepto simple?

 Número: surge de la necesidad de contar

 Aspecto cardinal: el tamaño de una colección de objetos
 Aspecto ordinal: permite asignar una posición a cada objeto

Condiciones necesarias para que pueda producirse el conteo:

 De orden estable: la repetición de una secuencia de números
siempre en un mismo orden
 De biunivocidad: a cada objeto de la colección se le asigna un y
sólo un número
 Tema 1 Introducción 3

Clasificación de los números. Operaciones

N: Números naturales

Axiomas de Peano
 Axioma 1 0 es un número natural (
 Axioma 2 Para cada , existe uno y sólo un número natural
(sucesor o siguiente: x´) 0´=1
 Axioma 3 ,
 Axioma 4 Si x´= y´, entonces x = y
 Axioma 5 (Axioma de inducción)
Si A verifica: 1) Si
Entonces A=N
 Tema 1 Introducción 4

Clasificación de los números. Operaciones

Principio de inducción
 Si una propiedad P es cierta para 1 (ó para cualquier otro valor inicial): P(1)
y P(n)P(n+1)
Entonces la propiedad es válida para todo n

Etapa base
Etapa inductiva
Conclusión
 Tema 1 Introducción 5

Clasificación de los números. Operaciones

OPERACIONES BÁSICAS EN N

Suma de números naturales Producto de números naturales

Propiedades

1) + bien definida en N y es única -bien definido en N y es único

2) Asociativa (x+y)+z = x+(y+z) -Asociativa (x.y).z = x.(y.z)
3) Elemento neutro -Posee elemento neutro
4) Conmutativa x+y = y+x -Conmutativa x.y = y.x
-Si x.y=1, entonces x=y=1
Sólo el 1 tiene elemento simétrico
 Tema 1 Introducción 6

Clasificación de los números. Operaciones

N: Números naturales

SUMA PRODUCTO

-Asociativa -Asociativa
-Conmutativa -Conmutativa
-Elemento Neutro -Elemento unidad
+Distributiva del producto respecto a la suma

(N,+, .)es un semianillo conmutativo

 Tema 1 Introducción 7

Clasificación de los números. Operaciones

Z: Números enteros

 Z se obtiene como una extensión del conjunto N

En NxN definimos (a,b) R (c,d) si a+d = b+c es una relación de
equivalencia

 Z es el conjunto cociente NxN/R

 Un número entero es cada una de las clases de
equivalencia [a,b]
 Tema 1 Introducción 8

Clasificación de los números. Operaciones

OPERACIONES BÁSICAS EN Z

Suma de números enteros Producto de números enteros

Propiedades

-la suma está bien definida en Z y es única - bien definido en Z y es único

-Asociativa (x+y)+z = x+(y+z) - Asociativa (x.y).z = x.(y.z)
-Posee elemento neutro - Elemento unidad
-Elemento simétrico - Conmutativa x.y = y.x
-Conmutativa x+y = y+x
 Tema 1 Introducción 9

Clasificación de los números. Operaciones

Z: Números enteros

SUMA PRODUCTO
-Asociativa Asociativa
-Conmutativa Conmutativa
-Elemento Neutro Elemento unidad
-Elemento simétrico
+Distributiva del producto respecto a la suma

(Z,+, .)es un anillo conmutativo

 Tema 1 Introducción 10

Clasificación de los números. Operaciones

Dominio de integridad: es un anillo conmutativo unitario

que no tiene divisores de 0

porque:
 Tema 1 Introducción 11

Clasificación de los números. Operaciones

•Ordenación de los números enteros

•Dados x,y
•Es una relación de orden.

Propiedades

•si t
 Tema 1 Introducción 12

Clasificación de los números. Operaciones

Q: Números racionales
 Q se obtiene como una extensión del conjunto Z
En ZxZ* definimos (a,b) R (c,d) si a.d = b.c es una relación de
equivalencia

 Z es el conjunto cociente ZxZ*/R

 Un número racional es cada una de las clases de
equivalencia [a,b]
 Cada representante de [a,b] se denota a/b y se
denomina fracción
 Tema 1 Introducción 13

Clasificación de los números. Operaciones

OPERACIONES BÁSICAS EN Q
Producto de números racionales
Suma de números racionales
[a,b].[c,d]=[ac, bd]
[a,b]+[c,d]=[ad+bc,bd]

Propiedades
-bien definida en Q y es única - bien definido en Q y es único
-Asociativa (x+y)+z = x+(y+z) - Asociativa (x.y).z = x.(y.z)
-Posee elemento neutro - Elemento unidad
-Elemento simétrico - Elemento inverso es [b/a]
-Conmutativa x+y = y+x - - Conmutativa x.y = y.x
 Tema 1 Introducción 14

Clasificación de los números. Operaciones

Q: Números racionales
SUMA (Q,+) grupo abeliano PRODUCTO (Q*,+) grupo abeliano
-Asociativa -Asociativa
-Conmutativa -Conmutativa
-Elemento Neutro [0/a] -Elemento unidad [a/a]
-Elemento opuesto [-a/b] -Elemento inverso de [a/b]: [b/a]
+Distributiva del producto respecto a la suma

(Q,+, .)es un cuerpo conmutativo

 Tema 1 Introducción 15

Clasificación de los números. Operaciones

Relación de orden en Q
 Dado un número racional r, r, ó r=0 ó -r,
 Q=
 se define una relación
Es una relación de orden total
 La relación de orden es compatible con la suma

La relación de orden no siempre es compatible con el producto

 Tema 1 Introducción 16

Clasificación de los números. Operaciones

Densidad de Q
 dados dos números racionales entre ellos
siempre se puede encontrar un número infinito
de números racionales
 no sirven los conceptos de anterior y siguiente
 Esto no ocurre en N ni tampoco en Z
 Tema 1 Introducción 17

Clasificación de los números. Operaciones

Valor absoluto de números racionales

 La función valor absoluto de un número racional se define como

 las propiedades son idénticas a las del valor absoluto de números enteros

1) (prop. Triangular)
2)
 Tema 1 Introducción 18

Clasificación de los números. Operaciones

• Q es un conjunto numerable
• No hay más números racionales que enteros-- el conjunto Q es un conjunto
numerable.
• Q(b)= {todas las fracciones con denominador b} (b>0)
• El subconjunto a N
• El subconjunto también es numerable.
• = Q(b) numerable
• Q(1)UQ(2)UQ(3)…. Es un conjunto numerable que contiene a Q--Q es
numerable
• Card N =Card Z = Card Q = infinito numerable
 Tema 1 Introducción 19

Clasificación de los números. Operaciones

R: Números reales
 Los números irracionales:
-tienen un nº infinito de cifras decimales no periódicas
-no son solución de ninguna ecuación de números enteros ni racionales
 Densidad de Q en R
 se puede considerar cualquier número real es el límite de una sucesión de
números racionales---- Q es denso en R.
 R se define como una ampliación de Q
C: Números complejos
 Tema 1 Introducción 20

Clasificación de los números. Operaciones

• La Matemática Discreta es un área de las Matemáticas que estudia los conjuntos

discretos: finitos o infinitos numerables.
• el cálculo infinitesimal: la base son números reales y maneja conceptos como la
continuidad, las Matemáticas discretas estudian estructuras cuyos elementos se
pueden contar uno a uno separadamente. No es posible manejar las ideas de
proximidad, límite, continuidad, suavidad en las curvas…
• En matemática discreta: los números naturales o los conjuntos numerables: Z y Q
• Gráficas: en matemática discreta son gráficos de puntos aislados, no trazos continuos
de curvas o rectas
Matemática Discreta: fundamental en la computación porque
sólo son computables las funciones de conjuntos numerables
 Tema 1 Introducción 21

Conjuntos

Conjunto:
colección de determinados objetos (elementos) bien
definidos y diferenciados unos de otros
o Por extensión: nombrando a todos los o Por comprensión: dando una
elementos que forman parte del propiedad que los caracteriza
conjunto  {x
 Ejemplos: {3,4,5,6…}  {x
 {a, 2, Madrid, 5}
 Tema 1 Introducción 22

Conjuntos

 N de números naturales N={1,2,3,4,5,…..}

 Z de números enteros Z ={…,-3, -2, -1, 0, 1,2,3,….}
 Q de números racionales Q={/ a,b
x
 R de números reales R={x/

: números enteros estrictamente positivos

 Tema 1 Introducción 23

Conjuntos

Ejemplo 1

Expresa por extensión estos conjuntos:

a) {x/x es real positivo t.q =1}
b) {x/x entero positivo menor que 12 }
c) {x es cuadrado de un entero y <100}
d) {x/x entero y =2}
 Tema 1 Introducción 24

Conjuntos

 Conjuntos no numéricos: listas, palabras, tiras…

(string)
 Ejemplo: palabras de longitud 2 con {0,1}:
 {0, 1, 00, 01, 10, 11}
 Tema 1 Introducción 25

Conjuntos

 Conjunto vacío
 Conjuntos iguales A=B tienen idénticos elementos
 A contenido en B A
 Si no pertenece a A: A es subconjunto propio

 A,B comparables: si ACB ó BCA:

 Tema 1 Introducción 26

Conjuntos

Representación gráfica: diagramas de Venn (1834-1923)

z
 Tema 1 Introducción 27

Conjuntos

Pregunta
Si B = { 4, 7, m, n, A} y A={1,2,3}
¿Cómo denotarías la relación entre A y B?
Ejercicio
Si U={1,2,3,4,5}, A={1,3,4} B={3,5}, C = {1,2,5}
¿qué relaciones observas entre estos conjuntos
 Tema 1 Introducción 28

Conjuntos

Pregunta
Si B = { 4, 7, m, n, A} y A={1,2,3}
¿Cómo denotarías la relación entre A y B?
Ejercicio
Si U={1,2,3,4,5}, A={1,3,4} B={3,5}, C = {1,2,5}
¿qué relaciones observas entre estos conjuntos
 Tema 1 Introducción 29

Conjuntos
 ¿Cómo representar conjuntos en un programa?

 Mediante una tira de bits: 

ui= 1 si x
ui= 0 si x

 Los bits “1” representan los elementos de

A
 Tema 1 Introducción 30

Conjuntos

Ejemplo

U = {1,2,3,4,5,6,7,8,9,10}
A = {números que exceden de 5}
0 0 0 0 0 1 1 1 1 1

B = {números impares}
1 0 1 0 1 0 1 0 1 0

Representar mediante tiras de bits AUB, A, , A

 Tema 1 Introducción 31

Conjuntos
AUB = {números que exceden de 5 o son impares}
1 0 1 0 1 1 1 1 1 1
A∩B = {números que exceden de 5 y son impares}
0 0 0 0 0 0 1 0 1 0

Ac= {números que no exceden de 5 }

1 1 1 1 1 0 0 0 0 0
A∩Bc = {números que exceden de 5 y son pares}

0 0 0 0 0 1 0 1 0 1
 Tema 1 Introducción 32

Conjuntos

 Cardinal de un conjunto : es el número de elementos que

posee
 El cardinal puede ser finito o infinito
 P(X) conjunto de las partes de X: formado por todos los
subconjuntos de X
 =n =

Ejemplo: A={1, a, x} Construir P(A)

 Tema 1 Introducción 33

Conjuntos

OPERACIONES ENTRE CONJUNTOS

AB = {x/ ó x
A{x/ y x
A-B = { / x

1) (A U B) U C = A U (B U C) Asociativa
2) ACXyBCX
3) ACB AUB=B
4) A U U = U Absorción
5) A U A = A Idempotencia
6) A U = A Neutralidad

7) A

Propiedades
 Tema 1 Introducción 34

Conjuntos
 Tema 1 Introducción 35

Conjuntos

1) (A B) C = A (B C) Asociativa
2) XCAyXCB
3) ACB A B=A
4) A U=A Neutralidad
5) A A=A Idempotencia
6) A = Absorción
Distributivas
A
A
A=A A = A Absorción
 Tema 1 Introducción 36

Conjuntos

Dos conjuntos son disjuntos cuando A

Complementario de A: contiene los elementos de

U que no están en A

Diferencia entre A y B: A
 Tema 1 Introducción 37

Conjuntos

Leyes de De Morgan

=

=
Diferencia simétrica de A y B: (A (B)
 Tema 1 Introducción 38

Conjuntos

Ejemplo 2

Hallar los conjuntos A y B si A-B = {1,5,7,8}, B-A ={2,10} y A

Ejemplo 3
Hallar la diferencia simétrica de A={1, 3, 5} y B= = {1, 2, 3}

Ejemplo 4
Describe la diferencia simétrica de los estudiantes de
matemáticas de tu universidad y los estudiantes de
ingeniería de software de la misma
 Tema 1 Introducción 39

Conjuntos

Ejemplo 5
Dado el conjunto universal U={1, 2, 3, 4, 5, 6} y los subconjuntos A={1, 3, 4}
B= {1, 4, 6}, C={1, 3, 5} y D={2, 4, 6}. Se pide calcular:
a) AUB, ACUD, C
b) Calcular los complementarios de A, de B, de AUB, y de A
c) Comprobar las leyes de De Morgan
d) Calcular la diferencia y la diferencia simétrica de A y B
e) Comprobar que + = +
f) Comprobar que , , y forman una partición de U
Ejemplo 6
Demostrar que =
 Tema 1 Introducción 40

Conjuntos

 Producto cartesiano de A1,…An es el conjunto de las n-tuplas

(a1, a2, ….an) donde ai i=1…n
 Producto cartesiano de A y B es el conjunto de los pares ordenados
AxB ={(a,b) con a}

Ejemplo: A={1,3,5} B={m,n} C={álgebra, cálculo}

a) Obtener AxB y AxBxC
b) ¿Es conmutativo?
 Tema 1 Introducción 41

Conjuntos

PRINCIPIO DE INCLUSIÓN-EXCLUSIÓN
 Cardinal de la unión de 2 conjuntos

 = +-

 Nota: Si A y B disjuntos (si A

 = ++--
 Tema 1 Introducción 42

Conjuntos

Ejemplo 7

Resultados de una muestra de 100 estudiantes

12 cursan matemáticas, física y química
22 cursan sólo matemáticas y física
23 cursan únicamente matemáticas y química
17, sólo física y química
Todos ellos cursan al menos una de las tres materias
Calcular el número de estudiantes que cursan una sola materia
 Tema 1 Introducción 43

Conjuntos

Identificar cada una de las secciones

 Tema 1 Introducción 44

Conjuntos

 CONJUNTO BORROSO es un subconjunto S de U en el que cada elemento posee un

grado de pertenencia (pi) al mismo
 pi
 Si S y T son conjuntos borrosos, SUT es un conjunto borroso en el que el grado de pertenencia de
cada elemento es el máximo de los grados de pertenencia a S y T
 Si S y T son conjuntos borrosos, ST es un conjunto borroso en el que el grado de pertenencia de
cada elemento es el mínimo de los grados de pertenencia a S y T
 Si el grado de pertenencia de un elemento a S es p, el grado de pertenencia de dicho elemento al
complementario de S es 1-p
 Tema 1 Introducción 45

Conjuntos
Ejemplo 8
S = {0,7 Diana, 0,8 Tomás, 0,4 Virginia, 0,1 Oscar}
T = {0,5 Diana, 0,3 Tomás, 0,6 Virginia, 0,2 Oscar}
Cómo se definirán , S y

= {0,3 Diana, 0,2 Tomás, 0,6 Virginia, 0,9 Oscar}

S = {0,7 Diana, 0,8 Tomás, 0,6 Virginia, 0,2 Oscar}

= {0,5 Diana, 0,3 Tomás, 0,4 Virginia, 0,1 Oscar}

 Tema 1 Introducción 46

Conjuntos

 PARTICIÓN DE UN CONJUNTO S es una distribución de subconjuntos ) de S tales que

2) = S

Ejemplo 9: S = {a, b, c, d, e, f}
A1 = {a, c, d} A2 = {b, f} A3 = {e} A4 = {a, e}

Pregunta: ¿es una partición de S: {A1, A2, A4}?

Y {A1, A2, A3}? Y {A1, A2}?

 Tema 1 Introducción 47

Conjuntos

• Ejemplo 10: algoritmo que genera una partición de U

• U = {1, 2, 3, …..20}
• Para I = 1 hasta 20
• A1(I) A1 = {0,1,0,1,0,1,0,1…………..0,1} =
• A2(I) {2,4,6,8,10,………………18,20}
• A3(I)
A2 = {1,0,1,0,0,0,0……………0,0} = {1,3}
A3 = {0,0,0,0,1,0,1,…………..1,0} =
• FIN- Para
{todos los impares excepto 1 y 3}
• Fin-Partición