REA DE ELECTRNICA, CONTROL Y AUTOMATIZACIN

CTEDRA: ESTRUCTURAS DISCRETAS

PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.

UNIDAD 1: LGICA PROPOSICIONAL Y TEORA DE CONJUNTOS

1. Proposiciones Lgicas
La lgica es una disciplina que busca modelar las leyes del pensamiento humano.
La lgica proposicional es un rea de la matemtica que permite el razonamiento
de enunciados y sentencias matemticas. Son reglas que:
- Dan significado a enunciados y sentencias matemticas.
- Distinguen argumentos validos y no validos.
- Se aplican en la construccin de programas, modelado de algoritmos, estructuras
de datos y circuitos de computadores.

Las Proposiciones Lgicas son oraciones declarativas que pueden ser

verdaderas o falsas pero no ambas a la vez.
Ejemplo:
a.- Maracaibo es la capital del Estado Zulia
b.- Bachaquero es la capital del Municipio Lagunillas
c.- 2 + 2 = 4
d.- 3 + 3 = 9
Todas son proposiciones, a y c verdaderas; b y d falsas.
Ejemplo:
a.- Que da es hoy?
b.- Lee esto con atencin
c.- X + 1 = 2
d.- X + Y = Z
En este caso a y b no son proposiciones porque no son declaraciones, por otra
parte, c y d no son proposiciones porque no son ni verdaderas, ni falsas.

Las Proposiciones se denotan con letras minsculas p, q, r y s. Tiene dos

posibles valores llamados Valor de Verdad, que pueden ser V = verdadero y F =
Falso. Para simplificar el anlisis, los valores verdaderos se asocian con el
nmero 1 y los falsos con el nmero 0 del sistema binario aplicado en
computacin.

La Tabla de la Verdad muestra las relaciones entre los valores de verdad de las
proposiciones.

p Q R
1 1 0
0 0 1

Modulo Instruccional Estructuras Discretas. Teora y Prctica 1

 REA DE ELECTRNICA, CONTROL Y AUTOMATIZACIN
CTEDRA: ESTRUCTURAS DISCRETAS
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.

2. Operadores y Conectivos Lgicos

Los Operadores Lgicos, son operadores aplicados a las proposiciones, para
generar nuevas proposiciones compuestas por dos o ms proposiciones simples.
Los Conectivos Lgicos, son operadores lgicos que se usan para formar
nuevas proposiciones a partir de 2 o mas proposiciones existentes.

Los Tipos de Operadores Lgicos son:

Negacin: sea p una proposicin, el enunciado << no se cumple p >> es otra
proposicin llamada Negacin de p. Se denota: p y se lee <<no p >>. Su tabla
de verdad es:
P p
1 0
0 1

Conjuncin: sean p y q proposiciones. La proposicin << p y q >>, denotada por

p q, es la proposicin que es verdadera cuando tanto p como q son verdaderas y
falsa en cualquier otro caso. Su tabla de verdad es:
p q p q
0 0 0
0 1 0
1 0 0
1 1 1

Ejemplo: p << hoy es viernes >>

q << hoy llueve >>
p q<< hoy es viernes y hoy llueve >>
Verdadera: Los viernes con lluvia
Falsa: Cualquier otro da diferente de viernes y los viernes que no llueve

Disyuncin: sean p y q proposiciones. La proposicin << p o q >>, denotada por

p q, es la proposicin 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

Modulo Instruccional Estructuras Discretas. Teora y Prctica 2

 REA DE ELECTRNICA, CONTROL Y AUTOMATIZACIN
CTEDRA: ESTRUCTURAS DISCRETAS
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.

Ejemplo: p << hoy es viernes >>

q << hoy llueve >>
p q<< hoy es viernes u hoy llueve >>
Verdadera: Cualquier da que sea viernes o llueva, incluyendo viernes que llueva..
Falsa: Los das que ni son viernes, ni llueve.

Disyuncin Excluyente u O-Excluyente: sean p y q proposiciones. La

proposicin << p o q (pero no ambas) >>, denotada por p q, es la proposicin
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 verdad
es:
p q p q
0 0 0
0 1 1
1 0 1
1 1 0

Ejemplo: p << hoy es viernes >>

q << hoy llueve >>
p q<< hoy es viernes u hoy llueve >>
Verdadera: Cualquier otro da que sea viernes o llueva, pero no ambos.
Falsa: Los viernes que llueve, los otros das que no llueve.

3. Implicaciones y Bicondicionales:
Sean p y q proposiciones. La implicacin pq es la proposicin que es falsa
cuando p es verdadera y q es falsa; y es verdadera en cualquier otro caso.

(Hiptesis o Causa) p q (Conclusin o Consecuencia)

Su tabla de verdad es:
p q pq
0 0 1
0 1 1
1 0 0
1 1 1

Las formas de expresar el condicional p q son:

<< si p, entonces q >>, << p implica q >>, << q si p >>, << p solo si q >>,<< q
siempre que p>>
Ejemplo:

Modulo Instruccional Estructuras Discretas. Teora y Prctica 3

 REA DE ELECTRNICA, CONTROL Y AUTOMATIZACIN
CTEDRA: ESTRUCTURAS DISCRETAS
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.

<< si soy elegido, entonces bajare los impuestos >>

Si el poltico es elegido (p es verdadera), no baja los impuestos (q es falsa), las
expectativas son falsas. (p q es F)

Otras implicaciones derivadas de p q son:

-Reciproca de p q: q p
-Contrarreciproca de p q: q p
-Inversa de p q: p q

Tablas de verdad:
q p qp q p qp p q pq
0 0 1 0 0 1 0 0 1
0 1 1 0 1 1 0 1 1
1 0 0 1 0 0 1 0 0
1 1 1 1 1 1 1 1 1
Reciproca Contrarreciproca Inversa
Ejemplo:
Cuales son las contrarreciproca, reciproca e inversa de la implicacin:
<< el equipo gana siempre que llueve >>
Se identifican la causa y la consecuencia: p q
<< si llueve, entonces el equipo local gana >>
Contrarreciproca: qp << si el equipo no gana, entonces no llueve >>
Reciproca: qp << si el equipo gana, entonces llueve >>
Inversa: pq << si no llueve, entonces el equipo no gana >>

Sean p y q proposiciones, el Bicondicional o Doble Implicacin, p q es la

proposicin que es verdadera cuando p y q tienen los mismos valores de verdad y
falsa en los otros casos.
Su tabla de verdad es:

p q pq
0 0 1
0 1 0
1 0 0
1 1 1

La proposicin p q, es verdadera cuando p q y q p son verdaderas. Las

formas de expresar el bicondicional p q son:

Modulo Instruccional Estructuras Discretas. Teora y Prctica 4

 REA DE ELECTRNICA, CONTROL Y AUTOMATIZACIN
CTEDRA: ESTRUCTURAS DISCRETAS
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.

<< p si, y solo si q >>,<< p es necesario y suficiente para q >>,<< p sii q >>

Ejemplo:
p << puedes tomar el vuelo>>
q << compras un pasaje>>
p q << puedes tomar el vuelo si, y solo si compras un pasaje>>
.Esta expresin es verdadera si p y q son ambas verdaderas o ambas falsas.

Orden en que se aplican en la construccin de formulas, cuando no se usan

parntesis:
Orden Operador Nombre
1 Negacin
2 Conjuncin
3 Disyuncin
4 Implicacin
5 Bicondicional

p q equivale (p) q(Negacin precede a la conjuncin)

p q r equivale (p q) r (Conjuncin precede a la disyuncin)
p q r equivale (p q) q(Disyuncin precede a la implicacin)

Pasar del lenguaje natural al lenguaje formal, se conoce como Formalizacin.

Ejemplo:
Cual es la formalizacin de la frase: << puedes acceder a Internet desde el
laboratorio solo si estudias computacin o no eres alumno de primero >>
p << puedes acceder a Internet desde el laboratorio >>
q<< estudias computacin >>
r<< eres alumno de primero>>
Formalizacin: p q r)
Ejemplo:
Cual es la formalizacin de la siguiente frase: << No puedes montarte en la
montaa rusa si mides menos de 1,2 Mts a no ser que seas mayor de 16 aos>>
q << Puedes montarte en la montaa rusa >>
r << Mides mas de 1,2 Mts >>
s << Eres mayor de 16 aos >>
Formalizacin: (r s) q

Modulo Instruccional Estructuras Discretas. Teora y Prctica 5

 REA DE ELECTRNICA, CONTROL Y AUTOMATIZACIN
CTEDRA: ESTRUCTURAS DISCRETAS
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.

4. Definicin de Conjunto
Un conjunto es un grupo de objetos con una o ms caractersticas comunes.
Tambin se puede decir que es una coleccin desordenada de objetos. Un
conjunto est bien definido si es posible conocer todos sus elementos.
Ejemplo:
Las Vocales del Alfabeto V = {a, e, i, o, u}
V = Nombre del conjunto en mayscula
a, e, i, o, u = Nombre de los elementos en minscula.
Ejemplo:
Los enteros positivos impares menores a 10 I = {1, 3, 5, 7, 9}
Los elementos pueden ser tambin nmeros.
Ejemplo:
B = {a, 2, Roberto, Francia}

Los elementos de un conjunto pueden tambin no estar relacionados. Los

elementos son los objetos que componen un conjunto, tambin se les conoce
como miembros. Se dice que el conjunto contiene a sus elementos y los
elementos pertenecen al conjunto.
Si un elemento a pertenece a un conjunto V, se denota por: a V
Si un elemento d no pertenece a un conjunto V, se denota por: d V

Modos de Representacin de un Conjunto:

Extensin
Se detallan todos los elementos del conjunto. Ejemplo: V = {a, e, i, o, u}
Comprensin
Se da una idea que representa los elementos. Ejemplo: Las vocales del alfabeto.
Descripcin por construccin
Se caracterizan todos los elementos del conjunto declarando la propiedad o
propiedades que deben tener sus miembros.
Ejemplo:
Conjunto I de todos los enteros impares menores que 10.
I = {x I x es un entero positivo menor que 10}
I = {x I x Z, x 10}
R = {x I x R}

Diagrama de Venn
Es una forma grfica de representar un conjunto. Parte del concepto de conjunto
Universal.

Modulo Instruccional Estructuras Discretas. Teora y Prctica 6

 REA DE ELECTRNICA, CONTROL Y AUTOMATIZACIN
CTEDRA: ESTRUCTURAS DISCRETAS
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.

Se define el Conjunto Universal U como aquel que contiene todos los

elementos que estn siendo objeto de estudio. Se representa por un rectngulo y
la letra U.
El diagrama se construye con el conjunto universal y luego utilizando crculos
dentro del rectngulo, se representan los conjuntos, identificados con letras
maysculas. Los elementos se representan dentro de los conjuntos, utilizando
letras minsculas.
Ejemplo:
Conjunto
U Universal
.a
.u V .e
.o .i Conjunto de
Elemento Vocales
s

Tipos de Conjuntos:
Conjunto Vaco: es aquel que no tiene elementos. Se representa por , tambin
puede ser denotado por { }
Conjunto Unitario: es aquel que tiene un solo elemento. Ejemplo: {a}, {}, {5}
Conjunto Finito: es aquel que tiene un nmero n de elementos definidos, n > 0,
ejemplo las vocales.
Conjunto Infinito: es aquel que no es finito, es decir tiene elementos no definidos,
ejemplo el conjunto de los enteros positivos.
Subconjunto: ee dice que el conjunto A es subconjunto de B, si y solo si todo
elemento de A es tambin un elemento de B.
A B x (xA xB)

Caractersticas de Conjuntos:
Igualdad de conjuntos
Dos conjuntos son iguales si y solo si, tienen los mismos elementos.
Ejemplo:
{1, 2, 4} = {2, 4, 1} = {1, 2, 2, 2, 4}
No importa el orden, no importa que se repitan, los tres conjuntos tienen los
mismos elementos.
Tamao de un conjunto
Sea S un conjunto, si hay exactamente n elementos distintos en S, donde n es
un entero no negativo, se dice que S es un conjunto finito y n es el cardinal de S,
el cual define su tamao. El cardinal del conjunto S se denota por ISI.
Ejemplo:
A Conjunto de los enteros positivos impares menores a 10. IAI = 5
S Conjunto de las letras del alfabeto. ISI = 28
V Conjunto de las vocales. IVI = 5

Modulo Instruccional Estructuras Discretas. Teora y Prctica 7

 REA DE ELECTRNICA, CONTROL Y AUTOMATIZACIN
CTEDRA: ESTRUCTURAS DISCRETAS
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.

Conjunto vacio. II = 0 (ya que no tiene elementos)

Conjuntos Numricos Fundamentales

N = {0, 1, 2, 3,} Nmeros Naturales. Puede empezar en 0 o en 1.
Z = {.-2, -1, 0, 1, 2,.} Nmeros Enteros (+ y -)
Z+ = {1, 2, 3,.} Nmeros Enteros (+)
Q = {p/q I pZ, qZ, q0} Nmero Racionales, decimales con frecuencia.
R = Nmeros Reales
C = Nmeros Complejos
N

5. Operaciones con Conjuntos

Unin de Conjuntos
Sean A y B conjuntos. La unin de los conjuntos A y B, denotada por A U B, es el
conjunto que contiene aquellos elementos que estn en A o bien en B, o en
ambos.
A U B = {x I xA xB}
AUB
UU

A B

Ejemplo: A = {1, 3, 5} B = {1, 2, 3} entonces A U B = {1, 2, 3, 5}

Ejemplo: A = {Alumnos Ing. Computacin} B = {Alumnos Ing. Industrial}
A U B = {Alumnos en alguna de las dos ingenieras}

Interseccin de Conjuntos:
Sean A y B conjuntos. La interseccin de los conjuntos A y B, denotada por A
B, es el conjunto que contiene aquellos elementos que estn tanto en A como en
B.
A B = {x I xA xB}
AB
UU

A B

Modulo Instruccional Estructuras Discretas. Teora y Prctica 8

 REA DE ELECTRNICA, CONTROL Y AUTOMATIZACIN
CTEDRA: ESTRUCTURAS DISCRETAS
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.

Ejemplo: A = {1, 3, 5} B = {1, 2, 3} entonces A B = {1, 3}

Ejemplo: A = {Alumnos Ing. Computacin} B = {Alumnos Ing. Industrial}
A B = {Alumnos que estn en ambas ingenierias}

Diferencia de Conjuntos
Sean A y B conjuntos. La diferencia de los conjuntos A y B, denotada por A B,
es el conjunto que contiene aquellos elementos que estn en A pero no en B. La
diferencia de A B se llama tambin el complementario de B respecto a A.
A B = {x I xA xB}
A-B
UU

A B

Ejemplo: A = {1, 3, 5} B = {1, 2, 3} entonces A B = {5} y B A = {2}

Se concluye que A B B A
Ejemplo: A = {Alumnos Ing. Computacin} B = {Alumnos Ing. Industrial}
A B = {Alumnos de Ing. Computacin que no estn a la vez en Ing. Industrial}

Diferencia Simtrica de Conjuntos

Sean A y B conjuntos. La diferencia simtrica de los conjuntos A y B, denotada
por A B, es el conjunto que contiene aquellos elementos que estn en A o que
estn en B, pero no en ambos. Es lo opuesto a la interseccin.
A B = {x I xA xB}
A B
U UU

A B
U

Ejemplo: A = {1, 3, 5} B = {1, 2, 3} entonces A B = {2, 5}

Ejemplo: A = {Alumnos Ing. Computacin} B = {Alumnos Ing. Industrial}
A B = {Alumnos de Ing. Computacin que no estn a la vez en Ing. Industrial y
Alumnos de ing. Industrial que no estn a la vez en Ing. Computacin}

Conjunto Complementario
Sea U el conjunto universal. El conjunto complementario de A, denotado por A se
define como los elementos que faltan a A para ser igual a U.
_ _
A=UA A = {x I xA}
Un elemento pertenece al complemento de A, si y solo si A.

Modulo Instruccional Estructuras Discretas. Teora y Prctica 9

 REA DE ELECTRNICA, CONTROL Y AUTOMATIZACIN
CTEDRA: ESTRUCTURAS DISCRETAS
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.

__
A

U
A

Ejemplo: A = {a, e, i, o, u} y U = abecedario

B = {enteros positivos mayores que 10}
__
A = {todas las letras excepto las vocales}
__
B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

6. Representacin de Conjuntos en el Sistema Binario

Se tiene un conjunto U, donde A U y A = {a1, a2,.an} , el conjunto se
representa a travs de una cadena de bits de longitud n en donde el bit i-esimo
es 1 si aA y el bit i-esimo es 0 si aA
Los bits (sistema binario) tienen 2 posibles estados, 0 y 1, las cadenas se agrupan
en grupos de 4 bits para mayor flexibilidad en el manejo de la informacin.
Ejemplo:
Sea U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} Representar en cadenas de bits los
siguientes subconjuntos:
A = Subconjunto de los impares de U. A = 10 1010 1010
B = Subconjunto de los pares de U. B = 01 0101 0101
C = Subconjunto de los enteros menores a 5. C = 11 1110 0000
_
El complemento de A A = 01 0101 0101

Las operaciones Unin e Interseccin se hacen a travs de operaciones tipo Bit,

es decir las cadenas se operan bit a bit para obtener el resultado de la unin o
interseccin de conjuntos.

0U0=0
0U1=1
1U1=1

00=0
01=0
11=1

Modulo Instruccional Estructuras Discretas. Teora y Prctica 10