Logica-matematica 6g6l6a

Apuntes de Lógica para computación Prof. Amaury Camargo Ben´ıtez Índice ´ Indice

1

´ ´ 1. LOGICA MATEMATICA ´ 1.1. LOGICA PROPOSICIONAL . . . . . . . . . . . . . . . . . 1.1.1. Proposiciones y Tablas de Verdad . . . . . . . . . . 1.1.2. Tablas de verdad . . . . . . . . . . . . . . . . . . . . 1.1.3. Equivalencias Proposicionales . . . . . . . . . . . . . ´ 1.2. ALGEBRA DE PROPOSICIONES . . . . . . . . . . . . . . ´ 1.3. INFERENCIAS LOGICAS . . . . . . . . . . . . . . . . . . 1.4. Cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1. Reglas para el uso . . . . . . . . . . . . . . . . . . . 1.4.2. Cuantificadores con varias variables . . . . . . . . . 1.4.3. Negando proposiciones con Cuantificadores . . . . . 1.4.4. Negando proposiciones con más de un cuantificador 1.4.5. Reglas para el uso . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

3 3 3 5 9 11 15 21 25 28 30 30 31

2. Sistemas de numeraci´ on 2.1. Concepto de codificaci´ on . . . . . . . . . . . . . . . . . . . . . 2.2. Sistema de numeraci´ on decimal . . . . . . . . . . . . . . . . . 2.3. Sistema de numeraci´ on binaria . . . . . . . . . . . . . . . . . 2.3.1. Conteo en binario . . . . . . . . . . . . . . . . . . . . 2.4. Sistema de numeraci´ on octal . . . . . . . . . . . . . . . . . . 2.5. Sistema de numeraci´ on hexadecimal . . . . . . . . . . . . . . 2.6. Conversi´ on entre sistemas de numeración . . . . . . . . . . . 2.6.1. Conversi´ on decimal a binario . . . . . . . . . . . . . . 2.6.2. Conversi´ on del sistema decimal al octal . . . . . . . . 2.6.3. Conversi´ on entre los sistemas binario y octal . . . . . 2.6.4. Conversi´ on del sistema decimal a hexadecimal . . . . . 2.6.5. Conversi´ on entre los sistemas hexadecimales y binario 2.7. Operaciones aritméticas en el sistema binario . . . . . . . . . 2.7.1. Suma binaria . . . . . . . . . . . . . . . . . . . . . . . 2.7.2. Resta binaria . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

33 33 33 34 34 35 35 36 36 37 39 40 41 41 42 42

1

ÍNDICE

ÍNDICE

2.7.3. Multiplicaci´ on binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. Conjuntos 3.1. Definiciones B´ asicas . . . . . . . . . . 3.2. Operaciones entre conjuntos . . . . . . 3.2.1. Uni´ on . . . . . . . . . . . . . . 3.2.2. Intersecci´ on . . . . . . . . . . . 3.2.3. Diferencia . . . . . . . . . . . . 3.2.4. Complementario . . . . . . . . 3.2.5. Diferencia Simétrica . . . . . . ´ 3.3. Algebra de conjuntos : Dualidad . . . 3.3.1. Leyes Idempotentes . . . . . . 3.3.2. Leyes Conmutativas . . . . . . 3.3.3. Leyes Asociativas . . . . . . . . 3.3.4. Leyes Distributivas . . . . . . . 3.3.5. Leyes de Identidad . . . . . . . 3.3.6. Ley Involutiva . . . . . . . . . 3.3.7. Leyes del Complementario . . . 3.3.8. Leyes de De D’Morgan . . . . . 3.4. Conjuntos finitos, principio de conteo .

43

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

44 44 44 44 44 45 45 45 45 45 46 46 47 48 49 49 50 54

´ 4. Nociones sobre Algebra de Boole ´ 4.1. Definici´ on de Algebra de Boole . . . . . . . . . . . 4.1.1. Principio de dualidad del álgebra de Boole . 4.1.2. Propiedades en un ´ algebra de Boole . . . . 4.2. Expresiones de Boole: Forma suma de productos . 4.2.1. Definici´ on de maxterm y minterm . . . . . 4.3. Obtenci´ on de las formas can´ onicas . . . . . . . . . 4.4. Simplificaci´ on de funciones Booleanas . . . . . . . 4.4.1. Método algebraico . . . . . . . . . . . . . . 4.4.2. Mapas de Karnaugh (K) . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

59 59 60 61 61 63 64 68 68 70

. . . .

83 83 83 84 84

5. Compuertas L´ ogicas 5.1. Compuerta NAND . . . . 5.2. Compuerta NOR . . . . . 5.3. Compuerta XOR . . . . . 5.3.1. Compuerta XNOR

Lero y Jose

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . . . . . .

. . . .

2

. . . . . . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Amaury Camargo B

1

´ ´ LOGICA MATEMATICA


1.

Se puede decir, que la l´ ogica es la ciencia de los principios de inferencia o razonamientos formalmente válidos. Lo espec´ıfico de un razonamiento o inferencia consiste en derivar una conclusión a partir de unas premisas, siguiendo una regla de inferencia dada llamada modus ponens. De esta conclusión se dice que es formalmente v´ alida, es decir, que si sus premisas son verdaderas entonces la conclusión también es verdadera. La l´ ogica se ocupa de la validez de los razonamientos y no de la verdad o falsedad de los enunciados que la componen. Cabe anotar también, que la l´ ogica se apoya en una serie de reglas las cuales le dan un significado preciso a los enunciados o sentencias matem´ aticas. Estas reglas se usan para distinguir entre argumentos v´ alidos y no válidos. Considerando que uno de los principales objetivos de estas notas (apuntes) es ense˜ nar al lector cómo entender y construir argumentos matemáticos correctos. Además de su importancia en el razonamiento matemático,la lógica tiene numerosas aplicaciones en ciencias de la computaci´ on. Las reglas de la lógica se usan en el dise˜ no de circuitos de ordenador,la construcción de programas inform´ aticos, la verificación de que un programa está bien construido y en muchas otras aplicaciones.

1.1. 1.1.1.

´ LOGICA PROPOSICIONAL Proposiciones y Tablas de Verdad

En el desarrollo de cualquier teor´ıa matemática se hacen proposiciones en forma de frases y que tienen un sentido pleno. Tales proposiciones, verbales o escritas, las denominaremos enunciados o proposiciones. Proposici´ on. Llamaremos proposici´ on a cualquier armación que sea verdadera o falsa, pero no ambas cosas a la vez. Valor de verdad de una proposici´ on. Llamaremos valor verdadero o de verdad de una proposición a su veracidad o falsedad. El valor de verdad de una proposici´ on verdadera es verdad (V ) y el de una proposición falsa es falso (F ). Por ejemplo: El tablero de este sal´ on es verdeel tablero del salón 19 − 01 es blanco . Ambas son proposiciones. De la primera no tenemos dudas si es verdadera o falsa y de la segunda no hay certeza, sin embargo, también es una proposici´ on y no es necesario estar en la capacidad de saber personalmente la respuesta. Por ejemplo, 1. Cuando se deja caer un cuerpo, va hacia arriba. (F) 2. Cuando se coloca una piedra en un recipiente de agua, el volumen es el mismo (F) 3. Una funci´ on es impar siempre y cuando sea monótona (F) 4. Todas las palabras esdr´ ujulas llevan acento (V) 5. La orbita de la tierra es el´ıptica, por lo tanto hay sectores del planeta en que son mas cálidos que otros (V) Lero y Jose

3

Amaury Camargo B

1.1

´ LOGICA PROPOSICIONAL

1


6. En los CDs se puede intercambiar información indefinidamente (F) 7. Todo numero real elevado a la cero da uno (F) Observaci´ on: Por otra parte se tienen expresiones como “Viajar en la noche”o “mirar televisi´ on ”. Las cuales no son proposiciones, puesto que de ellas no se puede decir que sean verdaderas o falsas. Nota. Toda afirmaci´ on es verdadera o falsa, y no hay una afirmación que sea verdadera y falsa al mismo tiempo. Esta suposici´ on la llamamos la Ley del tercero excluido Una consecuencia de esta suposici´ on es que si una afirmación no es falsa tendrá que ser verdadera; a partir de proposiciones podemos construir otras proposiciones. Operaciones b´ asicas Las palabras (y,o,si... entonces, etc.),(llamados conectivos o conectores lógicos) nos permitirán formar nuevas proposiciones a partir de proposiciones simples, y además, conociendo los valores de verdad de dichas proposiciones, podremos deducir el valor de verdad de la proposición que se construya. Observaci´ on: Cada proposici´ on tiene una forma l´ ogica a la cual se le da un nombre. Se distinguen dos tipos de proposiciones: simples y compuestas. Una proposición se denomina simple cuando en ella no interviene ning´ un conectivo l´ ogico o término de enlace (y, o, no, si,... entonces..., si y sólo si). Si se juntan una o varias proposiciones simples con un término de enlace, se forma una proposición compuesta. Los términos de enlace,(y,o,si... entonces, etc.); se usan para ligar dos proposiciones, en cambio el término de enlace “no” se agrega a una sola proposición. La forma de las proposiciones compuestas depende del término de enlace utilizado, y no del contenido de la proposici´ on o proposiciones simples. Es decir si en una proposición compuesta se sustituyen las proposiciones simples por otras proposiciones simples cualesquiera, la forma de la proposición compuesta se conserva. Nota: Generalmente se representan las proposiciones con letras latinas may´ usculas o min´ usculas como p, q, r, ... Un ejemplo, Teniendo como base las proposiciones: P : 2 es un n´ umero primo, Q: 10 es m´ ultiplo de 2, podemos construir nuevas proposiciones, por ejemplo: P y Q: 2 es un n´ umero primo y 10 es m´ ultiplo de 2, P o Q: 2 es un n´ umero primo o 10 es m´ ultiplo de 2.

Lero y Jose

4

Amaury Camargo B

1.1


1.1.2.

1


Tablas de verdad

Una tabla de verdad muestra las relaciones entre los valores de verdad de proposiciones. Las tablas de verdad son especialmente valiosas a la hora de determinar los valores de verdad de proposiciones construidas a partir de proposiciones más simples. La tabla 1 muestra los dos posibles valores de verdad de una proposici´ on p y los correspondientes valores de verdad de su negación ∼ p. El operador negaci´ on construye una nueva proposición a partir de la proposición individual existente. Ahora introduciremos los operadores l´ ogicos que se usan para formar nuevas proposiciones a partir de dos o más proposiciones ya creadas. Esos operadores lógicos se llaman también conectivos l´ ogicos. Una tabla de verdad es una representaci´ on esquemática de las relaciones entre proposiciones; sirve para determinar los valores de verdad de proposiciones compuestas, las cuales dependen de los conectivos utilizados y de los valores de verdad de sus proposiciones simples.

Tabla 1 p ∼p V F F V P : El tablero de este sal´ on es verde. ∼ P : El tablero de este salón no es verde.

Aunque es simple, no debe confundirse ∼ P con lo contrario de P. La negaci´ on de ”Juan es rico”; no es ”Juan es pobre” ´ CONJUNCION.(∧) (Corresponde al “y ” del lenguaje com´ un). Sean P y Q proposiciones. La afirmación P ∧ Q se lee ”P y Q” es intuitivamente verdadera si ambas son verdaderas y falsa si alguna de ellas es falsa, pero su definición precisa se consigna en la siguiente tabla, que llamamos tabla de verdad. Tabla 2 P Q P ∧Q V V V V F F F V F F F F Nota: En el lenguaje com´ un la palabra “y” podrá tener otros significados (pero, también, a´ un), sin embargo para nosotros el significado es el que nos da la tabla. ´ DISYUNCION:(∨)

Lero y Jose

5

Amaury Camargo B

1.1


1


(Corresponde al “o” del lenguaje com´ un). Las proposiciones P ∨ Q se lee “P ó Q”, intuitivamente P ∨ Q es verdadero si cualquiera de las dos proposiciones lo es o si ambas lo son. Tabla 3 P Q P ∨Q V V V V F V F V V F F F Nota: Este en un “o” inclusivo y no exclusivo. En el lenguaje coloquial muchas veces no se permite que ambas sean verdaderas. Después del almuerzo como postre o me lavo los dientes. En la afirmación anterior dada en lenguaje com´ un uno entiende que no har´ a las dos cosas después de almuerzo. Aqu´ı el “o” es exclusivo, pero en el lenguaje matem´ atico el “o” que se usa es el inclusivo. CONDICIONAL:(⇒) (Corresponde al “Si,...,entonces...” del lenguaje com´ un). La afirmación P ⇒ Q se lee “Si P entonces Q”, intuitivamente es verdadera si nunca ocurre que P sea verdadera y que Q sea falso al mismo tiempo. La definición precisa es: Tabla 4 P Q P ⇒Q V V V V F F F V V F F V Las dos primeras l´ıneas son “cre´ıbles”, las dos u ´ltimas nos cuestan más trabajo. Tratemos de entenderlas con el siguiente ejemplo. “Si Jorge se toma las sopas, entonces yo le compro un helado”. ¿Cuál ser´ıa el u ńico caso en el que Jorge reclamar´ıa?. Es claro que si Jorge se toma las sopas y yo le compro el helado, entonces la afirmaci´ on condicional se verifica; También es claro que si Jorge se toma las sopas y yo no le compro el helado, entonces la afirmaci´ on condicional no se verifica; ahora, si Jorge no se toma las sopas y yo le compro el helado, entonces la afirmaci´ on condicional se verifica. Por u ´ltimo, se cumple que si Jorge no se toma las sopas y yo no le compro el helado, la afirmación condicional se verifica. P ⇒ Q se puede escribir Q ⇐ P. Donde P es el antecedente y Q es el consecuente. As´ı pues, los dos u ´ltimos renglones de la tabla los interpretamos as´ı: Si el antecedente es falso, cualquier cosa puede ocurrir con el consecuente. P ⇒ Q se lee “si P, Q”; “Q si P ”; “P s´ olo si Q”; “Q siempre que P ”; “suponiendo P , entonces Q”; “Q dado que P ”; “P es suficiente para Q” y “Q es necesario para P ”. En el ejemplo siguiente, todas las proposiciones quieren decir lo mismo. Lero y Jose

6

Amaury Camargo B

1.1


1


1. Si p es un n´ umero par, p = 2m para alg´ un m ∈ Z. 2. p = 2m para alg´ un m ∈ Z, si p es par. 3. p es un n´ umero para s´ olo si p = 2m para alg´ un m ∈ Z. 4. p = 2m para m ∈ Z siempre que p sea par. 5. Suponiendo que p sea par entonces p = 2m para alg´ un m ∈ Z. 6. p es par es suficiente para que p = 2m para alg´ un m ∈ Z. 7. p = 2m para alg´ un m ∈ Z es necesario para que p sea par. BICONDICIONAL: (⇔) El conocimiento que tenemos de las tablas para ⇒ y ∧, y un análisis cuidadoso de la siguiente tabla (nótese que las columnas intermedias corresponde a las proposiciones más simples que conforman (P ⇒ Q) ∧ (Q ⇒ P ))

P V V F F

Q V F V F

Tabla 5 Q⇒P (P ⇒ Q) ∧ (Q ⇒ P ) V V V F F F V V

P ⇒Q V F V V

revela que la tabla de verdad para P ⇔ Q es la siguiente:

P V V F F

Tabla 6 Q P ⇔Q V V F F V F F V

´ EXCLUYENTE:(Y) DISYUNCION (Disyunción exclusiva): Si P y Q son proposiciones, la expresión P Y Q es una abreviatura de la proposición (P ∨ Q) ∧ P ∧ Q, de tal manera, su tabla de verdad se calcula como sigue:

P V V F F Lero y Jose

Q V F V F

P ∨Q V V V F

Tabla 7 P ∧Q Q∧P V F F V F V V F 7

(P ∨ Q) ∧ Q ∧ P F V V F Amaury Camargo B

1.1


1


Esto es, P V V F F

Tabla 8 Q P YQ V F F V V V F F

Observaci´ on: Si P y Q son proposiciones, entonces P Y Q es una proposición que es verdadera precisamente cuando los valores de verdad de P y Q no coinciden. En otras palabras, P Y Q es verdadera si se tiene que s´ olo P es verdadera, o se tiene que s´ olo Q es verdadera, pero no cuando ambas son verdaderas ni cuando ambas son falsas. (Ilustración) 1. Tráiganlo vivo o (tr´ aiganlo) muerto es una instancia de la disyunción excluyente. 2. (6 > 2) Y (6 < 2) es una ejemplo más formal. Observaci´ on: Cuando se trabaja con proposiciones, es indispensable el buen uso de los paréntesis; su descuido provoca numerosos errores. El papel de los paréntesis es similar al de la puntuación en nuestra gramática; separa unidades m´ as peque˜ nas dentro del discurso. Su importancia radica en que debemos procurar que lo que escribamos en Matemáticas no esté sujeto a interpretaciones distintas, es decir, que carezca de ambig¨ uedad. Tome en cuenta que un cambio en la puntuación puede modificar completamente el sentido de la frase. Nota: En el álgebra elemental, el uso de paréntesis en proposiciones tiene análoga utilidad y similares convenciones que el uso de paréntesis en expresiones algebraicas. También en el álgebra elemental puede cambiar el significado de la expresi´ on seg´ un los “separadores” que se emplea. Veamos algunos situaciones: 1. Considere la conocida y mal hecha pregunta ¿Cuál es la mitad de dosmás dos?. Como se sabe, 1 1 la respuesta depende de si usted entiende la pregunta como · 2 + 2, ó bien · (2 + 2) . 2 2 2. Note sin embargo que cuando se escribe ab + c todo el mundo entiende (ab) + c y no a (b + c) . En otras palabras, si usted quiere escribir (ab) + c, puede escribir ab + c, pero si quiere escribirlo tal cual. Para referirse a esta situaci´ on convencional, se suele decir que “la suma prevalece sobre la multiplicación”, ó bien que “el producto se hace antes que la suma”. Estas expresiones en espa˜ nol no son excelentes, pero no traen problema si se las usa correctamente. En cualquier caso, usted puede escribir 2 + 3 × 5 y todos entenderán 17 (y no 25). Lero y Jose

8

Amaury Camargo B

1.1


1


3. Ahora bien, si usted quiere escribir el n´ umero a (bc) puede escribir abc, pero puede escribir también abc para expresar (ab) c. Esto se debe a la ley de la asociatividad en los n´ umeros, que dice que si tiene a (bc) = (ab) c y entonces, la expresión abc puede significar cualquiera de las dos. 1.1.3.

Equivalencias Proposicionales

Equivalencias L´ ogicas Un tipo importante de paso utilizado en argumentos matemáticos es la sustitución de una sentencia por otra de igual valor de verdad. As´ı, en la construcción de argumentos matemáticos se emplean con frecuencia métodos que producen proposiciones con el mismo valor de verdad que una fórmula dada. Comenzaremos nuestra discusi´ on con una clasificación de de las fórmulas seg´ un sus posibles valores de verdad. Dos proposiciones l´ ogicamente equivalentes son dos proposiciones cuyos valores de verdad coinciden l´ınea por l´ınea en una tabla de verdad, y de esta manera tienen el mismo significado. Por ejemplo, las proposiciones P ⇔ Q y (P ∧ Q) ∨ (∼ P ∧ ∼ Q) son lógicamente equivalentes, como podemos ver en la siguiente tabla de verdad. P V V F F

Q V F V F

∼P F F V V

∼Q F V F V

(P ∧ Q) V F F F

(∼ P ∧ ∼ Q) F F F V

(P ⇔ Q) V F F V

(P ∧ Q) ∨ (∼ P ∧ ∼ Q) V F F V

Esto se evidencia en la coincidencia l´ınea por l´ınea de las dos u ´ltimas columnas. La equivalencia l´ ogica de P ⇔ Q y (P ∧ Q) ∨ (∼ P ∧ ∼ Q) la expresamos de la siguiente manera (P ⇔ Q) ≡ (P ∧ Q) ∨ (∼ P ∧ ∼ Q) Un ejemplo importante (como veremos más adelante) de equivalencia lógica es el siguiente (P ⇒ Q) ≡ (∼ Q) ≡ (∼ P ) Que son lógicamente equivalentes, podemos verlo en la tabla siguiente P V V F F

Q V F V F

∼P F F V V

∼Q F V F V

P ⇒Q V F V V

(∼ Q) ⇒ (∼ P ) V F V V

Otras dos equivalencias l´ ogicas importantes son las conocidas como Leyes de Morgan: 1. ∼ (P ∧ Q) ≡ (∼ P ) ∨ (∼ Q) 2. ∼ (P ∨ Q) ≡ (∼ P ) ∧ (∼ Q) Lero y Jose

9

Amaury Camargo B

1.1


1


Verifique estas dos equivalencias como un ejercicio. Definici´ on: Una fórmula que siempre es verdadera, no importa los valores de verdad de las proposiciones que la componen, se llama tautolog´ıa. Una f´ ormula que es siempre falsa se denomina contradicci´ on. Finalmente, una proposici´ on que no es ni una tautolog´ıa ni una contradicción se denomina contingencia. Definici´ on: Diremos que las proposiciones p y q son l´ ogicamente equivalentes si p ⇔ q es una tautolog´ıa. La notaci´ on p ≡ q denota que p y q son l´ ogicamente equivalentes Nota: El s´ımbolo ≡ no es un conectivo l´ ogico, puesto que p ≡ q no es una fórmula, sino la afirmación de que p ⇔ q es una tautolog´ıa. Observaci´ on: Una tabla de verdad para una f´ ormula dependiente de tres proposiciones diferentes requiere ocho filas, una para cada posible combinaci´ on de los valores de verdad de las tres proposiciones. En general, se requieren 2n filas si una f´ ormula depende de n proposiciones. Un ejemplo, Notemos en las tablas siguientes, que si P, Q son proposiciones cualesquiera, entonces P ∨ ∼ P es una tautolog´ıa, P ∧ P es un absurdo y P ∨ Q es una contingencia (a menos que p sea una tautolog´ıa, o que Q sea una tautolog´ıa, o bien que P y Q sean absurdos). P V V F F

Q V F V F

P ∧Q V F F F

Q∧P V F F F

P ∧Q⇔Q∧P V V V V

Si P, Q, R son proposiciones, entonces: 1. (P ∧ Q) ∧ R ⇔ P ∧ (Q ∧ R) 2. (P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R)

Lero y Jose

10

Amaury Camargo B

1.2

´ ALGEBRA DE PROPOSICIONES

1


La tabla siguiente ilustra uno de los dos casos anteriores: P V F V F V F V F

1.2.

Q V V F F V V F F

R V V V V F F F F

P ∨Q V V V F V V V F

Q∨R V V V V V V F F

(P ∨ Q) ∨ R V V V V V V V F

P ∨ (Q ∨ R) V V V V V V V F

(P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R) V V V V V V V V


Cuando se trabaja con proposiciones, la situación es análoga a la ley descrita. 1. (Asociatividad): Las propiedades de asociatividad de la conjunción y de la disyunción indican que, (P ∧ Q) ∧ R ⇔ P ∧ (Q ∧ R) (P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R) Esto permitirá escribir sin ambig¨ uedad: P ∧ Q ∧ R y P ∨ Q ∨ R. Algo análogo ocurre con la disyunci´ on excluyente. 2. (Distributividad): Contrario a la asociatividad, no son equivalentes las siguientes expresiones; (P ∧ Q) ∨ R ⇔ P ∧ (Q ∨ R) (P ∨ Q) ∧ R ⇔ P ∨ (Q ∧ R) Esto u ´ltimo, se puede comprobar, haciendo la tabla de verdad respectiva; esto obliga a escribir con los respectivos paréntesis: ya sea exactamente (P ∧ Q) ∨ R si es que piensa en esa expresión, o bien precisamente P ∧ (Q ∨ r) si eso es lo que quiere escribir. 3. (No asociatividad): Algo similar ocurre con (P ⇒ Q) ⇒ R P ⇒ (Q ⇒ R) P ⇔ (Q ⇔ R) P ⇔ (Q ⇔ R) y as´ı, en estos casos, es indispensable escribir los paréntesis. 4. De acuerdo a propiedades que se ver´ a más adelante y para simplificar la escritura, se conviene que la implicaci´ on y la equivalencia prevalecen sobre la conjunci´ on y la disyunci´ on.

Lero y Jose

11

Amaury Camargo B

1.2


1


Esto significa, por ejemplo, que la expresión P ∧ Q ⇒ R significa (P ∧ Q) ⇒ R pero P ∧ Q ⇒ R no significa P ∧ (Q ⇒ R) . Insistimos en que se trata aqu´ı s´ olo de una convención para simplificar la escritura (no hay en esto algo necesario sino simplemente conveniencia). 5. Es conveniente también en escribir ∼ (∼ P ) en lugar de ∼∼ P

En resumen: 1. Se puede escribir, sin ambig¨ uedad y por propiedades lo siguiente: P ∧ Q ∧ R, P ∨ Q ∨ R, P Y Q Y R 2. Se puede escribir, sin ambig¨ uedad y por convenciones: P ∧ Q ⇒ R,

P ∨Q⇒R

3. No se debe escribir, pues no son proposiciones: P ∧ Q ∨ R,

P ∨ Q ∧ R,

P ⇒ Q ⇒ R,

P ⇔ Q ⇔ R,

P ⇒Q⇔R

No se tienen propiedades ni convenios que permitan siquiera escribir las expresiones inmediatamente anteriores. Observe al pasar que la frase Tomo el bus y como chocolate o bebo agua. Tiene dos interpretaciones distintas –seg´ un d´ onde se ponga la separación (la coma, el paréntesis)– y por tanto no podemos aceptarla. Bien entendido, los siguientes cuadros contienen toda la información relevante de esta sección: P V V F F

Q V F V F

P ∨Q V V V F

P ∧Q V F F F

P ⇒Q V F V V

P ⇔Q V F F V

P YQ F V V F

∼p F F V V

Si P, Q, R son proposiciones, entonces: 1. P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R) (distributividad). 2. P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R) (distributividad).

Observaci´ on Es importante considerar algunas cuestiones acerca de las leyes de distributividad:

Lero y Jose

12

Amaury Camargo B

1.2


1


1. En primer lugar, usando la conmutatividad, uno tiene que,por ejemplo, (P ∨ Q) ∧ R ⇔ R ∧ (P ∨ Q) ⇔ (R ∧ P ) ∨ (R ∧ Q) ⇔ (P ∧ R) ∨ (Q ∧ R) ; de manera que la distributividad funciona “por ambos lados”. 2. Ahora bien, si se tiene una expresi´ on del tipo (P ∧ Q) ∨ (R ∧ S) , se procede como sigue: (P ∧ Q) ∨ (R ∧ S) ⇔ [(P ∧ Q) ∨ R] ∧ [(P ∧ Q) ∨ S] ⇔ [(P ∨ R) ∧ (Q ∨ R)] ∧ [(P ∨ S) ∧ (Q ∨ S)] ⇔ (P ∨ R) ∧ (Q ∨ R) ∧ (P ∨ S) ∧ (Q ∨ S) En otras palabras y seg´ un se indic´ o antes, se trabaja de manera análoga al cálculo elemental (a + b) (c + d) = ac + ad + bc + bd (que se basa en las propiedades an´ alogas para n´ umeros); con la diferencia de que, en este caso, tanto “∧” como “∨” pueden jugar el papel de la multiplicación, a condición de que el otro sea la suma. 3. Repare, sin embargo, en que por ejemplo, en la expresión, (P ∧ Q) ∨ (R ∨ S) , la situaci´ on es distinta: (P ∧ Q) ∨ (R ∨ S) ⇔ [(P ∧ Q) ∨ R] ∨ S ⇔ [(P ∨ R) ∧ (Q ∨ R)] ∨ S ⇔ (P ∨ R ∨ S) ∧ (Q ∨ R ∨ S)

Teorema 1. (Leyes de D’Morgan) Si P, Q, R son proposiciones, entonces: 1. ∼ (P ∧ Q) ⇔∼ P ∨ ∼ Q 2. ∼ (P ∨ Q) ⇔∼ P ∧ ∼ Q Las reglas de conmutatividad, asociatividad, distributividad y de D’Morgan son importantes para trabajar en el ´ algebra de proposiciones que se examina más adelante; pero son bastante sencillas de recordar. (Usamos el nombre leyes de D’Morgan, seg´ un la tradición, pero sólo se trata de un par de teoremas). Observaci´ on La siguiente e importante propiedad nos permite además presentar, en su demostración, cómo funciona el método de derivaci´ on. Si P, Q, R son proposiciones, entonces: Lero y Jose

13

Amaury Camargo B

1.2


1


1. (P ⇒ Q) ⇔ P ∨ Q 2. P ⇒ Q ⇔ P ∧ Q 3. (P ⇒ Q) ⇔ Q ⇒ P (contra-reciprocidad, contraposición). Se tiene: 1. Ya está establecida, se trata de la definición de la implicación. 2. Se tiene sucesivamente P ⇒Q ⇔ P ∨Q

(por definición de la implicación)

⇔ P ∧Q

(por una Ley de D’Morgan)

⇔ P ∧Q

(por doble negación).

3. Se tiene sucesivamente (P ⇒ Q) ⇔ P ∨ Q ⇔ Q∨P

(por definición de la implicación) (por conmutatividad)

⇔ Q∨P ⇔

Q⇒P

(por doble negación)

(por definición de la implicación)

Ejercicios propuestos 1. Verifique que si P, Q y R son proposiciones, entonces: 1. (P ⇔ Q) ⇔ [(P ⇒ Q) ∧ (Q ⇒ P )] 2. (P ⇔ Q) ⇔ (Q ⇔ P ) 3. (P ⇔ Q) ⇔ P ⇔ Q 4. P ⇔ Q ⇔ (P Y Q) Si tiene alguna duda, haga las tablas de verdad correspondientes, salvo para el n´ umero 1, que es la definición de equivalencia. Observaci´ on Note que se declara, también aqu´ı, conmutatividad; si P, Q, R son proposiciones, entonces: 1. P ∨ (P ∧ Q) ⇔ P (absorci´ on). 2. P ∧ (P ∨ Q) ⇔ P (absorci´ on).

Lero y Jose

14

Amaury Camargo B

1.3

´ INFERENCIAS LOGICAS

1


Las reglas de absorci´ on son muy importantes en la práctica. Si usted intenta simplificar una expresi´ on cualquiera y no lo logra, probablemente har´ıa bien en intentar usar una de ellas. (Intente desarrollar, por ejemplo, P ∨ (P ∧ Q) seg´ un la ley de la distributividad y vea lo que ocurre desde el cuarto paso). Si P, Q, R son proposiciones, entonces: 1. (P ∧ Q ⇒ R) ⇔ [P ⇒ (Q ⇒ R)] (exportación) 2. (P ∧ Q ⇒ R) ⇔ [(P ⇒ R) ∨ (Q ⇒ R)] 3. (P ∨ Q ⇒ R) ⇔ [(P ⇒ R) ∧ (Q ⇒ R)] 4. (P ⇒ Q ∧ R) ⇔ [(P ⇒ Q) ∨ (P ⇒ R)] 5. (P ⇒ Q ∨ R) ⇔ [(P ⇒ Q) ∧ (P ⇒ R)] Es interesante hacer todas estas demostraciones mediante derivación. Por ejemplo (P ∧ Q ⇒ R) ⇔ P ∧ Q ∨ R ⇔ P ∨Q ∨R ⇔ P ∨ Q∨R ⇔

P ∨ (Q ⇒ R)

⇔ [P ⇒ (Q ⇒ R)]

1.3.


Una Regla de inferencia es un esquema para construir inferencias validas osea conclusiones validas. Estas reglas permiten establecer relaciones sintácticas entre un conjunto de premisas y una aserci´ on llamada conclusi´ on. Estas relaciones sintácticas son usadas en el proceso de inferencia, por el que se llega a nuevas aserciones verdaderas a partir de otras ya conocidas. Para definir las inferencias l´ ogicas es necesario precisar algunos conceptos tales como razonamiento y demostración. Razonamiento. Es el proceso que se realiza para obtener una demostración. Demostraci´ on. Es el encadenamiento de proposiciones que permiten obtener otra proposición, llamada conclusión, a partir de ciertas proposiciones iniciales supuestas como verdaderas, que reciben el nombre de premisas. Las reglas de inferencia son: Modus Ponendo Ponens (MPP). Es te método establece que si una implicación es cierta y además también lo es su antecedente, entonces su consecuente es necesariamente verdadero; Simbólicamente se expresa as´ı: [(p → q) ∧ p] → q Lero y Jose

15

Amaury Camargo B

1.3


1


Ejemplo 1. premisa1 : Si Juli´ an estudia ingenier´ıa de sistemas a distancia, entonces el estudia en la UNICOR. premisa2 : Si Juli´ an estudia ingenier´ıa de sistemas a distancia. Conclusi´ on : Juli´ an estudia en la UNICOR. Simbólicamente, esta situaci´ on se expresa as´ı: Si p : Julián estudia ingenier´ıa de sistemas a distancia q : El estudia en la UNICOR. Entonces: premisa1 : p → q premisa2 : p Conclusi´ on : q Ejemplo 2. premisa1 : Si x + y = z, entonces y + x = z premisa2 : x + y = z Conclusi´ on y + x = z Simbólicamente, esta situaci´ on se expresa as´ı: Si p:x+y =Z q :y+x=z Entonces: premisa1 : p → q premisa2 : p Conclusi´ on : q

Modus Tollendo Tollens (MTT). Esta regla de inferencia dice que si una implicación es verdadera y su consecuente es falso, entonces su antecedente ser´ a necesariamente falso; Simbólicamente se expresa as´ı: [(p → q)∧ ∼ q] →∼ p Ejemplo 3. premisa1 : Si un ´ angulo de un triangulo es mayor de 90o , entonces la suma de los otros dos ángulos es o menor de 90 premisa2 : La suma de los otros dos ´ angulos no es menor de 90o Conclusi´ on Un ´ angulo de un tri´ angulo no es mayor de 90o

Lero y Jose

16

Amaury Camargo B

1.3


1


Simbólicamente, esta situaci´ on se expresa as´ı: p : Un ángulo de un tri´ angulo es mayor de 90o q : La suma de los otros dos ´ angulos es menor de 90o Entonces: premisa1 : p → q premisa2 : ∼ q Conclusi´ on : ∼ p Ejemplo 4. premisa1 : p ∨ q → r premisa2 : ∼ r Conclusi´ on ∼ (p ∨ q) ↔∼ p∧ ∼ q D’ Morgan Ejemplo 5. Demostrar que la conclusi´ on es consecuencia de las premisas dadas. premisa1 : ∼ b premisa2 : a → b premisa3 : ∼ a → c Demostrar c premisa4 : De la premisa 2 y de la premisa 1, [(a → b)∧ ∼ b] se puede concluir ∼ a por el MTT. premisa5 : De las premisas 3 y 4, [(∼ a → c)∧ ∼ a] se puede concluir la proposición c por el MPP.

Modus Tollendo Ponens (MTP). Esta ley se enuncia as´ı: Si una disyunción es verdadera y una de sus proposiciones simples es falsa, entonces necesariamente la otra proposición será verdadera. Simbólicamente se expresa as´ı: [(p ∨ q)∧ ∼ p] → q o [(p ∨ q)∧ ∼ q] → p Ejemplo 6. premisa1 : O la energ´ıa interna de un ´ atomo puede cambiar con continuidad o cambia sólo a saltos premisa2 : La energ´ıa interna de un ´ atomo no puede cambiar con continuidad Conclusi´ on : La energ´ıa interna de un ´ atomo cambia sólo a saltos Simbólicamente: p : La energ´ıa interna de un ´ atomo puede cambiar con continuidad q : La energ´ıa interna de un ´ atomo s´ olo cambia a saltos premisa1 : p ∨ q premisa2 : ∼ p Conclusi´ on : Q

Lero y Jose

17

Amaury Camargo B

1.3


1


Ejemplo 7. Demostrar que la conclusi´ on es consecuencia de las premisas dadas. premisa1 : ∼ q ∨ s premisa2 : ∼ s premisa3 : ∼ (r ∧ s) → q Demostrar r ∧ s premisa4 : De las premisas 1 y 2 se puede concluir ∼ q por el MTP. premisa5 : De las premisas 3 y 4, ∼ (∼ (r ∧ s)) por MTT, que es equivalente a r ∧ s por la ley de la doble negación

Silogismo Hipot´ etico (SH). Es un argumento que se expresa simb´ olicamente as´ı: [(p → q) ∧ (q → r)] → (p → r)

Ejemplo 8. premisa1 : Si el agua se hiela, entonces sus moléculas forman cristales premisa2 : Si las moléculas forman cristales, entonces el agua aumenta de volumen Conclusi´ on : Si el agua se hiela, entonces el agua aumenta de volumen Simbólicamente: p : El agua se hiela q : Sus moléculas forman cristales r : El agua aumenta de volumen premisa1 : p → q premisa2 : q → r Conclusi´ on : p → r Ejemplo 9. A partir de las premisas dadas indicar la demostración de la conclusión. premisa1 : ∼ r premisa2 : ∼ p → q premisa3 : q Demostrar p premisa4 : De las premisas 2 y 3 se puede concluir ∼ p → r por SH. premisa5 : De las premisas 1 y 4, se concluye p por MTT Use derivación. Por ejemplo: Si P, Q son proposiciones, entonces: Lero y Jose

18

Amaury Camargo B

1.3


1


(P ∨ Q) ∧ P ⇒ Q ⇔ (P ∨ Q) ∧ P ∨ Q i h ⇔ P ∨Q∨P ∨Q ⇔ P ∨Q∨P ∨Q ⇔ P ∨ Q ∨ (P ∨ Q) ⇔ V Note que hemos evitado conscientemente la tentación de pasar de P ∨ Q a P ∧ Q. De todas maneras, tal tentaci´ on no es grave y sólo se traducir´ıa en que la demostración, correcta, resultara un poco m´ as larga y m´ as inocente: (P ∨ Q) ∧ P ⇒ Q ⇔ (P ∨ Q) ∧ P ∨ Q h i ⇔ P ∨Q∨P ∨Q P ∧Q ∨P ⇔ ⇔ P ∧ Q ∨ (P ∨ Q) ⇔ P ∨ Q ∨ (P ∨ Q) ⇔ V ([∗] Para una reflexi´ on posterior: si bien se piensa, el teorema de arriba expresa las maneras en que uno tradicionalmente obtiene conclusiones). Si p, q, r son proposiciones, entonces: 1. [(p ⇒ q) ∧ (p ⇒ r)] ⇒ (p ⇒ r) (transitividad). 2. [(p ⇔ q) ∧ (p ⇔ r)] ⇒ (p ⇔ r) (transitividad). Si p, q, r son proposiciones, entonces: 1. (p ⇔ q) ⇒ (p ∧ r ⇔ q ∧ r) 2. (p ⇔ q) ⇒ (p ∨ r ⇔ q ∨ r) Como se ve, se puede simplificar. Si p, q, r son proposiciones, entonces: 1. p Y q ⇔ (p ⇔ q) 2. (p Y q) ⇔ (p ∨ q) ∧ p ∧ q 3. (p Y q) ⇔ (p ∧ q) ∨ (p ∧ q) 4. p Y V ⇔ p 5. p Y F ⇔ p Lero y Jose

19

Amaury Camargo B

1.3


1


6. (p Y q) ⇔ (q Y p) (conmutatividad) 7. [p Y (p Y r)] ⇔ [(p Y q) Y r] (asociatividad) 8. p ∧ (q Y r) ⇔ [(p ∧ q) Y (p ∧ r)] (distributividad) 9. (p Y q) ⇒ p ∨ q La primera afirmaci´ on es inmediata seg´ un la definición de disyunción excluyente. Suponga que ha demostrado la segunda propiedad mediante una tabla. Entonces, para la tercera, se tiene sucesivamente: (p Y q) ⇔ (p ∨ q) ∧ p ∧ q ⇔ (p ∨ q) ∧ (p ∨ q) ⇔ (p ∧ p) ∨ (p ∧ q) ∨ (q ∧ p) ∨ (q ∧ q) ⇔ F ∨ (p ∧ q) ∨ (q ∧ p) ∨ F ⇔ (p ∧ q) ∨ (q ∧ p)

Como se ve, este teorema indica las propiedades más importantes de la operación “Y”, en particular, las propiedades 2 y 3 permiten manejarla con mayor facilidad. En cualquier caso esta operaci´ on aparece menos que los otros conectivos en la practica matem´ atica corriente.

Ejercicios propuestos 2. 1. Si p es verdadero (1), q es falso (0) y r es verdadero (1), determinar el valor de verdad de cada una de las proposiciones: a) p ⇔∼ [(p ⇒ r) ∧ (q ⇒ r)] b) [(p ∧ q) ∨ r] ⇔ [(p ∨ r) ∧ (q ∨ r)] c) [(p ∧ q) ∧ r] ⇒ [(p ∧ q) ∨ ∼ r] d ) ∼ [(∼ p ∨ q) ∧ ∼ (q∧ ∼ p)] ⇒ [(∼ p ∧ r) ⇒ q] e) (p ∧ q) ⇔∼ [p ∧ (q ⇒ r)] f ) ∼ (p ∧ q) ⇒ (∼ p∨ ∼ q) g) ∼ q ⇒ [p ⇔ (p∨ ∼ q)] h) ∼ [(∼ p∧ ∼ q) ∧ (p ∨ r)] i ) {[(p ∨ q) ⇒ q] ∧ [(p ⇒ r) ⇒ (q ⇒ r)]} j ) [p ⇒ (q ∨ r)] ⇔ [(p ⇒ q) ∨ (p ⇒ r)]

Lero y Jose

20

Amaury Camargo B

1.4

Cuantificadores

1


2. Mediante una tabla de verdad demostrar que: (p ⊕ q) ⇔ [(∼ p ∧ q) ∨ (p∧ ∼ q)] 3. Demostrar, utilizando las leyes del álgebra de proposiciones que: a) (p ⊕ q) ⇔ (p∧ ∼ q) ∨ (∼ p ∧ q) b) ∼ (p ⊕ q) ⇔∼ [(p∧ ∼ q) ∨ (∼ p ∧ q)] c) ∼ (p ⊕ q) ⇔ [(∼ p ∨ q) ∧ (p∨ ∼ q)] 4. Dadas tres proposiciones p, q, r, demostrar utilizando las leyes del álgebra de proposiciones las siguientes equivalencias: a) [(p ∧ q) ∨ (∼ p ∧ r) ∨ (q ∧ r)] ⇔ [(p ∧ q) ∨ (∼ p ∧ r)] b) [(p ∨ q) ∧ (∼ p ∨ r) ∧ (q ∨ r)] ⇔ [(p ∨ q) ∧ (∼ p ∨ r)] c) (∼ p ∧ q ∧ r) ∨ (∼ p∧ ∼ q ∧ r) ∨ (p ∧ q∧ ∼ r) ∨ (p∧ ∼ q∧ ∼ r) ⇔ (∼ p ∧ r) ∨ (p∧ ∼ r) d ) (p ∧ q) ∧ (∼ p ∨ q) ⇔ (∼ p ∧ q) ∨ (p∧ ∼ q) e) (p∨ ∼ q) ∧ (q ∨ r) ∧ (q∨ ∼ r) ⇔ (p ∧ q) f ) (p∨ ∼ q) ∧ (q∨ ∼ r) ∧ (∼ p ∨ r) ∧ (∼ p∨ ∼ q) ⇔∼ p∧ ∼ q∧ ∼ r g) [(p ∨ q) ∧ (∼ p ∨ q)] ⇔ q h) (p∧ ∼ q) ∨ (p ∧ r) ∨ (p ∧ q) ⇔ p i ) (p ∧ q ∧ r) ∨ (∼ p∨ ∼ q∨ ∼ r) ⇔ 1 es una tautolog´ıa

1.4.

Cuantificadores

Vamos a usar los s´ımbolos “∀” y “∃”. Su uso se detalla más abajo. “∀” se lee para todo, para cada, cualquiera sea. “∃” se lee existe al menos un, o hay al menos un, o simplemente existe o hay. Usaremos conjuntos de referencia. Los conjuntos serán estudiados en el siguiente cap´ıtulo, pero lo u ńico que necesitamos saber por ahora es que es caracter´ıstico de los conjuntos tener elementos, salvo en el caso del llamado conjunto vac´ıo. Escribiremos a ∈ U para indicar que el objeto a es un elemento del conjunto U. Anotaremos adem´ as U 6= φ para indicar que U tiene al menos un elemento. Las expresiones: Todo hombre es mortal. Algunos hombres son sabios. pueden traducirse respectivamente como: Para todo x, si x es hombre entonces x es mortal. Lero y Jose

21

Amaury Camargo B

1.4

Cuantificadores

1


Existe un x, tal que x es un hombre y x es sabio. Otros giros utilizados para la expresi´ on “para todo x” son: Todo x, cualquiera x, cada x, que se simbolizan por “∀x” y se llama cuantificador universal. Otros giros utilizados para la expresi´ on “Existe un x” son: Hay x, Existe x, tal que, Alg´ un x, Algunos x, que se simbolizan por “∃x” y se llama cuantificador existencial. Existen tres formas de convertir una función proposicional P x en una proposición, a saber: Haciendo la situaci´ on de las variables por un término espec´ıfico. Anteponiendo la expresi´ on “para todo x” o cuantificador universal. Anteponiendo la expresi´ on “existe al menos un x” o cuantificador existencial.

El enunciado “para todo x, P x” se representa como: (∀x) (P x) . Al anteponer a la funci´ on proposicional P x un cuantificador, se dice que la variable x ha pasado a ser variable ligada. Una proposici´ on de la forma (∀x) (P x) es verdadera cuando todas las sustituciones de la variable x por términos espec´ıficos del conjunto de referencia, convierten a P x en enunciado verdadero. Un enunciado de la forma (∃x) (P x) es verdadero cuando al menos un caso de sustitución de la variable x por un término espec´ıfico del conjunto de referencia, convierte a P x en un enunciado verdadero. Las proposiciones universales pueden aparecer regadas, como en el enunciado: “No todos son mec´ anicos”. En este caso la simbolizaci´ on ser´ a: ∼ (∀x) (M x) donde M x es la función proposicional de “x es mecánico” que toma valores dentro del conjunto de referencia formado por los hombres. Las palabras “ning´ un”, “ninguno”, “nada”, “nadie”, corresponden también a enunciados universales con negaciones, pero de una manera distinta a las proposiciones anteriores. La preposición “ninguno es mecánico” no equivale a la proposici´ on “no todos son mecánicos” sino a la expresión “para todo x, x no es mecánico” que se simboliza (∀x) (∼ M x) . Las proposiciones existenciales pueden estar negadas, como por ejemplo “no es cierto que hay fantasmas” la cual se simboliza como ∼ (∃x) (F x) donde F x simboliza la expresión “x es un fantasma”. Análogamente a lo que ocurre con los cuantificadores universales, las proposiciones existenciales pueden tener negaciones internas como “algo no es mortal” la cual se simboliza como (∃x) (∼ M x) donde M x simboliza la expresi´ on “x es mortal”.

Lero y Jose

22

Amaury Camargo B

1.4

Cuantificadores

1


Observaci´ on As´ı como aclaramos en su momento en el cálculo proposicional, el cálculo cuantificacional presenta también una estructura propia, que adiciona a las reglas ya establecidas para el cálculo se proposiciones,permite la consolidaci´ on del complejo pero maravilloso universo de la lógica formal. Conservando la orientaci´ on que nos hemos propuesto, consideramos importante el conocimiento completo de la estructura b´ asica, y en este sentido presentamos los elementos fundamentales a continuaci´ on: Signos primitivos del c´ alculo cuantificacional: ∀ (cuantificador universal). Regla formativa: Si P designa una f´ ormula; en la cual no figura la expresión (∀x) , entonces (∀x) (P ) designa una fórmula. Signo definido: Si P designa una f´ ormula, en la cual no figura (∀x) , entonces (∃x) (P ) designa la fórmula ∼ (∀x) (∼ P ) .

1. Diremos que una f´ ormula P no est´ a cuantificada bajo el término x, si en P no figura (∀x) o (∃x) . 2. En adelante, cuando una expresi´ on figure cuantificada, se sobre entiende que se satisfacen las condiciones requeridas.

Cuantificadores en una letra Descripci´ on B´ asica Describimos ahora los objetos que estudiaremos. Antes de explicar los cuantificadores, debemos aclarar que ellos no se usan con proposiciones sino con proposiciones m´ as abiertas que se llaman funciones proposicionales. Para tales proposiciones no tiene sentido preguntarse directamente si son verdaderas o falsas, pues contienen uno o más objetos indeterminados, seg´ un iremos detallando. Cuando a una función proposicional se agrega cuantificador(es), se obtiene una proposici´ on. Comenzaremos por aquellas funciones proposicionales que tienen sólo una indeterminación.

Funciones proposicionales en una letra Una función proposicional en la letra x es una expresi´ on formal p (x) tal que se tiene lo siguiente: Cada vez que se remplaza la letra x por un elemento a de un conjunto (previamente) dado U, resulta una proposición p (a) . Observaci´ on La palabra letra tiene aqu´ı un sentido similar al de la palabra variable: una letra debe interpretarse como un espacio en blanco que se puede rellenar con ciertos objetos tomados de un conjunto dado. Usaremos el s´ımbolo“:” para definir funciones proposicionales (como en el ejemplo a continuaci´ on). Si el conjunto U es R y p (x) : 2 + x = 5, (2 + = 5), entonces: Lero y Jose

23

Amaury Camargo B

1.4

Cuantificadores

1


1. p (x) es una funci´ on proposicional. 2. p (3) : 2 + 3 = 5 y p (1) : 2 + 1 = 5 son proposiciones; p (3) es verdadera y p (1) es falsa.

Cuantificador universal Si p (x) es una función proposicional y U es un conjunto, entonces la expresión (∀x ∈ U ) p (x) es una expresi´ on que significa que al reemplazar la letra x por cualquier elemento a de U, resulta p (a) verdadera. La expresión (∀x ∈ U ) p (x) se lee; para todo x en (de) U (se cumple) p de x, cualquiera sea x en U (se cumple) p de x, etc. (Lecturas más informales son recomendadas, ocasionalmente y para entender mejor la proposici´ on. Encontrará algunos ejemplos en la secci´ on de ejercicios). Se tiene: 1. Si U es R y p (x) : 2 + x = 5, entonces (∀x ∈ U ) p (x) es falsa. 2. Si U es R y p (x) : x2 − 1 = (x + 1) (x − 1) , entonces (∀x ∈ U ) p (x) es verdadera. En el lenguaje habitual, corresponde a esta forma de expresiones tales como Todos los fantasmas son hologramas, Cada d´ıa aprendo algo nuevo, Cualquiera puede cantar; Todo hombre es mortal.

Cuantificador existencial Si p (x) es una función proposicional y U es un conjunto, entonces la expresión (∃x ∈ U ) p (x) es una proposici´ on que significa que al menos para un elemento a de U se tiene que p (x) es verdadera. La expresión (∃x ∈ U ) p (x) se lee; existe (al menos un) x (en U ) tal que p de x, hay (al menos un) x (en U ) tal que p de x, y similares. (Lecturas más informales son recomendadas, ocasionalmente y para entender mejor la proposici´ on. Encontrará algunos ejemplos en los ejercicios). Si U es R, p (x) : 2 + x = 5, q (x) : x2 − 1 = (x + 1) (x − 1) , r (x) : x2 − 1, entonces: 1. (∃x ∈ U ) p (x) , (∃x ∈ U ) q (x) son verdaderas. 2. (∃x ∈ U ) r (x) es falsa. En el lenguaje habitual corresponde a esta forma de expresiones tales como Algunos perros muerden, Alguien se comi´ o mi avena.

Lero y Jose

24

Amaury Camargo B

1.4

Cuantificadores

1.4.1.

1


Reglas para el uso

Veremos ahora algunas reglas fundamentales para el uso de los cuantificadores. Estas reglas son convencionales, pero es oportuno tener presente que ellas recogen el sentido que com´ unmente se da a las expresiones an´ alogas en idioma espa˜ nol, otorgándoles, claro está, una precisión mayor. Podemos darnos ejemplos de variada ´ındole para confirmar la impresión de que estas reglas son bastante razonables Lo anterior no obstante, es necesario tener presente que no bastar´ıa con coleccionar una multiplicidad de ejemplos para probar las reglas; ellas son, en definitiva, sólo convenciones, acuerdos expl´ıcitos; (una de nuestras reglas ser´ a una consecuencia de las otras). Por otra parte, si se nos presenta alg´ un ejemplo en el que una de estas reglas resulte poco razonable, entonces probablemente har´ıamos bien en abandonarla. As´ı, a´ un cuando no daremos justificaci´ on de las reglas (del mismo modo que no es necesario justificar las reglas de un juego como el ajedrez o uno de naipes), mencionaremos expresamente algunas expresiones que no ser´ıa conveniente aceptar como reglas. A continuación de cada reglas que presentaremos haremos un comentario de longitud variable. Para una referencia m´ as expedita, hemos reunido las reglas en un cuadro al final de este cap´ıtulo. Observaci´ on No somos capaces de enfatizar en modo suficiente cuán importante son las reglas 2 y 3 y la regla 8 (que es, en realidad, un teorema). Las otras, por el contrario, no serán usadas con frecuencia por ahora y puede leerlas con detenci´ on, comprenderlas y volver posteriormente sobre ellas. En toda esta secci´ on, U es un conjunto de referencia; p (x) , q (x) son funciones proposicionales, anotaremos (∀x) p (x) para expresar (∀x ∈ U ) p (x) y (∃x) p (x) para expresar (∃x ∈ U ) p (x) .

Regla 1 R1 : (∀x) p (x) ⇒ (∃x) p (x)

(U 6= φ)

Como se ve es bastante razonable. Hemos a˜ nadido que el conjunto U tenga al menos un elemento (en caso contrario y seg´ un puede comprobar posteriormente, de preferencia cuando haya visto conjuntos, se tiene que (∀x) p (x) es verdadera y que (∃x) p (x) es falsa).

Lero y Jose

25

Amaury Camargo B

1.4

Cuantificadores

1


Regla 2 R2 :(∀x) p (x) ⇔ (∃x) p (x) Esta es una regla en extremo importante, no sólo para este cap´ıtulo sino para cualquier trabajo en Matemáticas. Es una verdadera calamidad que haya al respecto un malentendido generalizado del alumnado con consecuencias diarias y catastróficas. La regla indica claramente que para la expresión (∀x) p (x) sea verdadera, no debe haber excepci´ on alguna, pues tal excepci´ on la invalidar´ıa, al hacer verdadera su negación. La regla puede expresarse diciendo que la falsedad de la expresión (∀x) p (x) se demuestra con un contra-ejemplo: un elemento x de U para el cual p (x) es falsa, (es decir, para el cual p (x) es verdadera. Lo que afirma esta regla es que cuando decimos siempre queremos decir siempre (y no casi siempre, o la mayor´ıa de las veces, o no se tiene noticia de que sea falsa, etc. ), cuando decimos todo queremos decir todo (y no casi todo, el 99, 99 % de las veces, parece que todo, para que nos vamos a hacer problema, etc.). Si se tratara de probar que la afirmaci´ on No es cierto que todos los osos son blancos es verdadera, bastar´ıa con exhibir un oso que no sea blanco. La afirmación Todo n´ umero real tiene un inverso multiplicativo tiene una (´ unica) excepción, y es por lo tanto, irredimible y decididamente falsa. [∗](Vea este ejemplo, m´ as sutil, m´ as adelante). Suponga que un hombre de 60 a˜ nos decide escribir sus memorias,. No tiene experiencia ni aprende, de modo que demora un a˜ no en escribir un a˜ no de su vida; (las memorias cada vez m´ as aburridas). Suponga que ese hombre no muere, ¿escribirá todas sus memorias? (Si se quiere probar que no, hay que encontrar alguna, en alg´ un a˜ no, que no logra relatar. −−Aqu´ı nos interesa s´ olo la l´ ogica del problema y no las eventuales dificultades prácticas−−). Observaci´ on Traducida al espa˜ nol, la expresi´ on (∀x) p (x) puede leerse “no siempre se tiene p(x)”, tal afirmaci´ on es distinta de (∀x) p (x), que puede leerse “nunca se tiene p(x)”. A´ un cuando es evidente que ambas expresiones afirman cuestiones distintas, en el uso diario no suele marcarse la diferencia. La frase No todo lo que brilla es oro corresponde a una expresión del tipo (∀x) p (x). Por otra parte, la expresi´ on ”Todo lo que brilla no es oro afirma que nada que brille es oro y su estructura es (∀x) p (x). Compare lo anterior con las frases No todo oso es blanco (verdadera) y Ning´ un osos es blanco (falsa). Lo que estos u ´ltimos ejemplos muestran es que no sólo podemos ser imprecisos en el lenguaje, sino que incluso podemos habernos “contaminado” de un modo de pensar inapropiado.

Lero y Jose

26

Amaury Camargo B

1.4

Cuantificadores

1


Regla 3 R3 :(∃x) p (x) ⇔ (∀x) p (x) Esta regla declara c´ omo se prueba que alguna propiedad no es cierta, nunca, jamás. Ella pone de manifiesto lo dif´ıcil que puede resultar la demostración de ciertas proposiciones. Considere al respecto, las frases Es imposible sacarse el chaleco sin sacarse la chaqueta, No existen los platillos voladores; No hay mal que dure cien a˜ nos. En genera, uno podr´ıa pensar que una proposición del tipo (∃x) p (x) no es fácil de probar; tal demostración deber´ıa convencer que ning´ un objeto que a alguien se le pudiere ocurrir cumplirá p (x) (y a´ un ello no ser´ıa suficiente). En otras palabras, la reglas indica que tan dif´ıcil puede ser probar que algo no puede ocurrir; en este sentido, cuando aqu´ı decimos nunca, queremos decir nunca (y no parece que nunca, no se ha tenido noticia de que, en realidad no creo, todos piensan que no, etc.).

Regla 4 R4 : (∀x) [p (x) ∧ q (x)] ⇔ (∀x) p (x) ∧ (∀x) q (x) Esta regla se suele expresar diciendo ∀ distribuye en ∧. Se trata de una regla que podemos proceder a olvidar −− es decir, usarla sin prestarle mayor atenci´ on−− . Aqu´ı estamos s´ olo declarando que no hay que preocuparse de este asunto, que se puede usar la regla con toda tranquilidad.

Regla 5 R5 : (∃x) [p (x) ∨ q (x)] ⇔ (∃x) p (x) ∨ (∃x) q (x) Esta regla se suele expresar diciendo que ∃ distribuye en ∨. Vale para ella lo comentado para la regla anterior.

Regla 6 R6 : (∀x) p (x) ∨ (∀x) q (x) ⇒ (∀x) [p (x) ∨ q (x)] Por oposición a las dos anteriores, esta regla no es una equivalencia, sino sólo una implicación.

Lero y Jose

27

Amaury Camargo B

1.4

Cuantificadores

1


De hecho, ser´ıa razonable ponerla como equivalencia, pues entonces deber´ıa ser siempre cierto que (∀x) [p (x) ∨ q (x)] ⇒ (∀x) p (x) ∨ (∀x) q (x) , lo que definitivamente no ser´ıa de esperar si encontramos en que el antecedente sea vertedero y el consecuente falso (y por lo tanto, la implicación también sea falsa). Para tal efecto compruebe que en Z : la afirmación Todo n´ umero es par o impar es verdadera, pero Todo n´ umero es par o bien todo n´ umero es impar es falsa, (pues ninguna de sus componentes es verdadera).

Regla 7 R7 : (∃x) [p (x) ∧ q (x)] ⇒ (∃x) p (x) ∧ (∃x) q (x) Con respecto a esta regla, la situaci´ on es análoga a la de la anterior, si bien aqu´ı la implicaci´ on esta “en la otra direcci´ on”. Si se asumiera que se tiene una equivalencia, se tendr´ıa entonces que (∃x) p (x) ∧ q (x) ⇒ (∃x) [p (x) ∧ (∃x) q (x)] ser´ıa siempre verdadera. Podemos construir un caso en que esta u ´ltima afirmación resulta falsa con las mismas proposiciones y conjunto que usamos para la regla anterior. Las proposiciones, Existe un n´ umero par y Existe un n´ umero impar, son ambas verdaderas, pero Existe un n´ umero que es par e impar (a la vez), es falsa.

Regla 8 h i R8 :(∀x) [p (x) ⇒ q (x)] ⇔ (∃x) p (x) ∧ q (x) Se tiene sucesivamente (∀x) [p (x) ⇒ q (x)] ⇔ (∃x) [p (x) ∧ q (x)] h i ⇔ (∃x) p (x) ∨ q (x) h i h i ⇔ (∃x) p (x) ∧ q (x) ⇔ (∃x) p (x) ∧ q (x)

1.4.2.

Cuantificadores con varias variables

Descripci´ on B´ asica En realidad se trata aqu´ı de los mismos cuantificadores que en la primera parte, pero ahora referidos a funciones proposicionales en m´ as de una letra. Si en una expresi´ on aparece m´ as de una variable libre, podemos usar más de un cuantificador. Lero y Jose

28

Amaury Camargo B

1.4

Cuantificadores

1


En la expresión y = x2 + 2x hay dos variables libres. Ahora si consideramos (∀y) (∃y) y − x2 + 2x = 0 es una afirmaci´ on verdadera, pues para cualquier x que se tome (real) puedo encontrar un y que satisface la ecuación. Sin embargo, dicha afirmaci´ on no es lo mismo que (∃y) (∀y) y − x2 + 2x = 0 que dice que existe un y que sirve para todo x que yo tome, claramente la afirmación es falsa. La conclusión del ejemplo anterior: El orden de los cuantificadores s´ı importa y es un error muy com´ un cambiar su orden. Cuando hay dos cuantificadores aparecen 8 combinaciones. Algunas combinaciones son equivalentes pero otras no. Lo vemos en el cuadro siguiente. Sea P (xc y) una expresión con dos variables libres. (∀x) (∀y) P ⇓ (∃x) (∀y) P ⇓ (∀y) (∃x) P ⇓ (∃y) (∃x) P

(xc y)

⇔

(xc y) (xc y) (xc y)

⇔

(∀y) (∀x) P ⇓ (∃y) (∀x) P ⇓ (∀x) (∃y) P ⇓ (∃x) (∃y) P

(xc y) (xc y) (xc y) (xc y)

Considere la tabla anterior con lo siguiente: Posibles valores de x son todos las personas, posibles valores de y son todas las frutas, P (xc y) : a la persona x le gusta la fruta y Nótese que si hubiera m´ as variables habr´ıa muchos más casos. Cuántos casos hay si se tienen 3 variables?. Observaci´ on: Es interesante mirar la cuesti´ on de proposiciones y funciones proposicionales en conjunto. Lo hacemos a través de un ejemplo simple y un tanto repetido, pero tomará sólo un par de minutos: Si fijamos, por ejemplo R como conjunto (´ unico) de referencia, tenemos que: 1. p : 2 + 3 = 5, q : 2 + 3 = 6 son proposiciones, y 1. p es verdadera, 2. q es falsa. 2. p (x) : x + 3 = 5 es una funci´ on proposicional en una letra y 1. p (x) no es verdadera ni falsa, 2. (∀x) p (x) es falsa, (tomar x = 5, por ejemplo, 3. (∃x) p (x) es verdadera, (tomar x = 2). 3. p (x, y) : x + y = 5 es una funci´ on proposicional en dos letras y 1. 2. 3. 4. 5.

p (x, y) no es verdadera ni falsa (no es una proposición), (∀x) (∀y) p (x, y) es una proposici´ on falsa, (∃x) (∀y) p (x, y) es una proposici´ on falsa, (∀x) (∃y) p (x, y) es verdadera (dado x = a, tomar y = 5 − a), (∃x) (∃y) p (x, y) es verdadera (tomar, por ejemplo o al azar, x = 2 y luego y = 3)

Lero y Jose

29

Amaury Camargo B

1.4

Cuantificadores

1


4. p (x, y, z) : x + y = z es una funci´ on proposicional en tres letras.

1.4.3.

Negando proposiciones con Cuantificadores

Neguemos ”Todo alumno en este sal´ on tiene cabello negro”. Para ello basta decir ”Existe un alumno en este salón que no tiene cabello negro”. Esta es la clave: ∼ (∀x) P (x) ⇔ (∃x) (∼ P (x)) . Obsérvese que para negar el primer ejemplo, no es necesario decir que todo alumno en este sal´ on no tiene el cabello negro, que simb´ olicamente ser´ıa (∀x) (∼ P (x)) . Es decir (∀x) (∼ P (x)) no es lo mismo que (∃x) (∼ P (x)) . Similarmente, negar que ”Existe un alumno con cabello morado” es equivalente a decir que ”Todos los alumnos no tienen el cabello morado”. La clave es ∼ (∃x) P (x) ⇔ (∀x) (∼ P (x)) . Y no estar´ıa bien negado decir que ”Existe un alumno que no tiene el cabello morado”.

1.4.4.

Negando proposiciones con m´ as de un cuantificador

Neguemos la afirmaci´ on [(∀x) (∃x) P (xc y)] . Hagámoslo por pasos: ∼ (∀x) (∃x) P (xc y) ⇔ (∃x) (∼ (∃y) P (xc y)) ⇔ (∃x) (∀y) (∼ P (xc y)) . Conclusi´ on: Para negar proposiciones que involucran cuantificadores, estos se cambian entre s´ı, sin cambiar las variables y la expresi´ on final se niega as´ı: ∼ (∀y) (∃w) (∀x) (∀m) y + w2 + x = m ⇔ (∃y) (∀w) (∃x) (∃m) y + w2 − x 6= m . Por supuesto, si escribimos p (x, y) , x puede tomar valores en un conjunto U, e y (tal vez) en otro conjunto V . Ilustraremos la situaci´ on anterior: 1. p (x, y) : x ≤ y es una funci´ on proposicional en dos letras que pueden tomar valores en R. 2. q (x, y, z) : x + y = z es una funci´ on proposicional de tres letras que pueden tomar valores en R. (Es claro que, aqu´ı, si x e y toman valores en R, entonces z no será, por ejemplo, un triángulo). 3. Informalmente, r (x, y) : x pasa por y es una función proposicional en dos letras, donde x toma valores en un conjunto de rectas, e y toma valores en un conjunto de puntos (del plano habitual, si se quiere).

Ejercicios propuestos 3. Lero y Jose

30

Amaury Camargo B

1.4

Cuantificadores

1.4.5.

1


Reglas para el uso

Procederemos como hicimos para los cuantificadores en una letra: iremos enunciando y comentando sucesivamente nuestras reglas, que persistimos, en llamar axiomas. Asumimos un conjunto de referencia U para la letra x y un conjunto V para la letra y, (lo que también puede expresarse diciendo que el par (x, y) toma valores en el conjunto U × V ). Convenimos que (∀x) (∀y) p (x, y) significa (∀x ∈ U ) (∀y ∈ V ) p (x, y) (∃x) (∀y) p (x, y) significa (∃x ∈ U ) (∀y ∈ V ) p (x, y) , etc.

Regla 9 R9 : (∀x) (∀y) p (x, y) ⇔ (∀x) (∀y) p (x, y) Esta regla indica que si hay dos cuantificadores universales seguidos, no importa el orden en el que se escriban. Tome nota de esto −−y no se haga problemas cuando le aparezca una expresión similar− − . Eso es todo.

Regla 10 R10 : (∃x) (∃y) p (x, y) ⇔ (∃x) (∃y) p (x, y) Para esta regla vale el mismo comentario que para la anterior.

Regla 11 R11 : (∀x) (∀y) p (x, y) ⇔ (∃x) (∀y) p (x, y) ;

(U 6= φ)

(Podr´ıa considerarse que esta regla es una especie de consecuencia natural de la regla 1). (Por supuesto, podr´ıamos haber escrito (∀x) (∀y) p (x, y) ⇔ (∃x) (∀y) p (x, y) , pero hemos preferido la otra forma para que la lista completa sea le´ıda con mayor facilidad, seg´ un comprobará en el resumen final).

Ejercicios propuestos 4. 1. Simbolizar los siguientes enunciados: a) Todo es perecedero. Lero y Jose

31

Amaury Camargo B

1.4

Cuantificadores

1


b) Hay marcianos. c) Alguien no es perfecto. d ) No hay cosas s´ olidas. e) Si todo es rojo, hay algo rojo. f ) Nada se mueve. g) No todo es perfecto. h) Nada es perecedero. 2. Indicar, con base en las reglas formativas establecidas en el cálculo de proposiciones y la u ´ltima regla anotada para el c´ alculo de cuantificadores, cuáles de las siguientes expresiones son fórmulas: a) (x = y) ⇒ ((∀x) (− (x = y))) b) (∀x) (x ∈ A ⇒ x ∈ B) c) (∀x) (x ∈ A) ∨ (∀x) (x ∈ B) d ) (∀x) (x ∈ A ∨ (∀x) (x ∈ B)) e) (∀x) ((x = z) ∧ (∀y) (y ∈ B)) f ) (∀x) (∀y) ((u = y) ⇒ (y = x)) g) (∀x) ((∀y) (z ∈ U )) 3. Sean: a) P x : (x ∈ A) ⇒ (x ∈ A ∨ x ∈ B) b) Qx : (x = t ∧ x ∈ B) ⇒ (t ∈ B) c) Sx : − ((x ∈ A ∧ y ∈ A) ⇒ (x = y))

Lero y Jose

32

Amaury Camargo B

2

2.

´ SISTEMAS DE NUMERACION

Sistemas de numeraci´ on

Objetivos: Al finalizar este cap´ıtulo el lector deberá comprender la necesidad de los diferentes códigos usados en lo sistemas digitales, y será capaz de expresar cualquier cantidad en los diferentes códigos (binario, decimal, hexadecimal, BCD, BCD8421 y Gray). Además efectuará aritméticas en el sistema binario y en el BCD8421 y podr´ a pasar de un código a otro con facilidad.

2.1.

Concepto de codificaci´ on

Un código no es m´ as que una manera l´ ogica de representar cantidades, mediante la asociación de un s´ımbolo a cada cantidad. Estos s´ımbolos en general son los n´ umeros naturales del 0 al 9 aunque también se utilizan las letras del alfabeto y otros s´ımbolos de uso general. Normalmente a los códigos se les denomina sistema de numeración, siendo los m´ as usados: Sistema de numeraci´ on decimal, el cual posee diez s´ımbolos, los n´ umeros del 0 al 9. Código binario, usa los s´ımbolos 0 y 1. Código octal, representado por los n´ umeros del 0 al 7. Código hexadecimal, usa dieciséis s´ımbolos: los n´ umeros del 0 al 9 y las letras A, B, C, D, E y F . Código especial BCD. Código especial Gray.

2.2.

Sistema de numeraci´ on decimal

Un sistema de numeraci´ on esta caracterizado por su base, b. As´ı en general, una cantidad cualquiera, representada por el n´ umero N, puede ser representada en la forma de la ecuación 1,1 N =ai bi Donde los ai son los s´ımbolos que caracterizan al sistema y b es la base. En otras palabras cualquier n´ umero N, puede ser expresado como un polinomio de potencias en la base b, cuyos coeficientes son s´ımbolos del sistema de numeración y pueden tomar un valor desde 0 hasta b − 1. Por ello si b = 10, tendremos los s´ımbolos de 0 a 10 − 1 = 9: y diremos que estamos en presencia del sistema decimal cuya base es el n´ umero 10. Sea el n´ umero 7419 7419 = 7∗ 103 + 4∗ 102 + 1∗ 101 + 9∗ + 100 Los s´ımbolos 7, 4, 1 y 9 son los coeficientes. Los valores posicionaleso pesos están representados por las potencias de 10. En el caso del n´ umero fraccionario se utilizan potencias negativas de la base 10, como puede verse en el siguiente ejemplo. Ejemplo 10. 435, 232 = 4∗ 102 + 3∗ 101 + 5∗ 100 + 2∗ 10−1 + 3∗ 10−2 + 2∗ 10−3 . Lero y Jose

33

Amaury Camargo B

2.3

Sistema de numeraci´ on binaria

2.3.

2


Sistema de numeraci´ on binaria

En este caso b = 2 y por lo tanto, el sistema binario tiene dos s´ımbolos (0 y 1), los cuales son conocidos como bits (del inglés Binary digits). Al igual que en el sistema decimal todo n´ umero puede representarse usando la notaci´ on posicional en potencias de la base b = 2, y su desarrollo nos equivale al decimal. Sea el n´ umero N = (110101)2 , donde el sub´ındice 2 indica la base, entonces: N

= 1∗ 25 + 1∗ 24 + 1∗ 23 + 1∗ 22 + 1∗ 21 + 1∗ 20

N

= 32 + 16 + 4 + 1

N

= 53

(110101)2 = (53)10 Para los n´ umeros fraccionarios se usan las potencias negativas de base (b = 2). Sea N = (0,1101)2 , entonces: N

= 0∗ 20 + 0∗ 2−1 + 0∗ 2−2 + 0∗ 2−3 + 0∗ 2−4

N

= 0,5 + 0,25 + 0,0625

N

= (0,8125)10

(0,1101)2 = (0,8125)10 2.3.1.

Conteo en binario

El sistema binario es el m´ as usado en sistemas digitales, ya que el hecho de tener dos s´ımbolos nos permite asociar a cada s´ımbolo con dos estados los cuales pueden ser prendido y apagado, positivo y negativo, mayor qué y menor qué, perforado y tapado; dando esta propiedad una gran versatilidad en el dise˜ no con dispositivos electr´ onicos sencillos. El hecho de tener dos s´ımbolos no implica que no podamos contar n´ umeros grandes, para ello tenemos en cuenta que si queremos contar n objetos necesitamos un n´ umero de bits, K, tal que 2K > n o sea que si queremos expresar o contar los n´ umeros decimales del 0 al 9, necesitaremos: 2K > 10, donde K es un entero superior a 4 Con 4 bits formamos los n´ umeros del 0 al 9 de acuerdo ala tabla 1,1 Decimal 0 1 2 3 4 5 6 7 8 9 Lero y Jose

34

Binario 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 Amaury Camargo B

2.4

Sistema de numeraci´ on octal

2


Si queremos contar debemos recordar que el sistema decimal llega hasta el 9, colocamos un 1 delante y continuamos hasta llegar al 19, y as´ı sucesivamente. En binario lo mismo; comenzamos 0, 1; agregamos un 1 delante...10, 11; agregamos otro 1 delante...100 101 110 111 y as´ı sucesivamente. Una manera de contar es pensar en decimal y eliminar todos los n´ umeros que tengan d´ıgitos decimales distintos de 0 y 1, y esto es extensible a cualquier sistema. 1. Sistema binario. 0, 1, 2, 3, 4, 5, 6, ..., 10, 11, 12, 13, 14, ..., 100, 101, 102, ... 2. Sistema de base tres (S´ımbolos 0 1 2) 0, 1, 2, 3, 4, 5, 6, ..., 10, 11, 12, 13, 14, ..., 20, 21, 22, ...

2.4.

Sistema de numeraci´ on octal

El sistema de octal tiene base, b = 8, y por lo tanto utiliza ocho s´ımbolos, que son los d´ıgitos del 0 al 7, para denotar las cantidades numéricas. Igual que el sistema binario, todo n´ umero octal puede representarse usando sus valores posici´ onales y expresarse en potencias de base ocho. Sea N = (373,043)8 . Entonces: N

= 3∗ 82 + 7∗ 81 + 3∗ 80 + 0∗ 8−1 + 4∗ 8−2 + 3∗ 8−3

N

= 192 + 56 + 3 + 0,0156 + 0,005859...

N

= (251,021459...)10

Observe que no necesariamente el valor es exacto. Para contar en octal, seguimos la misma técnica de la sección anterior: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 20...

2.5.

Sistema de numeraci´ on hexadecimal

Este sistema tiene como base el n´ umero decimal 16 y por lo tanto, posee dieciséis s´ımbolos: los n´ umeros del 0 al 9 y los literales A, B, C, D, E,F, representando estos u ´ltimos los s´ımbolos del 10 al 15. Sea N = (E5D7.A3)16

Lero y Jose

N

= E ∗ 163 + 5∗ 162 + D∗ 161 + 7∗ 160 + A∗ 16−1 + 3∗ 16−2

N

= 14∗ 163 + 5∗ 162 + 13∗ 161 + 7∗ 160 + 10∗ 16−1 + 3∗ 16−2

N

= (72839,63671878)10

35

Amaury Camargo B

2.6

Conversi´ on entre sistemas de numeración

2


La tabla 1,2 muestra un resumen de los cuatro sistemas de numeración que utilizaremos, y en pr´ oxima sección se explicar´ a como pasar de uno a otro. SISTEMA DECIMAL BINARIO OCTAL HEXADECIMAL

2.6.

BASE 10 2 8

S´ IMBOLOS 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 0, 1, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

Conversi´ on entre sistemas de numeraci´ on

Como lo representamos en la ecuaci´ on 1,1, cualquier n´ umero N puede ser representado como: N

= an bn + an−1 bn−1 + · · · + a0 + a−1 b−1 + · · · + a−m b−m

N

= Ne + Nf

Ec. 1,2

Donde Ne es la parte entera y Nf es la parte fraccionaria. Si tomamos Ne y lo dividimos por b N e = an bn + an−1 bn−1 + · · · + a0 Ne a0 = an bn−1 + an−1 bn−2 + · · · + b b 1 Ne = (cociente 1) + residuo b b

Ec. 1,5 Ec. 1,6

La ecuación 1,5, expresada literalmente en 1,6 nos dice que el primer residuo es a0 . Si tomamos ahora el cociente 1 y lo dividimos por b, obtenemos un cociente 2 y el nuevo residuo ser´ a a1 y as´ı consecutivamente. En el caso de Nf se har´ a lo mismo pero multiplicando por b en cada caso.

2.6.1.

Conversi´ on decimal a binario

Siguiendo el esquema de la secci´ on precedente, dividiremos consecutivamente por dos la parte entera y multiplicaremos por dos la parte fraccionaria.

Lero y Jose

36

Amaury Camargo B

2.6


2


Convertir (653)10 a binario. a0

653 1 a1

2 326 0 a2

2 163 1 a3

2 81 1 a4

2 40 0 a5

2 20 0 a6

2 10 0 a7

2 5 1 a8

2 2 0 a9

2 1 1

2 0

65310 = 10100011012 Observe que los residuos se colocan en orden inverso. Evidentemente para ir de binario a decimal, usamos el desarrollo de los valores posiciones. Convierta (653,61)10 a binario. En este caso dado que un n´ umero con parte entera y fraccionaria, se convierte primero la parte entera, ya realizado en el ejemplo anterior y luego la parte fraccionaria usando la técnica de multiplicar sucesivamente por dos.

(653,61)10

0,61∗ 2 = 1,22 a−1 ∗ 0,22 2 = 0,44 a−2 0,44∗ 2 = 0,88 a−3 0,88∗ 2 = 1,76 a−3 ∗ 0,76 2 = 1,52 a−4 0,52∗ 2 = 1,04 a−5 = (1010001101,10011...)2

=1 =0 =0 =1 =1 =1

Para comprobarlo utilizaremos el desarrollo de potencias en base a dos (0,100111...)2 = 1∗ 2−1 + 1∗ 2−4 + 1∗ 2−5 + 1∗ 2−6 = 0,5 + 0,625 + 0,03125 + 0,015625 = (0,609375)10 Observe que el resultado no es exacto porque detuvimos el proceso en a−6 ; si calculamos más fracciones binarias nos acercamos al resultado.

2.6.2.

Conversi´ on del sistema decimal al octal

Esta conversión se realiza de manera similar a la de decimal a binario, con la excepción de que en este caso la división consecutiva se hace por ocho, en lugar de 2. Lero y Jose

37

Amaury Camargo B

2.6


2


Supongamos que queremos convertir (653)10 a octal 653 5 a1

a0

8 81 1 a2

8 10 2 a3

8 1 1

8 0

(653)10 = (1215)8 Recuerde que la escogencia de los d´ıgitos se hace del u ´ltimo residuo al primero, tal como lo indica la flecha en el ejemplo anterior. Si queremos ir de octal a decimal, solo tenemos que aplicar el desarrollo de potencias de ocho, de acuerdo a los valores posici´ onales. Si tenemos (1215)8 (1215)8 = 1∗ 83 + 2∗ 82 + 1∗ 81 + 1∗ 80 = 512 + 128 + 8 + 5 = 653 Si el valor decimal es fraccionario se multiplica sucesivamente por ocho, pasando la parte entera de los resultados consecutivos a formar parte de la parte fraccionaria del n´ umero octal. Esta operaci´ on se contin´ ua hasta obtener una fracci´ on nula o hasta la precisión deseada, si lo anterior no se consigue. Sea (0,46875)10 a octal 0,46875∗ 8 = 3,75 ∗

0,75 8 = 6,00

a−1 = 3 a−2 = 6

(0,46875)10 = (0,36)8 Por supuesto, el ejemplo anterior es una muestra del primer caso, o sea la fracción octal es exacta. Sea (0,136)10 a octal 0,136∗ 8 = 1,088

a−1 = 1

∗

a−2 = 1

∗

a−3 = 5

∗

a−4 = 5

0,088 8 = 1,704 0,704 8 = 5,632 0,632 8 = 5,056

Si nos detenemos aqu´ı: (0,136)10 = (0,1155)8 , pero si desarrollamos (0,1155)8 , obtenemos: 1∗ 8−1 + 1∗ 8−2 + 5∗ 8−3 + 5∗ 8−4 = (0,1359875)10 La cual, salvo por un error menor de una diezmilésima coincide con el n´ umero original. Si tenemos un n´ umero de parte entera y parte fraccionaria hacemos la conversión por separado y luego combinamos ambos resultados.

Lero y Jose

38

Amaury Camargo B

2.6


2


Convertir (124,78125)10 a octal 124 4 a1

a0

8 15 7 a2

8 1 1

8 0

Parte fraccionaria 0,78125∗ 8 = 6,25

a−1 = 6

∗

0,25 8 = 2,00

a−2 = 2

(124,78125)10 = (174,62)8 2.6.3.

Conversi´ on entre los sistemas binario y octal

Como estudiaremos posteriormente, los circuitos digitales manipulan datos usando el sistema de numeración binario; sin embargo, esto trae el inconveniente de que a medida que aumenta el tama˜ no del n´ umero, aumenta también la cantidad de bits, y consecuentemente se complica el manejo de datos. Para simplificar esto se introdujeron los sistemas octal y hexadecimal que tienen una gran ventaja por la caracter´ıstica de que sus bases son potencias de dos. En el caso del sistema octal: N =i ai 8i Ec. 1,2 Y binario: N=

X

Ai 2 i

Ec. 1,2

i

Donde ai = [0, 1, 2, 3, 4, 5, 6, 7] Ai = [0, 1] Ahora bien, cualquiera de los ai puede ser expresado como combinación de tres d´ıgitos binarios o bits. De tal manera que si tomamos el n´ umero binario y lo separamos de tres en tres, partiendo del punto decimal a la izquierda para la parte entera, y al derecha para la parte fraccionaria, podemos sustituir cada uno de los grupos por su correspondiente valor octal, reflejado en la tabla siguiente y viceversa. Octal 0 1 2 3 4 5 6 7

⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔

Binario 000 001 010 011 100 101 110 111

Convertir (10010101,1011)2 a octal. Separamos en grupos de tres: 010 Lero y Jose

010

101. 101 39

100 Amaury Camargo B

2.6


2


Los ceros al principio (M SB) y al final (LSB) se agregan para completar grupos de tres (225,54)8 Para ir de octal a binario, simplemente se sustituye cada d´ıgito octal por su equivalente binario de acuerdo a la tabla anterior. Convertir (1752,714)8 a binario (1752,714)8 = (001

111

101

010.

111

001)2

Eliminando los ceros como bits m´ as significativos (M SB) o menos significativos (LSB). (1752,714)8 = (111101010,111001)2 Es importante hacer notar que si se quiere pasar de decimal a binario se puede pasar primero a octal y después utilizar este método, con lo cual se ahorra en las divisiones.

2.6.4.

Conversi´ on del sistema decimal a hexadecimal

Siguiendo los mismos procedimientos anteriores, corresponde dividir y/o multiplicar por 16. Convertir (47632)10 a hexadecimal 47632 156 123 112

(47632)10

16 2977 137 97

16 186 26

16 11

16 0

0←−−−1−−−−10 11 −−−−− − = (BA10)16

Recuerde que A = 10, B = 11, ..., F = 15 en hexadecimal. Convertir (124,136)10 a hexadecimal 124 16 12 7 16 7 0 Parte fraccionaria 0,136∗ 16 = 2,176

a−1 = 2

∗

a−2 = 2

∗

a−3 = D

∗

a−4 = 0

∗

a−5 = E

0,176 16 = 2,816 0,816 16 = 13,056 0,056 16 = 0,896 0,896 16 = 14,336 (124,136)10 = (7C,22D0E)16

Lero y Jose

40

Amaury Camargo B

2.7

Operaciones aritméticas en el sistema binario

2.6.5.

2


Conversi´ on entre los sistemas hexadecimales y binario

Como se anotó en entre los sistemas binario y octal), se puede aplicar la propiedad de que la base 16 es una potencia de la base binaria y todo s´ımbolo de la base hexadecimal puede ser expresado por cuatro d´ıgitos binario o bits, de acuerdo a la tabla siguiente la cual puede usarse para convertir de una a otro sistema separando en grupos de cuatro bits el n´ umero representado en binario o viceversa. Hexadecimal 0 1 2 3 4 5 6 7 8 9 A B C D E F

Binario 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Convertir 10101101101,0101101101 a hexadecimal 0101 0110 1101,0101 1011 0100 (56D,5B4)16 Observe que de nuevo se agregaron ceros al M SB y al LSB. Para convertir de hexadecimal a binario, se emplea el mismo método, sustituyendo cada d´ıgito hexadecimal por su equivalente binario de 4 bits aparece en la tabla anterior. Convertir (8F ,41)16 a binario 1000 1111,0100 0001 (8F ,41)16 = (1000111,01000001)2

2.7.

Operaciones aritm´ eticas en el sistema binario

Es evidente que el lector conoce las cuatro operaciones fundamentales de la aritmética (suma, resta, multiplicación, divisi´ on) en el sistema de numeración decimal, pero dado que en sistemas digitales utilizamos otros sistemas de numeraci´ on; es importante, entonces familiarizarse con dichas operaciones en el sistema binario, teniendo siempre en mente la aritmética decimal como gu´ıa.

Lero y Jose

41

Amaury Camargo B

2.7


2.7.1.

2


Suma binaria

Para sumar en binario, debemos primero construir una tabla de sumar como se observa en la siguiente, la cual se denomina Tabla de Verdad del sumador completo, todo lo cual será analizado en secciones posteriores. Sumandos Resultado Acarreo A B S C 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 Sumar en binario 1101 + 1101 Acarreo Sumando A Sumando B Resultado

1101 1101 1101 11010

Observe que el acarreo se suma a los bits que estén en la posición inmediata a la izquierda, similar a lo que se hace en el sistema decimal.

2.7.2.

Resta binaria

En este caso hacemos uso de la tabla siguiente donde en forma similar a la resta decimal, cuando el minuendo es menor que el sustraendo, se toma prestado un bit de la columna adyacente de la izquierda, como puede verse en el ejemplo a continuación. Minuendo m 0 0 1 1

Sustraendo S 0 1 1 0

Resta R 0 1 0 1

Prestado P 0 1 0 0

Reste 11011 − 1101 en binario Prestado Minuendo Sustraendo Resta

Lero y Jose

42

11 11011 1101 01110

Amaury Camargo B

2.7


2.7.3.

2


Multiplicaci´ on binaria

La multiplicaci´ on hace uso de los mismos principios del sistema decimal, utilizando las reglas de la tabla siguiente. En el ejemplo a continuación se ilustran tres casos de multiplicación binaria. Factores A B 0 0 0 1 1 0 1 1

Lero y Jose

Producto P 0 0 0 1

43

Amaury Camargo B

3

3.

CONJUNTOS

Conjuntos

3.1.

Definiciones B´ asicas

Construiremos nuestra teor´ıa estableciendo 3 conceptos indefinibles. Ellos son “conjunto” , “elemento” y “pertenece a”. Aunque son conceptos indefinidos, daremos una definición de ellos, basada en el lenguaje com´ un. Se notar´ a que en cierto sentido estas no son buenas definiciones, pues usan palabras que a su vez no hemos definido. Conjunto: Cualquier colecci´ on de objetos (no necesariamente matemáticos). Elemento o miembro: Un objeto de un conjunto es llamado elemento o miembro del conjunto. “a ∈ A” significa “el elemento a pertenece al conunto A”. “a ∈ / A” es la negación de la afirmación anterior. Observaci´ on: Dado un conjunto A y un objeto cualquiera suponemos que justamente una de las dos proposiciones siguientes se verifica “a ∈ A” ´ o “a ∈ / A”. ¿Cómo representamos conjuntos? La manera más simple es hacer una lista que encerramos entre llaves. A = {a, b, c, d} , B = {m ∈ Z : Existe un entero k tal que m = 2k} , C = {x ∈ Z/ Existe un entero q tal que x = 2q} . Observe que en las dos u ´ltimas definiciones lo u ńico que cambia es la variable, pero los conjuntos descritos son los mismos. Es decir el nombre de las variables es irrelevante.

3.2. 3.2.1.

Operaciones entre conjuntos Uni´ on

La unión de dos conjuntos A y B es el conjunto formado por todos los elementos que pertenecen a A o a B. Se nota A ∪ B. A ∪ B = {x : x ∈ A ∨ x ∈ B} . La disyunción, ∨, se utiliza en el sentido inclusivo, es decir, significa 2/ o”.

3.2.2.

Intersecci´ on

La intersección de dos conjuntos A y B es el conjunto formado por todos los elementos que pertenecen a A y a B. Se nota A ∩ B. A ∩ B = {x : x ∈ A ∧ x ∈ B} . Si A y B no tienen elementos en com´ un, es decir, si A ∩ B = ∅, entonces diremos que A y B son conjuntos disjuntos.

Lero y Jose

44

Amaury Camargo B

3.3

´ Algebra de conjuntos : Dualidad

3.2.3.

3

CONJUNTOS

Diferencia

La diferencia entre dos conjuntos A y B es el conjunto formado por todos los elementos que pertenecen a A y no a B. Se nota por (A − B) . A − B = {x : x ∈ A ∧ x 6∈ B} . El conjunto A − B se lee ”A menos B 2recibe también el nombre de complemento relativo del conjunto B respecto del conjunto A.

3.2.4.

Complementario

El complementario de un conjunto A es el conjunto formado por todos los elementos del conjunto universal que no pertenecen a A. Se nota Ac . Ac = {x : x ∈ U ∧ x ∈ / A} . Note que el complemento de A es la diferencia entre U y A, es decir, Ac = U − A.

3.2.5.

Diferencia Sim´ etrica

La diferencia simétrica entre dos conjuntos A y B es el conjunto formado por todos los elementos que pertenecen a (A − B) o a (B − A) pero no a ambos. Se nota por A 4 B. A 4 B = (A − B) ∪ (B − A) .

3.3.


Bajo las operaciones definidas en los apartados anteriores, los conjuntos satisfacen varias leyes o identidades. Observaremos que existe una dualidad entre las leyes que utilizan la intersección y las que utilizan la uni´ on.

3.3.1.

Leyes Idempotentes

Dado cualquier conjunto A en un universal arbitrario U , se verifica: 1. A ∪ A = A 2. A ∩ A = A Demostraci´ on (1.): En efecto, sea x un elemento arbitrario del universal U, entonces, [x ∈ (A ∪ A)] ⇔ [x ∈ A ∨ x ∈ A] ⇔ x∈A Lero y Jose

45

Amaury Camargo B

3.3


3

CONJUNTOS

De la arbitrariedad de x se sigue que ∀x [x ∈ (A ∪ A) ⇔ x ∈ A] , de aqu´ı que A ∪ A = A. 2. Análogamente se prueba que A ∩ A = A.

3.3.2.

Leyes Conmutativas

Dados dos conjuntos A y B de un universal arbitrario U , se verifica: 1. A ∪ B = B ∪ A 2. A ∩ B = B ∩ A Demostraci´ on (1.): En efecto, sea x cualquier elemento de U, entonces, [x ∈ (A ∪ B)] ⇔ x ∈ A ∨ x ∈ B ⇔ x∈B∨x∈A ⇔ x ∈ (B ∪ A) Como x es un elemento cualesquiera de U , se sigue que ∀x [x ∈ A ∪ B ⇔ x ∈ B ∪ A] , por lo tanto, A ∪ B = B ∪ A. 2. De una forma similar se demuestra que A ∩ B = B ∩ A.

3.3.3.

Leyes Asociativas

Dados tres conjuntos A, B y C de un universal arbitrario U , se verifica: 1. A ∪ (B ∪ C) = (A ∪ B) ∪ C 2. A ∩ (B ∩ C) = (A ∩ B) ∩ C

Lero y Jose

46

Amaury Camargo B

3.3


3

CONJUNTOS

Demostraci´ on (1.): En efecto, sea x un elemento arbitrario de U, entonces, x

∈

[A ∪ (B ∪ C)]

⇔ x ∈ A ∨ [x ∈ (B ∪ C)] ⇔ x ∈ A ∨ (x ∈ B ∨ x ∈ C) ⇔ (x ∈ A ∨ x ∈ B) ∨ x ∈ C ⇔ (x ∈ A ∪ B) ∨ x ∈ C ⇔ x ∈ (A ∪ B) ∪ C

.

De la arbitrariedad de x se sigue que ∀x [x ∈ A ∪ (B ∪ C) ⇔ x ∈ (A ∪ B) ∪ C] , de aqu´ı que A ∪ (B ∪ C) = (A ∪ B) ∪ C. 2. Análogamente se demuestra que A ∩ (B ∩ C) = (A ∩ B) ∩ C.

3.3.4.

Leyes Distributivas

Dado tres conjuntos A, B y C de un conjunto universal U , se verifica: 1. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) 2. A ∩ (B ∩ C) = (A ∩ B) ∪ (A ∩ C) Demostraci´ on (1.): En efecto,sea x una cualquier elemento del conjunto universal U , entonces x

∈

A ∪ (B ∩ C)

⇔ x ∈ A ∨ [x ∈ (B ∩ C)] ⇔ x ∈ A ∨ (x ∈ B ∧ x ∈ C) ⇔ (x ∈ A ∨ x ∈ B) ∧ (x ∈ A ∨ x ∈ C) ⇔ x ∈ (A ∪ B) ∧ x ∈ (A ∪ C) ⇔ x ∈ [(A ∪ B) ∩ (A ∪ C)]

.

Al ser x cualquier elemento de U , se sigue que ∀x [x ∈ A ∪ (B ∩ C) ⇔ x ∈ (A ∪ B) ∩ (A ∪ C)] , consecuentemente, A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) . Lero y Jose

47

Amaury Camargo B

3.3


3

CONJUNTOS

2. De una forma similar se prueba que A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) .

3.3.5.

Leyes de Identidad

Dado un conjunto cualquiera de un universal arbitrario U , se verifica: 1. A ∪ ∅ = A 2. A ∪ U = U 3. A ∩ ∅ = ∅ 4. A ∩ U = A Demostraremos la 1a y la 3a y la otras quedan como ejercicio. Demostraci´ on: 1. A ∪ ∅ = A. En efecto, sea x un elemento arbitrario de U, entonces, [x ∈ (A ∪ ∅)] ⇔ x ∈ A ∨ x ∈ ∅ ⇔ x ∈ A,

(x ∈ ∅ es falso siempre)

luego, ∀x [x ∈ (A ∪ ∅) ⇔ x ∈ A] , de aqu´ı que A ∪ ∅ = A. 3. A ∩ ∅ = ∅. Si x es cualquiera de , entonces [x ∈ (A ∩ ∅)] ⇔ x ∈ A ∧ x ∈ ∅ ⇔ x ∈ ∅,

(x ∈ ∅ es falso siempre) .

Nota: Los puntos 2 y 4 se dejan como ejercicio al estudiante.

Lero y Jose

48

Amaury Camargo B

3.3


3.3.6.

3

CONJUNTOS

Ley Involutiva

Dado un conjunto cualquiera A de un universal U , se verifica: (Ac )c = A. Demostraci´ on: Sea x cualquiera de U, entonces, [x ∈ (Ac )c ] ⇔ x ∈ / Ac ⇔ ∼ (x ∈ Ac ) ⇔ ∼ (x ∈ / A) ⇔ ∼ [∼ (x ∈ A)] ⇔ x∈A

,

luego, ∀x [x ∈ (Ac )c ⇔ x ∈ A] , es decir, (Ac )c = A.

3.3.7.

Leyes del Complementario

Dado un conjunto cualquiera A de un universal arbitrario , se verifica: 1. A ∪ Ac = U 2. U c = ∅ 3. A ∩ Ac = ∅ 4. ∅c = U Demostraremos la 1a y la 3a y los otras quedan como ejercicio. Demostraci´ on: 1. A ∪ Ac = U . En efecto, sea x cualquier elemento de U, entonces, [x ∈ (A ∪ Ac )] ⇔ x ∈ A ∨ x ∈ Ac ⇔ x∈A∨x∈ /A ⇔ x ∈ A ∨ ¬ (x ∈ A) ⇔ x∈U luego, ∀x [x ∈ (A ∪ Ac ) ⇔ x ∈] , por lo tanto, A ∪ Ac = U. Lero y Jose

49

Amaury Camargo B

3.3


3

CONJUNTOS

3. A ∩ Ac = ∅. En efecto, A ∩ Ac

=

{x ∈: x ∈ A ∧ x ∈ Ac }

⇐⇒ {x ∈: x ∈ A ∧ x ∈ / A} = ∅

3.3.8.

Leyes de De D’Morgan

Dados dos conjuntos A y B en un universal U , se verifica: 1. (A ∪ B)c = Ac ∩ B c 2. (A ∩ B)c = Ac ∪ B c Demostraci´ on: 1. (A ∪ B)c = Ac ∩ B c . En efecto, sea x un elemento arbitrario del conjunto universal . Entonces, [x ∈ (A ∪ B)c ] ⇔ x ∈ / (A ∪ B) ⇔ ∼ [x ∈ (A ∪ B)] ⇔ ∼ [(x ∈ A) ∨ (x ∈ B)] ⇔ [∼ (x ∈ A)] ∧ [∼ (x ∈ B)] ⇔ (x ∈ / A) ∧ (x ∈ / B) ⇔ (x ∈ Ac ) ∧ (x ∈ B c ) ⇔ x ∈ (Ac ∩ B c ) y al ser x un elemento arbitrario de , se sigue que ∀x [x ∈ (A ∪ B)c ⇔ x ∈ (Ac ∩ B c )] , luego, (A ∪ B)c = Ac ∩ B c . 2. Análogamente se prueba que (A ∩ B)c = Ac ∪ B c . Proposici´ on: Sean A, B, C y D subconjuntos arbitrarios de un conjunto universal arbitrario, . Entonces, 1. A ⊆ (A ∪ B) 2. A ∩ B ⊆ A 3. Si A ⊆ B, entonces A ∪ B = B Lero y Jose

50

Amaury Camargo B

3.3


3

CONJUNTOS

4. Si A ⊆ B, entonces A ∩ B = A 5. A ∪ (B − A) = A ∪ B Soluci´ on: 1. A ⊆ (A ∪ B), en efecto, si x es cualquiera de U , entonces (x ∈ A) ⇒ x ∈ A ∨ x ∈ B ⇔ x∈A∪B luego, ∀x [x ∈ A ⇒ x ∈ (A ∪ B)] , de aqu´ı que a ⊆ (A ∪ B) . 2. A ∩ B ⊆ A, en efecto, sea x un elemento de A ∩ B. Entonces, [x ∈ A ∩ B] ⇔ x ∈ A ∧ x ∈ B ⇒ x∈A luego, ∀x [x ∈ (A ∩ B) ⇒ x ∈ A] , de donde se sigue que A ∩ B ⊆ A. 3. Si A ⊆ B, entonces A ∪ B = B, en efecto, sea x cualquiera de U y supongamos que A ⊆ B [x ∈ (A ∪ B)] ⇔ x ∈ A ∨ x ∈ B ⇒ x∈B∨x∈B ⇔ x∈B luego, ∀x [x ∈ (A ∪ B) ⇒ x ∈ B] , por lo tanto, A ∪ B ⊆ B, y por (1) B ⊆ (A ∪ B) . 4. Si A ⊆ B, entonces A ∩ B = A, por el apartado (2), tenemos que A ∩ B ⊆ A.

Lero y Jose

51

Amaury Camargo B

3.3


3

CONJUNTOS

Veamos la inclusi´ on contraria. Supongamos que A ⊆ B y sea x un elemento arbitrario de U , entonces (x ∈ A) ⇒ x ∈ A ∧ x ∈ B ⇔ x ∈ (A ∩ B) luego, ∀x [x ∈ A ⇒ x ∈ (A ∩ B)] , de aqu´ı que A ⊆ (A ∩ B) . Tenemos pues que A ⊆ (A ∩ B)

y

(A ∩ B) ⊆ A,

por lo tanto, A = A ∩ B. 5. A ∪ (B − A) = A ∪ B, en efecto, A ∪ (B − A) = A ∪ (B ∩ Ac ) = (A ∪ B) ∩ (A ∪ Ac ) = (A ∪ B) ∩ U = A∪B Proposiciones: Sean A, B, C y D subconjuntos arbitrarios de un conjunto universal U . Entonces, 1. A − B ⊆ A 2. Si A ⊆ B y C ⊆ D, entonces (A ∪ C) ⊆ (B ∪ D) 3. Si A ⊆ B y C ⊆ D, entonces (A ∩ C) ⊆ (B ∩ D) 4. A − ∅ = A 5. A ∩ (B − A) = ∅ 6. A − (B ∪ C) = (A − B) ∩ (A − C) 7. A − (B ∩ C) = (A − B) ∪ (A − C) Ejercicio: Probar las identidades siguientes: 1. A ∪ (A ∩ B) = A 2. A ∩ (A ∪ B) = A Lero y Jose

52

Amaury Camargo B

3.3


3

CONJUNTOS

3. A ∪ (Ac ∩ B c ) = A ∪ B Soluci´ on: 1. A ∪ (A ∩ B) = A, sea x un elemento cualquiera del universal Ω, entonces x

∈

A ∪ (A ∩ B) ⇔ x ∈ A ∨ x ∈ (A ∩ B)

⇒ x ∈ A, luego, ∀x [x ∈ A ∪ (A ∩ B) ⇒ x ∈ A] , es decir A ∪ (A ∩ B) ⊆ A. Por otro lado, siempre se verifica que A ⊆ A ∪ X, ∀X ∈ Ω, en particular, A ⊆ A ∪ (A ∩ B) . De la doble inclusi´ on se sigue el resultado, A = A ∪ (A ∩ B) . 2. A ∩ (A ∪ B) = A, en efecto A ∩ (A ∪ B) = (A ∩ A) ∪ (A ∩ B) = A ∪ (A ∩ B) = A 3. A ∪ (Ac ∩ B) = A ∪ B, en efecto A ∪ (Ac ∩ B) = (A ∪ Ac ) ∩ (A ∪ B) = Ω ∩ (A ∪ B) = A∪B

Lero y Jose

53

Amaury Camargo B

3.4

Conjuntos finitos, principio de conteo

3.4.

3

CONJUNTOS


Se dice que un conjunto es finito si contiene exactamente m elementos diferentes en donde m denota alg´ un entero no negativo. En caso contrario, se dice que el conjunto es infinito. Por ejemplo, el conjunto vac´ıo y el conjunto de letras en el alfabeto espa˜ nol son finitos, mientras que el conjunto de los enteros positivos pares, {2, 4, 6, . . .} , es infinito. Si un conjunto A es finito, n (A) denotará el n´ u mero de elementos de A. Algunos textos usan 6= (A) en lugar de n (A). Si A y B son conjuntos finitos disyuntos, entonces A ∪ B es finito y n (A ∪ B) = n (A) + n (B) . Demostraci´ on: Al contar los elementos de A ∪ B, primero contamos los que están en A. Hay n (A) de éstos. Los u ńicos otros elementos de A ∪ B son los que est´ an en B, pero no en A. Pero como A y B son disyuntos, ning´ un elemento de B est´ a en A, de modo que hay n (B) elementos que están en B, pero no en A. Por lo tanto, n (A ∪ B) = n (A) + n (B), también tenemos una fórmula para n (A ∪ B), aunque A y B no sean disyuntos. Si A y B son conjuntos finitos, entonces A ∪ B y A ∩ B son finitos y n (A ∪ B) = n (A) + n (B) − n (A ∩ B) . Podemos aplicar este resultado para obtener una fórmula semejante para cualquier n´ umero finito, k, de conjuntos finitos. As´ı, para k = 3, tenemos que Si A, B y C son conjuntos finitos, entonces también lo es A ∪ B ∪ C, y n (A ∪ B ∪ C) = n (A) + n (B) + n (C) − n (A ∩ B) − n (A ∩ C) − n (B ∩ C) + n (A ∩ B ∩ C) . Por ejemplo: Supongamos que 100 de los 120 estudiantes de matemáticas de una facultad toman por lo menos un idioma entre, francés, alem´ an y ruso. Suponga también que: 65 45 42 20 25 15

estudian estudian estudian estudian estudian estudian

francés alem´ an ruso francés y alem´ an francés y ruso alem´ an y ruso

Sean F, A y R los conjuntos de estudiantes que estudian francés, alemán y ruso, respectivamente. Queremos encontrar el n´ umero de estudiantes que estudian todos los tres idiomas, y encontrar el n´ umero correcto de estudiantes en cada una de las ocho regiones del diagrama de Venn en la figura siguiente (a). Por el corolario anterior, n (F ∪ A ∪ R) = n (F ) + n (A) + n (R) − n (F ∩ A) − n (F ∩ R) − n (A ∩ R) + n (F ∩ A ∩ R) . Lero y Jose

54

Amaury Camargo B

3.4


3

CONJUNTOS

Ahora, n (F ∪ A ∪ R) = 100, ya que 100 de los estudiantes estudian por lo menos uno de los idiomas. Substituyendo, 100 = 65 + 45 + 42 − 20 − 25 − 15 + n (F ∩ A ∩ R) , y por lo tanto, n (F ∩ A ∩ R) = 8, o sea que 8 estudiantes estudian los tres idiomas. Usamos ahora este resultado para llenar el diagrama de Venn. Tenemos: 8 estudian todos los idiomas 20 − 8 = 12 estudian francés y alemán pero no ruso 25 − 8 = 17 estudian francés y ruso pero no alemán 15 − 8 = 7 estudian alem´ an y ruso pero no francés 65 − 12 − 8 − 17 = 28 estudian solamente francés 45 − 12 − 8 − 7 = 18 estudian solamente alemán 42 − 17 − 8 − 7 = 10 estudian solamente ruso 120 − 100 = 20 no estudian ninguno de los idiomas. As´ı el diagrama completo est´ a en la figura siguiente (b). Observe que 28 + 18 + 10 = 56 estudiantes estudian uno de los tres idiomas. (a)

(b)

Ejercicios propuestos 5. 1. Demostrar las siguientes relaciones entre conjuntos. a) A ∩ (B − C) = (A ∩ B) − C b) A − (B ∪ C) = (A − B) ∩ (A − C) c) (A − B) − C ⊂ A − (B − C) d ) (A − B) ∩ (B − A) = φ e) Si B ⊂ A entonces A ∪ B = A f ) Si X ⊂ A y X ⊂ B entonces X ⊂ A ∩ B g) Si B ⊂ A entonces B ∪ C ⊂ A ∪ C h) Si B ⊂ A entonces B ∩ C ⊂ A ∩ C i ) Si A ⊂ φ entonces A = φ j ) A − B = A − (A ∩ B) = (A ∪ B) − B k ) (A ∪ B) − C = (A − C) ∪ (B − C) l ) (A ∩ B) − C = (A − C) ∩ (B − C) m) (A − B) − C = A − (B ∪ C) n) A − (B − C) = (A − B) ∪ (A ∩ C) Lero y Jose

55

Amaury Camargo B

3.4


3

CONJUNTOS

n ˜) A ∪ (B − C) = (A ∪ B) − (C − A) o) A = (A ∩ B) ∪ (A ∩ (A − B)) 2. Dar un contraejemplo para probar que las siguientes proposiciones no son teoremas. a) A ∪ B = A ∪ D ⇒ B = D b) A ∩ B = A ∩ D ⇒ B = D c) A − B = φ ⇒ A = B d ) (B ∪ C ⊂ A ∪ C) ⇒ (B ⊂ A) e) (A ⊂ C) ⇒ (A ⊂ B ∧ B ⊂ C) f ) (B ∩ C ⊂ A ∩ C) ⇒ (B ⊂ A) g) (X ⊂ A ∪ B) ⇒ (X ⊂ A ∧ X ⊂ B) h) (A − B) − C = A − (B − C) i ) P (A ∪ B) ⊂ P (A) ∪ P (B) j ) (A ∩ B) = φ ⇒ (A = φ) ∨ (B = φ) 3. Para cada uno de los numerales siguientes, elaborar un diagrama de Venn-Euler que represente el conjunto indicado. a) (A − B) − C b) (A ∩ C) − (B ∪ A) c) (A ∩ B) − C d ) (A − B) ∪ (C − B) e) (A ∪ B ∪ C)c f ) (A ∩ B ∩ C)c g) Ac ∩ B c ∩ C c h) (Ac − C c ) − B c 4. A una conferencia internacional sobre contaminación del medio ambiente, asisten 100 especialistas, de los cuales 50 hablan inglés, 60 portugués y 50 espa˜ nol; de ellos 30 hablan portugués e inglés; 20 inglé s y espa˜ nol; 20 portugués y espa˜ nol. ¿Cuántos asistentes hablan los tres idiomas?. 5. Una ensambladora de autos recibi´ o una orden de fabricación de 38 automóviles tipo sedán, con las siguientes caracter´ısticas: 18 con aire acondicionado; 23 con vidrios eléctricos y 29 con cojiner´ıa de lujo. De estos, 3 deben tener solamente vidrios eléctricos, 8 deben tener solamente cojiner´ıa de lujo, 9 de los veh´ıculos deben tener solamente vidrios eléctricos y cojiner´ıa de lujo, 5 de los veh´ıculos deben tener los tres aditamentos. Determinar: a) ¿Cu´ antos veh´ıculos llevan aire acondicionado y cojiner´ıa de lujo, solamente?. b) ¿Cu´ antos veh´ıculos llevan aire acondicionado solamente?. Lero y Jose

56

Amaury Camargo B

3.4


3

CONJUNTOS

c) ¿Cu´ antos veh´ıculos llevan aire acondicionado y vidrios eléctricos solamente?. 6. En un inventario minero realizado en algunas regiones del pa´ıs acerca de la producción futura de recursos no renovables, se encontr´ o que: 8 poseen petróleo, 15 poseen carbón y 13 poseen oro; 6 poseen solamente carb´ on y oro; 4 solo poseen oro, 3 poseen los tres recursos; ninguna de las regiones posee petr´ oleo y carb´ on solamente. Determinar: a) ¿Cu´ antas regiones intervinieron en el inventario?. b) ¿Cu´ antas regiones poseen solamente petróleo?. c) ¿Cu´ antas regiones poseen solamente carbón?. 7. Los siguientes son los datos que muestran las preferencias de algunos aspirantes a ingresar a la universidad por ciertos programas: a) 50 prefieren medicina. b) 47 prefieren ingenier´ıa. c) 35 prefieren biolog´ıa. d ) 16 prefieren ingenier´ıa y biolog´ıa. e) 11 prefieren ingenier´ıa y medicina. f ) 15 prefieren biolog´ıa y medicina. g) 9 prefieren las tres. Determinar: 1.

a) 1) 2) 3) 4) 5)

¿Cu´ antos ¿Cu´ antos ¿Cu´ antos ¿Cu´ antos ¿Cu´ antos

aspirantes aspirantes aspirantes aspirantes aspirantes

fueron encuestados?. prefieren u ńicamente medicina?. no prefieren biolog´ıa?. prefieren medicina o biolog´ıa pero no ingenier´ıa?. prefieren medicina o ingenier´ıa?.

8. La secretar´ıa de educaci´ on municipal requiere la provisión de 29 cargos docentes en las áreas: 13 profesores de matem´ aticas; 13 profesores de f´ısica y 15 profesores de sistemas. Para el cubrimiento de los cargos se requiere que: 6 profesores dicten matemáticas y f´ısica, 4 profesores dicten f´ısica y sistemas y 5 profesores dicten matemáticas y sistemas. Determinar: 1.

a) ¿Cu´ antos profesores se requiere que dicten las tres áreas?. b) ¿Cu´ antos profesores se requiere que dicten matemáticas u ńicamente?. c) ¿Cu´ antos profesores se requiere que dicten matemáticas y sistemas pero no f´ısica?.

9. Con relaci´ on al problema anterior. En respuesta a la solicitud de trabajo, se seleccionaron 29 aspirantes cuyas solicitudes presentan las siguiente información: Lero y Jose

57

Amaury Camargo B

3.4


3

CONJUNTOS

a) 15 pueden dictar f´ısica. b) 16 pueden dictar sistemas. c) 6 pueden dictar matem´ aticas y f´ısica. d ) 5 pueden dictar f´ısica y sistemas. e) 1 puede dictar las tres ´ areas. f ) 7 pueden dictar solamente sistemas. Determinar: 1.

a) 1) ¿Cu´ antos aspirantes seleccionados se presentaron para dictar matemáticas?. 2) ¿Qué puestos no pueden cubrirse?. 3) ¿Cu´ antos solicitantes y en qué área no pueden ser finalmente itidos?.

Lero y Jose

58

Amaury Camargo B

4

´ NOCIONES SOBRE ALGEBRA DE BOOLE

´ Nociones sobre Algebra de Boole

4.

El álgebra de Boole es una estructura matemática que, como tal, abarca un abanico de situaciones cuya componente com´ un es la que se formula en su definición. En particular, el ´ algebra de Boole tiene aplicación en la s´ıntesis de redes de conmutación, en el estudio de circuitos digitales y en el an´ alisis y programación mediante ordenador.

4.1.

´ Definici´ on de Algebra de Boole

Un conjunto β dotado de dos leyes de composición interna (suma y producto) tiene estructura de a´lgebra de Boole si se verifican las propiedades siguientes. 1. Las dos leyes son asociativas (x + y) + z = x + (y + z) (xy) z = x (yz)

∀x, y, z ∈ β

2. Las dos leyes son conmutativas x+y = y+x ∀x, y, z ∈ β

xy = yx 3. Cada ley tiene elemento neutro ∃0 ∈ β : x + 0 = x

∀x ∈ β

∃1 ∈ β : x · 1 = x

∀x ∈ β

4. Para cada elemento x ∈ β existe un u ńico elemento x ∈ β, llamado complementario de x, tal que x+x = 1 xx = 0 5. Cada ley es distributiva respecto a la otra x (y + z) = xy + xz x + (yz) = (x + y) (x + z)

∀x, y, z ∈ β

Estos cinco pares de propiedades se consideran propiedades primitivas que caracterizan la estructura de álgebra de Boole. También reciben el nombre de axiomas del álgebra de Boole. El resto de propiedades se deduce a partir de éstas. Lero y Jose

59

Amaury Camargo B

4.1

´ Definición de Algebra de Boole

4


1. Consideremos un conjunto U al que nos referimos como universo. Llamamos conjunto de las partes del conjunto U al conjunto formado por todos los subconjuntos del conjunto U ; lo denotamos por P (U ). Si el n´ umero de elementos de U es n (U ) = n entonces n (P (U )) = 2n . Todo conjunto P (U ) con las operaciones unión de conjuntos, ∪, e intersección de conjuntos, ∩, tiene estructura de ´ algebra de Boole. El elemento neutro de la uni´ on de conjuntos es el conjunto vac´ıo, ∅, mientras que el neutro de la intersección es el conjunto universo U . El elemento complementario de cualquier subconjunto A ∈ P (U ) es el complementario en el sentido de conjuntos: A0 = {x ∈ U : x ∈ / A} 2. Una proposici´ on l´ ogica es un enunciado declarativo que puede ser verdadero o falso, pero no ambas cosas a la vez. El conjunto de las proposiciones lógicas con las operaciones disyunci´ on (o, ∨) y conjunci´ on (y, ∧) tiene estructura de álgebra de Boole. 3. El álgebra de Boole binaria, formada u ńicamente por dos elementos: β = {0, 1}

4.1.1.

Principio de dualidad del ´ algebra de Boole

Toda propiedad que pueda deducirse de las propiedades primitivas o de cualquier otra propiedad derivada de éstas da lugar a otra propiedad que se obtiene intercambiando: Las operaciones suma y producto Los s´ımbolos 0 y 1.

La propiedad as´ı obtenida recibe el nombre de propiedad dual de la inicial. El principio de dualidad es consecuencia de la propia estructura de álgebra de Boole, ya que cada para de propiedades en su definici´ on est´ a formada por una y por su dual.

Lero y Jose

60

Amaury Camargo B

4.2

´ Expresiones de Boole: Forma suma de productos 4 NOCIONES SOBRE ALGEBRA DE BOOLE

4.1.2.

Propiedades en un ´ algebra de Boole

Las siguientes propiedades son consecuencia de las propiedades primitivas: 1. Involución: x0

0

∀x ∈ β.

= x,

2. Idempotencia: x + x = x,

∀x ∈ β.

xx = x,

3. x0 = 0,

∀x ∈ β.

x + 1 = 1,

4. Absorción: x + xy = x x (x + y) = x

∀x, y ∈ β.

5. Los neutros son rec´ıprocamente complementarios: 00 = 1,

10 = 0.

y

6. x + x0 y = x + y,

x x0 + y = xy,

∀x, y ∈ β.

7. Leyes de De Morgan: (1a )

(x + y)0 = x0 y 0 (xy)0 = x0 + y 0

(2a )

4.2.

Expresiones de Boole: Forma suma de productos

Considere un conjunto de variables (o de letras o de s´ımbolos), digamos x1 , x2 , . . . , xn . Una expresi´ on Booleana E en estas variables, algunas veces escrito E (x1 , . . . , xn ), es una variable o una expresi´ on construida con estas variables que usan las operaciones Booleanas +, ∗ y (0 ) Ejemplo 11. 0 0 E = x + y 0 + z + xyz 0 + x0 + y

y

F =

0 0 xy 0 z 0 + y + x0 z

Son expresiones de Boole en x, y y z.

Definici´ on 1. Un literal es una variable o una variable complementaria, como x, x0 , y, y 0 .

Lero y Jose

61

Amaury Camargo B

4.2


Definici´ on 2. Un producto fundamental es un literal o un producto de dos o m´ as literales en los cuales no hay dos literales con una misma variable. Por ejemplo, xz 0 , xy 0 z, x, y 0 , yz 0 , x0 yz son productos fundamentales, sin embargo, xyx0 z y xyzy no lo son; el primero contiene x y x0 y el segundo contiene a y en dos sitios. Observe que: xyx0 z = xx0 yz = 0yz = 0 (ya que xx0 = 0, por la ley de complemento) y xyzy = xyyz = xyz (ya que yy = y, por la ley de idempotencia). En otras palabras, todo producto de Boole se puede reducir a 0 o a un producto fundamental. Observaci´ on: Un producto fundamental, P1 , se dice que está incluido o contenido en otro producto fundamental, P2 , si los literales de P1 son también literales de P2 . Por ejemplo, x0 z está incluido en x0 yz, ya que x0 y z son literales de x0 yz. Sin embargo, x0 z no está contenido en xy 0 z, ya que x0 no es un literal de xy 0 z. En caso de que P1 esté incluido en P2 , entonces por la ley de absorción P1 + P2 = P1 Por ejemplo, x0 z + x0 yz = x0 z. Observaci´ on: Una expresión de Boole E se dice que está en forma de suma de productos o en forma minterm si E es un producto fundamental, o es la suma de dos o más productos fundamentales, ninguno de los cuales está incluido en otro. Por ejemplo, considere las expresiones E1 = xz 0 + y 0 z + xyz 0

y

E2 = xz 0 + x0 yz 0 + xy 0 z

Aunque la primera expresi´ on, E1 , es una suma de productos, no está en la forma de suma de productos, 0 ya que xz est´ a contenida en xyz 0 . Sin embargo, por la ley de absorción, E1 se puede expresar como E1 = xz 0 + y 0 z + xyz 0 = xz 0 + xyz 0 + y 0 z = xz 0 + y 0 z que está en forma de suma de productos. La segunda expresión E2 , ya está en forma de suma de productos. Observaci´ on: Toda expresión de Boole no nula E se puede poner en forma de suma de productos con el siguiente procedimiento (Algoritmo). 1. Usando las leyes de De D’Morgan y la involución, podemos mover la operación de complemento dentro de cualquier paréntesis hasta que finalmente se aplique sólo a variables. E consistir´ a entonces solamente de sumas y productos de literales. 2. Usando la ley distributiva, podemos transformar E en una suma de productos. Lero y Jose

62

Amaury Camargo B

4.2


3. Usando las leyes conmutativa, de idempotencia y de complemento, podemos transformar cada producto de E en 0 o en un producto fundamental. Finalmente, usando la ley de absorci´ on, podemos poner E en forma de suma de productos. Por ejemplo: 0 Consideremos la expresi´ on Booleana E = (ab)0 c [(a0 + c) (b0 + c0 )]0 . Aplicando el anterior algoritmo, 1. E = (ab)00 + c0

0 (a + c) + (b0 + c0 )0 = (ab + c0 ) (ac0 + bc)

2. E = abac0 + abbc + ac0 c0 + bcc0 3. E = abc0 + abc + ac0 + 0 = ac0 + abc

Observaci´ on: Una expresión de Boole (no nula) E (x2 , x2 , . . . , xn ) se dice que está en forma completa de suma de productos si E est´ a en forma de suma de productos, y en cada producto se usan todas las variables (obsérvese que m´ aximo hay 2n de tales productos). Cualquier expresión de Boole E que sea una suma de productos se puede escribir en forma completa de suma de productos. En efecto, si un producto fundamental P de E no usa x, entonces podemos multiplicar P por xi + x0i ; éste se puede hacer ya que xi + x0i = 1. Continuamos hasta que todos los productos usen todas las variables. Otra consideraci´ on demuestra que la forma completa de suma de productos es u ńica. En resumen: Toda expresión Booleana no nula E (x1 , x2 , . . . , xn ) se puede poner en forma completa de sumas de productos, y tal representaci´ on es u ńica. Ejemplos:

4.2.1.

Definici´ on de maxterm y minterm

β = {0, 1} denota el ´ algebra de Boole binaria. En β n el producto de n variables diferentes, complementadas o no, recibe el nombre de minterm o término m´ınimo. En β n la suma de n variables diferentes, complementadas o no, recibe el nombre de maxterm o término máximo. En β 4 son minterm x1 x2 x3 x4 x1 x2 x3 x4 En β 3 son maxterm x1 + x2 + x3

x1 + x2 + x3

Propiedades Lero y Jose

63

Amaury Camargo B

4.3

Obtención de las formas can´ onicas

4


1. Toda funci´ on Booleana f : β n ⇒ β puede ser expresada como suma de minterm (suma de productos). Esta expresi´ on es la que se conoce como forma can´ onica disyuntiva de la funci´ on f . xi δi δ1 δ2 δn xi = f (x1 , x2 . . . , xn ) = x1 x2 . . . xn xi 2. Toda funci´ on Booleana f : β n ⇒ β puede ser expresada como producto de maxterm (producto de sumas). Esta expresi´ on es la que se conoce como forma can´ onica conjuntiva de la funci´ on f. xi δi δ2 δ1 δn xi = f (x1 , x2 , . . . , xn ) = x1 + x2 + · · · + xn xi De las dos formas can´ onicas la m´ as empleada es la forma disyuntiva.

Propiedades 1. Las formas can´ onicas de una funci´ on Booleana f : β n ⇒ β son u ńicas. 2. Dos funciones Booleanas son equivalentes (son la misma función) si y sólo si tienen las mismas formas can´ onicas.

4.3.

Obtenci´ on de las formas can´ onicas

Obtenci´ on a partir de la tabla de valores de la funci´ on La forma can´ onica disyuntiva de una función f : β n ⇒ β se obtiene a partir de cada uno de los valores 1 que toma la funci´ on. La u ńica forma en la que un producto de todas las variables (o sus complementarios) toma valor 1 es con todos sus factores tomando valor 1. As´ı el n´ umero de min en la forma disyuntiva es igual al n´ umero de unos (1) en la tabla de valores de f . Por su lado, la forma can´ onica conjuntiva de una función f : β n ⇒ β se obtiene a partir de cada uno de los valores 0 que toma la funci´ on. La u ńica posibilidad para que una suma de todas las variables (o sus complementarios) tome valor 0 es con todos sus términos tomando valor 0. El n´ umero de max en la forma conjuntiva es igual al n´ umero de ceros (0) en la tabla de valores de f . Para una funci´ on f : β n ⇒ β la suma del n´ umero de minterm en la forma canónica disyuntiva y el n´ umero de max en la forma can´ onica conjuntiva es igual a 2n , que es el cardinal de β n . Obtención de las formas can´ onicas disyuntiva y conjuntiva de la función f : β n ⇒ β cuya tabla de

Lero y Jose

64

Amaury Camargo B

4.3


4


valores es x1 0 0 0 0 1 1 1 1

x2 0 0 1 1 0 0 1 1

x3 0 1 0 1 0 1 0 1

f 1 0 1 1 0 0 1 1

Forma can´ onica disyuntiva: f (x1 , x2 , x3 ) = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 Forma can´ onica conjuntiva: f (x1 , x2 , x3 ) = (x1 + x2 + x3 ) (x1 + x2 + x3 ) (x1 + x2 + x3 ) N´ umero de min: 5.

N´ umero de max: 3. Total: 5 + 3 = 8 = 23 .

2. Obtenci´ on a partir de una expresi´ on en f´ ormula Para obtener la forma can´ onica disyuntiva a partir de una expresión cualquiera conviene, en una primera aproximación, obtener una suma de productos, aunque estos productos no sean min. La propiedad que en mayor medida permita esta aproximación es la distributiva del producto respecto a la suma. Una vez obtenida la suma de productos, cada variable xj que no figure en un producto se puede a˜ nadir al mismo multiplicando por 1 en la forma 1 = xj + xj . A continuación se vuelve a aplicar la propiedad distributiva. Para la forma can´ onica conjuntiva se requiere transformar la expresión inicial en producto de sumas. En este proceso juega un papel esencial la propiedad distributiva de la suma respecto al producto. Una vez obtenido el producto de sumas, cada variable xj que no figure en una suma se puede a˜ nadir a la misma sumando 0 en la forma 0 = xj xj . A continuación se vuelve a aplicar la propiedad distributiva. Observaci´ on: En ambos procedimientos, después de multiplicar por 1 o sumar 0 y aplicar la distributiva, se debe eliminar los min o max repetidos empleando la propiedad de idempotencia. Por ejemplo, obtener la forma can´ onica disyuntiva y conjuntiva de la función f : β n ⇒ β definida por f (x, y, z) = x + yz. Lero y Jose

65

Amaury Camargo B

4.3


4


Forma can´ onica disyuntiva: f (x, y, z) = x (y + y) (z + z) + (x + x) yz = xyz + xyz + xyz + xyz + xyz + xyz = xyz + xyz + xyz + xyz + xyz En este caso, la f´ ormula inicial ya era suma de productos. En el primer sumando se ha hecho aparecer las variables y, z, mientras que en el segundo se ha a˜ nadido x. Después de aplicar la propiedad distributiva se ha comprobado que el primer y el u ´ltimo minterm estaban repetidos y se ha eliminado uno de ellos. Forma can´ onica conjuntiva: f (x, y, z) = (x + y) (x + z) = (x + y + zz) (x + yy + z) = (x + y + z) (x + y + z) (x + y + z) (x + y + z) = (x + y + z) (x + y + z) (x + y + z)

En primer lugar se ha aplicado la distributiva de la suma respecto al producto para obtener un producto de sumas. En el primer sumando se ha agregado la variable z y en el segundo la variable y. Es importante a˜ nadir las variables en el orden que figuran en la función, x y z. De esta manera la simplificaci´ on de max es m´ as sencilla, tal y como ha sucedido con el primer y el tercer maxterm que estaban repetidos. Obtención de las formas can´ onicas disyuntiva y conjuntiva de la función f : β n ⇒ β definida por f (x, y, z, w) = (x + y) (z + w) (x + z) . Forma can´ onica disyuntiva: f (x, y, z, w) = xzx + xzz + xwx + xwz + yzx + yzz + ywx + ywz Después de aplicar la propiedad distributiva del producto respecto a la suma ha resultado una suma de ocho productos. De entre éstos, el primero, el segundo, el tercero y el sexto son nulos, pues en ellos o zz que es igual a 0 por la propiedad del complementario. Los cuatro aparece una expresi´ on del tipo xx ´ productos restantes se escriben con sus variables en el orden dado por la función , x y z w. f (x, y, z, w) = xzw + xyz + xyw + yzw = x (y + y) zw + xyz (w + w) + xy (z + z) w + (x + x) yzw = xyzw + xyzw + xyzw + xyzw + xyzw + xyzw + xyzw + xyzw

Los min segundo y séptimo, cuarto y quinto as´ı como sexto y octavo están repetidos. Por la independencia, eliminamos uno de cada pareja y obtenemos la forma canónica disyuntiva de f con 5 min: f (x, y, z, w) = xyzw + xyzw + xyzw + xyzw + xyzw Lero y Jose

66

Amaury Camargo B

4.3


4


Forma can´ onica conjuntiva: f (x, y, z, w) = (x + y + zz + ww) (xx + yy + z + w) (x + yy + z + ww) = (x + y + z + w) (x + y + z + w) (x + y + z + w) (x + y + z + w) = (x + y + z + w) (x + y + z + w) (x + y + z + w) (x + y + z + w) = (x + y + z + w) (x + y + z + w) (x + y + z + w) (x + y + z + w)

La expresión inicial de la funci´ on ya es un producto de suma. En cada sumando hemos a˜ nadido en la posición correspondiente las variables que faltan en la forma xx, yy, zz ó ww. Después de aplicar la propiedad distributiva aparecen los max, observando que el segundo y el sexto están repetidos. Una vez eliminado uno de ellos se obtiene la forma canónica conjuntiva de f con los esperados 11 max, ya que card β 4 = 24 = 16 y en la forma canónica disyuntiva obtuvimos 5 min: f (x, y, z, w) = (x + y + z + w) (x + y + z + w) (x + y + z + w) (x + y + z + w) = (x + y + z + w) (x + y + z + w) (x + y + z + w) = (x + y + z + w) (x + y + z + w) (x + y + z + w) (x + y + z + w) Ejercicios propuestos:

Lero y Jose

67

Amaury Camargo B

4.4

Simplificaci´ on de funciones Booleanas

4.4.

4



Las formas can´ onicas de una funci´ on Booleana en β = {0, 1} son expresiones u ńicas que identifican cada función Booleana y la diferencia de las restantes funciones. No son, sin embargo, expresiones sencillas ni tienen una forma simplificada. El objetivo de esta secci´ on es la obtenci´ on de expresiones simplificadas para las funciones Booleanas, tanto si su expresi´ on inicial es una de las formas canónicas como si no lo es.

Métodos comunes 1. El método algebraico . 2. El método gr´ afico: Mapas de Karnaugh. 3. Los métodos iterativos: el método de Quine - McCluskey.(opcional)

4.4.1.

M´ etodo algebraico

El método denominado .algebraico ¸cociste en la utilización de las propiedades generales válidas en cualquier álgebra de Boole. Las siguientes propiedades facilitan en gran medida los procesos de simplificación. 1. Complementario. Permite eliminar términos de la forma x+x=1

xx = 0

2. Idempotencia. Permite reducir términos de la forma x+x=x

xx = x

3. Absorci´ on. Permite simplificar términos de la forma x + xy = x

x (x + y) = x

4. Leyes de D’Morgan. Act´ uan sobre el complementario de las operaciones reduciéndolo a complementarios sobre las variables x + y = xy xy = x + y 5. Distributivas. Permiten agrupar las variables, seg´ un convenga, en productos o sumas xy + xz = x (y + z) Lero y Jose

(x + y) (x + z) = x + yz 68

Amaury Camargo B

4.4


4


Simplificar la funci´ on f : β 3 ⇒ β definida por f (x, y, z) = x + xy + xyz + xz + xz. Simplificación: f (x, y, z) = x + xy + xyz + xz + xz = x (1 + yz) + xy + x (z + z) = x + xy + x = x + xy = (x + x) (x + y) = x+y Simplificar la funci´ on f : β 2 ⇒ β definida por f (x, y) = (x + y) (x + y) (x + y) . Simplificación: f (x, y) = (x + y) (x + y) (x + y) = (xx + xy + yx + yy) (x + y) = [x + x (y + y) + 0] (x + y) = x (x + y) = xx + xy = xy Simplificar la funci´ on f : β 4 ⇒ β definida por f (x, y, z, w) = w + wx + yz. Simplificación: f (x, y, z, w) = w + wx + yz = w (1 + x) + yz = w + yz = wyz = w (y + z) En esta simplificaci´ on se ha empleado en primer lugar la propiedad distributiva. El paso de la segunda a la tercera l´ınea es por la propiedad 1 + x = 1, ∀x ∈ β. Luego hemos empleado la 1a y 2a ley de D’ Morgan.

Lero y Jose

69

Amaury Camargo B

4.4


4.4.2.


4

Mapas de Karnaugh (K)

Para simplificar expresiones Booleanas, además de las leyes del álgebra lógica, se emplea un método llamado Mapas de Karnaugh o Mapas K. Los Mapas K son diagramas cuadrangulares o rectangulares que tienen 2n compartimientos o casillas, donde n es el n´ umero de variables l´ ogicas consideradas. Los diagramas asocian a cada compartimiento una fila de la tabla de verdad. El n´ umero binario que identifica cada fila de la tabla de verdad se hace corresponder con las coordenadas binarias que identifican cada casilla del Mapa K. En estos mapas se puede trabajar con términos minimales (min) llenando los compartimientos correspondientes a los unos, maximales (max) con los ceros (0) de la tabla de verdad. El uso de min o de max depende de la forma elegida para la expresión: la forma normal disyuntiva o la forma normal conjuntiva, respectivamente; su disposici´ on es tal que el paso de una posición a otra de la tabla, tanto en vertical como en horizontal, corresponde a la variación de una y sólo una variable. Mapas K (dos variables) Una expresión Booleana con dos variables, es decir f (x, y), tiene una tabla de verdad con cuatro filas, conteniendo cada una el valor de la función para cada combinaci´ on de valores de verdad de las variables x, y. El mapa K correspondiente es una tabla de (2 × 2) casillas como se muestra a continuaci´ on: x0 = 0 x = 1 y0 = 0 y=1 Si dos casillas contiguas (horizontal o verticalmente, no en diagonal) tienen unos (1), se dice que forman una adyacencia. Por ejemplo, si en el mapa K sólo aparecen unos (1) en el primer renglón, entonces la función Booleana en forma normal disyuntiva es: itbpF 1,5247in1,1459in0inF igure f (x, y) = x0 y 0 + xy 0 = y 0 x0 + y 0 x = y 0 x0 + x = y 0 ,1 = y0 Note que al simplificar la expresi´ on se anula la variable x porque x + x0 = 1. Además, ambos unos (1) se encuentran en el primer rengl´ on, es decir, se encuentran en el renglón denominado y 0 , por tanto la expresión simplificada es: f (x, y) = y 0 Simplificar la funci´ on Booleana representada en la tabla: x 0 0 1 1 Lero y Jose

y 0 1 0 1 70

f 0 1 1 1 Amaury Camargo B

4.4


4


El mapa K correspondiente a la tabla es: Ddddddd Este mapa K tiene dos adyacencias, una en la segunda fila y la otra en la segunda columna. La funci´ on sin simplificar es: f (x, y) = x0 y + xy 0 + xy Utilizando las adyacencias mencionadas se obtiene la función reducida: f (x, y) = y + x Observe que las adyacencias pueden sobreponerse, y que los valores en una fila o una columna pueden ser usados más de una vez. Adem´ as, una adyacencia de dos unos (1) elimina una variable.

Mapas K (tres variables) continuación:

El mapa K para tres variables es una de (2 × 4) como se presenta a

z0 = 0 z=1

x0 y 0 00

x0 y 01

xy 11

xy 0 10

Hay que observar que en el anterior mapa K para tres variables, la numeración binaria se cambia de la segunda columna a la tercera, es decir, se pasa de 01 a 11, no a 10. La u ńica razón para esto es que es deseable que haya cambio en una sola variable y no en ambas, como suceder´ıa si al 01 le sigue 10. De esta forma pueden distinguirse seis regiones: Regi´ on de x : columnas 3a y 4a Regi´ on de x0 : columnas 1a y 2a Regi´ on de y : columnas 2a y 3a Regi´ on de y 0 : columnas 1a y 4a Regi´ on de z : fila 2a Regi´ on de z 0 : fila 1a . En este caso pueden ocurrir adyacencias de dos, cuatro u ocho unos (1) . También se consideran las adyacencias entre la primera y cuarta columna, tal como si el mapa K fuera dibujado sobre un cilindro. Además, las adyacencias pueden estar en una sola fila o formando un cuadrado. Los ejemplos siguientes ilustran lo anterior. Encontrar la expresi´ on Booleana simplificada cuyo mapa K es: itbpF 4,2272in1,8922in0inF igure

Soluci´ on: Al existir una adyacencia de cuatro unos (1), la función Booleana de tres variables se reduce a una sola. Observe que la adyacencia est´ a en la primera y cuarta columna, es decir, en la región de y 0 , por tanto, la función Booleana simplificada ser´ a: f (x, y, z) = y 0 . Lero y Jose

71

Amaury Camargo B

4.4



4

Para demostrar lo anterior, se escribe la función en forma normal disyuntiva, as´ı: f (x, y, z) = x0 y 0 z 0 + x0 y 0 z + xy 0 z 0 + xy 0 z = x0 y 0 z 0 + z + xy 0 z 0 + z = x0 y 0 + xy 0 = y 0 x0 + x = y0.

Encontrar la expresi´ on Booleana simplificada cuyo mapa K es: itbpF 4,1433in1,6613in0inF igure La adyacencia est´ a en la segunda y tercera columna, es decir, en la región de y, por lo que la funci´ on Booleana simplificada ser´ a: f (x, y, z) = y. Para demostrar lo anterior, se escribe la función en la forma normal disyuntiva: f (x, y, z) = x0 yz 0 + x0 yz + xyz 0 + xyz = x0 y z 0 + z + xy z 0 + z = x0 y + xy = y x0 + x

= y.

Mapas K (cuatro variables) El mapa K para funciones booleanas de cuatro variables, es una tabla de (4 × 4) dise˜ nada de la siguiente forma:

Como en el caso anterior, pueden distinguirse 8 regiones, as´ı: Regi´ on de

x : columnas 3a y 4a

Regi´ on de x0 : columnas 1a y 2a Regi´ on de y : columnas 2a y 3a Regi´ on de y 0 : columnas 1a y 4a Regi´ on de z : filas 3a y 4a Regi´ on de z 0 : filas 1a y 2a Regi´ on de w : filas 2a y 3a Regi´ on de w0 : filas 1a y 4a .

Lero y Jose

72

Amaury Camargo B

4.4


4


Aqu´ı pueden ocurrir adyacencias de dos, cuatro, ocho o dieciséis unos (1) que eliminan una, dos, tres o cuatro variables, respectivamente. Se consideran adyacencias entre la primera y cuarta columna y también entre la primera y cuarta fila como puede verse en los ejemplos siguientes. Simplificar la funci´ on Booleana cuyo mapa K asociado es: itbpF 4,3638in2,8867in0inF igure f (x, y, z, w) = x0 y 0 z 0 w0 + xy 0 z 0 w0 + x0 y 0 zw0 + xy 0 zw0 + x0 yz 0 w + xyz 0 w + x0 yzw + xyzw = y 0 z 0 w0 x0 + x + y 0 zw0 x0 + x + yz 0 w x0 + x + yzw x0 + x = y 0 z 0 w0 + y 0 zw0 + yz 0 w + yzw = y 0 w0 z 0 + z + yw z 0 + z = yw + y 0 w0 . Simplificar la funci´ on Booleana cuyo mapa K asociado es: itbpF 4,4581in2,9291in0inF igure f (x, y, z, w) = x0 y 0 z 0 w0 + x0 y 0 z 0 w + x0 y 0 zw + x0 y 0 zw0 + xy 0 z 0 w0 + xy 0 z 0 w + xy 0 zw + xy 0 zw0 = x0 y 0 z 0 w0 + w + x0 y 0 z w0 + w + xy 0 z 0 w0 + w + xy 0 z w0 + w = x0 y 0 z 0 + x0 y 0 z + xy 0 z 0 + xy 0 z = x0 y 0 z 0 + z + xy 0 z 0 + z = x0 y 0 + xy 0 = y 0 x0 + x = y0. En los ejemplos anteriores la consideración de las adyacencias se˜ naladas conducen directamente a las expresiones simplificadas, observando las regiones del mapa K en las que se encuentran estas adyacencias.

M´ etodo para obtener la tabla a partir de la funci´ on Cada posición de la tabla corresponde a cierta agrupaci´ on de valores de las variables. Hemos de mirar cuáles de estas agrupaciones hacen que el valor de la funci´ on sea igual a 1 y, en este caso, colocar un 1 en la posición correspondiente. Ejemplo 12. f (x, y, z, w) = xyzw + xyzw zw

xy

00 01 11 10

Lero y Jose

00 1

01

11

10

1

73

Amaury Camargo B

4.4


4


Esta función consta exactamente de dos min. En el primero, se consigue el valor de 1 exactamente en el caso x = y = z = w = 0. En el segundo se consigue valor 1 sólo si x = y = 1 a la vez que z = 0 y w = 1. Ejemplo 13. f (x, y, z, w) = xyz zw

xy

00

00 01 11 10

01

11

10

1 1

El u ńico término de esta funci´ on no es un minterm. Se obtiene valor 1 exactamente para x = 0, y = z = 1. La variable w no figura en la expresión de la función de manera que ésta puede tomar valor 0 ó 1 sin afectar al valor de la funci´ on. Ejemplo 14. f (x, y, z, w) = yw Esta función toma valor 1 s´ olo si y = 0 y w = 0. Las variables x, z no figuran en la expresión de la función as´ı que pueden tomar cualquier valor. zw

xy

00 01 11 10

00 1

01

11

1

10 1

1

Ejemplo 15. f (x, y, z, w) = z zw

xy

00 01 11 10

00

01

11

10

1 1

1 1

1 1

1 1

El valor z = 1 hace que la funci´ on tome el valor 1. Los valores de x, y y w no intervienen en el valor de la función, de manera que sus ocho posibles agrupaciones dan lugar a ocho 1‘s en la tabla. Una vez completadas las posiciones de la tabla con 1, se consigna valor 0 en las restantes posiciones.

M´ etodo para obtener la funci´ on simplificada a partir de la tabla La disposición de la tabla permite agrupar las posiciones con valor 1 en grupos de 2p (0 ≤ p < n) correspondientes a expresiones simplificadas.

Lero y Jose

74

Amaury Camargo B

4.4



4

Para p = 3 agrupaciones de 23 = 8 posiciones con valor 1. 1 1

1 1

1 1

1 1 1 1

1 1

1 1 1 1

Para p = 2 agrupaciones de 22 = 4 posiciones con valor 1. 1 1

1 1

1

1

1

1

1 1 1 1

Para p = 1 agrupaciones de 21 = 2 posiciones con valor 1. 1

1 1

1

Para p = 0 agrupaciones de 20 = 1 posiciones con valor 1 (min). 1 En el momento de vaciar la tabla y pasar a la expresión simplificada de la función conviene tener en cuenta estas dos reglas: 1. Son preferible las agrupaciones de más a la de menos 1‘s, ya que dan lugar a términos m´ as simplificados. Una agrupaci´ on de un solo 1 es un minterm y corresponde a un sumando sin simplificaci´ on. 2. Si es necesario, las diferentes agrupaciones pueden solaparse, es decir, tener 1‘s en com´ un. Simplificar la funci´ on Booleana f : β 3 ⇒ β cuya tabla de valores es x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

f 0 0 0 1 0 1 1 1

La tabla de valores de la funci´ on tiene cuatro 1‘s de manera que su forma canónica disyuntiva es f (x, y, z) = xyz + xyz + xyz + xyz. Lero y Jose

75

Amaury Camargo B

4.4


4


Mapa de Karnaugh de la funci´ on f : xy

z

0 1

00 0 0

01 0 1

11 1 1

10 0 1

itbpF 4,4613cm1,6672cm0cmF igure Expresión simplificada para f . f (x, y, z) = yz + xy + xz. Simplificar la funci´ on Booleana f : β 4 ⇒ β cuya expresión es f (x, y, z, w) = xyzw + xyzw + xyzw + xyzw + xyzw + xyzw + xyzw.

Esta función est´ a expresada en forma canónica disyuntiva como suma de siete min. Cada uno de ellos da lugar a un 1 en su tabla de valores o en su mapa. Mapa de Karnaugh de la funci´ on f : zw

xy

00 01 11 10

00 0 1 1 1

01 0 1 1 0

11 0 0 0 0

10 0 0 1 1

Expresión simplificada para f : f (x, y, z, w) = xw + yz. Simplificar la funci´ on Booleana f : β 4 ⇒ β definida por f (x, y, z, w) = xw + xy + yz + xz.

Mapa de Karnaugh de la funci´ on f : zw

xy

00 01 11 10

00 1 0 0 1

01 1 0 0 0

11 1 0 0 0

10 1 0 0 1

Expresión simplificada para f : f (x, y, z, w) = zw + yw.

Lero y Jose

76

Amaury Camargo B

4.4


4


Esta función ya hab´ıa sido simplificada empleando propiedades generales del álgebra de Boole. Aplicando la propiedad distributiva, se puede obtener una expresión más reducida de la función f (x, y, z, w) = (z + y) w. Escribir la funci´ on f = (xy + yz 0 )0 + y 0 en la forma normal disyuntiva. Soluci´ on: 0 0 xy + yz 0 + y 0 = (xy)0 . yz 0 + y 0 = x0 + y 0 . y 0 + z + y 0 = y 0 + x0 . y 0 + z + y 0 = y 0 + x0 z + y 0 = y 0 + x0 z = y 0 x + x0

z + z 0 + x0 z y + y 0 = y 0 xz + xz 0 + x0 z + x0 z 0 + x0 yz + x0 y 0 z

= xy 0 z + xy 0 z 0 + x0 y 0 z + x0 y 0 z 0 + x0 yz + x0 y 0 z = xy 0 z + xy 0 z 0 + x0 y 0 z + x0 y 0 z 0 + x0 yz Una función Booleana puede ser expresada en forma normal disyuntiva en más de una manera, mediante el cambio del n´ umero de variables; sin embargo, para un n´ umero dado de variables la forma normal es u ńica. Por ejemplo, f = xy est´ a en forma normal disyuntiva en x y en y, pero si xy es multiplicada por z + z 0 , entonces f = xyz + xyz 0 est´ a también en forma normal en las variables x, y, z. En forma similar, g = x0 yz + xyz + x0 yz 0 + xyz 0 está en forma normal disyuntiva en x, y, z, pero reduciéndola se llega a g = y, la cual est´ a en forma normal en y. La forma normal disyuntiva en n variables que tiene 2n términos se llama ”forma normal disyuntiva completa n variables 2es idénticamente igual a la unidad. Por ejemplo, para el caso de dos variables (n = 2) la forma normal disyuntiva se puede obtener de la tabla: x 0 0 1 1

y 0 1 0 1

f x0y0 x0y xy0 xy

x0 y 0 + x0 y + xy 0 + xy = 1

Lero y Jose

77

Amaury Camargo B

4.4


4


cuyo valor es 1 porque x0 y 0 + x0 y + xy 0 + xy = x0 y 0 + y + x y 0 + y = x0 1 + x1 = x0 + x = 1 Encontrar y simplificar la funci´ on Booleana f (x, y, z) especificada en la tabla siguiente: F ila 0 1 2 3 4 5 6 7

x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

f (x, y, z) 1 0 1 0 1 0 1 0

Soluci´ on: La tabla anterior muestra el valor de f para cada una de las 23 = 8 posibles combinaciones de valores de 0 y 1 para x, y, z. Las combinaciones representadas en las filas 1, 5 y 6 de la tabla tienen valor 1. As´ı la forma normal disyuntiva de f contendrá tres términos: f (x, y, z) = x0 y 0 z + xy 0 z + xyz 0 = y 0 z x0 + x + xyz 0 = y 0 z,1 + xyz 0 = y 0 z + xyz 0 Escribir la funci´ on (xy + yz 0 )0 + y 0 en la forma conjuntiva. Soluci´ on: 0 0 xy + yz 0 + y 0 = (xy)0 . yz 0 + y 0 = x0 + y 0 . y 0 + z + y 0 = y 0 + x0 + y 0 . y 0 + z = y 0 + x0 + y 0 y 0 + y 0 + z = x0 + y 0 y 0 + z = x0 + y 0 + zz 0 . xx0 + y 0 + z = x0 + y 0 + z x0 + y 0 + z 0 x + y 0 + z x0 + y 0 + z = x0 + y 0 + z . x0 + y 0 + z 0 x + y 0 + z Lero y Jose

78

Amaury Camargo B

4.4



4

Una función Booleana puede ser expresada en forma normal conjuntiva en más de una manera, mediante el cambio del n´ umero de variables; sin embargo, para un n´ umero dado de variable la forma normal es u ńica. Por ejemplo, f = x + y est´ a en forma normal en x y en y, pero si a x + y se le suma z.z 0 entonces f = x + y + zz 0 ´ o f = (x + y + z) (x + y + z 0 ) está también en forma normal en las variables x, y, z. Por otra parte, g = (x0 + y + z) (x + y + z) (x0 + y + z 0 ) está en forma normal conjuntiva en x, y, z, pero simplificándola se obtiene g = y que est´ a en forma normal en y. La forma normal conjuntiva en n variables que tiene 2n términos se llama la forma normal conjuntiva completa en n variables y es igual a cero. Por ejemplo, para el caso de dos variables (n = 2) la forma normal conjuntiva completa se puede obtener de la siguiente tabla, al tomar las variables complementadas: x 0 0 1 1 (x + y) x + y Porque (x + y) x + y 0

x0 + y

y 0 1 0 1 0

f x + y0 x+y x0 + y 0 x0 + y x0 + y x0 + y 0

x0 + y 0

x0 + yy 0 = (x + 0) x0 + 0 =

x + yy 0

= xx0 = 0 Encontrar y simplificar la funci´ on Booleana f (x, y, z) especificada en la tabla siguiente: F ila 0 1 2 3 4 5 6 7

x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

f (x, y, z) 1 0 1 0 1 0 1 0

Como sólo dos filas de la tabla, la 1 y la 5, tienen valor cero, es más fácil escribir la función en forma normal conjuntiva, as´ı: f (x, y, z) = x + y + z 0 . xZˇ + y + z 0 = y + z 0 + x . y + z 0 + x0 = y + z 0 + xx0 = y + z0 + 0 = y + z0 Lero y Jose

79

Amaury Camargo B

4.4


4


En los ejemplos de este tipo, la forma normal disyuntiva se usa si el n´ umero de unos (1) es menor que el n´ umero de ceros (0) en la columna f y la forma normal conjuntiva se usa si el n´ umero de ceros (0) es menor que el n´ umero de unos (1).

Dos funciones, cada una expresada en la forma normal conjuntiva en n variables, son iguales si tienen idénticos factores.

La forma normal conjuntiva puede usarse para hallar el complemento de funciones escritas en esta forma. El complemento de una funci´ on escrita en forma normal conjuntiva es una función cuyos factores son exactamente aquellos de la forma normal conjuntiva completa, los cuales no aparecen en la funci´ on 0 0 0 0 dada. Por ejemplo, el complemento de (x + y ) (x + y ) es (x + y) (x + y) . Para cambiar una funci´ on de una forma normal a la otra se utiliza (f 0 )0 = f . El siguiente ejemplo ilustra el método. Encontrar la forma normal conjuntiva para la función f = xyz + x0 yz + xy 0 z 0 + x0 yz 0 h 0 0 i0 f0 = xyz + x0 yz + xy 0 z 0 + x0 yz 0 0 0 = x + y 0 + z 0 x + y 0 + z 0 x0 + y + z x + y 0 + z = (x + y + z) x0 + y + z 0 x + y + z 0 x0 + y 0 + z El apóstrofo significa el complemento de toda la expresión entre paréntesis. Después de negar doblemente la función, la primera negaci´ on se trata con la ayuda de las leyes de D’Morgan; para la segunda negaci´ on (la del corchete) se construye el complemento, es decir, se buscan los términos que all´ı faltan para totalizar la forma normal conjuntiva completa. Hallar la forma normal conjuntiva para la función f = xyz + xyz 0 + xy 0 z + xy 0 z 0 + x0 y 0 z 0 h 0 0 i 0 f0 = xyz + xyz 0 + xy 0 z + xy 0 z 0 + x0 y 0 z 0 0 0 = x + y 0 + z 0 . x0 + y 0 + z . x0 + y + z 0 . x0 + y + z . (x + y + z) = x + y0 + z0 . x + y0 + z . x + y + z0

Lero y Jose

80

Amaury Camargo B

4.4


4


Ejercicios Propuestos 1. Simplificar las siguientes expresiones Booleanas: a) (x + y) (x0 + y) b) (x + xy + xyz) (x + y + z) c) (xy 0 + x0 y)0 . (xy + x0 y 0 )0 d ) (yz + xuw) (yz + x0 + u0 + w0 ) e) xyz + xy 0 z + x0 yzx f ) (x + y + z + x0 y 0 z 0 ) . (yz + yz 0 + y 0 z) g) (yz + y 0 z 0 + yz 0 )0 [(y 0 + z 0 ) (y + z 0 )]0 h) xy + x0 z + yz i ) (x + y) (x0 + z) (y + z) 2. Escribir cada una de las siguientes expresiones en la forma normal disyuntiva con el menor n´ umero posible de variables: a) (x + y 0 ) (y + z 0 ) (z + x0 ) (x0 + y 0 ) b) (x + y 0 ) (y + z) (y + z 0 ) c) x0 yz + xy 0 z + x0 yz 0 + x0 y 0 z + xyz 0 + x0 y 0 z 0 3. Escribir cada una de las siguientes expresiones en la forma normal conjuntiva con el menor n´ umero posible de variables: a) (x + y 0 ) (y + z 0 ) (z + x0 ) (x0 + y 0 ) b) (x + y 0 ) (y + z) (y + z 0 ) c) x0 yz + xy 0 z + x0 yz 0 + x0 y 0 z + xyz 0 + x0 y 0 z 0 4. Simplificar las siguientes expresiones mediante la ley de D’Morgan: a) (x0 yz 0 )0 b) (x0 + y 0 z)0 0 c) xy (zw)0 0 d ) x (y + z 0 )0 w e) [(x + y 0 ) (x0 + y)]0 n 0 o0 f) (xy)0 z w

Lero y Jose

81

Amaury Camargo B

4.4


4


5. Para cada una de las siguientes expresiones construir el circuito lógico correspondiente: 1) Utilizando compuertas AN D y OR. 2) Utilizando compuertas N AN D y N OR. Use inversores si es necesario: a) f = [xy (z + w)]0 b) g = (x + y + z 0 wu0 )0 + y 0 zw0 c) h = (x + y)0 + z 0 w d ) i = (x + zw0 )0 e) j = xy (z + y 0 )

Lero y Jose

82

Amaury Camargo B

5

5.

´ COMPUERTAS LOGICAS

Compuertas L´ ogicas

El álgebra Booleana es el soporte te´ orico del álgebra de los circuitos lógicos, lo cual se ajusta a la teor´ıa del álgebra Booleana como un ´ algebra con dos elementos, el 0 y el 1. Esto significa que, excepto por la terminolog´ıa y su significado en los circuitos, es idéntica al álgebra de proposiciones considerada como un sistema abstracto. El ´ algebra de circuitos utiliza dispositivos de dos estados; el ejemplo más simple de tales dispositivos es un interruptor o o (switch). Otros dispositivos de dos estados utilizan dos en circuitos l´ ogicos son diodos rectificadores, bobinas magnéticas, transistores. La naturaleza de los estados var´ıa con el dispositivo: conducción, contra no-conducción, cerrado contra abierto, cargada contra descargada, magnetizada contra desmagnetizada, alto voltaje contra bajo voltaje. Dos problemas que surgen con las aplicaciones del álgebra Booleana en los circuitos lógicos son: Simplificaci´ on de un circuito dado que tenga determinadas propiedades. El dise˜ no de circuitos l´ ogicos que tengan propiedades dadas. El problema de dise˜ nar un circuito que tenga propiedades dadas es exactamente el de encontrar la proposición o función Booleana asociada a una tabla de verdad dada. Las tres compuertas fundamentales ya mencionadas (AND, OR, NOT) son suficientes para escribir cualquier ecuaci´ on Booleana. Toda función lógica puede expresarse con la combinación de estas tres compuertas. Sin embargo, se utilizan otras cuatro compuertas lógicas: NAND, NOR, XOR y XNOR.

5.1.

Compuerta NAND

La compuerta (NOT NAND), denominada también operaci´ on de Sheffer, es la negación de una compuerta AND y se define: x NAND y = (xy)0 . El s´ımbolo para la compuerta NAND es: La tabla de verdad es:

5.2.

x

y

AND xy 0

NAND (xy)0

0 0 1 1

0 1 0 1

0 0 0 1

1 1 1 0

Compuerta NOR

La compuerta (NOT OR), denominada también operaci´ on de Pierce, es la negación de una compuerta OR y se define: x NOR y = (x + y)0 .

Lero y Jose

83

Amaury Camargo B

5.3

Compuerta XOR

5


El s´ımbolo para la compuerta NOR es: La tabla de verdad es:

5.3.

x

y

OR x + y

NOR (x + y)0

0 0 1 1

0 1 0 1

0 1 1 1

1 0 0 0

Compuerta XOR

Corresponde a la operaci´ on l´ ogica disyunción exclusiva (x ⊕ y) y a la operación entre conjuntos denominada diferencia simétrica. Para designar esta disyunción exclusiva o suma exclusiva se emplea el s´ımbolo ⊕: f (x, y) = x ⊕ y = xy 0 + x0 y. El s´ımbolo para la compuerta XOR es:

5.3.1.

Compuerta XNOR

La compuerta XNOR es la negaci´ on de una compuerta XOR. Su s´ımbolo es:

La tabla de verdad para las compuertas XOR y XNOR es: x

y

XOR x ⊕ y

XNOR (x ⊕ y)0

0 0 1 1

0 1 0 1

0 1 1 0

1 0 0 1

Debe notarse que la tabla de verdad de la compuerta XNOR es exactamente igual a la tabla de verdad de la equivalencia; por ello, esta compuerta recibe el nombre de “comparador”. Si la expresión para la compuerta XOR es: x ⊕ y = xy 0 + x0 y. Su complemento, la compuerta XNOR, ser´ıa: 0 (x ⊕ y)0 = xy 0 + x0 y .

Lero y Jose

84

Amaury Camargo B

5.3

Compuerta XOR

5


Para hallar este complemento se procede as´ı: 0 0 (x ⊕ y)0 = xy 0 . x0 y {Ley de D’Morgan} 0 = x + y . x + y 0 {Ley de D’Morgan} = x0 + y .x + x0 + y .y 0 P2 = xx0 + xy + x0 y 0 + yy 0 P2 = 0 + xy + x0 y 0 + 0 P4 = xy + x0 y 0 P3 Esta u ´ltima expresi´ on es la funci´ on Booleana que establece la equivalencia entre x, y, por tanto: (x ⇔ y) = (x ⊕ y)0 , se concluye que una equivalencia l´ ogica puede representarse mediante una compuerta XNOR. Escribir la funci´ on f = (xy 0 + xz)0 en forma normal disyuntiva, simplificarla y dibujar el circuito l´ ogico 0 f = xy 0 + xz + xx0 0 = x y 0 + z + x0 = x0 + xyz 0 = x0 y + y 0

z + z 0 + xyz 0

= x0 yz + x0 yz 0 + x0 y 0 z + x0 y 0 z 0 + xyz 0 El mapa K correspondiente es: itbpF 4,1433in1,7461in0inF igure La función Booleana simplificada es f = yz 0 + x0 . Para dise˜ nar el circuito l´ ogico correspondiente, no sólo para este ejemplo sino para todos los circuitos, se emplea un “bus” de variables de entrada y sus negaciones (la l´ınea que sale de la bolita es la negaci´ on de la variable correspondiente), as´ı: La simplificaci´ on de la ecuaci´ on Booleana es importante desde el punto de vista económico y por la reducción de los circuitos l´ ogicos, para hacerlos más simples y compactos. Un hecho que ha permitido dicha simplificaci´ on es la existencia de conjuntos funcionalmente completos de conectivos: {∼ ∧} y {∼ ∨} que pueden ser escritos y representados as´ı:

Esta propiedad origin´ o dos formas de dise˜ nar los circuitos lógicos, utilizando sólo compuertas NAND o sólo compuertas NOR, las cuales han sido denominadas t´ ecnicas NAND y NOR, respectivamente; tales técnicas han sido impuestas por las consideraciones constructivas, puesto que es más eficiente la fabricación en serie y automatizada de circuitos integrados y chips que sólo usan una clase de compuerta. La tabla siguiente muestra las equivalencias entre una y otra técnica. Dada la siguiente expresi´ on Booleana f = x0 y + x0 y 0 , implementar el circuito lógico correspondiente utilizando: Lero y Jose

85

Amaury Camargo B

5.3

Compuerta XOR

5


1. Técnica NAND. 2. Técnica NOR. Soluci´ on: 1. f = x0 y + x0 y 0 h 0 0 i0 f0 = x0 y + x0 y 0 h 0 0 i 0 f = x0 y . x0 y 0

(∗)

La anterior es la expresi´ on que implementa el circuito mediante la técnica NAND, as´ı:

2. A partir de la expresi´ on (∗), se obtiene: f

f

f 0 0

0 x + y 0 . (x + y) 0 = x + y 0 + (x + y)0 h i0 0 0 0 0 = x + y + (x + y)

=

Esta u ´ltima expresi´ on se implementa mediante técnica NOR, as´ı:

Otro recurso empleado para la simplificación de expresiones Booleanas es la consideración de condiciones “no importa” (don’t care) producidas por términos irrelevantes en la expresión, que resultan de aquellas combinaciones de los valores l´ ogicos de las variables no requeridas para la solución de un determinado problema. Estos términos, simbolizados por x en el mapa K, pueden ser utilizados para conformar adyacencias que producen notorias simplificaciones, como se verá en el ejemplo siguiente. Simplificar el siguiente mapa K, utilizando los términos irrelevantes (x). La función Booleana simplificada considerando la adyacencia es xw, mientras que sin considerar los términos irrelevantes (don’t care) es xyz 0 w. itbpF 4,395in2,981in0inF igure f

= xyz 0 w

f

= xw

Encontrar la funci´ on Booleana simplificada en las forma normal conjuntiva y disyuntiva asociada al siguiente mapa K. itbpF 4,3111in2,8444in0inF igure Lero y Jose

86

Amaury Camargo B

5.3

Compuerta XOR

5


Para la forma normal conjuntiva se consideran los ceros (0) y se tiene en cuenta que las variables consideradas se deben tomar complementadas, as´ı: f (x, y, z, w) = y 0 + w x0 + y 0 Para la forma normal disyuntiva se consideran los unos (1) . f (x, y, z, w) = y 0 + x0 w Al aplicar la ley distributiva de + sobre . se puede ver que las dos expresiones son equivalentes.

Lero y Jose

87

Amaury Camargo B

Logica-matematica 6g6l6a

Overview 4q3b3c

More details 26j3b

More Documents from "Amaury" 3s1822

2c82t

2c82t

2c82t

Logica-matematica 6g6l6a

Pensamiento Aleman Siglo Xix 5p6y62

2c82t