Download teoría de conjuntos

TEORÍA DE CONJUNTOS
La teoría de conjuntos es la rama de las matemáticas a la que el matemático alemán George
Cantor dio su primer tratamiento formal en el siglo XIX surgió de la necesidad de darle
rigurosidad lógica a las discusiones matemáticas con el fin de eliminar la ambigüedad del
lenguaje cotidiano. El concepto de conjunto es uno de los más fundamentales en
matemáticas, debido a que se puede encontrar implícita o explícitamente, en todas las
ramas de las matemáticas puras y aplicadas. En su forma explícita, los principios y
terminología de los conjuntos se utilizan para construir proposiciones matemáticas bien
claras y precisas y para explicar conceptos abstractos como el infinito. El término conjunto
juega un papel fundamental en el desarrollo de las Matemáticas modernas.
CONJUNTO.- Es un agregado o colección de objetos de cualquier naturaleza con
características bien definidas de manera que se puedan distinguir todos sus elementos. A los
objetos que lo componen se les llama, elementos del conjunto.
CONJUNTO.- Es una agrupación, clase o colección de objetos denominados elementos
del conjunto: utilizando símbolos como a  S representa que el elemento a pertenece o está
contenido en el conjunto S, o lo que es lo mismo, el conjunto S contiene al elemento a.
NOTACIÓN: A los conjuntos se les denota con letras mayúsculas y a sus elementos con
letras minúsculas. Para especificar un conjunto se recurre usualmente a uno de los
siguientes métodos:
1. Listar todos sus elementos, separarlos mediante comas y encerrarlos entre llaves { }
(llamado método de enumeración, de tabulación, o "por extensión"), en donde las
llaves engloba los elementos del conjunto (S) ya sea de forma explícita, escribiendo
todos y cada uno de los elementos, o dando una fórmula, regla o proposición que los
describa. El método "por extensión" es sumamente sencillo y no da lugar a
ambigüedades.
2. Encerrar entre llaves una propiedad definitoria que exprese específicamente cuáles
son los requisitos que debe satisfacer un elemento para pertenecer al conjunto
(llamado método "descriptivo" o "por comprensión"). El método "por comprensión"
proporciona un criterio práctico, para determinar si un elemento arbitrario pertenece
a un conjunto determinado: los objetos que poseen la propiedad, y sólo ellos,
pertenecen al conjunto.
EJEMPLO.- El conjunto cuyos elementos son los números 0, 7 y 14, está formado por tres
elementos. Si se designa este conjunto con la letra G, queda especificado convenientemente
mediante el método por "extensión", así: G = { 0 , 7 , 14 }.
Si se escribe V = { a , e , i , o , u } se ha especificado el conjunto de vocales del abecedario,
enumerando sus cinco elementos. Para especificar el conjunto mediante una propiedad
definitoria, se escribe: V = { x|x es una vocal del abecedario} y se lee así: V es el conjunto
de todos los elementos x, tales que x es una vocal del abecedario. La barra vertical | se lee
tal que. La x es un símbolo genérico, es decir un indicador de elementos. Cualquier otro
símbolo cumpliría la misma función; por ejemplo z, y, un asterisco, o cualquier otro
símbolo genérico.(Método Descriptivo).
SUBCONJUNTOS Y SUPERCONJUNTOS
OPERACIÓN DE CONJUNTOS
Las operaciones son formas específicas de combinar conjuntos para formar otros conjuntos.
Constituyen un sistema lógico de construcción de nuevos conjuntos en base a conjuntos
dados. Estas operaciones y sus propiedades nos llevan a la Teoría de Conjuntos como un
álgebra, o sea como un sistema matemático. En particular, se tratan las operaciones de
complementación, intersección, unión y diferencia.
UNIÓN.- Sean P y Q dos subconjuntos cualesquiera del conjunto universal U. La unión de
los conjuntos P y Q es el conjunto de los elementos de U que pertenecen por lo menos a
uno de los conjuntos P ó Q.
En símbolos:
Esta expresión se lee así: "P unión Q es el conjunto de elementos x que pertenecen a P, a Q,
o a ambos (P y Q)".
PROPIEDADES DE LA UNIÓN
i.
ii.
iii.
De la definición de unión se deduce directamente que A U B = B U A La operación
de unión de conjuntos es conmutativa.
Sea A un subconjunto cualquiera del conjunto universal U. La unión de A y Ø es
igual al conjunto A. En símbolos A U Ø = A. Por definición de unión
Sea A un subconjunto cualquiera del conjunto universal S. La unión de A y el
conjunto universal es igual al conjunto universal.
En símbolos: A U S = S. Por definición de unión
iv.
Para cualquier conjunto A se cumple que A U A = A. Por definición de unión
.
v.
La unión de un conjunto A y de su complemento A´es el conjunto universal
.
En símbolos: A U A´= U.
Por definición de unión de conjuntos
vi.
vii.
.
Si la unión de dos conjuntos es vacía, ambos conjuntos deben serlo. En símbolos: si
A U B = Ø entonces A = Ø y B = Ø.
La unión se ha definido como una operación binaria. No hay inconveniente en
extender su ámbito de aplicación y definir la unión de cualquier número (finito o
infinito) de conjuntos, como el conjunto formado por los elementos que pertenecen
al menos a uno de ellos.
Por ejemplo, para el caso de tres conjuntos A, B y C, se tiene:
para
k
cualesquiera
viii.
conjuntos
.
La operación de unión es asociativa:
A U ( B U C ) = ( A U B ) U C = A U B U C.
INTERSECCIÓN.- Sean A y B dos conjuntos cualesquiera del conjunto universal
intersección de los conjuntos A y B , es el conjunto de los elementos de
miembros tanto de A como de B. Se simboliza por A
comprensión como sigue:
. La
que son
B, y se especifica por
Esta expresión se lee así: "A intersección B, es el conjunto de elementos de
pertenecen a A y a B."
que
PROPIEDADES DE LA INTERSECCIÓN
i.
De la definición de intersección se deduce directamente que:
La operación de intersección es conmutativa.
ii.
la intersección de dos conjuntos da lugar a dos posibilidades distintas:
1.
El conjunto de interseccón no es vacío; al menos, hay un elemento común a
ambos conjuntos A y B.
En símbolos
2.
Los conjuntos A y B no tienen elementos en común; son disjuntos o
mutuamente excluyentes.
En símbolos
iii.
.
Para cualquier subconjunto A del conjunto universal
.
Por
definición
de
intersección
se cumple que
de
conjuntos
.
iv.
Para cualquier subconjunto A del conjunto universal
se cumple que
Por definición de intersección de conjuntos
v.
Para cualquier conjunto A se cumple que
Por definición de intersección
vi.
Para cualquier conjunto A se cumple que
Por definición de intersección
vii.
Se ha definido a la intersección como una operación binaria. No hay inconveniente
en extender su ámbito de aplicación y definir la intersección de cualquier número
(finito o infinito) de conjuntos, como el conjunto formado por los elementos
comunes a todos ellos. Por ejemplo, para el caso de tres conjuntos A, B y c, se
define
viii.
Para los conjuntos cualesquiera
La
operación
de
intersección
es
asociativa:
DIFERENCIA.- Sean A y B dos subconjuntos cualesquiera del conjunto universal U. La
diferencia de dos conjuntos A y B es el conjunto de elementos que pertenecen a A pero no a
B.
El conjunto diferencia se denota por A -B y se especifica por comprensión mediante la
expresión
PROPIEDADES DE LA DIFERENCIA
i.
La operación de diferencia de conjuntos no es conmutativa.
En símbolos:
En efecto A-B se ha definido como el conjunto de los elementos de A que no
pertenecen a B, o sea
conjunto de los elementos
de
B
que
no
; mientras que B - A es el
pertenecen a A, o sea:
.
ii.
De
la
definición
de
diferencia
se
deduce
directamente
que:
iii.
.
Si A es un subconjunto de B, no hay elementos de A que no estén en B, por lo que
el conjunto A - B carece de elementos.
En símbolos:
iv.
Los conjuntos (A - B), (B - A) y
son mutuamente excluyentes; la
intersección de dos cualesquiera de estos conjuntos es vacía.
En símbolos:
Nótese además que
conjuntos son totalmente exhaustivos.
. Se dice que estos
COMPLEMENTO.- Sea B un subconjunto cualquiera del conjunto universal
. El
complemento de B con respecto a U se define como el conjunto de elementos de que no
pertenecen a B. Se simboliza al complemento de B por B´, y se lo especifica por
comprensión mediante la expresión simbólica:
Esta expresión se lee así: "complemento de B es el conjunto de los elementos x que
pertenecen a U pero no pertenecen a B".
PROPIEDADES DE LA COMPLEMENTACIÓN
i.
El complemento del conjunto universal U es el conjunto vacío Ø. Recíprocamente,
el complemento del conjunto vacío es el conjunto universal.
En símbolos:
ii.
¿ Cuál es el complemento del complemento de un conjunto?
El complemento de A está formado por todos los elementos de U que no están en A´ (o sea
por todos los que no quedan fuera de A) y éstos son exactamente los elementos del
conjunto A.
En símbolos:
o sea (A´)´ = A.
LA INTERSECCIÓN Y LA INCLUSIÓN
i.
Sean P, Q y T subconjuntos cualesquiera del conjunto universal U. si T está
contenido tanto en P como en Q, también está contenido en la intersección
.
En símbolos: si
entonces
. A su vez, si un
conjunto T está incluido en la intersección de dos conjuntos P y Q, entonces está
incluido también en cada uno de ellos.
En símbolos: si
Resumiendo
ii.
ambas
.
propiedades
se
llega
a
Sean A y B dos subconjuntos cualesquiera del conjunto universal
intersección
iii.
entonces
que:
. El conjunto
está incluido tanto en A como en B. En símbolos:
Sean R y S dos subconjuntos cualesquiera del conjunto universal U. Si R es un
subconjunto de S, el conjunto intersección
símbolos:
intersección
es igual al conjunto R. En
A su vez, si el conjunto R es igual a la
,
esto
implica
Resumiendo
ambas
que
.
En
símbolos:
propiedades,
se
concluye
que
LA UNIÓN Y LA INCLUSIÓN
i.
Sean R, S y Q subconjuntos cualesquiera del conjunto universal U. Si el conjunto
unión R U S es subconjunto del conjunto Q, tanto R como S están contenidos en Q.
En símbolos:
A su vez si dos conjuntos R y S están contenidos en un tercero Q, su unión R U S,
es también un subconjunto de Q:
Resumiendo ambas propiedades, se llega a que
ii.
Sean A y B dos subconjuntos cualesquiera de U. Los conjuntos A y B son
subconjuntos de la unión A U B.
En símbolos:
Dados dos conjuntos no vacíos A y B, si A está incluido en B, el conjunto unión es
igual al conjunto B.
A su vez, si la unión de dos conjuntos no vacíos es igual a uno de ellos, entonces el
otro es subconjunto del primero. En símbolos: si A U B = B entonces
.
Resumiendo ambas propiedades se llega a que
para
.
Producto Cartesiano:
Para poder definir al producto cartesiano de dos conjuntos cualesquiera A y B
primero definiremos lo que es par ordenado:
Par Ordenado: Un par ordenado es un conjunto de dos elementos donde nos interesa el
orden en que estos aparezcan. Se representan con paréntesis y a los elementos se les
denominará componentes: (a, b) representa el par ordenado cuya primera componente es a
y su segunda componente es b. Para que dos pares ordenados sean iguales sus componentes
deben serlo: (a, b) = (c, d) si y solo si a = c y b = d.
El producto cartesiano de dos conjuntos A y B es el conjunto de todos los pares
ordenados cuya primera componente pertenece a A y cuya segunda componente pertenece a
B. Simbólicamente: A x B (a, b) / a  A y b  B
ÁLGEBRA DE CONJUNTOS O ÁLGEBRA DE BOOLE
Las siguientes propiedades utilizando las definiciones del apartado anterior se
cumplen si A, B y C... son subconjuntos de un conjunto I:
1.
2.
3.
4.
5.
6.
7.
8.
A  B , B  A
A  B = B  A
 A  B   C = A  B  C
 A B   C  A  B  C 
A  A
A  
A I  I
A I  A

9. A  B  C    A  B   A  C 
10. A  B  C    A  B   A  C 
11. A  A'  I
12. A  A'  
13.  A  B'  A'B'
14.  A  B'  A'B'
15. A  A  A  A  A
16.  A''  A
17. A  B  A  B'
18.  A  B  C  A  B  C 
19. Si A  B  , entonces  A  B  B  A
20. A  B  C    A  B   A  C 
DIAGRAMA DE VENN
Al trabajar con conjuntos, con las relaciones y operaciones entre ellos, es útil disponer de
un sistema de representación gráfica que permita visualizar lo que ocurre e interpretar con
diagramas las deducciones lógicas correspondientes.
El procedimiento usual consiste en dibujar rectángulos, círculos u otras figuras
geométricas, según un procedimiento que se conoce como "diagramas de Venn-Euler".
En un diagrama de Venn, el conjunto de puntos interiores de un rectángulo se toma como el
conjunto universal. Los subconjuntos del conjuntos universal se representan por los puntos
interiores de círculos (u otras regiones cerradas) trazados dentro del rectángulo.
Ilustraremos la utilidad de los diagramas de Venn, considerando diversos ejemplos de
representación gráfica.
i.Para un subconjunto A del conjunto universal
.
, el diagrama de Venn es el siguiente:
en el que los puntos interiores a la circunferencia representan al conjunto A, y los puntos de
rectángulo exteriores al circulo representan al conjunto A, y los puntos de rectángulo
exteriores al círculo representan al conjunto complementario A´.
ii.Para dos subconjuntos A y B del conjunto universal
, se tienen los siguientes diagramas:
En el primero se tienen dos conjuntos disjuntos, en el segundo se representan el caso de
inclusión
, en el tercero se observa el caso de inclusión
conjuntos con algunos elementos comunes.
, y en el último dos
Para representar las operaciones entre conjuntos, se tienen los siguientes diagramas:
.
En el primero, la zona rayada representa la intersección
; en el segundo, se
tiene la unión A U B; en el tercero, la diferencia A - B, y en el último la diferencia B - A.
También es necesario observar y comprobar algunas de las propiedades de esas
operaciones.
Por ejemplo, las propiedades
.
se aprecian en la figura BLa; las propiedades
.
se aprecian en la figura BLb; las propiedades
.
se aprecian en la figura BIb; las propiedades
.
se aprecian en la figura BH; las propiedades
.
se observan en los diagramas siguientes:
Finalmente, para representar gráficamente el caso de 3 subconjuntos del conjunto
universal, son usuales los siguientes diagramas:
PROPIEDADES DEL ÁLGEBRA DE CONJUNTOS
Ya hemos aprendido cómo obtener nuevos conjuntos a partir de subconjuntos dados del
conjunto universal U, aplicando ciertas operaciones y sus propiedades. Ahora resumiremos
en un cuadro único las propiedades más importantes a las que obedecen las operaciones
entre conjuntos.
Sean A, B y C subconjuntos cualesquiera no vacíos de un conjunto universal U. Entonces,
independientemente de cuáles sean las especificaciones de U, A, B y C, se verifican las
siguientes leyes de los conjuntos:
I.
de identidad
.
II.
de idempotentes
.
III.
de complementación
.
IV.
V.
de conmutatividad
de asociatividad
 A  B   C  A  B  C 
 A  B   C  A  B  C 
A  B  C   A  B  C 
VI.
de distributividad
.
VII.
de "De Morgan"
VIII.
Neutros
A E  A
A  A
IX.
Propiedad de Negación
A  A'  E
A  A'  
X.
Absorbentes
A E  E
A  
XI.
Doble Negación
 A''  A
XII.
Simplificativas
A  A  B  A
A  A  B  A
LÓGICA PROPOSICIONAL
Introducción.La lógica proposicional trabaja con sentencias u oraciones a las
cuales se les puede asociar un valor de verdad (cierto o falso), estas sentencias se conocen
como sentencias declarativas o simplemente proposiciones.
PROPOSICIÓN.- Es una idea, juicio, pensamiento, oración, sentencia. Para que sea una
proposición debemos asignarle un “valor” de verdadero falso y debe ser en forma
declarativa.
Ejemplo.- El día está soleado
Las proposiciones pueden ser simples o compuestas.
Proposición Simple o Atómica.- Son aquellas que no tienen los conectivos y /o o una
negación.
Proposición Molecular o Compuesta.- Tienen los conectivos y/ o , la negación,
“si...entonces”, “....si y solo si.....”
Otro aspecto importante es el de determinar si una proposición esta construida (o
puede ser deducida) a partir de un conjunto de proposiciones, es decir, si es una
consecuencia lógica de dicho conjunto.
La lógica proposicional (o cálculo proposicional) tiene el propósito de simbolizar
cualquier tipo de razonamiento para su análisis y tratamiento. Específicamente, para
simbolizar razonamiento, al lógica proposicional usa sentencias declarativas a las que se
puede asociar un valor de verdad; es decir usa proposiciones.
No existe una notación generalmente utilizada para representar proposiciones, pero
en este curso se identifica a cada una de ellas con un letra mayúscula (o una cadena de
letras mayúsculas).
Conectivas Lógicas.- La construcción de fórmulas compuestas requiere del uso de
elementos que permitan establecer una relación entre los átomos que la forman; estos
elementos se conocen como conectivas lógicas.
Las conectivas lógicas usadas en la lógica proposicional son cinco y son
representadas simbólicamente de varias formas, como se muestra a continuación:
Conectivo Conjunción “Y”.- Se puede encontrar expresada como: además, también, pero,
aún, aunque, sin embargo, no obstante, a pesar de que, igualmente, tanto, como, e, lo
mismo que, incluye, aún así, coma (,). Símbolos más asociados: ,&,* .
Su tabla de verdad es la siguiente:
P
V
V
F
F
Q
V
F
V
F
PQ
V
F
F
F
Conectivo Disyunción “O”.- La disyunción tiene dos significados: el exclusivo (uno, el
otro pero no ambos), el inclusivo (uno, el otro u ambos positivos). Los podemos encontrar
expresados como: al menos P o Q, como mínimo P o Q, en otro caso, de otra manera, ya
sea que, elija entre. Símbolos más asociados: , |, .
Su tabla de verdad es:
“O” Exclusivo
P
V
V
F
F
Q
V
F
V
F
P Q
F
V
V
F
“O” Inclusivo
P
V
V
F
F
Q
V
F
V
F
P Q
V
V
V
F
Conectivo Negación (No).- La negación cambia el valor de verdad. Símbolos asociados:
, ,
Tabla de verdad:
P P
V F
F V
Conectivo Condicional (Si ... entonces).- P  Q, Q siempre que P, P es condición
suficiente para que Q, Q es condición necesaria para que P, Q si P, P solamente si Q, Q con
tal de que P, dado que P entonces se asigna que Q. Su símbolo es.  .
Tabal de verdad:
P
V
V
F
F
Q
V
F
V
F
P Q
V
F
V
V
Conectivo Bicondicional (Si y solo si).- P si Q, solo si Q. Sus símbolos son: ,  .
Tabla de verdad:
P
V
V
F
F
Q
V
F
V
F
P Q
V
F
F
V
Jerarquía de Conectivas.- La jerarquía de conectivas no es más que el orden con el que se
utilizaran las conectivas ya que unas tienen mayor valor jerárquico que otras y su jerarquía
es la siguiente: negación es el operador con mayor jerarquía en la secuencia, después
teniendo el mismo nivel de potencia siguen la disyunción y conjunción, después la
condicional y por último el bicondicional.
Al tener una fórmula con la presencia de dos o más conectivas iguales, el orden de
asociatividad siempre será de izquierda a derecha.
Interpretación de fórmulas.- Es una asignación de valores de verdad a un conjunto de
átomos: para una fórmula con dos átomos se tienen dos posibles interpretaciones, para una
con tres se tienen ocho interpretaciones, y en general para una fórmula con n átomos se
tienen 2n interpretaciones.
Tautología o fórmula válida.- Una fórmula es tautología si es verdadera para todas sus
posibles interpretaciones.
Cuando una proposición molecular es siempre cierta para cualquier valor que se le
asigne a las proposiciones atómicas que la constituye.
Contradicción, Fórmula inconsistente, fórmula insatisfactible o Absurdo.- Cuando una
proposición molecular es siempre falsa para cualquier asignación de valores de certeza de
las proposiciones atómicas que la constituyen.
Contingencia.- Cuando una proposición molecular contiene los dos valores de cierto y
falso.
Proposiciones Equivalentes.- Si ellos tienen el mismo valor de certeza para las mismas
condiciones de valores de certeza de las proposiciones atómicas que la constituyen.
Fórmula Consistente o Satisfactible.- Una fórmula que al menos tiene una interpretación
verdadera.
Como consecuencia de las definiciones anteriores, se tiene que:
 Una fórmula es válida si y solo si su negación es inconsistente.
 Una fórmula es inconsistente si y solo si su negación es válida.
 Una fórmula es inválida si y solo si existe por lo menos una interpretación sobre la cual
la fórmula es falsa.
 Una fórmula es consistente si y solo si existe por lo menos una interpretación sobre la
cual la fórmula es verdadera.
 Si una fórmula es válida, entonces es consistente, pero no viceversa.
 Si una fórmula es inconsistente, entonces es inválida, pero no viceversa.
Fórmulas Equivalentes.- Existen varias equivalencias entre fórmulas de la lógica
proposicional, las cuales se conocen como leyes de equivalencia. La siguiente tabla muestra
las leyes. Se utiliza el símbolo Tautología para indicar una tautología y el símbolo
Contradicción para indicar una contradicción.
Ley de Equivalencia Fórmula
Doble Implicación
F  G  ( F  G )  (G  H )
Implicación
F  G  F  G
Distribución
F  (G  H )  ( F  G )  ( F  H )
F  (G  H )  ( F  G )  ( F  H )
Asociación
( F  G )  H  F  (G  H )
( F  G )  H  F  (G  H )
Complementación
F  F  Contradicción
F  F  Tauto log ía
 F  F
Conmutación
F G  G F
Cero
Identidad
Idempotencia
Absorción
Leyes de Morgan
F G  G  F
F  Tauto log ía  Tauto log ía
F  Contradicción  Contradicción
F  Contradicción  F
F  Tauto log ía  F
FF F
FF  F
F  F Q  F
F  ( F  Q)  F
F  F  Q  F  Q
( F  Q  H )  F  Q  H
( F  Q  H )  F  Q  H
Formas Normales.- En lógica proposicional son las formas para presentar fórmulas que
son importantes debido a que permiten definir métodos genéricos de evaluación y análisis y
de forma particular reciben el nombre de forma normal conjuntiva y forma normal
disyuntiva.
Forma Normal Conjuntiva.- Una fórmula está en su forma normal conjuntiva (FNC) si
es una conjunción de disyunciones, es decir, si tiene la forma: F1  F2  ...  Fn en la cual Fn
es una fórmula construida por una agrupación de átomos unidos por disyunciones, esto es
Fn es P1  P2  ...  Pm . En ambos casos n y m pueden ser mayores o iguales a 1.
Forma Normal Disyuntiva.- Una fórmula está en su forma normal disyuntiva (FND) si es
una disyunción de conjunciones, es decir, tiene la forma: F1  F2  ...  Fn , en la cual Fn es
una fórmula construida por una agrupación de átomos unidos por conjunciones; esto es Fn
es P1  P2  ...  Pm .
Para poder transformar cualquier fórmula a su forma normal (conjuntiva o
disyuntiva), es necesario aplicar la siguiente secuencia de operaciones de equivalencia
sobre la fórmula original:
1. Sustituir todas las ocurrencias de conectivas  y  en la fórmula usando las
correspondientes leyes de equivalencia.
2. Asegurarse que las negaciones afecten solo a átomos, usando las leyes de Morgan y la
eliminación de dobles negaciones.
3. Aplicar las otras leyes para encontrar la forma normal (las principales leyes que se
aplican son las distributivas).
Consecuencias lógicas.- Uno de los aspectos a analizar en la lógica proposicional es el de
determinar la validez de argumentos representados por fórmulas bien formadas.
ARGUMENTO.- Esta formado por las premisas, axiomas o postulados y por una
conclusión, objetivo o consecuencia lógica.
PREMISAS.- Son proposiciones que son base para la deducción de una conclusión o
consecuencia.
En términos de lógica proposicional, una consecuencia lógica es aquella fórmula
(G) que es derivada de un grupo de fórmulas (F) cumpliendo la restricción de ser verdadera
para todas las interpretaciones verdaderas del grupo de fórmulas (F). Esto es G es una
consecuencia lógica de las premisas F, si y solo si, al ser verdaderas las premisas G siempre
es verdadera.
Para comprobar si una fórmula es una consecuencia lógica de un grupo de fórmulas
se tienen dos métodos, que se producen a partir de los conceptos de validez e
inconsistencia. Estos métodos se conocen en forma de Teoremas:
Teorema 1.- Teniendo un grupo de fórmulas F1, F2 ,.....Fn y otra llamada G. G es una
consecuencia lógica de F1,F2..Fn si y solo si la fórmula ( F1  F2  ...  Fn )  G es válida.
Teorema 2.Teniendo un grupo de fórmulas F1, F2,....Fn y otra llamada G. G es ua
consecuencia lógica de F1, F2...Fn si y solo si la fórmula F1  F2  ...Fn  G es
inconsistente.
Circuitos Lógicos.- Debido a que una proposición puede ser evaluad y resultar solo
verdadera o falsa, se puede deducir alguna equivalencia con el álgebra boolenana, que
maneja solamente dos valores (0 y 1). Las propiedades del cálculo proposicional son
equivalentes a la del álgebra booleana desarrollada por Boole.
En el álgebra booleana, una proposición es equivalente a una variable y las
conectivas lógicas se utilizan como compuertas lógicas. Lo esquemas que resultan de
aplicar las compuertas lógicas se conocen como circuitos lógicos.
PRONTUARIO DE LÓGICA MATEMÁTICA
IDEMPOTENCIA:
pq  p
pq  p
LEY DE DOBLE NEGACIÓN:
( p ' )'  p
pq  q p
LEYES DE CONMUTACIÓN:
pq  q p
pqq p
p  (q  r )  ( p  q)  r
p  (q  r )  ( p  q)  r
LEYES DE ASOCIACIÓN:
p  (q  r )  ( p  q)  r
p  (q  r )  ( p  q)  ( p  r )
LEYES DE DISTRIBUCIÓN:
(q  r )  p  (q  p)  (r  p)
p  (q  r )  ( p  q)  ( p  r )
(q  r )  p  (q  p)  (r  p)
LEYES DE ABSORCIÓN:
p  ( p  q)  p
p  ( p  q)  p
LEYES DE DUALIDAD (LEYES DE DE MORGAN):
p V  V
LEYES DE IDENTIDAD:
p V  p
pF  p
pF  F
( p  q )'  p ' q '
( p  q )'  p ' q '
p  p'  V
LEYES DE COMPLEMENTO:
p  p'  F
V' F
F' V
1) p  p
2) p  q  p  ( p  q )
3) p  q  q  ( p  q )
4) p '  q  q '  p
5) p '  q  q  p
6)( p  q )'  p  q '
7)( q  p )'  p ' q
8) p  (q  q ' )  p '
9)( p  q )  p  p  q
10)( p  q )  q  p  q
11)( p  q )  q '  ( p  q )'
12)( p  q )  q '  ( p  q )'
13) p  q  ( p  q )  ( p ' q ' )
14) p  q  ( p ' q )  ( p  q ' )
15) p  q  ( p  q )  (q  p )
16) p  q  ( p  q )  ( p '  q ' )
17) p '  q  p  q '
18) p '  q '  p  q
19)( p  q )'  p  q '
20)( p  q )'  p '  q
21)( p  q )  q  p
22)( p  q )  q '  p '
23)( p  q )  r  p  (q  r )
24) p  (q  r )  q  ( p  r )
25)( p  q )  ( p  r )  p  (q  r )
26)( p  r )  (q  r )  ( p  q )  r
27)( p  q )  ( p  r )  p  (q  r )
28)( p  r )  (q  r )  ( p  q )  r
29)( p  q )  (q  r )  (r  p )  p  q  r
30) p  p
31) p  p  q
TAUTOLOGÍAS: 32) p  q  p
33) p  ( p  q )  q
34) p  ( p  q )  q
35) p '  p  q
36) p '  ( p  q )  q
37) p '  (q  p )  q '
38) p  p '  q
39) p  q  p
40) p  q  p  q
41) p  q  p  q
42) p  q  q  p
43) p  q  p  q
44)( p  q )  p '  q
45)( p  q )  ( p  q ' )
46)( p  q )  ( p '  q )
47)( p  q )'  p
48)( p  q )'  q '
49)( p  q )  p  q
50)( p  q )  q '  p '
51) p  q  (q  r )  ( p  r )
52) p  q  (r  p )  (r  q )
53)( p  q )  (q  r )  p  r
54)( p  r )  (q  r )  ( p  q )  r
55)( p  r )  (q  s )  ( p  q )  r  s
56)( p  r )  (q  s )  ( r ' s ' )  p ' q '
57) p  q  p  q
58) p  q  q  p
59) p  q  ( p  r )  (q  r )
60) p  q  ( p  r )  (q  r )
61) p  q  ( p  r )  (q  r )
62) p  q  (r  p )  (r  q )
63) p  q  ( p  r )  (q  r )
64)( p  q )  (q  r )  p  r
EQUIVALENCIAS CON LOS CONECTIVOS NEGACIÓN Y CONJUNCIÓN:
65) p  q  ( p ' q ' )'
66) p  q  ( p  q ' )'
67) p  q  ( p  q ' )'( p ' q )'
68) p  q  ( p ' q ' )'( p  q)'
69) p  q  ( p  q )'
70) p  q  p ' q '
EQUIVALENCIAS CON LOS CONECTIVOS NEGACIÓN Y DISYUNCIÓN:
71) p  q  ( p ' q ' )'
72) p  q  p ' q
73) p  q  ( p ' q ' )' ( p  q )'
74) p  q  ( p ' q )' ( p  q' )'
75) p  q  p ' q '
76) p  q  ( p  q )'
EQUIVALENCIAS CON EL CONECTIVO NAND:
77) p '  p  p
78) p  q  ( p  q )  ( p  q )
79) p  q  ( p  p )  (q  q)
80) p  q  p  (q  q)
81) p  q  ( p  q )  (( p  p )  (q  q))
82) p  q  ( p  (q  q))  (q  ( p  p ))
83) p  q  (( p  p )  (q  q ))  (( p  p)  (q  q ))
EQUIVALENCIAS CON EL CONECTIVO NOR:
84) p '  p  p
85) p  q  ( p  p )  (q  q )
86) p  q  ( p  q )  ( p  q )
87) p  q  (( p  p)  q )  (( p  p)  q )
88) p  q  ( p  (q  q ))  (q  ( p  p ))
89) p  q  ( p  q )  (( p  p )  (q  q))
90) p  q  (( p  p )  (q  q ))  (( p  p )  (q  q ))
HISTORIA DE LOS LENGUAJES DE
PROGRAMACIÓN
AÑO LENGUAJE
INVENTOR
1900s BINARIO
Bool
primer lenguaje
1946 Plankalkul
Konrad Zuse
creado para jugar al ajedrez
DESCRIPCION
1949 Short Code
lenguaje traducido a mano
1950 ASM (ensamblador)
lenguaje ensamblador
1951 A-0
Grace Hopper
fue el primer compilador
1952 AUTOCODE
Alick E. Glennie
compilador muy rudimentario
1956 FORTRAN
IBM
sistema de TRAducción de
FORmulas matemáticas
1956 COBOL
Compilador
1958 ALGOL 58
1960 LISP
1961 FORTRAN IV
1961 COBOL 61 Extendido
1960 ALGOL 60 Revisado
IBM
Interprete orientado a la Inteligencia
Artificial
sistema de TRAducción de
FORmulas matemáticas
1964 PASCAL
Niklaus Wirth
programación estructurada
1964 BASIC
Universidad de
Dartmouth
(California)
Beginners All Purpose Symbolic
Instruction Code
1965 SNOBOL
1965 APL
solo anotación
1965 COBOL 65
1966 PL/I
1966 FORTRAN 66
IBM
sistema de TRAducción de
FORmulas matemáticas
1967 SIMULA 67
1968 ALGOL 68
1968 SNOBOL4
1970s GW-BASIC
antiguo y clásico BASIC
1970 APL/360
1972 SMALLTALK
Centro de
Investigación de
Xerox en Palo Alto
pequeño y rápido
1972 C
Laboratorios Bell
lenguaje con tipos
1974 COBOL 74
1975 PL /I
Lenguaje sencillo
1977 FORTRAN 77
IBM
sistema de TRAducción de
FORmulas matemáticas
1980s SMALLTALK/V
Digitalk
pequeño y rápido
1980 C con clases
Laboratorios Bell
lenguaje con clases
1981 PROLOG
1982 ADA
1984 C++
Ministerio Japonés
de Comercio
Internacional e
Industria (MITI)
Ministerio de
Defensa de los
EE.UU.
AT&T Bell
Laboratories (Bjarne
Stroustrup)
1985 CLIPPER
1985 QuickBASIC 1.0
Lenguaje estándar para la
Inteligencia Artificial
lenguaje muy seguro
compilador
compilador para bases de datos
Microsoft®
Compilador de BASIC
1986 QuickBASIC 2.0
Microsoft®
soporte de tarjeta gráfica EGA
1987 QuickBASIC 3.0
Microsoft®
43 líneas con la tarjeta EGA
1987 QuickBASIC 4.0
Microsoft®
tarjetas Hercules, VGA
1987 CLIPPER SUMMER '87
compilador para bases de datos
1988 QuickBASIC 4.5
Microsoft®
tarjeta SVGA
1989 QuickBASIC 7.1
Microsoft®
ultima versión de QuickBASIC
1989
BASIC v5.0
interprete tipo QBASIC shareware
1990s VISUAL C++
1990s VISUAL BASIC Script
Microsoft®
lenguaje de script
Tim Berners-Lee
para internet
1993 XML
C. M. SperbergMcQueen
para internet
1993 SGML
Charles F. Goldfarb
para internet
1990
HTML
1990s WML
1990s ASP
para internet
Microsoft®
1990s PHP
1995 JAVA
para internet
para internet
Sun Microsystems
1995 CLIPPER 5.01
para internet y propósito general
compilador para bases de datos
1995 GNAT ADA95
Ministerio de
Defensa de los
EE.UU.
lenguaje muy seguro
1995 FORTRAN 95
IBM
sistema de TRAducción de
FORmulas matemáticas
1991 VISUAL BASIC 1.0
Microsoft®
1992 VISUAL BASIC 2.0
Microsoft®
1993 VISUAL BASIC 3.0
Microsoft®
1994 VISUAL BASIC 4.0
Microsoft®
1995 VISUAL BASIC 5.0
Microsoft®
1998 VISUAL BASIC 6.0
Microsoft®
1990s C#
2001 VISUAL BASIC .NET
Microsoft®
La evolución de Visual Basic