• Author / Uploaded
• William Paucar

Citation preview

Apuntes de Álgebra I

CAPÍTULO 1

FUNDAMENTOS DE LÓGICA PROPOSICIONAL Y MÉTODOS DE DEMOSTRACIÓN

OBJETIVOS: 1. Conocer las leyes del álgebra de proposiciones como equivalencias lógicas. 2. Entender las inferencias lógicas como implicaciones lógicas. 3.

Utilizar las leyes e inferencias lógicas en la demostración de razonamientos válidos.

4. Aplicar los fundamentos de la lógica proposicional en los métodos de demostración. 5. Conocer los métodos de demostración directa, indirecta e inducción matemática. 6. Aplicar los métodos de demostración en la demostración de teoremas o propiedades básicos del álgebra. SUMILLA Este capítulo se inicia con una breve exposición de los conceptos básicos, de manera intuitiva y luego deductiva, de la lógica proposicional; es decir, se desarrollarán los conceptos de equivalencia lógica que da lugar a las leyes del álgebra de proposiciones, para continuar con el concepto de la implicación lógica, que es el camino para el estudio de las inferencias lógicas o razonamientos válidos o correctos. Se continúa con el estudio de los métodos de demostración, que permiten explicar las diversas técnicas que se usan para las demostraciones de teoremas o propiedades.

1

Apuntes de Álgebra I

1.1 FUNDAMENTOS DE LÓGICA PROPOSICIONAL 1.1.1 Introducción La lógica de proposiciones es la parte más elemental de la lógica matemática. En esta primera parte de la lógica, las inferencias se construyen sin tomar en cuenta la estructura interna de las proposiciones; sólo se examinan las relaciones lógicas existentes entre proposiciones consideradas como un todo, y de ellas sólo se toma en cuenta su propiedad de ser verdadera o falsa. Por esta razón emplea sólo variables proposicionales. La lógica de proposiciones estudia las relaciones formales existentes entre proposiciones y no las que se dan dentro de ellas. Se le denomina, también, lógica de proposiciones sin analizar. Dispone de medios de análisis formal de las inferencias (lenguaje simbólico y métodos específicos), y la validez de éstas se determina por las relaciones entre proposiciones consideradas como un todo, sin penetrar en su estructura interna. Los métodos empleados en la lógica de proposiciones resultan insuficientes para examinar algunos tipos de inferencias. Así, por ejemplo, no es posible decidir con dichos métodos la validez del siguiente razonamiento: Todos los peruanos son americanos (p) Todos los ayacuchanos son peruanos (q) ____________________________________ Luego, todos los ayacuchanos son americanos (r) Expresando simbólicamente las premisas y la conclusión, tenemos: p q _____ r

o p  q  r

La inferencia propuesta es intuitivamente válida, pero la fórmula p  q  r no es válida porque es posible hacer verdadera las premisas (p y q) y falsa la conclusión (r). Analizando detenidamente la estructura de la inferencia llegamos a la evidencia que su validez depende no sólo de las relaciones existentes entre sus proposiciones, sino también de las relaciones existentes entre los elementos de sus proposiciones, elementos conocidos tradicionalmente con el nombre de términos. De este tipo de inferencias, basado en el análisis de la estructura interna de las proposiciones simples, se ocupa la llamada Lógica de Predicados; tema que no es parte de este capítulo. 1.1.2 Proposiciones lógicas El lenguaje, en sentido estricto, es un sistema convencional de signos, es decir, un conjunto de sonidos y grafías con sentido sujeto a una determinada articulación interna. Sirve para afirmar o negar (oraciones aseverativas o declarativas), expresar deseos (oraciones desiderativas); formular preguntas (oraciones interrogativas); expresar sorpresa o admiración (oraciones exclamativas o admirativas) e indicar exhortación, mandato o prohibición (oraciones imperativas). De todas estas clases de oraciones, la lógica

2

Apuntes de Álgebra I

proposicional sólo toma en cuenta las declarativas o aseverativas, las únicas que pueden constituir proposiciones, según cumplan o no determinados requisitos. Entonces, todas las proposiciones son oraciones, pero no todas las oraciones son proposiciones. Por ejemplo: a) El átomo es una molécula.

(proposición)

b) El pentágono es un polígono de cinco lados. (proposición) c) ¿Qué es la matemática? d) x + 7 = 10. e) ¡Alto! ¡No pasar! f) Juan es bueno Sólo a) y b) son ejemplo de proposiciones. Las demás: c) no es proposición, pues es una oración interrogativa, d) es una oración aseverativa, pero no es proposición; no es verdadera ni falsa porque en ella figura una letra sin interpretas (es ejemplo de función proposicional); e) no es proposición, pues es una oración imperativa; finalmente, f) no es proposición porque constituye un juicio de valor. 1.1.2.1 Proposición, oración y enunciado Es necesario distinguir una proposición (objeto conceptual o constructo) de las oraciones (objetos lingüísticos) que la designan, expresan o formulan, así como es preciso distinguir una oración de sus diversas enunciaciones (acto psicofísico) orales, escritas, o por ademanes. Es decir, cuando se enuncia, o se escucha, o se escribe, o se lee una oración, como por ejemplo, “cinco es menor que diez”, se ejecuta un acto psicofísico. Toda proposición es expresable por una o más oraciones, pero la recíproca no es cierta. Pues, hay oraciones gramaticales que no formulan proposición alguna, como por ejemplo: “la raíz cuadrada de una melodía es igual a un sueño” (ejemplo propuesto por Mario Bunje, en su obra Epistemología) Entonces, entre proposición, oración y enunciado, se tienen tres clases de objetos y dos relaciones enuncian expresan Enunciados

(acto psicofísico)

Oraciones

(acto lingüístico)

Proposiciones

(objeto conceptual)

El propósito de la lógica proposicional es simbolizar cualquier tipo de razonamiento, para su análisis y tratamiento. Para ello usa enunciados declarativos a los que se puede asociar un valor de verdad (verdadero o falso); es decir, usa proposiciones. El lenguaje formal de la lógica proposicional está formada por dos elementos: proposiciones y conectivos lógicos (operadores lógicos).

3

Apuntes de Álgebra I

1.1.3 Proposición y conectivos lógicos a) Proposición simple Una proposición es un enunciado del lenguaje con contenido de información sobre lo que es posible pronunciarse con un verdadero o con un falso, pero no ambas cosas a la vez. Notas: 1. Si una proposición es verdadera, diremos que su valor de verdad o valor lógico (VL) es verdadero o uno (V o 1). 2. Si una proposición es falsa, su valor de verdad o valor lógico es falso o cero (F o 0). Las proposiciones pueden ser de varios tipos. a) Proposiciones de acción con sujeto no determinado: “hace calor”, “llueve”, etc. b) Proposición de atribución de propiedades a sujetos determinados: “Ana es estudiosa”, “dos es un número primo”, etc. c) Proposiciones de relación: “tres es mayor que cinco”, “todo cuadrado es un rectángulo”, etc. Observaciones: i) Al construir una proposición se debe garantizar que ésta pueda ser evaluada (fórmula bien formada). ii) Determinar si una proposición está constituida (o puede ser deducida) a partir de un conjunto de proposiciones. Es decir, si es una consecuencia lógica de dicho conjunto. iii) Existen varias formas de representar una fórmula de la lógica proposicional. Aquí, se introduce el concepto de circuito lógico, donde se asocia a los conectivos lógicos un símbolo gráfico; tal como: p

q

 p  q

p  p  q q Ejemplo. Las siguientes afirmaciones son proposiciones simples. a) La región Arequipa está al sur de Lima.

(V)

i)

(V)

La luna es un satélite de la tierra.

ii) El número 18 es divisible por 4 y por 6.

(F)

iii) Uno es un número primo.

(F)

iv) Cuatro es un número real complejo de la forma (4, 0).

(V)

v) El número atómico del hidrógeno es 1.

(V)

vi) Un punto sobre una recta determina dos rayos sobre dicha recta.

(V)

vii) Todo rombo es un cuadrado.

(F)

4

Apuntes de Álgebra I

Variable Proposicional Una variable proposicional es aquella que se usa para simbolizar una proposición simple. Para ello se usan, generalmente, las letras minúsculas: p, q, r, …, etc. Un enunciado que contenga al menos una variable proposicional se dice una forma o fórmula proposicional. Ejemplo. p: llueve ; q: hace frío b) Conectivos lógicos (Operadores lógicos) Son los signos que permiten construir frases u oraciones nuevas, a partir de las existentes, obteniéndose nuevos significados. Además de enlazar o conectar proposiciones establecen determinadas operaciones entre ellas. Son de dos tipos: diádicos y el monádico. Los conectivos diádicos tienen un doble alcance: hacia la izquierda y hacia la derecha, es decir, afectan a dos variables. Los más usados son:  El conjuntivo. Representa a la conjunción gramatical “y”. Su símbolo es “”.  El disyuntivo. Representa a la conjunción gramatical “o”. Puede ser inclusivo y exclusivo. El símbolo del inclusivo es “”; el del exclusivo es “”.  El condicional. Representa a la conjunción compuesta “si …, entonces …”. Su símbolo es “⟶”.  El bicondicional. Representa a la conjunción compuesta “si y sólo si”. Su símbolo es “⟷”. El conectivo monádico tiene un solo alcance: hacia la derecha, es decir, afecta a una sola variable. Es el conectivo de la negación. Representa al adverbio “no”. Su símbolo es “”. 1.1.4 Tablas de verdad Para que entendamos como están definidas las operaciones proposicionales, es necesario recurrir a un artificio lógico llamado tabla de verdad. Para ello dibujamos una tabla de doble entrada, de manera que para cada variable proposicional exista una columna debajo de ella. Luego en las columnas escribimos todas las combinaciones posibles de los valores de la variable p, q, r, … , etc, según sea el caso, y en forma ordenada, para después aplicar la definición y establecer la verdad de las operaciones proposicionales que estudiaremos en forma breve más adelante. A cada combinación se le denomina arreglo. Construimos, a continuación, el sector de la tabla donde deben estar las columnas de valores de la variable. A este sector se le denomina margen. El número de valores que van a constituir cada columna se calcula aplicando la expresión numérica 2n, donde n es una variable numérica cuyo valor depende del número de variables proposicionales que tenga la proposición que vamos a tabular. Además, el número de arreglos coincide con el número de valores que constituyen cada columna Se recomienda escribir en la primera columna la mitad de valores verdaderos y la mitad de valores falsos. En la segunda columna un cuarto de valores verdaderos y un cuarto de valores falsos; en la tercera, cuando hay tres variables, un

5

Apuntes de Álgebra I

octavo y así sucesivamente. Estas sucesivas divisiones entre dos de los valores de las columnas son siempre posible debido a que todo número que se obtiene aplicando 2n es siempre par. Entonces, a. Para una proposición simple p, tenemos: p V F 21 = 2 arreglos o posibilidades de combinar sus valores de verdad. b. Para dos proposiciones simples p y q, se tiene: p

q

V

V

V

F

F

V

F

F

22 = 4 arreglos o posibilidades de combinar los valores de verdad de p y q. c. Para tres proposiciones simples p, q y r , tenemos: p

q

r

V

V

V

V

V

F

V

F

V

V

F

F

F

V

V

F

V

F

F

F

V

F

F

F

23 = 8 arreglos o posibilidades de combinar los valores de verdad de p, q y r. En general, si tenemos n proposiciones, n  1, las tablas que construiremos tendrán 2n arreglos o posibilidades de combinar las n proposiciones sus valores de verdad. Observación. El orden en que aparecen las variables proposicionales, en las tablas de verdad, es el lexicográfico (orden de aparición de las letras en el alfabeto español). 1.1.5 Operaciones proposicionales A las proposiciones que se obtienen combinando otras, mediante los conectivos u operadores lógicos, se les llama proposiciones compuestas. Por ejemplo, el enunciado Si quince en divisible entre tres, entonces quince es un múltiplo de tres.

6

Apuntes de Álgebra I

es una proposición compuesta, donde, si ... , entonces ... es el conectivo lógico. Esto significa que los conectivos elementales nos permiten definir operaciones proposicionales. Estas operaciones, como veremos a continuación, en forma breve, tienen la característica que el valor de verdad de la proposición resultante depende de los valores de verdad de las proposiciones componentes. A toda operación con esta propiedad se le llama, también, operación veritativa. A continuación, definimos las operaciones proposicionales elementales, empleando un nombre y un símbolo. 1.1.5.1 La Negación Sean las proposiciones: p: el símbolo químico de la plata es Ag. q : el hidrógeno es un gas. r : el oro es un metaloide. Usando las proposiciones q y r construimos la proposición: q  r : el hidrógeno es un gas y el oro es un metaloide. A las proposiciones escritas como:  El símbolo químico de la plata no es Ag  Es falso que el hidrógeno es un gas y el oro es un metaloide les llamaremos la negación de p (escrita como  p ) y la negación de (q  r ) (escrita por  (q  r) ), respectivamente. Definición.- Sea p una proposición. La negación de p es otra proposición escrita como  p y definida mediante la tabla de verdad siguiente: p

p

V

F

F

V

La proposición  p se lee “no p”. La negación cumple la función de negar una afirmación o de afirmar una negación. Nota. Existen otras formas idiomáticas para expresar la negación. Para ello, se utilizan las expresiones, “no es cierto que”, “no es el caso que”, “es falso que”, etc. Estos términos se usan, generalmente, para negar proposiciones compuestas. O sea,  (proposición compuesta) Por ejemplo, expresar en forma simbólica la siguiente proposición: “No es cierto que Carlos juegue fútbol en un club profesional y obtenga buenas calificaciones en las evaluaciones finales” Solución. Sean las proposiciones, p: Carlos juega fútbol en un club profesional

7

Apuntes de Álgebra I

q: Carlos obtiene buenas calificaciones en las evaluaciones finales Luego, en forma simbólica se tiene:  (p  q) Ejemplo. Negar la proposición p: 8  12 (V) Solución. En este caso negamos la relación menor. Se sabe que dados dos números reales a y b, cualesquiera, por la propiedad de tricotomía sólo una de las siguientes posibilidades se cumple: a  b, a  b o a = b. Entonces, si negamos a  b, quedan dos posibilidades: a  b o a = b. Estas dos posibilidades las podemos escribir como a  b. Por tanto,  p: 8  12 (F) 1.1.5.2 La Conjunción Tengamos las dos proposiciones siguientes: r: 3 es un número primo s: 6 es múltiplo de 3 Sobre la base de estas proposiciones, conectándolas mediante la letra “y”, se puede construir la proposición: 3 es un número primo y 6 es múltiplo de 3 Observamos que la proposición anterior tiene como componentes a las variables proposicionales r y s, unidas por la letra “y”, a la cual le llamaremos conjunción y cuya representación simbólica será r  s, llamada proposición conjuntiva. Las proposiciones conjuntivas que podemos construir tendrán en común una forma lógica o estructura que puede ser presentada por ............... y ............... Los puntos suspensivos, a la derecha e izquierda de “y”, pueden ser ocupados por cualquier otro par de proposiciones escritas en forma literal o mediante las variables proposicionales p, q, r, etc. Definición.- Si las variables proposicionales p y q representan cualquier par de proposiciones, la conjunción de estas proposiciones es la proposición p  q. Las condiciones de verdad de la conjunción p  q es: a. Verdadera, solamente en el caso que p y q sean ambas verdaderas. b. Falsa, en cualquier otro caso. Es decir, si por lo menos una de las proposiciones es falsa. En forma práctica y en una tabla de verdad, tenemos:

8

Apuntes de Álgebra I

p

q

p  q

V

V

V

V

F

F

F

V

F

F

F

F

A la columna de valores bajo la conectiva  se le llama matriz de la conjunción. Ejemplo. Sea la proposición Juan comprará una computadora, pero no tiene dinero En esta proposición la palabra “pero”, del lenguaje natural que no tiene el mismo uso que la “y”, debe ser traducida al lenguaje lógico por la conectiva  . Entonces, si observamos que las variables proposicionales p y q representan a: p: Juan comprará una computadora q: Juan no tiene dinero Entonces, p  q, representa a la proposición mencionada líneas arriba. Nota. Las palabras del lenguaje natural: “pero”, “sin embargo”, “además”, “no obstante”, “aunque”, “a la vez”, etc. son, desde el punto de vista lógico, equivalentes a “y” (  ). Tengamos las siguientes expresiones: a. El número dos es par y primo b. Juan comió pescado en mal estado y se intoxicó La conjunción, en lógica proposicional, es conmutativa mientras que en el lenguaje natural no siempre se cumple. Así, tenemos que c. El número dos es primo y par. El sentido sigue siendo el mismo que la proposición en (a). Por tanto, esta expresión es una proposición conjuntiva y se puede simbolizar por p  q, donde p: El número dos es par q: El número dos es primo En cambio, d. Juan se intoxicó y comió pescado en mal estado. A pesar de llevar la letra “y” como término de enlace tiene distinto significado que la expresión en (b). La diferencia se puede establecer en que la expresión en (b) sugiere una relación de causalidad la cual se desvirtúa en la expresión (d). Pero, la conectiva de la conjunción no establece ningún tipo de nexo causal o de orden. Esto significa que las proposiciones dadas en (b) y (d) son equivalentes para los fines del análisis lógico proposicional. Así tenemos, por ejemplo, que las proposiciones: Luis besó a su novia y se fue a Arequipa Luis se fue a Arequipa y besó a su novia Son lógicamente equivalentes, aunque en el lenguaje natural no sea así.

9

Apuntes de Álgebra I

1.1.5.3 La Disyunción Escribamos las siguientes proposiciones: a. Carla practica gimnasia o natación b. Este libro es de matemática o es de historia Observamos que lo que tienen en común estas dos proposiciones compuestas es que han sido construidas sobre la base de proposiciones simples y que han sido enlazadas mediante la letra “o”. La “o” en lógica proposicional se llama conectivo de disyunción y a cada una de las proposiciones dadas: proposiciones disyuntivas. Las proposiciones componentes en (a), son: p: Carla practica gimnasia, y q: Carla practica natación La proposición en (a), es de carácter inclusivo, pues aunque Carla practique o bien gimnasia o bien natación, no excluye la posibilidad que pueda practicar ambas disciplinas. En forma simbólica, tenemos p  q

(p o q)

Las proposiciones componentes en (b), son: r: este libro es de matemática, y s: este libro es de historia. Estas dos componentes no pueden ser ambas verdaderas. Pues, si el libro es de matemática, entonces ya no puede ser de historia y en el caso que sea de historia, entonces ya no puede ser de matemática. O sea, la verdad de una proposición excluye la verdad de la otra y, por tanto, las propiedades son excluyentes entre si. Por esta razón se dice que la proposición en (b) es de carácter exclusivo. En forma simbólica, se anota

r  s o rs

(o r o s)

La disyunción podemos entenderla, de acuerdo a lo anterior, en dos sentidos. Una como disyunción inclusiva o débil y la otra como disyunción exclusiva o fuerte; y en forma simbólica escribimos la estructura lógica de la disyunción, por:  p  q, para expresar la disyunción inclusiva.  p  q o p  q, para expresar la disyunción exclusiva. 1.1.5.3.1 Disyunción inclusiva Definición.- Si las variables proposicionales p y q representan cualquier par de proposiciones, la disyunción inclusiva de estas proposiciones es otra proposición dada por p  q. Las condiciones de verdad de la disyunción inclusiva son: a) verdadera, siempre que p sea verdadera o que q sea verdadera o que ambas sean verdaderas. Es decir, cuando por lo menos una de las variables sea verdadera.

10

Apuntes de Álgebra I

b) falsa, sólo cuando ambas variables, p y q, son falsas. Aplicamos esta definición y en una tabla de verdad, tenemos: p

q

p  q

V

V

V

V

F

V

F

V

V

F

F

F

A la columna de valores bajo la conectiva  se le llama matriz de la disyunción inclusiva. Ejemplo. Sean las proposiciones siguientes: p: Todo triángulo determina tres ángulos q: Todo rectángulo es un cuadrado r: Todo triángulo isósceles es equilátero Entonces, tenemos que VL (p) = V, VL (q) = F y VL (r ) = F . Luego: a) p  q: Todo triángulo determina tres ángulos o todo rectángulo es un cuadrado Es una proposición verdadera, es decir, VL (p  q) = V . ¿Por qué? b) q  r: Todo rectángulo es un cuadrado o todo triángulo isósceles es equilátero. Es una proposición falsa, o sea, VL (q  r) = F ; pues, q es F y r es F. 1.1.5.3.2 Disyunción exclusiva Definición.- Si las variables proposicionales p y q representan cualquier par de proposiciones, la disyunción exclusiva de estas proposiciones es otra proposición dada por p  q (o, p  q). Las condiciones de verdad de la disyunción exclusiva, son: i)

Verdadera, si una y sólo una de las variables proposicionales es verdadera. Es decir, si VL (p)  VL (q).

ii) Falsa, en cualquier otro caso. Es decir, si VL (p) = VL(q). En una tabla de verdad, la disyunción exclusiva la expresamos, en forma práctica, por: p

q

p  q

V

V

F

V

F

V

F

V

V

F

F

F

A la columna de valores bajo la conectiva  se le llama matriz de la disyunción exclusiva.

11

Apuntes de Álgebra I

Nota. Observamos, en la tabla, que la disyunción exclusiva es verdadera si los valores lógicos de p y q son diferentes, y es falso si los valores lógicos son iguales. Ejemplo. Si tenemos, p: la ciudad de Huamanga está en la Región Ayacucho. q: la ciudad de Abancay está en la Región Apurímac. r: la ciudad de Puquio está en la Región Puno. entonces, por conocimiento elemental de geografía, tenemos que: p es V, q es V y r es F. Luego, a) p  q: o Huamanga está en la Región Ayacucho o Abancay está en la Región Apurímac. Es una proposición falsa, ya que p es V y q es V. Es decir, VL (p  q) = F. b) q  r: o Abancay está en la Región Apurímac o Puquio está en la Región Puno. Es una proposición verdadera. O sea, VL (q  r) es V. ¿Por qué? 1.1.5.4 El Condicional El condicional es quizás el conectivo u operador de mayor relevancia en la comprensión del razonamiento lógico. Al condicional, algunos autores, le llaman implicación material que según C.I. Lewis lo diferencia con la implicación y la implicación estricta. Estos condicionales tienen en común la expresión esquemática “si ... , entonces ...” . Este esquema corresponde a las oraciones del tipo “si tengo dinero, entonces viajaré a la ciudad de Trujillo”; que no será falsa en el caso que no viaje a la ciudad de Trujillo siempre que no tenga dinero; pero sí, en el caso que tenga dinero y no viaje. Esta oración hipotética podemos entenderla como: “no es el caso que tenga dinero y no viaje a la ciudad de Trujillo” que traducida al lenguaje simbólico corresponde a la forma proposicional  (p   q ). O sea, p ⟶ q   (p   q)

.................... ( ∗ )

de donde, p : tengo dinero y q : viajaré a la ciudad de Trujillo (el símbolo  se lee “equivalente). De acuerdo a lo mencionado en ( ∗ ), el condicional equivale a la negación de una conjunción cuya primera variable está afirmada y la segunda está negada. Sean los siguientes enunciados: a. Si 0! = 1, entonces 3! + 1! = 7. b. Si toda función es una relación, entonces toda relación es una función. c. Si todos los animales tienen cuatro patas, entonces algunos animales tienen 2 patas. d. Si 2 fuera un número impar, entonces 2 + 1 sería un número par. Estas proposiciones condicionales tienen la característica común de tener una estructura del tipo “Si .......... , entonces .......... “ la diferencia radica en que las componentes que ocupan los puntos suspensivos son en cada ejemplo diferentes. Pero a la lógica le interesa fundamentalmente el aspecto estructural. Por tanto, la expresión “si ......, entonces ...... “ constituye el conectivo llamado condicional cuyo operador es, “ ⟶ “

12

Apuntes de Álgebra I

En cada condicional, a la proposición que se encuentra entre los términos “si” y “entonces” se le llama antecedente y a la que se encuentra después de “entonces” se le llama consecuente. Así por ejemplo, en el condicional siguiente: Si el cuadrilátero es un cuadrado, entonces el cuadrilátero es un rectángulo Tenemos que: p : el cuadrilátero es un cuadrado   

,

q : el cuadrilátero es un rectángulo  

antecedente

consecuente

Luego, p   

⟶  q  

antecedente

con sec uente

Observaciones: Analizando los valores de verdad de los condicionales, antes mencionados, tenemos que: (a) El condicional es verdadero. Pues, el antecedente y el consecuente son verdaderos por la aritmética. (b) El condicional es falso. Pues el antecedente “toda función es una relación” es una proposición verdadera, pero el consecuente “toda relación es una función” es una proposición falsa; ya que sabemos que existen relaciones que no son funciones (c) El condicional es verdadero. En este caso la proposición nos dice que si aceptamos hipotéticamente que todos los animales tienen cuatro patas, entonces algunos de ellos (un grupo) tienen dos patas. En este condicional, el antecedente es falso y el consecuente verdadero. (d) El condicional es verdadero. Por cuanto no se está afirmando que 2 es un número par, sino que si lo sería 2 + 1 sería igual a 3. Aceptamos que este razonamiento es verdadero, a pesar que el antecedente y consecuente son proposiciones falsas. A este tipo de condicionales se les llama condicionales contrafácticos. Definición.- Sean las variables proposicionales p y q que representan a cualquier par de proposiciones. La proposición condicional, con antecedente p y consecuente q, es la proposición p ⟶ q; cuyas condiciones de verdad, son: a) Verdadero, cuando por lo menos.  el antecedente es falso ;  el consecuente es verdadero b) Falso, solamente cuando el antecedente es verdadero y el consecuente falso. De acuerdo a la definición y las reglas conocidas, la tabla de verdad de una proposición condicional está dada por: p

q

p ⟶ q

V

V

V

V

F

F

F

V

V

F

F

V

13

Apuntes de Álgebra I

A la columna de valores bajo la conectiva ⟶ se le llama matriz del condicional. Notas: 1. La verdad de una proposición condicional es completamente independiente de las relaciones que puedan existir o no entre los significados del antecedente y el consecuente. Por ejemplo, en el condicional: “Si un polígono tiene tres lados, entonces es un triángulo” Existe relación entre lo que afirma el antecedente y el consecuente; es decir, “hablan” de lo mismo. Cuando esto ocurre, se dice que hay una relación de atingencia entre el antecedente y el consecuente. Por otro lado en el condicional: “Si Supe Puerto es un puerto pesquero, entonces tres es un número primo” Observamos que lo que afirma el antecedente es completamente diferente a lo que afirma el consecuente, pues el hecho que Puerto Supe sea un puerto pesquero nada tiene que ver con que tres sea un número primo. Es decir, no existe relación entre los significados del antecedente y consecuente. En este caso se dice que no se da una relación de atingencia. Sin embargo, la proposición condicional es verdadera. ¿Por qué? 2.

En el lenguaje matemático las proposiciones condicionales tienen especial relevancia, pues una gran cantidad de sus teoremas son proposiciones del tipo “si ......, entonces ......”. En este caso, al antecedente se le llama hipótesis y al consecuente, tesis. Es decir,

⏟𝑝 ℎ𝑖𝑝ó𝑡𝑒𝑠𝑖𝑠

⟶

𝑞 ⏟ 𝑡𝑒𝑠𝑖𝑠

Por ejemplo, Teorema. Si A y B son dos conjuntos cualesquiera, entonces A – B = A  Bc En este caso, tenemos: Hipótesis: A y B son dos conjuntos cualesquiera Tesis:

A – B = A  Bc

La tesis, es la proposición a demostrar y la hipótesis es la proposición (medio auxiliar) que usamos para demostrar la tesis. 3. En el lenguaje natural, existen varias expresiones idiomáticas para indicar el condicional p ⟶ q. Entre éstas tenemos: 1. Si p, entonces q. 2. p es condición suficiente para q. 3. Una condición suficiente para q, es p. 4. q es condición necesaria para p. 5. Una condición necesaria para p, es q. 6. q, si p.

14

Apuntes de Álgebra I

7. p sólo si q. 8. p solamente si q. Por ejemplo, simbolizar los siguientes condicionales: 1. El agua se congela si la temperatura está bajo cero 2. Una condición necesaria para que un cuadrilátero sea un rombo, es que el cuadrilátero sea un cuadrado. Solución. 1. Este condicional tiene la forma de la expresión (6). Entonces, sean a: el agua se congela;

t: la temperatura está bajo cero

Luego, escribimos t  a 2. Este condicional tiene la forma de la expresión (4). Entonces, sean r: el cuadrilátero es un rombo; c: el cuadrilátero es un cuadrado Luego, escribimos r  c Nota. Es común encontrar en algunos párrafos, del lenguaje natural, los términos: porque, puesto que, ya que, siempre que, cuando, cada vez que, dado que, etc. Estos términos también son considerados como conectivos condicionales, y se caracterizan porque después de cada uno de éstos términos se encuentra el antecedente. Ejemplo. Simbolizar la siguiente expresión. El profesor no asistió a clases, puesto que el Jefe del Departamento Académico citó a una reunión de profesores y el Decano de la Facultad dictó una conferencia. Solución. Es una proposición condicional, ya que se tiene el término “puesto que”. En este condicional, el antecedente es: el Jefe del Departamento Académico citó a una reunión y el Decano de la Facultad dictó una conferencia. Entonces, sean las proposiciones simples dadas en el texto: p: el profesor asistió a clases q: el jefe del Departamento Académico citó a una reunión de profesores r: el Decano de la Facultad dictó una conferencia Luego, escribimos en forma simbólica: (q  r) ⟶  p 1.1.5.5 El Bicondicional Sean las siguientes proposiciones: a. La figura tiene cuatro lados b. La figura es un cuadrilátero c. Ruth aprobó Matemática I d. Ruth obtuvo una calificación de once o más

15

Apuntes de Álgebra I

Con estos enunciados y anexándolos mediante la expresión del lenguaje natural “ ... si y sólo si ... “, construimos las siguientes proposiciones: e) La figura tiene cuatro lados si y sólo si es un cuadrilátero f) Ruth aprobó Matemática I si y sólo si obtuvo una calificación de once o más. A estas expresiones les llamaremos

proposiciones bicondicionales cuyo conectivo, en el lenguaje

lógico, se denota por el símbolo “⟷” (flecha en ambas direcciones). El Bicondicional dado en (e) lo escribimos p  q (se lee “p si y sólo si q), donde p: La figura tiene cuatro lados y q: La figura es un cuadrilátero. En forma similar, para ( f ). Las proposiciones bicondicionales se encuentran generalmente en la matemática, como en el ejemplo (e) y, también en el lenguaje natural como en el ejemplo ( f ). La característica de estas proposiciones es que están constituidas por dos proposiciones condicionales de sentido inverso y conectados por la conjunción. Así, tenemos: 1. Si la figura tiene cuatro lados, entonces es un cuadrilátero y si la figura es un cuadrilátero, entonces tiene cuatro lados. 2. Si Ruth aprobó Matemática I, entonces obtuvo una calificación de once o más y si Ruth obtuvo una calificación de once o más, entonces aprobó Matemática I. Traduciendo la proposición (1) a la forma simbólica, tenemos: (p ⟶ q)  (q ⟶ p). Luego, entonces: p  q  (p  q)  (q  p) lo que significa que, en los condicionales del lado derecho, si el antecedente (p) es verdadero ó falso, entonces el consecuente (q) tiene que ser verdadero ó falso, en ese orden. Además, si el consecuente es verdadero ó falso, entonces el antecedente también debe serlo. Es decir, la verdad o falsedad de una proposición bicondicional exige necesariamente la verdad o falsedad de la otra. Definición.- Si las variables proposicionales p y q representan cualquier par de proposiciones, llamaremos bicondicional de p y q a la proposición p ⟷ q cuyas condiciones de verdad, son: a. Verdadero, cuando ambas proposiciones tienen el mismo valor de verdad. Es decir, cuando VL (p) = VL (q) ; b. Falso, cuando VL (p)  VL (q). De acuerdo a la definición y las reglas conocidas, construimos la tabla de verdad de p ⟷ q de la siguiente forma p

q

p ⟷ q

V

V

V

V

F

F

F

V

F

F

F

V

16

Apuntes de Álgebra I

A la columna de valores bajo la conectiva ⟷ se le llama matriz del bicondicional La proposición Bicondicional

p ⟷ q se puede expresar también por “p es condición necesaria y

suficiente de q” y que “q es condición necesaria y suficiente de p”. Notas: 1. El nombre de Bicondicional proviene del hecho que: p  q  (p  q)  (q  p)  (q  p)  (p  q) como hemos afirmado líneas arriba. Entonces, en el lenguaje natural: a. “p si y sólo si q” es conjunción de “p, si q” y “p sólo si q”, que corresponden a los condicionales q  p y p  q, respectivamente. b. “p es condición necesaria y suficiente de q”, es la conjunción de “p es condición necesaria de q” y “p es condición suficiente de q”, que corresponde a los condicionales q  p y p  q, respectivamente. 2. La matriz de la proposición bicondicional es equivalente a la negación de la matriz de la disyunción exclusiva. Es decir: p ⟷ q



 (p  q)

V

V

F

F

F

V

F

F

V

V

V

F

Ejemplo. Si, p: 15 es múltiplo de 3 q: 6 es divisible por 3 r: 3 es un número compuesto entonces, p es V; q es V y r es F. Luego, a. p ⟷ q: 15 es múltiplo de 3 si y sólo si 6 es divisible por 3. Es una proposición bicondicional falsa. Es decir, VL (p ⟷ q) = V, ya que VL (p) = VL (q) = V. b. q ⟷ r: 6 es divisible por 3 es condición necesaria y suficiente de 3 es un número compuesto. Esta proposición es falsa. Es decir, VL (q ⟷ r) = F, pues VL (q)  VL (r) 1.1.6 Formalización de proposiciones Formalizar una proposición significa abstraer su forma lógica, es decir, revelar su estructura sintáctica a través del lenguaje formalizado de la lógica. En términos sencillos, formalizar una proposición equivale a representarla simbólicamente. Toda proposición tiene su forma lógica y su forma proposicional (fórmula). La forma lógica de una proposición es otra proposición equivalente a la primera con la diferencia que en ella toda su estructura sintáctica está completamente explicitada. A partir de aquí, su forma proposicional o fórmula no es otra cosa que la que resulta de sustituir a toda proposición simple distinta por una variable proposicional

17

Apuntes de Álgebra I

también distinta, a toda conjunción gramatical por el conectivo u operador correspondiente y el adverbio “no” por el conectivo negativo. Ejemplo. Formalizar las siguientes proposiciones. a) Kant es filósofo, pero Frege es lógico.  Forma lógica: Kant es filósofo y Frege es lógico  Forma proposicional: p: Kant es filósofo. q: Frege es lógico. p  q b) No iremos al cine a menos que venga Ruth.  Forma lógica: si Ruth viene, entonces iremos al cine.  Forma proposicional: p: Ruth viene. q: iremos al cine. p ⟶ q c) Cuatro no es un número primo, sino compuesto.  Forma lógica: cuatro es un número compuesto y cuatro no es primo.  Forma proposicional: p: cuatro es un número compuesto. q: cuatro es un número primo. p  q d) Veinte no es múltiplo de tres ni de siete.  Forma lógica: veinte no es múltiplo de tres y veinte no es múltiplo de siete.  Forma proposicional: p: veinte es múltiplo de tres. q: veinte es múltiplo de siete  p   q. e) Sin carbono, oxígeno, nitrógeno e hidrógeno, no hay vida.  Forma lógica: si no hay carbono y no hay oxígeno y no hay nitrógeno y no hay hidrógeno, entonces no hay vida.  Forma proposicional: p: hay carbono q: hay oxígeno. r: hay nitrógeno s: hay hidrógeno. t: hay vida. ( p   q   r   s)   t

18

Apuntes de Álgebra I

f) Tanto diez como treinta son múltiplos de dos porque son divisibles por dos.  Forma lógica: si diez es divisible por dos y treinta es divisible por dos, entonces diez es múltiplo es dos y treinta es múltiplo de dos.  Forma proposicional: p: diez es divisible por dos. q: treinta es divisible por dos. r: diez es múltiplo de dos s: treinta es múltiplo de dos. (p  q)  (r  s) 1.1.7 Definición formal del lenguaje proposicional La definición formal de un lenguaje requiere la especificación de su alfabeto y de sus reglas de sintaxis. Alfabeto. Las notaciones simbólicas que se pueden utilizar son los siguientes: a) Símbolos de proposiciones: p, q, r, … b) Símbolos de conectivos: , , , ,  (notación simbólica de Scholz) c) Símbolos de agrupación: ( , ); [ , ]; { , }; … Reglas de sintaxis. Al igual que en el lenguaje natural no toda combinación de proposiciones y conectivos puede ser considerada como frase sintácticamente correcta. Así, en el lenguaje proposicional se hace necesario definir reglas de sintaxis para la obtención de fórmulas o formas proposicionales bien constituidas. Forma Proposicional. Llamaremos forma proposicional a cualquier expresión formada por: a) Variables proposicionales, tales como p, q, r, … (formas proposicionales atómicas) b) Los conectivos lógicos: , , , , , etc. c) Los paréntesis ( , ) Si A y B son formas proposicionales, también lo son:  A, A  B, A  B, A  B, A  B, A  B. Ejemplo. A(p, q) =  p  (q  p); B (p, q, r) = (p  r)   (q  r), son formas proposicionales. Para la correcta relación entre conectivos y proposiciones, en las formas proposicionales, se deben tener en cuenta: a) No deben aparecer conectivos adyacentes, excepto la negación. Por ejemplo:  (p  q), es una forma proposicional,  (p  q), no es una forma proposicional. b) Es preciso definir la relación conectivo – proposiciones, cuando exista más de un conectivo en la forma proposicional:

19

Apuntes de Álgebra I

c) Un conectivo afecta a la variable inmediata o al conjunto de variables encerradas entre signos de agrupación. Por ejemplo,  (p  q)   p   q. Para evitar el exceso de signos de agrupación, se adoptan las siguientes convenciones; que nos permitirán eliminar algunos de estos signos sin caer en ambigüedades. Convención I. Asignaremos el siguiente rango a cada conectiva (SAENZ, Jorge y OTROS. Fundamentos de la Matemática, pág. 30). ⟷

rango 4

⟶

rango 3

, , 

rango 2



rango 1

Nota. Establecemos que el rango de una forma proposicional atómica es 0 y que el rango de una forma proposicional no atómica es el rango de su conectivo principal. Así, la forma proposicional  p  (q  r), es de rango 2   [p  (q  r)], es de rango 1  p  (q  r), es de rango 4 Observación. Si se tiene una forma proposicional con la presencia de dos o más conectivos iguales, el orden de asociatividad es de izquierda a derecha. Por ejemplo, el orden de evaluación de: p  q  r es (p  q)  r Convención II. Escribimos  p en lugar de  ( p). Convención III. Si una forma proposicional es de la forma (A) ∗ B o A ∗ (B), donde ∗ es uno de los conectivos: , , , , ; entonces: i) Escribimos A ∗ B, si el rango de A es menor que el rango de ∗. ii) Escribimos A ∗ B, si el rango de B es mayor que el rango de ∗. Por ejemplo, (p  q)  r se puede escribir como p  q  r, pues el rango del condicional es mayor que el rango de la conjunción. Nota. Los signos de agrupación se usan cuando su omisión hace ambigua una forma proposicional, es decir, cuando una forma proposicional es susceptible de una doble interpretación. Por ejemplo, p  q  r es una ambigüedad. Por otro lado, cada forma proposicional tiene asociada una tabla de verdad, que recoge los distintos valores de verdad, de la forma proposicional, al asignar los valores V y F a las distintas variables involucradas. La tabla de verdad asociada a una forma proposicional se puede construir sistemáticamente a partir del procedimiento empleado para construir dicha forma proposicional; o empleando cualquiera de los dos métodos más usados: el método acumulativo o el método abreviado.

20

Apuntes de Álgebra I

Ejemplo. Construir la tabla de verdad de la forma proposicional (p   r)  q. Solución. Usaremos el método acumulativo. Este método consiste en asignar una columna para cada variable proposicional y una columna para cada operación indicada, como aparece en la siguiente tabla: p

q

r

r

p  r

(p   r) ⟶ q

V

V

V

F

F

V

V

V

F

V

V

V

V

F

V

F

F

V

V

F

F

V

V

F

F

V

V

F

F

V

F

V

F

V

F

V

F

F

V

F

F

V

F

F

F

V

F

V

En la tabla anterior, el resultado de la matriz principal presenta valores verdaderos y uno falso; por tanto, es una contingencia. Por esta razón, algunos autores llaman a (p   r) ⟶ q fórmula molecular consistente.

EJERCICIOS PROPUESTOS 1. Formalice las proposiciones siguientes, y en cada caso, halle su forma lógica y escriba su fórmula o forma proposicional. a) Ni Sandra, ni Raúl, ni Felipe ingresaron a la universidad de San Marcos. b) La Facultad de Ciencias está sin decano. c) En los países democráticos no hay delito de opinión, tampoco prisión por difamación. d) Tanto Carla como María no creen en dios, porque son materialistas. e) Si hay ley, razón y justicia en el mundo, no sucederá lo que temes. f) Aunque esté enfermo, no faltaré a la cita. g) No pudo asistir a la conferencia porque estaba de viaje en el interior del país. h) Sin su libre consentimiento, sin la debida retribución, no se le puede obligar a prestar trabajo. i) Se te enviará la constancia de estudios, bien por el correo de hoy, bien por el de mañana. j) Los yacimientos mineros y restos arqueológicos son patrimonio de la Nación, están bajo el amparo del estado y la ley regula su conservación. 2. De la falsedad de (p ⟶  q)  ( r ⟶ s) deduzca el valor de verdad de las siguientes expresiones: a) ( p   q)   q b) [( r  q)  q] ⟷ [( q  r)  s] c) (p ⟶ r) ⟶ [(p  q)   q]

21

Apuntes de Álgebra I

3. Sabiendo que la proposición compuesta  p  [q ⟶ ( r   s)] es verdadera, determinar el valor de verdad de [ p ⟶ ( r  q)]  s 4. Dadas las proposiciones p, q, r y la proposición compuesta t: [(p ⟷ r)  (q ⟶  p)]  [ ( p ⟷ ( r  q)  (r  p)] Hallar el valor de t sabiendo que r es falsa y, además, p y q tienen valores de verdad opuestas. 5. Sean las proposiciones t: (r ⟷ s)   r y u: (r ⟶  s) ⟶ r. Si el valor de verdad de t es falso y de u es verdadero, determinar el valor de [(r ⟷ u)  (t  s)]   t 6. Si las proposiciones p, r ⟶  p y  p ⟶ s son verdaderas, hallar el valor de verdad de  r y s. 7. Sean las proposiciones p, q, r, s y t. Si la proposición ( p  q) ⟶ [(r ⟶ p)  t] es una proposición falsa, hallar el valor de verdad de  (q   r)   [t ⟶ ( q  p)] 8. Si las proposiciones (p  q) ⟷ (r  s) y r  s son verdaderas, deducir el valor de verdad de la proposición [( p  r)  (s ⟶ q)] 9. Si el valor de verdad de  m  n es falso y el valor de p ⟷  q es verdadero, entonces hallar el valor de verdad de la expresión [x  (p ⟷ q)] ⟷ [(m ⟶ n) ⟶ y]

1.1.8 Tautologías y contradicciones Encontremos las tablas de verdad, de las siguientes formas proposicionales (una forma proposicional es una proposición compuesta que simbolizamos por A, B, C, etc.) a) A (p, q) = (p  q)  q b) B (p, q) =  [(p  q)  q] Solución. a) Usando la definición de la conjunción y luego el condicional, obtenemos (p  q)

⟶

q

V

V

V

F

V

F

F

V

V

F

V

F

22

Apuntes de Álgebra I

b) Usamos la definición de la conjunción, del condicional y luego de la negación, tenemos:  [(p  q)

⟶

F

V

F

V

F

V

F

V

q]

Observamos, en la primera tabla, los valores debajo de la conectiva principal (⟶) son todos verdaderos y en la segunda tabla bajo la conectiva principal () son todos falsos. Cuando ocurre este hecho decimos, en el primer caso, que tenemos una tautología, y una contradicción, en el segundo caso, respectivamente. Entonces, la forma proposicional en a) es una tautología y en b) es una contradicción. El concepto de tautología es el punto crucial de la lógica proposicional. Definición.- Una forma proposicional es una tautología si toma el valor verdadero (V ) cualquiera que sea la forma en que asignemos los valores V o F a las variables proposicionales que en ella intervienen. Es decir, si en su tabla de verdad la columna bajo su conectivo principal son todos V. Definición.- Una forma proposicional es una contradicción si toma el valor falso (F) cualquiera que sea la forma en que asignemos los valores V o F a las variables proposicionales que en ella intervienen. Es decir, si en su tabla de verdad la columna bajo su conectivo principal son todos F. Es evidente que la negación de una tautología es una contradicción y que la negación de una contradicción es una tautología. Es decir:  A es una tautología si y sólo si  A es una contradicción   A es una contradicción si y sólo si A es una tautología Ejemplo. Construir la tabla de verdad de la forma proposicional (p ⟶ q) ⟷ ( p  q). Solución. Usando la definición de la disyunción inclusiva, la conjunción y luego el bicondicional, tenemos p

q

(p ⟶ q)

p

( p  q)

(p ⟶ q) ⟷ ( p  q)

V

V

V

F

V

V

V

F

F

F

F

V

F

V

V

V

V

V

F

F

V

V

V

V

Observamos, por el resultado de la tabla, que la forma proposicional (p ⟶ q) ⟷ ( p  q) es una tautología.

23

Apuntes de Álgebra I

Ejemplo. La forma proposicional p   p es una tautología y la forma proposicional p   p es una contradicción. En efecto, p

p

p  p

p  p

V

F

V

F

F

V

V

F

A las tautologías las conocemos, también, con el nombre de leyes de la lógica proposicional. A algunas de estas, debido a su importancia que desempeñan en el desarrollo del cálculo proposicional, se les ha asignado un nombre propio. Así por ejemplo, a la tautología p   p se le llama ley del tercio excluido. Esta ley afirma que una proposición, o es verdadera o es falsa, quedando excluida una tercera posibilidad.

1.1.9 Equivalencia lógica La equivalencia lógica es otro tipo de tautología que tiene la forma bicondicional. Así, por ejemplo, si tenemos las formas proposicionales A: p ⟶ q y B:  q ⟶  p se verifica, fácilmente, que la proposición bicondicional (p ⟶ q) ⟷ ( q ⟶  p) es una tautología. En este caso se dice que A es equivalente a B y se escribe A  B o A  B. Es decir, p  q  q  p Por otro lado, el concepto de “A sí y sólo si B” es diferente al concepto de “A es lógicamente equivalente a B” o “A es equivalente a B”. Esto significa que A  B  A  B Definición.- Sean A y B dos formas proposicionales. Se dice que A equivale lógicamente a B o que A es equivalente a B; y escribimos A  B o A  B, si la forma bicondicional A ⟷ B es una tautología. Es decir, A  B si y sólo si A ⟷ B es una tautología De la definición anterior, se afirma que si una forma proposicional A es equivalente a otra forma proposicional B, entonces A implica a B, y a la vez, B implica a A. También, a toda forma bicondicional A  B que sea tautología se le llama equivalencia lógica. Observación. Si A  B es una tautología, entonces no es posible asignar valores de verdad a las variables proposicionales de A y B de manera que el valor de verdad de A sea diferente del valor de B .Es decir, A es equivalente a B cuando A es V si y sólo si B es V, y A es F si y sólo si B es F.

24

Apuntes de Álgebra I

Ejemplo. Probar que p  q equivale lógicamente a q  p. Es decir, p  q  q  p. Solución. Debemos probar que p  q ⟷ q  p es una tautología. En efecto, mediante una tabla de verdad se tiene p  q

⟷

q  p

V

V

V

V

V

V

V

V

V

F

V

F

es una tautología. Por tanto, p  q  q  p. Esta equivalencia se llama “ley conmutativa”. Observando la tabla anterior, se puede afirmar que dos formas proposicionales son equivalentes si ambas tienen la misma tabla de verdad. Ejemplo. Probar si p  ( p  q)  p  q. Solución. Verificaremos si la forma bicondicional p  ( p  q) ⟷ p  q, es una tautología. p

q

p

p  q

p  q

p  ( p  q)

p  ( p  q) ⟷ p  q

V

V

F

F

V

V

V

V

F

F

F

F

V

F

F

V

V

V

F

V

F

F

F

V

F

F

F

V

Observamos que el bicondicional es una contingencia. Entonces, concluimos que p  ( p  q) no es equivalente a p  q. En este caso, escribimos p  ( p  q) ≢ p  q. Nota. Si A no es lógicamente equivalente a B o simplemente A no es equivalente a B, escribimos A ≢ B o A ⇎ B. Propiedad La equivalencia lógica, es: a. Reflexiva. Para toda forma proposicional A, se tiene que A  A. b. Simétrica. Si A  B, entonces B  A. c. Transitiva. Si A  B y B  C, entonces A  C. 1.1.10 Álgebra de proposiciones o leyes lógicas Se pueden encontrar muchas equivalencias lógicas en la lógica proposicional, pero éstas pueden deducirse a partir de unas pocas equivalencias, a las que llamaremos leyes del álgebra de proposiciones o leyes lógicas.

25

Apuntes de Álgebra I

Las leyes lógicas o principios lógicos son equivalencias lógicas de carácter general y que a partir de éstas se pueden deducir otras más. Convenimos en usar T para representar cualquier tautología y C para cualquier contradicción.

Equivalencias o Leyes lógicas más comunes del Álgebra de Proposiciones 1. Idempotencia de la conjunción y la disyunción 1.1 p  p  p

1.2 p  p  p

2. Conmutatividad de la conjunción y la disyunción 2.1 p  q  q  p

2.2 p  q  q  p

3. Asociatividad de la conjunción y la disyunción 3.1 (p  q)  r  p  (q  r)

3.2 (p  q)  r  p  (q  r)

4. Distributividad de la disyunción () respecto de la conjunción () y de la conjunción () respecto de la disyunción (). 4.1 Disyunción respecto de la conjunción: p  (q  r)  (p  q)  (p  r) 4.2 Conjunción respecto de la disyunción: p  (q  r)  (p  q)  (p  r) 5. Leyes de identidad o elemento neutro 5.1 El elemento neutro de la disyunción es una contradicción: 5.2 Elemento neutro de la conjunción es una tautología:

p C  p p T  p

6. Leyes de dominación 6.1 p  T  T

6.2 p  C  C

7. Leyes de complementación 7.1 Tercio excluido: p   p  T 7.2 Contradicción: p   p  C 8. Leyes de De Morgan 8.1  (p  q)   p   q

8.2  (p  q)   p   q

9. Leyes de absorción 9.1 p  (p  q)  p

9.2

p  (p  q)  p

Tan importantes como las anteriores, existen otras equivalencias notables como las siguientes: 10. Doble negación p  p

26

Apuntes de Álgebra I

11.   T  C

 C  T

12. Ley del condicional:

p  q  p  q

13. Ley del bicondicional:

p ⟷ q  (p ⟶ q)  (q ⟶ p)

14. Ley de la disyunción exclusiva:

p  q  (p   q)  (q   p)

15. Ley de reducción al absurdo:

p ⟶ q  (p   q) ⟶ C

16. Ley del contrarrecíproco:

p ⟶ q  q ⟶ p

17. Ley de demostración por casos: (p  q) ⟶ r  (p ⟶ r)  (q ⟶ r) Estas leyes son útiles para simplificar los problemas (pues es válido reemplazar una proposición por su equivalente sin alterar el resultado) y para probar otras equivalencias. A este tipo de prueba se le llama prueba deductiva. Ejemplo. Demostrar que  (p  q)  (p   q)  ( p  q)  ( p   q) Solución. En efecto,  (p  q)   p   q

(por De Morgan)

 ( p  T)  ( q  T)

(por ley de identidad)

 [ p  (q   q)]  [ q  (p   p)]

(por tercio excluido)

 ( p  q)  ( p   q)  ( q  p)  ( q   p)

(por Ley distributiva)

 (p   q)  ( p  q)  [( p   q)  ( p   q)] (por ley conmutativa)  (p   q)  ( p  q)  ( p   q)

(por idempotencia de )

Ejemplo. Simplificar la proposición ( p  q)   p. Solución ( p ⟶ q)   p

 (  p  q)   p

(por ley del condicional)

 (p  q)   p

(por doble negación)

  p  (p  q)

(por ley conmutativa)

 ( p  p)  q

(por ley asociativa)

 T  q

(por tercio excluido)

 q  T

(por ley conmutativa)

 T

(por ley de dominación)

Por tanto, ( p ⟶ q)   p  T Ejemplo. Demostrar que  [ (p  q) ⟶  p]  C.

27

Apuntes de Álgebra I

Solución.  [ (p  q) ⟶  p]   [(p  q)   p]

(por ley del condicional)

  [(q  p)   p]

(por ley conmutativa)

  [q  (p   p)]

(por ley asociativa)

  [q  T]

(por tercio excluido)

 T

(por ley de dominación)

 C

(por negación de tautología)

Ejemplo. Simplificar la proposición [p  ( q  p)] ⟶ p. Solución [p  ( q  p)] ⟶ p  [p  (p   q)] ⟶ p  p ⟶ p

(por ley conmutativa) (por ley de absorción)

 p  p

(por ley del condicional)

 T

(por tercio excluido)

Por tanto, [p  ( q  p)] ⟶ p  T. Ejemplo. Probar deductivamente que p ⟷ q   (p  q)  (p  q). Solución.

Probaremos la equivalencia, empezando por la proposición del lado derecho de dicha

equivalencia. En efecto,  (p  q)  (p  q) 

( p   q)  (p  q)

(por De Morgan)



[(p  q)   p]  [(p  q)   q]



[(p   p)  (q   p)]  [(p   q)  (q   q)]

(por ley distributiva)

(por ley distributiva) 

[T  (q   p)]  [(p   q)  T] (por tercio excluido)



(q   p)  (p   q)

(por identidad)



(p ⟶ q)  (q ⟶ p)

(por condicional)



p ⟷ q

(por bicondicional)

Luego, por ser simétrica la equivalencia lógica, se cumple que: p ⟷ q   (p  q)  (p  q) Ejemplo. Probar deductivamente la siguiente equivalencia (p ⟶ q)  r  (r ⟶ p) ⟶ (q  r) Solución. Empezamos la prueba de la equivalencia, por la proposición por el lado derecho de ésta. En efecto, (r ⟶ p) ⟶ (q  r)  ( r  p) ⟶ (q  r) (por ley del condicional)  (r   p)  (q  r)

(por ley del condicional)

 ( p  r)  (q  r)

(por ley conmutativa)

 ( p  q)  r

(por ley distributiva)

28

Apuntes de Álgebra I

 (p ⟶ q)  r

(por ley del condicional)

Como la equivalencia lógica es simétrica, se tiene que: (p ⟶ q)  r  (r ⟶ p) ⟶ (q  r).

EJERCICIOS PROPUESTOS 1.

Demostrar por medio de tablas de verdad, que son equivalencias lógicas los bicondicionales siguientes: a) p  q ⟷  p  q

b) (p ⟷ q) ⟷ (p ⟶ q)  (q ⟶ p)

c) p  (p  q) ⟷ p

d) (p  q)  r ⟷ (p  r)  (q  r)

2. Probar, usando leyes lógicas, que la proposición siguiente es una tautología: (p   q)  q ⟶ p 3. Simplificar las siguientes expresiones: a)  [ (p  q) ⟶  q]  q

b) [( p  q) ⟶ (r   r)]   q

c) [( p  q) ⟶  q]   p

d) [( q ⟶  p) ⟶ ( p ⟶  q)]   (p  q)

4. Demostrar, en forma deductiva, las siguientes equivalencias. a) (p  q)  p  p

b) (p  q)  p  p

c)  (p ⟶ q)  (p   q)

d) (p ⟶ q)  [(p  q) ⟷ q]

5. Si la proposición (q   p) ⟶ (p  r)  t es falsa, hallar el valor de verdad de: a)  [( p   q) ⟶ (r   t) b) ( q   r)  [ t  (p  q)] c) ( p ⟶ t) ⟶ ( q ⟶ r) 6. Si la proposición (p ⟶  q) ⟶ (r  t) es falsa, encontrar el valor de verdad de la expresión (p  q)  (r  t) 7. Demostrar que (p ⟶  p)  ( p ⟶ p)  C. 8. Probar la siguiente equivalencia: (p ⟶ q)  r  p ⟶ (q  r) 1.1.11 Implicación lógica Supongamos que tenemos las formas proposicionales A: p  q y B: p  q, y las relacionamos en la forma condicional A ⟶ B. Entonces, sustituyendo A y B y construyendo la tabla de verdad del condicional p  q  p  q, tenemos que es una tautología; como se observa en la tabla

29

Apuntes de Álgebra I

p  q

⟶

p  q

V

V

V

F

V

V

F

V

V

F

V

F

Cuando ocurre este hecho diremos que “p  q implica lógicamente a p  q” o simplemente que “p  q implica a p  q”, y escribimos p  q ⟹ p  q. Entonces, no es lo mismo el concepto condicional “si A, entonces B” que el concepto implicación “A implica a B”. Es decir, en general A  B  A ⟹ B Definición.- Si A y B son dos formas proposicionales, se dice que A implica lógicamente a B, o simplemente A implica B, o que de A se deduce B; y escribimos A ⟹ B, si la forma condicional A ⟶ B es una tautología. Es decir, A ⟹ B si y sólo si A ⟶ B es una tautología

De la definición anterior podemos afirmar que: si una forma proposicional A implica a otra forma proposicional B, entonces B se deduce lógicamente de A (o que de A se deduce lógicamente B). Es decir, si cada asignación de valores lógicos que hacen a A verdadera, también hacen a B verdadera. De manera que si A ⟶ B es una tautología entonces no es posible asignar valores de verdad a las variables proposicionales de A y B tal que A sea verdadera (V) y B sea falsa (F). O sea, si A ⟶ B es una tautología y A es V, entonces necesariamente B es V. Por tanto, A ⟹ B significa que cuando A es verdadera, también B es verdadera y que cuando B es falsa, A es falsa. Por consiguiente, a toda forma proposicional condicional A  B, que sea tautología, se le llamará implicación lógica. Ejemplo. Probar que p  q implica a p  q. O sea, p  q ⟹ p  q. Solución. Probaremos, mediante una tabla de verdad, que (p  q) ⟶ (p  q) es una tautología. En efecto, p  q

⟶

p  q

F

V

V

V

V

V

V

V

V

F

V

F

30

Apuntes de Álgebra I

(p  q) ⟶ (p  q) es una tautología, como se observa en la tabla. Entonces, se tiene que la forma proposicional p  q implica lógicamente a la forma proposicional p  q, o simplemente p  q implica a p  q. Es decir, p  q ⟹ p  q. Ejemplo. Probar si p  q implica a p  q. Es decir, si p  q ⟹ p  q. Solución. En este caso debemos probar si el condicional p  q ⟶ p  q, es una tautología. Veamos, p  q

⟶

p  q

V

V

V

V

F

F

V

F

F

F

V

F

observamos, en la tabla, que p  q ⟶ p  q es una contingencia. Por tanto, se concluye que p  q no implica a p  q. Esta conclusión la denotamos por p  q ⇏ p  q. Nota. En general, dadas las formas proposicionales A y B; si A no implica lógicamente a B, escribimos A ⇏ B. Esto significa que la forma condicional A ⟶ B, no es una tautología. Proposición Sean A, B y C formas proposicionales. La implicación lógica es: 1. Reflexiva. Para toda forma proposicional A se cumple que A ⟹ A. 2. Antisimétrica. Si A ⟹ B y B ⟹ A, entonces A  B. 3. Transitiva. Si A ⟹ B y B ⟹ C, entonces A ⟹ C. Ejemplo. Demostrar deductivamente que (p ⟶ q)   q ⟹  p. Solución. Probaremos que (p ⟶ q)   q ⟶  p, es una tautología. En efecto, (p ⟶ q)   q ⟶  p  ( p  q)   q ⟶  p

(por ley del condicional)

 ( p   q)  (q   q) ⟶  p (por ley distributiva)  ( p   q)  C ⟶  p

(por de contradicción)

 ( p   q) ⟶  p

(por ley de identidad)

 (p  q)   p

(por condicional y De Morgan)

 (q  p)   p

(por ley conmutativa)

 q  (p   p)

(por ley asociativa)

 q  T  T

(por tercio excluido) (por ley de dominación))

Por tanto, (p ⟶ q)   q ⟹  p.

31

Apuntes de Álgebra I

Ejemplo. Simplificar la siguiente proposición ( p   q)  [ p  (q ⟶ p)] Solución. Usando las leyes de la lógica proposicional, se tiene: ( p   q)  [ p  (q ⟶ p)]  ( p   q)  [ p  ( q  p)]  ( p   q)  [( p   q)  ( p  p)]  ( p   q)  [( p   q)  C]  ( p   q)  ( p   q)  [( p   q)   p]   q  p  q Por tanto, ( p   q)  [ p  (q ⟶ p)]   p   q Ejemplo. Demostrar que el siguiente condicional es una implicación lógica: (p ⟶ q)  (q ⟶ r) ⟶ (p ⟶ r) Solución. De acuerdo a la definición, probaremos que (p ⟶ q)  (q ⟶ r) ⟶ (p ⟶ r) es una tautología, es decir (p ⟶ q)  (q ⟶ r) ⟶ (p ⟶ r)  T En efecto, (p ⟶ q)  (q ⟶ r) ⟶ (p ⟶ r)   [(p ⟶ q)  (q ⟶ r)]  (p ⟶ r)  [ (p ⟶ q)   (q ⟶ r)]  (p ⟶ r)  [ ( p  q)   ( q  r)]  ( p  r)  [(p   q)  (q   r)]  ( p  r)  [(p   q)   p]  [(q   r)  r]  [(p   p)  ( p   q)]  [(q  r)  ( r  r)]  [T  ( p   q)]  [(q  r)  T]  ( p   q)  (q  r)   p  ( q  q)  r  p  T  r  T Por tanto, (p ⟶ q)  (q ⟶ r) ⟹ (p ⟶ r)

EJERCICIOS PROPUESTOS 1. Probar que p implica lógicamente a p  q. 2. Usando las layes del álgebra proposicional simplificar la expresión  p ⟶ (q ⟶  p) 3. Probar deductivamente que (p ⟶ q)   q ⟹  p.

32

Apuntes de Álgebra I

4. Probar deductivamente que la siguiente expresión es una contradicción, p   (q  p) 5. Si p es una proposición cualquiera, probar que a) C  p b) p  T 6. Demostrar que los siguientes condicionales son implicaciones lógicas : a)  p ⟶ (p ⟶ q) b) p  q ⟶ p c) (p ⟷ q) ⟶ (p ⟶ q) 1.1.12 Inferencia lógica La teoría de la inferencia lógica, llamada teoría de la deducción, teoría de la demostración o teoría del razonamiento correcto, constituye una de las partes más importantes de la lógica proposicional. Dado que no siempre es factible construir una tabla de verdad para comprobar la validez de un razonamiento (cuando el número de proposiciones es elevado, la tabla puede ser excesivamente larga y laboriosa) utilizaremos el método deductivo, que se da a la implicación lógica. Una inferencia (razonamiento, deducción o argumento) es una operación lógica que consiste en derivar a partir de la verdad de ciertas proposiciones conocidas como premisas la verdad de otra proposición conocida como conclusión. Las reglas de inferencia son técnicas que nos ayudan en las demostraciones de los teoremas. Cada regla de inferencia tiene su origen en una implicación lógica. 1.1.12.1 Razonamiento En esta parte se estudia el significado formal del concepto de razonamiento válido y lo utilizamos para demostrar la veracidad de proposiciones a través de las reglas de inferencia. Definición.- Un razonamiento es el proceso de pasar de un conjunto de proposiciones dadas, llamadas premisas, a una proposición llamada conclusión. Entonces, llamaremos razonamiento a cualquier proposición con la estructura P1  P2  . . .  Pn ⟶ C siendo n un entero positivo. A las proposiciones P1

,

P2 , . . . , Pn se les llama premisas del razonamiento y a la proposición C la

conclusión. La proposición anterior se puede escribir usando el siguiente esquema (notación clásica):

33

Apuntes de Álgebra I

P1 P2 . . . Pn _____ C Las premisas de un razonamiento son proposiciones que nos proporcionan las razones para aceptar la conclusión. Preceden a las premisas, las palabras “luego”, “por tanto”, “puesto que”, “ya qué”, “si”, “pues”, “siempre que”, etc. Además, la conclusión de un razonamiento es la proposición que se afirma sobre las bases de las premisas. En resumen, diremos que la proposición C, llamada conclusión, se infiere de las proposiciones P1

,

P2 ,

. . . , Pn , llamadas premisas. C será verdadero cuando todas las Pi , i = 1, 2, 3, … , n lo sean, es decir cuando P1  P2  . . .  Pn ⟹ C. Significa, entonces, que cada razonamiento válido o inferencia tendrá su origen en una implicación lógica. Ejemplos: a)

Ningún metaloide es metal, puesto que todos los metales son cuerpos brillantes y ningún metaloide es cuerpo brillante (inferencia desordenada). Premisas: 1. Todos los metales son cuerpos brillantes. 2. Ningún metaloide es cuerpo brillante. Conclusión:

Luego, ningún metaloide es metal.

b) Si la figura tiene cuatro lados, es un cuadrilátero. Si la figura tiene tres lados, es un triángulo. La figura tiene cuatro lados o tres lados. Por tanto, la figura es un cuadrilátero o es un triángulo. Premisas: 1. Si la figura tiene cuatro lados, es un cuadrilátero. 2. Si la figura tiene tres lados, es un triángulo. 3. La figura tiene cuatro lados o tres lados. Conclusión:

Por tanto, la figura es un cuadrilátero o es un triángulo.

En forma simbólica, sean las proposiciones p: la figura tiene cuatro lados. q: la figura es un cuadrilátero. r: la figura tiene tres lados. s: la figura es un triángulo

34

Apuntes de Álgebra I

Premisa 1. p ⟶ q Premisa 2. r ⟶ s Premisa 3. p  r __________ Conclusión  q  s

Ejemplo. Simbolizar el razonamiento siguiente: Sin mandato judicial ni autorización de la persona que lo habita, no se puede ingresar en el domicilio, tampoco efectuar investigación. Pero se ingresó al domicilio y efectuó investigación. En consecuencia, hubo mandato judicial y autorización de la persona que lo habita. Solución. Para las variables proposicionales podemos usar cualquier letra minúscula (las más comunes son p, q, r, etc.) y las proposiciones se escriben en forma afirmativa. Así, m: hay mandato judicial. a: hay autorización de la persona que lo habita. d: se puede ingresar en el domicilio. i: se puede efectuar investigación. Premisa 1. ( m   a)  ( d   i) Premisa 2. d  i ______________________ Conclusión  m  Observación. En el enunciado anterior, la forma lógica de la premisa 1 es: Premisa 1: Si no hay mandato judicial y no hay autorización de la persona que lo habita, entonces no se puede ingresar en el domicilio y no se puede efectuar investigación. El razonamiento anterior ¿es válido o correcto?. (verificar usando una tabla de verdad) Ejemplo. La siguiente secuencia de proposiciones es un razonamiento. Si no llueve, entonces se perderá la cosecha. Si se pierde la cosecha, entonces no se podrá cancelar la deuda. ____________________________________________________ Por tanto, si no llueve, no se podrá cancelar la deuda. En este esquema, los enunciados que están encima de la línea horizontal son las premisas. Reemplazando cada proposición por una variable proposicional, tenemos: p: llueve q: se perderá la cosecha r: se podrá cancelar la deuda En forma simbólica, escribimos: Premisa 1:  p  q Premisa 2: q   r _____________________ Conclusión:  p   r

35

Apuntes de Álgebra I

Notas: 1. Un razonamiento puede ser una tautología, una contingencia o una contradicción. Estaremos interesados, entonces, en aquellos razonamientos que de premisas verdaderas se deriven conclusiones verdaderas. Estos son los llamados razonamientos válidos. 2. Verdad y validez. Verdad, es un concepto semántico que se usa sólo para calificar a las proposiciones, mientras que validez es un concepto que se usa para calificar la coherencia formal de los razonamientos válidos o inferencias.

EJERCICIOS PROPUESTOS 1. Simbolizar los razonamientos siguientes. a) La figura no es un cuadrilátero, puesto que es un triángulo. La figura es un triángulo. En consecuencia, la figura no es un cuadrilátero. b) El triángulo no se llama equilátero a menos que tenga tres lados de medidas iguales. Si se llama equilátero, no se llama isósceles. En consecuencia, si tiene tres lados de medidas iguales, no se llama isósceles. c) Sin variables ni operadores, no hay lenguaje lógico posible. No hay variables ni operadores. Por tanto, no hay lenguaje lógico posible. d) La “p” es una variable proposicional o es un operador lógico, pero no puede ser ambas cosas a la vez. En consecuencia, es falso que la “p” sea un operador lógico. e) Un número es divisible por dos si termina en cero o en cifra par. Un número es divisible por cinco si termina en cero o en cinco. Por tanto, un número es divisible por dos si no termina en cinco. f) Los profesores ordinarios son principales, asociados y auxiliares. Los profesores extraordinarios son eméritos, honorarios, investigadores y visitantes. Luego, los profesores ordinarios son principales, asociados y auxiliares. g) Si un número natural es primo, es mayor que uno. Es divisible por si mismo si es primo. Por tanto, es divisible por si mismo si es mayor que uno. h) Si dos es un número natural, su opuesto es un número entero y no un número natural. Es falso que el opuesto de dos sea un número entero y no sea un número natural. Luego, dos es un número natural o entero. 1.1.12.2 Razonamientos válidos Definición.- Un razonamiento es válido o correcto si la conjunción de las premisas implica lógicamente a la conclusión. Es decir, si P1  P2  . . .  Pn  C En otros términos, si P1  P2  . . .  Pn  C es una tautología. Nota. Si nos piden demostrar la validez del razonamiento

36

Apuntes de Álgebra I

P1 P2 . . . Pn _____ C O, lo que es lo mismo, P1  P2  . . .  Pn  C ; debemos probar que P1  P2  . . .  Pn  C es una tautología Falacia A un razonamiento que no es válido se le llama falacia. Veamos ejemplos de las falacias más habituales. Ejemplo. La falacia de afirmar el consecuente. Estudiar la validez del siguiente razonamiento: Si Grau nació en Piura, entonces Grau es peruano Grau es peruano __________________________________________ Por tanto, Grau nació en Piura. Sean las proposiciones: p: Grau nació en Piura q: Grau es peruano El razonamiento escrito en forma simbólica es: Premisa 1. Premisa 2.

p ⟶ q q _______  p

Verificamos la validez del razonamiento, mediante la tabla de verdad de: (p ⟶ q)  q ⟶ p, usando el método acumulativo (p ⟶ q)  q

(p ⟶ q)  q ⟶ p

p

q

(p ⟶ q)

V

V

V

V

V

V

F

F

F

V

F

V

V

V

F

F

F

V

F

V

Observamos que la matriz de la proposición (p ⟶ q)  q ⟶ p es una contingencia. Por tanto el razonamiento no es válido. Es decir, es una falacia y por tanto, (p ⟶ q)  q ⇏ p

37

Apuntes de Álgebra I

Ejemplo. La falacia de negar el antecedente. Estudiar la validez del siguiente razonamiento: Si las manos del mayordomo están manchadas de sangre, entonces es culpable. Las manos del mayordomo no están manchadas de sangre. ________________________________________________________________ Luego, el mayordomo es inocente. Sean las proposiciones: p: El mayordomo tiene las manos manchadas de sangre. q: El mayordomo es culpable. En forma simbólica: (p ⟶ q)

Premisa 1. Premisa 2.

p _______ q

Verificamos la validez del razonamiento, mediante la tabla de verdad de: (p ⟶ q)   p ⟶  q. p

q

p

q

p ⟶ q

(p ⟶ q)   p

(p ⟶ q)   p ⟶  q

V

V

F

F

V

F

V

V

F

F

V

F

F

V

F

V

V

F

V

V

F

F

F

V

V

V

V

V

Observamos que los valores de verdad de la proposición (p ⟶ q)   p ⟶  q es una contingencia. Por tanto el razonamiento no es válido. Es decir, es una falacia y por consiguiente (p ⟶ q)   p ⇏  q 1.1.12.3 Reglas de inferencia Se presentan a continuación las reglas de inferencias más usuales (algunas llevan nombres en latín): REGLAS DE INFERENCIAS 1. Modus Ponendo Ponens (MPP) p ⟶ q p ________

O bien, (p ⟶ q)  p ⟹ q

q Según el Modus (método) Ponendo Ponens, afirmando (Ponendo) el antecedente de una premisa condicional se concluye que podemos afirmar (Ponens) el consecuente. 2. Modus Tollendo Tollens (MTT)

38

Apuntes de Álgebra I

p ⟶ q q ________ p

O bien, (p ⟶ q)   q ⟹  p

Según el Modus (método) Tollendo Tollens, negando (Tollendo) el consecuente de una premisa condicional se concluye que podemos negar (Tollens) el antecedente. 3. Silogismo Disyuntivo (SD) o Modus Tollendo Ponens (MTP) a) p  q q _______ p

O bien (p  q)   q ⟹ p

b) p  q p _______ q

O bien (p  q)   p ⟹ q

Según el SD, negando (Tollendo) uno de los componentes de una premisa disyuntiva, se puede afirmar (Ponens) el otro componente . 4. Silogismo Hipotético (SH) p ⟶ q q ⟶ r ________ p ⟶ r

Es decir, (p ⟶ q)  (q ⟶ r) ⟹ (p ⟶ r)

El silogismo hipotético, es una inferencia que responde a la transitividad del condicional. 5. Ley de Simplificación (LS) a)

p  q ______ p

b) p  q ______ q

O bien p  q ⟹ p

O bien p  q ⟹ q

6. Ley de Adición (LA) a)

p ______ p  q

b) q ______ p  q

O bien p ⟹ p  q

O bien q ⟹ p  q

39

Apuntes de Álgebra I

7. Ley de la Conjunción (LC) p O bien p  q ⟹ p  q

q ______ p  q

Se prueba que estas formas proposicionales son implicaciones lógicas. Además, sirven para demostrar la validez de un razonamiento en forma deductiva. Ejemplo. Demostrar la validez del razonamiento siguiente. q ⟶ p q ⟶ r ___________ p ⟶ r Solución. La validez de este razonamiento podemos demostrarlo por tres formas: por tablas de verdad, por el método abreviado y por el método deductivo. Usaremos éste último. Método Deductivo Cuando el razonamiento tiene varias variables, la prueba de validez de un razonamiento, mediante las tablas de verdad, se hace muy laborioso. Para evitar esta dificultad, contamos con otro método que lo llamaremos método deductivo. Este método consiste en dividir el razonamiento en una secuencia de razonamientos cortos, simples y que de antemano sabemos que son válidos. Para ello utilizamos las leyes de la lógica proposicional y las reglas de inferencias. Entonces, en el ejercicio, tenemos: 1.  q ⟶  p

Premisa 1.

2. q ⟶ r

Premisa 2.

3. p ⟶ q

De 1, por ley del contrarrecíproco.

4. p ⟶ r

De 3 y 2, por el Silogismo Hipotético.

Por tanto, el razonamiento es válido y ( q ⟶  p)  (q ⟶ r) ⟹ (p ⟶ r). Ejemplo. Probar deductivamente la validez del razonamiento siguiente. r ⟶ q p ⟶ q r  t p ___________ t Solución. 1. r ⟶ q

Premisa 1.

2.  p ⟶  q

Premisa 2.

3. r  t

Premisa 3.

40

Apuntes de Álgebra I

4.  p

Premisa 4.

5.  q

De 2 y 4, por MPP.

6.  r

De 1 y 5, por MTT.

7. t

De 3 y 6 , por SD.

Ejemplo. Obtenga la conclusión del conjunto de premisas que aparecen en el siguiente párrafo. Si el cielo está nublado y hace frío, entonces no se llevará a cabo el concurso de natación. Ocurre que el cielo está nublado y hace frío. Por tanto, . . . Solución. En forma simbólica, escribimos, p: El cielo está nublado. q: Hace frío r: Se llevará a cabo el concurso de natación. Luego, tenemos: p  q ⟶ r p  q _____________ r

Por el Modus Ponendo Ponens.

Por tanto, la conclusión es: no se llevará a cabo el concurso de natación. Ejemplo. Probar que el razonamiento siguiente es válido. Si Juan se casa, entonces tiene que trabajar; y si trabaja no podrá estudiar. Si Juan no se casa, entonces perderá mucho tiempo visitando a su novia; y si pierde tiempo, no podrá estudiar. Si Juan no estudia, sus padres se sentirán infelices. Luego, los padres de Juan se sentirán infelices. Solución. Variables proposicionales: c: Juan se casa t: Juan tiene que trabajar e: Juan podrá estudiar n: Juan perderá mucho tiempo visitando a su novia p: Los padres de Juan se sentirán infelices Simbolizamos el razonamiento: 1. (c ⟶ t)  (t ⟶  e) 2. ( c ⟶ n)  (n ⟶  e) 3.  e ⟶ p _______________________ p Demostración. 1. (c ⟶ t)  (t ⟶  e)

Premisa 1

2. ( c ⟶ n)  (n ⟶  e)

Premisa 2

3.  e ⟶ p

Premisa 3

41

Apuntes de Álgebra I

4. c ⟶ t

de 1, por LS

5. t ⟶  e

de 1, por LS

6. c ⟶  e

de 4 y 5, por SH

7.  c ⟶ n

de 2, por LS

8. n ⟶  e

de 2, por LS

9.  c ⟶  e

de 7 y 8, por SH

10. e ⟶  c

de 6, por ley del contrarrecíproco

11. e ⟶  e

de 10 y 9, por SH

12.  e   e

de 11, por ley del condicional

13.  e

de 12, por ley idempotente

14. p

de 3 y 13, por MPP

Ejemplo. Demostrar la validez del razonamiento siguiente. Si estudio computación, ganaré mucho dinero. Si estudio periodismo, conoceré mucha gente. Si gano mucho dinero o conozco mucha gente, seré feliz. Por tanto, si no soy feliz, no estudié computación ni estudié periodismo. Solución. Variables proposicionales: c: estudio computación d: ganaré mucho dinero p: estudio periodismo g: conoceré mucha gente f: seré feliz Simbolizamos el razonamiento: 1. c ⟶ d 2. p ⟶ g 3. (d  g) ⟶ f ________________  f ⟶ ( c   p) Demostración. 1. c ⟶ d

Premisa 1

2. p ⟶ g

Premisa 2

3. (d  g) ⟶ f

Premisa 3

4.  (d  g)  f

de 3, por ley del condicional

5. ( d   g)  f

de 4, por De Morgan

6. ( d  f)  ( g  f)

de 5, por ley distributiva

7. g ⟶ f

de 6, por leyes de simplificación y condicional

8. p ⟶ f

de 2 y 7, por silogismo hipotético

9. d ⟶ f

de 6, por leyes de simplificación y condicional

42

Apuntes de Álgebra I

10. c ⟶ f

de 1 y 9, por silogismo hipotético

11. (p ⟶ f)  (c ⟶ f)

de 8 y 10, por ley de la conjunción

12. ( p  f)  ( c  f)

de 11, por ley del condicional

13. ( p   c)  f

de 12, por ley distributiva

14.  (p  c)  f

de 13, por De Morgan

15. (p  c) ⟶ f

de 14, por ley del condicional

16.  f ⟶  (p  c)

de 15, por ley del contrarrecíproco

17.  f ⟶ ( p   c)

de 16, por De Morgan

18.  f ⟶ ( c   p)

de 17, por ley conmutativa

Ejemplo. Para el conjunto de premisas siguientes decir cuál es la conclusión y la regla de inferencia utilizada. Todas las funciones trigonométricas son periódicas y todas las funciones periódicas son continuas. Solución. Sean las proposiciones: p: función trigonométrica. q: función periódica. r: función continua. Argumento propuesto: (p ⟶ q)  (q ⟶ r) siendo la regla de inferencia, (p ⟶ q)  (q ⟶ r) ⟹ (p ⟶ r) o también, p ⟶ q q ⟶ r _________ p ⟶ r

Silogismo hipotético

La conclusión es: Todas las funciones trigonométricas son continuas. Observación. La expresión: Todas las funciones trigonométricas son periódicas, se puede expresar por el condicional: Si una función es trigonométrica, entonces es periódica Nota. Cuando se definen conceptos matemáticos, generalmente se utiliza el condicional. Consideremos, por ejemplo, el universo de todos los triángulos del plano. Definición.- Si un triángulo tiene sus tres lados de medidas iguales, entonces es equilátero.

43

Apuntes de Álgebra I

La definición se deduce del hecho que: Todos los triángulos que tienen sus tres lados de medidas iguales son equiláteros Ejemplo. Demostrar la validez del razonamiento siguiente: El cielo azul me pone contento y el cielo gris me pone triste. El cielo está azul o gris. Por tanto, estoy contento o triste. Solución. Sean las proposiciones: p: el cielo está azul. q: el cielo está gris. r: estoy contento. s: estoy triste. La proposición: el cielo azul me pone contento, es un condicional de la forma, si el cielo está azul, entonces estoy contento Entonces, en forma simbólica, las premisas son: (p ⟶ r)  (q ⟶ s) p  q ________________ r  s Demostración. 1. (p ⟶ r)  (q ⟶ s)

Premisa 1

2. p  q

Premisa 2

3. p ⟶ r

de 1, por ley de simplificación

4.  p ⟶ q

de 2, por ley del condicional

5.  r ⟶  p

de 3, por ley del contrarrecíproco

6.  r ⟶ q

de 5 y 4, por silogismo hipotético

7. q ⟶ s

de 1, por ley de simplificación

8.  r ⟶ s

de 6 y 7, por silogismo hipotético

9. r  s

de 8, por ley del condicional

Ejemplo. Demostrar la validez del razonamiento siguiente: p  q p ⟶ r _______ r  q

O bien, (p  q)  (p ⟶ r) ⟹ (r  q)

Solución. 1. p  q

Premisa 1

2. p ⟶ r

Premisa 2

3. p

de 1, por ley de simplificación

4. r

de 2 y 3, por MPP

44

Apuntes de Álgebra I

5. q

de 1, por ley de simplificación

6. r  q

de 4 y 5, por ley de la conjunción.

Otra forma: (p  q)  (p ⟶ r) ⟺ (q  p)  (p ⟶ r) Conmutatividad de  ⟺ q  [p  (p ⟶ r)] Asociatividad de  ⟹ q  r

Modus Ponendo Ponens

⟹ r  q

Conmutatividad de 

EJERCICIOS PROPUESTOS 1. Para cada uno de los siguientes conjuntos de premisas, decir cuáles son las conclusiones y las reglas de inferencia utilizadas en cada caso.

a) Estoy gordo o delgado. Ciertamente no estoy delgado. b) Si corro, me quedaré sin aliento. No estoy sin aliento. c) Si el mayordomo lo hizo, entonces tiene las manos sucias, Las manos del mayordomo no están sucias.

d ) Todas las funciones trigonométricas son periódicas y todas las funciones periódicas son continuas. 2. Fue X o Y quién cometió el crimen. X estaba fuera del pueblo cuando el crimen fue cometido. Si X estaba fuera del pueblo, no pudo haber estado en la escena del crimen. Si X no estaba en la escena del crimen, no pudo haber cometido el crimen.

a) Represente en forma simbólica el conjunto de premisas y obtenga la conclusión usando reglas de inferencia.

b) ¿Quién cometió el crimen? c) Demostrar la validez del razonamiento. 3. Demostrar los siguientes razonamientos, usando el método deductivo. a)

p ⟷ q r  q r ________ q

b)

p  q (p  q) ⟶ r r ⟶ s __________ s

45

Apuntes de Álgebra I

c) p   q r ⟶ p r ⟶ t _________ q  t d)

p ⟶ q r ⟶ q  ( p   t) t ⟶ s r ____________ s r ⟶ q

e)

p ⟶ q r  t p ___________ t f) r ⟶ p  p  ( q  r) t  r ⟶ h r  h _______________ q ⟶ t g)

a  b ⟶ d d ⟶ (p ⟶  t) q  (p  t) _______________ a  b ⟶ q

h)

r  h h r ⟶ q q  (p  t) ___________ t

4. Probar la validez de los siguientes razonamientos, usando el método deductivo: a) p _________  (p  q)

46

Apuntes de Álgebra I

b)

p  r ⟶ q s ⟶ p

r _____________ s ⟶ q c)  q ⟶  p r q ⟶ t p  r _____________ t d)

t ⟶ p p ⟶ (r ⟶ q) r _____________ q ⟶ t

5. Probar la validez de los razonamientos siguientes, usando el método deductivo: a) Si el testigo dice la verdad, entonces el mayordomo estaba en la escena del crimen. Pero el mayordomo no estaba en la escena del crimen. En consecuencia, el testigo no dice la verdad. b) El agua se congela si y sólo si la temperatura está bajo cero. Ocurre que el agua no se congela. Por tanto, si la temperatura está bajo cero entonces la refrigeradora está malograda. c) Si el paquete es liviano y no es muy grande, el correo lo aceptará. Si el paquete contiene ropa, entonces es liviano. El paquete no es muy grande. Luego, si el paquete contiene ropa, el correo lo aceptará. d) Si llego a tiempo, cenaré, siempre que tenga apetito. No cené y tengo apetito. En consecuencia, no llegué a tiempo. e) Si no hay tormenta, entonces no es cierto que no me quedaré en casa y no dormiré temprano. Si hay muchas nubes negras, entonces no habrá tormenta. Si viene Pedro, no iré al cine. Es suficiente que haya muchas nubes negras para que Pedro venga. Voy al cine. Luego, me quedo en casa o me duermo temprano. 1.1.13 Cuantificadores Uno de los principales elementos formales en las proposiciones son los llamados cuantificadores. Los cuantificadores son términos del lenguaje que especifican si un enunciado se refiere a todos los elementos de un conjunto o sólo a algunos de ellos; es decir, sirven para distinguir entre enunciados de carácter general y particular. El enunciado x + 5 = 0, donde x es cualquier objeto, no es una proposición, pues no se sabe que es x. Pero, si especificamos en cada discusión que objetos se van a considerar, se puede lograr que el enunciado anterior tenga algún sentido.

47

Apuntes de Álgebra I

Por ejemplo: a) Objetos a considerar: números enteros. Si x se reemplaza por -5, el enunciado es una proposición verdadera. Si x se reemplaza por cualquier otro número entero, diferente de cinco, el enunciado es una proposición falsa. - 5 + 5 = 0 (V), x + 5 = 0 (F), para todo x  5 b) Objetos a considerar: nombres de personas. Si x se reemplaza por “Ruth”, el enunciado Ruth + 5 = 0 no tiene sentido. Más aún, si x se reemplaza por cualquier “nombre de persona” el enunciado no tiene sentido. Función Proposicional En su forma más intuitiva, una función proposicional es una expresión que contiene una variable, y que se transforma en proposición cuando se reemplaza la variable por un elemento de un conjunto A, dado. Notación. Se representará una función proposicional por P(x), Q(x), R(x), etc. , donde x es la variable. P (x) se lee: “x tiene la propiedad P” o “x cumple la propiedad P”. Ejemplo. Sean A = , P(x): 2x + 1 = 5 y Q(x): x + 1 es número primo. a) Sea la expresión P(0) ⟶ Q(0). La expresión así escrita, ¿es proposición?. Si los es, ¿cuál es su valor de verdad?. b) Sea la expresión P(1) ⟶ Q(1). La expresión así escrita, ¿es proposición?. Si los es, ¿cuál es su valor de verdad?. c) ¿P(x) ⟶ Q(x) es función proposicional? Justifique su respuesta. Solución. a) P(0) ⟶ Q(0) es equivalente a la expresión: 20 + 1 = 5 ⟶ 0 + 1 es número primo O también a: Si 20 + 1 = 5, entonces 0 + 1 es número primo la cual es una proposición condicional. El valor de verdad de esta proposición es verdadera (V); pues tanto el antecedente como el consecuente son falsos. b) En forma análoga, P(1) ⟶ Q(1) es equivalente a la expresión 21 + 1 = 5 ⟶ 1 + 1 es número primo la cual es una proposición condicional verdadera (V), pues el consecuente es verdadero. c) P(x) ⟶ Q(x)   P(x)  Q(x). Entonces, P(x) ⟶ Q(x) es una función proposicional, ya que tanto  P(x) como Q(x) son funciones proposicionales y la disyunción de estas dos, es otra función proposicional. En efecto,

48

Apuntes de Álgebra I

 P(x)  Q(x):  (2x + 1 = 5)  x + 1 es primo  2x + 1  5  x + 1 es primo. Haciendo,  P(x)  Q(x) = R(x), se tiene R(x): 2x + 1  5  x + 1 es número primo Por tanto, tenemos la función proposicional (A, R(x)). Observaciones: 1.

Para tener una función proposicional no basta contar con solamente un enunciado que contenga variables (como por ejemplo P(x)); se debe contar, además, con un conjunto A en el cual la variable (o variables) tomen sus valores. Este conjunto A se llama dominio de la función proposicional o conjunto de variación de la variable. En este caso se puede expresar la función proposicional por

(A, P(x)). Ejemplo. Sea la función proposicional (A, P(x)) donde A = {0, 1, 2, 3, 4} y P(x): 2 x  6 Esta función proposicional da lugar a las siguientes proposiciones.  P (0): 2 (0)  6 (V)  P (1): 2 (1)  6 (V)  P (2): 2 (2)  6 (V)  P (3): 2 (3)  6 (F)  P (4): 2 (4)  6 (F) Se observa que con los elementos 0, 1 y 2 de A se obtienen proposiciones verdaderas. Al conjunto formado por estos elementos que hacen verdadero a P(x), {0, 1, 2} se le llama dominio de verdad de la función proposicional dada. 2. Si P (x), Q (x), R (x), etc. Son funciones proposicionales, entonces también lo son:  P (x), P (x) ∗ Q(x); donde ∗ representa a un conectivo lógico. Ejemplo. Consideremos la función proposicional (A, P(x)) tal que A = {1, 3, 4, 5, 7} y P(x): x2 + 4  20 ¿cuál de las expresiones siguientes se cumple?  P(x) es verdadera para todos los elementos de A.  P(x) es verdadera para algunos elementos de A.  P(x) es verdadera para un único elemento de A. Veamos:  P (1) : 12 + 4  20 (V)

 P (3) : 32 + 4  20 (V)

 P (4) : 42 + 4  20 (V)

 P (5) : 52 + 4  20 (F)

 P (7) : 72 + 4  20 (F)

49

Apuntes de Álgebra I

Respuesta. P (x) es verdadero para algunos elementos de A (para tres elementos de A). Los términos todos, algunos, un único; por indicar cantidad son llamados cuantificadores. Los principales son: todos y algunos. 1.1.13.1 El cuantificador universal El cuantificador “todos” se llama cuantificador universal y se representa con el símbolo . Definición.- Sea (A, P (x)) una función proposicional. Se dice que la expresión “para toda x en A, P (x)” es una afirmación cuantificada universalmente. Nota. El símbolo  significa

“para todo”, “todos”, “para cada”, “para cualquiera”. Entonces la

afirmación para toda x en A, P (x) se escribe  x  A, P (x) y se lee “para todo x que pertenece al conjunto A, se cumple la propiedad pe de x”. Al símbolo  se le llama cuantificador universal. A las proposiciones que tienen la forma:  x  A, P (x), se les llama proposiciones universales y también se pueden leer como: “para cada x de A, P (x)”, “para cualquier x de A, P (x)”, “todo x de A, P (x)”, “para cualquier x en A, P (x)”. Notas: 1) Cuando el dominio A de P (x) está sobreentendido, la proposición universal se escribe:  x, P (x). 2) La proposición:  x  A, P (x) es verdadera, si P (x) es verdadera para toda x en A. Es decir, si el dominio de verdad de P (x) coincide con A. 3) La proposición:  x  A, P (x) es falsa, si P(x) es falsa para al menos un x en A. Ejemplo. Si A =

y P (x): x2 – 1  0, la afirmación cuantificada universalmente x

, x2 – 1  0

es falsa, pues si x = 1, la proposición P (1): 12 – 1  0 es falsa. Cuando ocurre lo anterior, se dice que el valor x = 1 es un contraejemplo de la proposición universal x

, x2 – 1  0.

50

Apuntes de Álgebra I

Las proposiciones universales son generalizaciones de las conjunciones, es decir, cuando el dominio A es finito se puede entender la cuantificación universal como una forma abreviada de la conjunción. Para ello, supongamos que el dominio A, de la función proposicional P (x), es un conjunto finito cuyos elementos son: a1, a2, … ,an. Entonces,  x  A, P (x) es verdadera ⟺ P (a1), P (a2), … , P (an) son proposiciones verdaderas ⟺ P (a1)  P (a2)  …  P (an) es verdadera. Luego,  x  A, P (x)  P (a1)  P (a2)  …  P (an) Ejemplo. Si el dominio de la variable x es el conjunto A = {1, 2, 3, 4}, tal que la proposición  x  A, P (x) es verdadera, entonces se puede entender como que la proposición P (1)  P (2)  P (3)  P (4) es verdadera. Ejemplo. Para A = {3, 4, 5, 7} y P (x): x + 1 es un número par, la proposición  x  A, P (x) es falsa. Pues, para x = 4, P (4): 4 + 1 = 5 es un número par, es falso. Nota. Un valor x en el dominio A que hace que P (x) sea falsa se llama contraejemplo de la afirmación  x  A, P (x) (Un contraejemplo, para la proposición anterior es x = 4) Ejemplo. Simbolizar las siguientes proposiciones y determinar su valor lógico. a) Cualquier número entero positivo es menor que el doble de él. En este caso el dominio A =

+

= {1, 2, 3, … } y P (n): n  2n, con n 

+

. Luego,

tenemos: n

+

, n  2n

Esta proposición es verdadera, pues: n  2n ⟹ 2n – n  0 ⟹ n 0 ⟹ n 

+

b) Todos los televisores son de pantalla plana. En este caso, hagamos A = T = {televisores} y P (a): a es un televisor de pantalla plana. Entonces, tenemos:  a  T, P (a) Esta proposición es falsa, pues existen televisores que no son de pantalla plana. Nota. Definiciones matemáticas. Cuando se definen conceptos matemáticos, normalmente se utiliza el condicional. Sea, por ejemplo, el universo de todos los triángulos del plano. En un libro se puede tener la siguiente definición:

51

Apuntes de Álgebra I

“Si un triángulo tiene sus tres lados de medidas iguales, entonces el triángulo es equilátero” y en otro texto, la siguiente: “Si un triángulo es equilátero, entonces el triángulo tiene sus tres lados de medidas iguales” En ambos casos se están utilizando proposiciones cuantificadas universalmente. En efecto, sean P (x): x tiene tres lados de medidas iguales. Q (x): x es un triángulo equilátero. Entonces, en notación simbólica el primer texto afirma ( x) [P (x) ⟶ Q (x)] y el segundo ( x) [Q (x) ⟶ P (x)] Observamos que una de las proposiciones es recíproca de la otra y, si tenemos en cuenta que una proposición y su recíproca no son, en general, equivalentes; entonces ¿cuál de las dos definiciones es la correcta?. La respuesta es que ambas lo son, en el sentido que los dos textos utilizan el condicional como un bicondicional, es decir ( x) [P (x) ⟷ Q (x)] O sea que los dos están diciendo que “Un triángulo es equilátero si, y sólo si tiene sus tres lados de medidas iguales” En conclusión: En las definiciones un condicional puede leerse e interpretarse correctamente como un bicondicional. Ejemplo. En el universo de los números enteros, podemos definir el concepto de divisibilidad de la siguiente forma: “Para cada par de enteros x e y, se dice que x es divisible por y si x es múltiplo de y” Pero, ¿qué significa “ser múltiplo de”?. Significa que “x es múltiplo de y si, y sólo si puede encontrarse otro número entero k tal que x = k ⋅ y” Si llamamos R (x, y): x = k ⋅ y, en símbolos se tiene ( x) ( y) [Q (x, y) ⟷  k / R (x, y)] y relacionando esta definición con la anterior, se tendrá que ( x) ( y) [P (x, y) ⟷  k / R (x, y)] Entonces, otra forma de definir la divisibilidad sería: “Para cada par de números enteros x e y, se dice que x es divisible por y si, y sólo si existe un entero k tal que x = k ⋅ y”. 1.1.13.2 El cuantificador existencial El cuantificador “algunos” se llama cuantificador existencial, y se lo representa con el símbolo . Definición.- Sea (A, P (x)) una función proposicional. Se dice que la afirmación “existe x en A tal que P (x)”

52

Apuntes de Álgebra I

es una afirmación cuantificada existencialmente. Nota. El símbolo  significa “existe al menos”, “algunos”. Entonces, la afirmación Existe x en A tal que P (x) se escribe, en forma simbólica, por  x  A / P (x) El símbolo  se llama cuantificador existencial. A las proposiciones que tienen la forma:  x  A / P (x), se les llama proposiciones existenciales y se pueden leer, también, como: “para al menos un x de A tal que P (x)”, “para algunos x en A tal que P (x)”, “P (x), para algún x en A”. Notas: 1) Cuando el dominio A de P (x) está sobreentendido, la proposición existencial se escribe:  x / P (x). 2) La proposición  x  A / P (x) es verdadera, si P (x) es verdadera para al menos una x en A. 3) La proposición  x  A / P (x) es falsa, si P (x) es falsa para toda x en A.

Ejemplo.

Consideremos el dominio A =

y P (x):

x 2  , la afirmación cuantificada x 1 5 2

existencialmente x

En efecto,

si x = 2,

P (2):

Ejemplo. Consideremos A =

/

x 2 es verdadera.  x 1 5 2

2 2 es verdadera.  2 1 5 2

1  1 . La proposición existencial x  1 1 x / 2  1 es falsa. x  1

y P (x):

2

Para verificar esta afirmación, debe demostrarse que

1  1 es falsa, para todo número real x. Una x  1 2

de las formas es argumentando lo siguiente:

1 1  1 es falsa, pues 2  1 es verdadera para todo número real x. x  1 x 1 2

En efecto, sea x un número real. Se sabe que x2  0, para cualquier x real. Entonces, x2  0 ⟹ 1  x2 + 1

53

Apuntes de Álgebra I

O sea,

⟹

x2  1 1 (pues, x2 + 1  0)  x2  1 x2  1

⟹

1 1 x 1 2

1  1 es verdadera, para todo número real x. x 1 2

Por tanto,

1  1 es falsa, para cualquier número real x. En consecuencia, x  1 2

x

Ejemplo. Sea A =

+

/

1  1 es una proposición existencial falsa. x  1 2

y P (n): si n es primo, entonces n + 1, n + 2, n + 3 y n + 4 son primos. La

proposición existencial, n

+

/ P (n): si n es primo, entonces n + 1 o n + 2 o n + 3 o n + 4 son primos

es verdadera. En efecto, podemos encontrar al menos un número entero primo n para lo cual la proposición condicional es verdadera. Por ejemplo, si n = 17:  17 

+

/ si 17 es primo, entonces 18 o 19 o 20 o 21 son primos, es verdadera

Las proposiciones existenciales son generalizaciones de las disyunciones, es decir, cuando el dominio A es finito se puede entender la cuantificación existencial como una forma abreviada de la disyunción. Para ello, sea la función proposicional

(A, P (x))

donde el dominio A es un conjunto finito cuyos elementos

son: a1, a2, … , an. Entonces,  x  A / P (x), es verdadera  por lo menos una de las P (a1), P (a2), … , P (an) es verdadera  P (a1)  P (a2)  …  P (an) es verdadera Por tanto,  x  A / P (x)  P (a1)  P (a2)  …  P (an) Ejemplo. Si el dominio de la variable x es el conjunto A = {0, 2, 4, 6}, entonces la proposición  x  A / P (x) es verdadera, si la proposición P (0)  P (2)  P (4)  P (6) es verdadera, para algún x de A. Ejemplo. Simbolizar las proposiciones siguientes y determinar su valor de verdad: a) Existe un número natural mayor que uno. b) Algunos números enteros son positivos. c) Existe un número real cuyo cuadrado es negativo. Solución. a) Para este caso: A =

, P (n): n  1. Entonces, en símbolos es: n

/n 1

Esta proposición es verdadera. Pues, para n = 2 satisface 2  1.

54

Apuntes de Álgebra I

b) Hacemos: A =

, P (n): n  0. Entonces, en símbolos es: n

/n 0

Esta proposición es verdadera. Pues, para n = 1 se cumple 1  0. c) Para este caso: A =

, P (x): x2  0. En símbolos tenemos: x

/ x2  0

Esta proposición es falsa. Pues, se sabe que para cualquier x real, x2  0. 1.1.13.3 El cuantificador existencial de unicidad Como un caso particular del cuantificador “existe” tenemos el cuantificador “existe un único” o “existe solo uno”, al que se le llama cuantificador existencial de unicidad y se representa por el símbolo  o 1. Entonces, la afirmación “existe un único x en A tal que P (x)” se escribe  x  A /P (x) Observación. La expresión  x  A /P (x) se lee también “existe un x y uno sólo en A tal que P (x). El símbolo  se llama cuantificador existencial de unicidad. Nota. El valor de verdad de la proposición  x  A /P (x), es verdadera si P (x) es verdadera para un único x en A. Es decir, si el dominio de verdad de P (x) es un conjunto unitario. Ejemplo. Si A =

+

y P (n): n es un entero par y primo, la proposición  n 

/ n es un entero par y primo

es verdadera. Pues, el único número entero par y primo es 2 (n = 2). Ejemplo. Simbolizar las proposiciones siguientes y determinar su valor de verdad. a) Existe un único número entero positivo tal que su cuadrado es uno. b) Existe solo un número entero tal que su cuadrado es 9. c) Existe un único número real tal que su cuadrado es menor que cero. Solución. a) Para este caso, tenemos: existe un único (), dominio (A =

+

) y P (n): n2 = 1. Luego,

en forma simbólica escribimos:  n 

+

/ n2 = 1

Esta proposición es verdadera, ya que para n = 1, P (1): 12 = 1 es verdadera. Para cualquier otro número entero positivo n  1, P (n) es falso. b) Tenemos: A =

y P (n): n2 = 9. En símbolos,  n 

/ n2 = 9

Esta proposición es falsa. Pues, n = 3 y n = -3 cumplen con n2 = 9. c) Sea A =

y P (x): x2  0. En símbolos tenemos:

55

Apuntes de Álgebra I

 x 

/ x2  0

Esta proposición es falsa. Pues, se sabe que para cualquier número real x, x2 es positivo o cero. Es decir, x2  0;  x 

.

1.1.13.4 Reglas de negación de cuantificadores Sea

(A,

P (x)) una función proposicional. Las proposiciones universales y existenciales son

generalizaciones de la conjunción y disyunción, respectivamente; como se afirmó anteriormente. Las dos leyes de De Morgan nos proporcionan las relaciones entre las negación, conjunción y disyunción. Entonces, tenemos: i) Negación del cuantificador universal Sea (A, P (x)) una función proposicional. La negación de la proposición  x  A, P (x) es equivalente a:  No es cierto que, para cada x  A, P (x).  Existe al menos un x  A tal que  P (x).  Hay al menos un x  A para el cual  P (x).  Es falso que, para toda x  A, P (x).  No todas las x de A satisfacen P (x).   x  A /  P (x). Entonces,

 [ x  A, P (x)]   x  A /  P (x)

ii) Negación del cuantificador existencial Sea (A, P (x)) una función proposicional. La negación de la proposición  x  A /P (x) es equivalente a:  No es cierto que, para alguna x  A, P (x).  Para toda x  A,  P (x).  Ni una x de A, cumple P (x).  Ninguna x de A, cumple P (x).   x  A,  P (x). Entonces, se puede ver que  [ x  A /P (x)]   x  A,  P (x) Estas reglas indican que para negar una proposición cuantificada se cambia el cuantificador y se niega el enunciado P (x). Las dos reglas anteriores implican las dos reglas siguientes: iii)

 [ x  A,  P (x)]   x  A /P (x)

56

Apuntes de Álgebra I

 [ x  A /  P (x)]   x  A, P (x)

iv)

Ejemplo. Usando las reglas de negación de cuantificadores negar las siguientes proposiciones: a)  n 

/ 2n = n

b)  n 

/n+25

c)  x 

/ 1  x2  4

Solución. a)  [ n 

/ 2n = n]   n 

,  (2n = n)

 n

, 2n  n

b)  [ n  / n + 2  5]   n   n c)  [ x 

/ 1  x2  4]   x 

/  (n + 2  5) /n+2  5 ,  (1  x2  4)

 x

,  (1  x2  x2  4)

 x

, (x2  1  x2  4)

Ejemplo. Demostrar que las proposiciones siguientes son verdaderas. a)  [ n  b)  [ x  c)  [ x 

, (n2 – 3 n – 10 = 0 ⟶ n = 5)]

1  1 )] x / (1 + 5 x + 3 x + 4 = 8 x + 1)]

, (x  1 ⟶

Solución. Bastará con probar que las proposiciones dentro de los corchetes son falsas. En efecto, a) n2 – 3 n – 10 = 0 ⟹ (n – 5) (n + 2) = 0 ⟹ n–5=0  n+2=0 ⟹ n = 5  n = -2

C. S. {-2, 5}

Entonces, tenemos que cuando n = 5 la forma condicional n2 – 3 n – 10 = 0 ⟶ n = 5 es verdadera. Pero cuando n = - 2, la forma condicional n2 – 3 n – 10 = 0 ⟶ n = 5 es falsa, pues el antecedente es verdadero y el consecuente es falso. Por tanto, la proposición n

, n2 – 3 n – 10 = 0 ⟶ n = 5, es falsa

En consecuencia, su negación  [ n 

, n2 – 3n – 10 = 0  n = 5]   n 

/  (n2 – 3 n – 10 = 0 ⟶ n = 5)

 n

/  ( (n2 – 3 n – 10 = 0)  n = 5)

 n

/ (n2 – 3 n – 10 = 0  n  5)

es verdadera. b)

x 1 0  , x0 x x 1 ⟹ 1–  0, x  0 x

x  1  x–1 0 ⟹

57

Apuntes de Álgebra I

1  -1, x  0 x 1 ⟹  1, x  0 x ⟹ -

Luego, el condicional x  1 ⟶

1 1 x

es verdadero, para cualquier x real diferente de cero. Pero cuando x = 0, el condicional x  1 ⟶

1 1  1 es falso ( no está definido). x 0

Por tanto, la proposición x

,x  1 ⟶

1  1 , es falsa. x

La negación,  [ x 

c)

,x1 ⟶

1  1]   x  x

/  (x  1 ⟶

 x

/  (x  1 

 x

/ (x  1 

1  1) x

1  1) x

1  1 ), es verdadera x

1 + 5x + 3x + 4 = 8x + 1 ⟹ 8x – 8x = - 4 ⟹ 0x=-4 Esta última igualdad es falsa para cualquier x  x

. Por tanto, la proposición

/ 1 + 5x + 3x + 4 = 8x + 1, es falsa.

La negación,  [ x 

/ 1 + 5x + 3x + 4 = 8x + 1]   x 

, 1 + 5x + 3x + 4  8x + 1

es verdadera. 1.1.13.5 Cuantificadores dobles Supongamos que se pide escribir simbólicamente la afirmación: “ La suma de cualesquiera dos números enteros pares es par ” Como se trata de dos números, se necesitan dos variables; como por ejemplo x e y. La afirmación se puede establecer como: Si x es par e y es par, entonces x + y es par Esta afirmación dice que la suma de cualesquiera dos números enteros pares es par, de modo que se necesitan dos cuantificadores universales. Así, simbólicamente tenemos: x

,y

, (x es par  y es par ⟶ (x + y) es par)

Es decir, para cada x y para cada y, si x es par e y es par, entonces x + y es par. Se dice, entonces, que cuando escribimos  x,  y se tienen cuantificadores dobles (o también: cuantificadores anidados o múltiples).

58

Apuntes de Álgebra I

En los ejemplos anteriores se han usado funciones proposicionales de una variable, pero también las hay de dos o más variables. Por ejemplo, sea 3 x + y2  8 una función proposicional con las variables x e y, a la cual simbolizamos por P (x, y) tal que P (x, y): 3 x + y2  8 Además, sean A y B (no necesariamente A  B) los conjuntos de variación de las variables x e y, respectivamente. Entonces, son proposiciones:   x  A,  y  B, P (x, y)   x  A,  y  B / P (x, y)   x  A /  y  B, P (x, y)   x  A /  y  B, P (x, y)   x  A /  y  B / P (x, y), etc. Nota. Cuando existen más de un cuantificador, en las proposiciones cuantificadas, la jerarquía de los cuantificadores son de izquierda a derecha; ya que los cuantificadores universal y existencial son operadores monádicos y, como tal, sólo operan hacia la derecha. Lo anterior, significa que el orden en que aparecen los cuantificadores indican el orden en que se están cuantificando. Por ejemplo, en la proposición  x  A,  y  A, P (x, y) primero se cuantifica la variable y, luego la variable x. Es decir,  x  A,  y  A, P (x, y) =  x  A, [ y  A, P (x, y)] Ejemplo. Escribir, en palabras, la proposición  m,  n / m  n. El dominio es el conjunto

.

Solución. Esta afirmación podemos expresarla como: Para toda m, existe n tal que m es menor que n Significa que si se toma cualquier entero m, hay un entero n mayor que m. Dicho de otra forma: no existe un entero que sea el más grande Ejemplo. Sea el conjunto A =

y P (x, y): x + y = 0. La proposición x

,y

/x+y =0

es verdadera. Pues, para todo número real x, existe al menos una y (y = - x) de manera que x + y = 0 es verdadera. Notas: 1. Cuando aparecen varios cuantificadores en un enunciado, es indiferente el orden en el que escriben siempre que los cuantificadores involucrados sean del mismo tipo. Por ejemplo, si P (x, y) es una propiedad relativa a los elementos x e y, entonces:

i )  x,  y, P (x, y), es lo mismo que escribir  y,  x, P (x, y); ii )  x,  y / P (x, y), es equivalente a  y,  x / P (x, y).

59

Apuntes de Álgebra I

2. Hay que tener cuidado cuando se ven involucrados cuantificadores de distinto tipo. Por ejemplo, el enunciado  x,  y /P (x, y) no es equivalente a la expresión  y /  x, P (x, y) En este caso, si A =

y P (x, y): x  y, la primera expresión se lee como que “para todo

número natural existe otro mayor”. Por tanto, x ,y

/ x  y , es verdadero

La segunda expresión significa que “existe un número natural que es mayor que todos los demás”. Por consiguiente, y

/  x  , x  y , es falso.

Por tanto, en general  x,  y / P (x, y) ≢  y /  x, P (x, y) 3. El cuantificador existencial y el conectivo de la disyunción se pueden intercambiar en la escritura de un enunciado, así como el cuantificador universal y el conectivo de la conjunción. O sea,

i ) ( x, P (x)) y ( y, Q(y)) es lo mismo que  x, y, (P (x)  Q (y)). Es decir, ( x, P (x))  ( y, Q (y))   x, y, (P (x)  Q (y))

ii ) ( x / P (x)) o ( y /Q (y)) es equivalente a  x, y / (P (x)  P (y)). O sea, ( x /P (x))  ( y /Q (y))   x, y /(P (x)  P (y)) 4. En general, no se pueden intercambiar cuantificadores con conectivos en la escritura de un enunciado. Así por ejemplo: a) La expresión  x, (P (x)  Q (x)) no es equivalente a ( x, P (x))  ( x, Q (x)). En efecto, si A = ℤ, P (x): ser par y Q (x): ser impar, respectivamente, entonces:   x  ℤ , (x es par  x es impar), significa que todo número entero x es un número par o un número impar (lo cual es verdadero).  ( x  ℤ , x es par)  ( x  ℤ , x es impar), quiere decir que todo número entero es par o que todo número entero es impar (lo cual es falso). Por tanto,  x, (P (x)  Q (x)) ≢ ( x, P (x))  ( x, Q (x)) b) La expresión  x / (P (x)  Q (x)) no es equivalente a ( x / P (x))  ( x / Q (x)). Pues, si A = ℤ, P (x): x es par y Q (x): x es impar, respectivamente, entonces:   x  ℤ / (x es par  x es impar), es falso, pues el entero 8 es par pero no impar.  ( x  ℤ / x es par)  ( x  ℤ / x es impar), es verdadero. Pues, por ejemplo existe en ℤ “x = 0 que es par” y existe en ℤ “x = 3 que es impar. Por tanto,

60

Apuntes de Álgebra I

 x /(P (x)  Q (y)) ≢ ( x /P (x))  ( x / Q (x))

EJERCICIOS PROPUESTOS 1. Determinar el valor de verdad de las proposiciones siguientes, considerando como dominio el conjunto de los números reales

.

a)  x 

, x3 = x

b)  x 

/ 2x = x

c)  x 

/ x2 + 3x – 2 = 0

d)  x 

/ x2 – 2x + 5 = 0

e)  x 

, 2x + 3x = 5x

f)  x 

/ 2x2 + x = 15

g)  x 

, x –3  x

h)  x 

, x+3  6

i)  x 

/x+3  6

j)  x 

, x2 – 10  6

2. Dado el conjunto M = {1, 2, 3, 4, 5}, indicar el valor de verdad de las proposiciones siguientes: a)  x  M, x + 3  5

b)  x  M / x + 3  5

c)  x  M, x + 3  8

d)  x  M / x0 = x

e)  x  M / x es par y primo

f)  x  M, x divide a 20

g)  x  M, x es factor de 60

h)  x  M / x es divisor de 15

3. Negar las proposiciones siguientes e indicar su valor de verdad: x2  x x

a)  x 

/ (-1) x = 0

b)  x 

c)  n 

/ 2n  0

d)  n 

,

f)  n 

/

e)  x  , x + 3  5

,

n es racional 2 1 1 n!

4. En cada proposición establezca su valor de verdad, sabiendo que: A = {1, 2, 3, 4, 5, 6} y  P (x): x es par  Q (x): x es divisible por 3  R (x): x  6  S (x): x es múltiplo de 6 a)  x  A, [P (x)  Q (x)] b)  x  A / [Q (x) ⟶ R (x)] c)  x  A / [ P (x)  Q (x)  R (x)] d)  x  A, [P (x)  Q (x) ⟷ S (x)] 5. Determine el valor de verdad de las proposiciones siguientes, justificando sus respuestas. a)  x 

, x2  x

b)  x 

c)  x 

/ x2  x

d)  x 

, (x  1  x2  x) / (x  1  x2  x)

61

Apuntes de Álgebra I

 x 1 , x 1  2   x  1 3 

e)  x 

f)  x 

 x 1 / x 1  2   x  1 3 

6. Indicar el valor de verdad y negar cada una de las proposiciones siguientes. (Aquí a)  x 

/y

c)  x 

,y

, (x + y)2 = x2 + 2xy + y2

d)  y 

,x ,y

f)  x 



*

=

– {0}).

b)  y 

,x

/xy = y

/xy  y

e)  x 

,y

/xy = y

/xy = 1

g)  y 

/x

, xy = y



, xy = 1

1.2 MÉTODOS DE DEMOSTRACIÓN 1.2.1 Introducción En esta parte, estudiaremos la estructura de las demostraciones así como las estrategias para su construcción. Aunque no consideremos todos los casos posibles, describiremos algunas de las técnicas de demostración más comunes, daremos ejemplos de su uso, las relaciones con las leyes de la lógica proposicional y las reglas de inferencia anteriormente descritas. Un sistema matemático consiste en axiomas, definiciones y términos no definidos. Se supone que los axiomas son verdaderos. Las definiciones se usan para crear nuevos conceptos en términos de los existentes. Algunos términos no están definidos de forma explícita por los axiomas. Un teorema es una proposición que se ha probado que es verdadera. Algunos tipos especiales de teoremas reciben el nombre de lemas y corolarios. Un lema es un teorema que no suele ser muy interesante por sí mismo, pero que resulta útil para probar otro teorema. Un corolario es un teorema que se deriva de otro teorema. Hemos visto que una demostración era un razonamiento que establece la veracidad de un teorema, es decir demostrar un teorema equivale a probar que la forma condicional H ⟶ T es una tautología o lo que es igual a probar que H ⟹ T. Además, un argumento que establece la veracidad de un teorema se llama demostración o prueba y la lógica es una herramienta para el análisis de las demostraciones.

Entonces, serán numerosos los casos en los cuales debemos demostrar o probar enunciados (proposiciones) de la forma H ⟶ T Algunas de las técnicas más importantes son: la demostración directa, la demostración indirecta y la demostración por inducción. Cuando veamos las características de cada uno de estos métodos, veremos con cierta claridad cuándo es uno de ellos preferible a los otros Observaciones: 1. La demostración de un razonamiento válido, como se ha visto anteriormente, se reduce a probar la implicación H1  H2  …  Hn ⟹ T

62

Apuntes de Álgebra I

donde H1, H2, … , Hn son las premisas y T es la conclusión. 2. En la matemática, las proposiciones que se demuestran se llaman teoremas o corolarios; en los cuales las premisas constituyen la hipótesis y la conclusión la tesis. Es decir, H  H 2  ...  H n  T  1  Tesis

Hipótesis

3. En general, se trata de demostrar la implicación: H ⟹ T, donde H es la hipótesis y T la tesis. 4. Para demostrar la validez del teorema H ⟹ T, consideramos necesario que el lector deba:  Manejar los fundamentos básicos del cálculo proposicional.  Entender las relaciones más importantes de los elementos de H y T y, procurar, que se hagan presentes en tu mente las ideas relacionadas entre ellos, provenientes de tu estudio previo. Se debe tener presente que: “la Matemática es el lenguaje de los matemáticos, y una demostración es un método para comunicar una verdad matemática a otra persona que también “habla” el mismo idioma”. Antes de estudiar algunas de las técnicas utilizadas para probar implicaciones, definiremos algunos conceptos básicos que se estudian en el conjunto de los números enteros. 1.2.2 Conceptos básicos definidos en el conjunto de los números enteros Suponemos que el lector está familiarizado con los conjuntos = {1, 2, 3, . . . } y

= {. . . , - 3, - 2, - 1, 0, 1, 2 , 3, . . . }

de los números naturales (o enteros positivos) y de los números enteros, respectivamente. Una de las propiedades más importante de los números naturales es ser un conjunto bien ordenado, como lo establece las siguientes definiciones. Definición 1.- Sea A un subconjunto de

. Se dice que A posee primer elemento si existe un elemento

n  A tal que n  x, para todo x  A. Definición 2.- Un subconjunto B de

se dice bien ordenado si todo subconjunto no vacío de B posee

primer elemento. Entonces, de las definiciones anteriores, todo subconjunto no vacío de números naturales tiene primer elemento (o un menor elemento). Es decir, para todo subconjunto H   de Se dice entonces, por el principio de buen orden, que

, H tiene primer elemento.

es un conjunto Bien Ordenado. Intuitivamente,

este sencillo principio nos dice que siempre es posible encontrar, en algún subconjunto de

el más

pequeño número natural tal que . . . , donde la línea de puntos se puede llenar por cualquier propiedad (siempre que exista al menos un número natural que verifique dicha propiedad). Por otro lado,

no

verifica el Principio de Buen Orden ya que no tiene primer elemento. También, los enteros menores que 10, o los enteros negativos, etc. son subconjuntos no vacíos de

que no tiene primer elemento.

63

Apuntes de Álgebra I

Definición 3.- Intuitivamente, se define el conjunto de números enteros como  {0}  -

= donde - = {- n / n  } =

ˉ = {x 

/ x  0}. También, =

+

 {0} 

= {x 

/ x  0} =

+

. Luego,

ˉ

Por otra parte, se sabe que el conjunto de números enteros es cerrado para la adición, multiplicación y la diferencia, y que los únicos números enteros que tienen inverso multiplicativo son los números 1 y -1. Ejemplo. Sea igual”, entonces

+

el conjunto de los números enteros positivos. Si consideramos la relación “menor o +

está ordenado, y, además, como todo subconjunto no vacío de +

mínimo o primer elemento se dice que

+

tiene elemento

está bien ordenado por la relación “menor o igual”.

1.2.2.1 Divisibilidad Aunque el conjunto de los números enteros

no es cerrado para la división, existen muchos casos en los

que un número entero divide a otro. Por ejemplo, 3 divide a 15 y 4 divide a 16. La división es exacta y no existe resto. Así pues, el que 3 divida a 15 implica la existencia de un cociente 5 tal que 15 = 3 ⋅ 5. Si a y b son dos números reales, y a  0, podemos escribir b = a ⋅ (b ⋅ a-1), siendo b ⋅ a-1 un número real. Es decir, si a y b 

, y a  0, entonces existe c 

tal que b = a ⋅ c.

Si nos restringimos al conjunto de los números enteros, entonces ya no podemos asegurar que para cualquier par a , b 

, se cumple que b ⋅ a-1 sea un número entero. En los casos que sea cierto, diremos

que a divide a b o que a es un divisor de b. Definición.- Sean a y b dos números enteros tales que a  0. Se dice que a divide a b, y se denota a|b, si existe c 

tal que b = a ⋅ c. Es decir, a|b   c 

/b=a⋅c

Expresiones equivalentes a “a divide a b” son: “a es un divisor de b” o “b es múltiplo de a” o “b es divisible por a” Equivalentemente, si negamos ambos miembros de la equivalencia anterior, en virtud de la equivalencia lógica entre una proposición y su contrarrecíproco, tendremos a∤b   c  Por ejemplo, 5|15, pues  3 

, b  a⋅c

tal que 15 = 5 ⋅ 3. Del mismo modo se tiene que 3|15, pues  5 

tal que 15 = 3 ⋅ 5. En este caso se dice que 15 es divisible por 5 y por 3, respectivamente. También, 6∤15, pues no existe ningún entero c tal que 15 = 6 ⋅ c. Por otro lado, 2|4, 2|-2, 2|10, 2|16, etc. En este caso, todo número par es divisible por 2.

64

Apuntes de Álgebra I

Como se ha expresado líneas arriba, dados dos números enteros a y b , no siempre ocurre que a|b. Por ejemplo, 4 no divide a 23; esto es, si queremos repartir equitativamente 23 objetos entre 4 personas entonces podemos darle 5 objetos a cada uno y sobrarán 3. Luego, podemos escribir 23 = 4  5 + 3 Aquí el número 3 se llama resto de la división de 23 por 4. La expresión 23 = 4  5 + 3, expresa un hecho general. Dados los números enteros a y b , a  0, existe un único número entero no negativo r con la propiedad que 0  r  a y que a|(b – r) En este caso, b = 23, a = 4, r = 3. Entonces, 0  3  4 y 4|(23 – 3) Nota. La definición de divisibilidad nos permite hablar de división en

sin ir a

.

Teorema. (Existencia y Unicidad del Cociente y el Resto) Sean a , b 

, b  0, entonces existen dos enteros q y r, únicos, tales que a = b ⋅ q + r, con 0  r  b

a los números a, b, c y r se les llama, respectivamente, dividendo, divisor, cociente y residuo. Además, q y r son únicos con esta propiedad, es decir, si a=b⋅q + r

y

a = b ⋅ q' + r', con 0  r'  b

entonces q = q' y r = r'. Dados a, b, q y r, como en el teorema anterior, los números q y r son llamados, respectivamente, cociente y resto de la división de a por b . Notemos que cuando b divide a a , se tiene r = 0. Nota. En el estudio de la estructura algebraica de los números enteros, es importante anotar que la adición y la multiplicación de números enteros son operaciones asociativas y conmutativas, que el par (

, ) es un grupo abeliano y que cumple la propiedad distributiva del producto respecto de la suma, por

lo que (

, , ⋅) es un anillo conmutativo con elemento unidad (el 1) y sin divisores de cero.

Algunas propiedades básicas de divisibilidad Sean a, b y c tres números enteros, siendo a y b distintos de cero. Se verifica: i) 1 divide a “a” y “a” divide a 0. ii) Si “a” divide a “b” y “b” divide a “a”, entonces a =  b. iii) Si “a” divide a “b” y “b” divide a “c”, entonces “a” divide a “c”. iv) Si “a” divide a “b” y “a” divide a “c”, entonces “a” divide a pb + qc, cualesquiera que sean p y q enteros. (A la expresión pb + qc se le llama combinación lineal de b y c con coeficientes enteros). Demostración. Demostraremos (i) y (ii). i) 1|a y a|0

65

Apuntes de Álgebra I

En efecto, a = 1 ⋅ a, con a 

, luego 1|a

a = a ⋅ 0, con 0 

, luego a|0

a|b  b|a  a =  b,  a, b 

ii)

– {0}

En efecto, a|b  b|a   p 

/ b = ap   q 

/ a = bq

 b = bqp  b – bqp = 0  b(1 – qp) = 0 y al ser b  0 y no tener

divisores de cero, se tiene que

1 – qp = 0  1 – pq = 0  pq = 1  p = q = 1  p = q = -1 Por tanto, (b = ap  a = bq  p = q = 1  a = b)  (b = ap  a = bq  p = q = -1  a = -b)  a =  b Otras propiedades importantes de divisibilidad Sean los números enteros a , b y c . Entonces, 1. Para cada a 

, a  0, a a.

2. Si a (b + c) y a b, entonces a c. 3. Si a b y a c, entonces a (b + c) y a (b – c). Demostración de (2). Probaremos que: a (b + c) y a b  a c. En efecto, a (b + c)  a b  ( m 

/ b + c = a ⋅ m)  ( n 

/ b = a ⋅ n)

 c =a ⋅ m – b  b =a ⋅ n  c = a ⋅ m – a ⋅ n = a (m – n) = a ⋅ k, con m – n = k   k

/c =a ⋅ k

 ac 1.2.2.2 Números pares e impares Definición.- Un entero n es par si existe un entero k tal que n = 2k. O sea n

es par   k 

/ n = 2k

Recordemos que un número entero es par si es divisible por 2. Entonces, “Para cada entero n, n es par si, y sólo si n es divisible por 2” Por tanto, “Para cada entero n, n es par si, y sólo si puede encontrarse un entero k tal que n = 2k” Por ejemplo, si n = 18 y 18 = 2k, entonces k = 9 que es entero, luego n = 2 ⋅ 9, es decir, n es par. Definición.- Un entero m es impar si existe un entero k tal que m = 2k + 1. Es decir,

66

Apuntes de Álgebra I

m

es impar   k 

/ m = 2k + 1

Por tanto, “Para cada entero m, m es impar si y sólo si puede encontrarse un entero k tal que m = 2k + 1” Ejemplo. El entero n = -20 es par porque existe un entero k (k = -10) tal que n = 2k; es decir, -20 = 2 ⋅ (-10). Ejemplo. El entero n = 23 es impar porque existe un entero k (k = 11) tal que m = 2k + 1; es decir, 23 = 2 ⋅ 11 + 1. 1.2.2.3 Máximo común divisor Siguiendo con la operación de división veremos, en forma breve, los divisores comunes de un par de números enteros. i) Divisores comunes Dados dos números enteros a y b, se dice que el entero d  0 es un divisor común de ambos, si divide a “a” y a “b”, es decir, d  0, es divisor de a y b  d|a y d|b Observación. Es lo mismo decir que a y b son divisibles por d o que a y b son múltiplos de d. Por ejemplo,  3 15 y 3|9, por tanto 3 es un divisor común de 15 y 9, respectivamente.  -5|10 y -5|25, luego -5 es un divisor común de 10 y 25. ii) Máximo común divisor Sean a y b dos números enteros. Se dice que d es el máximo común divisor de a y b, si d es el máximo del conjunto de los divisores positivos comunes a ambos, ordenado por la relación de divisibilidad. Se denota con m.c.d.(a, b). Nota. Teniendo en cuenta la definición de máximo de un conjunto ordenado, si se llama D al conjunto de todos los divisores positivos comunes a a y a b, se tiene d = m.c.d.(a, b)  (1. d|a  d|b)  (2. d = max (D))  (1. d|a  d|b)  (2.  c, c  D  c|d)  (1. d|a  d|b)  (2. c|a  c|b  c|d) Por tanto, d es el máximo común divisor de los enteros a y b si y sólo si se cumple 1. d|a  d|b. 2. si c  D, c|a  c b  c|d. Ejemplo. Calcular el máximo común divisor de 24 y 36. Solución. Por definición, los divisores positivos de 24 y 36 son:

67

Apuntes de Álgebra I

D24 = {1, 2, 3, 4, 6, 8, 12, 24} y D36 = {1, 2, 3, 4, 6, 9, 12, 18, 36} Por tanto, el conjunto de los divisores comunes será D = D24  D36 = {1, 2, 3, 4, 6, 12} Entonces, como max (D) = 12 se tiene que d = m.c.d. (24, 36) = 12. El siguiente diagrama de Hasse representa la ordenación del conjunto D = {1, 2, 3, 4, 6, 12} por la relación de divisibilidad, 12

4

6

2 2

3

2

1

y como puede observarse claramente el máximo es 12, por lo tanto d = m.c.d.(24, 36) = max (D) = 12. Propiedades Sean a y b dos números enteros distintos de cero. Se cumple: i)

m,c,d,(a, 0) = |a|.

ii) m.c.d.(a, b) = m.c.d.(|a|, |b|). iii) Si m.c.d.(a, b) = d, entonces m.c.d.(

𝑎 𝑏

, ) = 1.

𝑑 𝑑

iv) m.c.d.(ka, kb) = k m.c.d.(a, b),  k 

+

.

Demostración. Probaremos la parte ii): m.c.d.(a, b) = m.c.d.(|a|, |b|). En efecto, sea d un divisor de a y de b. Como a y b son distintos de cero, pueden ocurrir cuatro casos: 1. a  0 y b  0. Entonces, d a  d b  d -a  d b  d -a  d b  d a  d b 2. a  0 y b  0. Entonces, d a  d b  d a  d -b  d a  d -b  d a  d b 3. a  0 y b  0. Entonces, d a  d b  d -a  d -b  d -a  d -b  d a  d b

68

Apuntes de Álgebra I

4. a  0 y b  0. Entonces, da  db  d a  d b Luego, en cualquier caso el conjunto de los divisores comunes a “a” y a “b” coincide con el de los divisores comunes a a y a b , por tanto el máximo común divisor será el mismo, es decir, m.c.d.(a, b) = m.c.d.(|a|, |b|) Observaciones: 1. Si a y b son enteros positivos, se cumplen las siguientes igualdades: m.c.d.(-a, b) = m.c.d.(a, -b) = m.c.d.(-a, -b) = m.c.d.(a, b) Por ejemplo, m.c.d.(-6, 9) = 3 = m.c.d.(6, 9). 2. Dados dos números enteros a y b distintos de cero, existe un único d, que es el máximo común divisor de ambos. 3. Sean a1, a2, . . . , an números enteros. Llamaremos máximo común divisor de a1, a2, . . . , an al divisor común d  0 tal que cualquier otro divisor común de a1, a2, . . . , an divide también a d. Se denotará mediante m.c.d.(a1, a2, . . . , an). Corolarios: Corolario 1 Si d es el máximo común divisor de a y b, entonces d es el menor entero positivo que puede escribirse como combinación lineal de a y b con coeficientes enteros. Es decir, d = ma + nb 

, para ciertos m, n 

+

Por ejemplo, se sabe que d = m.c.d.(27, 6) = 3. Entonces, 3 puede escribirse como combinación de 27 y 6 de la siguiente forma: 3 = 1 ⋅ 27 + (-4) ⋅ 6 Nota. Al corolario 1 se le conoce como Lema de Bezout. Corolario 2. Si a y b son dos enteros distintos de cero, entonces m.c.d.(a, b) = 1 si y sólo si existen dos números enteros p y q tales que pa + qb = 1. Es decir, m.c.d.(a, b) = 1   p, q 

/ pa + qb = 1

Ejemplo. Demostrar que si m.c.d.(a, b) = 1 y m.c.d.(a, c) = 1, entonces m.c.d.(a, bc) = 1. Demostración. Aplicando el corolario 2, tendremos m.c.d.(a, b) = 1  m.c.d.(a, c) = 1   p, q 

/ pa + qb = 1   r, s 

/ ra + sc = 1

 (pa + qb)( ra + sc) = 1  para + pasc + qbra + qbsc = 1  (apr + psc + bqr)a + (qs)bc = 1

69

Apuntes de Álgebra I

 ma + n bc = 1, con m = apr + psc + bqr    m, n 

y n = qs 

/ ma + n bc = 1

 m.c.d.(a, bc) = 1 Ejemplo. Probar que, si m.c.d.(a, b) = d, entonces m.c.d.(

𝑎 𝑏

, ) = 1.

𝑑 𝑑

Solución. m.c.d.(a, b) = d   p, q 

/ pa + qb = d 𝑝𝑎 + 𝑞𝑏

  p, q 

/

  p, q 

/𝑝

 m.c.d. (

𝑑 𝑎 𝑑

+ 𝑞

(Corolario 1)

=1 𝑏 𝑑

= 1

𝑎 𝑏

, )=1

𝑑 𝑑

(Corolario 2)

1.2.2.4 Números primos y números compuestos en Observemos que: si a es cualquier número entero mayor que 1, entonces a = a ⋅ 1, con 1 

; es decir, a es un divisor de a,

a = 1 ⋅ a, con 1 

; es decir, 1 es un divisor de a.

por tanto, todo número entero a  1 tiene, al menos, dos divisores: el 1 y el propio a. i) Números primos Definición.- Un número entero positivo p , distinto de 1 (p  1), se dice que es primo si los únicos divisores positivos que tiene son 1 y p . Por ejemplo, 2, 5, 7, y 13 son números primos ya que los cuatro números tienen sólo dos divisores positivos. En efecto, D2 = {1, 2}, D13 = {1, 13}, etc. Nota. De la definición de número primo se sigue que p es primo si y sólo si no es posible escribir p = ab con a, b 

y 1  a, b  p.

Nota. Algunos autores definen los números primos del modo siguiente: Se dice que un número entero p es primo, si sus únicos divisores son  p,  p, 1 y 1 . Números primos entre sí Definición.- Sean a y b dos números enteros. Se dice que a y b son primos entre sí o primos relativos, cuando el máximo común divisor de ambos es 1. Entonces, dos números enteros son primos entre sí cuando el mayor divisor común a ambos es 1. Por tanto, a, b 

se dicen primos entre sí si y sólo si m.c.d.(a, b) = 1

70

Apuntes de Álgebra I

Por ejemplo, los números 4 y 9 son primos entre sí, pues m.c.d.(4, 9) = 1. En efecto, D4 = {-4, -2, -1, 1, 2, 4}, D9 = {-9, -3, -1, 1, 3, 9}, D = D4  D9 = {1} y max (D) = 1 En general, si se tienen n números enteros: a1, a2, . . . , an, éstos serán primos entre sí, cuando m.c.d.( a1, a2, . . . , an) = 1 Aplicando el lema de Bezout, si a y b son primos entre sí, entonces am + bn = 1, para algunos m, n  Ejemplo. Probar que cualquiera que sea n 

, los números 3n + 11 y 2n + 7 son primos entre sí.

Solución. Se tiene lo siguiente: 2(3n + 11) + (-3)( 2n + 7) = 6n + 22 – 6n – 21 = 1 entonces, por el corolario 2, se sigue que m.c.d.( 3n + 11 y 2n + 7) = 1 Por tanto, 3n + 11 y 2n + 7 son primos entre sí. Veamos otra forma de probar lo mismo. Sea d = m.c.d.( 3n + 11 y 2n + 7), entonces probaremos que d = 1. En efecto, d = m.c.d.( 3n + 11 y 2n + 7)  d 3n + 11  d 2n + 7  d 2(3n + 11)  d (-3)( 2n + 7)  d 6n + 22 + (-6n – 21)  d1  d = 1, pues d  0 Por tanto, ambos números son primos entre sí. Ejemplo. En

+

definimos la siguiente relación: a ℛ b  a y b son primos entre sí

Estudiar las propiedades de esta relación. Solución. 1. Reflexiva. Se debe cumplir,  a 

, a ℛ a  m.c.d.(a, a) = 1.

+

Veamos: dado cualquier a 

+

, se tiene que m.c.d.(a, a) = a.

Por tanto, ℛ no es reflexiva. 2. Simetría. Se debe cumplir que para a, b 

, a ℛ b  b ℜ a.

+

En efecto, a ℛ b  a y b son primos entre sí  m.c.d.(a, b) = 1  m,c,d,(b, a) = 1  b y a son primos entre sí

71

Apuntes de Álgebra I

 bℛa Luego, ℛ es simétrica. 3. Transitiva. Se debe cumplir que para a, b, c 

, a ℛ b  b ℛ c  a ℛ c.

+

Si a y b son primos entre sí y b y c también lo son, a y c no tienen porque serlo. En efecto, +

sean 5, 12 y 25 elementos de

, entonces:

5 y 12 son primos entre sí. 12 y 25 son primos entre sí. Pero, m.c.d.(5, 25) = 5. Por tanto 5 y 25 no son primos entre sí. Luego, ℛ no tiene la propiedad transitiva. Ejemplo. Verificar si los números 2p y 4p + 3 son primos entre sí, cualquiera que sea p entero. Solución. Sea d = m.c.d.(2p, 4p + 3). Entonces, d = m.c.d.(2p, 4p + 3)  d 2p  d 4p + 3  d (-2)2p  d 4p + 3  d -4p + 4p + 3  d3  d = 1  d = 3, pues d  0. Por tanto, no siempre los números enteros 2p y 4p + 3, son primos entre sí. ii) Números compuestos Definición.- A un número entero que no es primo, se le llama compuesto. Por ejemplo, 12 no es un número primo; pues tiene más de dos divisores positivos. En efecto, D12 = {1, 2, 3, 4, 6, 12}. por tanto, 12 es un número compuesto. Al observar D12, notamos que 12 tiene a los números primos 2 y 3, como divisores. Proposición Todo número compuesto posee al menos, un divisor primo. Teorema. Un entero positivo n  1 es compuesto si y sólo si n tiene un divisor d que satisface 2 d 

n

Por ejemplo, 451 es un número compuesto ya que 11 divide a 451 (451 = 11 x 41) y 2  11 

451

Por ejemplo el número 37 no es compuesto. Pues suponiendo que lo sea, se tiene: 2 d 

37 , d = 2, 3, 4, 5, 6

72

Apuntes de Álgebra I

observamos que ningún entero positivo d divide a 37. Por tanto 37 es primo. Euclides demostró en el libro IX de los elementos que existían infinitos números primos. La argumentación que utilizó ha sido considerada desde siempre como un modelo de elegancia matemática. Teorema. Existen infinitos números primos. Los números primos y su distribución dentro de los números enteros, han sido estudiados desde la antigüedad. Ellos han ejercido una atracción fascinante sobre los matemáticos, debido a la forma tan irregular como aparecen en la sucesión de los enteros. Muchos matemáticos han tratado en vano de hallar una fórmula que genere exclusivamente números primos. Así, por ejemplo, Pierre Fermat conjeturó que todo número de la forma 𝑛

s(n) = 22 + 1 era primo. Esto lo comprobó para n  1, 2, 3 y 4 . Sin embargo en 1732 Leonhard Euler demostró que

s (5) no era primo. Teorema Si un número entero mayor que 1 no tiene divisores primos menores o iguales que su raíz, entonces es primo. Por ejemplo, supongamos que queremos saber si el 9 es primo. Entonces, como √9 = 3, los números primos menores o iguales que 3 son 2 y el propio 3. 2 no es divisor de 9, pero 3 si lo es, luego 9 no es primo. Ejemplo. Verificar si el número 811 es primo utilizando la criba de Eratóstenes. Solución. √811 = 28.5 y los números primos menores o iguales a 28.5 son 2, 3, 5, 7, 11, 13, 17, 19, 23. Como ninguno de estos números divide a 811, concluimos que dicho número es primo. 1.2.3 El método de demostración directa El tipo más natural de demostración es la demostración directa. Este método consiste en asumir que la hipótesis H es verdadera y por medio de reglas de inferencia, leyes de la lógica, axiomas, definiciones o teoremas ya probados, deducir que la tesis (conclusión) T es verdadera. Tiene la forma H ⟹ T Es decir, si H representa a la hipótesis y T a tesis o conclusión, se demuestra que la proposición condicional “si H, entonces T” es verdadera. Cuando se quiere probar que la proposición “Si H, entonces T” es verdadera, lo primero que se hace es reconocer quién es la proposición H y quién es la proposición T. Por lo general, todo lo que está entre las

73

Apuntes de Álgebra I

palabras “si” y “entonces” constituye la proposición H; y todo lo que está después de “entonces”, la proposición T. Por tanto, forma de reconocer H ⟹ T: todo lo que se supone que es cierto, o sea , la hipótesis, es H; y todo lo que se tiene que probar que es cierto, o sea la tesis, es T. Observación. A partir de los teoremas, definiciones o axiomas, entre otros, se tienen las siguientes implicaciones lógicas: 1) H ⟹ T1 2) (H  T1) ⟹ T2 . . . n) (H  T1  T2  . . .  Tn-1) ⟹ Tn n+1) (H  T1  T2  . . .  Tn-1  Tn) ⟹ T Al asumir que H es verdadero, aplicando las reglas de inferencia (Modus Ponendo Ponens y adjunción), se tuene que T es verdadero. En efecto, si H es verdadero,

(∗)

por Modus Ponendo Ponens a 1) y (∗) se tiene que T1 es verdadero. O sea (H ⟶ T1)  H ⟹ T1 Por adjunción se tiene que H  T1 es verdadero, (∗∗) y nuevamente por Modus Ponendo Ponens a 2) y (∗∗) se tiene que T2 es verdadero. Es decir, [(H  T1) ⟶ T2]  (H  T1) ⟹ T2 El proceso de deducción continúa hasta llegar a que T es verdadero. Ejemplo. Demostrar que el cuadrado de un número entero par también es par. Demostración. El teorema a demostrar en forma de condicional, será Para cualquier entero n, si n es par, entonces n2 es par Aquí: Hipótesis H: n es par. Tesis T: n2 es par En efecto, sea n un entero cualquiera. Entonces, n es par   k 

/ n = 2k

(Def. de número par)

 n2 = (2k)2 = 4k2

(Elevando al cuadrado)

 n2 = 2(2k2)

(Descomp. de factores)

 n2 = 2m, para m = 2k2   m  n2 es par

/ n2 = 2m

(Tomando m = 2k2) (Def. de número par)

74

Apuntes de Álgebra I

Aunque el ejemplo anterior es bastante sencillo, el desarrollo lógico de la demostración es idéntico al de otros teoremas de contenidos más complicados. Observemos, una vez más, el camino seguido a través de implicaciones. Ejemplo. Demostrar que para p, q 

, tales que

si p es un entero par y q un entero impar, entonces p ⋅ q es un entero impar. En este caso: Hipótesis H: p es un entero par y q un entero impar. Tesis T: p ⋅ q es un entero impar. Demostración. Sean p = 2 m, con m 

y q = 2n + 1, con n 

. Entonces,

p = 2 m  q = 2 n + 1  p ⋅ q = 2 m(2 n + 1)  p ⋅ q = 4 mn + 2m  p ⋅ q = 2 (2 mn + m)  p ⋅ q = 2 k, con k = 2 mn + m   k

/p⋅q=2k

 p ⋅ q es entero par Ejemplo. Demostrar que: Si A, B y C son subconjuntos de un conjunto referencial 𝔼, entonces (A – B)  (B – A) = (A  B) – (A  B) En este caso: Hipótesis H: A, B y C son subconjuntos de un conjunto referencial 𝔼. Tesis T : (A – B)  (B – A) = (A  B) – (A  B). Demostración. (A – B)  (B – A) = (A  Bc)  (B  Ac) = [(A  Bc)  B]  [(A  Bc)  Ac] = [(A  B)  (Bc  B)]  [(A  Ac)  (Bc  Ac)] = [(A  B)  𝔼]  [𝔼  (Bc  Ac)] = (A  B)  (Bc  Ac) = (A  B)  (B  A)c = (A  B) – (B  A) Por tanto, (A – B)  (B – A) = (A  B) – (A  B). Ejemplo. Sea n un número entero. Demostrar, en forma directa, el siguiente teorema: Si n es impar, entonces n 2 es impar Demostración. Otra forma de demostrar esta propiedad es usando el siguiente esquema: Sea n un entero cualquiera, entonces 1. n es impar

(Hipótesis)

75

Apuntes de Álgebra I

2. n = 2p + 1, para algún entero p

(Definición de número impar)

3. n 2 = (2p + 1)2

(de 2, elevando al cuadrado)

4. n 2 = 4p2 + 4p + 1

(de 3, potencia de un binomio)

5. n 2 = 2(2p2 + 2p) + 1

(de 4, por descomposición de factores)

6. n 2 = 2q + 1

(de 5, tomando 2p2 + 2p = q 

7. n 2 es impar

(de 6, definición de número impar)

)

O como en los casos anteriores, n es impar   p 

/ n = 2p + 1

(Definición de número impar)

 n2 = (2p + 1)2

(Elevando al cuadrado)

 n2 = 4p2 + 4p + 1

(Resolviendo la potencia)

 n2 = 2(2p2 + 2p) + 1

(Por factorización)

 n2 = 2q + 1, con q = 2p2 + 2p 

(Tomando q = 2p2 + 2p)

 q

/ n2 = 2q + 1

 n2 es impar

(Definición de número impar)

Observaciones: 1. No es necesario escribir todos estos pasos en una demostración, suelen aparecer versiones mucho más abreviadas. 2. Sea un teorema H ⟹ T. Para demostrar la validez de H ⟹ T, se parte de H y seguidamente de un número finito de conclusiones previas T1, T2, … , Tn se deduce la conclusión T. Es decir, (H ⟹ T1 ⟹ T2 ⟹ T3 ⟹ . . . ⟹ Tn) ⟹ T Ejemplo. Demostrar que el producto de dos números enteros impares, es un número impar Demostración. Este enunciado lo podemos escribir por, Si p y q son números enteros impares, entonces p ⋅ q es un número entero impar En efecto, sean p y q dos números enteros impares cualesquiera. Entonces, p y q números enteros impares   m 

/ p = 2m + 1   n 

/ q = 2n + 1

 p ⋅ q = (2m + 1)(2n + 1)  p ⋅ q = 4mn + 2m + 2n + 1  p ⋅ q = 2(2mn + m + n) + 1  p ⋅ q = 2k + 1, con k = 2mn + m + n   k

/ p ⋅ q = 2k + 1

 p ⋅ q es impar Por tanto, p y q números enteros impares  p ⋅ q es un número impar. Ejemplo. Demostrar que para cualquier n 

,

si n es un entero par, entonces 5 n + 3 es un entero impar. Demostración.

76

Apuntes de Álgebra I

n es un entero par  n = 2 p. para un cierto p   5 n = 10 p, con p   5 n + 3 = 10 p + 3  5 n + 3 = 10 p + 2 + 1  5 n + 3 = 2 (5 p + 1) + 1  5 n + 3 = 2 k + 1, con k = 5 p + 1   k

/5n+3=2k+1

 5 n + 3 es un entero impar Ejemplo. Demostrar que la suma de enteros impares es par. Es decir, si m y n son enteros impares, entonces m  n es entero par. O también, m y n son enteros impares  m  n es entero par

Demostración. 1. m y n son enteros impares

(Hipótesis)

2. m = 2p + 1 y n = 2q + 1, para enteros p y q

(definición de número impar)

3. m  n = 2p + 1 + 2q + 1

(de 2, por suma de m y n)

4. m  n = 2p + 2q + 2

(de 3, por suma de enteros)

5. m  n = 2 (p + q + 1)

(de 4, por distributividad)

6. m  n = 2 r

(de 5, haciendo (p + q + 1) = r 

7.  r 

)

/m+n=2r

7. m  n es entero par.

(de 7, por definición de número par)

Ejemplo. Sean a, b y c números enteros con a  0 y c  0. Demostrar que ac|bc si y sólo si a|b En este caso se trata de probar una equivalencia. Demostración. Probaremos que ac|bc  a|b En efecto, i) “Sólo si” () ac|bc  a|b. ac|bc   r 

/ bc = acr

 bc – acr = 0  bc – arc = 0  (b – ar) c = 0  b – ar = 0, pues c  0  b = a r, con r   r

/b=ar

77

Apuntes de Álgebra I

 a|b ii) “Si” () a|b  ac|bc. Usaremos la propiedad: a|b  c|d  ac|bd, con a  0 y c  0 Entonces, como c|c, se tiene a|b  c|c  ac|bc. Ejemplo. Demostrar que el cuadrado de cualquier número impar puede escribirse de la forma 4 k + 1. Solución. Sea a cualquier número entero. Por el teorema de existencia y unicidad de cociente y resto en , pueden encontrarse números enteros q y r, únicos, tales que a = 2q + r, con 0  r  2 es decir, a = 2q + r, con r = 0 o r = 1. Luego,  si r = 0, entonces a = 2q. Es decir a es par.  si r = 1, entonces a = 2q + 1. Es decir a es impar. Luego, a2 = (2q + 1)2  a2 = 4q2 + 4q + 1  a2 = 4(q2 + q) + 1  a2 = 4 k + 1, con k = q2 + q  Otra forma: Probaremos que: si a es un número impar, entonces a2 = 4 k + 1. En efecto, a es un número impar   p 

/ a = 2p + 1

 a2 = 4 p2 + 4 p + 1  a2 = 4(p2 + p) + 1  a2 = 4 k + 1, con k = p2 + p  Ejemplo. Demostrar que a) El cuadrado de cualquier número entero es de la forma 3 k o 3 k + 1 b) El cubo de cualquier número entero es de la forma 9 k o 9 k + 8. Solución. Sea n un entero cualquiera. Entonces por el teorema de la unicidad y resto en

, existen q y r

tales que n = 3 q + r, con 0  r  3 a) El cuadrado de n: n = 3 q + r  n2 = (3 q + r)2  n2 = 9 q2 + 6 qr + r2  n2 = 3(3 q2 + 2 qr) + r2  n2 = 3 p + r2, con p = 3 q2 + 2 qr 

78

Apuntes de Álgebra I

Entonces,  Para r = 0, n2 = 3 k, con k = p.  Para r = 1, n2 = 3 k + 1, con k = p.  Para r = 2, n2 = 3 p + 4 = 3 p + 3 + 1 = 3(p + 1) + 1 = 3 k + 1, con k = p + 1. b) El cubo de n: n = 3 q + r  n3 = (3 q + r)3  n3 = 27 q3 + 27 q2 r + 9 qr2 + r3  n3 = 9(3 q3 + 3 q2 r + qr2) + r3  n3 = 9 k + r3, con k = 3 q3 + 3 q2 r + qr2  Entonces,  Para r = 0, n3 = 9 k.  Para r = 1, n3 = 9 k + 1.  Para r = 2, n3 = 9 k + 8. Observación. En el ejemplo anterior, al dividir n2 por 3, el resto obtenido es 0 ó 1. Por esta razón, escribimos n = 3 q + r, con 0  r  3 Ejemplo. Determinar si la suma de tres números enteros consecutivos es siempre divisible por seis. Solución. Sean n, n + 1 y n + 2 los tres enteros consecutivos. Se determinará si 6|n + (n + 1) + (n + 2). Veamos, 6|n + (n + 1) + (n + 2)   q 

/ n + (n + 1) + (n + 2) = 6 q

Entonces, n + (n + 1) + (n + 2) = 6 q  3n + 3 = 6 q  3(n + 1) = 6 q  n + 1 = 2 q, con q  Luego, se tiene que n + 1 es par para cualquier n 

, lo cual es falso. Por tanto,

6∤ n + (n + 1) + (n + 2) Es decir, la suma de tres enteros consecutivos no es necesariamente divisible por 6. Ejemplo. Demostrar que el cuadrado de todo número entero es de la forma 4 k ó 4 k + 1. Demostración. Por el teorema de la existencia y unicidad del cociente y el resto en

, cualquier número

n puede escribirse en la forma n = 4 q + r, con 0  r  4 de aquí que n = 4 q + r  n2 = 16 q2 + 8 qr + r2  n2 = 4(4 q2 + 2 qr) + r2 = 4 p + r2, con p = 4 q2 + 2 qr   n2 = 4 p + r2, p  y ahora pueden ocurrir cuatro casos :

79

Apuntes de Álgebra I

 cuando r = 0, n2 = 4 k, con k = p.  cuando r = 1, n2 = 4 k + 1, con k = p.  cuando r = 2, n2 = 4 p + 4 = 4(p + 1) = 4 k, con k = p + 1.  cuando r = 3, n2 = 4 p + 9 = 4 p + 8 + 1 = 4(p + 2) + 1 = 4 k + 1 , con k = p + 2. Por tanto, en cualquier caso n2 puede escribirse de la forma 4 k ó 4 k + 1. Ejemplo. Verificar, si los números 2 p y 4 p + 3 son primos entre sí, cualquiera que sea p entero. Solución. Sea d = m.c.d. (2 p, 4 p + 3). Se debe verificar si d = 1. Veamos, d = m.c.d. (2 p, 4 p + 3)  d|2 p  d|4 p + 3

(Definición de m.c.d.)

 d|(-2) 2 p  d|4 p + 3  d|-4 p  d|4 p + 3  d|-4 p + 4 p + 3

(Propiedad de divisibilidad)

 d|3 Por tanto, en general, los enteros 2 p y 4 p + 3 no siempre son primos entre sí. Como por ejemplo, para el caso en que p = 1 cumple; pero para p = 3 no cumple. Ejemplo. Demostrar que: Si x 

, entonces x2  0

Demostración. Sea x un número cualquiera de x

. Luego, por el axioma de tricotomía (axioma de orden de  x

+

 x⋅x

 x = 0  (-x)  +

+

 x2 = 0  (-x) ⋅ (-x) 

 x2 

+

 x2 = 0  x2 

 x2 

+

 x2 = 0

) se tiene:

+

+

 x2  0  x2 = 0  x2  0 Por tanto, el cuadrado de cualquier número real, es mayor o igual a cero. Ejemplo. Probar que: Si la función f ( x) 

x 1 , entonces f es inyectiva 2x  1

Solución. Para probar que la función f es inyectiva, se debe probar que: f (a) = f (b)  a = b. En efecto, a 1 b 1  2 a  1 2b  1  (a  1) (2 b  1)  (b  1) (2 a  1)

f (a)  f (b) 

80

Apuntes de Álgebra I

 2 ab  a  2b  1  2 ab  b  2 a  1  a  2b  b  2a  b  a  ab

Por tanto, f es inyectiva. Ejemplo. Probar que: Si f ( x)  tan x , entonces f ( x)  (tan x)  sec2 x Solución. f ( x)  lím

h 0

f ( x  h)  f ( x ) h

tan x  tan h  tan x tan ( x  h)  tan x 1  tan x tan h  lím  lím h 0 h 0 h h 2 tan x  tan h  tan x  tan x tan h tan h  tan 2 x tan h  lím  lím h 0 h 0 h (1  tan x tan h) h (1  tan x tan h)  lím

h 0

 1.

 tan h  tan h  sec 2 x sec 2 x  lím   h (1  tan x tan h) h0  h 1  tan x tan h 

sec 2 x sec 2 x  1  tan x . 0 1

 sec 2 x

1.2.4 El método de demostración indirecta En el método de demostración indirecta, en lugar de demostrar la implicación H ⟹ T se demuestra una implicación equivalente. Para el método de demostración indirecta, tenemos dos casos: el método del contrarrecíproco y el método de reducción al absurdo. 1.2.4.1 Método de demostración por el contrarrecíproco En este método en lugar de demostrar la proposición Si H, entonces T se demuestra la proposición Si  T, entonces  H es decir, se hace uso de la ley del contrarrecíproco o contrapositivo: H ⟶ T  T ⟶ H En general, en lugar de probar la implicación H1  H2  …  Hn ⟹ T se prueba la implicación  T ⟹  (H1  H2  …  Hn)

81

Apuntes de Álgebra I

Notas: i) Para demostrar H ⟶ T, indirectamente, se supone que T es falsa (es decir,  T es verdadera) y se demuestra que H es falsa (es decir,  H es verdadera). ii) En la demostración por el contrarrecíproco, se supone que tanto H como  T son verdaderas. Pero, no se parte de H y  T; sino de  T y el objetivo es deducir que H es falsa, con lo que se llega a la contradicción () H   H. Ejemplo. Demostrar por el contrarrecíproco que: Si 3n + 2 es impar, entonces n es impar, con n 

.

Demostración. En lugar de demostrar la implicación 3 n  2 es impar  n es impar   H

T

demostraremos, por el contrarrecíproco, la implicación n no es impar  3 n  2 no es impar   

H

T

En efecto, sea n un entero cualquiera; entonces partiendo de  T : n no es impar  n es par  n = 2k, para algún k   3n = 6k  3n + 2 = 6k + 2  3n + 2 = 2(3k + 1)  3n + 2 = 2p, con p = 3k + 1   p

/ 3n + 2 = 2p

 3n + 2 es par  3n + 2 no es impar () Contradice a la hipótesis, ya que 3n + 2 es impar; es decir H es falsa y  H es verdadera . Por tanto, n es impar. Ejemplo. Sea n un número entero. Demostrar, mediante el método del contrarrecíproco, la siguiente propiedad: Si n 2 es par, entonces n es par O sea, n 2 es par  n es par

Demostración. Por el contrarrecíproco, demostraremos que:  ( n es par)   ( n 2 es par) n no es par  n 2 no es par n es impar  n 2 es impar

donde, H: n 2 es par, T: n es par. Entonces, demostraremos que H es falsa a partir de  T: n es impar.

82

Apuntes de Álgebra I

En efecto, 1. n es impar

hipótesis

2. n = 2p + 1, para algún entero p

definición de número impar

3. n 2 = (2p + 1)2

de 2, elevando al cuadrado

4. n 2 = 4p2 + 4p + 1

de 3, potencia de un binomio

5. n 2 = 2 (2p2 + 2p) + 1

de 4, por descomposición de factores

6. n 2 = 2q + 1

de 5, haciendo q = 2p2 + 2p 

7. n 2 es impar

de 6, definición de número impar.

Entonces, como  H es verdadera y H es falsa, hemos encontrado una contradicción (): n 2 es impar y n 2 es par. Por tanto, se concluye que n es par. Ejemplo. Probar la siguiente propiedad, para los conjuntos A y B. Si A  B = , entonces A =   B =  Demostración. Por el contrarrecíproco, probaremos que: Si A    B  , entonces A  B   A  B  AB

O sea, En efecto,

A  B  x/xA  x/xB  x/xA  xB  x/xAB  A  B   () Contradicción: A  B =   A  B  . Por tanto, A =   B = . Ejemplo. Demostrar la validez del siguiente razonamiento, usando el método del contrarrecíproco. p⟶ q ___________ pq ⟶ q

o bien, p ⟶ q  p  q ⟶ q

Demostración. Probaremos, por el contrarrecíproco, que el razonamiento,  (p  q ⟶ q) _____________  (p ⟶ q) es válido. Es decir,  (p  q ⟶ q)   (p ⟶ q). En efecto, 1.  (p  q ⟶ q)

Premisa 1

2.  [ (p  q)  q]

de 1, por ley del condicional

3.  [( p   q)  q]

de 2, por ley de De Demorgan

4.  [( p  q)  ( q  q)]

de 3, por ley distributiva

5.  [( p  q)  T ]

de 4, por tercio excluido

6.  ( p  q)

de 5, por ley de dominación

83

Apuntes de Álgebra I

7.  (p  q)

()

de 6, por ley del condicional

Por tanto, el razonamiento es válido. Ejemplo. Supongamos que m y b son números reales con m  0 y sea f la función definida por f (x) = m x + b Demostrar que: si x  y, entonces f (x)  f (y) ( f es una función inyectiva.) Es decir, x  y  f (x)  f (y) Demostración. Por el contrarrecíproco, probaremos que f (x) = f (y)  x = y. En efecto, f (x) = f (y)  m x + b = m y + b  mx = my  x = y, pues m  0 () Contradice que x  y. Por tanto, f (x)  f (y). Ejemplo. Demostrar que si c es un entero impar, entonces la solución de la ecuación n2 + n – c = 0, no es un entero impar. Demostración. Probaremos, por el contrarrecíproco, que la solución de la ecuación n2 + n – c = 0, es un entero impar  c no es un entero impar. En efecto, si r es solución de la ecuación n2 + n – c = 0 tal que r = 2p + 1, para algún p 

, entonces r2 + r – c = 0.

Luego, (2p + 1)2 + 2p + 1 – c = 0  4p2 + 4p + 1 + 2p + 1 – c = 0  c = 2 (2p2 + 2p + 1)  c = 2 k, con k = 2p2 + 2p + 1   c es un número par  c no es un número impar () Contradice a que c es un entero impar. Por tanto, la solución de la ecuación n2 + n – c = 0, no es un entero impar. Ejemplo. Demostrar: Si un entero m no es divisible por 2, entonces m no es divisible por 4. Demostración. Por el contrarrecíproco, probaremos que: Si un entero m es divisible por 4, entonces el entero m es divisible por 2 En efecto, m es divisible por 4  4|m  p

/ m = 4p

 m = 2 (2p)  m = 2k, con k = 2p 

84

Apuntes de Álgebra I

 k

/ m = 2k

 2|m  m es divisible por 2 () Contradice a que m no es divisible por 2. Por tanto, m no es divisible por 4. 1.2.4.2 Método de demostración por reducción al absurdo Otro tipo de demostración indirecta es la demostración por el absurdo o contradicción. Aquí, en lugar de demostrar la implicación H1  H2  …  Hn ⟹ T se demuestra  T  H1  H2  …  Hn ⟹ a una contradicción Es decir, el método de demostración por reducción al absurdo se fundamenta en la equivalencia H ⟶ T  H  T ⟶ C donde H y T son formas proposicionales y C una contradicción. Notas: i) En una demostración por reducción al absurdo, se debe suponer que H y  T son verdaderas y, usar esta información para llegar a una contradicción cualquiera. Es decir, dado un teorema de la forma: H ⟹ T, la idea de la demostración por reducción al absurdo es suponer que H es verdadera y T es falsa, luego ver que no puede ocurrir esto. O sea, encontramos una contradicción cualquiera r   r () y, por tanto, se concluye que la proposición dada es verdadera. Ejemplo. Demostrar, por el método de reducción al absurdo, que para todo entero n, si 5n + 3 es un número par, entonces n es un número impar Demostración.. Supongamos, por reducción al absurdo, que n no es impar. Entonces, la nueva hipótesis será H': H   T. O sea, H': 5 n  3 es un número par  n no es un número impar .   H  T Luego, 5n + 3 es par  n no es impar  5n + 3 es par  n es par  5n + 3 = 2p  n = 2q, para ciertos p, q   5(2q) + 3 = 2p  10q + 3 = 2p  p = 5q +

3  2

()

Contradice a que p es un número entero. Por tanto, la suposición es falsa y aceptamos que n es un número impar.

85

Apuntes de Álgebra I

El Dr. Miguel de Guzmán afirma: uno de los matemáticos más importantes de este siglo, el inglés G. H. Ardí, decía que “el método de reducción al absurdo, que tanto complacía a Euclides, es una de las armas más finas que puede emplear un matemático”. Ejemplo. Demostrar por el método de reducción al absurdo que Si 3n + 2 es impar, entonces n es impar Demostración. Supongamos, por el absurdo, que n no es impar o sea n es par ( T). Nueva hipótesis H': H y  T: 3n + 2 es impar y n es par Entonces, 3n + 2 es impar y n es par  3n + 2 = 2k + 1  n = 2p, para ciertos k, p   3(2p) + 2 = 2k + 1  6p + 2 = 2k + 1  6p = 2k – 1  p=

2𝑘 − 1 6

 p

()

Contradice a que p es un número entero. Por tanto, la suposición es falsa y n es impar. ii) El método de reducción al absurdo se puede aplicar cuando la proposición T contiene la palabra no o cuando contiene el cuantificador existe (). Por ejemplo, en las proposiciones siguientes se puede aplicar el método de reducción al absurdo.  Proposición: si r es un número real tal que r2 = 2, entonces r no es racional.  Proposición: si A  B, entonces  x / x  A  x  B. Ejemplo. Demostrar que: Si r es un número real tal que r2 = 2, entonces r no es racional Demostración. Supongamos, por reducción al absurdo, que r es racional (r  r=

𝑎 𝑏

, a, b 

). Entonces,

, b  0; a y b primos entre si.

Elevando al cuadrado, r2 =

𝑎2 𝑏2

. ...... ∗

De ∗ : r2 =

𝑎2 𝑏2

= 2  a2 = 2 b2 = 2p, con p = b2   a2 es par  a es par (2|a)

Entonces, a es par  a = 2k, para algún k 

.

En ∗ : r2 =

𝑎2 𝑏2



(2𝑘)2 𝑏2

= r2

86

Apuntes de Álgebra I



4 𝑘2 𝑏2

= 2  4 k2 = 2 b2

 b2 = 2 k2  b2 es par  b es par (2|b) Así, 2 es divisor común de a y b (). Es una contradicción, ya que a y b son primos entre si. Por tanto, la suposición es falsa y r no es racional. Ejemplo. Demostrar que: Si A  B, entonces  x / x  A  x  B Demostración. Supongamos, por reducción al absurdo, que no es cierto que ( x / x  A  x  B). Entonces,  ( x / x  A  x  B)   x, (x  A  x  B) Luego,  x, (x  A  x  B)   x, (x  A  x  B)  A  B () Contradice a la hipótesis que afirma A  B. Por tanto, la suposición es falsa y  x / x  A  x  B. iii) También, el método de reducción al absurdo nos dice que: (H1  H2  …  Hn ⟹ T)  (H1  H2  …  Hn   T ⟹ C) donde, T: conclusión y C: contradicción. Es decir, si al agregar a las premisas la negación de la conclusión se obtiene como consecuencia lógica una contradicción, entonces el razonamiento es válido. La contradicción que aparece es de la forma m   m. Ejemplo. Mediante el método de reducción al absurdo, probar la validez del siguiente razonamiento: p  (q  r) q  p t  r p ____________ r Demostración. A las premisas dadas, le agregamos la negación de la conclusión y, aplicando las leyes lógicas o inferencias; buscamos una contradicción. En efecto, 1. p  (q  r)

Premisa 1

2. q   p

Premisa 2

3. t   r

Premisa 3

4. p

Premisa 4

5.  r

Premisa adicional, por reducción al absurdo

6.  ( p)

de 4, por doble negación

87

Apuntes de Álgebra I

7.  q

de 2 y 6, por Modus Tollendo Tollens (MTT)

8. q  r

de 1 y 4, por Modus Ponendo Ponens (MPP)

9. q

de 8 y 5, por Silogismo Disyuntivo

10. q   q ()

de 9 y 7, por ley del conjunción

11. r

de 10, por ley de reducción al absurdo

Ejemplo. Demostrar que: Si el cuadrado de un número entero es impar, entonces el número es impar Expresado de otra forma: Sea n un entero, si n2 es impar, entonces n es impar Demostración. Supongamos, por el absurdo, que n no es impar. Entonces, la nueva hipótesis será: H': n2 es impar y n no es impar. Luego, n2 es impar y n no es impar  n2 es impar y n es par  n2 = 2k + 1  n = 2p, para ciertos k, p   n2 = 2k + 1  n2 = 4p2  2k + 1 = 4p2  1 = 4p2 – 2k = 2(2p2 – k)  1 = 2q, con q = 2p2 – k   1 es un número par () Contradice a que 1 es un número impar. Por tanto, la suposición es falsa y aceptamos que n es impar. Ejemplo. Demostrar que el número real

3 no es racional. Es decir,

3 es real 

3 no es racional

Demostración. Haremos uso de la propiedad: Sea x 

, x2 es divisible por 3  x es divisible por 3.

Entonces, Supongamos, por el absurdo, que

3

a , a, b  b

, b  0 y a, b irreducibles. Luego, elevando al cuadrado: 3

 De (∗):

3 es racional ( 3  ). Luego,

a2  a 2  3 b2 b2

…………. (∗)

a2 = 3 b2  a2 = 3p, con p = b2 

 3|a2  3|a. De aquí,

a 2 es divisible por 3  a es divisible por 3. (por la propiedad mencionada)

 Siendo, a es divisible por 3  3|a   k 

/ a = 3k. Entonces, en (∗), se tiene:

(3k)2 = 3b2  9k2 = 3b2  b2 = 3k2  b2 = 3q, con q = k2   3|b2  3|b  b es divisible por 3 (propiedad anterior)

88

Apuntes de Álgebra I

Se tiene, entonces, que a y b son divisibles por 3 y, por tanto no son irreducibles ( ). Esto contradice a lo supuesto de que a y b eran irreducibles. Esta contradicción es el resultado de suponer que racional. Por tanto, admitimos que

3 es

3 no es racional.

Ejemplo. Demostrar la siguiente propiedad: Si n2 es divisible por 3, entonces n es divisible por 3 Demostración. Probaremos que: 3|n2  3|n. Supongamos, por reducción al absurdo, que n no es divisible por 3. Entonces, n no es divisible por 3  3∤n   k 

, n  3k

 n2  9k2  n2  3(3k2)  n2  3p, con p = 3k2   p

, n2  3p  3∤n2

 n2 no es divisible por 3 () Contradice a que n2 es divisible por 3. Por tanto, la suposición es falsa y n es divisible por 3. Ejemplo. Probar que: Si n = k3 – k, para algún k  , entonces n es divisible por 6. Solución. De la hipótesis, se tiene: n = k3 – k = k (k2 – 1) = k (k + 1) (k – 1) Pero, para algún k 

resulta que el número k (k + 1) es par. Es decir, k (k + 1) = 2p, para algún p 

.

Entonces, n = k (k + 1) (k – 1) = 2p (k – 1) = 2(pk – p) = 2q, con q = pk – p 

 n es par.

Ahora, supongamos, por el absurdo, que n no es divisible por 6. Entonces, n no es divisible por 6  6∤n   m 

, n  6m

 n  2(3m)  n  2r, con r = 3m   n no es par () Contradice a que n es par. Por tanto, la suposición es falsa y n es divisible por 6. Ejemplo. Demostrar que si q es un entero no divisible por 2 ni divisible por 3, entonces q2 – 1 es divisible por 12. Demostración. Probaremos que: 2∤q  3∤q  12|q2 – 1 Supongamos, por el absurdo, que 12∤q2 – 1. Entonces, 12∤q2 – 1   k 

, q2 – 1  12k

 q2 – 1  2(6k)  q2 – 1  2p, con p = 6k   q2 – 1 no es par  q2 – 1 es impar  q2 – 1 = 2m + 1, para algún m 

89

Apuntes de Álgebra I

 q2 = 2m + 2  q2 = 2(m + 1)  q2 = 2n, con n = m + 1   q2 es par  q es par  q es divisible por 2  2|q () Contradice a que 2∤q. Por tanto, la suposición es falsa y 12|q2 – 1. 1.2.5 Demostración por inducción Este método de demostración está relacionada a la definición del conjunto de los enteros naturales ( ) o +

enteros positivos (

). Es una técnica para probar que una propiedad P (n) es cierta para todos los

enteros naturales n, o para los que son iguales o superiores a un cierto n. En 1889 Guiseppe Peano (1858 – 1932) presentó la siguiente axiomática para los números naturales

.

1) 1  . 2)  n  : ! n + 1  . 3)  n  : n + 1  1. 4)  n, m  : n  m  n + 1  m + 1 5) [𝑆 ⊂ ℕ 𝑡𝑎𝑙 𝑞𝑢𝑒 {

𝑎) 1 𝜖 𝑆 ] ⟹ 𝑆= ℕ 𝑏) 𝑛 𝜖 𝑆 ⟹ 𝑛 + 1 𝜖 𝑆

El axioma 5, Axioma de inducción, nos permitirá demostrar la validez de proposiciones en todo el conjunto de los enteros naturales. El Principio de Inducción Matemática Teorema. Sea H de

un subconjunto de

tal que:

i) 1  H. ii) Si p  H, entonces p + 1  H. Entonces, H = . En efecto, De i) y ii) implican que H es inductivo, por tanto

 H.

Por hipótesis se tiene que H  . Luego, por el teorema de igualdad de conjuntos (como veremos más adelante) debe ser H =

.

El principio de inducción matemática es útil para probar la veracidad de propiedades relativas a los números naturales (enteros positivos). Por ejemplo, consideremos las siguientes propiedades: P (n), Q (n) y R (n) tales que: a) P (n): 2n – 1  n2 + 1. b) Q (n): si n es par, entonces n es divisible por 4. c) R (n): 2n  n – 1. Intuitivamente observamos que P (n) es verdadera para cualquier n natural, Q (n) lo es para algunos valores de n y es falsa para otros; y R (n) es falsa para todo n 

. Sin embargo, para verificar realmente

90

Apuntes de Álgebra I

que la propiedad P(n) es verdadera para todo n natural no podemos hacerlo para cada n en particular. Resulta entonces muy útil el siguiente teorema equivalente al del Principio de inducción. Teorema. Sea P (n) una propiedad de n 

tal que:

1. Se cumple que P (1) es verdadera. 2. Hipótesis Inductiva: Asumiendo que para todo k  , P (k) es verdadera implica P (k + 1) verdadera. Por tanto, P (n) es verdadera para todo n  . A partir del Principio de Inducción es posible probar una gran cantidad de fórmulas o identidades, que involucran un número natural n o número positivo n . Por tanto, a continuación enunciamos, a manera de ejemplos, algunas propiedades de los números naturales, y la demostración de su veracidad la haremos usando el Principio de Inducción. Ejemplo. Probar que 2n  n, para todo n natural. Demostración. Sea P (n): 2n  n. Debemos demostrar que: 1. P (1) es verdadera y que 2. P (k) verdadera  P (k + 1) verdadera. Nota. A P (k) verdadera se le llama Hipótesis inductiva. Entonces, 1. Para n = 1, P (1) es verdadera, pues 21  1. 2. Hipótesis Inductiva. Suponemos verdadera para P (k): 2k  k. (n = k  1) Entonces, debemos probar que: 2k  k  2k+1  k + 1. En efecto, 2k+1 = 2k ⋅ 2 = 2 ⋅ 2k = 2k + 2 k  k+k

(Hipótesis inductiva)

 k+1

( Pues, k  1 y k + k  k + 1,  k  )

Por tanto, por transitividad se sigue que 2k+1  k + 1. Luego, P (n) es verdadera para todo n natural. Observación. La transitividad anterior se refiere a lo siguiente: Si 2k+1  k + k y k + k  k + 1, entonces 2k+1  k + 1 Ejemplo. Demostrar que una expresión de la forma 32n – 1 es divisible por 8, para todo n natural. Demostración. Sea P (n): 32n – 1 es divisible por 8,  n  . Es decir, P (n): 8 32n – 1,  n  . Entonces, 1. Para n = 1, se tiene: 32(1) – 1 = 9 – 1 = 8 = 8 ⋅ 1. O sea,  1 

/ 8 = 8 ⋅ 1  8 8.

91

Apuntes de Álgebra I

Luego, para n = 1, P (1) es verdadera. 2. Hipótesis inductiva. Suponemos verdadera para n = k, P (k): 32k – 1 es divisible por 8. Es decir, 8 32k – 1   r 

/ 32k – 1 = 8r. Por tanto, probaremos que para n = k + 1 es,

también, verdadera. O sea, 8 32k – 1  8 32(k+1) – 1 En efecto, 32(k+1) – 1 es divisible por 8 si existe un p 

tal que 32(k+1) – 1 = 8 p. Veamos,

32(k+1) – 1 = 32k+2 – 1 = 32k ⋅ 32 – 1 = 32 ⋅ 32k – 1 = 32 ⋅ 32k + 32 – 32 – 1 = 32(32k – 1) + 32 – 1 = 32(32k – 1) + 8 = 32 ⋅ 8r + 8

(Hipótesis inductiva)

= 8(9r + 1) = 8 p, con p = 9r + 1  Entonces,

p

/ 32(k+1) – 1 = 8 p  8 32(k+1) – 1.

Por tanto, P (n) es verdadera para todo n natural. Ejemplo. Demostrar que la expresión a2n – 1 es divisible por a + 1, para cualquier n natural. Demostración. Sea P (n): a2n – 1 es divisible por a + 1,  n  . Es decir, P (n): a + 1 a2n – 1,  n  . Entonces, 1. Para n = 1, se tiene: a + 1 a2 – 1  a + 1 (a + 1) (a – 1). Luego, a2 – 1 es divisible por a + 1. Por tanto, P (1) es verdadero. 2. Hipótesis inductiva. Suponemos verdadera para n = k, P (k): a2k – 1 es divisible por a + 1. Es decir, a + 1 a2k – 1   p 

/ a2k – 1 = (a + 1) p. Por tanto, probaremos que también

para n = k + 1, a2(k+1) – 1 es divisible por a + 1. O sea, a + 1 a2(k+1) – 1 En efecto, a2(k+1) – 1 = a2k+2 – 1 = a2k a2 – 1 = a2k a2 – 1 + a2 – a2 = a2(a2k – 1) + a2 – 1 = a2 (a + 1) p + (a + 1) (a – 1) = (a + 1) (a2 p + a – 1) = (a + 1) q, con q = a2 p + a – 1  Luego  q 

/ a2(k+1) – 1 = (a + 1) q  a + 1 a2(k+1) – 1. Es decir, a2(k+1) – 1 es divisible

por a + 1. Por tanto, P (n) es verdadera para todo n natural. Ejemplo. Probar que:  n  , 8n – 1 + 6 es divisible por 7 Es decir,

92

Apuntes de Álgebra I

 n  , 7|8n – 1 + 6 Demostración. Sea P (n): 8n – 1 + 6 es divisible por 7,  n  . Es decir, P (n): 7|8n – 1 + 6,  n  . Entonces, 1. Para n = 1, se tiene: 7|80 + 6  7 1 + 6  7|7 Luego, P (1) es verdadero. 2. Hipótesis inductiva. Suponemos verdadera para n = k, P (k): 8k – 1 + 6 es divisible por 7. Es decir, 7|8k – 1 + 6   m 

/ 8k – 1 + 6 = 7m. Entonces, probaremos que también para

n = k + 1, 8k + 6 es divisible por 7. O sea, 7|8k + 6 En efecto, 8k + 6 = 8k – 1 ⋅ 8 + 6 = 8k – 1 ⋅ 8 + 6 + 6 ⋅ 8 – 6 ⋅ 8 = 8(8k – 1 + 6) – 42 = 8(8k – 1 + 6) – 7 ⋅ 6 = 8 ⋅ 7m – 7 ⋅ 6 = 7(8m – 6) = 7p, con p = 8m – 6  Luego  p 

/ 8k + 6 = 7p  7|8k + 6. Es decir, 8k + 6 es divisible por 7.

Por tanto, P (n) es verdadera para todo n natural. Ejemplo. Demostrar que para todo n  1, n  , 1 + 4 + 7 + . . . + (3n – 2) = Demostración. Sea P (n) = 1 + 4 + 7 + . . . + (3n – 2) =

n (3n  1) 2

n (3n  1) . Entonces, 2

1) Para n = 1, 3(1) – 2 =

1(3(1)  1)  1 = 1. Por tanto, P (1) es verdadera. 2

2) Hipótesis inductiva. Supongamos que para n = k, se cumple que: P (k): 1 + 4 + 7 + . . . + (3k – 2) =

k (3k  1) 2

Probaremos que para n = k + 1 es: P (k + 1): 1 + 4 + 7 + . . . + (3k – 2) + (3k + 1) =

(k  1) (3k  2) 2

En efecto, 1 + 4 + 7 + . . . + (3k – 2) + (3k + 1) = =

3k 2  k  6k  2 k (3k  1) + (3k + 1) = 2 2 3k 2  5k  2 (k  1) (3k  2)  2 2

Por tanto, se tiene que para todo n  1, el enunciado es verdadero.

93

Apuntes de Álgebra I

Ejemplo. Probar la fórmula que representa la suma de los primeros n números naturales: 𝑛 (𝑛 + 1)

1+2+3+...+ n= Demostración. Sea P (n): 1 + 2 + 3 + . . . + n =

2

𝑛 (𝑛 + 1) 2

, n

, n  . Entonces,

1. Para n = 1, 1=

1 (1 + 1) 2

= 1. Por tanto, P (1) es verdadera.

2. Hipótesis inductiva. Suponemos verdadera para n = k. o sea P(k): 1 + 2 + 3 + . . . + k =

𝑘 (𝑘 + 1) 2

, es verdadera

Probaremos que para n = k + 1, P (k + 1), la fórmula es verdadera; es decir 1+2+3+...+ k+k+1=

(𝑘 + 1) (𝑘 + 2) 2

es verdadera

En efecto, 1 + 2 + 3 + . . . + k + k + 1 = (1 + 2 + 3 + . . . + k) + (k + 1) = = = Vemos que esta última fórmula es igual a

𝑛 (𝑛 + 1) 2

𝑘 (𝑘 + 1) 2

+ (k + 1)

(Hip. Inductiva)

𝑘 (𝑘 + 1) + 2 (𝑘 + 1) 2 (𝑘 + 1) (𝑘 + 2) 2

, con n = k + 1. Por tanto, P (k + 1) es verdadera, si

se asume que P(k) es verdadadera. Luego, P(n) vale para todo n natural. Nota. Cuentan que siendo niño, el célebre matemático Gauss estaba un tanto inquieto en su clase. Para que tuviera algo con qué contentarse su maestro le pidió que sumara todos los números del 1 al 100. Gauss tardó pocos minutos en dar la respuesta: 5050. ¿Cómo lo hizo?. El niño observó que si sumaba los números agrupando el primero con el último, el segundo con el penúltimo y así sucesivamente el cálculo se simplificaba bastante, o sea 1 + 2 + 3 + . . . + 100 = (1 + 100) + (2 + 99) + (3 + 98) + . . . + (50 + 51) = ⏟ 101 + 101 + 101 + . . . + 101 = 50 (101) 50 𝑣𝑒𝑐𝑒𝑠 𝑐𝑜𝑚𝑜 𝑠𝑢𝑚𝑎𝑛𝑑𝑜

= 5050

EJERCICIOS PROPUESTOS 1. Mediante el método del contrarrecíproco, probar la validez de los razonamientos siguientes : a) p  q __________ p  pq

b) (p   q)  (q  r) _________________ (p  q)  r

94

Apuntes de Álgebra I

c) p  (q  r) ____________ (p  q)  r

d) p  q ____________ p  q  q

2. Demostrar, en el conjunto

, que:

i ) Si p es un número par y q un número impar, entonces p⋅q es un número par. ii ) El producto de dos números impares es impar. iii ) La suma de dos números impares es par. iv) La suma de un número par y un número impar, es impar 3. Demostrar que la diferencia de los cubos de dos números enteros consecutivos no puede ser múltiplo de 3. 4. Demostrar que si m.c.d .(a, b)  1 , entonces m.c.d .(a  b, a  b)  1  2 . 5. Pruébese que si a y b son números positivos e impares, entonces

a) 2 divide a a 2  b2 ; b) 4 no divide a a 2  b2 . 6. Demuestre que el cuadrado de cualquier número impar puede escribirse de la forma 8 k  1 . 7. Demuestre que el cuadrado de cualquier número entero es de la forma 3 k o 3 k  1 , k  8. Demuestre, por inducción matemática, que para todo n 

+

.

se cumple que:

(1 + 2 + 3+ . . . +𝑛)2 = 13 + 23 + 33 + . . . + 𝑛3 9. Demostrar por el método de reducción al absurdo las siguientes afirmaciones: a) Si n 

+

y n2 es múltiplo de 3, entonces n es múltiplo de 3.

b) √2 + √6  √15 c) √6 – √2  1. d) Si n = k3 – k par algún k 

+

, entonces n es múltiplo de 6.

10. Demostrar por inducción matemática que  n  n (3 n  1) . a) 1  4  7  . . .  3 n  2  2

+

, n  1:

b) 1 + 3 + 5 + . . . + (2n – 1) = n2. c) 3n3  2 n . d) 2n2  2 n . e) 5n  1  4 n .

95

Apuntes de Álgebra I

f) 3n  1  2 n . g) n  2n. h) 4|n4 + 2n3 + n2. i) 13 + 23 + 33 + . . . + n3 =

n 2 ( n  1) 2 . 4

j) a + ar + ar2 + . . . + arn-1 =

11. Si n 

+

a (r n  1) , r  1. r 1

y n es impar, pruébese que 8n 2  1 . (Por inducción)

12. Determine si la suma de tres números enteros consecutivos es siempre divisible por 6. 13. Demuestre que √5 es irracional. 14. Demostrar, usando el método directo, la siguiente propiedad: Para cualquier n 

, Si n es número par, entonces 5 n  3 es número impar.

15. Demuestre que el cuadrado de cualquier número impar puede escribirse de la forma 8 k  1 . 16. Demuestre que el cubo de cualquier número entero es de la forma 9 k , 9 k  1 o 9 k  8; k 

.

17. Determine si la suma de tres números enteros consecutivos es siempre divisible por 6. 18. Demostrar que n3 + 5n es divisible por 6, para todo n 

+

.

19. Demostrar la identidad siguiente: cos x . cos (2 x) . cos (4 x) . . . cos (2 n x) 

sen (2 n 1 x) 2 n 1 . sen x

96