Lógica y teoría de conjuntos

Diana Patricia Acevedo VélezJuan Carlos Arango Parra

Formación / Matemácas

Lógica y teoría de conjuntos

Colección Formación / Matemáticas© Diana Patricia Acevedo Vélez, Juan Carlos Arango Parra© Editorial Universidad de Antioquia®

ISBN: 978-958-714-936-4ISBNe: 978-958-714-937-1

Primera edición: abril del 2020Impresión y terminación: Imprenta Universidad de Antioquia

Impreso y hecho en Colombia / Printed and made in ColombiaProhibida la reproducción total o parcial, por cualquier medio o con cualquierpropósito, sin autorización escrita de la Editorial Universidad de Antioquia

Editorial Universidad de Antioquia®

(574) 219 50 10editorial@udea.edu.cohttp://editorial.udea.edu.coApartado 1226. Medellín, Colombia

Imprenta Universidad de Antioquia(574) 219 53 30imprenta@udea.edu.co

Acevedo Vélez, Diana PatriciaLógica y teoría de conjuntos / Diana Patricia Acevedo Vélez, Juan

Carlos Arango Parra. - - 1. edición - - Medellín: Editorial Universidad deAntioquia; 2020.

xiii, 188 páginas. – (Colección: Formación / Matemáticas)ISBN: 978-958-714-936-4ISBNe: 978-958-714-937-11. Lógica matemática. 2. Teoría de conjuntos. I. Arango Parra, Juan

Carlos. II. Título. III. Serie.LC QA248511.3-dc23

Catalogación en publicación de la Biblioteca Carlos Gaviria Díaz

Introducción ............................................................................................. xi

Capítulo 1 .Sistemas formales ............................................................................................. 11.1 Profundización ........................................................................................... 91.2 Ejercicios .................................................................................................... 9

Capítulo 2 . Lógica proposicional ......................................................................................... 13 2.1 Proposiciones y conectores ......................................................................... 132.1.1 Proposiciones compuestas ...................................................................... 152.1.2 Tautologías, indeterminaciones y contradicciones ................................. 212.1.3 Circuitos lógicos ....................................................................................... 242.2 Ejercicios ..................................................................................................... 302.3 Sistema formal ............................................................................................ 352.3.1 Alfabeto ................................................................................................ 352.3.2 Reglas de formación ................................................................................ 352.3.3 Definiciones ............................................................................................. 362.3.4 Axiomas .................................................................................................. 362.3.5 Reglas de inferencia ................................................................................ 372.3.6 Teoremas ................................................................................................ 382.4 Profundización ............................................................................................ 532.5 Ejercicios .................................................................................................... 53

Contenido

2.6 Argumentación, razonamiento e inferencia .............................................. 562.7 Ejercicios ..................................................................................................... 61

Capítulo 3 .Lógica cuanficacional ...................................................................................... 663.1 Nociones preliminares ............................................................................... 663.2 Sistema formal ........................................................................................... 72 3.2.1 Alfabeto .................................................................................................... 72 3.2.2 Reglas de formación ................................................................................ 723.2.3 Definiciones ............................................................................................ 733.2.4 Axiomas .................................................................................................. 733.2.5 Reglas de inferencia ................................................................................ 733.2.6 Teoremas ................................................................................................ 743.3 Inferencias .................................................................................................. 793.4 Profundización ........................................................................................... 813.5 Ejercicios .................................................................................................... 82

Capítulo 4 . Métodos de demostración ............................................................................... 844.1 Introducción .............................................................................................. 844.2 Método directo ........................................................................................... 844.2.1 Ejemplos de lógica proposicional ............................................................ 854.2.2 Ejemplos de números pares e impares ................................................ 864.2.3 Ejemplos de relación de orden ............................................................. 884.2.4 Ejemplos de divisibilidad ......................................................................... 894.2.5 Ejemplos de complejos ........................................................................... 914.3 Método del contraejemplo ........................................................................ 944.4 Método de casos ........................................................................................ 954.5 Método del contrarrecíproco ...................................................................... 974.6 Método indirecto ........................................................................................ 994.7 Inducción matemáca ................................................................................. 1024.8 Profundización .......................................................................................... 1084.9 Ejercicios ..................................................................................................... 109

Capítulo 5 .Teoría de conjuntos ........................................................................................... 115

5.1 Ideas preliminares ............................................................................... 115

5.2 Sistema formal ................................................................................. 117

5.2.1 Alfabeto ........................................................................................... 118

5.2.2 Reglas de formación ......................................................................... 118

5.2.3 Definiciones, axiomas y teoremas ..................................................... 118

5.3 Operaciones entre conjuntos ............................................................... 124

5.4 Situaciones problema .......................................................................... 136

5.5 Conjunto de partes ............................................................................. 140

5.6 Profundización ................................................................................... 143

5.7 Ejercicios ........................................................................................... 143

Capítulo 6

Relaciones ............................................................................................... 149

6.1 Introducción ........................................................................................ 149

6.2 Producto cartesiano ............................................................................ 149

6.3 Relaciones binarias .............................................................................. 154

6.3.1 Representación de la gráfica de una relación ....................................... 156

6.3.2 Elementos de una relación ................................................................ 161

6.3.3 Relación inversa ............................................................................... 164

6.3.4 Relación compuesta ......................................................................... 166

6.4 Relaciones definidas sobre conjuntos .................................................... 169

6.5 Profundización .................................................................................... 180

6.6 Ejercicios ............................................................................................ 181

Bibliograa ............................................................................................... 185

Introducción

Estas notas de clase han permitido enriquecer el trabajo del curso de Lógicay Teoría de Conjuntos para el programa de Licenciatura en Matemáticas y

Física (Facultad de Educación) en los últimos nueve años, donde los autores he-mos sido parte activa como estudiantes y docentes. El curso se ha enfocado enla formalidad de las matemáticas (lógica clásica) desde la construcción teóricaque plantea Guillermo Restrepo en Los fundamentos de las matemáticas [15]o desde una interpretación de esta. Este libro se escribió como ayuda para losestudiantes y enfoca el trabajo para otros cursos como Cálculo (conjuntos y re-laciones) y Estadística (conjuntos), pero, sobre todo, para los cursos de Análisisy Sistemas y Estructuras (inducción, métodos de demostración, conjuntos, etc.)en la Universidad de Antioquia.

Es necesario resaltar que la forma de presentación de las demostracionescomo afirmación-razón tiene un fin pedagógico: somos conscientes de que en ar-tículos y libros especializados la forma de demostrar se escribe en prosa. Caberesaltar que no hay un camino único para hacer las demostraciones; la habili-dad para hacerlo se desarrolla con la solución de diferentes ejercicios en contex-tos variados: es por ello que se presentan más de cuatrocientas demostracionesresueltas y propuestas en diferentes ámbitos.

Las partes de un sistema formal (alfabeto, axiomas, definiciones) y sus con-secuencias (teoremas) deben ser enlazados por medio de las reglas de inferen-cia. Al unir los dos bloques se genera un espacio entre ellos que se construye demanera personal, pieza a pieza, a través del entendimiento del sistema formaly sus aplicaciones (es una construcción del sujeto); sin embargo, siempre ha-brá espacios entre los bloques, ya que no todos los enunciados son demostrables.

xii

El libro se estructuró de la siguiente manera:En el capítulo 1 se estudian los sistemas formales; con este apartado se

pretende conceptualizar sobre términos como fórmulas bien formadas (f. b. f.),axioma, hipótesis, teorema, demostración, entre otros, y se indica qué es unsistema formal.

En el capítulo 2 se trabaja con las proposiciones y los conectores, que sonlos elementos conceptuales para la construcción del sistema formal de la lógicaproposicional. En primer lugar se presentan las tablas de verdad que luegose utilizan para “mostrar” que algunos enunciados son ciertos (tautologías) y,posteriormente, se demuestran. Sin embargo se aclara que otros autores iniciandemostrando los teoremas para construir la tabla de verdad de los conectores.

En el capítulo 3 se presentan las funciones proposicionales y el sistema for-mal de la lógica cuantificacional.

El capítulo 4 trata los métodos de demostración, los cuales se validan pormedio de la lógica proposicional, pero se estudian en contextos como los de lossistemas numéricos y en conceptos como números pares e impares, divisibili-dad, números complejos, orden y número racional. Aprender a demostrar de-pende, en última instancia, de la persona que está interesada en este menester.

En el capítulo 5 se abordan los conjuntos basados en la lógica proposicional,cuantificacional y las representaciones en diagramas de Venn, al analizarseel cardinal y otros conceptos importantes para el desarrollo axiomático de laestadística. El producto cartesiano se deja para el estudio del capítulo 6, pese aque muchos autores lo trabajan en conjuntos.

En el capítulo 6 se estudia el concepto de relación y su consecuencia en elcálculo.

Al final de cada capítulo se anexa una serie de ejercicios de cada tema quese relaciona con conceptos, demostraciones, indagaciones, etcétera. Anexamosuna sección de profundización donde el estudiante puede ir más allá de lastemáticas estudiadas en el curso, pero que no se evalúan por el corto tiempoque se tiene para lograr los objetivos del mismo.

En el curso se han estudiado otros documentos como complemento de algu-nas temáticas, pero que no han sido tomados como obligatorios y no se anexaronen este libro, acerca de, por ejemplo, álgebra booleana, bloques lógicos, sistemasnuméricos, familias de conjuntos, cardinalidad, entre otros.

Como parte de la metodología del curso, hay temáticas que no se abordande forma directa, como “la lógica en el cine”, “la lógica en los estándares dematemáticas”, “las herramientas tecnológicas que posibilitan el estudio de lalógica”, “la lógica desde Lewis Carroll”, “las lógicas no-clásicas”, etc. Algunas de

xiii

estas situaciones fueron plasmadas en blogs como parte de seguimiento del cur-so. La mejor propuesta fue la del estudiante Sergio Correa Díez (http://proofandfundamentals.blogspot.com); en ella, por medio de videos y explicaciones, se ha-ce un aporte a la enseñanza y el aprendizaje de algunas demostraciones enmatemáticas.

1Sistemas formales

El “lenguaje natural” se refiere a las lenguas utilizadas por las diferentescomunidades de hablantes en sus procesos de comunicación (castellano,

inglés, francés, etc.). Se denomina así porque se trata de convenciones humanasconstruidas a lo largo de un gran periodo histórico. De este modo, cada formade nombrar las cosas es convencional (está establecida de una manera determi-nada).

Este lenguaje se utiliza para asuntos diversos como expresar deseos, pre-guntar, etc. También se usa para hacer afirmaciones sobre lo que ocurre o paradescribir objetos y situaciones; estas afirmaciones son las que interesan a laciencia (con su validación), ya que con ellas se expone o construye un conoci-miento de algo (uso referencial).

El lenguaje natural es el vehículo con el que se consigue una enorme expre-sividad y riqueza comunicativa, pero con él se pueden presentar deficien-cias en la comunicación. Con el lenguaje natural surgen los mitos como unacreación colectiva para dar una explicación racional o no de los diferentes fe-nómenos que acontecen en la cotidianidad, y da poderes sobrehumanos a seresinanimados sobre quienes se despliega una gran carga emocional. Este lengua-je es ambiguo, no es exacto, propicia diversas interpretaciones y es muy pocooperativo, pero es el sistema con mayor capacidad expresiva y permite conocerel mundo que habitamos e imaginar otros.

Por otro lado, el “lenguaje artificial” surge para resolver los problemas queplantea el lenguaje natural; es creado de una manera absolutamente conscientey voluntaria, a diferencia de la espontaneidad que caracteriza los lenguajesnaturales.

Un caso particular de los lenguajes artificiales son los “lenguajes formales”,que se definen completamente sin que haya necesidad de darles interpretaciónalguna; es decir, están exentos de cualquier componente semántico fuera de

2 Lógica y teoría de conjuntos

sus signos, y es gracias a esta ausencia de significado especial que los lengua-jes formales pueden ser usados para modelar distintas teorías, debido a que loimportante en estas son las estructuras que se construyen con sus signos. Ade-más, los lenguajes formales se pueden identificar con el conjunto de palabraso “fórmulas bien formadas” (f. b. f., cadenas de signos o caracteres) de longitudfinita, construidas a partir de un “alfabeto” (conjunto de signos) y teniendo encuenta unas “reglas de formación” (gramática). Así, se puede decir que para de-finir un lenguaje formal es necesario:

1. Determinar el alfabeto: dicho alfabeto es un conjunto de signos de la lengua(signos primitivos y/o signos auxiliares). Los signos auxiliares más caracte-rísticos son los signos de agrupación: paréntesis, corchetes y llaves.

2. Determinar el conjunto de reglas de formación, que definen qué secuenciaso cadenas de signos del alfabeto son f. b. f. de la lengua escrita, al cuidar queuna regla no contradiga la otra.

3. Designar lo anterior sin apelar a ninguna interpretación.4. Definir, es decir, proporcionar autorizaciones para usar un signo abreviado

(combinación de signos) en lugar de una combinación de signos primitivos ode otros signos ya definidos.

Si se constituye un mecanismo deductivo para un lenguaje formal, esto lle-va al concepto de “sistema formal". Un mecanismo deductivo para un lenguajeformal L está constituido por la estipulación de algunas fórmulas del lengua-je L, como “axiomas”, y/o el establecimiento explícito de un conjunto de reglasde transformación o “reglas de inferencia”, que determinan qué relaciones en-tre las fórmulas del lenguaje constituyen relaciones de consecuencia inmediata(derivación o deducción de unas fórmulas a partir de otras). Los axiomas sontambién f. b. f. que se asumen como verdaderas sin demostración y que sirvencomo base para la construcción de las teorías científicas.

A toda cadena que ha de deducirse a partir de los axiomas, por aplicacio-nes sucesivas de las reglas de inferencia, se le denomina “teorema”, al igualque a toda fórmula que se deduce de otros teoremas. Esta aplicación sucesivade reglas recibe el nombre de “deducción” o “demostración”; las demostracio-nes se pueden presentar de dos maneras: por afirmación-razón o en prosa (enel ámbito científico se hace uso de la prosa, pero en estas notas se hará usoreiteradamente de la afirmación-razón con fines pedagógicos). La primera con-siste en postular un razonamiento (afirmar alguna f. b. f) y al frente proponersu respectiva justificación (razón); la prosa, en cambio, consiste en narrar la

Capítulo 1. Sistemas formales 3

demostración paso a paso de forma continua. Al finalizar una demostración, sesuelen escribir los símbolos o , o la locución latina quod erat demonstran-dum (que abreviada se escribe QED y significa “lo que se quería demostrar”), olos tres puntos en forma de triángulo ∴, que significan “conclusión” o “por lotanto”.

Los teoremas no siempre se deducen partiendo de los axiomas, puesto queen algunos casos los teoremas poseen una estructura lógica en la que una f. b. f.se debe presentar para garantizar que la conclusión sea cierta; por ejemplo, enenunciados como “b se deriva de a”, “b se deduce a partir de a”, “b es conse-cuencia de a” y “si a entonces b” son equivalentes e implican que es necesariola presencia de a para que ocurra b; en este caso, a recibe el nombre de “hipó-tesis” mientras que b de “tesis”: el enunciado completo es en sí el teorema. Enestos casos se parte de la hipótesis para concluir la tesis. Cabe resaltar que notodo teorema tiene hipótesis (considere el teorema “

p2 es irracional”).

En el lenguaje de algunas teorías científicas se hace uso de la palabra “lema”para referirse a un teorema que sirve para demostrar otro teorema de mayorimportancia en dicha teoría, mientras que la palabra “corolario” corresponde aun teorema que se deduce a partir del teorema previo de una forma inmediata.

Por su parte, un “sistema formal” es un lenguaje formal dotado de un meca-nismo deductivo, que induce la creación de teorías científicas o el apoyo a estas.Es necesario agregar que no todos los teoremas son demostrables en un sistemaformal, lo que recibe el nombre de “principio de incompletitud de Gödel” [30]:algunos enunciados se expresan como “conjeturas” debido a que no han sidodemostrados, pero tampoco refutados. En la figura 1.1 se muestra la relaciónentre los conceptos hasta aquí mencionados.

Lema

Sistema formal Teoremas

CorolarioLenguaje formal Mecanismo deductivo

Alfabeto Reglas de formación Reglas de inferencia Axiomasf. b. f.

Signos primitivosSignos auxiliares

Definiciones

Figura 1.1 Sistemas formales y conceptos

4 Lógica y teoría de conjuntos

La construcción de sistemas formales propicia la creación de modelos quedescriben de una mejor forma los fenómenos que los mitos mencionados ante-riormente no logran explicar. A continuación se ilustran los conceptos mencio-nados hasta este punto por medio de ejemplos.

Ejemplo 1.1 Se define un alfabeto y una regla de formación:

1. Alfabeto:*,∆

2. Regla de formación: Toda cadena finita que inicie con ∗.

Bajo estas características se ha construido un lenguaje formal (alfabeto yregla de formación), mas no un sistema formal, puesto que se carece de unmecanismo de deducción. En las siguientes cadenas, se justificará al frente siestas cumplen o no con la condición de ser f. b. f.

a) ∗∆ Sí es una f. b. f., porque es finita e inicia en ∗.b) ∗;∆ No es una f. b. f., porque el signo ; no hace parte del alfabeto.c) ∆∆ A pesar de que es finita, no es f. b. f., porque no comienza en ∗.d) ∗∗ . . . Los puntos suspensivos indican que la cadena es infinita, por lo

que no constituye una f. b. f.

¿Cuántas f. b. f. se pueden obtener si las cadenas solo tienen dos elementosdel alfabeto? ¿Cuántas con tres elementos? La respuesta a la primera preguntaes dos: ∗∗ y ∗∆. Con tres elementos se consiguen cuatro f. b. f.: ∗∗∗, ∗∗∆, ∗∆∗,∗∆∆. Hacer el mismo proceso para determinar cuántas f. b. f. se obtienen si seutilizan cuatro y cinco signos del alfabeto y generalizar para diez elementos.

Ejemplo 1.2 Se cuenta con:

1. Alfabeto: , X , I

2. Regla de formación: Toda cadena finita de signos del alfabeto que empiecepor y ninguna otra.

3. Axiomas:i. I IX

ii. X II

4. Mecanismo deductivo:i. Cualquier signo de una cadena se puede duplicar.

ii. Si en una cadena existen los signos X X , estos se pueden reemplazarpor I.

Capítulo 1. Sistemas formales 5

iii. Si en una cadena existen los signos I I, estos pueden ser sustituidospor X siempre que la cadena resultante sea f. b. f.

iv. Si en una cadena aparecen los signos IX o , estos se pueden omi-tir siempre que la cadena resultante sea una f. b. f.

v. Si en una cadena aparece X , esta se puede sustituir por X.vi. No hay otra regla.

Bajo estas condiciones se obtiene un sistema formal, porque se cuenta con elalfabeto, las reglas de formación y el mecanismo de deducción. A continuaciónse obtendrá la cadena I I (la cual es f. b. f.) a partir de los dos axiomas dondese utilizan las diferentes reglas de inferencia definidas anteriormente.

Deducción Deducción1. I IX Axioma i 1. X II Axioma ii2. I Regla iv en 1 2. XI I Regla v en 13. I I Regla i en 2 3. X X Regla iii en 2

4. I Regla ii en 35. I I Regla i en 46. I I Regla iv en 5

En este caso, la f. b. f. I I recibe el nombre de “conclusión” o “teorema”, yaque se obtuvo a partir de otras f. b. f. Es necesario aclarar que la deducción noes lineal, es decir, no existe una forma única de obtener la conclusión, sino quepueden existir diferentes caminos para hacerlo, algunos de los cuales consistenen cambiar el orden de los pasos. Utilizando cualquiera de los axiomas, deducirlas f. b. f. siguientes: I I y X .

Deducción Deducción1. X II Axioma ii 1. X II Axioma ii2. XI I Regla v en 1 2. X II Regla i en 13. XI I I Regla i en 2 3. X II Regla iv en 24. X X I Regla iii en 3 4. XI I Regla v en 35. I I Regla ii en 4 5. X X Regla iii en 4

6. X X X X Regla i en 57. IX X Regla ii en 68. X Regla iv en 7

En este caso se utilizó el axioma ii. Hacer uso del axioma i para modificarlos razonamientos anteriores.

6 Lógica y teoría de conjuntos

Ejemplo 1.3 Consideremos el sistema formal:

1. Alfabeto: s, t2. Regla de formación: Toda cadena finita.3. Mecanismo deductivo:

i. Cualquier signo puede ser duplicado.ii. Si en una cadena aparecen los signos tt, estos pueden ser omitidos.

iii. Si en una cadena aparecen los signos sss, estos se pueden sustituirpor t.

iv. A la derecha de s se puede adicionar t.v. No hay otra regla.

Una conclusión se puede obtener a partir de otra f. b. f.; esta f. b. f. que sustentala conclusión se denomina “hipótesis” y se asume como verdadera para esteteorema (no necesariamente para otro) y debe utilizarse en la demostración.

1. Teorema 1: De la f. b. f. sstts, deducir t.

a) sstts . . . Hipótesisb) sss . . . Regla ii en 1c) t . . . Regla iii en 2

2. Teorema 2: De la f. b. f. sstts, deducir tt.

a) sstts . . . Hipótesisb) t . . . Teorema 1 en 1c) tt . . . Regla i en 2

3. Teorema 3: La cadena tst se deriva de s.a) s . . . Hipótesisb) ss . . . Regla i en 1c) ssss . . . Regla i en 2d) ts . . . Regla iii en 3e) tst . . . Regla iv en 4

Un teorema se convierte en una f. b. f. y por lo tanto se puede utilizar paradeducir otros teoremas. Por un razonamiento análogo, deducir tttt a partir desstts y ttst cuya hipótesis es s.

El juego de dominó es una combinación de 28 piezas en forma rectangular(desde lo plano), donde se colocan dos números que pueden variar entre 0 y 6.¿Por qué son 28? Porque si iniciamos con el 0 es posible construir 7 piezas: losdos 0, que se denotará (0,0), el 0 y el 1 (0,1), el 0 y el 2 (0,2), y así sucesivamentehasta el 0 y el 6 (0,6). Para el 1, se forman 6 piezas diferentes al anterior: (1,1),(1,2)... y así hasta el (1,6); la pieza (1,0) es la misma (0,1) por rotación. Al seguir

Capítulo 1. Sistemas formales 7

un proceso inductivo, resultan las parejas del número de la figura 1.2. ¿Cómoescribir un sistema formal para este juego tan tradicional?

0 1 2 3 4 5 6 Total0 (0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) 71 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) 62 (2,2) (2,3) (2,4) (2,5) (2,6) 53 (3,3) (3,4) (3,5) (3,6) 44 (4,4) (4,5) (4,6) 35 (5,5) (5,6) 26 (6,6) 1

28

Figura 1.2 Fichas del dominó

Ejemplo 1.4 Para resolver el anterior interrogante, se tiene que el alfabetolo constituyen las piezas de dicho juego; la regla de formación indica en estecaso cómo pueden ser utilizadas las piezas del dominó: es necesario saber quedos piezas de este juego se utilizan (para formar una cadena) siempre y cuandotengan un número en común y que dicho número no se vuelve a utilizar paraestas piezas. Con base en esto:

1. Alfabeto: las 28 piezas del dominó que se denotan (i, j), donde i y j soncualquier número del 0 al 6, i, j = 0,1, . . . ,6.

2. Regla de formación: Una cadena de dos elementos es f. b. f., siempre ycuando haya un número en común entre tales elementos; dicho númerose utiliza una y solo una vez.

(5, 3)(3, 6)(6, 1)Sí es f. b. f.

(1, 5)(5, 3)(3, 6)Sí es f. b. f.

No es f. b. f.

(5, 3)(3, 6)Sí es f. b. f.

Figura 1.3 Configuración del dominó como f. b. f.

8 Lógica y teoría de conjuntos

La cadena (5,3)(3,6) es bien formada porque el 3 es común y hace el puen-te entre las fichas (5,3) y (3,6); para que (5,3)(3,6) siga siendo una f. b. f. sele debe agregar otra pieza del dominó que tenga el 5 o el 6, pero no el 3;así, (5,3)(3,6)(6,1) es una cadena bien formada, al igual que (1,5)(5,3)(3,6), pero(5,3)(3,6)(3,1) no lo es. En la figura 1.3 se ejemplifica esto.

Antes de pasar a las reglas de inferencia, es necesario recordar que en eljuego los pares son aquellas piezas que tienen los mismos números; este nom-bre, en el juego, es una convención (no una exigencia). No obstante, en el juegose constituye en una definición:

3. Definición: Una pieza en la que los números son iguales se denomina“par”; se escribe (i, i) para i = 0,1, . . . ,6.

Las reglas de inferencia (mecanismo deductivo) consisten en las normas deljuego que establecen lo que está o no permitido para la práctica del mismo.Veamos:

4. Reglas de inferencia:a) A cada jugador le corresponden siete piezas.b) Inicia el juego quien tenga el par (6,6) o, en su defecto, el par si-

guiente de mayor a menor. El siguiente en turno es quien esté a laderecha de quien inició.

c) Es posible colocar dos pares simultáneamente, excepto al inicio.d) Cede el turno quien no tenga posibilidad de colocar una pieza en la

cadena que esté en la mesa.e) El juego termina por dos situaciones: cuando alguien queda sin pie-

zas o cuando, teniendo piezas, nadie puede colocarlas por la confi-guración de la cadena; en dicho caso, se hace la sumatoria de lospuntos, no de las fichas, que se tienen, y gana quien tenga la sumamenor.

f) Por convención entre los jugadores, se pueden anexar otras reglas.

Con estos elementos se construye el sistema formal que rige el juego deldominó; en este caso, se quitan las ambigüedades posibles que se puedan pre-sentar en el desarrollo del juego. Esta formalidad es la que se requiere para elmanejo de lenguajes de programación que se basan en estructuras lógicas. Enesto consisten los sistemas formales: en describir de forma precisa y objetiva unfenómeno físico, social, cultural o abstracto.

Capítulo 1. Sistemas formales 9

1.1 ProfundizaciónPara ampliar el estudio de este capítulo se invita al estudiante a que haga unalectura crítica sobre la verdad en matemáticas ([35], pág. 17; [29], pág. 61; [9],pág. 73) y sobre los teoremas de incompletitud ([9], pág. 175).

1.2 Ejercicios1. Busque la definición de cada una de las siguientes palabras: axioma, teore-

ma, proposición, lema, corolario, hipótesis, tesis, conjetura y demostración.Compare con lo estudiado en este capítulo.

2. ¿Cuál es la diferencia entre las palabras teorema, ley, propiedad y propo-sición?

3. Haga un rastreo sobre la conjetura de Goldbach y otras conjeturas para pre-sentarlo en clase; puede apoyarse en videos.

Para cada conjunto A que se presenta a continuación, determine si cumplelas condiciones de ser lenguaje formal y sistema formal, explicando claramentepor qué. Para los sistemas formales, haga las deducciones necesarias de losteoremas justificando adecuadamente.

4. Para el conjunto A se define:Regla de formación: Toda cadena finita que inicia en ∆ y termina en ∆.

5. Para el conjunto A se definen:a. Alfabeto: f,∗

b. Regla de formación: Toda cadena de cuatro signos del alfabeto que ini-cie en f.

Resuelva:a) ¿Cuáles de las siguientes cadenas son f. b. f.?

i) ffff ii) f∗∗iii) f;∗f iv) f∗∗∗

b) ¿Cuántas f. b. f. se pueden obtener bajo la regla de formación antesdefinida?

6. Por convención se asumirá N = 1,2,3,4, . . .. Sea A un conjunto con las si-guientes características:

a. Alfabeto: 1,−2,3,−5,0Signos auxiliares: +,×, ( , )

10 Lógica y teoría de conjuntos

b. Regla de formación: Toda cadena finita de signos del alfabeto cuya su-ma o multiplicación sea un número natural, donde 1+3 y 3+1 son f. b.f. diferentes.

Resuelva:a) Indique si las siguientes cadenas son f. b. f.

i) (−5)+0. ii) 1×1+ (−2). iii) 3+3+ (−2)+ (−2).iv) 0×0+0. v) 1+1+ (−5)× (−5). vi) 0× (−5)+ (−5)×0.

b) Determine el número de f. b. f. que se pueden encontrar si se tomansolo dos signos del alfabeto y explicite cuáles son.

7. Sea A el lenguaje formal definido comoa. Alfabeto: L1 = Λ,Θ,Ω y L2 = ♦

b. Reglas de formación:i. Si x está en L1, x es f. b. f.

ii. Si y está en L2, y es f. b. f.

iii. Si z está en L1 y w en L2, wz es f. b. f.

iv. Ninguna otra secuencia de signos es f. b. f.Resuelva:a) Construya seis f. b. f.

b) Justifique si las siguientes cadenas de signos son f. b. f.:i) ΛΩ ii) Ω iii) ♦♦iv) ♦ v) Λ♦Λ vi) ♦;Θvii) ♦Θ viii) Θ♦ ix) ΘΘ

c) ¿Cuántas f. b. f. se pueden construir con estas reglas de formación?

8. Consideremos un conjunto A con la siguiente estructura:a. Alfabeto: a,b, c

b. Regla de formación: Toda cadena finita de signos del alfabeto que iniciaen a y termina en c.

c. Reglas de inferencia:i. Todo signo del alfabeto puede ser triplicado.

ii. Cualquier cadena de dos signos puede ser omitida siempre y cuan-do la cadena resultante sea f. b. f.

iii. Las cadenas aa, bb y cc pueden reemplazarse por b, c y a, respec-tivamente, siempre que la cadena resultante sea f. b. f.

iv. No hay otra regla.