La ciencia de programar

Vista previa del material en texto

La ciencia de
programar
Jonatan Goméz Perdomo, Ph.D.
Arles Rodŕıguez, Ph.D.(c)
Camilo Cubides, Ph.D.(c)
´
Indice general J
Índice general I
Índice de tablas VII
Índice de figuras IX
1. Introducción 1
1.1. Generaciones de los computadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2. Lenguajes 5
2.1. Componentes del lenguaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2. Lenguajes de Programación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3. Clasificación de los lenguajes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4. Paradigmas de programación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3. Lógica Matemática 15
3.1. Lógica Proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.1. El lenguaje de la lógica proposicional . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.2. Precedencia de conectivos lógicos . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.3. Interpretaciones y clasificación de las fórmulas lógicas . . . . . . . . . . . . 19
3.1.3.1. Tautoloǵıas, contradicciones y contingencias . . . . . . . . . . . . 20
3.1.3.2. Tablas de verdad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.4. Argumentación y leyes lógicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
I
II ÍNDICE GENERAL
3.1.4.1. Argumentación lógica directa . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.4.2. Equivalencias Lógicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.4.3. Argumentación lógica indirecta por la contrarrećıproca . . . 22
3.1.4.4. Implicaciones Lógicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.4.5. Argumentación mediante implicaciones lógicas . . . . . . . . . . 25
3.2. Lógica de predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.1. Cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.2. Semántica de los cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.3. Leyes de De Morgan para cuantificadores . . . . . . . . . . . . . . . . . . . . . 28
3.2.4. Reglas de inferencia sobre fórmulas cuantificadas . . . . . . . . . . . . . . . 28
3.2.4.1. Particularización universal . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.4.2. Generalización universal . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.4.3. Particularización existencial . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.4.4. Generalización existencial . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.5. Lógica de predicados en programación . . . . . . . . . . . . . . . . . . . . . . . 30
3.3. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4. Teoŕıa de conjuntos 35
4.1. Conceptos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.1. Conjunto y elemento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.2. Especificación de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.2.1. Extensión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.2.2. Comprensión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.3. El conjunto vaćıo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.4. Representación de conjuntos mediante diagramas de Venn . . . . . . . . 37
4.1.4.1. Diagramas de Venn para 2 conjuntos . . . . . . . . . . . . . . . . . 37
4.1.4.2. Diagramas de Venn para 3 conjuntos . . . . . . . . . . . . . . . . . 38
4.1.5. Contenencia e igualdad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.1.6. Conjunto universal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2. Construcción de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2.1. Unión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
ÍNDICE GENERAL III
4.2.2. Intersección . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2.3. Complemento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.4. Diferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2.4.1. Diferencia simétrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2.5. Conjunto de partes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.6. Producto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2.6.1. Producto cartesiano generalizado . . . . . . . . . . . . . . . . . . . . 48
4.2.7. Cardinalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5. Introducción a los lenguajes de programación 53
5.1. Identificadores y variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2. Tipos de datos primitivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2.1. Enteros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2.1.1. Literales enteros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.2.2. Reales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.2.2.1. Densidad y distribución de los números reales de máquina . 57
5.2.2.2. Literales reales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2.3. Booleanos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.2.3.1. Literales booleanos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.2.4. Caracteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2.4.1. Literales carácter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.3. Operadores y expresiones aritméticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.3.1. Operadores aritméticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.3.2. Operadores de asignación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.3.3. Conversión de tipos de datos numéricos (typecasting) . . . . . . . . . . . . 71
5.3.4. Operadores lógicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.3.5. Operadores de igualdad y relacionales . . . . . . . . . . . . . . . . . . . . . . . . 73
5.3.6. Precedencia de operadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.4. Evaluación de secuencias de expresiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
IV ÍNDICE GENERAL
6. Relaciones y funciones 81
6.1. Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.1.1. Propiedades de las relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.1.2. Relaciones de orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.1.3. Relaciones de equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.2. Función parcial . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . 86
6.2.1. Propiedades de las funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.3. Extensión de una función parcial a una función total . . . . . . . . . . . . . . . . . . 89
6.4. Funciones importantes en computación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.5. Composición de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.5.1. Evaluación como composición de funciones . . . . . . . . . . . . . . . . . . . . 100
6.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
7. Funciones en programación y la estructura condicional 107
7.1. Compilación y ejecución de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.2. Funciones con más de un parámetro de entrada . . . . . . . . . . . . . . . . . . . . . . 112
7.3. La estructura de control condicional sı́ (if) . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3.1. El condicional if . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3.2. El operador condicional ?: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
7.3.3. El condicional if sin la sentencia else . . . . . . . . . . . . . . . . . . . . . . . 119
7.3.4. Estructuras if enlazadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.3.5. La estructura de conmutación (switch) . . . . . . . . . . . . . . . . . . . . . 124
7.4. Validación de datos usando condicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8. Flujos de entrada y salida 133
8.1. Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
8.2. La jerarqúıa del conjunto de los flujos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
8.3. Los flujos en C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
8.3.1. Ejemplo del uso de los flujos de entrada y salida estándares . . . . . . . 137
8.4. Flujos de entrada y salida desde y hacia archivos . . . . . . . . . . . . . . . . . . . . . 137
8.4.1. Uso de archivos como flujos de entrada . . . . . . . . . . . . . . . . . . . . . . . 138
ÍNDICE GENERAL V
8.4.2. Uso de archivos como flujos de salida . . . . . . . . . . . . . . . . . . . . . . . . 138
8.4.3. Cierre de los flujos desde y hacia archivos . . . . . . . . . . . . . . . . . . . . . 139
8.4.4. Ejemplo del uso de archivos como flujos de entrada y salida . . . . . . . 139
8.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
9. Funciones recursivas 143
9.1. Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
9.2. Ejemplos de problemas que pueden resolverse
recursivamente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
9.3. Teorema fundamental de la programación recursiva . . . . . . . . . . . . . . . . . . . 168
9.4. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
10.Estructuras de programación ćıclicas 171
10.1.La estructura de control de ciclos mientras (while) . . . . . . . . . . . . . . . . . . 171
10.2.La estructura de control de ciclos para (for) . . . . . . . . . . . . . . . . . . . . . . . 176
10.3.La estructura de control de ciclos hacer-mientras (do) . . . . . . . . . . . . . . . 181
10.4. Simulación de ciclos usando funciones recursivas . . . . . . . . . . . . . . . . . . . . . 187
10.5.Teorema fundamental de la programación estructurada . . . . . . . . . . . . . . . . 189
10.6.Validación de datos usando ciclos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
10.7.Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
11.Vectores o arreglos unidimensionales 195
11.1.Conceptos y notación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
11.1.1. El conjunto de los vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
11.2.Los arreglos o vectores en computación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
11.2.1. Funciones para utilizar arreglos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
11.2.1.1. Creación de arreglos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
11.2.1.2. Eliminación de arreglos . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
11.3.Arreglos y flujos de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
11.3.1. Ejemplos de funciones con arreglos . . . . . . . . . . . . . . . . . . . . . . . . . . 204
11.4.Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
12.Cadenas de caracteres 219
VI ÍNDICE GENERAL
12.1.Repaso del tipo carácter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
12.2.Cadenas (Strings) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
12.3.Funciones generales sobre cadenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
12.3.1. Creación de cadenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
12.3.2. Eliminación de cadenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
12.3.3. Funciones de lectura y de persistencia . . . . . . . . . . . . . . . . . . . . . . . . 224
12.3.4. Otras funciones importantes sobre cadenas . . . . . . . . . . . . . . . . . . . . 225
12.3.4.1. Longitud de una cadena . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
12.3.4.2. Copia de una cadena . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
12.3.4.3. De cadenas a números enteros o reales . . . . . . . . . . . . . . . . 227
12.3.5. Un ejemplo completo sobre manipulación de cadenas . . . . . . . . . . . . 227
12.4.Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
13.Matrices o arreglos bidimensionales 231
13.1.Conceptos y notación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
13.2.Definiciones alternativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
13.2.1. El conjunto de las matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
13.3.Las matrices en computación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
13.3.1. Funciones para utilizar matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
13.3.1.1. Creación de matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
13.3.1.2. Eliminación de matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
13.3.1.3. Matrices y flujos de datos . . . . . . . . . . . . . . . . . . . . . . . . . . 238
13.3.2. Ejemplos de funciones con matrices . . . . . . . . . . . . . . . . . . . . . . . . . 242
13.4.Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
Bibliograf́ıa 251
´
Indice de tablas
3.1. Prioridad de los conectivos lógicos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2. Equivalencias lógicas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3. Implicaciones lógicas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.1. Precedencia de los operadores en C++. . . . . . . . . . . . . . . . . . . . .. . . . . . . . 74
6.1. Pesos atómicos del Potasio (K), el Cloro (Cl) y el Ox́ıgeno (O). . . . . . . . . . 97
12.1. Longitud de cadena para nombres de archivos en distintos sistemas operativos.223
VII
VIII ÍNDICE DE TABLAS
´
Indice de figuras
2.1. Modelo matemático de la comunicación de Claude Elwood Shannon (1948) . 8
2.2. figure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3. Estructura general de un compilador. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4. Estructura general de un interprete. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.1. Representación del conjunto A = {1,2,3,4,8,®,™,_} mediante diagramas
de Venn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2. Representación del conjunto A ∪B mediante diagramas de Venn. . . . . . . . . 40
4.3. Representación del conjunto A∪B = {1,2,3,4,8,®,™,_} mediante diagra-
mas de Venn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.4. Representación del conjunto A ∩B mediante diagramas de Venn. . . . . . . . . 41
4.5. Representación del conjunto A∩B = {2,4,®,™} mediante diagramas de Venn. 42
4.6. Representación del conjunto A mediante diagramas de Venn. . . . . . . . . . . . 43
4.7. Representación del conjunto A = {1,3,5,6,7,9,0,©,´,_} mediante diagra-
mas de Venn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.8. Representación del conjunto A �B mediante diagramas de Venn. . . . . . . . . 44
4.9. Representación del conjunto A �B = {8} mediante diagramas de Venn. . . . . 44
4.10. Representación del conjunto B �A = {1,3,_} mediante diagramas de Venn. 45
4.11. Representación del conjunto A△B mediante diagramas de Venn. . . . . . . . . 46
4.12. Representación del conjunto A△B = {8,1,3,_} mediante diagramas de Venn. 46
6.1. Representación de la relación R = �(0,®), (0,´), (2,´), (2,©)� mediante
diagramas Sagitales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
IX
X ÍNDICE DE FIGURAS
6.2. Representación de la relación R = �(®,©), (©,®), (™,´), (´,™)� mediante
diagramas Sagitales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.3. Representación de la función f = �(0,©), (1,©), (4,™)� mediante diagramas
Sagitales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.4. Representación de la relación f ′ = �(0,®), (1,®), (2,™), (1,´)� mediante
diagramas Sagitales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.5. Representación de la función inyectiva f = �(0,´), (2,®)� mediante diagra-
mas Sagitales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.6. Representación de la función sobreyectiva f = �(0,®), (1,™), (2,´), (4,®)�
mediante diagramas Sagitales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.7. Representación de la función total f = �(0,´), (1,©), (2,®), (3,´), (4,®)�
mediante diagramas Sagitales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.8. Representación de la función biyectiva f = �(0,™), (1,©), (2,´), (3,®)�
mediante diagramas Sagitales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.9. Representación de la función identidad id
A
. . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.10. Representación mediante diagramas Sagitales de la composición de las fun-
ciones f y g, f ○ g = �(1, a), (2, d), (3, c), (4, c), (6, c)�. . . . . . . . . . . . . . . . . . 96
6.11. Representación mediante diagramas de la función f○g = �(1, a), (2, d), (3, c), (4, c), (6, c)�. 96
Caṕıtulo1
Introducción
1.1. Generaciones de los computadores
Primera generación de los computadores (1946 − 1958):
• Programación en lenguaje de máquina (el programa se escribe en código bina-
rio).
• La tecnoloǵıa electrónica era a base de bulbos o tubos de vaćıo y válvulas.
• Desprend́ıan bastante calor y teńıan una vida relativamente corta.
• Máquinas grandes y pesadas.
• Alto consumo de enerǵıa. El voltaje de los tubos era de 300V y la posibilidad
de fundirse era grande.
• Almacenamiento de la información en cilindros magnéticos para almacenar in-
formación e instrucciones internas.
• La reprogramación se hacia intercambiando el cableado.
• Continúas fallas o interrupciones en el proceso.
• Requeŕıan sistemas auxiliares de aire acondicionado especial.
• Alto costo.
• Uso de tarjetas perforadas para suministrar datos de programas.
Las computadoras de esa generación fueron:
• 1947 ENIAC. Primera computadora digital electrónica de la historia.
• 1949 EDVAC. Primera computadora programable.
• 1951 UNIVAC I. Primera computadora comercial.
• 1953 IBM 701. Se usaban tarjetas perforadas para introducir los datos.
• 1954 IBM desarrolló otros modelos que usaban tambor magnético.
1
2 CAPÍTULO 1. INTRODUCCIÓN
• Z1 (Alemana).
• Mark II.
Segunda generación de los computadores (1959 − 1964):
• Comunicación mediante el uso de lenguajes de alto nivel.
• Uso de los transistores construidos en base al uso de un trozo de semiconduc-
tor que reemplazaron a los bulbos en los circuitos de los computadores. Fue-
ron inventados por John Bardeen, Walter Houser Brattain y William Bradford
Shockley.
• Tamaño más reducido que sus antecesoras de la primera generación.
• Consumı́an menos electricidad y produćıan menos calor que sus antecesoras.
• Aumento en la velocidad de las operaciones que ya no se mide en segundos sino
en microsegundos.
• Costo más bajo que el de sus antecesoras.
• Almacenamiento en cintas y discos magnéticos.
• Aparece gran cantidad de empresas dedicadas a la fabricación de los compu-
tadores.
• Programación con cintas perforadas y otras por medio de un cableado en un
tablero.
• La transferencia de información de una computadora a otra requeŕıa un mı́nimo
esfuerzo.
• Uso de impresoras para visualizar los resultados obtenidos a partir de los cálcu-
los hechos.
Las computadoras de esa generación fueron:
• Philco 212.
• UNIVAC M460.
• Control Data Corporaions serie 1604.
• Control Data Corporaions serie 3000.
• IBM 7090.
• NCR 315.
• Burroughs serie 5000.
• ATLAS.
Tercera generación de los computadores (1965 − 1971):
• Circuitos integrados desarrollado en 1958 por Jack Kilbry.
• Miniaturización y reunión de centenares de elementos en una placa de silicio o
(chip).
1.1. GENERACIONES DE LOS COMPUTADORES 3
• Menor consumo de enerǵıa.
• Reducción de espacio utilizado.
• Aumento de fiabilidad y flexibilidad.
• Aumenta la capacidad de almacenamiento y se reduce el tiempo de ejecución.
• Disponibilidad de gran cantidad de lenguajes de programación de alto nivel.
• Compatibilidad para compartir software entre diversos equipos.
• Construcción de computadoras en serie.
• Teleproceso.
• Multiprogramación.
• Tiempo compartido.
• Aparición de periféricos.
• Aparición de aplicaciones.
• Aparición del sistema operativo llamado OS.
• Aparición de la mini computadora.
Las computadoras de esa generación fueron:
• IBM 360.
• Control Data Corporaions serie 6000.
• Control Data Corporaions serie 6600. Considerada la más rápida de su época.
• IBM 370.
Cuarta generación de los computadores (1972 − 1981):
• Microprocesador: un único circuito integrado en el que se reúnen los elementos
básicos de la máquina desarrollado por Intel Corporation (1971).
• Se minimiza el tamaño de los circuitos.
• Aumenta la capacidad de almacenamiento.
• Reemplazo de las memorias con núcleos magnéticos, por las de chips de silicio.
• Colocación de muchos componentes electrónicos en un sólo chip.
• Se aumenta la velocidad de computo.
• Reducción significativa de los costos de los computadores.• Popularización del uso de los computadores.
• Steve Woziniak y Steve Jobs inventan la primera microcomputadora de uso
masivo, fundadores de APPLE (1976) .
• Sistemas de tratamiento de base de datos.
• Generalización de las aplicaciones.
• Multiproceso.
4 CAPÍTULO 1. INTRODUCCIÓN
Quinta generación de los computadores (1982 − 1989):
• Japón lanzó en 1983 el llamado“programa de la quinta generación de compu-
tadoras”.
• Traductores de lenguajes.
• Creación de la primera supercomputadora con capacidad de proceso paralelo,
diseñada por Seymouy Cray (1982).
• Fuerte aplicación de la inteligencia artificial: sistemas expertos, redes neurona-
les, teoŕıa del caos, programación heuŕıstica, algoritmos genéticos.
• Fibras ópticas.
• Telecomunicaciones.
• DVD.
• Uso del ratón (mouse).
• Robots con capacidad de movimiento.
• Juegos.
• Reconocimientos de formas tridimensionales, voz e imágenes.
Sexta generación de los computadores (1990−actualidad):
• Arquitecturas combinadas Paralelo / Vectorial.
• Masificación del uso de redes de área mundial (Wide Area Network, WAN).
• Comunicación a través de fibras ópticas y satélites.
• 1997- El Pentium II
• 1999- El Pentium III
• 2001- el Pentium 4
• Intel Core i3
• Intel Core i5
• Intel Core i7
• AMD Phenom II
• Tablets y Smartphones.
Caṕıtulo2
Lenguajes
El lenguaje ha acompañado al hombre desde el inicio de sus tiempos, ha crecido y
evolucionado con éste y de la misma manera el hombre transforma el lenguaje. Se define
lenguaje como un conjunto de señales articuladas que dan a entender algo[de la Len-
gua Española n.d.], y esta definición relaciona el concepto de lenguaje con el acto de la
comunicación. “Dar a entender algo” implica que existe algo que se quiere transmitir, y
que debe llevarse a cabo exitosamente.
La creación y transformación de los lenguajes ha propiciado el aprendizaje, con esto
la generación continua de conocimiento, el permanente y acelerado intercambio de infor-
mación y el actual desarrollo de las tecnoloǵıas. Sin el lenguaje no se podŕıa hablar hoy
en d́ıa de civilizaciones, de sociedades complejas, de la expresión y de la ciencia[Domenec
Campillo Valero 2005].
Existen dos enfoques frente a la relación del hombre con el lenguaje: el de creador, y el
de usuario.
El lenguaje es una forma de adaptación del ser humano, es una respuesta al ambiente,
al entorno. El lenguaje ha evolucionado con el hombre, incluso existen teoŕıas y estudios
enfocados al análisis de la evolución del hombre con el lenguaje, que atribuyen los cambios
del cerebro a presiones selectivas, a necesidades o al instinto de supervivencia[ThinkQuest
2000].
Aunque existen otras especies de las cuales se dice que “comparten un lenguaje”, es el
lenguaje verbal el que realmente diferencia a la raza humana de especies animales con una
capacidad cerebral similar -cuyos medios de comunicación son sistemas de transmisión de
información como los delfines o los chimpancés[Domenec Campillo Valero 2005].
Existen diferentes teoŕıas acerca de la evolución del lenguaje: las vocalistas y las espećıfi-
cas, las cuales difieren en la aceptación de un factor genético que propiciara la evolución
del lenguaje. Las hipótesis que se han planteado los vocalistas afirman que la evolución
de la capacidad vocal de los simios se dio debido a una mutación genética que permi-
tió que los sonidos emitidos fueran susceptibles de combinación, formando aśı lenguajes
de comunicación[O. 2008].
5
6 CAPÍTULO 2. LENGUAJES
Las hipótesis espećıficas proponen e identifican el papel de la cultura como determinante
para la aparición del lenguaje, además del aumento de la capacidad craneal y el desarrollo
de la inteligencia. También se debe tener en cuenta que la base genética de los seres
humanos precede a la emergencia del lenguaje, de manera que el lenguaje evolucionó para
encajar en la estructura cerebral. Sin embargo las convenciones culturales cambian mucho
más rápido que los genes, de manera que se le atribuye a la cultura, la generación y
desarrollo del lenguaje.
La fusión de estas dos teoŕıas da lugar a un escenario donde el simio evolucionó y ad-
quirió caracteŕısticas fisiológicas, que unidas a la interacción con otros seres le permitieron
expresarse de forma verbal.
Desde esta perspectiva, el desarrollo de la comunicación y el lenguaje en la antigüedad
inició, porque el ser humano se vio forzado a interactuar con otros, porque tuvo la necesidad
de expresar y transmitir: como el cazador que quiso dar a conocer a sus compañeros dónde
estaba la presa, o cómo estaban las condiciones del clima, o el recolector que deb́ıa informar
del encuentro de una fruta venenosa, situaciones que hicieron que el hombre tuviera que
valerse de gestos, señas y sonidos para comunicarse con otros.
Los primeros homı́nidos no eran f́ısicamente aptos para hablar, debido a que sus cuerdas
vocales no estaban completamente desarrolladas. Según estudios de fósiles de diferentes
especies de homı́nidos, el Homo-habilis fue el homı́nido precursor del lenguaje. En los
cráneos del Homo-habilis se encontró la presencia de las áreas cerebrales asociadas a la
capacidad lingǘıstica (áreas de Broca y Wernicke) y también signos de que la laringe
hab́ıa iniciado su descenso. Los sucesores de esta especie potenciaron estas caracteŕısticas,
pero se destaca al Homo-sapiens como el que tuvo la capacidad para el lenguaje de doble
articulación.[Domenec Campillo Valero 2005]
El lenguaje requirió entonces de unos factores para poder desarrollarse: tamaño cerebral
adecuado, canales apropiados e intensa interacción social [Segarra 2010].
Los lingüistas concuerdan en que el cambio cultural se produjo en la prehistoria y se
dio una única vez. Sin embargo, actualmente existen muchas lenguas e idiomas, lo cual
demuestra que después de que surgió el lenguaje - siendo este único o múltiple- se dieron
cambios muy rápidos por lo que actualmente no es posible conocer sus fonemas, gramática
o léxico.
Históricamente, el hombre ha propiciado la evolución del lenguaje, pero hablando desde
la temporalidad de cada hombre, es éste el que adquiere el lenguaje, es éste el que por medio
de la repetición, la imitación y la estimulación aprende las convenciones que le permitirán
interactuar y comunicarse con su entorno y especialmente con otros hombres.[Domingo
1990] El hombre encuentra en el lenguaje el medio para interactuar con el universo, con
su realidad. Todo ser humano es capaz de crear y desarrollar sistemas de lenguaje. El ser
humano es la única especie capaz de articular las palabras1 y las ideas que se generan en
el cerebro casi inmediatamente.
1El ser humano tiene un lenguaje de doble articulación: Se unen los fonemas en palabras y las palabras
en frases.
7
El ser humano tiene una capacidad muy amplia con respecto a los fonemas que puede
emitir, sin embargo, no todos los idiomas emplean todos los fonemas, e incluso dependiendo
de la cultura, hay personas a las que no les es posible pronunciar ciertos sonidos. Se podŕıa
decir que hay una biblioteca universal de donde las civilizaciones empezaron a formar y
establecer los lenguajes como se conocen hoy en d́ıa.
“Mientras la necesidad aumenta, el vocabulario se expande, al combinar
viejas palabras o inventar nuevas, y las reglas se pueden volver más y más
detalladas. En algún punto, mucho tiempo atrás, el vocabulario y la gramática
habŕıan aparentemente “despegado”: todos los lenguajes hoy en d́ıa parecen
ser iguales en su capacidad de expresar los matices y complejidades de la vida
humana.”[Boeree 2007]
El lenguaje articulado opera con palabras integradas con sonidos que remiten a con-
ceptos, y lo hace con signos lingǘısticos. El signo tiene tanto significado como significante
(Ferdinand de Saussure), y sustituye la idea o concepto para que ésta pueda ser percep-
tible, pero no tiene ninguna relación con aquello que evoca, de manera que el signo es
arbitrario.Los signos lingǘısticos son fijos, limitados, pero su combinación, inmersa en las
convenciones sociales, permite infinitos significados conformando aśı la lengua.
Se podŕıa concebir al lenguaje como un medio descriptivo y referencial, pero la verdad
es que no es objetivo de la realidad en lo más mı́nimo. El lenguaje es circunstancial,
cambiante y relativo.
Las palabras no tienen un significado inherente, por lo tanto su significado surge de la
relación con las palabras que la acompañan y en teoŕıa, cada palabra es libre de significar
lo que sea.
Para Ferdinand de Saussure, el lenguaje es una red compleja de enunciados que se
entremezclan para formar significados, todo es eqúıvoco, ambiguo y transformable.[Vicente
2012]
El lenguaje consta de elementos iguales: el espacio, el punto, la coma y las letras y aún
aśı es ilimitado.
Como se mencionaba anteriormente, la comunicación es un proceso mediante el cual
se transmite la información. Para que haya comunicación, debe haber una coincidencia
en el tipo de lenguaje, es decir que al codificar la información se hace siguiendo unos
lineamientos o reglas preestablecidas por un sistema con el cual está familiarizado tanto
emisor como receptor. El emisor codifica, el receptor decodifica[Pelayo & Cabrera 2001].
Los elementos de la comunicación son:
• Fuente de información: Genera la información que será transmitida.
• Mensaje: Dato o conjunto de datos a transmitir. Surge de la selección de posibilidades
en un conjunto de combinaciones simbólicas posibles.
• Emisor: Codifica el mensaje.
8 CAPÍTULO 2. LENGUAJES
• Señal: Signo o śımbolo de sistema convencional.
• Canal: Medio por el cual se transmite el mensaje codificado.
• Fuente de ruido: interferencia que distorsiona la señal y puede cambiar el mensaje.
• Receptor: Decodifica para poder ser recibido por el destino
• Destino: Ente al que se dirige el mensaje.
Fuente de
información
Emisor Canal Receptor
Destino
Fuente de
ruido
Mensaje
original
Señal
Señal
recibida
Mensaje
final
Figura 2.1. Modelo matemático de la comunicación de Claude Elwood Shannon (1948)
2.1. Componentes del lenguaje
En la anterior sección se vio el lenguaje desde un punto de vista humano, sin embargo
esos conceptos ....
de aqui en adelante le concepto de lenguajes se definirá de la siguiente manera sistema-
tica
Definición. Un lenguaje está formado por tres elementos (el léxico, la sintaxis y la
semántica), que permiten expresar y comunicar información entre entes, ya sean personas,
animales, computadores, etc.
Léxico: El léxico de un lenguaje lo conforman las unidades mı́nimas con significado com-
pleto. A cada uno de estas unidades mı́nimas con significado se le conoce como
lexema2. Por ejemplo, en el español, las palabras y los śımbolos de puntuación (que
son usados para formar frases, oraciones y párrafos) conforman el léxico. A tales
lexemas se les asocia un significado preciso en términos de las frases construidas con
ellos.
Es el conjunto de palabras y signos de puntuación que componen una lengua. Las
palabras generalmente se componen de dos unidades mı́nimas: lexema y morfema,
2La palabra lexema usada en este libro tiene un significado similar (pero no igual) a la que se usa
en lingǘıstica. En lingǘıstica las palabras móvil y móviles se derivan del mismo lexema (móvil), es decir,
son el mismo lexema (por las relaciones semánticas propias del español), solamente que tienen diferente
gramema (", -es).
2.1. COMPONENTES DEL LENGUAJE 9
las cuales aportan significado léxico y gramatical, respectivamente. Una familia de
palabras comparte un mismo lexema:
Arte, Artista, Art́ıstico, Artesanal.[Gramáticas.net 2013]
Sintaxis: La sintaxis de un lenguaje explica la forma en que se pueden construir frases en
el lenguaje a partir del léxico. Usualmente la sintaxis se presenta como una colección
de reglas de reescritura que se definen con una gramática. Éstas son reglas que
indican como unos śımbolos de la gramática pueden ser reescritos por otros śımbolos
de la gramática o por lexemas. La idea es que al final del proceso de reescritura
sólo se tengan lexemas. Por ejemplo en español una frase se puede reescribir como
un sujeto y un predicado, a su vez un sujeto se puede reescribir como un art́ıculo,
un sustantivo y un adjetivo, finalmente un sustantivo puede ser reescrito como la
palabra perro.
La sintaxis se presenta como una colección de reglas que indican cómo unos śımbolos
pueden ser reescritos o descompuestos hasta tener sólo lexemas.
Ejemplo. Una frase se reescribe como un sujeto y un predicado, un sujeto se re-
escribe como art́ıculo y sustantivo, un predicado se reescribe como un sujeto, un
adverbio y un adjetivo, aśı
Figura 2.2. figure
La derivación de la frase “El profesor hará un examen muy difı́cil ” se puede
modelar mediante un árbol de derivación como el siguiente.
Semántica: La semántica de un lenguaje define la forma en que se le asocia significado
(sentido) a las frases construidas mediante la gramática. En español la semántica
no es fácil de definir ya que intervienen elementos muy elaborados que han sido
construidos de manera natural a través del tiempo (cada objeto/idea conocido(a)
por el ser humano esta asociado(a) con una palabra). El sentido de una frase o una
oración en español depende mucho del contexto en el que se escribe o dice la frase y
del posible conjunto de significados el cual es muy grande. Este hecho es lo que hace
dif́ıcil, para los computadores actuales, trabajar directamente en lenguaje natural.
10 CAPÍTULO 2. LENGUAJES
�Frase�
�Sujeto�
�Art́ıculo�
El
�Sustantivo�
profesor
�Predicado�
�Verbo�
hará
�Complemento�
�Sujeto�
�Art́ıculo�
un
�Sustantivo�
examen
�Adverbio�
muy
�Adjetivo�
difı́cil
2.2. Lenguajes de Programación
Para ordenarle a una máquina de computo (computador) que ejecute cierto procedi-
miento o realice un calculo predeterminado, se dispone de los lenguajes de programación,
los cuales son definidos a partir del lenguaje matemático, por eso los computadores hacen
exactamente lo que se les dice, no lo que se quiere que hagan. De esta manera, en progra-
mación se tiene un lenguaje bien definido donde los significados de las frases son únicos
(no ambiguos). Esto exige que el programador exprese de forma precisa lo que desea hacer.
Al principio programar era muy complicado ya que se programa directamente en el
hardware: se requeŕıa que los programas se escribieran cableando ciertas compuertas de la
máquina. Un error en el cableado, es decir un error en el programa era dif́ıcil de detectar.
Posteriormente el hombre construyó máquinas de cálculo para tareas muy espećıficas
como investigación y militares, usando dispositivos electro-mecánicos como relés y tubos
de vaćıo. Se programaba revisando las salidas de los estados de los tubos (encendido ó 1 y
apagado ó 0). A estos computadores soĺıan acercarseles insectos en busca de calor dañando
los tubos. De alĺı proviene el termino “bug” (bicho de programación) conocido actualmente
en programación como un defecto en el programa.
Para reducir este problema, se intento separar el programa de la parte f́ısica, es aśı como
llegaron las tarjetas perforadas inspiradas en las máquinas telares de la época. De esta
forma, los programas eran representados por huecos en las tarjetas, y la máquina realizaba
lecturas de aquellos huecos en un orden espećıfico. De desordenarse las tarjetas el programa
dejaŕıa de funcionar.
Estos computadores dieron paso a los elementos transistorizados. Las máquinas de
cómputo de esta generación teńıan pocas facilidades de programación. La comunicación
se establećıa en lenguaje de máquina, que como su nombre lo indica, depend́ıan de la
máquina, lo que hacia poco portable al programa.
A continuación se presentan una clasificación de los lenguaje por su nivel de abstracción.
2.3. CLASIFICACIÓN DE LOS LENGUAJES 11
2.3. Clasificación de los lenguajesDe acuerdo a la complejidad de la sintaxis y la abstracción necesaria los lenguajes de
programación se pueden se clasifican en las siguientes categoŕıas:
Lenguajes de máquina o de bajo nivel. Es el único lenguaje que entiende el hardwa-
re (máquina) y usa exclusivamente el sistema binario (ceros y unos). Este lenguaje
es espećıfico para cada hardware (procesador, dispositivos, periféricos, etc.).
El programa (tanto códigos de instrucción como datos) es almacenado en memoria.
Ejemplo. La estructura de una instrucción en lenguaje máquina es la siguiente:
CODIGO ARGUMENTO(S)
0010 00011010
1010 10111000
0110 11010001
Lenguaje ensamblador o de intermedio nivel. El lenguaje ensamblador surgió de la
necesidad de desarrollar un lenguaje de nivel mayor, que fuese más comprensible
que el de la máquina pero que permitiera acceder a los detalles de éstas. Por es-
ta razón se desarrolló una forma de construir un lenguaje intermedio que empleara
mnemónicos (palabras cortas escritas con caracteres alfanuméricos), para codificar
las operaciones. Los datos y/o direcciones son codificados generalmente como núme-
ros en un sistema hexadecimal. Generalmente es espećıfico (aunque no único) para
cada lenguaje de máquina. Entre los mnemónicos t́ıpicos se tienen
ADD: Utilizado para sumar dos direcciones de memoria.
SUB: Utilizado para restar dos direcciones de memoria.
MUL: Utilizado para multiplicar dos direcciones de memoria.
MOV: Utilizado para mover un dato de un registro de la memoria en otro.
CALL: Utilizado para ejecutar una subrutina.
INT: Utilizado para invocar una interrupción.
Ejemplo. La estructura de una instrucción en este lenguaje es la siguiente:
MNEMONICO ARGUMENTO(S)
ADD R1, F4
MOV F4, C2
SUB AX, AX
MOV AX, 18D
SUB AX, 18D
INT 20h
12 CAPÍTULO 2. LENGUAJES
Un Ensamblador es un software, generalmente escrito en lenguaje de máquina, que es
capaz de traducir de lenguaje ensamblador a lenguaje de máquina. Con este lenguaje
se dio un salto fundamental, donde se logró separar el programa de la máquina
empleando los conceptos de máquina de Turing y la arquitectura de Von Neumann.
Almacenando el programa en memoria y empleando el hardware como elemento de
control.
Lo anterior dio origen a los sistemas operativos, logrando que la máquina completa
pudiera controlar otro programa.
Lenguajes de alto nivel. Aunque útil, el lenguaje ensamblador, es aún muy dif́ıcil de
entender, por eso se planteó la idea de generar un lenguaje más parecido al lenguaje
natural que tiene facilidades de aprendizaje, lectura, escritura, corrección, transfor-
mación y conversión.
Estos lenguajes están basados en una estructura gramatical para codificar estructuras
de control y/o instrucciones. Cuenta con un conjunto de palabras reservadas (escritas
en lenguaje natural).
Adicionalmente éstos permiten el uso de śımbolos aritméticos y relacionales para
describir cálculos matemáticos, y generalmente representan las cantidades numéricas
mediante sistema decimal.
Ejemplo. La estructura de un programa escrito en un lenguaje de alto nivel tal
como C++ es la siguiente:
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
cout << "Hola mundo" << endl;
return EXIT_SUCCESS;
}
Gracias a su estructura gramatical, estos lenguajes permiten al programador olvidar
el direccionamiento de memoria (donde cargar datos y/o instrucciones en la memo-
ria), ya que esto se realiza automáticamente por parte de un programa compilador
o interprete.
Los programas fuente escritos en lenguajes de alto nivel se compilan y a partir de
estos se generara un programa objeto de código de máquina (Figura 2.3). El lenguaje
de programación C entra en la clase de lenguajes compilados.
Otra forma de tratar los programas fuente es utilizando interpretes, en estos se
toma instrucción por instrucción, estas se traducen a un código intermedio similar
al Ensamblador y de hay se traducen a código de máquina, usualmente utilizando
un programa que depende de la plataforma y que se suele denominar La maquina
2.3. CLASIFICACIÓN DE LOS LENGUAJES 13
Programa
fuente
Compilador
Programa
objeto
Lenguaje de
alto nivel
Lenguaje de
máquina
Figura 2.3. Estructura general de un compilador.
virtual (Figura 2.4). Para Algunos lenguajes interpretados tales como Java, el código
ensamblador que se obtiene al traducir el programa fuente se llama Bytecode.
Programa
fuente
Interprete
Máquina
virtual
Programa
objeto
Lenguaje de
alto nivel
Ensamblador
Bytecode
Lenguaje
de
máquina
Compilación
ĺınea a ĺınea
Figura 2.4. Estructura general de un interprete.
Lenguajes de muy alto nivel. También conocidos como lenguajes declarativos. Su defi-
nición es más complicada que la de los anteriores. Se trata esencialmente de lenguajes
taquigráficos que usan macroinstrucciones (se escribe más con menos). Cuando una
operación que requiere de cientos de ĺıneas en un lenguaje de alto nivel, en un len-
guaje de muy alto nivel se requiere t́ıpicamente de unas cinco a diez ĺıneas. Entre las
caracteŕısticas de estos lenguajes está el no uso de procedimientos. En los lenguajes
de procedimientos se dice con detalle a la computadora las tareas a realizarse. En
estos lenguajes se define solamente lo que se necesita computar, es decir, se enfatizan
el qué hacer, en lugar del cómo hacerlo. Para esto, el compilador se encarga de los
detalles relativos a cómo obtener el conjunto completo o parcial, y correcto de las
soluciones.
Ejemplo. Entre tareas t́ıpicas de estos lenguajes se pueden:
• Generar reportes sobre un criterio especifico sobre un conjunto de datos.
– Listar todas la personas que nacieron después de 1990.
• Encontrar las soluciones a una consulta realizada a un sistema con respecto a
una base de conocimientos.
– Pedro es padre de Jesus.
– Maŕıa es madre de Jesus.
– ¿Quién es progenitor de Jesus?.
14 CAPÍTULO 2. LENGUAJES
Los lenguajes de muy alto nivel son fáciles de leer, comprender y programar, no
requieren altos conocimientos de arquitecturas computacionales, esto los hace alta-
mente transportables.
El principal inconveniente de estos lenguajes es que no hacen uso eficiente de los
recursos computacionales.
Lenguajes naturales. Se denominan aśı por su acercamiento a la escritura de los len-
guajes humanos (inglés, frances, español, etc). El uso de un lenguaje natural con una
base de conocimientos produce un sistema basado en el conocimiento. Una clase de
estos sistemas son los Sistemas Expertos, que son base de la Inteligencia Artificial.
Éstos están todav́ıa en su infancia, y actualmente puede considerarse que están más
cerca de los lenguajes de muy alto nivel que de los lenguajes humanos.
Los lenguajes de alto y muy alto nivel se clasifican por el modelo conceptual que desa-
rrollan. En la siguiente se presenta esta clasificación.
2.4. Paradigmas de programación
Existen muchos lenguajes de programación de alto nivel con sus diferentes versiones.
Por esta razón es dif́ıcil su tipificación, pero una clasificación muy extendida desde el punto
de vista de su forma de codificación y la filosof́ıa de su creación es la siguiente:
Lenguajes de programación imperativos o estructurados. Describe la programa-
ción en términos del estado de la memoria del programa y sentencias que cambian
dicho estado. Los programas imperativos son un conjunto de instrucciones que le
indican al computador cómo realizar una tarea. La implementación de hardware de
la mayoŕıa de computadores es imperativa ya que el hardware está diseñado para
ejecutar código de máquina que es imperativo. Ejemplos: Cobol, Pascal, Fortran, C,
Ada, MathLab, SciLab.
Lenguajes de programación declarativos. Basado en la utilización de predicados
lógicos (lógicos) o funciones matemáticas (funcionales), su objetivo es conseguir len-
guajes expresivos en los que no sea necesario especificar cómo resolver el problema
(programación convencional imperativa), sino qué problemase desea resolver. Los
interpretes de los lenguajes declarativos tienen incorporado un motor de inferencia
genérico que resuelve los problemas a partir de su especificación. Ejemplos: Lisp, ML,
Haskell, Maude, Prolog, SQL.
Lenguajes de programación orientados a objetos. Usa los objetos como instancias
de clases y sus interacciones para diseñar aplicaciones y programas. Está basado
en varias técnicas, incluyendo abstracción, herencia, modularidad, polimorfismo y
encapsulamiento. Usualmente los lenguajes orientados a objetos se usan en com-
binación con la programación imperativa. Ejemplos: Smalltalk, C++, Java, Python,
R.
Caṕıtulo3
Lógica Matemática
3.1. Lógica Proposicional
Definición. Una proposición cerrada o simplemente proposición es un juicio, afirmación
o enunciado el cual se puede calificar como verdadero o falso, pero no ambos simultánea-
mente.
• No es necesario saber de antemano śı es verdadero o falso.
• Pero con certeza el enunciado debe poseer algún valor fijo que lo califique.
• No debe haber incertidumbre acerca de śı se posee un valor que lo califique.
Una proposición consta básicamente de tres partes:
• Un sujeto: del cual se dice algo o que él hace algo.
• Un verbo: que indica un estado o una acción que realiza el sujeto.
• El complemento: que describe o aclara el estado o acción que realiza el sujeto.
Ejemplos. Los siguientes enunciados son ejemplos de proposiciones
Ejemplos. Los siguientes enunciados son ejemplos de proposiciones
p: El jugador está en la casilla [2,2].
q: El archipiélago de San Andrés, Providencia y Santa Catalina pertenece a Colombia.
r: El perro corre velozmente por la pradera jugando con la pelota azul y verde.
s: 2 + 2 ≠ 4.
t: 3
√
125 = 5.
u: Existe vida alienigena inteligente.
v: El universo tiene una longitud infinita.
w: Está lloviendo.
x: Mañana es sábado.
15
16 CAPÍTULO 3. LÓGICA MATEMÁTICA
Ejemplos. Los siguientes enunciados son ejemplos que no son proposiciones
• ¿Vamos mañana a cine?; ¿Hacemos quiz?. (interrogaciones)
• ¡Ah, cuánta mentira hay en esos argumentos!; ¡No te vayas!. (exclamaciones, deseos)
• No te aprendas la tablas de memoria; No te metas con ese muchacho; Cállate. (con-
sejos, mandatos)
• El lindo y hermoso perro de Maŕıa Antonieta; El ronroneo de los gatos. (no son
afirmaciones que puedan valorarse)
• x + 9 = 21 (no hay un sujeto fijo predeterminado, éste se denomina un enunciado
abierto)
• Mañana lloverá (hay incertidumbre acerca del valor que califica el enunciado, no
tiene una calificación fija y precisa)
3.1.1. El lenguaje de la lógica proposicional
En la lógica proposicional, el léxico esta definido por tres elementos: los śımbolos o
letras proposicionales, los conectivos lógicos y los paréntesis.
Definición. El léxico de la lógica proposicional se compone de tres tipos de lexemas:
śımbolos y/o letras proposicionales: ⊥,�, p, q, r, s, t, p0, p1, . . .
conectivos lógicos: ¬,∨,∧,→,↔
śımbolos auxiliares: (, )
El śımbolo proposicional ⊥ (que se lee “bottom”) es usado para representar una propo-
sición genérica que su significado es siempre falso1, mientras que � (que se lee “top”) es
usado para representar una proposición genérica que su significado es siempre verdadero2.
Las letras proposicionales p, q, r, s, t, p0, p1, . . . son usadas para representar proposicio-
nes, por lo tanto el significado de una letra proposicional es el significado que tiene la
proposición que dicha letra representa.
Los conectivos lógicos son operadores lógicos que permiten formar frases que se llaman
proposiciones compuestas o fórmulas lógicas a partir de śımbolos y/o letras proposiciona-
les.
En la definición más común de la lógica proposicional clásica, estos operadores son:
La negación: es un operador unario prefijo que se representa mediante el śımbolo (¬),
que se lee “no”.
1Que se representará abreviadamente por el śımbolo F .
2Que se representará abreviadamente por el śımbolo V .
3.1. LÓGICA PROPOSICIONAL 17
La disyunción: es un operador binario infijo que se representa mediante el śımbolo (∨),
que se lee “o”.
La conjunción: es un operador binario infijo que se representa mediante el śımbolo (∧),
que se lee “y”.
El condicional: o implicación es un operador binario infijo que se representa mediante el
śımbolo (→), que se lee “entonces” o “implica”. A el primer operando del operador
condicional se le suele llamar el antecedente de la implicación y a el segundo operador
se le suele llamar el consecuente de la implicación.
El bicondicional: o equivalencia o doble implicación es un operador binario infijo que se
representa mediante el śımbolo (↔), que se lee “si y sólo si”.
El significado que cada uno de estos conectivos le da a las proposiciones compuestas que
se construyen con ellos se explicará más adelante3.
Los paréntesis son usados para agrupar de manera apropiada las fórmulas o proposi-
ciones compuestas de la lógica proposicional.
En la lógica proposicional la gramática se describe en términos de fórmulas bien for-
madas (fbf) de manera recursiva4, es decir, suponiendo que los śımbolos y letras proposi-
cionales son fbfs y definiendo nuevas fbfs en términos de fbfs ya construidas.
Definición. La gramática de la lógica proposicional se define recursivamente en términos
de fórmulas bien formadas (fbf), aśı:
i) Si p es un śımbolo o letra proposicional, entonces p es una fbf.
ii) Si f es fbf entonces ¬(f) es una fbf.
iii) Si f1 y f2 son fbfs entonces: (f1 ∨ f2), (f1 ∧ f2), (f1 → f2) y (f1↔ f2) son fbfs.
Ejemplo. Las siguientes secuencias de śımbolos son fórmulas bien formadas:
• f1: �(p ∨ ¬(q))↔ (r ∧ s)� • f2: ¬�(r → q) ∧ ¬(q↔ s)�
Ejemplo. Las siguientes secuencias de śımbolos no son fórmulas bien formadas:
• f1: (∧ p)¬(r ∧ s)� • f2: �(∨ p q)↔ (q p →)
En el lenguaje de la lógica proposicional, a diferencia del español u otro lenguaje natural,
la semántica es fácil de definir ya que los posibles sentidos que tiene una frase son solamente
dos (verdadero y falso) y las frases que se pueden construir se definen de manera recursiva
(fórmulas bien formadas).
3Existen diversas formas de definir la lógica proposicional clásica dependiendo de los conectivos lógicos
usados (śımbolo y definición semántica). La presentada aqúı es la mas usual y se le dice clásica por la
definición semántica de los conectivos lógicos.
4En una definición recursiva se definen casos particulares o base y los demás se definen como construc-
ciones sobre estos casos base y sobre estas construcciones.
18 CAPÍTULO 3. LÓGICA MATEMÁTICA
Definición. La semántica de la lógica proposicional se define de manera recursiva sobre
las fórmulas bien formadas aśı (⇠(f) se usa para representar el significado de la fórmula
bien formada f):
i) Si f es un fbf definida solamente por un śımbolo o letra proposicional, el significado
de la fórmula f es el mismo significado del śımbolo o letra proposicional.
⇠(�) ⇠(�) ⇠(p)
V F significado de la proposición p
ii) Si f es una fbf, entonces:
⇠(f) ⇠�¬(f)�
V F
F V
iii) Si f1 y f2 son fbfs, entonces:
⇠(f1) ⇠(f2) ⇠�(f1 ∨ f2)� ⇠�(f1 ∧ f2)� ⇠�(f1 → f2)� ⇠�(f1↔ f2)�
V V V V V V
V F V F F F
F V V F V F
F F F F V V
Ejemplo. Suponga que ⇠(p) = F, ⇠(q) = F, ⇠(r) = V , entonces el significado (valor de
verdad) de la fórmula bien formada
f : ¬��¬(p)→ q� ∧ �(r↔ q) ∨ ¬(�)��
para hallar el significado de f , primero se debe hallar el valor de verdad de los paréntesis
más internos y luego con esos resultados ir hallando el valor de verdad de las fórmulas más
internas que vayan apareciendo, de esta manera
⇠(p) ⇠(q) ⇠(r) ⇠�¬(p)� ⇠�(r↔ q)� ⇠�¬(�)� ⇠��¬(p)→ q��
F F V V F V F
⇠��(r↔ q) ∨ ¬(�)�� ⇠���¬(p)→ q� ∧ �(r↔ q) ∨ ¬(�)���
V F
⇠�¬��¬(p)→ q� ∧ �(r↔ q) ∨ ¬(�)���
V
aśı, ⇠(f) = V .
3.1. LÓGICA PROPOSICIONAL 19
3.1.2. Precedencia de conectivos lógicos
Uno de las principales limitaciones de las fórmulas bien formadas es el uso excesivo de
los paréntesis,los cuales, en muchos casos, son redundantes. Para evitar este uso excesivo
de paréntesis (sin que esto implique que toda fórmula pueda ser escrita sin paréntesis), a
los conectores lógicos se les asigna una prioridad que determina de manera exacta el orden
en que los paréntesis se deben asumir si no se escriben. Entre más alta es la prioridad de
un conector, los paréntesis asociados a él, tienen mayor prelación, es decir, en el proceso
de completar los paréntesis, los paréntesis asociados al operador con más prioridad son
adicionados primero que los paréntesis de un conectivo con menor prioridad. Las priori-
dades asignadas a los operadores se pueden observar el la tabla 3.1. Cuando en la fórmula
aparece el mismo operador varias veces y no se puede determinar a cuál se le deben asignar
los paréntesis primero, se asignan los paréntesis de izquierda a derecha.
Conectivo Prioridad Significado(, ) 1 más alta¬ 2 alta∧,∨ 3 media→,↔ 4 baja
Tabla 3.1. Prioridad de los conectivos lógicos.
Ejemplo. La fórmula p → q ↔ r ∨ (s ∧ p) representa la fbf �(p → q)↔ �r ∨ (s ∧ p)��, ya
que completando paréntesis:
i) p→ q↔ r ∨ (s ∧ p)
ii) p→ q↔ �r ∨ (s ∧ p)� (∨ prioridad 3)
iii) (p→ q)↔ �r ∨ (s ∧ p)� (→ más a la izquierda prioridad 4)
iv) �(p→ q)↔ �r ∨ (s ∧ p)�� (↔ prioridad 4)
3.1.3. Interpretaciones y clasificación de las fórmulas lógicas
Dada una fórmula f y ✓
f
su respectiva colección de letras proposicionales, una interpre-
tación de ✓
f
es una asignación de valores de verdad a cada una de las letras proposicionales
de la colección ✓
f
.
Ejemplo. Sea ✓
f
= {q, r, s} la colección de letras proposicionales de una fórmula f .
1. Una interpretación de ✓
f
es: {⇠(q) = V, ⇠(r) = V, ⇠(s) = F}.
2. Una interpretación de ✓
f
es: {⇠(q) = F, ⇠(r) = F, ⇠(s) = F}.
3. Una interpretación de ✓
f
es: {⇠(q) = F, ⇠(r) = V, ⇠(s) = V }.
20 CAPÍTULO 3. LÓGICA MATEMÁTICA
Proposición. Si una colección ✓
f
tiene n letras proposicionales, entonces ✓ tiene en total
2n interpretaciones diferentes.
Nota. El valor de verdad de una fórmula f para una interpretación I de la colección de
śımbolos proposicionales ✓
f
se notará como ⇠
I
(f).
Ejemplo. Las interpretaciones posibles de la colección de letras proposicionales ✓
f
={p, q, r}, entonces ✓
f
tiene ocho (23 = 8) interpretaciones:
⇠(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
3.1.3.1. Tautoloǵıas, contradicciones y contingencias
Definición. Una fórmula f se dice tautoloǵıa si para cualquier interpretación de su colec-
ción de letras proposicionales, su significado (valor de verdad) es V , se dice contradicción si
para cualquier interpretación su significado es F y se dice contingencia si no es tautoloǵıa
ni contradicción.
Ejemplo. Determinar el tipo (tautoloǵıa, contingencia o contradicción) de cada una de
las siguientes fórmulas:
1. f = p ∨ q↔ q ∨ p
2. f = p ∧ ¬p
3. f = p ∧ (q ∨ r)
Solución.
1. Si f = p ∨ q↔ q ∨ p entonces ✓
f
= {p, q}
p q p ∨ q q ∨ p p ∨ q↔ q ∨ p
V V V V V
V F V V V
F V V V V
F F F F V
entonces f es tautoloǵıa.
2. Si f = p ∧ ¬p entonces ✓
f
= {p}
3.1. LÓGICA PROPOSICIONAL 21
p ¬p p ∧ ¬p
V F F
F V F
entonces f es contradicción.
3. Si f = p ∧ (q ∨ r) entonces ✓
f
= {p, q, r}
p q r q ∨ r p ∧ (q ∨ r)
V V V V V
V V F V V
V F V V V
V F F F F
F V V V F
F V F V F
F F V V F
F F F F F
entonces f es contingencia.
3.1.3.2. Tablas de verdad
Al esquema de presentar todas las interpretaciones y el valor de verdad de la fórmula
se le llama tabla de verdad de la fórmula f . Las tablas de verdad son muy útiles para
realizar demostraciones a nivel semántico, ya que ellas no solamente se pueden usar con
letras proposicionales sino con fórmulas bien formadas, es decir, considerando toda una
fórmula bien formada como verdadera o falsa y construyendo la tabla de verdad para
dichas fórmulas.
3.1.4. Argumentación y leyes lógicas
En la lógica proposicional clásica, una ley lógica es una equivalencia o implicación entre
fórmulas lógicas. Tal equivalencia o implicación lógica debe ser verdadera para cualquier
interpretación de las letras proposicionales que conforman las fórmulas relacionadas por
la equivalencia (debe ser tautoloǵıa). Las más famosas leyes lógicas son: Modus Ponen,
Modus Tollen, Inconsistencia, Doble negación, Conmutatividad, Distributivas, Asociativas
y De Morgan.
3.1.4.1. Argumentación lógica directa
Ejemplo. A continuación se presenta un argumento directo para demostrar el siguiente
teorema.
Teorema. Sea n un número entero, si n es impar, entonces n2 es impar.
22 CAPÍTULO 3. LÓGICA MATEMÁTICA
Demostración. Si n es impar, entonces n se puede escribir en la forma n = 2m + 1, con
m en los enteros; aśı que n2 = (2m + 1)2 = 4m2 + 4m + 1 = 2(2m2 + 2m) + 1 = 2k + 1, donde
k = 2m2 + 2m es un entero. De lo anterior se puede concluir que n2 es impar. �✓
Teorema. Sea n un número entero, si n2 es impar, entonces n es impar.
Demostración. ¿? �✓
Para demostrar el anterior teorema, un argumento directo es muy complicado, por lo
que una estrategia más eficiente es utilizar un argumento que sea lógicamente equivalente
al argumento directo, aqúı es donde resultan útiles las fórmulas lógicamente equivalentes.
3.1.4.2. Equivalencias Lógicas
Definición. Sean f1 y f2 dos fórmulas, se dice que f1 es lógicamente equivalente a f2,
(f1⇔ f2) si y solamente si la fórmula
f1↔ f2
es una tautoloǵıa.
Ejemplo. Las fórmulas f1 = ¬(↵∧�) y f2 = ¬↵∨¬� son lógicamente equivalentes, es decir,¬(↵ ∧ �)⇔ ¬↵ ∨ ¬�, para cualesquiera fórmulas ↵ y �. Para esto, se debe demostrar que¬(↵ ∧ �)↔ ¬↵ ∨ ¬� es una tautoloǵıa; como se aprecia en la siguiente tabla
↵ � ↵ ∧ � ¬(↵ ∧ �) ¬↵ ¬� ¬↵ ∨ ¬� ¬(↵ ∧ �)↔ ¬↵ ∨ ¬�
V V V F F F F V
V F F V F V V V
F V F V V F V V
F F F V V V V V
como se observa, f1 ↔ f2 es una tautoloǵıa, por lo tanto, f1 y f2 son lógicamente equiva-
lentes.
Las equivalencias lógicas más conocidas se presentan en la tabla 3.2. La demostración
de las mismas se deja al lector.
3.1.4.3. Argumentación lógica indirecta por la contrarrećıproca
Teorema. Sea n un número entero, si n2 es impar, entonces n es impar.
Demostración. Aplicando la equivalencia contrarrećıproca
↵ → �⇔ ¬� → ¬↵
con
3.1. LÓGICA PROPOSICIONAL 23
Equivalencia Nombre
↵ ∨ ¬↵⇔ � Tercio exclúıdo
↵ ∧ ¬↵⇔ � Contradicción
↵ ∨ �⇔ ↵
Identidad
↵ ∧ �⇔ ↵
↵ ∨ �⇔ �
Dominación
↵ ∧ �⇔ �
↵ ∨ ↵⇔ ↵
Idempotencia
↵ ∧ ↵⇔ ↵¬¬↵⇔ ↵ Doble negación
↵ ∨ �⇔ � ∨ ↵
Conmutativas↵ ∧ �⇔ � ∧ ↵
↵↔ �⇔ � ↔ ↵(↵ ∧ �) ∧ �⇔ ↵ ∧ (� ∧ �)
Asociativas(↵ ∨ �) ∨ �⇔ ↵ ∨ (� ∨ �)
↵ ∨ (� ∧ �)⇔ (↵ ∨ �) ∧ (↵ ∨ �)
Distributivas↵ ∧ (� ∨ �)⇔ (↵ ∧ �) ∨ (↵ ∧ �)
↵ → (� → �)⇔ (↵ → �)→ (↵ → �)¬(↵ ∧ �)⇔ ¬↵ ∨ ¬�
De Morgan¬(↵ ∨ �)⇔ ¬↵ ∧ ¬�
↵ → �⇔ ¬� → ¬↵ Contrarrećıproca
↵↔ �⇔ (↵ → �) ∧ (� → ↵) Material
↵ → (� → �)⇔ ↵ ∧ � → � Exportación
Tabla 3.2. Equivalencias lógicas.
↵ = n2 es impar y � = n es impar
entonces ¬↵ = n2 es par y ¬� = n es par
Por lo tanto demostrar el anterior teorema es equivalente a demostrar que
si n es par, entonces n2 es par
para esto, obsérvese que si n es par, entonces n se puede escribir en la forma n = 2m, con
m en los enteros; aśı que n2 = (2m)2 = 4m2 = 2(2m2) = 2k, donde k = 2m2 es un entero y
por lo tanto se puede concluir que n2 es par. Del razonamiento anterior se tiene que por
la equivalencia contrarrećıproca queda demostrada la proposición original. �✓
De los teoremas anteriores se tiene que para que n2 sea impar es necesario que n sea
impar, y de forma similar para que n sea impar es necesario que n2 sea impar. Esto se
expresa como que para que n2 sea impar es razón necesaria y suficiente que n sea impar,
de donde ambas proposiciones son verdaderas o ambas son falsas y se puede enunciar el
siguiente teorema bidireccional general.
Teorema. Sea n un número entero, n2 es impar, si y sólo si n es impar.
24 CAPÍTULO 3. LÓGICA MATEMÁTICA
Demostración. A partir de las demostraciones previas. �✓
3.1.4.4. Implicaciones Lógicas
En algunos casosno es necesario exigir que dos fórmulas sean equivalentes, tal vez sea
útil exigir que en una dirección de la equivalencia la fórmula del consecuente sea verdadera
cuando la fórmula del antecedente sea verdadera, o lo que es lo mismo, que la fórmula del
antecedente sea falsa cuando la fórmula del consecuente sea falsa.
Ejemplo. A continuación se presenta un argumento directo para demostrar el siguiente
teorema.
Teorema. Sean m y n números enteros, si m es par y n es par, entonces m + n es par.
Demostración. Si m es par y n es par, entonces m y n se pueden escribir en la forma
m = 2k1 y n = 2k2, con k1 y k2 en los enteros; aśı que m + n = 2k1 + 2k2 = 2(k1 + k2) = 2k,
donde k = k1 + k2 es un entero. De lo anterior se puede concluir que m + n es par. �✓
Obsérvese que en el teorema anterior el consecuente (m+n es par) es verdadero cuando
el antecedente (m es par y n es par) es verdadero.
Ahora, para el enunciado que se obtiene cuando se toma el teorema en dirección rećıpro-
ca,
Si m + n es par, entonces, m es par y n es par.
se puede observar que cuando m = 3 impar y n = 5 impar, entonces m+n = 8 par, se tiene
que el consecuente es verdadero y el antecedente es falso, de donde la implicación es falsa
y no se tendŕıa una equivalencia lógica, sino que se cumpliŕıa en sólo una dirección.
Cuando una fórmula (llamada conclusión) se cumple siempre que una colección de
fórmulas (llamadas premisas) se cumplan simultáneamente, se dice que las premisas im-
plican la conclusion. Formalmente esto se expresa de la siguiente manera.
Definición. Sea � = {f1, f2, . . . , fn} una colección de fórmulas (premisas) y g una fórmula
(conclusión), se dice que � implica lógicamente a g (�⇒ g), si y solamente si
(f1 ∧ f2 ∧�∧ fn)→ g
es una tautoloǵıa.
Ejemplo. Las premisas � = {¬�,↵ → �} implican lógicamente a g = ¬↵, para esto es
necesario que la fórmula �¬� ∧ (↵ → �)� → ¬↵ sea una tautoloǵıa, como se aprecia en la
siguiente tabla
3.1. LÓGICA PROPOSICIONAL 25
↵ � ¬� ↵ → � ¬� ∧ (↵ → �) ¬↵ �¬� ∧ (↵ → �)�→ ¬↵
V V F V F F V
V F V F F F V
F V F V F V V
F F V V V V V
como se observa, �¬� ∧ (↵ → �)� → ¬↵ es una tautoloǵıa, por lo tanto, � = {¬�,↵ → �}
implica lógicamente a g = ¬↵.
Las implicaciones lógicas más conocidas se presentan en la tabla 3.3. Se deja al lector
la demostración de las mismas.
Implicación Nombre{↵,�}⇒ (↵ ∧ �) Combinación{↵,�}⇒ ↵ Ley de simplificación{↵,�}⇒ � Variante de la ley de simplificación{↵}⇒ (↵ ∨ �) Ley de adición{�}⇒ (↵ ∨ �) Variante de la adición{↵,↵ → �}⇒ � Modus Ponendo Ponens (Modus ponens){¬�,↵ → �}⇒ ¬↵ Modus Tollendo Tollens (Modus tollens){↵ → �,� → �}⇒ (↵ → �)
Silogismos hipotéticos{↵↔ �,� ↔ �}⇒ (↵↔ �){¬↵,↵ ∨ �}⇒ �
Silogismos disyuntivos{↵,¬↵ ∨ ¬�}⇒ ¬�{¬�,↵ ∨ �}⇒ ↵ Variante de los silogismos{�,¬↵ ∨ ¬�}⇒ ¬↵ disyuntivos{↵ → �,¬↵ → �}⇒ � Ley de casos{↵↔ �}⇒ (↵ → �) Eliminación de equivalencia{↵↔ �}⇒ (� → ↵) Variante de eliminación
de equivalencia{� → ↵,↵ → �}⇒ (↵↔ �) Introducción de la equivalencia{↵,¬↵}⇒ � Ley de inconsistencia{↵ → �,� → ⌧,↵ ∨ �}⇒ (� ∨ ⌧)
Dilemas constructivos{↵ → �,� → ⌧,¬� ∨ ¬⌧}⇒ (¬↵ ∨ ¬�)
Tabla 3.3. Implicaciones lógicas.
3.1.4.5. Argumentación mediante implicaciones lógicas
Dado un triángulo △ABC. Si el △ABC no tiene todos sus ángulos iguales; y, si el△ABC tiene todos sus lados iguales (es equilátero), entonces todos los ángulos internos
del △ABC son iguales. De lo anterior, se puede concluir que el △ABC no es equilátero.
El argumento anterior se puede justificar usando una implicación lógica de la siguiente
manera:
26 CAPÍTULO 3. LÓGICA MATEMÁTICA
� = El △ABC tiene todos sus ángulos internos iguales
↵ = El △ABC tiene todos sus lados iguales
usando la implicación lógica Modus tollens �{¬�,↵ → �}⇒ ¬↵� se concluye
¬↵ = El △ABC no tiene todos sus lados iguales= El △ABC no es equilátero
3.2. Lógica de predicados
En la lógica proposicional no definen objetos variables, siempre se hace referencia a un
objeto espećıfico. Aśı como se puede hablar de una proposición como la siguiente “p: el
niño juega con la pelota roja y blanca”, también se podŕıa hablar de una proposición como
“q: la foca juega con la pelota azul y verde”, en este caso las proposiciones son similares,
pues lo que cambia es el sujeto y/o el complemento.
A partir de los casos anteriores se puede pensar en definir enunciados sin un sujeto o un
complemento espećıfico. Por ejemplo el sujeto puede cambiar (la foca, el niño) y también
el complemento puede cambiar (la pelota roja y blanca, la pelota azul y verde) de acuerdo
a una realidad. Esto da como resultado frases del estilo “x juega con y”.
x e y son objetos que están relacionados mediante un predicado y dependiendo de
los objetos, se obtiene una proposición que es V o es F . En términos de los sujetos y
los complementos se define un predicado o proposición abierta a una frase que dice algo
acerca del sujeto que lo relaciona con el complemento. En el ejemplo anterior el predicado
es “juega con” y se escribiŕıa simbólicamente mediante le expresión juegaCon(x, y), que
se interpreta conceptualmente como “x juega con y”, a las variables x e y se les denomina
variables libres.
Un predicado da una forma más amplia de hablar. Se podŕıa tener una colección{0,1,2,3,4,5,6,7,8,9}, y sobre esta colección se puede definir un predicado. Por ejem-
plo, se podŕıa hablar del predicado esPar(x). Si se toma el predicado y se asigna al sujeto
x el valor 3 entonces esPar(3) tendrá un valor de verdad F , si se toma el predicado y se
asigna al sujeto x el valor 6 entonces esPar(6) tendrá un valor de verdad V .
A una colección de objetos a los cuales se les desea aplicar el predicado se le llama el
universo del discurso. Cuando en un predicado se reemplaza una variable libre x por un
valor concreto del universo del discurso, se dice que se está “instanciando” la variable x,
la fórmula resultante se dice que es una “instancia” o del predicado inicial.
Cuando no se ha instanciado un predicado, a éste no se le puede asignar un valor de
verdad. Por ejemplo, el predicado o proposición abierta esPrimo(x) no se puede valorar,
por el contrario, cuando se instancian todas las variables de un predicado, lo que se obtiene
es una proposición cerrada, y por lo tanto se cumple la condición de que en ese caso la
instancia tendrá un valor o V o F , y no puede tener los dos a la vez.
3.2. LÓGICA DE PREDICADOS 27
3.2.1. Cuantificadores
Pueden haber predicados como esDigito(x) que para todos los objetos del univer-
so del discurso {0,1,2,3,4,5,6,7,8,9} son V . Para este mismo universo, el predica-
do esMayora10(x) es F para todos los elementos de dicha colección, y el predicado
esModuloAditivo(x) es V sólo para x = 0 y para el resto de los casos será F .
Cuando se desea expresar que un predicado P (x) describe una propiedad sobre todos
los elementos del universo del discurso o para sólo algunos, se dice que se está cuantificando
la variable x, y ahora la variable libre pasa a ser una variable ligada.
Cuando se desea expresar que un predicado describe una propiedad para todos los
elementos del universo del discurso, se dice que se está cuantificando universalmente.
Cuando el predicado describe una propiedad para algunos de los elementos del universo
del discurso, se dice que se está cuantificando existencialmente.
Para expresar estas nuevas propiedades se necesitan nuevos śımbolos, y estos son los
śımbolos ∀ y ∃ que permiten ampliar el léxico y se utilizan de la siguiente manera:
• Para notar que una variable x está cuantificada universalmente en un predicado
P (x) se utiliza la expresión ∀xP (x)
que se lee “para todo x P (x)”.
• Para notar que una variable x está cuantificada existencialmente en un predicado
P (x) se utiliza la expresión ∃xP (x)
que se lee “existe x tal que P (x)”.
3.2.2. Semántica de los cuantificadores
Cuando en una expresión una variable está cuantificada universalmente, se tiene que
⇠�∀xP (x)�⇔ ⇠�P (x1) ∧ P (x2) ∧�∧ P (xn)�
paratodo valor x
i
del universo del discurso.
Cuando en una expresión una variable está cuantificada existencialmente, se tiene que
⇠�∃xP (x)�⇔ ⇠�P (x1) ∨ P (x2) ∨�∨ P (xn)�
para todo valor x
i
del universo del discurso.
Ejemplo. Si se tienen los números d́ıgitos como universo del discurso y se establece como
predicado
P (x) ∶= x es múltiplo de 4,
28 CAPÍTULO 3. LÓGICA MATEMÁTICA
se tiene que ⇠�∃xP (x)� = V y ⇠�∀xP (x)� = F ; esto porque el predicado será cierto cuando
se instancia la variable con los valores 0, 4 y 8 �P (0), P (4), P (8)�, aqúı se ha tomado la
definición de múltiplo como
Definición. Se dice que un número m es múltiplo de d (d ≠ 0) si existe un entero k, tal
que se satisface la igualdad m = dk, esto se expresa como que “m es un múltiplo de d”. A
el número d se le conoce como divisor o factor de m, lo que se denota como d �m y se lee
“d divide a m”. Si d no divide a m esto se denotará como d ��m.
3.2.3. Leyes de De Morgan para cuantificadores
Con respecto a los cuantificadores, se tienen la siguientes equivalencias que expresan
leyes análogas a las leyes de De Morgan para la lógica de proposiciones:
¬∃xP (x)⇔ ∀x¬P (x): no existe un x que cumpla el predicado P quiere decir que para
todo x no se cumple el predicado P .
¬∀xP (x)⇔ ∃x¬P (x): no todo x cumple el predicado P es decir que existe un x que no
cumple el predicado.
3.2.4. Reglas de inferencia sobre fórmulas cuantificadas
3.2.4.1. Particularización universal
Sea D un universo del discurso, entonces se tiene la siguiente regla de inferencia.
∀x P (x)∴ P (d) si d ∈D
Si se piensa por un segundo en el argumento atribuido a Aristóteles,
“Todo hombre es Mortal, Aristóteles es un hombre entonces Aristóteles es Mor-
tal”
Uno de los universos de discurso podŕıa ser
U = todas las cosas pensadas por Aristóteles.
En este caso se pueden identificar dos predicados: Mortal(x) y Humano(x).
∀x�Humano(x)→Mortal(x)�
Humano(Aristoteles)∴ Mortal(Aristoteles)
3.2. LÓGICA DE PREDICADOS 29
en este razonamiento se observa que Aristóteles realiza una particularización univer-
sal, esto consiste en reemplazar una variable que está cuantificada universalmente por
un objeto del universo. Éste es un argumento valido, ya que si se asume la veraci-
dad del predicado ∀x�Humano(x) → Mortal(x)� y también la veracidad de la pro-
posición Humano(Aristoteles), entonces la conclusión Mortal(Aristoteles) debe ser
verdadera, ya que si no fuese aśı, entonces, la proposición �Humano(Aristoteles) →
Mortal(Aristoteles)� seria falsa, y eso haŕıa que el predicado ∀x�Humano(x)→Mortal(x)�
fuese falso, lo que contradice la suposición de su veracidad.
3.2.4.2. Generalización universal
Sea D un universo del discurso, entonces se tiene la siguiente regla de inferencia.
si P (d) para cada d ∈D∴ ∀x P (x)
Ejemplo. Para los integrantes de la Familia Simpson se cumple que:
• Bart vive en Springfield.
• Lisa vive en Springfield.
• Maggie vive en Springfield.
• Homero vive en Springfield.
• Marge vive en Springfield.
Mediante generalización universal se puede inferir que
“Cada miembro de la Familia Simpson vive en Springfield.”
3.2.4.3. Particularización existencial
Sea D un universo del discurso, entonces se tiene la siguiente regla de inferencia.∃x P (x)∴ P (d) para alguna d ∈D
Ejemplo. De los planetas en el Sistema Solar ., existen planetas que poseen vida inte-
ligente. Mediante particularización existencial se puede inferir que
“Algún planeta del Sistema Solar ., como La Tierram, posee vida inteligente”.
3.2.4.4. Generalización existencial
Sea D un universo del discurso, entonces se tiene la siguiente regla de inferencia.
30 CAPÍTULO 3. LÓGICA MATEMÁTICA
si P (d) para alguna d ∈D∴ ∃x P (x)
Ejemplo. En los personajes de Los Simpson, El señor Burns es el jefe de Homero
. Mediante generalización existencial se puede inferir que
“Existe un personaje de Los Simpson que es jefe de Homero .”.
3.2.5. Lógica de predicados en programación
Cuando un profesor revisa un programa, éste evalúa que para toda entrada dada, se
tenga una salida esperada. Si el profesor encuentra un caso para el que el programa no
muestra una salida esperada (particularización universal), se concluye que el programa
no funciona pues se espera que haga lo que debe hacer para todos los posibles casos
contemplados.
La lógica de predicados ayuda a establecer precondiciones en la elaboración de los
programas. Validaciones de este tipo incluyen verificaciones en los tipos de datos, por
ejemplo:
• El cálculo de peŕımetros y áreas debe funcionar solamente con números positivos.
• El valor de una temperatura requiere que la medición se realice con magnitudes
continuas.
• El tiempo promedio de vida de un animal unicelular es una cantidad continua que
representa tiempos positivos.
3.3. EJERCICIOS 31
3.3. Ejercicios
1. De los siguientes enunciados ¿cuáles son proposiciones y cuáles no?, justifique su
respuesta.
• Tom Hanks ha ganado dos premios Oscar como mejor actor por dos años con-
secutivos.
• Dame una cerveza.
• Colombia ganó ocho medallas oĺımpicas en Londres 2012.
• Todo número primo es impar.
• 1 + 1 = 2.
• La diferencia de dos primos.
• Todo número par mayor que 2 puede escribirse como suma de dos números
primos. (Christian Goldbach, 1742).
• ¿Que hora es?.
• xn + yn = zn.
• x + y = z + y si x = z.
2. De las siguientes secuencias de śımbolos ¿cuáles son fórmulas bien formadas y cuáles
no?.
• �(¬(p)→ r) ∧ (p ¬ q)�
• �(¬(p)↔ ¬(q))↔ (q → r)�
• (p ∧ q) ∨ (q → p)�
• �(p↔ p) ∧ (p→ p) ∨ (p ∧ ¬(p))�
3. Escriba la fórmula bien formada que representa cada una de la siguientes secuencias
de śımbolos:
• p ∧ q↔ r ∨ s→ q
• p→ q → q → p
• ¬p↔ q ∨ ¬r ∨ (q → r)↔ ¬¬q
• p ∨ (q ∧ r)↔ p ∨ q ∧ (p ∨ q)
4. Hallar el significado de cada fórmula que se especifica a continuación con respecto a
la interpretación definida para ésta.
• f = p ∧ q↔ r ∨ s→ q, si ⇠(p) = V , ⇠(q) = V , ⇠(r) = V , ⇠(s) = F .
• f = p→ q → q → p, si ⇠(p) = V , ⇠(q) = F .
• f = ¬p↔ q ∨ ¬r ∨ (q → r)↔ ¬¬q, si ⇠(p) = F , ⇠(q) = V , ⇠(r) = V .
• f = p ∨ (q ∧ r)↔ p ∨ q ∧ (p ∨ q), si ⇠(p) = V , ⇠(q) = F , ⇠(r) = V .
32 CAPÍTULO 3. LÓGICA MATEMÁTICA
5. Verifique las equivalencias lógicas de la tabla 3.2.
6. Verifique las implicaciones lógicas de la tabla 3.3.
7. Verifique que las fórmulas f1 = p ∧ q ∨ r y f2 = p ∧ (q ∨ r) no son lógicamente
equivalentes.
8. Con los operadores lógicos ¬ y ∧ es posible expresar los otros operadores lógicos
(∨,→,↔) de forma equivalente, de la siguiente manera
p ∨ q⇔ ¬(¬p ∧ ¬q)
p→ q⇔ ¬(p ∧ ¬q)
p↔ q⇔ ¬(p ∧ ¬q) ∧ ¬(q ∧ ¬p)
verificar que efectivamente los operadores lógicos ∨,→,↔ se pueden expresar en
términos de los operadores lógicos ¬ y ∧.
9. Con los operadores lógicos ¬ y ∨ es posible expresar los otros operadores lógicos
(∧,→,↔). Encontrar fórmulas lógicas que contengan sólo los operadores lógicos ¬ y∨ que sean equivalentes a las fórmulas p∧q, p→ q, p↔ q y verifique que efectivamente
son lógicamente equivalentes.
10. Adicional a los conectivos lógicos presentados, existen otros conectivos, tal como el
conectivo o exclusivo (⊗), el cual es muy utilizado en computación, y tiene como
objetivo que dadas dos fórmulas f1 y f2, la operación f1 ⊗ f2 será únicamente ver-
dadera cuando se cumpla que sólo una de la fórmulas f1 o f2 sea verdadera. De esta
manera, la semántica para este conectivo es la siguiente
⇠(f1) ⇠(f2) ⇠(f1 ⊗ f2)
V V F
V F V
F V V
F F F
(a) Encuentre una fórmula que sea equivalente lógicamente a la fórmula f1 ⊗ f2,
que sólo utilice los operadores lógicos ¬ y ∧.
(b) Encuentre una fórmula que sea equivalente lógicamente a la fórmula f1 ⊗ f2,
que sólo utilice los operadores lógicos ¬ y ∨.
11. Adicional a los conectivos lógicos presentados, existe otro conectivo, tal como el
conectivo barra de She↵er (�), para el cual su semántica es la siguiente
⇠(f1) ⇠(f2) ⇠(f1 � f2)
V V F
V F V
F V V
F F V
3.3. EJERCICIOS 33
La principal caracteŕıstica de