UNIDAD II
Álgebra de Boole
MATEMÁTICA DISCRETA
MATEMÁTICA DISCRETA
Unidad II
ÁLGEBRA DE BOOLE
Revisado y Actualizado por
Prof. Dra. Martha Cuenca
Asunción, enero 2019
2
TABLA DE CONTENIDO
INTRODUCCIÓN ............................................................................................... 3
LÓGICA ............................................................................................................. 3
Reseña histórica ...................................................................................... 3
Lógica de proposiciones .......................................................................... 4
Proposiciones .......................................................................................... 5
Expresiones lingüísticas que no son proposiciones ................................. 6
Tipos de proposiciones ............................................................................ 7
Valor de verdad de una proposición atómica ........................................... 7
Términos de enlace ................................................................................. 8
Función proposicional .............................................................................. 8
Valor de verdad de una proposición atómica ........................................... 7
Axiomas de la negación ......................................................................... 10
Proposiciones compuestas .................................................................... 11
Tablas de verdad ................................................................................... 12
Valor de verdad de una proposición compuesta .................................... 13
Tautología y contradicción ..................................................................... 15
Equivalencia lógica ................................................................................ 15
Cuantificadores ...................................................................................... 16
ÁLGEBRA DE BOOLE .................................................................................... 17
Antecedentes del Álgebra de Boole ....................................................... 17
Definición ............................................................................................... 18
Descripción del Álgebra de Boole .......................................................... 18
Funciones Lógicas ................................................................................. 19
Operaciones y expresiones booleanas .................................................. 20
Suma lógica o suma booleana............................................................... 22
Producto lógico o multiplicación booleana ............................................. 23
Ilustración de las leyes y reglas del Álgebra de Boole ........................... 23
Reglas del Álgebra Booleana ................................................................ 25
Relación entre Álgebra de Conjuntos, Álgebra de Proposiciones y
Álgebra de Boole ................................................................................... 25
EJERCICIOS DE FIJACIÓN DE CONCEPTOS Y PROPIEDADES ................ 26
BIBLIOGRAFÍA ............................................................................................... 29
3
INTRODUCCIÓN
Con el estudio de la Lógica se pretende llegar a ser preciso y cuidadoso. La
Lógica tiene un lenguaje exacto, y simbólico proposicional, en los que interviene
relaciones y cuantificadores.
La lógica moderna que surge en el último tercio del siglo XIX, como una disciplina
íntimamente vinculada a las matemáticas y a consideraciones relativas al
lenguaje de éstas, es hoy una ciencia altamente especializada relacionada con
otras ramas de la cultura, tales son el derecho, la psicología, la gramática, la
lingüística, la filosofía, la computación.
No obstante, la estrecha relación existente entre la matemática moderna y la
lógica formal es una de sus características fundamentales.
En las matemáticas y la lógica matemática, el Álgebra de Boole es la subárea
del álgebra en la cual los valores de las variables que son los valores de la verdad
verdadera y falsa, es denotado generalmente por 1 y 0 respectivamente, será
estudiado en esta unidad.
1. LÓGICA
1.1. Reseña histórica
Etimológicamente el término lógica significa la ciencia de los logos. En efecto, el
vocablo logos traduce palabra o discurso, hecho por el cual se definió a la lógica
como una rama de la gramática que estudia ciertos estilos del lenguaje. En este
contexto, se hace necesario la elaboración de argumentos para defender o
refutar pensamientos o posturas ideológicas, se recurrió a métodos para poder
evaluar o verificar la validez de dichos razonamientos. En este sentido, el gran
filósofo griego Aristóteles, tiene el honor de ser el primer sistematizador de los
conceptos de la lógica que los condensó en el célebre texto denominado
“Organon”, en este ensayo, el filósofo trata a la lógica como un simple método
de las ciencias, debido que los propósitos de la lógica se encaminaban a estudiar
las estructuras del pensamiento. En concordancia con lo anterior, la lógica
Aristotélica resalta la estrecha conexión entre los conceptos de categoría,
definición, juicio de valor, proposición y silogismo, es decir, desarrollar la lógica
proposicional, estableciendo los procedimientos para demostrar la verdad o
4
falsedad de las proposiciones compuestas y de los silogismos, esto indica que,
en la antigüedad, la lógica estuvo asociada al conjunto del pensamiento de las
diferentes doctrinas filosóficas y religiosas.
Por su parte, el término lógica matemática fue acuñado en los años 500 a.C. por
el pensador Lao-Tse, al llegar a una evidente conclusión: “El total es mayor que
sus partes” al referirse a la relación existente entre las partes separadas y el
conjunto coordinado de esas partes.
Asimismo, es de capital importancia los aportes del matemático alemán Gottfried
Leibniz quien fue el primero en formular la estrecha conexión entre la lógica y la
matemática, además, introdujo los símbolos matemáticos para hacer
representaciones proposicionales.
En el siglo XIX, los avances de esta ciencia se deben a los aportes de los
matemáticos George Boole y Augustus Morgan.
Años más tarde, el matemático alemán Georg Cantor, ya referido en la Unidad I,
establece la teoría de conjuntos y sus operaciones y la hace la conexión de los
operadores lógicos para la unión, la intersección, diferencia y complemento.
En 1910, aparece la obra “Principio matemático” de Bertrand Russell y Alfred
Whitehead, en donde redefinen los conceptos básicos de la aritmética en
términos y conceptos de la lógica, estableciendo los fundamentos de las
matemáticas puras, esto es, la lógica formal moderna y sus poderosos
instrumentos para el avance de las matemáticas y las demás ciencias.
(Sandoval, s/f)
1.2. Lógica de proposiciones
Arenas (2011), expone que la lógica de proposiciones es la parte más elemental
de la lógica moderna o matemática, donde las inferencias se construyen sin
tomar en cuenta la estructura interna de las proposiciones, sólo se examinan las
relaciones lógicas existentes entre proposiciones consideradas como un todo, y
de ellas se toma en cuenta su propiedad de ser verdaderas o falsas. Por esta
razón emplea variables proposicionales.
5
La lógica de proposiciones estudia las relaciones formales extraproposicionales,
es decir, aquellas relaciones existentes entre proposiciones y no las que se dan
dentro de ellas. Se la denomina, también, lógica de las proposiciones sin
analizar. Dispone de medios de análisis formal de las inferencias (lenguaje
simbólico y métodos específicos), y la validez de éstas se determina por las
relaciones entre proposiciones consideradas como un todo, sin penetrar en su
estructura interna.
Por su parte, Moret (2014) refiere que la lógica proposicional o lógica de orden
cero es un sistema formal cuyos elementos más simples representan
proposiciones, y cuyas constantes lógicas, llamadas conectivas, representan
operaciones sobre proposiciones, capaces de formar otras proposiciones de
mayor complejidad.
La lógica proposicional trata con sistemas lógicos que carecen de
cuantificadores. En lógica proposicional si bien no hay signos para variables de
tipo entidad, sí existen signos para variables proposicionales, es decir, que
pueden ser interpretadas a manera de proposiciones con un valor de verdad de
definido, de ahí el nombre proposicional. La lógica proposicional incluye además
de variables interpretables como proposiciones simples, signos para conectivas
lógicas, por lo que dentro de este tipo de lógica puede analizarse la inferencia
lógica de proposiciones a partir de proposiciones, pero sin tener en cuenta la
estructura interna de las proposiciones más simples.
1.3. Proposiciones
El lenguaje, en sentido estricto, es un sistema convencional de signos, es decir,
un conjunto de sonidos y grafías con sentido, sujeto a una determinada
articulación interna. Sirve para afirmar o negar (oraciones aseverativas o
declarativas); expresar deseos (oraciones desiderativas); formular preguntas
(oraciones interrogativas); expresar sorpresa o admiración (oraciones
exclamativas o admirativas) e indicar exhortación, mandato o prohibición
(oraciones exhortativas o imperativas).
De todas estas clases de oraciones, la lógica sólo toma en cuenta las
declarativas o aseverativas, las únicas que pueden constituir proposiciones,
según cumplan o no determinados requisitos.
6
La proposición es una oración aseverativa de la que tiene sentido decir que es
verdadera o falsa.
Ejemplo 1
a) Dolly fue la primera oveja clonada. (es una proposición verdadera)
b) El átomo es una molécula. (es una proposición falsa)
Ambas proposiciones tienen sentido, aunque una sea verdadera y la otra sea
falsa. En consecuencia, la verdad y la falsedad son sus propiedades, es decir,
sólo las proposiciones pueden ser verdaderas o falsas. Arenas (2011)
Para Suppes (2004), con el estudio de la Lógica se persigue llegar a ser preciso
y cuidadoso. La Lógica tiene un lenguaje exacto.
Sin embargo, es necesario redactar un conjunto de reglas que sean claras y
definidas, libres de las vaguedades que pueden hallarse en el lenguaje cotidiano.
Una expresión del lenguaje a la cual puede aplicarse con sentido, uno y sólo uno
de los calificativos “verdadera” o “falsa”, esa es una proposición.
1.3.1. Expresiones lingüísticas que no son proposiciones
Siguiendo con Arenas (2011), todas las proposiciones son oraciones, pero no
todas las oraciones son proposiciones. En efecto, las oraciones interrogativas,
las exhortativas o imperativas, las desiderativas y las exclamativas o admirativas
no son proposiciones porque ninguna de ellas afirma o niega algo y, por lo tanto,
no son verdaderas ni falsas. Asimismo, las oraciones dubitativas, así como los
juicios de valor, no obstante afirmar algo, no constituyen ejemplos de
proposiciones, pues su verdad o falsedad no puede ser establecida.
Finalmente, toda proposición es una oración aseverativa, pero no toda oración
aseverativa es una proposición.
Ejemplo 2
a) ¿Qué es la lógica? (no es proposición porque es una oración interrogativa)
b) Debemos honrar a nuestros héroes. (no es proposición porque es una
oración imperativa o exhortativa)
7
c) Sea en hora buena. (no es proposición porque es una oración
desiderativa)
d) ¡Por Júpiter! ¡Casi me saco la lotería! (no es proposición porque es una
oración exclamativa).
e) Quizá salga el sol esta tarde. (no es proposición porque es una oración
dubitativa).
f) Walter es solidario. (no es proposición porque constituye un juicio de
valor).
g) El triángulo es inteligente. (oración aseverativa, pero no es proposición).
1.3.2. Tipos de proposiciones
Dice Suppes (2004), que se consideran y simbolizan dos clases de proposiciones
en Lógica: atómicas y moleculares.
Atómicas son las proposiciones de forma más simples o elementales; son
aquellas que carecen de conjunciones gramaticales típicas o conectivas.
Ejemplo 3. Son proposiciones atómicas
a) El sol alumbra de noche
b) El doble de 500 es menor que el triple de 100.
c) Los alumnos de Informática estudian Programación Lineal.
En tanto, si se juntan una o varias proposiciones atómicas con un término de
enlace se tiene una proposición molecular. (Suppes, 2004)
1.3.3. Valor de verdad de una proposición atómica
Se denomina valor verdadero o de verdad de una proposición a su veracidad o
falsedad. El valor de verdad de una proposición verdadera es verdad (V) y el de
una proposición falsa es falso (F). Lo que nunca puede ocurrir es que una
proposición sea al mismo tiempo falsa y verdadera. (González, 2005)
Ejemplo 4. Escribe el valor de verdad de cada una de las siguientes
proposiciones atómicas, marcando con una V las verdaderas y con una F las
falsas.
a) Caacupé está ubicada sobre el Río Paraná. (F)
8
b) Todos los cuadriláteros tienen cuatro lados. (V)
c) La roca es un mineral. (V)
d) El doble de 1500 es 4000. (F)
1.3.4. Términos de enlace
Se denominan términos de enlace de proposiciones a las palabras de enlace
entre proposiciones atómicas.
Son términos de enlace que permiten obtener proposiciones moleculares, los
siguientes conectivos: “y”; “o”; “si... entonces”; “si y sólo si”, o del adverbio de
negación “no”.
En las proposiciones conjuntivas no es necesario que sus proposiciones
componentes estén relacionadas en cuanto al contenido; es suficiente la
presencia de la conjunción “y”. Arenas (2011)
Ejemplo 5. Son proposiciones moleculares
a) El círculo es un polígono o el triángulo es un polígono. (término de enlace
“o”)
b) Si dos ángulos adyacentes forman un par lineal, entonces son
suplementarios. (término de enlace “si…, entonces”)
c) Rubén y Juana son estudiantes de Informática de la Universidad
Americana. (término de enlace “y”)
Menciona Suppes (2004) que las proposiciones se indican por medio de una letra
minúscula, dos puntos y la proposición propiamente dicha.
Ejemplo 6
p: El ser humano es mortal.
q: Mauricio come pizza o bebe jugo de frutas.
1.4. Función proposicional
Expresa Carreño (1993) que se llama función proposicional o proposición
abierta a una proposición en que el sujeto está dado en forma de símbolo y
9
puede ser reemplazado por alguno de los elementos de un conjunto fijado con
anterioridad.
𝒑 (𝒙): 𝒙 𝒆𝒔 𝒖𝒏 𝒏𝒖𝒎𝒆𝒓𝒐 𝒏𝒂𝒕𝒖𝒓𝒂𝒍 𝒙 ∈ ℝ
Cada vez que el símbolo o variable (x) sea reemplazado por un elemento del
conjunto (en este caso ℝ) la función proposicional pasa a ser proposición y tiene
su valor de verdad.
Ejemplo 7. Determina cuáles de las siguientes expresiones son proposiciones y
cuáles son funciones proposicionales.
a) Los números mayores que 2 son negativos. (Es proposición, su valor de
verdad es falso)
b) El número entero “x” es mayor que 10. (Es función proposicional, según
el valor que tome “x”, su valor de verdad será verdadero o falso)
a) Los múltiplos de 3 son infinitos. (Es proposición, su valor de verdad es
verdadero)
b) Los enteros “x” ; “y” son factores de 12. (Es función proposicional, según
los valores que tomen “x” ; “y” será su valor de verdad)
Ejemplo 8
Si x = 2 “2 es número natural” es Verdadero (V)
Si x = 0,5 “0,5 es numero natural” es Falso (F)
Siguiendo con Carreño (1993), al conjunto al que pertenece la variable se le
llama dominio o universo de la función proposicional.
Las funciones proposicionales pueden tener más de una variable.
𝑞 (𝑥, 𝑦): 𝑥 𝑒 𝑦 𝑣𝑖𝑎𝑗𝑎𝑟𝑜𝑛 𝑒𝑛 𝑒𝑙 𝑏𝑢𝑞𝑢𝑒 𝐸𝑠𝑚𝑒𝑟𝑎𝑙𝑑𝑎 𝑒𝑛 𝑒𝑙 𝑎ñ𝑜 1992
La negación de una proposición es aquella que modifica la proposición dándole
sentido contrario.
𝑝 ∶ 5 𝑒𝑠 𝑚𝑎𝑦𝑜𝑟 𝑞𝑢𝑒 2
La negación de 𝑝 se denota ∼ 𝒑
10
Ejemplo 9
∼ 𝒑 ∶ 5 𝑛𝑜 𝑒𝑠 𝑚𝑎𝑦𝑜𝑟 𝑞𝑢𝑒 2 ó
∼ 𝒑 ∶ 𝑒𝑠 𝑓𝑎𝑙𝑠𝑜 𝑞𝑢𝑒 5 𝑛𝑜 𝑒𝑠 𝑚𝑎𝑦𝑜𝑟 𝑞𝑢𝑒 2
Ejemplo 10
Sean 𝒑 ∶ 𝒙 . 𝒚 > 𝟎 ; 𝒒: 𝒙 > 𝒐 ; 𝒓: 𝒚 > 𝒐 𝒙, 𝒚 𝝐 ℝ , 𝒙 , 𝒚 ≠ 𝟎
a) Explica qué significa ∼ 𝒒 , ∼𝒓 , ∼𝒑
b) Escribe en símbolos la siguiente proposición: “el producto de dos números
reales es mayor que cero si y sólo si ambos son positivos o ambos son
negativos”.
Solución
a) Como 𝒙, 𝒚 𝝐 ℝ 𝒚 𝒙 , 𝒚 ≠ 𝟎, entonces:
∼ 𝒒: 𝒙 < 𝒐 ; ∼ 𝒓: 𝒚 < 𝒐 ; ∼ 𝒑: 𝒙 . 𝒚 < 𝟎
b) Sean las proposiciones:
𝒑 ∶ 𝑒𝑙 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑜 𝑑𝑒 𝑑𝑜𝑠 𝑛ú𝑚𝑒𝑟𝑜𝑠 𝑥 𝑒 𝑦 𝑒𝑠 𝑚𝑎𝑦𝑜𝑟 𝑞𝑢𝑒 𝑐𝑒𝑟𝑜
𝒒 ∶ 𝑥 𝑒𝑠 𝑚𝑎𝑦𝑜𝑟 𝑞𝑢𝑒 𝑐𝑒𝑟𝑜
𝒓 ∶ 𝑦 𝑒𝑠 𝑚𝑎𝑦𝑜𝑟 𝑞𝑢𝑒 𝑐𝑒𝑟𝑜
Así, la simbolización solicitada es: 𝒑 ↔ (𝒒 ∧ 𝒓) ∨ (∼ 𝒒 ∧ ∼ 𝒓)
1.5. Axiomas de la negación
𝒑 𝑦 ∼ 𝒑 tienen valores de verdad contrarios.
11
1.6. Proposiciones compuestas
Con respecto a las proposiciones, específicamente, las proposiciones simples,
éstas dan origen a nuevas proposiciones, las llamadas proposiciones
compuestas, cuando se conectan a través de los siguientes conectivos lógicos:
Ejemplo 11
𝑆𝑖 𝑎 . 𝑏 = 0 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑎 = 0 ó 𝑏 = 0
𝑝 ∶ 𝑎 .𝑏 = 0
𝑞∶ 𝑎 =0
𝑟∶ 𝑏=0
Son proposiciones simples que dan origen a la proposición compuesta
enunciada y que simbólicamente se escribe:
𝒑 → (𝒒 ∨ 𝒓)
Es decir,
(𝒂 . 𝒃) = 𝟎 → (𝒂 = 𝟎 ∨ 𝒃 = 𝟎)
El condicional 𝒑 → 𝒒 se puede expresar de las siguientes maneras:
El bicondicional 𝒑 ↔ 𝒒 a su vez se puede expresar de las siguientes formas:
12
1.6. Tablas de verdad
Según Hernández (2017), la tabla de verdad fue desarrollada por Charles
Sanders Peirce por los años 1880, pero el formato más popular es el que
introdujo Ludwig Wittgenstein en su Tractatus logico-philosophicus, publicado
en 1921.
La tabla de los “valores de verdad”, es usada en el ámbito de la lógica, para
obtener la verdad (V) o falsedad (F), valores de verdad, de una expresión o de
una proposición.
Las tablas de verdad son, por una parte, uno de los métodos más sencillos y
conocidos de la lógica formal, pero al mismo tiempo también uno de los más
poderosos y claros. Entender bien las tablas de verdad es, en gran medida,
entender bien a la lógica formal misma.
Para construir la tabla de verdad, la misma dependerá del número de
proposiciones, ajustada a la relación: 𝟐𝒏 donde la base de la potencia indica los
valores de verdad, es decir, Verdadero, o Falso, y el exponente, indica el número
de proposiciones.
Ejemplo 12
▪ Si se tiene una sola proposición, entonces n = 1, y 𝟐𝒏 = 𝟐𝟏 = 𝟐. El valor
de verdad será Verdadero o Falso.
▪ Si se tienen dos proposiciones, “p” y “q” respectivamente, entonces n = 2,
y 𝟐𝒏 = 𝟐𝟐 = 𝟒, es el número de filas que deberá tener la tabla. El valor de
verdad dependerá de los conectivos entre las proposiciones.
13
La tabla inicial se construye de la siguiente manera:
▪ Si se tienen tres proposiciones, “p” ; “q” y “r” respectivamente, entonces
n = 3, y 𝟐𝒏 = 𝟐𝟑 = 𝟖, es el número de filas que deberá tener la tabla. El
valor de verdad dependerá de los conectivos entre las proposiciones.
La tabla inicial se construye de la siguiente manera:
1.7. Valor de verdad de una proposición compuesta
Dice González (2005), que el valor de verdad de una proposición compuesta
depende del valor de verdad de las proposiciones simples que la forman según
las tablas de verdad, que se expone a continuación.
14
Disyunción
Conjunción
Condicional
Bicondicional
La conectiva disyunción ∨ se usa con una variante si se considera en forma
excluyente. Se denotará por ∆ y su tabla de verdad es:
15
Disyunción excluyente
1.8. Tautología y contradicción
Se definen los siguientes tipos de proposiciones según los valores de su tabla
de verdad:
Una proposición es una tautología, cuando todos los valores de su tabla de
verdad son verdaderos. La tautología es una proposición siempre verdadera
independientemente de los valores de verdad o falsedad de las proposiciones
simples que la constituyen.
Una proposición es una contradicción, cuando todos los valores de su tabla de
verdad son falsos. Por tanto, es falso, independientemente de los valores de
verdad o falsedad de las proposiciones simples que la constituyen.
Una proposición es indeterminada cuando en su tabla de verdad hay valores
verdaderos y falsos. Esto indica que su valor lógico depende de los valores de
verdad o falsedad de las proposiciones simples que la constituyen. (García Valle,
1994)
1.9. Equivalencia lógica
Las proposiciones compuestas 𝒑 y 𝒒 son lógicamente equivalentes y se escribe
𝒑 ≡𝒒 ó 𝒑 ⟺ 𝒒
cuando ambas proposiciones tienen los mismos valores de verdad.
De esta definición se sigue que para probar que dos proposiciones son
lógicamente equivalentes hay que probar que si 𝒑 es verdad, 𝒒 también ha de
serlo y que si 𝒑 es falso, 𝒒 tiene que ser falso. (González, 2005)
16
Ejemplo 13. Demuestra las Leyes de De Morgan (a cargo del alumno)
a) ~(𝒑 ∨ 𝒒) ⟺ ~𝒑 ∧ ~𝒒
b) ~(𝒑 ∧ 𝒒) ⟺ ~𝒑 ∨ ~𝒒
1.10. Cuantificadores
Los símbolos ∀ y ∃ se llaman cuantificador universal y cuantificador
existencial, respectivamente, y se leen para todo y existe.
El cuantificador universal presenta una variante que es ∃! que significa existe un
único.
Ejemplo 14
Si 𝑝(𝑥) es una proposición abierta (o función proposicional) y E es el conjunto en
el cual se define (dominio o universo de la función), entonces:
1. (∀ x ∈ E), p(x)se lee: "para todo x en E, tal que p(x)" o "para cada x de E, p(x)".
2. (∃ x ∈ E), p(x)se lee: "existe x en E tal que, p(x)" o existe por lo menos un x en E tal que, p(x)".
3. (∃! x ∈ E), p(x)𝑠𝑒 𝑙𝑒𝑒:existe un único x en E, tal que p(x)" o 𝑒𝑥𝑖𝑠𝑡𝑒 𝑠ó𝑙𝑜 𝑢𝑛 𝑥 ∈ 𝐸 𝑡𝑎𝑙 𝑞𝑢𝑒 p(x)".
Así podemos decir que:
1. (∀ x ∈ E), p(x) ↔ [𝑝(𝑥1 ) ∧ 𝑝(𝑥2 ) ∧ 𝑝(𝑥3 ) ∧ … ]
2. (∃ x ∈ E), p(x) ↔ [𝑝(𝑥1 ) ∨ 𝑝(𝑥2 ) ∨ 𝑝(𝑥3 ) ∨ … ]
3. (∃! x ∈ E), p(x) ↔ [𝑝(𝑥1 ) ∆ 𝑝(𝑥2 ) ∆ 𝑝(𝑥3 ) ∆ … ]
Si a una función proposicional se le agrega un cuantificador ésta pasa a ser una
proposición puesto que tiene un valor de verdad.
Ejemplo 15
𝑆𝑒𝑎 𝑝(𝑥): 𝑥 𝑒𝑠 𝑢𝑛 𝑚ú𝑙𝑡𝑖𝑝𝑙𝑜 𝑑𝑒 2
𝐸 = {𝑥 ∈ ℕ|𝑥 < 10} = {1,2,3,4,5,6,7,8,9}
(∀ x ∈ E), p(x)𝑒𝑠 𝑓𝑎𝑙𝑠𝑎 𝑝𝑢𝑒𝑠𝑡𝑜 𝑞𝑢𝑒 ℎ𝑎𝑦 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠 𝑑𝑒 𝐸 𝑞𝑢𝑒 𝑛𝑜 𝑠𝑜𝑛 𝑝𝑎𝑟𝑒𝑠.
(∃ x ∈ E), p(x) 𝑒𝑠 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑟𝑎 𝑝𝑢𝑒𝑠𝑡𝑜 𝑞𝑢𝑒 ℎ𝑎𝑦 𝑎𝑙 𝑚𝑒𝑛𝑜𝑠 𝑢𝑛 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜 𝑑𝑒 𝐸 𝑞𝑢𝑒 𝑒𝑠 𝑝𝑎𝑟.
(∃! x ∈ E), p(x) 𝑒𝑠 𝑓𝑎𝑙𝑠𝑎 𝑦𝑎 𝑞𝑢𝑒 𝑒𝑥𝑖𝑠𝑡𝑒 𝑚á𝑠 𝑑𝑒 𝑢𝑛 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜 𝑑𝑒 𝐸 𝑞𝑢𝑒 𝑒𝑠 𝑝𝑎𝑟.
17
Leyes de Morgan para cuantificadores
1. ~(∀ x ∈ E), 𝑝(𝑥) ↔ (∃ x ∈ E), ~p(x)
2. ~(∃ x ∈ E), 𝑝(𝑥) ↔ (∀ x ∈ E), ~𝑝(𝑥)
Lo que significa:
1. “Es falso que para todo x en E se cumple p(x)” es equivalente a “existe algún
x en E tal que no se cumple p(x)”.
2. “Es falso que existe x en E tal que se cumple p(x)” es equivalente a “para todo
x en E, no se cumple p(x)”. (Carreño, 1993)
Ejemplo 16. Sean las siguientes proposiciones:
𝒑 ∶ ∀ 𝐱 ∈ ℕ, 𝐱 + 𝟐 > 𝟎
𝒒 ∶ ∃𝐱 ∈ ℕ,𝐱−𝟏 ∉ ℕ
a) Determina su valor de verdad
b) Escribe ~ 𝒑 𝑦 ~ 𝒒
Solución
a) 𝒑 𝑒𝑠 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑟𝑎 𝑝𝑜𝑟𝑞𝑢𝑒 𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑜 𝑛ú𝑚𝑒𝑟𝑜 𝑛𝑎𝑡𝑢𝑟𝑎𝑙 𝑥, 𝑥 + 2 > 𝑜
𝒒 𝑒𝑠 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑟𝑎 𝑝𝑜𝑟𝑞𝑢𝑒 𝑒𝑥𝑖𝑠𝑡𝑒 𝑢𝑛 𝑛ú𝑚𝑒𝑟𝑜 𝑛𝑎𝑡𝑢𝑟𝑎𝑙 𝑥, 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑥 − 1 𝑛𝑜 𝑒𝑠 𝑛𝑎𝑡𝑢𝑟𝑎𝑙.
Ese número es 1, puesto que 1 – 1 = 0 ∉ ℕ.
b) ~ 𝒑 ∶ ∃ 𝐱 ∈ ℕ , 𝐱 + 𝟐 ≤ 𝟎
c) ~ 𝒒 ∶ ∀ 𝐱 ∈ ℕ, 𝐱 − 𝟏 ∈ ℕ
2. ÁLGEBRA DE BOOLE
2.1. Antecedentes del Álgebra de Boole
Expone García Valle (1994) que en 1847 un matemático inglés autodidacta
llamado George Boole (1815 – 1864), desarrolla unos símbolos matemáticos con
unas reglas que pueden ser aplicadas en problemas de lógica deductivas.
Después e su muerte, algunos matemáticos perfeccionaron su sistema para
hacerlo más utilizable.
18
Posteriormente, en 1938, el científico Claude Shannon lo aplica a relés y circuitos
de conmutación. A partir de entonces, el Álgebra de Boole se ha utilizado en el
diseño de los circuitos lógicos de las computadoras, pues permite simplificar las
conexiones físicas reduciendo el hardware y consiguientemente el espacio
necesario para alojarlo.
2.2. Definición
Siguiendo con García Valle (1994), el álgebra booleana son reglas algebraicas,
basadas en la teoría de conjuntos, para manejar ecuaciones de lógica
matemática.
2.3. Descripción del Álgebra de Boole
El Álgebra de Boole permite expresar, en forma de funciones matemáticas, tanto
la realización de cálculos en el sistema binario como la adopción de decisiones
a través de la combinación de proposiciones.
Cantidades y cualidades pueden ser representadas por conjuntos de “ceros” y
“unos”, es decir, mediante palabras binarias cuyos dígitos pueden adoptar
solamente los valores 0 y 1; cada dígito o “bit” corresponde a una variable.
Una función booleana establece una dependencia entre una variable de salida
“y” y un conjunto de variables de entrada “a b c…”: una correspondencia entre el
conjunto de valores de las variables de entrada y el valor de la variable de salida.
Las funciones booleanas son “multiformes”, es decir, pueden representarse de
muy diversas formas: desde el mero enunciado textual que expresa las
especificaciones o requisitos que definen la función, hasta su forma algebraica
como operaciones entre variables, pasando por su tabla funcional (o “tabla de
verdad”) que detalla, en forma de listado, el valor de la función para cada
conjunto de valores de las entradas.
Precisamente el diseño del circuito digital correspondiente a una función
booleana consiste en el “cambio de forma” de la misma, a partir de su enunciado,
construyendo su tabla funcional y extrayendo de ella la forma algebraica de la
función; dicha expresión algebraica puede ser trasladada directamente a un
esquema de puertas lógicas que conforma el circuito digital de dicha función.
19
En este proceso resulta de mucha importancia la simplificación de la expresión
algebraica de la función, de forma que contenga el menor número de términos y
el menor número de variables posible. Al reducir la expresión algebraica
disminuye el tamaño, la complejidad y el coste (y, en muchos casos, aumenta la
velocidad) del circuito digital que permite “obtener” tal función. (Pollán, s/f)
2.4. Funciones Lógicas
Dentro del Álgebra de Boole de dos elementos, una función booleana o función
lógica es una expresión de operaciones booleanas enlazando variables que
solamente pueden adquirir los valores 0 y 1.
Una función booleana es una aplicación que a cada conjunto de valores
booleanos de sus variables le asigna un y sólo un valor booleano.
La primera de las dos definiciones anteriores es de tipo “descriptivo”, describe la
forma algebraica de una función booleana; mientras que la segunda es de tipo
“conceptual”, identifica la función como correspondencia entre el conjunto de
valores de las variables y el valor booleano de la variable dependiente.
Las funciones lógicas pueden representarse en dos formas diferentes:
▪ Por su expresión algebraica o fórmula booleana, como expresión de las
operaciones que ligan a sus variables;
▪ Por su tabla operativa o tabla de verdad, expresando en forma de tabla la
correspondencia entre la variable de salida y cada combinación posible
de valores de sus variables de entrada.
También puede expresarse una función en forma de enunciado o texto que
manifiesta las especificaciones o requisitos que dan lugar a dicha función y en
forma gráfica como circuito digital o esquema de puertas lógicas que produce los
valores de salida de la función al recibir los correspondientes valores en sus
entradas.
El proceso de síntesis o “construcción digital” de una función parte del enunciado
o especificaciones de la misma, para configurar la “tabla de verdad” de la función
y obtener, a través de ella, su expresión algebraica; una vez simplificada, dicha
expresión puede ser directamente trasladada a un esquema de puertas como
representación gráfica del circuito digital que “hace efectiva” dicha función.
20
enunciado → tabla funcional → expresión algebraica → esquema de puertas
Dada una función de m variables, cada una de las posibles combinaciones de
valores de dichas m variables recibe el nombre de vector de entrada; el número
total de vectores de entrada será 2m y tal será el número de filas que ha de tener
la tabla funcional completa.
Para cada vector de entrada podemos construir un término mínimo, formado por
el producto booleano (operación “y”) de las m variables de entrada, estando cada
una de ellas afirmada si su valor en el vector de entrada es 1 y negada cuando
vale 0. (Pollán, s/f)
2.5. Operaciones y expresiones boolenas
Floyd (2006), sostiene que el Álgebra de Boole son las matemáticas de los
sistemas digitales.
Los términos variable, complemento y literal son términos utilizados en el álgebra
booleana:
▪ Una variable es un símbolo que se utiliza para representar magnitudes
lógicas. Una variable puede tener el valor 0 o 1.
▪ El complemento es el inverso de una variable y se indica mediante una
̅.
barra encima de la misma. Así, el complemento de 𝑨 𝑒𝑠 𝑨
▪ Un literal es una variable o el complemento de una variable.
Indica García Valle (1994), que un conjunto cualquiera 𝑨 en el cual se han
definido dos operaciones binarias denominadas suma lógica (+) y producto
lógico ( ∙ ), y una operación binaria llamada complemento, se dice que es un
Álgebra de Boole si se cumple las siguientes propiedades axiomáticas:
Conmutativa
∀ 𝐚 , 𝐛 ∈ 𝐀, 𝐚 + 𝐛 = 𝐛 +𝐚 𝐲 𝐚 .𝐛 = 𝐛 .𝐚
Identidad. Los elementos neutros de (+) y ( ∙ ) son, respectivamente, el
elemento ( 0 ) y el elemento unidad ( 1 ):
∀ 𝐚 ∈ 𝐀, 𝐚 + 𝟎 = 𝐚 𝐲 𝐚 .𝟏 = 𝐚
Distributiva. De la (+) y del ( ∙ ) respecto a (+):
21
∀ 𝐚 , 𝐛 , 𝐜 ∈ 𝐀, 𝐚 + (𝐛 . 𝐜) = (𝐚 + 𝐛). (𝐚 + 𝐜) 𝐲
𝒂 . (𝒃 + 𝒄) = (𝒂 . 𝒃) + (𝒂 . 𝒄)
Complementario
∀ 𝐚 ∈ 𝐀, ̅ = 𝟏 𝐲 𝐚 .𝒂
𝐚+𝒂 ̅ = 𝟎
De los axiomas anteriores, se deducen las consecutivas tablas para las
operaciones de la suma lógica (+) y del producto lógico ( ∙ ).
Suma lógica
Producto lógico
Asimismo, se tiene:
Estas operaciones indica Martin (2010), cumplen los cuatro axiomas ya
mencionados, y se denominan:
22
1) AND (Y lógico) a la operación del producto lógico
2) OR (O lógico) a la operación de la suma lógica
3) NOT (NO lógico) a la operación de complementación
Además, refiere el mismo autor que la electrónica digital es el estudio y
realización de circuitos que realizan las funciones AND, OR, NOT y sus
combinaciones.
2.5.1. Suma lógica o suma booleana
Expone Floyd (2006) que la suma lógica o suma booleana es equivalente a la
operación OR. El término suma es 1 si al menos uno de sus literales son 1. El
término suma es cero solamente si cada literal es 0.
En el Álgebra de Boole, el término suma es una suma de literales. En los
circuitos lógicos, un término suma se obtiene con la operación OR, sin que exista
̅; 𝑨 + 𝑩
ninguna operación AND. Así: 𝑨 + 𝑩; 𝑨 + 𝑩 ̅ + 𝑪.
Ejemplo 17
Ejemplo 18
Determina los valores de A, B, y C que hacen la suma de la expresión
𝐴̅ + 𝐵 + 𝐶̅ = 0.
Solución
Cada literal debe ser = 0; por lo tanto A = 1, B = 0 y C = 1.
23
2.5.2. Producto lógico o multiplicación booleana
La multiplicación booleana es equivalente a la operación AND. El producto de
literales forma un término producto. El término producto será 1 solamente si
todos literales son 1.
En el álgebra de Boole, el término producto es un producto de literales. En los
circuitos lógicos, un término producto se obtiene con la operación AND, sin que
exista ninguna operación OR. Se tiene: 𝐴𝐵 ; 𝐴𝐵̅ ; 𝐴𝐵𝐶 ; 𝐴𝐵𝐶̅ 𝐷
̅ . (Floyd, 2006)
Ejemplo 19
Ejemplo 20
¿Cuáles son los valores de A, B y C si el término producto de 𝐴. 𝐵̅ . 𝐶̅ =1?
Solución
Cada literal debe ser = 1; por lo tanto A = 1, B = 0 y C = 0.
2.6. Ilustración de las leyes del Álgebra de Boole
Las leyes del Álgebra de Boole ya enunciadas más arriba se presentan
seguidamente de manera ilustrativa, recordando que éstas son las mismas que
en el álgebra ordinaria. Floyd (2006)
Leyes conmutativas
Las leyes conmutativas se aplican a la suma y la multiplicación.
24
1. Para la suma la ley conmutativa declara: En términos del resultado, el orden
en el cual se suman (OR) las variables es indiferente.
2. Para la multiplicación la ley conmutativa declara: En términos del resultado, el
orden en el cual se multiplican (AND) las variables, es indiferente.
Leyes asociativas
Las leyes asociativas se aplican también a la suma y la multiplicación.
1. Para la suma la ley asociativa declara: Cuando se suman (OR) más de dos
variables, el resultado es el mismo a pesar del agrupamiento de las variables.
2. Para la multiplicación la ley asociativa declara: Cuando se multiplican (AND)
más de dos variables, el resultado es el mismo a pesar del agrupamiento.
Ley distributiva
La ley distributiva es la ley de factorización. Una expresión que contiene factores
comunes se puede factorizar tal como en el álgebra ordinaria.
25
La ley distributiva se puede ilustrar con circuitos equivalentes:
2.7. Reglas del Álgebra Booleana
Siguiendo con Floyd (2006) se enumeran a continuación, las reglas básicas y
muy útiles, para la manipulación y simplificación de expresiones booleanas.
Ejemplo 21. Aplica las reglas del Álgebra Booleana y calcula,
̅)
𝑨 + (𝑨 . 𝑨
Aplicando las reglas correspondientes se tiene,
̅) = 𝑨 + 𝟎 = 𝑨
𝑨 + (𝑨 . 𝑨
2.8. Relación entre Álgebra de Conjuntos, Álgebra de Proposiciones y
Álgebra de Boole
El conjunto de las partes de un conjunto tiene estructura de Álgebra de Boole,
con las operaciones unión e intersección, y las propiedades de la
complementación.
26
El conjunto de las proposiciones lógicas tiene estructura de Álgebra de Boole
con los conectivos disyunción, conjunción y negación.
Las equivalencias entre las operaciones de estas tres álgebras se exponen en la
tabla de abajo. (García Valle, 1994)
EJERCICOS DE FIJACIÓN DE CONCEPTOS Y PROPIEDADES
Aplica adecuadamente los conceptos y las propiedades estudiados
1. Señala cada proposición atómica con una A y cada proposición molecular con
una M.
a) Las frutas tropicales no son buenas para la salud.
b) El 20 es un número par.
c) Gael canta y Luana es chef.
d) 5 es el inverso aditivo de -5.
e) La lluvia es un fenómeno natural.
f) Si García Lorca fue un poeta, entonces gauss fue un matemático.
g) Iré de compras si y solo si tengo efectivo.
2. Determina si las siguientes expresiones son o no proposiciones. Si lo son,
determina su valor de verdad.
a) p: Las vacas son invertebrados.
b) q: Celebremos tu cumpleaños.
c) m: Mozart es un pintor famoso.
d) n: El 25% de 400 más el 10% de 500 es 15.
e) t: 1000 < 285
27
3. Determina cuáles de las siguientes expresiones son proposiciones y cuáles
son funciones proposicionales.
a) 80º es el suplemento de 100º.
3
b) 𝑥 𝑒𝑛 ℚ 𝑒𝑠 𝑒𝑞𝑢𝑖𝑣𝑎𝑙𝑒𝑛𝑡𝑒 𝑎 4.
c) El conjunto de los números naturales es parte de los números enteros.
d) Los enteros “a” y “b” son factores de 90.
4. Verifica si las siguientes proposiciones son o no una tautología:
a) 𝑝 → (𝒒 → 𝒑)
b) (𝒑 → 𝒒) → (∼ 𝒒 ⟶ ~ 𝒑)
5. Representa cada proposición con el término de enlace correspondiente.
a) Nueve es igual a diez o nueve es mayor que cinco.
b) O Juan es el ganador o Luciano es el ganador.
c) El Pentium no es un microprocesador.
d) Si el candidato M gana las elecciones, entonces bajará los impuestos.
6. Completa la siguiente tabla de verdad para las proposiciones dadas, y obtiene
el valor de verdad de: ∼ 𝒑 ⟶ ~ 𝒒
7. Aplica las reglas del Álgebra Booleana y calcula:
̅ ) + (𝑨 . 𝟏) =
a) (𝑨 + 𝑨
̅) =
b) (𝑨 . 𝟏) + (𝑨 + 𝑨
28
8. Completa la siguiente tabla de verdad para las proposiciones dadas:
9. Utiliza las variables 1 y 0 del álgebra booleana para obtener el valor de verdad
de la proposición (𝑝 ⟶ ~ 𝒒) 𝑉 (𝑞 ⟶ 𝒑 ) y concluye si es una tautología o una
contradicción.
10. Completa la siguiente tabla de verdad para las proposiciones dadas:
29
BIBLIOGRAFÍA
Arenas, W. (2011). Proposiciones. Recuperado de
[Link]
Carreño, X.; Cruz, X. (1993). Álgebra Arrayán. Chile, Santiago: Editorial Lord
Cochrane.
Floyd, F. (2006). Fundamentos de sistemas digitales. 9ª Edición. Madrid:
Pearson Prentice Hall.
García Valle, J. (1994). Matemáticas especiales para computación. 2ª Edición.
Madrid: McGraw-Hill.
González, F. (2005). Lógica de proposiciones. Apuntes de Lógica Matemática.
Recuperado de [Link]
Hernández, N. (2017). Tablas de verdad. Recuperado de [Link]
fnhp8bnfd/tabla-de-la-verdad/.
Martin, M.J. (2010). Recuperado de [Link]
tecnicas/electronica/contenido/electronica/Tema6_AlgebraBOOLE.pdf.
Moret, V. (2014). Representación del conocimiento y razonamiento automático.
Universidad de A Coruña. Recuperado de
[Link]
Pollán, T. (s/f). Funciones booleanas y su simplificación. Recuperado de
[Link]/~tpollan/libro/Apuntes/[Link].
Sandoval. F. (s/f). Lógica matemática. Recuperado de
[Link]
df? t.
Sendra, J. (s/f). Álgebra de Boole. Electrónica digital. Recuperado de
[Link]
ownload/transparencias/algebra_boole.pdf.
Suppes, P.; Hill, S. (2004). Introducción a la lógica matemática. México: Reverte
Ediciones S.A.
