algebra y logica algebra i apuntes

88
1 ÁLGEBRA Y LÓGICA ÁLGEBRA I APUNTES DE CLASE Escritos por la Profesora Nora Andrada

Upload: pitercantropus

Post on 27-Dec-2015

136 views

Category:

Documents


8 download

TRANSCRIPT

Page 1: Algebra y Logica Algebra i Apuntes

1

ÁLGEBRA Y LÓGICA ÁLGEBRA I

APUNTES DE CLASE

Escritos por la Profesora Nora Andrada

Page 2: Algebra y Logica Algebra i Apuntes

2

Temas

• El Cálculo Proposicional

• Álgebra de Conjuntos

• Combinatoria

• Números Enteros

• Números Complejos

• Polinomios

Page 3: Algebra y Logica Algebra i Apuntes

3

EL CÁLCULO PROPOSICIONAL

Introducción

En la vida diaria, y en el desarrollo de cualquier ciencia deductiva, por ejemplo las matemáticas, se utilizan ciertas construcciones gramaticales denominadas enunciados o proposiciones, es decir una oración declarativa que es verdadera o falsa, por ejemplo: (a) 2+2=4 (b) Todos los hombres son mortales. (c) La vida es hermosa. (d) Existen infinitos enteros primos. Algunas de estas afirmaciones se consideran a veces válidas a priori, es decir sin demostración previa, y son los denominados axiomas : Por un punto exterior a una recta pasa una y sólo una paralela, es un axioma de la geometría euclideana. Es decir, entendemos por una proposición a una sentencia del lenguaje que es verdadera (V) o falsa (F). La verdad o falsedad de una proposición es su valor de verdad. Denotaremos la proposiciones con las letras P , Q , R, etc. Naturalmente, nosotros estamos más interesados en proposiciones como la de los ejemplos (a) y (d) , que corresponden al terreno de las matemáticas, si bien (b) y (c) son ejemplos legítimos de proposiciones. Podría argüirse que (c) no es exactamente una proposición en virtud de que su validez depende de una interpretación individual. Pero nuestro objetivo aquí es sintáctico, es decir cómo obtener nuevas proposiciones a partir de otras proposiciones. Las proposiciones pueden ser combinadas entre ellas formando proposiciones compuestas, mediante nexos llamados conectivos lógicos. En este sentido las proposiciones: Si la vida es hermosa entonces 2+2 = 4. Si Juan tiene 16 años, entonces no terminó el secundario. se obtienen combinando otras proposiciones mediante un formato común que se puede sintetizar: ''Si P entonces Q '' En una ciencia deductiva, la verdad o falsedad de ciertas proposiciones permite hacer inferencias o tomar decisiones posteriores. “Si todo hombre es mortal y Sócrates es hombre, entonces Sócrates es mortal”, es una inferencia típicamente filosófica. “Si es ab>0 entonces debe ser a>0 y b>0, o debe ser a<0 y b<0” , es una inferencia típicamente matemática. “Si c>0 y x<1 entonces continuar el procedimiento, si c=0 o si 1<x entonces finalizar el procedimiento”, es una instrucción típica de un programa de computación. El cálculo proposicional es un método algebraico de cálculo con proposiciones, donde los valores de verdad de ciertas proposiciones llamadas compuestas se deducen de los valores de verdad de otras proposiciones más simples. En este sentido, para construir dicho cálculo PROPOSICIONAL, sólo estamos interesados en los dos posibles valores de verdad: V , F que puede tomar ciertas proposiciones P,

Page 4: Algebra y Logica Algebra i Apuntes

4

Q, R , ect. que intervienen en una determinada construcción. Entonces, si consideramos a P, Q, R como variables que toman los valores en Γ = {V , F }, podemos definir operaciones entre estas variables. Estas operaciones pueden ser 1-arias , 2-arias, 3-arias, etc. Nosotros sólo definiremos una operación 1-aria (unaria) y todas las 2-arias (binarias). Negación lógica: Esta es una operación 1-aria, que consiste en, dada un proposición P negar lo que ella afirma. Obtenemos así una nueva proposición que indicaremos ∼P. Es claro que si P es verdadera ∼P será falsa. La siguiente Tabla define ∼P , la negación de P:

P ∼P F V V F

Ahora definiremos las operaciones binarias. Si llamamos Γ = {V , F }, hay 4 elementos en Γ x Γ, a saber (F,F), (F,V), (V,F) y (V,V) . Cualquier función de Γ x Γ en Γ debe asignar un valor, o F o V , a cada uno de esos elementos. Como a cada uno de esos cuatro elementos se le puede asignar uno de los dos valores F o V, hay 16 posibles funciones de Γ x Γ en Γ. En la siguiente tabla mostramos todas las funciones posibles:

P Q 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 F F F F F F F F F F V V V V V V V V F V F F F F V V V V F F F F V V V V V F F F V V F F V V F F V V F F V V V V F V F V F V F V F V F V F V F V

Tabla 1

En la Tabla 1 están representadas todas las asignaciones posibles de valores de verdad para dos argumentos P y Q, luego, no importa cuan compleja sea una proposición construida a partir de dos proposiciones básicas, siempre será posible calcular su valor de verdad, si podemos verificar leyes. Observando esta Tabla encontramos la representación para las operaciones o conectivos que queremos definir. Columna 1: Conjunción lógica: responde a “ P y Q “ . Intuitivamente es claro que esta nueva proposición es cierta o verdadera sí, y sólo sí, tanto P como Q son verdaderas. Definimos entonces la conjunción de P y Q , que indicaremos P∧Q , mediante la siguiente tabla:

P Q P∧Q F F F F V F V F F V V V

Page 5: Algebra y Logica Algebra i Apuntes

5

Columna 7: Disyunción Lógica : Es una operación binaria que corresponde a la expresión “P o Q “, pensando la palabra “o” en sentido incluyente, lo cual significa que “ P o Q “ es verdadera si P es verdadera o Q es verdadera o ambas lo son. La siguiente Tabla define entonces la disyunción P o Q , que indicaremos P∨Q :

P Q P∨Q F F F F V V V F V V V V

Columna 6: Inequivalencia Lógica: esta operación binaria corresponde al “ o “ excluyente , el nombre de inequivalencia responde al hecho de que la proposición compuesta “ P o Q “ tiene valor de verdad V cuando P y Q tienen valores de verdad distintos, y F cuando tienen el mismo valor de verdad. La siguiente tabla define entonces la inequivalencia, que indicaremos P ∨ Q

P Q P ∨ Q F F F F V V V F V V V F

Se observa también que P está representada en la columna 3 , ∼P en la columna 12 , Q en la columna 5 y ∼Q en la columna 10. La columna 15 es universalmente verdadero y la columna 0 universalmente falsos . En general, dada una columna n de la Tabla, la columna 15 - n , corresponde a su negación. Así: la columna 7 representa la disyunción (P∨Q) y la columna 8, su negación ( ni ). Columna 13: esta una nueva operación entre proposiciones, la llamamos condicional o implicación e indicamos P→Q. que responde a la expresión “si P entonces Q” o “P implica Q”. La tabla de valor de verdad del condicional, es:

P Q P →Q F F V F V V V F F V V V

La columna 15 - 13 = 2 representa la negación de” P implica Q “.

Page 6: Algebra y Logica Algebra i Apuntes

6

De igual modo, la columna 9 responde a la expresión “ P si y sólo si Q”, operación que denominamos bicondicional o equivalencia, e indicamosP Q↔ . Luego la tabla de valor de verdad de esta operación es:

P Q P Q↔ F F V F V F V F F V V V

La columna 15-9 = 6 representa la negación de “P si, y sólo si Q”, que no es sino la inequivalencia. Observemos que la columna 11 representa la operación Q P→ .

POLINOMIOS BOOLEANOS Las sumas, productos y diferencias de variables x y z, , ,..., bajo las reglas usuales del álgebra ordinaria, constituyen los Polinomios en esas variables. Por ejemplo: f (x, y) = x.x.y + x.y.y - y.y.y = x2y + x y2 - y3

Si en ese polinomio se reemplaza cada una de las variables por números reales x0, y0 ,... , la expresión f(x0, y0 ) es ella misma un número real. De igual modo, si P, Q, R, ... son variables proposicionales, combinando estas variables con los conectivos ∧, ∨, ~, →, ↔ , se obtienen expresiones llamadas Polinomios Booleanos. Ejemplo: A (P, Q ) = (P ∧ Q ) ∨ (~P ) B ( P, Q, R ) = ( P∨ Q ) → R son polinomios booleanos en dos y tres variables, respectivamente. También puede operarse con polinomios booleanos, de modo que puede hablarse de conjunción, negación, disyunción, etc., de polinomios booleanos. Ejemplo: A (P, Q) ∧ B ( P, Q, R ) = [(P ∧ Q ) ∨ (~P )] ∧ [ ( P∨ Q ) → R ] Reemplazando las variables P, Q, R, ... de un polinomio booleano A (P, Q, R, ...) por valores particulares P0, Q0, R0 ,. . . la expresión A (P0, Q0, R0, ...) tiene valor F o V, luego es ella misma una proposición. Ejemplo: A (P, Q) = ~(P ∧ ~ Q ) Sean P0 = 2 x es impar. y Q0 = 3 es un número primo. “no es cierto que 2x es par y 3 no es un número primo” resulta verdadera.

Page 7: Algebra y Logica Algebra i Apuntes

7

Sean P0, Q0, R0, ... proposiciones particulares cuyo valor de verdad coinciden, respectivamente con los de las proposiciones P1, Q1, R1, ..., entonces A (P0, Q0, R0, ...) tiene el mismo valor de verdad que A (P1, Q1, R1, ...). Por ello, el valor de verdad de un Polinomio Booleano evaluado sobre enunciados particulares depende sólo de los valores de verdad de los enunciados y no de los enunciados mismos. Así hablamos del valor de verdad de cada una de las variables P, Q, R, ... y del valor de verdad del Polinomio. El modo de determinar el valor de verdad de un Polinomio Booleano es a través de los valores de verdad de las variables que lo integran, mediante la construcción de una Tabla de valor de verdad. Ejemplo: A (P, Q, R ) = (P∧ Q ) → [ ( ~Q ∧P) ∨ R ] P Q R P∧ Q ~Q ~Q ∧P (~Q ∧P) ∨ R (P∧ Q ) → [ ( ~Q ∧P) ∨ R ] F F F F V F F V F F V F V F V V F V F F F F F V F V V F F F V V V F F F V V V V V F V F V V V V V V F V F F F F V V V V F F V V

En la columna final se dan los valores de verdad para el Polinomio booleano dado. Una Tabla de Valor de Verdad es, entonces, un cuadro que muestra el valor de verdad de un polinomio booleano para cada valor de veradd de las proposiciones componenetes. Definición: Si para toda asignación de valores de verdad de sus variables, un polinomio booleano tiene valor V, entonces diremos que ese polinomio es una tautología. Definición: de igual modo, si para todo asignación de valores de verdad de sus variables, un polinomio booleano tiene valor de verdad F, diremos que es una contradicción. Observemos entonces que si un polinomio booleano A (P, Q, R, ...) es una tautología, entonces ~ A (P, Q, R, ...), es una contradicción. Equivalencia lógica y Consecuencia lógica Definición: Dos polinomios booleanos en las variables P, Q, R, ...; A (P, Q, R, ...) B ( P, Q, R ), son lógicamente equivalentes si y sólo si tienen la misma tabla de valor de verdad. Indicaremos A ≡ B. Que dos polinomios booleanos sean equivalentes no significa que sean la misma cosa. Por ejemplo: “Si hoy es lunes entonces tengo clase”, y “Si x es par, entonces x es

Page 8: Algebra y Logica Algebra i Apuntes

8

divisible por dos”. Ambas expresiones tienen la misma forma lógica ( P ⊃ Q) y son lógicamente equivalentes. Teorema: Un polinomio booleano A(P, Q,...) es equivalente a otro B(P, Q,...) si y sólo si al establecer el bicondicional entre ellos se obtiene una tautología. Esto es, A ≡ B si y sólo si A(P, Q,...) ⇔ B(P, Q,...) es tautología. Demostración: supongamos que A(P, Q,...) ⇔ B(P, Q,...) es tautología, entonces, para todo valor de verdad de las variables P, Q, .. , A(P, Q,...) ⇔ B(P, Q,...) es siempre V. Esto significa que si A es V, debe ser B también V, y si A es F, debe ser el valor de verdad de B también F. Luego ambos tienen la misma tabla de valor de verdad y, por lo tanto, son equivalentes. Recíprocamente: supongamos que A ≡ B , esto significa que ambos polinomios tienen la misma tabla de valor de verdad. Consideremos un asignación particular para las variables de A y supongamos que A(P0, Q0,...) es V, entonces B (P0, Q0,...) debe ser V, luego A⇔B es V, pues ambos lo son. De igual modo, si A(P0, Q0,...) es F, debe ser B (P0, Q0,...) también F por tener la misma tabla de valor e verdad, luego A⇔B es V. Resulta entonces que A⇔B es tautológico. Propiedades de los conectivos lógicos

Mediante la equivalencia lógica, pueden expresarse las más importantes propiedades de los conectivos lógicos y leyes del cálculo proposicional, demostrables por las Tablas de Valor de Verdad correspondientes. En la siguiente Tabla se resumen las propiedades del Álgebra de Proposiciones:

LEYES DEL ÁLGEBRA DE PROPOSICIONES

Leyes de Idempotencia 1a. P∨P ≡ P 1b. P∧P ≡ P

Leyes Asociativas 2a. (P ∨Q )∨ R ≡ P∨ (Q∨ R) 2b. (P∧Q) ∧ R ≡ P∧(Q∧R)

Leyes Conmutativas 3a. P∨Q ≡ Q ∨ P 3b. P∧Q ≡ Q ∧ P

Leyes Distributivas 4a. P∨(Q∧R) ≡ (P∨Q) ∧ (P∨Q) 4b. P∧(Q∨R) ≡ (P∧Q)∨(P∧R)

Leyes de Identidad 5a. P∨F ≡ P 5b. P∧V ≡ P 6a. P∨ V ≡ V 6b. P ∧ F ≡ F

Leyes del Complemento 7a. P ∨ ∼P ≡ V 7b. P∧ ∼P ≡ F

Page 9: Algebra y Logica Algebra i Apuntes

9

8a. ∼∼P ≡ P 8b. ∼V ≡ F , ∼F ≡ V

Leyes de De Morgan 9a. ∼(P∨Q) ≡ ∼P ∧ ∼Q 9b. ∼(P∧Q) ≡ ∼P ∨ ∼Q A título de ejemplo, consideremos la siguiente propiedad de la Conjunción: Propiedad Distributiva respecto de la disyunción: P ∧(Q ∨ R) ≡ (P∧Q) ∨ (P ∧R )

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

Como se observa, el bicondicional establecido entre P ∧(Q ∨ R) y (P∧Q) ∨ (P ∧R ) resulta tautológico, luego P ∧(Q ∨ R) ≡ (P∧Q) ∨ (P ∧R ). Consecuencia o implicación lógica Definición: Diremos que A (P, Q, R, ...) implica lógicamente a B ( P, Q, R,...), o que B ( P, Q, R,...) es consecuencia lógica de A (P, Q, R, ...), si para toda asignación de valores P0, Q0,... tales que A(P0, Q0,...) es V, resulta también que B (P0, Q0,...) es V. Indicaremos A (P, Q, R, ...) ⇒ B ( P, Q, R,...), para indicar que el polinomio booleano A implica lógicamente a B, o que B es consecuencia lógica de A. Teorema: Un polinomio booleano A (P, Q, R, ...) implica formalmente el polinomio booleano B ( P, Q, R,...) si y sólo si A → B es una tautología. Demostración: supongamos que A (P, Q, R, ...) → B ( P, Q, R,...) es tautológico, entonces para todo valor de verdad de las variables P, Q, R,.. , A (P, Q, R, ...) → B ( P, Q, R,...) es verdadero. Luego, si A (P, Q, R, ...) es V, debe ser también V el valor de verdad de B ( P, Q, R,...), así resulta A (P, Q, R, ...) ⇒ B ( P, Q, R,...) , esto es, B es consecuencia lógica de A. Recíprocamente: supongamos que B es consecuencia lógica de A, esto es A ⇒ B, lo que significa que para toda asignación de valores de las variables de A, toda vez que A tiene valor de verdad V, B también tiene valor de verdad V. Entonces resulta A → B (por definición de → ).

Page 10: Algebra y Logica Algebra i Apuntes

10

Puede generalizarse el concepto del teorema anterior, reemplazando el polinomio A (P, Q, R, ...) por A1 ∧ A2 ∧...∧ An , con Ai polinomios booleanos en varias variables, para todo subíndice i = 1, 2, ..,n. Así: A1 ∧ A2 ∧...∧ An ⇒ B si y sólo si siempre que A1 ∧ A2 ∧...∧ An sean todos V, es B también cierta.

Page 11: Algebra y Logica Algebra i Apuntes

11

q p (~p→ ~q)

Page 12: Algebra y Logica Algebra i Apuntes

12

Page 13: Algebra y Logica Algebra i Apuntes

13

Page 14: Algebra y Logica Algebra i Apuntes

14

M.T por M.T

Page 15: Algebra y Logica Algebra i Apuntes

15

Page 16: Algebra y Logica Algebra i Apuntes

16

CUANTIFICADORES

Funciones proposicionales o funciones lógicas: Sea A un conjunto cualquiera, explícita o implícitamente dado. Una función proposicional sobre A es una expresión que denotamos por P(x), que tiene la propiedad de que P(a) es Verdadera o Falsa para todo elemento a ∈ A. Esto es, P(x) es una función proposicional sobre A si al reemplazar la variable x por un elemento a ∈ A, se convierte en proposición. Ejemplo: P(x) : “x es un número primo” P(x) es una función proposicional sobre Z. Así, 8∈ Z , entonces P(8): “8 es un número primo” es una proposición P. En este caso el valor de verdad de P es F. Si P(x) es una función proposicional sobre un conjunto A, entonces el conjunto de elementos a ∈ A, tales que P(a) es verdadera, se llama Conjunto de validez de P(x), que indicaremos VP. VP = {x / x ∈ A, P(x) es verdadera} VP = {x / P(x)} Ejemplo 1: sea P(x): “ x + 2 < 7” está definida en N entonces VP = {x ∈N / x + 2< 7 } VP = { 1, 2, 3, 4, 5, 6 } es su conjunto de validez. Ejemplo 2: sea P(x): “x + 5 < 2” definida sobre N. Entonces su VP = { x ∈ N / x + 5 < 2 } = ∅ Como se ve, el conjunto de validez de P(x), definida sobre A, puede ser todo A, algunos elementos de A o ningún elemento de A. Cuantificador Universal: Sea P(x) una función proposicional sobre un conjunto A. Entonces, anteponiendo a P(x) la expresión “para todo elemento de A”, obtenemos la proposición: “para todo x en A, P(x) es verdadero” Simbólicamente: ∀ x∈A, P(x) o ∀x, P(x) y se lee “para todo x en A se verifica P(x). ∀∀∀∀ es el Cuantificador Universal. La expresión ∀x, P(x), significa en definitiva que el conjunto de validez de P(x) es todo A: VP = {x / P(x)} = A Obsérvese que P(x) es una función proposicional y no tiene valor de verdad. En cambio, precediéndola de ∀: ∀x, P(x) es una proposición y por lo tanto tiene un valor de verdad. Si {x / x∈ A, P(x)} = A , entonces ∀x, P(x) es V. Si {x / x∈ A, P(x)} ≠ A , entonces ∀x, P(x) es F.

Page 17: Algebra y Logica Algebra i Apuntes

17

Cuantificador existencial: De modo equivalente, si a P(x) le anteponemos la expresión “existe un x en A”, resulta: “existe un x en A tal que P(x) se verifica” o “para algún x, P(x)” En símbolos: ∃ x ∈ A, P(x) . ∃∃∃∃ se lee “existe” y se denomina cuantificador existencial. Si P(x): x + 4 ≤ 7 definida sobre N, entonces ∃ x en N tal que P(x) ó “∃ x ∈N, tal que x + 4 ≤ 7” es un proposición V. Si {x / x ∈ A, P(x) } ≠ φ entonces ∃ x ∈A, P(x) es V. Si {x / P(x) }= φ entonces ∃ x ∈A, P(x) es F. En el ejemplo: {x / x + 4 ≤ 7} = {1, 2, 3 }, luego ∃ x ∈N tal que P(x) es verdadero.

Page 18: Algebra y Logica Algebra i Apuntes

18

ÁLGEBRA DE CONJUNTOS

Ante la seguridad de que el tema de conjuntos ya es conocido, recordaremos aquí los conceptos básicos para su aplicación y relación con el Cálculo Proposicional.

Conjuntos - Introducción Intuitivamente podríamos decir que un conjunto es una clase bien definida de objetos. El concepto “bien definido” significa que cualquiera sea el objeto considerado, se puede determinar si está o no en el conjunto dado.

Los elementos que están en el conjunto se llaman elementos del conjunto, y se dice que pertenecen al conjunto. Así, si a es un objeto que está en el conjunto A, escribiremos a∈A (y se lee a pertenece a A ) y en caso contrario a∉A (y se lee a no pertenece a A).

Un conjunto puede definirse enumerando los objetos que lo forman, como por ejemplo:

A = { 1, 2, 3, 4, 5, 6} B = { 3, 5, 7}

En este caso se dice que el conjunto se ha definido por extensión. Solo los conjuntos finitos pueden definirse por extensión.

Otra forma de definir un conjunto es indicando la propiedad que caracteriza los objetos que están en él, esto es los elementos que lo forman. Por ejemplo:

C = { x / x es número entero primo} D = { x / x es número real tal que x2 + 4 x -1 = 0 }

En ente caso decimos que el conjunto ha sido definido por comprensión.

Por lo ya visto, la expresión “ x es un número entero primo” es una función proposicional, por lo que podríamos simbolizarla por P(x). Así C = {x/ P(x)}. En general los conjuntos definidos por comprensión quedan caracterizados a través de una función proposicional. Recíprocamente, dada una función proposicional Q(x) queda determinado un conjunto A={x/ Q(x)}. Entonces a∈A es equivalente a decir Q(a), esto es a∈A es verdadero es equivalente a decir Q(a) es proposición verdadera.

Igualdad de conjuntos Dos conjuntos son iguales cuando tienen los mismos elementos, es decir A = B, si

para todo x, x∈ A es equivalente a x∈ B.

Inclusión Sean A y B dos conjuntos, diremos que A está incluido en B, o que A es subconjunto de B, si todo elemento de A lo es también de B. Esto es, A está incluido en B si ∀x∈A entonces x∈B. Simbólicamente escribiremos A⊂B para indicar que el conjunto A está incluido en el conjunto B.

Así, siendo B y C los conjuntos arriba definidos: B⊂ C.

Si un conjunto A está incluído en otro B, diremos que A es un subconjunto de B.

Page 19: Algebra y Logica Algebra i Apuntes

19

Observación: algunos autores definen la igualdad de conjuntos de la siguiente manera:

A = B si A⊂B y B⊂A.

Otra observación: todo conjunto es subconjunto de si mismo, ya que siempre que x∈A, entonces x∈A.

Algunos conjuntos especiales Como los elementos que pueden estar en un conjunto pueden ser de cualquier tipo, es oportuno introducir un conjunto universal. Habitualmente se trabaja con subconjuntos de un conjunto al que llamaremos referencial o conjunto universal e indicaremos simbólicamente con U. Un conjunto universal U no contiene todo, sino que es el universo del discurso en un momento determinado.

Así, observando los conjuntos A, B, C y D definidos en los ejemplos anteriores, vemos que los elementos de todos ellos son números reales, esto es, el conjunto universal es entonces U = R. En cambio, no podría considerarse para estos ejemplos, que U = N.

Sea A ={ x / x entero, 2 x = 7 }. Se observa que A no tiene ningún elemento, pues para todo valor de x, resulta 2x par y por lo tanto ≠ de 7.

Se ve entonces la necesidad de otro conjunto especial ∅, llamado Conjunto Vacío o Conjunto Nulo, que es el conjunto que no tiene elemento alguno. Podría caracterizarse como ∅ = {x / x ≠ x}.

OPERACIONES CON CONJUNTOS

Complementación Sea U un conjunto universal y A⊂ U, un conjunto cualquiera.

Definición : El complemento de A , indicado por A’, está definido por

A’ = { x / x ∈ U y x∉A}

Ejemplo: Sea U={ x / x número dígito } , A = { 2, 4, 6, 8, 10} , B={ 1, 6}

entonces A’ = { 1, 3, 5, 7, 9} , B’ = { 2, 3, 4, 5, 7, 8, 9, 10 }

Definición : Si A y B son conjuntos, el complemento relativo de A respecto de B es B-A = { x / x ∈ B y x∉ A }.

Si A = { x / x es un número entero primo} B= { x / x es número natural primo}

entonces A-B = { x / x es número primo negativo}.

Intersección Sea U un conjunto referencial y A⊂U , B⊂U ;llamaremos intersección de A con B al conjunto que denotaremos A ∩ B formado por los elementos comunes a ambos conjuntos, es decir:

Page 20: Algebra y Logica Algebra i Apuntes

20

A ∩ B = { x∈ U/ x∈A ∧ x∈B } Ejemplo: Si U = N , A ={ x / x es número natural / x ≤ 18 } y B = { x / x ∈ N , x es primo } entonces A ∩ B = {x∈ N/ x es un número primo ∧ x ≤ 18 } A ∩ B = { 2, 3, 5, 7, 11, 13, 17 } Si los conjuntos A y B están definidos por comprensión por las funciones proposicionales P(x) y Q(x), respectivamente, resulta que el conjunto A∩B está definido por la función proposicional P(x) ∧ Q(x). Es decir, si A={x∈U / P(x)}; B= {x ∈U / Q(x)} entonces A∩B= {x∈U / P(x) ∧ Q(x)} Esto muestra que relación existe entre la intersección de conjuntos y la disyunción, relación que permite probar las propiedades de la intersección mediante las propiedades de la disyunción. Si dos conjuntos no tienen elementos comunes, se dice que son disjuntos, entonces podemos dar la siguiente definición: A y B son disjuntos si A∩B = ∅. Unión Sea U un conjunto referencial y A⊂U, B⊂U; llamaremos unión de A con B al conjunto que denotaremos A∪B, formado por los elementos comunes y no comunes de ambos conjuntos, es decir: A∪B = {x∈U/ x∈A ∨ x∈B} Ejemplo: U = Z , A ={x∈U/ -2< x ≤ 7 } , B={ x∈U/ x es natural par ∧ x ≤ 12} Entonces A∪B ={ -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12} Si los conjuntos A y B están definidos por comprensión por las funciones proposicionales P(x) y Q(x), respectivamente, resulta que el conjunto A∪B está definido por comprensión por la función proposicional P(x) ∨ Q(x), es decir: Si A = { x∈U/P(x) } ; B= { x∈U/ Q(x) } entonces A∪B ={ x∈U/ P(x) ∨ Q(x)}. Como en la operación anterior, esto muestra una relación entre la unión y la conjunción, de modo que pueden probarse las propiedades de la primera mediante las propiedades de la segunda. Diferencia simétrica de conjuntos Sea U un conjunto referencial y A⊂U, B⊂U. Llamaremos diferencia simétrica de A con B al conjunto que denotaremos A∆B formado por los elementos de A o de B pero no de ambos, es decir: A∆B = { x∈U / x∈A ∨ x∈B } Ejemplo: Sea U = {x∈N/ x ≤ 12}, A = { x∈U/ x es par } , B={ x∈U/ x es múltiplo de 3}

Page 21: Algebra y Logica Algebra i Apuntes

21

Entonces A∆B = { x∈U /x es par ∨ x es múltiplo de 3} o también: A∆B = {2, 3, 4, 8, 9, 12} Si los conjuntos A, B están definidos como antes, por las funciones proposicionales P(x) y Q(x) respectivamente, entonces A∆B queda definido por la función proposicional P(x) ∨ Q(x). Si A = { x∈U/P(x) } ; B= { x∈U/ Q(x) } entonces A∆B ={ x∈U/ P(x) ∨ Q(x)}. La siguiente Tabla muestra las propiedades de las operaciones de conjuntos:

LEYES DEL ÁLGEBRA DE CONJUNTOS

Leyes de Idempotencia 1a. A∪A = A 1b. A∩A = A

Leyes Asociativas 2a. (A ∪B)∪C = A∪(B∪C) 2b. (A∩B)∩C = A∩(B∩C)

Leyes Conmutativas 3a. A∪B = B∪A 3b. A∩B = B ∩A

Leyes Distributivas 4a. A∪(B∩C) = (A∪B)∩(A∪C) 4b. A∩(B∪C) = (A∩B)∪(A∩C)

Leyes de Identidad 5a. A∪∅ = A 5b. A∩U = A 6a. A∪U = U 6b. A∩∅ = ∅

Leyes de Complemento 7a. A∪A’ = U 7b. A∩A’ = ∅ 8a. (A’)’ = A 8b. U’ = ∅ , ∅‘ = U

Leyes de De Morgan 9a. (A∪B)’ = A’ ∩B’ 9b. (A∩B)’ = A’ ∪B’ Observando la similitud de las leyes que son válidas en el Álgebra de Conjuntos y en el Álgebra de Proposiciones y considerando la siguiente correspondencia entre operaciones: Álgebra Proposiciones Álgebra de Conjuntos Negación Complementación Conjunción Intersección Disyunción Unión

Page 22: Algebra y Logica Algebra i Apuntes

22

analizamos la posibilidad de considerar una estructura abstracta con operaciones que verifiquen ciertos axiomas, de modo que cualquier propiedad válida para esta estructura, sea válida tanto para el Cálculo Proposicional como en el Álgebra de Conjuntos. En el cuadro siguiente se muestra el paralelismo entre las Leyes del Álgebra de Conjuntos y las del Cálculo Proposicional.

Leyes del Álgebra de Conjuntos

Leyes del Cálculo Proposicional

De Idempotencia

1.a- A∪A = A 1.b- A∩A = A

De Idempotencia

1.a- P∨P ≡ P 1.b- P∧P ≡ P

Asociativas

2.a- A∪(B∪C) = (A∪B)∪C 2.b- A∩(B∩C) = (A∩B)∩C

Asociativas

2.a- P∨(Q∨R) ≡ (P∨Q)∨R 2.b- P∧(Q∧R) ≡ (P∧Q)∧R

Conmutativas

3.a- A∪B = B∪A 3.b- A∩B = B∩A

Conmutativas

3.a- P∨Q ≡ Q∨P 3.b- P∧Q≡ Q∧P

Distributivas

4.a- A∪(B∩C) = (A∪B)∩(A∪C) 4.b- A∩(B∪C) = (A∩B)∪(A∩C)

Distributivas

4.a- P∨(Q∧R) ≡(P∨Q)∧(P∨R) 4.b- P∧(Q∨R) ≡ (P∧Q)∨(P∧R)

De Identidad

5.a- A∪∅ = A 5.b- A∩U = A

De Identidad

5.a- P ∨ F ≡ P 5.b- P∧ V ≡ P

6.a- A∪ U = U 6.b- A∩∅ = ∅

6.a- P∨ V ≡ V 6.b- P∧ F ≡ F

De Complemento

7.a- A∪A’ = U 7.b- A∩A’ = ∅

De Complemento

7.a- P∨ ∼P ≡ V 7.b- P∧ ∼P ≡ F

8.a- (A’)’ = A involución 8.b- U’ = ∅ ; ∅‘ = U

8.a- ∼(∼P) ≡ P involución 8.b- ∼ V ≡ F ; ∼F ≡ V

de De Morgan

9.a- (A ∪B)’ = A’ ∩ B’ 9.b- (A∩B)’ = A’ ∪ B’

de De Morgan

9.a- ∼(P∨Q) ≡ ∼P ∧ ∼Q 9.b- ∼(P∧Q) ≡ ∼P ∨ ∼Q

Page 23: Algebra y Logica Algebra i Apuntes

23

COMBINATORIA

Contar es hallar el cardinal de un conjunto. Si el conjunto es pequeño y sin regla de formación fija, el único procedimiento viable para contar sus elementos es hacer la enumeración de los mismos. Para contar las provincias argentinas, iré enumerándolas una a una: Jujuy, Salta, Misiones, . . . , Chubut, Tierra del Fuego. Las provincias son 24. Oralmente, la mayoría lo hará tocándose la punta de los dedos. Puede ser que los conjuntos a contar tengan muchos elementos para enumerarlos exhaustivamente. Pero si sus elementos obedecen a una regla de formación fija, pueden construirse artificios que permitan conocer cuantos son sin necesidad de hacer la lista. A menudo estos artificios son ingeniosos y poner de manifiesto la estructura del conjunto. La Combinatoria es la parte de la Matemática que estudia los problemas sobre cuántas combinaciones diferentes –sometidas o no a otras condiciones- se pueden formar con objetos dados. La Combinatoria surgió en el siglo XVI. En la vida de las capas sociales privilegiadas de entonces, ocupaban un lugar importante los juegos de azar: cartas, dados, loterías de lo más variadas. Es comprensible entonces que, al principio, los problemas combinatorios trataran fundamentalmente sobre juegos de azar, tratando de averiguar de cuántas maneras puede obtenerse un número determinado de puntos al arrojar dos o tres dados juntos, o de cuántas formas se pueden obtener dos reyes en un juego de cartas. Estos y otros problemas fueron la fuerza motriz del progreso de la Combinatoria y de la Teoría de Probabilidades, que se desarrolló paralelamente. Uno de los primeros en ocuparse del recuento del número de combinaciones diferentes en el juego de los dados fue el matemático italiano Tartaglia. El estudio teórico de los problemas combinatorios fue abordado en el siglo XVII por los científicos franceses Pascal y Fermat. La Combinatoria es el arte de contar sin hacer enumeraciones. Es contar “usando la cabeza en lugar de los dedos”. En este capítulo veremos algunos procedimientos para contar. Primer método para contar El primer método consiste en establecer una correspondencia biunívoca entre los elementos del conjunto en cuestión y un conjunto de la forma {1, 2, 3, …,n}, lo que permite afirmar que ambos conjuntos son coordinables; sabemos entonces que el cardinal del conjunto dado es n. Ejemplo 1: ¿Cuántos números enteros hay entre 3 y 25, incluidos ambos? Establecemos entonces la correspondencia: 3 4 5 . . . 24 25 ↓ ↓ ↓ ↓ ↓ 1 2 3 . . . 22 23 La función aplicada consiste en asignar a cada número del conjunto, el que se obtiene restándole 2.Luego hay 23 números. En forma general: si m ≤ n, el conjunto {m, m+1, m+2, . . ., n-1, n} de los enteros comprendidos entre m y n, ambos incluidos, se puede poner en correspondencia

Page 24: Algebra y Logica Algebra i Apuntes

24

con el conjunto {1, 2, 3, . . . , n-m+1} mediante la relación “restar m-1 unidades a cada elemento”. Entonces tenemos: m→ m-(m-1) = 1, m+1 → (m+1)-(m-1) = 2, . . . , n-1→ (n-1)-(m-1) = n-m, n → n-(m-1) = n-m+1 Así, entre m y n hay n-m+1 enteros, o, dicho de otra manera, el conjunto de los enteros {m, m+1, m+2, …, n} tiene n-m+1 elementos. Ejemplo 2: El cardinal del conjunto {-7, -6, -5, …, 10, 11} es 11-(-7) +1= 19 Aquí se podría haber enumerado los elementos del conjunto pues son pocos, pero en el caso de tener que determinar, por ejemplo, cuántos enteros hay entre 14.576 y 74.531, incluidos ambos, tendríamos: 74.531 - 14.576 + 1 = 59.956 Aquí se nota claramente la ventaja de tener un método general. Razonamientos equivalentes pueden emplearse en muchas situaciones similares. Ejemplo3: ¿Cuántos números pares hay entre 1 y 75? Aquí la relación posible de tomar es “divida cada elemento del conjunto por 2 y tome el cociente”: 2: 2 = 1 luego al 2 le asigno el 1 4 : 2 = 2 “ 4 → 2 6 : 2 = 3 “ 6 → 3 ….. 74 : 2 = 37 “ 74 → 37 Hay entonces 37 números pares entre 1 y 75. A veces no es tan evidente que transformación biyectiva usar. Ejemplo 4: En cada eliminatoria de un campeonato de tenis, se forma el número de parejas posible y, tras jugar el correspondiente partido, el ganador clasifica para la siguiente ronda y el perdedor, queda eliminado. Si en alguna de las instancias el número de jugadores es impar, uno de ellos (elegido de alguna manera, por ejemplo por sorteo) pasa directamente a la siguiente ronda sin jugar. ¿Cuántos partidos se jugarán en un campeonato con 37 inscriptos? Para simplificar el problema y poder esquematizar la situación, pensemos en que son sólo 9 los inscriptos. Así, el esquema de los partidos será: 1º Ronda: 321

* * 321

* * 321

* * 321

* * *

2º Ronda: 44 344 21 * * * 44 344 21 * *

3º Ronda: 44 344 21 * * *

4º Ronda : 44 344 21 * *

* ganador Luego, en la primera ronda se juegan 4 partidos, se eliminan 4 jugadores y pasan 5 a la ronda siguiente. En la segunda ronda se juegan 2 partidos, se eliminan 2 jugadores y pasan 3 a la siguiente. En la tercera ronda se juega un partido, se elimina 1 jugador y paran 2 a la final o cuarta ronda, en la que se juega el último partido en el que se elimina

Page 25: Algebra y Logica Algebra i Apuntes

25

1 jugador y queda el ganador. Así, habiendo 9 jugadores, se han jugado 9 – 1 = 8 partidos. Siguiendo el mismo esquema, al tener 37 jugadores inscriptos, se tendrá: 1º Ronda: se juegan 18 partidos, se eliminan 18 jugadores y pasan 19 a la siguiente. 2º Ronda: se juegan 9 partidos, se eliminan 9 jugadores y pasan 10 a la siguiente. 3º Ronda: se juegan 5 partidos, se eliminan 5 jugadores y pasan 5 a la 4º Ronda: se juegan 2 partidos, se eliminan 2 jugadores y pasan 3 a la 5º Ronda: se juega 1 partido, se elimina 1 jugador y pasan dos a la 6º Ronda: se juega 1 partido final, se elimina 1 jugador y resulta otro ganador. Entonces: 18 + 9 + 5 + 2 + 1 + 1 = 36 partidos jugados. Esto en realidad es también contar con los dedos pero, analicemos: . ¿para que se juega cada partido?

- Para eliminar 1 jugador. . Todo jugador es eliminado en algún partido, salvo el ganador. entonces: la transformación que a cada jugador le asigne el partido en el que fue eliminado, es una biyección. Luego hay que jugar tantos partidos como jugadores se pretende eliminar. En general: si hay n jugadores, se jugarán n-1 partidos. Segundo método para contar En ocasiones, el conjunto cuyo cardinal se quiere determinar no es coordinable con ningún conjunto de estructura más simple, ni está ordenado, ni puede ordenarse para facilitar el recuento, de modo que deberá escribirse exhaustivamente, elemento a elemento y luego contar. Ejemplo 5:¿Cuántos anagramas distintos (esto es palabras, tengan o no sentido) se pueden formar con las letras de la palabra TEMO, de modo que tengan 4 letras distintas y la primera sea vocal? Este sería el caso de escribirlas todas y contar, lo que no es muy inteligente. De cualquier manera, habría que hacerlo con mucho cuidado para no olvidar ninguna posibilidad. Esto obligaría a escribirlas siguiendo un orden o alguna regla que permita consignar todas las posible: 1) como deben comenzar con vocal, la 1º letra será E u O. Luego hay 2 posibilidades de elegirla : E _ _ _ O _ _ _ 2) como no se pueden repetir las letras, para las que comienzan con E habrá 3 posibilidades de elegir la segunda letra: E T _ _ , E M _ _ , E O _ _ 3) elegida la segunda letra, por ejemplo la T, para elegir la tercera quedan 2 posibilidades: E T M _ , E T O _ 4) elegida la tercera letra, queda sólo una posibilidad de elegir la última: E T M O , E T O M Luego hay 2 anagramas que comienzan con ET, de igual modo hay 2 que comienzan con EM, y hay otras 2 que comienzan con EO. Hay entonces 6 anagramas que comienzan con E. Razonando análogamente, resulta que hay 6 anagramas que comienzan con O, en total, hay 12 anagramas de cuatro letras distintas que pueden armarse con las letras de la palabra temo.

Page 26: Algebra y Logica Algebra i Apuntes

26

Este proceso de construir da la pauta para hacer el recuento de anagramas sin escribirlos todos. Todo consiste en recorrer mentalmente los pasos a seguir, anotando las bifurcaciones que se pueden elegir en cada paso:

dposibilida 1 :4 Paso

desposibilida 2 :3 Paso

desposibilida 3 :2 Paso

desposibilida 2:1 Paso

2 . 3 . 2 . 1 = 12 posibilidades

Esto obedece a la siguiente: Regla de la multiplicación: si un conjunto A tiene n elementos y el conjunto B tiene m elementos, el número de elecciones distintas de un elemento en A y otro en B en n.m.- En el caso de que el número de elecciones posibles en cada caso depende de qué elementos fueron elegidos antes, resulta cómodo representar el proceso de confección o armado de los distintos casos en forma de “árbol”. Primero se trazan, a partir de un punto, tantos segmentos como elecciones distintas se pueden hacer en el primer paso, así, cada segmento corresponde a un elemento. A partir del extremo de cada segmento, se trazan tantos segmentos como elecciones posibles hay para el segundo paso, si la primera vez fue elegido el elemento dado. Así se continúa hasta el último elemento dado. Como resultado de esta construcción resulta un árbol cuyo análisis da fácilmente en número de soluciones a nuestro problema. El diagrama de árbol correspondiente al problema anterior, es: M O T O M O T E M T O M T O T M M E T E M E T O M T E M T

E T M Ejemplo 5: ¿Cuántos números capicúas se pueden formar con 5 cifras significativas? La primera cifra la podemos elegir de 9 maneras distintas, ya que los números no podrán comenzar con cero. La segunda cifra puede elegirse de 10 maneras, lo mismo

Page 27: Algebra y Logica Algebra i Apuntes

27

que la tercera cifra, pero una vez elegida la segunda, hay una única manera de elegir la cuarta y lo mismo con la quinta cifra, ya que el número ha de ser capicúa, de modo que:

}-

9 }-

10 }-

10 }−

1 }−

1 9 . 10 . 10 . 1 . 1 = 900 ¿Cuántos de esos números son impares?

}_

5 }-

10 }-

10 }−

1 }−

1 Luego 5 . 10 . 10 . 1 .1 = 500 son impares, ya que la primera cifra puede ser sólo un dígito impar para que la última también lo sea. Ejemplo 6: ¿De cuántas maneras se pueden escoger dos fichas de dominó, de las 28 que hay en el juego, de modo que se puedan aplicar una en la otra (es decir, de modo que se encuentre el mismo número de tantos en ambas fichas)? Al elegir una ficha se lo puede hacer de 28 maneras distintas: 1º) en 7 casos la ficha elegida puede ser doble, 2º) en los 21 casos restantes la ficha será simple. En el 1º caso, la segunda ficha puede elegirse de 6 maneras distintas, entonces hay 7 . 6 = 42 posibles elecciones de una ficha doble y otra que se aplica en ella. En el 2º caso, la segunda ficha se puede elegir de 12 maneras distintas (6 por cada punta de la primera ficha), luego habrá 21 . 12 = 252 posibles elecciones de dos fichas simples que se apliquen una en otra. Luego, el número total de posibles elecciones del par de fichas es: 42 + 252 = 294. Esto lleva a la: Regla de la suma: si cierto objeto A puede elegirse de m maneras y otro objeto B puede elegirse de n maneras, la elección de “o A o B” se puede hacer de m + n maneras. Debe cuidarse que ninguna forma de elegir A coincida con alguna forma de elegir B. Si existiera esa coincidencia, la regla de la suma pierde validez y se obtienen m + n – k modos de elección distintos, siendo k en número de coincidencias. Algunos importantes modelos Los métodos anteriores permiten resolver una infinidad de problemas de recuento; pero entre ellos hay algunos que se presentan con mucha frecuencia y por eso han merecido un nombre propio y una simbología particular. Nota: Ante un problema concreto no es conveniente tratar de ajustarse a uno de esos modelos, es preferible razonar directamente empleando el método constructivo y ajustándose al enunciado propuesto. Permutaciones o Sustituciones Ejemplo 7: ¿De cuantas maneras distintas pueden ordenarse en fila 8 personas? Usando el método de selección anterior, podemos resolver fácilmente:

{8

__ {

7

__ {

6

__ {

5

__ {

4

__ {

3

__ {

2

__ {

1

__

Page 28: Algebra y Logica Algebra i Apuntes

28

La primera persona se puede elegir de 8 maneras distintas; por cada elección de la primera, la segunda puede elegirse entre las 7 restantes; elegida esa, hay 6 posibilidades para elegir la tercera; … y así sucesivamente. Luego, según la regla del producto, hay: 8 . 7 . 6 . 5 . 4 . 3 . 2 . 1 = 40.320 maneras distintas de ordenar 8 personas en fila. Esas ordenaciones se denominan Permutaciones o sustituciones. Definición: Dado un conjunto de m elementos, se llama permutación de orden m a cada uno de los distintos ordenamientos de esos elementos. Así, dos permutaciones son distintas sólo cuando difieren en el orden en que ha sido considerado al menos uno de sus elementos. Indicaremos con Pm el número total de permutaciones de m elementos, que calcularemos mediante el producto de enteros positivos consecutivos decrecientes a partir de m, hasta 1. Para simplificar su escritura, se emplea la siguiente notación: m! En el caso del ejemplo: 8! = 8.7.6.5.4.3.2.1 Definición: Sea m ∈ Z , m ≥ 0, se llama factorial de m y se representa por m! al número definido por recurrencia de la siguiente manera: 0! = 1 m! = m. (m-1)! Es decir que: m! = m.(m-1)! (m-1)! = (m-1)(m-2)! (m-2)! = (m-2)(m-3)! . . . . . . . . . . . . . . . . . entonces m! = m.(m-1) (m-2) . . . 2.1 Ejemplo 8: Un padre ha comprado para regalar a sus tres hijos, una caja de lápices de colores, una pelota y un libro. ¿De cuántas maneras puede repartir los regalos entre sus hijos?

{

3

__ {

2

__ {

1

__ 3! = 3. 2. 1 = 6

Entonces, existen 3! = 6 formas distintas de repartirlos. En cambio, si hubiera traído dos pelotas idénticas y un libro, cómo podría ahora repartir los regalos? 1º 2º 3º L P P P L P P P L esta construcción nos permite ver que sólo hay 3 repartos posibles. Esto muestra que la regla enunciada antes sólo es aplicable si los elementos son distinguibles. Analicemos otra situación que nos permitirá generalizar una respuesta cuando hay objetos repetidos entre los que se debe ordenar. Ejemplo 9: En un bar, cinco amigos han pedido tres cafés y dos cervezas. ¿De cuántas maneras distintas puede el mozo distribuir las cinco bebidas?

Page 29: Algebra y Logica Algebra i Apuntes

29

Si los cafés fueran distintos (solo, con crema , cortado) y las cervezas fueran de distintas marcas, entonces es claro que las posibles distribuciones podrían hacerse de 5! =120 maneras distintas. Pero siendo los 3 cafés iguales y las dos cervezas idénticas, una vez hecho un reparto, los 3 cafés podrían permutarse entre sí sin que cambie el resultado. Esto significa que los 120 resultados pueden agruparse en 3! = 6 grupos que no presentan diferencias.

Quedan pues 20 6

120 = resultados distintos.

Análogamente, cada reparto idéntico a aquel en que se intercambian las cervezas. Por lo

tanto, hay sólo 2

20 maneras distintas de distribuir las bebidas.

En resumen, el número de repartos posibles es: 10 2 . 6

120

!2 !3

!5 ==

Luego: Una colección de n objetos, clasificados en grupos de objetos idénticos entre sí, el

primero con k1 objetos, el segundo con k2, etc., se pueden ordenar de !!...!

!

21 rkkk

n

maneras distintas. En este caso estamos frente a permutaciones con repetición de n objetos, con k1, k2, …,kr iguales entre sí. Subconjuntos ordenados o Variaciones Veamos ahora otra situación: Ejemplo 10: En una carrera de 7 atletas, de cuántas maneras distintas pueden adjudicarse las medallas dorada, de plata y de bronce? Aquí no interesa la lista completa de llegada, sino los nombres de los tres primeros. Mediante el método constructivo obtenemos la respuesta: El atleta que recibirá la medalla dorada puede ser cualquiera de los 7 participantes de la carrera, adjudicada esa, la medalla de plata puede obtenerla cualquiera de los 6 restantes y la de bronce, alguno de los 5 que quedaron. Esto es:

{ { {567

3º 2º º1 luego hay 7 . 6 . 5 =210 formas distintas de adjudicar las tres

medallas. Obsérvese que son 7! Los órdenes de llegada de los 7 atletas, pero para los efectos de la adjudicación de las medallas, los 4 últimos da lo mismo que lleguen en el lugar 4 que en el lugar 7. Entonces, todas las listas de llegada se pueden dividir en grupos de 4! Listas, obtenidas permutando sus cuatro últimos nombres. Entonces, el

número de listas con diferencia en la entrega de medallas es: 7.6.5 4!

7.6.5.4!

!4

!7 ==

En general: Dado un conjunto A, de n elementos, el número de subconjuntos

ordenados de r elementos que pueden elegirse entre los n, es: )!(

!

rn

n

−.

Obviamente, se consideran subconjuntos ordenados distintos aquellos que difieren en al menos un elemento o en el orden en que han sido considerados.

Page 30: Algebra y Logica Algebra i Apuntes

30

Usualmente el número de subconjuntos ordenados de r elementos, de un conjunto de n elementos, se denominan Variaciones de n elementos de orden r. Siempre n > r. El número de Variaciones de n elementos de orden r (o tomas de a r ) lo indicamos:

1)r-2)...(n-1).(n-n.(n r)!-(n

n! +==r

nV

Ejemplo 11: Consideremos el conjunto {1, 2, 3, 4}, las Variaciones de esos 4 elementos de orden 2, o tomados de a 2, son: 123.42

4 ==V Ellas son: 1 2 2 1 3 1 4 1 1 3 2 3 3 2 4 2 1 4 2 4 3 4 4 3 Si ahora quisiéramos construir las variaciones de esos elementos tomados de a 3, bastará agregar a cada una de las anteriores otro elemento a elegir de entre los restantes. Así, para cada una de las anteriores habrá 2 nuevas: 3 3 2 1 2 2 1 3 1 . . . 4 4 4 2 1 3 . . . 4 Luego: 2 . 2

43

4 VV = → 24 4.3.2 24 ==V

Proposición: El número de variaciones de n elementos tomados de a r (r ≤ n) está dado por la expresión: 1)r-2)...(n-1).(n-n.(n Vr

n += , esto es, r factores decrecientes a partir de n. Demostración: Por Inducción sobre r : 1) Sea r = 1: n V1

n = pues hay n maneras distintas de elegir 1 elemento entre los n. 2) Sea r > 1 y supongamos que la expresión es verdadera para (r-1) elementos:

[ ]11)-(r-n1)...-n(n V 1-rn +=

= n (n-1) …(n – r + 2) 3) Probaremos que también es verdadera para r: De acuerdo al ejemplo anterior, una vez formadas las variaciones de orden (r-1), para formar las de orden r podremos agregar a cada una de las anteriores un nuevo elemento elegido entre los restantes n-(r-1) que no están considerados en ella. Con eso, por cada variación de orden (r – 1) tendremos n-r+1 variaciones de orden r. Luego:

1)r-2)(nr-1)...(n-n.(n V

)1.(V Vrn

1-rn

rn

++=

+−= rn

lo que prueba la proposición. Variaciones con repetición

Page 31: Algebra y Logica Algebra i Apuntes

31

Definición: dado un conjunto finito A de n elementos, se llama variación con repetición de orden r de esos n elementos, a toda sucesión de r términos formada por elementos de A, no necesariamente distintos entre sí. Indicaremos: r'

nV . Ejemplo 12: ¿Cuántas sucesiones de tres elementos pueden formarse con los elementos 0 y 1? Armemos esas sucesiones: 0 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 Luego: 8V '3

2 = Proposición: El número r'

nV de variaciones con repetición de n elementos tomados de a

r , está dado por la expresión: rr'n n V = .

Demostración: Por Inducción sobre r. 1) Sea r = 1, es inmediato que 1'1

n n n V == 2) Sea r > 1 y supongamos que la expresión es verdadera para (r-1) elementos: 1-r1)-(r'

n n V = 3) Probemos que la expresión es verdadera para r. Razonando como en la Proposición anterior, una vez construidas las variaciones con repetición de orden (r-1) para obtener las de orden r, deberemos agregar un elemento a cada una de las anteriores, que puede ser cualquiera de los n elementos de A. Por lo tanto, de cada una de las anteriores obtendremos n, de orden r:

n .V V 1)-(r'n

r 'n =

= nr-1 . n = nr con lo que queda demostrada la validez de la Proposición.

Subconjuntos o Combinaciones Ejemplo 13: ¿De cuántas maneras distintas pueden seleccionarse los 6 números de la boleta del Quini 6? Sabemos que hay que elegir los 6 números entre los 36 primeros números naturales y que han de ser distintos entre sí. Constructivamente calcularíamos los subconjuntos ordenados así:

{36

__ {35

__ {34

__ {33

__ {32

__ {31

__

6)!-(36

36! V 6

36 =

Pero, en esta situación, el orden en que elegimos los números no distingue dos tarjetas, así es que ese número de posibilidades se puede dividir en 6! grupos, lo que deja un

total de !6!.30

!36 posibles elecciones o tarjetas distintas.

Page 32: Algebra y Logica Algebra i Apuntes

32

Esto es, se eligen 6 elementos de 36, pero dos tarjetas son distintas si difieren al menos en un número. Esto es, se eligen subconjuntos de 6 elemento, no subconjuntos ordenados.

Luego, de un conjunto de n elementos, pueden formarse )!rn(!r

!n

subconjuntos de r elementos. Los subconjuntos de r elementos de un conjunto de n elementos se denominan Combinaciones de n elementos tomados de a r (o de orden r ). Indicaremos:

r)!-(n r!

n! Cr

n =

Ejemplo 14: Sea A = {a, e, i, o, u }, de cuantas maneras pueden elegirse conjuntos de tres vocales? Construyamos las posibilidades: aei aeo aeu aio aiu aou eio eiu eou iou Son:

10 C35 =

Obsérvese que si ahora formamos las 3

5V , tendríamos:

aei aeo aeu aio aiu aou eio eiu eou iou aie aoe aue aoi aui auo eoi eui euo iuo eai eao eau iao iau oau ieo ieu oeu oiu eia eoa eua ioa iua oua ioe iue oue oui iae oae uae oai uai uao oei uei ueo uio iea oea uea oia uia uoa oie uie uoe uoi Esto es, por cada una de las combinaciones obtenidas antes, permutando sus elementos, obtenemos todas las variaciones de orden 3.

335

35 P . C V = →

3

353

5 P

V C = →

3! 3)!-(5

5! C3

5 =

En general, el número de combinaciones de n elementos tomados de a r, está dado por la expresión:

r! r)!-(n

n! C

P

V C r

nr

rnr

n =→=

Como el número r

nC aparece con frecuencia en muchos tipos de cálculos, existe

una notación especial para indicarlo:

=

r

n Cr

n que llamamos número combinatorio

n sobre r.

Definición: Se llama número combinatorio n sobre r al número que indicamos:

r! r)!-(n

n! =

r

n

Page 33: Algebra y Logica Algebra i Apuntes

33

Así: 154

6

2!4!

6.5.4!

!4)!46(

!6

4

6=

→=

−=

ó 792 5! 5)!-(12

12!

5

12==

Propiedades de los números combinatorios Los números combinatorios verifican interesantes propiedades y relaciones entre ellos. Entre las más simples:

P.1.-

=

r-n

n

r

n Estos números combinatorios se dicen complementarios.

Definición: Dos números combinatorios se dicen complementarios si tienen igual numerador y sus denominadores suman ese numerador. Verificación de P.1.:

[ ]!r)-(n-n r)!-(n

n!

r-n

n =

= r)!n-(n )!r-n(

!n

+

= r! )!r-n(

!n

=

r

n

P.2.-

+

=

1-r

1-n

r

1-n

r

n

Verificación a cargo del lector.

P.3.- nn

0

2 k

n =

=k

Esto es: n2 n

n . . .

2

n

1

n

0

n=

++

+

+

¿Cómo verificarlo? Obsérvese que el primer miembro expresa el número total de subconjuntos de un conjunto de n elementos, pues es la suma del número de subconjuntos de cero elementos, más el número de subconjuntos de un elemento, más … Pero el número total de subconjuntos puede calcularse directamente. Para identificar un subconjunto arbitrario, se puede señalar con X los elementos elegidos y con 0 los descartados. Hay

Page 34: Algebra y Logica Algebra i Apuntes

34

dos posibilidades de elección (X o 0) para el primer elemento del conjunto, las mismas para el segundo elemento, … y las mismas para cualquiera de los n elementos:

{ { { {2222

__ . . . __ __ __

Luego, el número total de subconjuntos es 2n. La propiedad P.2. permite el cálculo rápido de los números combinatorios de numerador n, conociendo los de denominador n-1. Suelen escribirse en filas sucesivas, así: n=0 1 n=1 1 1 n=2 1 2 1 n=3 1 3 3 1 n=4 1 4 6 4 1 n=5 1 5 10 10 5 1 n=6 1 6 15 20 15 6 1 Este es el llamado Triángulo Aritmético, atribuido a Tartaglia, aunque parece que su origen es mucho más antiguo. Este Triángulo ofrece múltiples relaciones interesantes y curiosas entre sus elementos. Obsérvese que, escritas las dos oblicuas 1, 1, …, 1, los elementos de cada línea se forman aplicando P.2., que en definitiva expresa: cada elemento es la suma de los dos que figuran encima de él; la P.1. expresa la igualdad de los números colocados simétricamente respecto del eje vertical de simetría del triángulo. Potencia de un binomio Una aplicación interesante de los números combinatorios es su empleo en la fórmula que permite calcular expresiones del tipo (a + b)n, con n ∈ Z, n ≥ 0, esto es, el desarrollo de la potencia n-ésima de un binomio. Las expresiones correspondientes a n = 1, n =2 y n = 3, son conocidas por los alumnos, expresiones que escribimos:

n = 1 (a + b)1 = a + b = b 1

1 a

0

1

+

n = 2 (a + b)2 = a2 + 2 ab + b2 = 22 b 2

2 ab

1

2 a

0

2

+

+

n = 3 (a + b)3 = a3 + 3 a2 b + 3 a b2 + b3

= 3223 b 3

3 b a

2

3 ba

1

3 a

0

3

+

+

+

Page 35: Algebra y Logica Algebra i Apuntes

35

En general demostraremos el siguiente Teorema: Cualesquiera sea el entero no negativo n, es:

( ) n0kk-n22-n1-n0nn b a n

n ... ba

k

n ... b a

2

n b a

1

n a

0

n b a

++

++

+

+

=+ b

(a + b)n = kk-nn

0k

b a ∑=

k

n

Demostración: se hará por Inducción sobre n:

1) sea n = 1 → ( ) kk-11

0k

1 b a k

1 b a ∑

=

=+

= b a 1

1 b a

0

1 00

+

= a + b luego es válida la expresión para n = 1. 2) Supongamos válida la expresión para el exponente (n–1), esto es:

( ) kk-1-n1-n

0k

1-n b a k

1-n b a ∑

=

=+

y 3) probemos su validez para exponente n: (a + b)n = (a + b)n-1 (a + b)

(a + b)n = (a + b) . kk-1-n1-n

0k

b a k

1-n ∑

=

(aplicando propiedad

distributiva)

(a + b)n = 1kk-1-n1-n

k

kk-n1-n

0k

b a k

1-n b a

k

1-n +

=∑∑

+

Sacando fuera de la primera sumatoria el primer sumando (que corresponde a k = 0) y en la segunda sumatoria, sacamos el último sumando (que corresponde a k = n-1), resulta:

(a + b)n = n01k1-k-n2-n

0k

kk-n1-n

1k

0n b a 1-n

1-n b a

k

1-n b a

k

1-n b a

0

1

+

+

+

− +

==∑∑

n

En la segunda sumatoria haciendo un cambio en el índice de la variable k, por k-1, resulta:

kk-n1-n

1k

1k1-k-n2-n

0k

b a 1-k

1-n b a

k

1n∑∑

=

+

=

=

Luego:

(a + b)n = n0kk-n1-n

1k

1-n

1k

kk-n0n b a 1-n

1-n b a

1-k

1-n b a

k

1-n ba

0

1n

+

+

+

−∑∑

==

Page 36: Algebra y Logica Algebra i Apuntes

36

En ambas sumatoria hay términos semejantes que podemos agrupar, con lo que quedará:

(a + b)n = n01-n

1k

kk-n0n b a 1-n

1-n b a

1-k

1-n

k

1-n ba

0

1n

+

+

+

−∑

=

(a + b)n = an + nkk-n1

1

b b a k

n +

=

n

k

(a + b)n = kk-nn

0k

b a n

∑=

k con lo que queda probado el teorema.

Esta expresión general recibe el nombre de Fórmula del binomio de Newton. Ejemplo 15: Desarrollar (x2 + 3y)6.

(x2 + 3y)6 = ( ) ( )kk626

0k

3y x k

6

=∑

(x2 + 3y)6 =

0

6(x2)6 (3y)0 +

1

6(x2)5 3y +

2

6(x2)4 (3y)2 +

3

6(x2)3 (3y)3 +

+

4

6(x2)2 (3y)4 +

5

6x2 (3y)5 +

6

6(x2)0 (3y)6

(x2 + 3y)6 = x12 + 6 x10 3y + 15 x8 9 y2 + 20 x6 27 y3 + 15 x4 81 y4 + 6 x2 243 y5 + 729 y6 (x2 + 3y)6 = x12 + 18 x10 y + 35 x8 y2 + 540 x6 y3 + 1215 x4 y4 + 1458 x2 y5 + 729 y6 Veamos ahora cómo calcular un término dado, correspondiente al desarrollo de la potencia n-ésima de un binomio. Ejemplo 16: Calcular el sexto término del desarrollo de (3x + 2y)8. De acuerdo a la fórmula de Newton, el desarrollo correspondiente es:

(3x + 2y)8 = ( ) ( )kk88

0k

2y 3x k

8 −

=∑

Luego, el sexto término corresponde a k=5, con lo que será:

T5 =

5

8(3x)3 (2y)5 = 53 y 32 x27 .

!3!.5

!5.6.7.8

T5 = 48382 x3 y5 Ejemplo 17: Desarrollar (1 – ½ a2)5

( ) k255

0k

52 )a (-1/2 1 k

5 a 2/11 k−

=∑

=−

=

0

515 +

1

514 (-1/2 a2) +

2

513 (-1/2 a2)2 +

3

512 (-1/2 a2)3 +

Page 37: Algebra y Logica Algebra i Apuntes

37

+

4

51 (-1/2 a2)4 +

5

5(-1/2 a2)5

(1 – ½ a2)5 = 1 – 5/2 a2 + 5/2 a4 – 5/4 a6 + 5/16 a8 – 1/32 a10 Obsérvese que, tratándose de un binomio diferencia, esto es de la forma (a – b)n, resultan siempre, en el desarrollo, los signos alternados.

Page 38: Algebra y Logica Algebra i Apuntes

38

Los números enteros

En el conjunto Z de los números enteros están definidas dos operaciones binarias: la suma y el producto. Esas operaciones verifican las siguientes propiedades: S1.- Asociatividad. ∀a, b, c ∈ Z : (a+b) + c = a + (b+c) S2.- Conmutatividad. ∀ a, b∈ Z : a + b = b + a S3.- Existencia de elemento neutro. ∃ 0∈ Z : 0 + a = a ∀ a∈ Z S4- Existencia de elemento opuesto. ∀ a∈ Z, ∃ b∈ Z : a + b = 0 Notación: b = -a, luego: a + (-a) = 0 y decimos que (-a) es opuesto de a y viceversa. P1.- Asociatividad. ∀a, b, c ∈ Z : (a · b) · c = a · (b · c) P2.- Conmutatividad. ∀ a, b∈ Z : a · b = b · a P3.- Existencia de elemento neutro. ∃ 1∈ Z : 1 · a = a ∀ a∈ Z D.- Distributividad del producto respecto de la suma. ∀a, b, c ∈ Z : a · (b+c) = a·b + a·c y también (b+c) · a = b·a + c·a Estas propiedades de la suma y el producto dan a Z su estructura característica de anillo. En base a estas propiedades o leyes de las operaciones de suma y producto, se pueden probar otras propiedades tales como: a) ∀ a ∈ Z: a · (-1) = -a Esto es, el opuesto de a es igual a (-1)·a b) -(-a) = a ∀ a ∈ Z c) Si a + b = 0 entonces b = -a d) -(a+b) = (-a) + (-b) Notación: escribimos a + (-b) = a - b y a ese elemento le llamamos “a menos b” e) –(a-b) = b – a En Z se define también una relación binaria “<” de modo que se verifican las siguientes leyes: 1.- Ley de Tricotomía: ∀ a, b∈ Z se verifica una y sólo una de las siguientes relaciones: a < b , a = b ó b < a 2.- Ley Transitiva: si a < b y b < c → a < c 3.- Ley de monotonía de la suma. a < b y c ∈ Z → a + c < b + c 4.- Ley de Monotonía del producto: a < b y c ∈ Z , c > 0 → a · c < b · c a < b y c ∈ Z , c < 0 → a · c > b · c Notación: Si a < b entonces b > a a ≤ b si y sólo si a = b ó a < b

Page 39: Algebra y Logica Algebra i Apuntes

39

El tema central de esta Unidad es analizar otras dos propiedades importantes y características del conjunto Z, que son: 1.- La existencia del algoritmo de la división. 2.- La Factorización de enteros. Antes de llegar a ellas, hemos de analizar la relación divide en Z. Definición: Se dice que un entero a ≠ 0 es divisor de un entero b, si ∃ k∈ Z : b = k · a. En tal caso decimos que “a es divisor de b” o “ a divide a b” y escribimos a/b. Ejemplos: -3 / 15 pues existe -5 ∈ Z : (-5) ·(-3) = 15 9 / 9 pues existe 1 ∈ Z : 9 · 1 = 9 -1 / -4 pues existe 4 ∈ Z : 4 · (-1) = -4 Propiedades: 1.- Propiedad reflexiva. ∀ a∈ Z : a / a 2.- ∀ a∈ Z : a / 0 3.- Si a / b → a / -b ; -a / b ; -a / -b 4.- Propiedad transitiva. Si a / b y b / c → a / c 5.- Si a / b y a / c → a / x·b + y·c ∀ x, y ∈ Z Esto es, a divide a cualquier combinación lineal de b y c. 6.- Si a / b → a·c / b·c ∀ c∈ Z Recíprocamente: si c ≠ 0 y a·c / b·c → a / b. A modo de ejemplo desarrollaremos la demostración de alguna de estas propiedades, quedando las restantes a cargo del lector. Propiedad 3. Demostración: Si a / b → ∃ k1∈ Z: b = k1 · a Como k1∈Z → ∃ -k1∈Z, luego, multiplicando por (-1) la igualdad anterior, resulta: (-1) · b = (-1) · k1 · a -b = [(-1)·k1] · a -b = -k1 · a → a / -b A partir de esta demostración, pruebe el lector que -a / b y que -a / -b. Propiedad 5. Demostración: Si a /b → b = k1 · a con k1∈Z Sea x∈Z : x = x . b· x = (x · k1) · a (*)

Page 40: Algebra y Logica Algebra i Apuntes

40

Si a / c → c = k2· a con k2∈Z Sea y∈Z : y = y . c · y = (y · k2) · a (**) Sumando (*) y (**) resulta: b · x + c · y = (x · k1 + y · k2) · a Como (x · k1 + y · k2) ∈Z, entonces a / b·x + c·y Propiedad 6. Demostración: Si a /b → b = k1 · a con k1∈Z. Sea c ∈Z : c·b = c·k1 · a aplicando propiedad conmutativa: c·b = k1· c·a → c·a / c·b Recíprocamente. Sea c ≠0, c∈ Z → ∃ c-1∈Q Si a·c / b·c → b·c = k · a·c multiplicando por c-1: b = k · a·c·c-1 → b = k · a → a / b. Importancia de la relación divide en Z 300 años antes de Cristo, ya Euclides y sus contemporáneos conocían y manejaban muchos resultados sobre el tema. Es claro que si a ∈ Z, a≠0, entonces a / b, b∈Z si y sólo si el resto de dividir a por b es cero. En cambio si se piensa en el conjunto Q de los racionales, no existe problema para dividir, ya que cualquier racional es divisible por cualquier otro distinto de cero. División entera Es bien conocido el procedimiento por el que, dados dos enteros positivos a y b se determina el cociente q y el resto r, de la división de a por b. Si a = 1543 y b = 25 → 1543 | 25 . 043 61 18 → q = 61 y r = 18 ∴∴∴∴ 1543 = 25 · 61 + 18 En general: a = b · q + r Teorema: Para todo par de enteros a y b, con b≠0, existen enteros q y r, llamados cociente y resto de dividir a por b, unívocamente determinados, tales que a = q · b + r con 0 ≤ r < b Demostración: Por razones de simplicidad probemos primero que si q y r existen, entonces son únicos. Supongamos, por Absurdo, que además del par de enteros q y r, existen q’ y r’ ∈Z, tales que:

a = q · b + r con 0 ≤ r < b

Page 41: Algebra y Logica Algebra i Apuntes

41

a = q’ · b + r’ con 0 ≤ r’ < b entonces será: q · b + r = q’ · b + r’ → q · b - q’ · b = r’ - r → (q – q’)· b = r’ – r y tomando valor absoluto, resulta: q – q’·b = r’ - r Entonces, si r ≠r’ → r’ - r≠ 0 y si q’≠ q → q – q’≠ 0 tenemos: q – q’·b = r’ - r (·)

b≤ q – q’·b = r’ - r → b≤ r’ - r (*) Pero, siendo r < b y r’< b → b>r’ - r lo que contradice la expresión (*). Esta contradicción provino de suponer que r ≠r’, luego r = r’ y entonces, como b≠0, en (·) debe ser: q – q’ = 0 → q = q’, lo que prueba la unicidad del cociente y del resto. Probemos ahora que, efectivamente existen los enteros q y r en las condiciones del teorema. 1) Obsérvese primero que si a es múltiplo de b, entonces: a = k · b , para algún k∈Z, entonces tomando q = k y r = 0, se tiene el par de enteros en las condiciones exigidas. 2) Supongamos que a no es múltiplo de b, esto es ∀x∈Z, a ≠ x · b (o, dicho de otro modo, no existe ningún x∈Z, tal que a = x · b) Consideremos entonces el conjunto S de todos los enteros positivos de la forma a – x·b con x∈Z. Por lo dicho anteriormente, a – x ·b ≠ 0, pero habría que ver si existe x∈Z de tal modo que esa diferencia sea positiva; en caso contrario, S sería vacío. Veamos que S ≠∅:

Sea

<>

=0 a si 1-

0 a si 1 α

<>

=0 b si 1-

0 b si 1 β

Entonces a= α·a y b= β·b Consideremos x∈Z, x de las forma : x = - α·β·a Entonces: a – x·b = a – (- α·β·a) ·b a – x·b = a + α·β· a ·b a – x·b = a + a·b a – x·b = αa+a·b

a – x·b = a(α+b) siendo b> 1, pues b ≠0 y a ≠·

b Entonces: (α+b) > 0 → (α+b)·a> 0 , por lo tanto a – x·b > 0, esto es, es un entero positivo, luego S ≠∅. Significa entonces que S es un subconjunto no vacío de N, luego S tiene primer elemento.

Page 42: Algebra y Logica Algebra i Apuntes

42

Sea r el primer elemento de S, que se obtiene cuando x asume el valor q: r = a – q·b Entonces:

a = q · b + r Veamos ahora que r < b. Que r >0, lo hemos dicho al indicar que r∈S y S⊂N. Supongamos que r ≥b → r > r - b ≥ 0

Como r - b = a – q·b - b = a – (q+β)·b > 0 pues a ≠·

b, entonces r - b tiene la forma a – x·b (para x = q + β) con lo que r -b∈S. Luego resulta r - b< r, un elemento de S. Absurdo! Pues r es el primer elemento de S. Por lo tanto, r < b. Con lo que queda demostrado el teorema. Ejemplos: Si a = 3 y b = 9 → q = 0 y r = 3 ya que 3 = 0·9 + 3 Si a = 18 y b = -4 → q = -4 y r = 2 “ “ 18 = (-4)·(-4) + 2 Si a = -1548 y b = 12 → q = -129 y r = 0 “ “ -1548 = (-129)·12 + 0 Una interesante aplicación del Algoritmo de la división entera es la de representar un entero positivo cualquiera en base b >1: Representación b-ádica de un entero, o representación en base b. El problema es el siguiente: Representar el entero positivo a ≥ 0 en forma de polinomio en b, cuyos coeficientes ci satisfagan las relaciones:

a = c0 + c1 b + c2 b2 + c3 b

3 + . . . + cn bn b >1, 0 ≤ ci < b , para i = 0, 1,

2, …, n

Esto es: a = in

0ii b c∑

=

El problema radica en determinar los ci, que llamaremos cifras, siendo b la base de representación. Una vez determinados los ci, se conviene en escribir el entero a de la siguiente manera:

a = cn cn-1 . . . c2 c1 c0 (base b) Veamos un ejemplo: sea a= 1536 y b= 10 (b es la base de la representación) a = 1530 + 6 a = 153 · 10 + 6 a = (150+3) · 10 +6 a = (15 · 10 +3) ·10+ 6 a = {[(10 +5) ·10] +3} ·10 + 6 a = [(5·10 + 10·10) +3] ·10+6 a = 5· 102 + 103 + 3·10 + 6

Page 43: Algebra y Logica Algebra i Apuntes

43

a = 6 + 3·10 + 5·102 + 1·103 Descomposición 10-ádica o decimal de a. ¿Cómo resolver el problema en forma general? Simplemente procediendo como en el ejemplo, usando sucesivamente el algoritmo de la división: a = b · q1 + r1 con 0 ≤ r1 < b Obsérvese que por ser a > 0, 0 ≤ q1 < a Si q1 < b, ya está la solución, tomando: c0 = r1 , c1 = q1 y entonces n = 1 : a = c1 b + c0 entonces a = c1c0

Si q1 ≥ b, entonces lo dividimos por b: q1 = q2 ·b + r2 0 ≤r2 < b ; 0≤ q2 < q1

Entonces: a = b (q2 ·b + r2) + r1

a = q2 b2 + r2 b + r1

Si q2 < b → c0 = r1 ; c1 = r2 ; c2 = q2 , n = 2 ∴ a = c0 + c1 b + c2 b

2 → a = c2c1c0(b) Si q2 ≥ b → q2 = b q3 + r3 0 ≤ r3< b ; q3 <q2 a = (b q3 + r3 ) b

2 + r2 b + r1

a = q3 b3 + r3 b

2 + r2 b + r1 a = c3 b

3 + c2 b2 + c1 b + c0 con c3 = q3 ; c2= r3 ; c1 = r2 ; c0 =r1 n =

3 Entonces a = c3c2c1c0 (b) Si q3 ≥ b iteramos el proceso. Este proceso concluye en un número finito de pasos pues q va disminuyendo, llegándose a qn < b ≤ qn-1 Probablemente el alumno haya trabajado representando enteros en base b = 2, en ese caso, se usan sólo dos cifras: 0, 1. Ejemplo: 417 = 110100001 (2) 417 2 . 17 208 2 . 1 008 104 2 .

0 04 52 2 . 0 12 26 2 . 0 06 13 2 . 0 1 6 2 . 0 3 2 . 1 1 = cn

417 = 1 + 0 · 2 + 0 · 22 + 0 · 23 + 0 · 24 + 1 · 25 + 0 · 26 + 1 · 27 + 1 · 28

Page 44: Algebra y Logica Algebra i Apuntes

44

Ejemplo: Expresar 117 en base 5 117 5 . 17 23 5 . Así, 117 = 432(5) 2 3 4 Cómo constatar? Escribiendo el polinomio: 2·50 + 3·5 + 4·52 = 117 Observaciones: 1.- Nuestro sistema de numeración es decimal, esto es, en base 10. Las cifras son 0, 1, 2, . . .,9 El número 3429 = 9 + 2 ·10 + 4·102 + 3·103 El 756 es: 6 + 5·10 + 7·100 2.- En base b, las cifras son 0, 1, 2, …, b-1 b≤ 10 Los números menores que b se representan mediante una única cifra . 3.- El número b se representa siempre como : b = 10 (b) Así, 6 = 10 (6) En efecto: 6 6 . entonces 6 = 0 + 1·6

0 1 4.- Para representar números en base b>10, se necesitan más símbolos para indicar las cifras que siguen al 9. Por ejemplo, para b = 13, las cifras pueden ser: 0, 1, 2, …, 9, α, β, γ Así 1493 = 8αβ (13) ya que 1493 13 . 19 114 13 . 63 α 8 β 1493 = β + α·13 + 8·132

Ejemplos: 1. Qué número decimal es N = 2α3γ3 (13) ? N = 2· 134 + α· 133 + 3·132 + γ· 13 + 3 N = 2· 28561 + 10 · 2197 + 3 . 169 + 12· 13 + 3 N =57122 + 21970 + 507 + 156 + 3 N = 79758 2. Representar en base 9 el número 2534 (7) 2534 (7) = 2·73 + 5·72 + 3·7 + 4

= 956 = 1272 (9)

Page 45: Algebra y Logica Algebra i Apuntes

45

3. Considerando el entero positivo cuya representación en base 6 es: n = 342x (6),determinar la cifra x para que dicho número sea divisible por 5. n = 342x (6) → n = 3·63 + 4·62 + 2·6 + x n = 648 + 144+12 + x n = 804 + x Luego, si x = 1 → n = 805 por lo tanto es divisible por 5 Números primos Hemos dicho que si a≠0 y a/b, entonces b es múltiplo de a y al dividir b por a, el resto es cero. Es claro que, ∀ a∈Z, a es divisible por 1, -1, a y -a. Estos son los llamados divisores triviales de a. Cualquier divisor de a, distinto de ellos, se llamará divisor propio de a. Ejemplo: sea a = 48, entonces los divisores triviales de 48 son: 1, -1, 48 y -48. Son divisores propios de 48: 2, -2, 3, -3, 4, -4, 6, -6, 8, -8, 12, -12, 16, -16, 24 y -24 Definición: un entero p, distinto de 0, 1 y -1 se dice primo, si no admite mas divisores que los triviales. Esto es: p∈Z es primo si sus únicos divisores son: 1, -1, p y -p. Si a∈Z no es primo, entonces a se dice compuesto. Ejemplos: son enteros primos: 17, 43, -7, -61 Son enteros compuestos: -96, 28, 100, -65 Así, Z queda dividido en tres subconjuntos disjuntos dos a dos, no vacíos: {0, 1, -1 } P = { p∈Z : p es primo} C = {a ∈Z : a es compuesto} Z C

P ¿Constituyen esos tres subconjuntos una partición de Z? Vemos cómo son los divisores de un entero dado. Teorema: Sea a∈Z, a ≠ 0 y sea c/a, entonces 1 ≤ c ≤ a Si c es divisor propio de a, entonces 1 < c < a

Page 46: Algebra y Logica Algebra i Apuntes

46

Demostración: Si c/a → a = k· c con c ≠0 y k≠0 → a=k·c siendo k≥ 1 pues k≠0 → a≥c ≥ 1 (·) Si c es divisor propio de a → c ≠ ±1 → c≠ 1 y c ≠ ±a → c≠ a Luego la expresión (·) se reduce a : a>c > 1 con lo que queda probado el Teorema. Esto nos dice que dado a∈Z, a≠0, a tiene un número finito de divisores. Estos divisores forman un subconjunto del conjunto de los enteros cuyo valor absoluto está comprendido entre a y 1. Si a es compuesto, entonces es de la forma a = b · c siendo b y c divisores propios ∴ 1 < b< a y 1 < c < a Proposición: Cualesquiera sean a, b ∈ Z, las siguientes proposiciones son equivalentes:

1) a y b tienen los mismos divisores 2) a y b difieren en un factor unitario, esto es, a = ± b 3) a/b y b/a

Demostración: Recordemos que los únicos enteros que tienen inverso multiplicativo en Z son 1 y -1. A ellos se los llama enteros unitarios. Respecto de la división, los enteros unitarios tienen la particularidad de dividir a cualquier otro entero. 1 → 2: Supongamos que a y b tienen los mismos divisores, entonces como a / a ,∀a∈ Z, debe darse también que a / b → b = k1 · a con k1∈Z. De igual modo, como b / b y a tiene los mismos divisores que b, entonces b / a → a = k2 · b con k2∈Z. Luego: b = k1 · (k2· b) → b = (k1·k2) b Entonces, si b ≠0, por la ley cancelativa, resulta: k1·k2 = 1 → k1 = k2 = 1 ó k1 = k2 = -1 con lo que resulta b = ± a Si b = 0, siendo a = k2·b → a = 0 y obviamente se verifica la proposición. 2 → 3 : Suponiendo que a = ± b, entonces b / a pues existe (±1) ∈ Z, tal que : a = ±1·b y si a = ± b → b = ± a → a / b 3 → 1: Si a /b y b/ a veremos que a y b tienen los mismos divisores: Sea c∈Z tal que c / a, entonces como a / b → c / b. Esto es, cualquier divisor de a lo es también de b. De igual modo, si k / b como b /a → k /a. Luego, todo divisor de b también divide a a.

Page 47: Algebra y Logica Algebra i Apuntes

47

Definición: Dos enteros a y b que verifican las condiciones de la Proposición anterior se dicen enteros asociados. Evidentemente el asociado de un entero a es –a. Ejercicio: Probar que la relación “ser asociado de …” definida sobre Z es una relación de equivalencia.

Divisor Común Mayor Sea a∈Z, indicaremos con D(a) el conjunto de todos los divisores de a.

D(a) = {x∈Z : x /a } Ejemplos: D(12) = {±1, ±2, ±3, ±4, ±6, ±12 } D(-27) = {±1, ±3, ±9, ±27} D(1) = {±1} D(p) = {±1, ±p} D(0)= Z D(12) ∩ D(-27) = {±1, ±3} En general, el conjunto de los divisores comunes de dos enteros no simultáneamente nulos, es distinto de vacío y finito. Entonces, como subconjunto de Z finito y distinto de ∅, tiene último elemento. Esto es, existe un divisor común de a y de b que es mayor que los demás y además, ese es positivo, pues si c/x → -c/x de modo que c∈ D(a)∩D(b) ⇔ -c∈ D(a)∩D(b). Definición: Dados dos enteros a y b, no simultáneamente nulos, se llama Divisor Común Mayor de a y b al mayor de los divisores comunes. Indicaremos el divisor común mayor de los enteros a y b con: (a, b). Ejemplo: (12, -27) = 3 Observación: Si b/a → (a, b) =b b≠0 En particular: (0, a) = a Proposición: Si a, b ∈Z, b≠0 y r es el resto de dividir a por b, entonces a y b tienen los mismos divisores que b y r. Demostración: Sean q y r ∈Z: a = q b + r , con 0≤ r <b, entonces r = a - q b Sea c un divisor común de a y de b, entonces c / xa + yb ∀x, y ∈Z, en particular: c / a - q b → c / r Luego, c es divisor común de b y de r. Esto es, cualquier divisor de a y b, es también divisor de b y r.

Page 48: Algebra y Logica Algebra i Apuntes

48

Recíprocamente: Sea t un divisor de b y de r → t/b y t/r → t / q b + r → t / a Luego t es divisor de a y de b. Corolario: (a, b) = (b, r) Esto es, el divisor común mayor entre a y b es igual al divisor común mayor entre b y r. Probar el Corolario anterior como ejercicio. Ejemplo: consideremos el problema de calcular el divisor común mayor de los números 342 y 126. 342 126 12690 90 36 36 18 90 2 36 1 18 2 0 2 Así: (342, 126) = (126, 90) = (90, 36) = (36, 18) = 18

Cálculo del divisor común mayor – Algoritmo de EUCLIDES Vamos a organizar las divisiones sucesivas realizadas en el ejemplo anterior, a través del siguiente cuadro:

2 1 2 2 342 126 90 36 18 90 36 18 0

Obsérvese que el divisor común mayor entre 342 y 126 es el último resto no nulo obtenido luego de las sucesivas divisiones. Veamos en general: Sean a , b ∈ Z , b≠0 Efectuamos divisiones sucesivas como indica el cuadro. Se observa que los restos que se obtienen son positivos y estrictamente decrecientes, por ello el procedimiento podrá repetirse un número finito de veces. El último resto será siempre nulo.

q1 q2 q3 … qn-2 qn-1 qn qn+1

a b r1 r2 … rn-3 rn-2 rn-1 rn

r1 r2 r3 … rn-1 rn 0 Formalizamos ahora en el siguiente: Teorema: si a , b∈Z , b≠0, el último resto no nulo que se obtiene en el Algoritmo de Euclides, es el divisor común mayor d de a y b. Además d = x·a + y·b , x, y ∈Z. Demostración: 1) Si el primer resto obtenido es cero → d = (a, b) = b y este puede escribirse: b= 0·a + (±1)·b con lo que se verifica el teorema.

Page 49: Algebra y Logica Algebra i Apuntes

49

2) Si el resto es 0 al cabo de n+1 divisiones, n>1, se tiene: a = q1 b + r1 0 ≤ r1 < b b = q2 r1 + r2 0 ≤ r2 < r1 r1 = q3 r2 + r3 0 ≤ r3 < r2

. . . . . . . . . . . . . . . . rn-2 = qn rn-1 + rn 0 ≤ rn < rn-1 rn-1 = qn+1 rn + 0 De esta última igualdad resulta que: rn/rn-1 → (rn-1, rn) = rn Por el Corolario de la Proposición anterior, resulta:

rn = (rn-1, rn) = (rn-2, rn-1) = . . . = (r1, r2) = (b, r1) = (a, b) Esto es,

rn = (a, b) = d Por otra parte, de las igualdades anteriores, resulta: r1 = a – q1 b → r1 = a + (-q1) b r2 = b – q2 r1 → r2 = b – q2 (a + (-q1) b) → r2 = (-q2) a + (1 + q1q2) b r3 = r1 – q3 r2 → r3 = a + (-q1) b – q3 [(-q2) a + (1 + q1q2) b] → r3 = (1 + q2 q3) a + (-q1 – q3 – q1 q2 q3) b . . . . . . . . . . . . . . . . . . . . . . . Sea observa que todo resto se puede escribir como un múltiplo de a más un múltiplo de b, en particular:

rn = d = x a + y b con x, y ∈Z En el ejemplo anterior, expresaremos (342, 126) = 18 como un múltiplo de 342 más un múltiplo de 126: 342 = 2 · 126 + 90 → 90 = 342 + (-2) 126 126 = 1 · 90 + 36 → 36 = 126 + (-1) 90 90 = 2 · 36 + 18 → 18 = 90 + (-2) 36 → 18 = [342+(-2) 126]+ (-2)[126 + (-1)90] → 18 = 342 + (-4) 126 + 2·90 → 18 = 342 + (-4) 126 + 2 [342 + (-2) 126] → 18 = 3·342 + (-8)126 donde se ve que x = 3 , y = -8 Observaciones: 1.- Como a y –a tienen los mismos divisores, entonces por la definición de divisor común mayor, resulta: (a, b) = (-a, b) = (a, -b) = ( -a, -b) Luego, para el cálculo del divisor común mayor, d, de dos enteros cualesquiera, no simultáneamente nulos, se puede suponer a ambos positivos. Enteros relativamente primos.

Page 50: Algebra y Logica Algebra i Apuntes

50

Definición: se dice que el entero a es primo con el entero b, o que a y b son coprimos o primos relativos, si (a, b) = 1 Proposición: Si (a, b) = 1 entonces existen enteros s, t, tales que a s + b t = 1 y Recíprocamente, si tales enteros existen, entonces a y b son coprimos. Demostración: A cargo del alumno Proposición: Sean a, b∈Z, (a, b) = 1 y a / b c entonces a/c. Demostración: (a, b) = 1 → 1 = s a + t b multiplicando ambos miembros por c∈Z: c = s a c + t b c y como por hipótesis a/ bc y a/a → a / (sc) a + t (bc) → a/c. Corolario: Si p es un entero primo y p/ bc, entonces p/b ó p/c. Demostración: 1) Si p/b entonces es obvio que se verifica el corolario. 2) Supongamos que p no divide a b y probaremos entonces que p/c. Como p es primo y no divide a b → (p, b) = 1, luego, por la proposición anterior, resulta que: p/ bc y (p, b) = 1 → p/c Corolario: Si p/ a1 a2 … ar y p es primo, entonces p/ ai para algún i =1, 2, .., r. Proposición: Si a, b, c ∈Z y (a, b) = 1 entonces existen x0, y0 ∈Z tales que: a.x0 + b.y0 = c. Es decir, la ecuación a.x + b.y = c admite al menos una solución entera. Demostración: Si (a, b) = 1 → s a + t b = 1 y multiplicando por c y asociando, es: (cs) a + (ct) b = c con lo que x0 = cs , y0 = c t, probando la existencia de soluciones x0, y0. Proposición: la condición necesaria y suficiente para que la ecuación de coeficientes enteros a x + b y = c tenga solución entera, es que el divisor común mayor de a y b sea divisor de c. Esto es: (a, b) /c. Demostración: 1) Probaremos primero que si (a, b) =d y d/c entonces la ecuación a x + b y = c admite

solución entera:

Page 51: Algebra y Logica Algebra i Apuntes

51

Sea d= (a, b) tal que d/c, entonces existe k∈Z : c = k d Por otra parte, existen enteros s, t: d = s a + t b multiplicando por k: k d = k s a + k t b → c = (ks) a + (kt) b Tomando x0 = ks ∈Z y y0 = kt ∈Z resulta que (x0, y0) es solución de la ecuación dada. 2) Recíprocamente: si a x + b y = c tiene solución, probaremos que d/c. Sea (x1, y1) una solución de la ecuación a x + b y = c → a x1 + b y1 = c Si d = (a, b) → a = a’d y b = b’d, reemplazando en la expresión anterior: a’dx1 + b’dy1 = c → d (a’x1 +b’y1) = c → d/c.

Ecuaciones DIOFÁNTICAS Las ecuaciones Diofánticas son ecuaciones de coeficientes enteros, para las que interesa determinar, si existen, las soluciones enteras. El matemático Diofanto (siglo III a.C) se ocupó de estudiar las soluciones enteras de ciertas ecuaciones, de ahí el nombre dado a estas ecuaciones. Las ecuaciones planteadas en las Proposiciones anteriores, son de ese tipo, en particular, son ecuaciones diofánticas lineales de dos incógnitas como las siguientes: 3 x + 5 y = 8 137 x – 25 y = 1 12 x + 81 y = 3 Veamos que una ecuación Diofántica del tipo ax + by = c, no tiene solución entera o admite infinitas soluciones enteras: 1) Si a = b = c = 0 es obvio que todo para de enteros (x0, y0) es solución de la ecuación, ya que 0 x0 + 0 y0 = 0 2) Si a = b = 0 y c ≠ 0, entonces no existe solución posible. 3) Si a y b no son simultáneamente nulos, la proposición anterior nos indica que la

ecuación admite al menos una solución si (a, b) / c. La siguiente Proposición muestra que si hay solución, entonces existen infinitas soluciones. Proposición: Si ax + b y = c , con a, b, c ∈Z, tiene solución entera y (x0 ,y0) es una solución cualquiera, entonces todas las soluciones de esa ecuación son de la forma:

*

td

a y y

td

b - xx

0

0

+=

= siendo d = (a, b) y t∈Z

Demostración: 1. Veamos que cualquier par de enteros de las forma indicada en * es solución de la

ecuación ax + by = c Reemplazando en la ecuación, según *, resulta:

=

++

t

d

a y b t

d

b - x a 00 a x0 - a

d

bt + b y0 + b

d

a t

Page 52: Algebra y Logica Algebra i Apuntes

52

= a x0 + b y0 siendo (x0, y0) una solución → = c Luego, efectivamente la forma indicada en * es solución de la ecuación. 2. Veamos ahora que toda solución de la ecuación ax + b y = c se escribe de la forma

indicada en *: Supongamos que a ≠0 y sea (m, n ) otra solución, entonces tenemos:

a x0 + b y0 = c a m + b n = c

restando, miembro a miembro, a la segunda expresión la primera: a ( m - x0) + b (n - y0) = 0 → a ( m - x0) = - b (n - y0) Como d = (a, b) → a = a' d y b = b' d siendo a' y b' coprimos Remplazando en la expresión anterior: a' d (m - x0) = - b' d (n -y0) cancelamos d en ambos miembros: a' (m - x0) = - b' (n -y0) Esto muestra que: a' / -b (n - y0) → a' / n -y0 → n - y0 = t a' → n = y0 + a' t →

n = y0 + td

a

De igual forma, tomando n - y0 = td

a → a' (m - x0) = - b' t

d

a con

a ≠ 0

→ m - x0 = - td

b →

m = x0 - td

b

Luego, una solución (m, n) cualquiera, está dada por la forma * , con t∈Z, lo que hace que entonces existan infinitas soluciones, una para cada t elegido. En resumen, conociendo una solución de la ecuación ax + by = c, se pueden conocer todas. Ejemplo 1: Consideremos la ecuación lineal diofántica 3 x + 12 y = 6 Como (3, 12 ) = 3 y 3/6, entonces existen infinitas soluciones. Fácilmente se observa que el par (-2, 1) es una solución ya que : 3 (-2) + 12 · 1 = 6 Luego las restantes soluciones serán del tipo:

+=

=

t3

3 1 y

t3

12 - 2- x

+==

t 1 y

t4- 2- x t ∈Z

Luego también son soluciones, por ejemplo:

Page 53: Algebra y Logica Algebra i Apuntes

53

Para t = 1 el par (-6, 2) Para t = 3 el par ( -14, 4) Para t = -1 el par ( 2, 0) Etc., etc. Ejemplo 2: 8 x + 12 y = 5 Como ( 8, 12) = 4 y 4 no divide a 5 → no existen soluciones para esta ecuación. Ejemplo 3: Sea la ecuación: 11 x + 4 y = 120 Como (11, 4) = 1 Expresamos d = 1, como combinación lineal de 11 y 4. 11 = 4 · 2 + 3 → 3 = 11 - 4 · 2 4 = 3 ·1 + 1 → 1 = 4 - 3 · 1 → 1 = 4 - 11 + 4 · 2 1 = 3 · 4 - 11 1 = (-1) · 11 + 3 · 4 → u = -1 y v = 3 Por otro lado, como d = 1 → c' = c, en este caso c' = 120 Luego la solución obtenida es: x0 = (-1)· 120 = -120 y0 = 3 · 120 = 360

esto es:

==

360y

120- x

0

0

Verificación: 11 (-120) + 4 · 360 = -1320 + 1440 = 120

Cualquier otra solución de la ecuación dada será de la forma:

+==

t11· 360 y

·t 4 - 120- x siempre

t ∈Z Múltiplo común menor Teorema: Dados a, b ∈Z+, existe un m ∈Z+, tal que:

1) m es múltiplo de a y de b, 2) si m' es múltiplo de a y de b, entonces m' es múltiplo de m.

Demostración: Sea d = (a, b) → a = d · a', b = d · b' siendo (a', b') = 1 Sea m = a · b' → m es múltiplo de a, pero m = a' · d · b' → m es múltiplo de b Luego m reúne la condición 1) Supongamos que m' ∈Z+: m' es múltiplo de a y es también múltiplo de b → m' = k1 a , m' = k2 b con k1, k2 ∈ Z → m' = k1 d a' , m' = k2 d b' → k1 d a' = k2 d b' , esto es k1 a' = k2 b' → a' /k2b' pero siendo (a', b') = 1 → a'/ k2 luego existe c∈Z : k2 = a' c → m' = a' d b' c m' = a' c b y como a' b = m →

Page 54: Algebra y Logica Algebra i Apuntes

54

m' = m c → m/m' → m' es múltiplo de m. Definición: El entero m de la proposición anterior es el múltiplo común menor de a y b. Lo indicamos: m = [a, b]

De acuerdo a la proposición anterior m = a b' y b' = d

b, reemplazando entonces, es:

m = d

b a → [a, b] =

b) (a,

b · a

Ejemplo: [128, 36] = 36) (128,

36 · 128 → [128, 36] =

2

4608 → [128, 36] =

2304 Como todo múltiplo de un entero a , lo es también de (-a), claramente se verifica:

[a, b] = [a, -b] = [-a, b] = [-a, -b] Otra definición : dados dos enteros no nulos, el menor múltiplo común de ambos, es el menor entero positivo m, tal que es múltiplo de los dos enteros dados. M(a) ={n·a, n ∈Z} → M+(a) = {n·a, n∈Z+} M(b) ={n·b, n ∈Z} → M+(b) = {n·b, n∈Z+} → M+ (a) ∩ M+(b) ≠ ∅ pues al menos a·b = a·b∈ M+ (a) ∩ M+(b) Así, el múltiplo común menor es el primer elemento del conjunto [M+ (a) ∩ M+(b)]. De modo equivalente a como hemos definido el múltiplo común menor de dos enteros dados, es posible definir el divisor común mayor: Definición: dados dos enteros a y b, un número entero d se dice un divisor común mayor de a y b si verifica las siguientes propiedades: 1) d/a y d/b 2) Si d' es un entero tal que: d'/a y d'/b, entonces d'/d. Nótese que si d y d' son dos divisores comunes mayores entre a y b, entonces d/d' y d'/d, por lo cual son asociados, esto es: d = ± d'. Luego, según esta definición, el divisor común mayor de a y b es único, salvo el signo. Teorema Fundamental de la Aritmética: Todo entero distinto de ±1 y 0, se puede escribir como producto de ±1 por enteros primos positivos y esa descomposición es única, salvo el orden. Demostración:

Page 55: Algebra y Logica Algebra i Apuntes

55

Basta hacer la demostración para enteros positivos. Entonces: sea a ∈Z, a >1 Si a = 2 → a es primo → a = 1 · 2, luego 2 se escribe de la forma indicada. Sea a > 2 y supongamos por Hipótesis Inductiva que la descomposición en factores primos existe para todo m, 2 ≤ m < a, probemos entonces que también existe para a: Si a es primo, no hay nada que probar. Si a no es primo, entonces admite al menos un divisor no trivial, supongamos entonces que a = b · c con b, c ∈Z y además, 1 < b < a , 1 < c < a Por la hipótesis inductiva, tanto b como c pueden escribirse como producto de primos positivos, luego a también. Probaremos ahora que esa descomposición es única: Supongamos que a = p1.p2. p3. …pn con pi primos, y que también a = q1. q2 . q3 … qr qi primos Probaremos por inducción sobre n, el número de factores de la primera descomposición. Si n = 1: a = p1 entonces q1. q2 . q3 … qr debe tener un solo factor, podemos suponer que es q1: p1 = q1 y n = r = 1 Por Hipótesis inductiva supongamos que la descomposición es única para (n-1) factores, probaremos que lo es para n factores p1.p2. p3. …pn = q1. q2 . q3 … qr (*) → p1 / q1. q2 . q3 … qr

siendo p1 un número primo → p1/qi para algún i = 1, 2,…, r. Podemos suponer i =1 → p1/ q1 → p1 = q1. Entonces la expresión (*) se reduce a : p2. p3. …pn = q2 . q3 … qr

con lo cual ahora tenemos (n-1) factores en la descomposición, por lo que se cumple la proposición por la H.I. Luego, ordenando los factores de la derecha, resultan respectivamente iguales a los de la izquierda y p2 = q2, p3 = q3, ….. y n = r Este Teorema Fundamental de la Aritmética, era ya conocido por Euclides que, aunque es razonable suponer que conocía la demostración de la unicidad, pues está implícita en su obra, sólo dio la de la descomposición. La demostración general basada en las ideas de Euclides fue hecha recién por Gauss (1777 - 1855). Otras demostraciones no basadas en el concepto de divisor común mayor, fueron dadas recién a principios del siglo XX. O sea, pasaron 22 siglos antes que se diera una demostración distinta a la esbozada por Euclides. Veamos ahora cuántos números enteros primos hay: Proposición: Existen infinitos números primos. Demostración: Bastará probar que existen infinitos primos positivos. Supongamos, por absurdo, que el número de primos es finito. Entonces la lista de los primos existentes será: p1, p2, p3, …, pn

Page 56: Algebra y Logica Algebra i Apuntes

56

Consideremos el número entero: a = p1· p2· p3 ·…· pn +1 Como a > 1, puede descomponerse en ±1 por primos positivos, al menos un factor primo p. Ese p debe ser alguno de los primos de la lista, supongamos p = pk. Luego pk/a y como pk / p1· p2· p3 ·…· pn → pk / a - p1· p2· p3 ·…· pn → pk/1 Absurdo! Luego existen infinitos enteros primos. Ahora sabemos que hay infinitos primos. Pero ¿los conocemos realmente? ¿es fácil reconocer si un entero dado es o no primo? Si queremos determinar la primalidad de un número natural n, la forma más ingenua es verificar que no es divisible por ningún número entero menor que él, a partir del 2. Pero obsérvese que podemos limitar la búsqueda de posibles divisores a los números primos menores que n. De todas maneras habrá que realizar muchos cálculos y debemos contar previamente con una buena lista de primos. Podemos aliviar un poco mas la situación, a partir del siguiente resultado: Proposición: Si n es compuesto, n es divisible por algún primo menor o igual que su raíz cuadrada. Demostración: sea n >1, por el Teorema Fundamental, puede descomponerse en primos. Sea p el menor de esos factores: n = p · b Si n no es primo → p ≤ b , pues p es el menor divisor propio de n.

Entonces : p · p ≤ p · b → p2 ≤ n → p ≤ n .

Esto es, n es primo o admite un divisor primo menor que n . Entonces podemos reducir la búsqueda de eventuales divisores primos de un número, a aquellos menores o iguale que su raíz cuadrada. Si ninguno de ellos lo divide, entonces el número es primo. Criba de Eratóstenes El método de la Criba de Eratóstenes permite confeccionar tablas de primos. Es llamado así por Eratóstenes de Cirene (278-194 a.C), matemático griego que construyó la primera tabla de primos conocida. Supongamos que queremos hacer la tabla de todos los primos menores o iguales que un cierto m. Para ello se escriben todos los números naturales entre 1 y m y procedemos así: primero suprimimos el 1 (tachamos); luego, a partir de 2, sin incluirlo, tachamos todos sus múltiplos hasta llegar a m. A continuación, y a partir del 3, que no quedó tachado, tachamos todos sus múltiplos hasta llegar a m. Y así siguiendo, por cada número que no se tacha, se tachan sus múltiplos. Por ejemplo, para obtener la tabla de primos menores o iguales que 50: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

Page 57: Algebra y Logica Algebra i Apuntes

57

Tenemos así los primos menores que 50 y observamos que son 15. Cómo encontrar la descomposición en factores primos de un entero a dado? No hay un método general de factorización. Teóricamente todos los primos que dividen a un a>1 se pueden determinar directamente dividiendo a a por los primos menores que

él o aplicando la Proposición anterior, bastará con probar con primos p ≤ a .

Supongamos que así obtenemos los primos p1, p2, …, ps tales que pi /a, pi ≤ a , ∀i = 1, 2, …, s Entonces: a = p1· p2 · ··· · ps · c Si c ≠1, razonamos análogamente a lo que hicimos con a y observamos entonces que c

es primo ( c > a ) ó c admite un divisor primo p ≤ c . Siendo c < a . Así obtenemos todos, eventualmente todos excepto el c, que es el cociente de a por p1· p2 · ··· · ps. Ejemplo: Descomponer en factores primos : -3540.

Como 3540 =59,49… debemos probar de dividir 3540 por los primos menores o iguales que 59: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 Los divisores primos de 3540 son: 2, 3, 5 y 59 3540 2 3540 = 22 · 3 · 5 · 59 1770 2 885 5 177 3 59 59

1

En general a∈Z se escribe entonces como. a = ± s21 es

e2

e1 p ... p.p con pi

primos positivos, i = 1, 2, …, s y ei ∈Z , ∀i = 1, 2, …, s. Ejemplo: Escribir 7320 como producto de primos positivos. Es obvio que 10 / 7320 luego 7320 = 732 · 10 = 732 · 2 ·5

Los factores primos divisores de 732 son los p ≤ 732 = 27.0…, luego p< 27. Esto es: 2, 3, 5, 7, 11, 13, 17, 19 y 23 podrían ser divisores de 732. Se observa que 2/732 y 3/732 → 732 = 2 · 3 · c 732 = 2 · 3 · 122 → 732 = 2 · 3 · 2 · 61 → 7320 = 23 · 3 · 5 · 61 ¿Cuántos divisores tiene 7320?

En general, si a = s21 es

e2

e1 p ... p.p , cualquier divisor b de a, debe ser de la forma:

b = n21 fn

f2

f1 p · · ·p·p con 0 ≤ fi≤ ei Entonces a = b ( nfff −−− n2211 e

ne2

e1 p ···p · p ) 0 ≤ ei-f i

≤ei . Veamos cuales y cuantos son entonces los divisores de 7320 = 23 · 3 · 5 · 61.

Si b/ 7320 → b = 4321 fff 61 · 5 · 3 · 2f con: 0≤f1≤3; 0≤f2≤ 1; 0≤f3 ≤1; 0≤f4 ≤1

Page 58: Algebra y Logica Algebra i Apuntes

58

Entonces, son divisores de 7320: (±1) 21 · 30 · 50 · 610 = ±2 (±1) 22 · 30 · 50 · 610 = ±4 (±1) 23 · 30 · 50 · 610 = ±8 (±1) 21 · 31 · 50 · 610 = ± 6 (±1) 22 · 31 · 50 · 610 = ±12 (±1) 23 · 31 · 50 · 610 = ±24 (±1) 21 · 30 · 51 · 610 = ± 10 (±1) 22 · 30 · 51 · 610 = ±20 (±1) 23 · 30 · 51 · 610 = ±40 (±1) 21 · 30 · 50 · 611 = ± 122 (±1) 22 · 30 · 50 · 611 = ±244 (±1) 23 · 30 · 50 · 611 = ±488 (±1) 21 · 31 · 51 · 610 = ±30 (±1) 22 · 31 · 51 · 610 = ±60 (±1) 23 · 31 · 51 · 610 = ±120 (±1) 21 · 31 · 50 · 611 = ±366 (±1) 22 · 31 · 50 · 611 = ±732 (±1) 23 · 31 · 50 · 611 = ±1464 (±1) 21· 31 · 51 · 611 = ±1830 (±1) 22 · 31 · 51 · 611 = ±3660 (±1) 23 · 31 · 51 · 611 = ±7320 (±1) 21· 30 · 51 · 611 = ±610 (±1) 22 · 30 · 51 · 611 = ±1220 (±1) 23 · 30 · 51 · 611 = ±408 (±1) 20 · 30 · 50 · 611 = ±61 (±1) 20 · 31 · 50 · 610 = ±3 (±1) 20 · 30 · 51 · 610 = ±5 (±1) 20 · 31 · 51 · 610 = ±15 (±1) 20 · 30 · 51 · 611 = ±305 (±1) 20 · 31 · 51 · 611 = ±915 (±1) 20 · 31 · 50 · 611 = ± 183 (±1) 20 · 30 · 50 · 610 = ±1

se observa que son 64 divisores.

En general, el número de divisores positivos de un entero a = s21 es

e2

e1 p ... p.p , es:

(e1+1) · (e2 +1) · ·· (es + 1)

En el ejemplo: (3+1) · (1+1) · (1+1) · (1+1) = 32 Congruencias Hemos definido la relación de congruencia módulo m en Z: a ≡ b (m) ↔ a – b = k . m Esto es, dos enteros a y b son congruentes módulo m si la diferencia entre ambos es un múltiplo de m. Observación: es claro que si a ≡ b (m) → a ≡ b (-m)

Sea ℜ : Z → Z la relación definida por: a ℜ b si a y b arrojan el mismo resto al dividirlos por m ( tomando un m fijo, m ≥ 2), esto es: a = k1 . m + r con 0 ≤ r < m

b = k2 . m + r con 0 ≤ r < m

Veamos que esta relación recién definida y la congruencia módulo m son la misma relación.

Page 59: Algebra y Logica Algebra i Apuntes

59

En efecto: a ≡ b (m) → a – b = k . m → a = k . m + b con b<m o b≥m 1) si b < m → b = 0 . m + b de modo que a y b arrojan en mismo resto b, al dividir por m. 2) si b ≥ m → b = k’.m + r y 0 ≤ r < m

como a = k.m + b → a = k . m + (k’.m + r) → a = (k+k’).m + r luego a arroja el mismo resto que b al dividirlos por m. Observaciones: 1) a ≡ b (m) ↔ a ≡ b (-m) entonces podemos tomar siempre m ≥ 0 2) si m = 0 → a ≡ b (m) ↔ a = b Proposición: Cada a ∈Z es congruente módulo m con uno y sólo uno de los enteros 0, 1, 2, …, m-1. Demostración: a = k . m + r → a ≡ r (m) siendo 0 ≤ r < m → 0 ≤ r ≤ m-1

Además, los enteros 0, 1, 2, …, m-1 no son congruentes entre sí módulo m → Ca = Cr y r ∈{0, 1, 2, 3, …, m-1} Proposición: Si a ≡ b (m) y c ≡ d (m) entonces:

1) a + c ≡ b + d (m) 2) a . c ≡ b . d (m)

Demostración: 1) si a ≡ b (m) entonces a = q1 m + r1 y b = q2 m + r1 si c ≡ d (m) entonces c = q3 m + r2 y d = q4 m + r2 Luego a + c = (q1 + q3) m + (r1 + r2) b + d = )q2 + q4) m + (r1 + r2) → a + c ≡ b + d (m) 2) a .c = (q1 m + r1) (q3 m + r2) a . c = q1 q3 m

2 + q1 m r2 + r1 q3 m + r1 r2 a . c = (q1 q3 m + q1r2 + r1 q3) m + r1 r2 (*) por otra parte: b . d = (q2 m + r1) (q4 m + r2) b . d = q2 q4 m

2 + r1 q4 m + q2 m r2 + r1 r2 b . d = (q2 q4 m + r1 q4 + q2 r2 ) + r1 r2 (**) De (*) y (**) resulta a . c ≡ b. d (m) Así la congruencia módulo m es compatible con la suma y con el producto. Corolario 1: Si ai ≡ bi (m) i = 1, …, s

Entonces ∑=

s

1iia ≡ ∑

=

s

1iib (m) y ∏

=

s

1iia ≡ ∏

=

s

ii

1b (m)

(Puede probarse por inducción sobre s)

Page 60: Algebra y Logica Algebra i Apuntes

60

Corolario 2: Si a ≡ b (m) → an ≡ bn (m) Corolario 3: Si a + c ≡ b + c (m) → a ≡ b (m) Esto es: vale la Ley de Cancelación en la suma de congruencias. Demostración: si a + c ≡ b + c (m) → (a + c) – (b + c) = k m → a – b = k m

∴ a ≡ b (m) Observación: En cambio, no vale la Ley de Cancelación en el producto de congruencias. El siguiente contraejemplo lo muestra: 3 . 4 ≡ 6 . 3 (6) sin embargo 4 no es congruente con 6 módulo 6. La siguiente proposición muestra en que condiciones particulares es posible cancelar un factor en una congruencia: Proposición: a . c ≡ b .c (m) si y sólo si a ≡ b (m/d) siendo d = (c, m) Demostración: 1) Sea a .c ≡ b.c (m) a .c = q1 (m) + r b.c = q2 (m) + r → a.c – b.c = k.m → c (a – b) = k.m (*) Por otra parte , siendo d = (c,m) es : c= c’.d y m = m´.d Dividiendo entonces (*) por d, resulta: c’ (a-b) = k.m’ luego m’/ c’.(a-b) → m’/ a-b → m’.h = a-b con h∈Z

→ a ≡ b (m’) → a ≡ b

d

m

2) Si a ≡ b

d

m → a-b = k.m’

multiplicando por c: c.(a-b) = c.k.m’ → c.(a-b) = c’.d.k.m’ asociando convenientemente: c (a-b) = k.c’.m → c.a – c.b = (k.c’)m

→ ac ≡ bc (m) Corolario: Si c.a ≡ c.b (m) y (c,m) = 1 → a ≡ b (m) (Probarlo como ejercicio) Esto nos dice que en una congruencia se pueden cancelar factores que son coprimos con el módulo m. Proposición: Si a, b son enteros positivos, entonces a ≡ b (m) si y sólo si a(m) = b(m) Demostración: 1) Si a ≡ b (m) es, por definición a – b = k . m con k∈Z Si a = q1 . m + r1 con r1 < m → a(m) = r1 Si b = q2 . m + r2 con r2 < m → b(m) = r2 a – b = (q1 – q2) m + (r1 – r2)

Page 61: Algebra y Logica Algebra i Apuntes

61

Por la unicidad del cociente y el resto, (r1 – r2) = h . m con h ∈Z Pero r1 – r2 < m por lo tanto h = 0 → r1 – r2 = 0 → r1 = r2 Esto es, a (m) = b(m) 2) Recíprocamente, supongamos que a(m) = b(m) entonces ambos enteros arrojan el mismo resto al dividir en m: a = q1 m + r y b = q2 m + r → a – b = (q1 – q2) m → a ≡ b (m) Con lo que queda probada la proposición. Aplicaciones Problema 1.- Multiplicar, módulo 5 los números 7421 y 124592. Solución: En lugar de hacer la multiplicación directamente, tomamos los restos módulo 5: 7421 = 1484 · 5 + 1 → 7421 ≡ 1 (5) 124592 = 24918 · 5 + 2 → 124590 ≡ 2 (5) Luego 7421 · 124590 = 1 · 2 ≡ 2 (5) Problema 2.- Demostrar que el entero a.(a2 –1) es múltiplo de 3. Solución: Obsérvese que los restos que es posible obtener al dividir un entero por 3 son: 0, 1 ó 2, entonces a ≡ 0 (3) ó a ≡ 1 (3) ó a ≡ 2 (3) 1) si a ≡ 0 (3) → a es múltiplo de 3, luego a (a2-1) es múltiplo de 3. 2) si a ≡ 1 (3) → a.a ≡ 1.1 (3) → a2 ≡ 1 (3) → a2 – 1 es múltiplo de 3, luego se verifica la proposición. 3) si a ≡ 2 (3) → a2 ≡ 22 (3) → a2 ≡ 4 (3) ≡ 1 (3) → a2 –1 3s múltiplo de 3, lo que verifica también la proposición. Problema 3.- El resto de dividir el entero a en 7 es 5. ¿Cuál es el resto de dividir (a –15) en 7? Solución: Por hipótesis a = q1 . 7 + 5 → a ≡ 5 (7) Debemos calcular r : a – 15 = k . 7 + r con 0 ≤ r < 7 O, lo que es lo mismo, r ≡ a – 15 (7) Veamos: como a ≡ 5 (7) y , siendo -15 ≡ -8 (7) es a – 15 ≡ -3 (7) pero –3 ≡ 4 (7) luego a – 15 ≡ 4 (7) → r = 4 Por lo tanto, el resto de dividir (a-15) en 7 es 4. Problema 4.- Probar que 10624 es divisible por 16. Solución: Dividiendo 106 entre 16 se obtiene: 106 = 16 x 6 + 10 → 106 ≡ 10(16)

→ 1062 ≡ 102 (16) ≡ 4 (16) → 1063 ≡ 4 x 10 (16) ≡ 8 (16) → 1066 ≡ 82 (16) ≡ 0 (16)

Page 62: Algebra y Logica Algebra i Apuntes

62

→ (1066)4 ≡ 0 (16) → 106 24 ≡ 0 (16) por lo tanto 16 / 10624

Así resulta que efectivamente 16 es divisor de 10624. Hemos abierto el campo de la aritmética modular. Podemos hacer operaciones ( sumas y productos) módulo m. Tiene también sentido plantear ecuaciones de congruencia del tipo c x ≡ b(m). Proposición: Si (c,m) = 1, la congruencia c x ≡ b (m) tiene solución entera y dos soluciones cualesquiera, x1 , x2 , son congruentes entre sí módulo m. Demostración: como (c,m) = 1 → 1 = s.c + t.m con s, t ∈Z multiplicando por b: b.s.c + b.t.m = b → b – bsc = (b.t) m Esto es: b ≡ b s c (m) → c.(bs) ≡ b (m) luego x = bs es solución de la ecuación c x ≡ b (m). Por otra parte si x1 y x2 son soluciones de la ecuación, entonces: c x1 ≡ b (m) y c x2 ≡ b (m) por lo tanto c x1 ≡ c x2 (m) siendo (c,m) = 1 por lo que vale la Ley de Cancelación, entonces x1 ≡ x2 (m) Así queda demostrada la proposición. Ejemplo: Sea la congruencia: 3 x ≡ 2 (5) Esta congruencia tiene solución entera, ya que c =3 y b =5 son relativamente primos. 1 1 2 5 = 1 · 3 + 2 → 2 = 5 + (-1) ·3 5 3 2 1 3 = 1 ·2 + 1 → 1 = 3 - 2 = 3 -5 +3 → 1 = 2·3 + (-1)·5 2 1 0 s = 2 y t = -1 → x = b·s → x = 2·2 → x= 4 es solución. En efecto: 3·4 ≡ 2 (5) Cualquier otra solución será: x1 ≡ 4(5) , por ejemplo x1= 24 Ejercicio: 4 x + 3 ≡ 4 (5) A cargo del lector.

Page 63: Algebra y Logica Algebra i Apuntes

63

Números Complejos

Definición: Un número complejo es un par ordenado (a,b) de números reales. El conjunto C de los números complejos coincide, por lo tanto, con el conjunto R2 de todos los pares ordenados de números reales y, geométricamente, un complejo puede verse como un punto o como un vector en el plano cartesiano. Aunque como conjuntos C y R2 sean iguales, desde el punto de vista algebraico, son diferentes. En R2 estamos interesados en la suma de vectores y en la multiplicación de éstos por un número real. En C interesa esa misma suma de complejos (vectores) y la multiplicación de complejos, como veremos más adelante. Módulo de un complejo Definición: el módulo de un complejo, o valor absoluto, es su distancia al origen. Si z = (a,b)

entonces escribimos : z = 22 ba + . Ejemplo: Sea b= (-3,1) ∈C, lo representamos en el plano y calculamos su módulo:

b= 22 1)3( +− → b= 19+ → b= 10

Suma de números complejos Definición: Sean z = (a, b) y w = (c, d), números complejos. La adición o suma de complejos z + w se define: z + w = (a,b) + (c,d) = (a+c , b+d) Ejemplo: Sea z = (3, -2), w = (-1, 4) → z + w = [ 3+(-1), (-2)+4 ]

→ z + w = (2, 2)

Gráficamente:

Esa definición coincide con la de suma de vectores en el plano.

Page 64: Algebra y Logica Algebra i Apuntes

64

Ejercicio: Calcula (3,-2) + (-1,6). Dibuja estos complejos en el plano. Indicando z= (3,-2) y

w= (-1,6), ¿qué figura forman los cuatro puntos: O=(0,0), z, w y z+w ?

Propiedades de la suma de complejos

Sean z, w y v ∈C, z = (a, b) ; w = (c,d) y v = (r, s)

1.- Asociativa: se verifica que z + (w + v) = (z +w) + v

En efecto: z + (w + v) = (a, b) + [(c, d) + (r, s)]

= (a, b) + (c+r, d+s)

z + (w + v) = [a+(c+r), b+(d+s)] por asociatividad de la suma en R

= [(a+c)+r , (b+d)+s]

= [(a+c),(b+d) ] + (r, s)

= (z + w) + v

2.- Conmutativa: se verifica que z + w = w + z

En efecto: z + w = (a, b) + (c, d)

= (a+c , b+d) por conmutatividad de la suma en R

= (c+a , d+b) luego

= w + z

3.- Existencia de neutro en C : supongamos que x = (x1 , x2) ∈C es neutro para la suma,

debe verificarse entonces que ∀ z = (a, b) ∈C : z + x = z

Luego: (a, b) + (x1, x2) = (a, b) → (a+x1 , b+x2) = (a, b) →

a + x1 = a → x1 = 0

b + x2 = b → x2 = 0 Así resulta que x = (0, 0) es neutro para la suma en C.

El complejo 0 = (0, 0) es llamado complejo nulo.

4.- Existencia de simétrico u opuesto

∀ z∈C, ∃ -z ∈C tal que z + (-z) = (0,0)

En efecto, si z = (a, b) , el simétrico es -z = (-a, -b), pues:

Page 65: Algebra y Logica Algebra i Apuntes

65

(a, b) + (-a, -b) = (a-a , b-b) = (0,0)

Ejercicio: Verifica que, ∀ u, v, w ∈ C, valen las siguientes propiedades: i) u + v = u + w → v = w (Ley de Cancelación) ii) –(u + v) = (-u) + (-v) Diferencia: La suma de un complejo z más el simétrico de otro cualquiera (-w), se llama diferencia de z menos w, e indicamos: z + (-w) = z - w Ejercicio: Verifica que la ecuación x + z = w , siendo z, w ∈ C, cualesquiera, admite como única solución: x = w – z. Multiplicación de un real por un complejo Definición: Si t∈R y z= (a,b)∈C, entonces se define tz = (ta , tb) Ejemplo: Calcular y graficar en el plano: i) 2(3,-1) ii) (-1/2)(2,3) iii) 0(-7,1/2)

i) 2 (3, -1) = (2.3, 2(-1)) = (6, -2)

Apartados ii) y iii) a cargo del lector. Ejercicio: Analiza e interpreta geométricamente la multiplicación de un real t por un complejo z. Distingue los casos t>0, t<0 y t=0. Proposición: tz= tz, para todo t∈R y z∈C.

Page 66: Algebra y Logica Algebra i Apuntes

66

Demostración: Sea z = ( a, b) → t.z = (ta, tb) → t.z= 22 )()ta( tb++

→ t.z= + )ba(t 222 + → t.z= 222 ba t +

→ t.z= tz Propiedades del producto de un real por un complejo Se verifican las siguientes propiedades, siendo t, s ∈R y z, w∈C: (Probarlas como ejercicio) i) s(tz) = (st)z ii) (s+t)z = sz + tz iii) t(z+w) = tz + tw iv) 0z = (0,0) v) t(0,0) = (0,0) vi) 1z = z Unitarios, Argumento, Forma Trigonométrica Siendo z=(a, b) un complejo no nulo (esto es, z ≠ (0,0)), vamos a describir el complejo

z

z, en módulo, dirección y sentido.

Calculemos primero el módulo de z: z= 22 ba ++

Luego z

z =

22 ba

b) (a,

+ →

z

z =

++ 2222 ba

b;

ba

a

Calculemos ahora la norma de este complejo:

2222 ba

b ;

ba

a

++=

2

22

2

22 ba

b

ba

a

++

+

→ z

z =

22

22

ba

ba

++

→ z

z = 1

Por otro lado, siendo zun real positivo, → z

1 es también un real positivo < 1

Por lo tanto, la dirección de z

z y su sentido, coinciden con el de z.

Page 67: Algebra y Logica Algebra i Apuntes

67

Definición: Cualquier complejo de módulo 1 es llamado unitario .

Dado un complejo no nulo z, el complejo z

z es el unitario de z. Todo complejo

unitario pertenece a la circunferencia de centro en el origen y de radio 1, por lo tanto es de la forma (cosθ, senθ). A un ángulo θ de este tipo se le llama argumento de z. Cualquier otro ángulo de la forma θ+ 2kπ (en radianes) es también un argumento del mismo z. Luego, para todo complejo no nulo z, se puede escribir:

)sen,(cos z

z θθ= ó )sen ,(cos z z θθ= ó ) sen z ,cos z ( z θθ=

Cada una de estas expresiones es llamada forma polar o forma trigonométrica del número complejo z. El argumento 0 ≤ θ ≤ 2π es llamado argumento principal. y )sen ,(cos z z θθ=

)sen,(cos z

z θθ=

Ejemplo: Siendo z = (-3,5), se tiene que z= 22 5)3( +− = 34≅5,8310.

Luego, )34

5 ,

34

3( 34 z

−= Por lo tanto cos θ = 34

3− ≅ - 0,5145 y

sen θ = 34

5 ≅ o,8575. Como θ es del 2ª cuadrante, podemos calcular directamente en

la calculadora: θ = arc cos 34

3− = 120,96º.

Luego: z = (-3,5) = 34 (cos 120,96º, sen 120,96º).

Multiplicación de complejos unitarios Cada complejo unitario, (cos α, sen α), define una rotación de centro en el origen y de amplitud α. Por definición, multiplicar dos complejos unitarios es equivalente a componer las rotaciones que ellos definen, o sea, sumar sus ángulos. Por

Page 68: Algebra y Logica Algebra i Apuntes

68

lo tanto, el producto de dos complejos unitarios es un nuevo complejo unitario cuyo argumento es la suma de los argumentos de los dos factores dados:

(cos α, sen α) .(cos β, sen β) = [cos (α+β), sen (α+β)]

Y w

zw z z = (cos α, sen α) w = (cos β, sen β) X z.w = [cos(α+β), sen (α+β)]

Ejemplo: (0,1) . 2

1 ,

2

1

−= (cos 135º, sen 135º) . (cos90º , sen 90º)

= (cos (135º+90º) , (sen (135º+90º)) = (cos 225º , sen 225º)

= 2

1- ,

2

1

Veamos como se comporta algebraicamente el producto de complejos unitarios. Sean z = (a,b) = (cos α, senα) y z’= (c,d) = (cosβ, senβ), complejos unitarios, entonces: z . z’ = (cos α, senα). (cosβ, senβ) → z. z’ = ([cos (α+β), sen (α+β)] y, por las fórmulas usuales de seno y coseno de la suma de dos ángulos resulta: z . z’ = (cosα cosβ - sen α sen β; sen α cos β + cos α sen β) z . z’ = (ac – bd ; bc + ad) Esto significa que para complejos unitarios, la definición de producto equivale a :

(a , b) . (c , d) = (ac – bd , ad + bc) Multiplicación de complejos en general Definición: El producto de dos complejos no nulos cualesquiera z y w, es otro complejo cuyo módulo es el producto de los módulos y cuyo unitario es el producto de los unitarios de cada uno de los factores. Esto es, si z = (a , b) y w = (b , c), tenemos: (a , b) . (c , d) = z.w = zw. (unitario de zw)

(a ,b ) . (c , d) = zw . [(unitario de z). (unitario de w)]

Page 69: Algebra y Logica Algebra i Apuntes

69

= zw .

w

d;

c .

z

b;

z

a

w

=

+w z

bc ad ,

w z

bd - ac w z

= (ac – bd , ad + bc) Esto muestra que la definición dada para multiplicación de unitarios vale también para cualquier par de complejo. En resumen: Para complejos cualesquiera, el producto está definido por: (a , b) . (c , d) = (ac – bd , ad + bc) Para complejos no nulos, esto equivale a: multiplicar módulos y sumar argumentos. Ejercicio: Verifica que la multiplicación de complejos es conmutativa, asociativa y distributiva respecto de la suma. Existencia de Neutro multiplicativo, inverso, conjugado

•• Existe neutro para la multiplicación de complejos? Cuál?

Se trata de buscar un complejo w que satisfaga que w.z = z , ∀ z ∈ C. Si tal complejo existe, será de la forma: w = w(cos α, sen α).

Si z =z(cos β, sen β), entonces: w. z tendrá como módulo, el producto de los módulos de w y z , y por argumento, la suma de los argumentos.

Así: w. z=w.z → w.z= z por lo tanto w= 1

Respecto de los argumentos: α+ β =β → α= 0

Por lo tanto: w = 1 ( cos 0, sen 0) o, lo que es lo mismo: w = (1, 0)

•• Existe el inverso de z, ∀ z ∈ C, z ≠ 0?

El inverso de z, si existe, tendrá que ser un complejo z' tal que z .z' = (1, 0), esto es, igual al neutro.

Razonando como en el caso anterior, z' será de la forma : z' = z'(cos δ, sen δ)

Luego: z.z'=z.z' → z.z'= 1 → z-1=z'

Respecto de los argumentos: β+ δ = 0 luego δ = -β

Así, z' tiene por argumento, el opuesto del argumento de z y por módulo el inverso del módulo de z.

Llamando z' = z-1, resulta que ∀ z∈ C, z≠(0, 0), es z-1=z-1(cos( -β), sen (-β) )

Ejemplo: Si z =

−2

1,

2

1 determinar z-1.

Page 70: Algebra y Logica Algebra i Apuntes

70

El módulo de z es: z= 22

2

1

2

1

+

− → z= 1

Cos β = 1

2

1− → β = 135º

Luego z-1 = (cos (-135), sen (-135)) → z-1 = cos 225º, sen 225º)

Veamos como es la expresión del inverso de un complejo en forma de par ordenado:

Sea z = (a, b) ∈ C, su inverso será otro complejo (x, y), tal que (a, b) . (x, y) = (1, 0)

Luego: (ax – by , ay + bx) = (1, 0) →

=+=

0 x b y a

1 y b - x a → (*)

=+=

0 y a x b

1 y b - x a →

a)(por 0

) bpor ( 2

2

=+=−

yaabx

bybbax

( ) b y a - b 22 =−

→ y = ( )22 ba

b

+− → y = ( )22 ba

b

+−

Retomando el sistema (*), ahora multiplicamos la primera ecuación por a y la segunda por b:

0 aby b

a y ab - x a2

2

=+=

a x )b a( 22 =+ → 22 b a

a x

+=

Así: z-1 = (a, b)-1 =

++ 2222 b a

b- ,

b a

a

Definición: Siendo z = (a , b), llamamos conjugado de z, al complejo z = (a, -b) Interpretemos geométricamente el conjugado de un complejo:

Ejemplo: w = (-1/2, 5) → w = (-1/2, -5)

Page 71: Algebra y Logica Algebra i Apuntes

71

Proposición: Siendo z ≠ (0 , 0), entonces: 2z

z

z

1 =

Demostración: Calculemos : z . z = (a, b) . (a, -b) = [ a.a -b.(-b) ; a(-b)+ b.a ] = ( a2 + b2 ; 0 ) = z 2

Luego: z . z = z 2 → z

1

z

z2

= → z-1 = 2

z

z

Cociente de complejos

Definición: El cociente w

z de complejos, (siendo w ≠ 0), es el producto de z por el

inverso

de w. Por lo tanto: 2w

wz.

wz

w1

x. ==

Ejemplo: Calculemos ( )( )4 , 3

2 , 1.

( )( )4 , 3

2 , 1 =

24) , (3

4)- (3, )2 , 1(

= 16 9

6) 4- , 8 3(

+++

=

25

2 ,

25

11

Los complejos como “cuerpo” de números Hasta aquí hemos definido dos operaciones en C, suma y multiplicación, de acuerdo a las reglas:

(a , b) + (c , d) = (a+c , b+d) (a , b) . (c , d) = (ac – bd , ad + bc)

De acuerdo con las propiedades que esas operaciones verifican, resulta que C tiene estructura de cuerpo. Forma binómica o algebraica de un complejo Sea X = {z ∈ C: z = (x, 0)}, esto es el eje X. Sea f : R → X, tal que f(x) = (x , 0). Fácilmente puede verificarse que f es una biyección de R sobre el conjunto X de los complejos de la forma (x, 0): En efecto si x, y ∈R, entonces f(x) = (x , 0) , f(y) = (y , 0) Si f(x) = f(y) → (x ,0) = (y ,0) → x = y por lo que f es inyectiva

Page 72: Algebra y Logica Algebra i Apuntes

72

Por otra parte: ∀ (x , 0)∈ X, ∃ x ∈R : f(x) = (x ,0) luego f es sobreyectiva Así f: R → X es una función biyectiva. Además, para t, x, y ∈ R se verifica: i) f(x + y) = f(x) + f(y) ii) f(x.y) = f(x). f(y) iii) f(t x) = t. f(x) (Probar como ejercicio) La función biyectiva anterior nos permite identificar el conjunto R de los números reales con el X, de los complejos de la forma (x , 0). En virtud de esa identificación escribiremos: (x , 0) = x en particular: (0 , 0) = 0 y (1 , 0) = 1 El número i Nos concentramos ahora en el eje Y. Todo punto (0 , b) del eje Y es un múltiplo del

complejo unitario (0 , 1) = (cos 2

π , sen

2

π ), el cual, de ahora en más llamaremos i, o

sea: i = (0 , 1)

Entonces, cualquier complejo (a , b) se puede escribir: (a , b) = (a , 0) + (0 , b) = a (1 , 0) + b (0 , 1) = a + bi →

(a , b) = a + bi

Esta es la llamada forma binómica o algebraica del complejo z = (a , b)

Obsérvese que i2 = i . i = (cos

+

22

ππ, sen

+

22

ππ )

i2 = (cos π , sen π ) = (-1,0) → i2 = -1 Ejemplo: Siendo z = a + bi, escribir en forma algebraica: i) -z → -z = -a – bi ii) z → z = a – bi

iii) z

1 →

z

1 =

22 b a

b - a

+i

iv) z. z → z. z = (a + bi). (a – b i) → z. z = a2 – a b i + bi a – b2 i2 → z. z = a2 + b2 Ejercicio: Siendo z = (2+3i) y w = -1+5i, calcula: i) z ii) w iii) 1/z iv) z + w v) z.w vi) z/w vii) z2

Ejercicio: Dibuja en el plano el complejo genérico z (si es necesario discute casos).

Page 73: Algebra y Logica Algebra i Apuntes

73

Dibuja ahora: i) z ii) i.z iii) –i.z iv) 2i.z v) z2 Nomenclatura:

Eje X Eje real Eje Y Eje imaginario a + bi Forma algebraica del complejo (a, b)

a = Re (a + bi) Parte real del complejo (a + bi) b = Im (a + bi) Parte imaginaria del complejo (a + bi)

Un complejo de la forma bi (donde b∈R) se denomina imaginario puro. Ejercicio: Dado z ∈C, determina: i) z + z ii) z - z iii) z. z (a cargo del lector) iv) Cuándo es z = z? Observa que si z = a + bi → z = a – bi Entonces si z = z , b = - b y el único real que coincide con su opuesto es 0 ∴ z es de la forma a + 0i esto es, z es un complejo real. v) Cuándo es z = -z? (a cargo del lector)

Propiedades de la conjugación Si z y w son números complejos, valen las siguientes propiedades:

i) z z = ii) w z w z +=+

iii) w z z.w = iv) ( ) ( )nn z z = , n ∈Z

v) z1/ z/1 = (z ≠ 0) vi) z /w w/z= (z ≠ 0) Demostración:

i) Sea z = a + bi → z = a – bi → ib - a z= = a + bi

v) Si z = a + bi → z = a – bi → ib a

1

z

1

−= →

22 ba

b a

z

1

++= i

=

2222 ba

b

ba

a

++

+(1)

Por otro lado: 22222 2 ba

b

ba

a

ba

b - a

z

1

+−

+=

+= ii

entonces

2222 ba

b

ba

a z/1

+−

+= =

2222 ba

b

ba

a

++

+ (2)

Page 74: Algebra y Logica Algebra i Apuntes

74

luego de (1) y (2) resulta z1/ z/1 = La demostración de los restantes apartados queda a cargo del lector. Otra notación Todo complejo unitario es de la forma (cos α, sen α). Escribiendo este unitario en forma algebraica o binómica, se tiene: cosα + i senα. Esta expresión se simplifica escribiendo: cisα. Entonces, dado un complejo no nulo z, resulta: z = z ( cosα + i senα) = z cisα

que es otro modo de escribir un complejo en forma trigonométrica. Potencia de complejos La potencia n-ésima (n ∈N) de un complejo puede calcularse a partir de la forma binómica o algebraica del complejo o a partir de su forma polar o trigonométrica. En el primer caso, si z = a + bi, zn se puede calcular aplicando la fórmula del Binomio de Newton. Ejemplo: Sea z3 = (1 + i)3 entonces (1 + i)3 = 13 + 3 i + 3 i2 + i3 = -2 + 2 i Empleando la forma polar: (1 + i )3 = (1 + i)2. (1 + i)

= ( )[ ]2º45sen,º45cos2 ( )[ ]º45sen,º45cos2 Así, recordando que el producto de dos complejos es otro complejo cuyo módulo es el producto de los módulos de los complejos dados y su argumento es el la suma de los argumentos correspondientes, resulta:

(1 + i )3 = ( )

)90ºsen ,90º (cos 2

2 ( )[ ]º45sen,º45cos2

(1 + i )3 =

)135ºsen ,135º (cos 2

3

Observen que el complejo z3 obtenido tiene por módulo 3z y por argumento, tres

veces el argumento de z. Este razonamiento puede generalizarse para todo z ∈C y para todo n ∈N:

( ) ( )α=α n cis z cis znn

Esta expresión es conocida como la fórmula de De Moivre (1667 – 1754) Ejercicio: determinar ( -1 + i)4.

Llamando z = -1 + i → z = ( ) 22 1 1 +− → z = 2

Page 75: Algebra y Logica Algebra i Apuntes

75

El argumento de z: cos α = 2

1− → α = ¾ π o α = 135º

Luego ( -1 + i)4 = ( ) )(4.3/4 cis 24 π

( -1 + i)4 = 4 cis (3π ) ( -1 + i)4 = 4 cis π Raíces de un complejo Consideremos ahora el problema de resolver, en C, la ecuación zn = w, donde z es la incógnita y w es un complejo dado. Una ecuación de este tipo se llama ecuación binomia. Analicemos las soluciones de tal ecuación: 1) Si w = 0, la única solución a la ecuación zn = 0 es z = 0.

En efecto: si zn = 0 entonces el módulo de zn debe ser cero, esto es 0zn = →

0zn =

por lo tanto 0z =

y el argumento θ debe ser cero: θ =0 2) Si w ≠ 0, podemos escribir: w = θ cis w y z = φ cis z donde w y θ son

conocidos, mientras z y φ son las incógnitas. Así la ecuación zn = w quedará:

θ=φ cis w n cis z n →

θ=φ=

cis n cisw z

n →

π+θ=φ=

2k nw z n

→ n

2k

π+θ=φ

(k∈Z) El hecho de que k recorra el conjunto de los enteros puede dar la impresión de que existen infinitas soluciones, pero en verdad hay repeticiones. Sin embargo dando a k los valores 0, 1, 2, …, n-1 se obtienen los siguientes argumentos:

n

θ ,

n

2

πθ + ,

n

4

πθ + ,

n

6

πθ + , . . . ,

n

1)-2(n

πθ + (*)

y en consecuencia los n números complejos z1, z2, z3, . . . , zn que tienen por módulo n w y argumento igual a cada uno de los ángulos antes indicados, son las n raíces n-

ésimas de w, todas distintas entre sí. En efecto, la diferencia entre dos argumentos cualesquiera es:

n

2k

πθ +-

n

2k´

πθ +=

n

k' -k 2π

Como k y k’ son distintos y comprendidos entre 0 y n-1, su diferencia es no nula y menor en valor absoluto que n, por lo tanto no es un múltiplo entero de 2π , esto es no son ángulos congrurntes, lo que prueba que z1, z2, z3, . . . zn son distintas entre si. En cambio, tomando k ≥n, se obtendría un argumento que difiere con alguno de los indicados en (*) en un múltiplo entero de 2π y en consecuencia la raíz que corresponde a ese argumento coincide con una de las n ya encontradas.

Page 76: Algebra y Logica Algebra i Apuntes

76

Por lo tanto la ecuación binómia zn = w ( con w≠0) tiene exactamente n soluciones distintas. Conclusión:

Las soluciones de la ecuación zn = w , con w ≠0 , w = θ cis w son:

z =

+n

2k

ncis wn

πθ (k = 0, 1, 2, . . . , n-1)

Las n raíces de la ecuación binomia zn = w , con w≠0, se denominan raíces n-ésimas del complejo w. En el plano complejo ellas constituyen los vértices de un polígono

regular de n lados, inscripto en la circunferencia de centro en el origen y radio n w .

Ejemplo: resolver la ecuación binomia z4 = 1 + i 3 .

Aquí w = 1 + i 3 y lo expresamos en forma polar y resulta: w = 2 cis 60| = 2 cis 1/3π

Se tiene entonces que z = 4

2 1/3 cis 24 ππ k+

o z = 4

180260 cis 24 °+° k

luego, tomando k = 0, 1, 2, 3 obtenemos las cuatro raíces cuartas del complejo w dado:

z0 = °=°15 cis 2

4

60 cis 2 44 z1

z1 = °=°+°105 cis 2

4

180.260 cis 2 44 z0

z2

z2 = °=°+°195 cis 2

4

180.2.260 cis 2 44 z3

z3 = °=°+°285 cis 2

4

180.3.260 cis 2 44

Ejercicio: Resuelve las siguientes ecuaciones binomios: a) z3 = 3 – 2i b) z4 = -1 c) z5 = -3 + 4i Raíces de la unidad Analicemos la ecuación binomia zn = 1. Considerando 1 = 1 cis 0°, resulta entonces que las soluciones de la ecuación o las raíces n-ésimas de 1 están dadas por:

cis n

k2 π con k = 0, 1, . . . , n-1

Llamamos raíces n-ésimas de la unidad a las soluciones de la ecuación zn = 1. Obviamente una de las raíces es 1, que corresponde a k = 0. Nótese que si n es par, n = 2 t, hay otra raíz real, -1, que corresponde al valor de k = t. Si n es impar, 1 es la única raíz real.

Page 77: Algebra y Logica Algebra i Apuntes

77

Ejemplo: Calculemos las raíces cuartas de 1, o, lo que es lo mismo, determinemos las soluciones de la ecuación z4 = 1. Para k = 0: z0 = cis 0° → z0 = 1

k=1: z1 = cis 4

180.2 ° → z1 = cis 90° = (cos 90°+ i sen 90°) = i

k=2: z2 = cis 4

180.2.2 ° → z2 = cis 180° = (cos 180°+i sen180°) = -1

k=3: z3 = cis 4

180.3.2 ° → z3 = cis 270°= (cos270°+i sen270°) = -i

En el plano complejo, las raíces cuartas de la unidad representan los vértices de

un cuadrado con centro en el origen i del sistema y radio 1. -1 1

-i Las raíces n-ésimas de la unidad son particularmente interesantes pues se verifica que: Todas las raíces n-ésimas de un complejo z se obtienen multiplicando una de ellas por cada una de las n raíces n-ésimas de la unidad. En efecto, sea c es una raíz n-ésima de z (z ≠ 0) y sean w1, w2, . . . , wn son las n raíces n-ésimas de la unidad, entonces (c. wi)

n = cn . win = z . 1 = z ∀i = 1, 2, …, n

De modo que c.w1 , c. w2 , . . . , c. wn son n raíces n-ésimas de z. Además, todas ellas son distintas pues, si c. wi = c. wj → wi = wj. Así, conocida una raíz n-ésima de un número z las restantes se pueden determinar conociendo las raíces de igual orden de la unidad. Ejemplo: Por un ejercicio anterior sabemos que una raíz cuarta del complejo w =1 + i

3 es

°15 cis 2 4 . Entonces todas las raíces cuartas de w se calculan:

w0 = °15 cis 2 4 . cis 0° = °15 cis 2 4 w1 = °15 cis 2 4 . cis 90° = 4 2 cis 105°

w2 = °15 cis 2 4 . cis 180° = 4 2 cis 195°

w3 = °15 cis 2 4 . cis 270° = 4 2 cis 285° Obteniendo, obviamente, las mismas soluciones anteriores.

Page 78: Algebra y Logica Algebra i Apuntes

78

Llamemos Gn al conjunto de las raíces n-ésimas de la unidad, esto es: Gn = {u ∈ C: un = 1} Proposición: 1) si u ∈ Gn y v ∈ Gn entonces u.v ∈ Gn.

2) si u ∈ Gn entonces 1/u ∈ Gn. Demostración: a cargo del lector. Las raíces n-ésimas de la unidad pueden clasificarse en dos grupos: por un lado, las que aparecen como raíces de 1 de algún orden inferior a n, y por otro lado, las que no aparecen como raíces de 1 de algún orden inferior a n. Estas últimas se llaman raíces primitivas de la unidad de orden n. Definición: una raíz n-ésima ε de la unidad se dice una raíz primitiva de orden n si el menor exponente natural k, tal que εk = 1, es k = n. Ejemplo: Considerando las raíces de la unidad de orden cuatro que hemos calculado: 1, i, -1, -i, sólo i y –i son raíces primitivas de orden cuatro, ya que 1 es raíz de orden 1 y –1 es raíz de orden 2. Proposición: Si ε es una raíz primitiva de la unidad de orden n, entonces ε0, ε, ε2, . . . , εn-1 son las n raíces n-ésimas distintas de 1. Demostración: si ε es una raíz n-ésima de 1significa que εn = 1, entonces εk es raíz n-ésima de 1 cualquiera sea el exponente entero k, pues: (εk)n = (εn)k = 1k = 1 En particular: 1, ε, ε2, . . . , εn-1. Cómo calcular las raíces primitivas de la unidad? Proposición: Las raíces primitivas de la unidad de orden n se obtienen dando a k los valores

coprimos con n en la expresión: cis n

k2 π= cos

n

k2 π+ i sen

n

k2 π.

Ejemplo: Para obtener las raíces primitivas de la unidad de orden 6 se toma k = 1 y k =5.

Entonces: cis 6

2π = cis 60° y cis

6

5.2 π= cis 300° son las únicas

primitivas de orden 6.

Page 79: Algebra y Logica Algebra i Apuntes

79

POLINOMIOS Los alumnos están familiarizados con ecuaciones de primer y segundo grado en una indeterminada o incógnita, del tipo: a1 x + a0 = 0 a2 x

2 + a1 x + a0 = 0 y saben resolverlas. En general, se llama ecuación algebraica de grado n a la expresión del tipo: an x

n + an-1 xn-1 + . . . + a2 x

2 + a1 x + a0 = 0 (*) donde an, an-1, . . . a2, a1, a0 son números reales dados, an ≠ 0, n es un número natural y x un símbolo llamado indeterminada o incógnita. Resolver la ecuación (*) significa hallar los números t tales que, reemplazados en lugar de x, verifican la igualdad, es decir, tales que: an t

n + an-1 tn-1 + . . . + a2 t

2 + a1 t + a0 = 0 esos números se llaman raíces de la ecuación (*). El cálculo de las raíces de las ecuaciones algebraicas es un capítulo muy importante del Álgebra y uno de los más antiguos. Para estudiar este problema es conveniente comenzar por estudiar las expresiones del tipo

an xn + an-1 x

n-1 + . . . + a2 x2 + a1 x + a0

que forman el primer miembro de (*). Monomios: son expresiones algebraicas de la forma P(x) = a xn donde a es un número real, llamado coeficiente, x es la indeterminada y n es un número natural. El valor de n determina el grado del monomio. Por ejemplo: M(x) = -5 x3 es un monomio de grado tres. A(x) = ½ x2 es un monomio de grado dos. Si el coeficiente de un monomio es 1, el monomio se dice mónico.

Por ejemplo: P(x) = x7 es un monomio mónico de grado siete. Polinomios: Observen la expresión: P(x) = 2 x5 + 7 x4 + x3 – 2 x2 + 3 x – 5 es una suma de monomios. Esta suma no puede reducirse a un solo término ya que la indeterminada x tiene distintos exponentes en cada término, esto es, los términos no son semejantes. A una suma de varios monomios no semejante, la llamamos polinomio. Así P(x) es un polinomio. En forma general, un polinomio es una expresión de la forma: P(x) = an x

n + an-1 xn-1 + . . . + a2 x

2 + a1 x + a0 donde ai ∈K , siendo K el cuerpo de los números reales R , los racionales Q o los complejos C. an llamado coeficiente principal (an ≠ 0), es el coeficiente que acompaña a la indeterminada x que tiene mayor exponente (xn). Si an = 1, el polinomio se dice mónico.

Page 80: Algebra y Logica Algebra i Apuntes

80

n es el mayor exponente al que figura la indeterminada x, y define el grado del polinomio. an es el término independiente. an, an-1, . . . , a2, a1 , a0 son números reales constantes, llamados coeficientes. x es la indeterminada y sus exponentes, n, n-1, . . . ,2, 1,0 son números naturales. El conjunto de los polinomios en la indeterminada x con coeficientes en K lo indicamos con K[x]. Así como a los polinomios de un solo término se los llama monomios, a los de dos términos se los llama binomios, a los de tres, trinomios y en general, polinomios. Un polinomio se dice ordenado cuando los monomios que lo forman están escritos según las potencias crecientes o decrecientes de la indeterminada. Por ejemplo: B(x) = -2x3 – 3 x2 + x + 4 es un polinomio ordenado en forma decreciente, mientras que C(x) = -8x + 3 x2 – 5 x3 + x6 está ordenado en forma creciente. El primero de estos polinomios, B(x), es un polinomio completo, ya que a partir del mayor exponente al que está elevada la indeterminada (en este caso 3), la x figura, en cada término, elevada a cada una de las sucesivas potencias decrecientes (2, 1 y 0). El polinomio C(x) no es completo, ya que faltan los términos en x a la cero, a la cuarta y a la quinta potencia. Decimos que C(x) es un polinomio incompleto. Grado de un polinomio Sea P(x) = a0 + a1 x + a2 x2 + ……..* anx

n . Si no todos los coeficientes ai de un polinomio son nulos y n es el mayor índice tal que an≠0, n se llama grado del polinomio P(x) y se escribe gr(P(x)) = n Polinomio nulo es el polinomio de la forma P(x) = 0 xn + 0 xn-1 + . . . + 0 x + 0 o P(x) = 0 y su grado no está definido. Los polinomios de grado cero, es decir los de la forma P(x) = a0 y el polinomio nulo, se llaman polinomios constantes. Ejercicios: a) Escribe un polinomio completo de grado cinco. b) Escribe un polinomio de grado tres, cuyo coeficiente principal sea –2. c) Escribe otro polinomio de grado tres, mónico, cuyo término independiente sea 3/2. d) Escribe un polinomio de grado 4, ordenado según las potencias de decrecientes de la

indeterminada y completo. e) Escribe un polinomio de grado un y otro de grado cero. Igualdad de polinomios: dos polinomios A(x) = an x

n + an-1 xn-1 + . . . + a2 x

2 + a1 x + a0 y B(x) = bm xm + bm-1 x

m-1 + . . . + b2 x2 + b1 x +

b0 son iguales si los coeficientes de cada uno de los monomios de igual grado coinciden, esto es: n = m y an= bn , . . . ,a2=b2 , a1=b1, a0=b0

Page 81: Algebra y Logica Algebra i Apuntes

81

Suma de polinomios Definición: Sean A(x) = an x

n + an-1 xn-1 + . . . + a2 x

2 + a1 x + a0 ∈ K [x] B(x) = bm xm + bm-1 x

m-1 + . . . + b2 x2 + b1 x + b0 ∈ K [x]

Se llama suma de A(x) mas B(x) al polinomio: A(x) + B(x) = S(x) ∈ K [x] tal que si = ai + bi ∀ i = 0, 1, 2, …. Ejemplo:dados los polinomios A(x) = 3x4 + x3 – 3 x2 + 2 x – 8 y B(x) = -4 x3 + 7 x2 – 3 x + ½ la suma de ellos es otro polinomio que se calcula: A(x) = 3x4 + x3 – 3 x2 + 2 x – 8 + B(x) = -4 x3 + 7 x2 – 3 x + ½ A(x) + B(x) = 3 x4 – 3x3 + 4x2 – x – 15/2 donde cada uno de los coeficientes del polinomio suma, resulta de sumar los coeficientes de los términos semejantes. Polinomios opuestos: Para todo polinomio P(x) existe otro polinomio, que indicaremos por –P(x), tal que P(x) + (-P(x)) = 0. Estos polinomios se dicen opuestos. Por ejemplo: si A(x) es el polinomio A(x) = 3x4 + x3 – 3 x2 + 2 x – 8 entonces su opuesto, -A(x) es : -A(x) = -3x4 - x3 + 3 x2 - 2 x + 8 De modo equivalente a la suma, resolvemos una diferencia, sumando al minuendo el opuesto del sustraendo: A(x) = 3x4 + x3 – 3 x2 + 2 x – 8 - B(x) = 4 x3 - 7 x2 + 3 x - ½ A(x) - B(x) = 3 x4 + 5x3 - 10x2 + 5 x – 17/2 Producto de monomios: dados dos monomios, el producto de ambos es otro monomio cuyo coeficiente es el producto de los coeficientes y la indeterminada resulta elevada a un exponente igual a la suma de los exponentes de los monomios dados. Ejemplo: 3 x4 · 5 x2 = 15 x6 (Observa que el resultado surge naturalmente de aplicar propiedades de las operaciones con números reales). Producto de polinomios: Definición: Sean A(x) y B(x) ∈ K [x], llamamos producto de A(x) por B(x) al polinomio A(x) . B(x) = P(x) = p0+ p1x + p2 x

2 + …….. tal que pi = ∑

=+ i jkjk ba ∀i = 0, 1, 2, ….

En la práctica, el producto de dos polinomios es otro polinomio que surge de multiplicar cada monomio de polinomio multiplicando, por cada monomio del polinomio multiplicador.

Page 82: Algebra y Logica Algebra i Apuntes

82

Por ejemplo: sean A(x) = – 3 x2 + 3x4 – 8 + x3 + 2 x y B(x) = 7 x2 –3 x -4 x3 . Para multiplicar A(x) por B(x) seguiremos los siguientes pasos: . escribimos A(x) completo y ordenado y debajo de él, escribimos B(x) ordenado de la misma manera. . multiplicamos el último monomio de B(x) por cada uno de los términos o monomios de A(x), escribiendo los resultados en forma ordenada. . repetimos para cada monomio de B(x), encolumnando los términos semejantes obtenidos. . finalmente sumamos los resultados obtenidos. Entonces escribimos A(x) y B(x) ordenados: A(x) 3x4 + x3 – 3 x2 + 2 x – 8 B(x) -4 x3 + 7 x2 – 3 x . -9 x5 – 3 x4 + 9 x3 – 6 x2 + 24 x 21 x6 +7 x5 –21 x4 +14 x3 - 56 x2 -12 x7 – 4 x6 +12 x5 – 8 x4+ 32 x3 . -12 x7 +17 x6 +10x3 - 32 x4 + 55 x3 – 62 x2 + 24 x Luego A(x) · B(x) = -12 x7 +17 x6 +10x3 - 32 x4 + 55 x3 – 62 x2 + 24 x Proposición: Dados dos polinomios A(x)≠0 y B(x)≠0, se verifica: 1) si A(x) + B(x) ≠0 → gr (A + B) ≤ max.(gr(A), gr(B)) 2) si A(x) . B(x) ≠0 → gr (A.B) = gr(A) + gr (B) Ejercicio: Dados los polinomios: A(x) = x4 – 3x3-2x2 + 7x –5 B(x) = 2x3 – 5x +3 C(x) = x2 -1 Calcular, indicando en cada caso el grado del polinomio solución: a) A(x) – B(x) b) B(x) – [ -C(x) ] c) B(x) · C(x) d) A(x) · [B(x) + C(x)] Teorema: la suma y el producto tienen las siguientes propiedades, ∀A(x), B(x), C(x) ∈K [x] S1) Propiedad asociativa de la suma: A(x) + [B(x) + C(x)] = [A(x) + B(x)] +

C(x)

S2) Propiedad conmutativa de la suma: A(x) + B(x) = B(x) + A(x)

S3) Existencia de elemento neutro para la suma: A(x) + 0 = 0 + A(x) 0∈

K [x]

S4) ∀A(x) ∈K [x] , ∃ B(x) ∈K [x] tal que A(x) + B(x) = 0 siendo ai = -bi ∀i

M1) Asociatividad del producto: [A(x) . B(x)]. C(x) = A(x).[B(x) .C(x)]

M2) Conmutatividad del producto: A(x) . B(x) = B(x) . A(x)

M3) Existencia de elemento neutro para el producto:

Page 83: Algebra y Logica Algebra i Apuntes

83

el polinomio constante 1 es tal que A(x). 1 = 1 . A(x) = A(x)

D1) Propiedad distributiva del producto respecto de la suma:

A(x) .[B(x) + C(x)] = [A(x) .B(x)]+[A(x) . C(x)] Observación: En K [x] los únicos polinomios inversibles respecto de la multiplicación, son las constantes no nulas, esto es, los polinomios de la forma P(x) = a0. En efecto, supongamos que A(x) ∈K [x] tiene inverso y que B(x) ∈K [x] es ese inverso, entonces: A(x) . B(x) = 1 Luego: gr(A) + gr(B) = gr(1) = 0 → gr(A) = gr(B) = 0 y A(x) y B(x) son constantes. Así: B(x) = A-1(x) División entera de polinomios Recordemos que en el conjunto Z de los números enteros existe la división entera, esto es, dados dos enteros a y b, b≠0, existen otros dos enteros q y r , llamados cociente y resto respectivamente de dividir a por b, unívocamente determinados, tales que: a = q · b + r con 0 ≤ r ≤ | b |. Para determinar q y r se aplica el algoritmo de la división entera. Ejemplo: 343 | 12 . aquí a = 343 b = 12 q = 28 y r = 7 - 24 28 ↓ ↓ ↓ ↓ 103 dividendo divisor cociente resto - 96 7 De igual modo, en el conjunto de los polinomios en una indeterminada, existe también la división entera. Teorema: Dados los polinomios A(x) y B(x) ≠0 ∈K [x], existen dos polinomios Q(x) y R(x) ∈K [x], llamados respectivamente cociente y resto de dividir A(x) por B(x), unívocamente determinados, tales que: A(x) = Q(x) · B(x) + R(x) con gr (R(x) ) < gr (B(x)) o R(x) = 0 También aquí aplicamos el algoritmo de la división entera para hacer el cociente entre A(x) y B(x). Por ejemplo: veamos el caso de un polinomio dividido un monomio Sean A(x) = 6 x4 – 12 x3 + 2 x – 7 y B(x) = 2 x2 6 x4 – 12 x3 + 2 x – 7 | 2 x2 - 6 x4 3 x2 – 6 x → cociente

0 - 12 x3 + 2 x – 7 - 12 x3 0 + 2 x – 7 → resto

Page 84: Algebra y Logica Algebra i Apuntes

84

Analicemos el procedimiento: . Dividimos el primer monomio del dividendo (6x4) por el monomio divisor (2x2). El resultado es 3 x2 y representa el primer monomio del cociente. Multiplicamos 3 x2 por el divisor, obteniendo 6 x4 que restamos del divisor. Nos queda –12 x3 + 2x -7 . Ese nuevo dividendo es de grado mayor que el divisor, por lo que procedemos como antes, obteniendo –6 x, segundo monomio del cociente. Multiplicamos por el divisor y restamos. Nos queda 2 x –7. . Este polinomio es de grado menor que el divisor, entonces es el resto. Así: 6 x4 – 12 x3 + 2 x – 7 = (3 x2 – 6 x) · (2 x2) + 2 x – 7 A(x) = Q(x) · B(x) + R(x) Hagamos ahora una división de un polinomio por otro polinomio: A(x) = 3 x5 + 2 x4 – x + 3 y B(x) = x2 + 3 x – 1 Aquí conviene completar el polinomio A(x): 3 x5 + 2 x4 + 0 x3 + 0 x2 – x + 3 x2 + 3 x - 1 . - 3 x5 + 9 x4 - 3 x3 3 x3 – 7 x2 + 24 x – 79 → cociente 0 - 7 x4 + 3 x3 + 0 x2

- - 7 x4 - 21 x3 + 7 x2 0 + 24 x3 - 7 x2 - x - 24 x3 + 72 x2 - 24 x 0 - 79 x2 – 23 x + 3 - - 79 x2 – 237 x + 79 0 + 260 x - 76 → resto Entonces es: 3 x5 + 2 x4 – x + 3 = (3 x3 – 7 x2 + 24 x – 79) · (x2 + 3 x – 1) + (260 x - 76) A(x) = Q(x) · B(x) + R(x) Procedimiento: es como el anterior, sólo que ahora, el monomio obtenido en el primer paso, lo multiplicamos por todos los términos del divisor. ¿ Está claro verdad ? Veamos otro ejemplo: Calcular el cociente y el resto de dividir P(x) = 2 x3 – 4 x2 – 7 x + 3 por B(x) = x – 2 2 x3 – 6 x2 - 7 x + 3 x – 2 . - 2 x3 – 4 x2 2 x2 - 2x – 11 -2x2 – 7 x + 3 - - 2x2 + 4 x - 11 x + 3 - - 11 x + 22 - 19

Page 85: Algebra y Logica Algebra i Apuntes

85

Observen que el polinomio cociente tiene como coeficiente principal el mismo que el polinomio dividendo (2) y que es un polinomio de un grado menos que él (grado 2). El resto, es un polinomio de grado cero o polinomio constante. Cuando el polinomio divisor es mónico de grado uno, o sea es de la forma (x ± a), como en el ejemplo anterior, es posible determinar el cociente y el resto de la división usando la disposición práctica siguiente:

Coeficientes de P(x) → 2 -6 -7 3 Valor de a → 2 4 -4 -22

2 -2 -11 -19 → Resto

Coeficientes

del cociente

Este procedimiento se conoce como Regla de Ruffini. Cuando el resto de dividir un polinomio A(x) por otro B(x) es cero, se dice que B(x) divide a A(x). En ese caso: A(x) = B(x).Q(x) Divisibilidad en K[x] Desarrollaremos aquí una teoría de la divisibilidad de polinomios semejante a la desarrollada en Z. Relación divide Se dice que un polinomio A(x) divide a otro B(x) en K[x], si existe C(x) ∈ K[x]: B(x) = A(x) . C(x) En ese caso escribimos: A/B Si A/B se dice también que A8x) es divisor de B(x) o que B(x) es múltiplo de A(x). Propiedades de la relación divide en K[x] 1) Propiedad reflexiva: A/A para todo A(x) ∈ K[x] 2) Propiedad transitiva: Si A/B y B/C → A/C ∀ A(x), B(x), C(x) ∈ K[x] 3) A/0 ∀ A(x), ∈ K[x] 4) Si A/B y A/C → A/ S.B + T.C con S, T ∈ K[x] Polinomios unitarios Definición: Un polinomio en K [x] se dice unitario si es inversible respecto de la multiplicación. Según hemos visto los polinomios unitarios son las constantes no nulas. En relación a la divisibilidad un polinomio es unitario si y sólo si divide a cualquier otro polinomio. Proposición: dados A(x) y B(x) ∈ K[x], no nulos, las siguientes propiedades son equivalentes:

1) A(x) y B(x) tienen los mismos divisores

Page 86: Algebra y Logica Algebra i Apuntes

86

2) A(x) y B(x) difieren en un factor unitario (es decir en una constante no

nula) 3) A/B y B/A

Demostración: 1→2: Supongamos que A(x) y B(x) tienen los mismos divisores: como A/A entonces B/A → ∃ C(x) ∈K [x] : A = C . B como B/B entonces A/B → ∃ C`(x)∈K [x] : B = C`. A → A = C.C`.A → A – C.C`. A = 0 → A .(1 – C.C`) = 0 Si A ≠0 → 1 = C.C` por lo tanto C y C` son polinomios constantes. Luego A y B difieren en una constante. Si A = 0 → B = 0 y se verifica 2) 2 →3: Supongamos que A = k.B con k∈K , k≠0 entonces B/A Además, siendo k∈K , ∃k-1 tal que k-1. A = B → A/B 3→4: Supongamos que A/B y B/A Sea D∈K [x]: D/A, como A/B → D/B Si D∈̀K [x]: D`/B y como B/A → D`/ A Los polinomios que verifican la Proposición anterior se llaman asociados. Entonces los polinomios asociados de un A(x) ∈K [x], son de la forma k. A(x) con k∈K , k≠0. Así, todo polinomio es divisible por las constantes no nulas y por sus asociados. Estos son los divisores triviales. Cualquier otro divisor, distinto de estos, serán divisores propios. Divisor común mayor Definición: Dados A y B ∈K [x], un D∈K [x] es el divisor común mayor de A y de B, si: 1) D/A y D/B 2) Si D´/A y D`/B → D´/D Escribiremos: D = (A, B) para indicar el divisor común mayor entre A y B. Proposición: Sean A, B ∈K [x] y sea D∈K [x] el resto de dividir A por B. Entonces A y B tienen los mismos divisores que B y D Demostración: Probaremos primero que cualquier divisor de A y B es también divisor de D y luego que todo divisor de D y B es también divisor de A. 1) Sea A = Q.B + R y sea P∈K [x] : P/A y P/B → P divide a cualquier combinación lineal de A y B, en particular P/ A – Q.B → P/R Luego, si P/A y P/B → P/B y P/R 2) Sea P∈̀K [x] tal que P´/B y P´/R → P´/ Q.B + R → P´/A Luego si P´/B y P´/R → P´/A y P´/B Corolario : D = (A, B) ↔ D = (B, R) Algoritmo de Euclides

Page 87: Algebra y Logica Algebra i Apuntes

87

Como en K [x] existe la división entera es posible aplicar el Algoritmo de Euclides para determinar el divisor común mayor entre dos polinomios A(x) y B(x) dados, de igual manera que se hace en Z. Entonces, dados A(x) y B(x) no nulos, se van haciendo divisiones sucesivas de acuerdo al esquema conocido. Los restos que se van obteniendo son polinomios de grado estrictamente decrecientes. Así el procedimiento se aplicará sólo un número finito de veces. El último paso conduce a un resto nulo.

Q1(x) Q2(x) … … Qn(x) Qn+1(x) A(x) B(x) R1(x) … Rn-2(x) Rn-1(x) Rn(x) R1(x) R2(x) … … Rn(x) 0

Proposición: Si A(x) y B(x) ∈K [x] son no nulos, el último resto no nulo que se obtiene aplicando el Algoritmo de Euclides, es el divisor común mayor D, entre A(x) y B(x). Además D se puede escribir de la forma D(x) = S(x). A(x) + T(x) . B(x) con S, T ∈K [x] Esta proposición prueba entonces la existencia del divisor común mayor para dos polinomios no nulos. Si alguno de ellos es el polinomio nulo, por ejemplo A(x) = 0, entonces: (B(x), 0) = B(x) y B(x) = 1. 0 + 1. B(x) Observación: de la definición de divisor común mayor resulta que si D(x) = (A(x), B(x)), otro D`(x) ∈K [x] es un divisor común mayor de A(x) y B(x) si y sólo si D(x) y D´(x) son asociados. Vale entonces el siguiente Teorema Para todo par de polinomios A(x) y B(x) ∈K [x] existe un divisor común mayor D(x) ∈K [x] y D(x) = S(x). A(x) + T(x) .B(x) con S(x) y T(x)∈K [x]. Además, los divisores comunes mayores de A(x) y B(x) son de la forma k.D(x), con k ∈K , k≠0. Como el divisor común mayor de dos polinomios es único, se considera el D(x) mónico que cumple las condiciones de la definición. Se habla entonces de el divisor común mayor. Ejemplo: En R[x] hallar el divisor común mayor de A(x) y B(x) y expresarlo como combinación lineal de ambos, siendo: A(x) = x4 – 3 x3 + 5x2 – 9 x + 6 y B(x) = x3 + 4x2 + 3x +12 x- 7 x + 4 x4 – 3 x3 + 5x2 – 9 x + 6 x3 + 4x2 + 3x +12 x2 + 3 - x4 + 4x3 + 3x2 + 12 x -7 x3 + 2x2 – 21 x + 6 - -7 x3 – 28x2 – 21x - 84 30 x2 + 90

- x3 + 3x 4 x2 + 12 - 4x2 + 12 0

Por lo tanto D(x) = (A, B) = x2 + 3

Page 88: Algebra y Logica Algebra i Apuntes

88

y A(x) = B(x). (x – 7) + 30 (x2 + 3) → x2 + 3 = 301

A(x) - 301

B(x) . (x – 7)

Observación: Como A(x) tiene los mismos divisores que k.A(x) con k∈K , k≠0, entonces: (A(x), B(x)) = (k.A(x), k’.B(x)) con k∈K , k≠0 y k ∈́K , k´≠0 Luego, para calcular el divisor común mayor de dos polinomios dados, se pueden simplificar los cálculos descartando los factores constantes de los polinomios dados y de los sucesivos restos obtenidos en el algoritmo, puesto que los resultados variarán a lo sumo en un factor constante, que no tiene interés para el cálculo del divisor común mayor. Otro ejemplo: Hallar D(x) = (A, B) siendo: A(x) = 6x4 – 3x3 + 11x2 – 15x +1 y B(x) = 6x3 + 14 x – 8 Podemos considerar: B`(x) = 3x3 + 7x – 4