La ciencia de programar

La ciencia de
programar
Jonatan Gom´ez Perdomo, Ph.D.
Arles Rodr´ıguez, Ph.D.(c)
Camilo Cubides, Ph.D.(c)

´Indice general

J

´Indice general

I

´Indice de tablas

VII

´Indice de figuras

IX

1. Introducci´
on
1.1. Generaciones de los computadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2. Lenguajes

1
1
5

2.1. Componentes del lenguaje . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .

8

2.2. Lenguajes de Programaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3. Clasificaci´on de los lenguajes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4. Paradigmas de programaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3. L´
ogica Matem´atica

15

3.1. L´ogica Proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.1. El lenguaje de la l´ogica proposicional . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.2. Precedencia de conectivos l´ogicos . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.3. Interpretaciones y clasificaci´on de las f´ormulas l´ogicas . . . . . . . .. . . . 19
3.1.3.1. Tautolog´ıas, contradicciones y contingencias . . . . . . . . . . . . 20
3.1.3.2. Tablas de verdad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.4. Argumentaci´on y leyes l´ogicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
I

II

´INDICE GENERAL

3.1.4.1. Argumentaci´on l´ogica directa . . . . . . . . . . . . . . . . . . . . . . .21
3.1.4.2. Equivalencias L´ogicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.4.3. Argumentaci´on l´ogica indirecta por la contrarrec´ıproca . . . 22
3.1.4.4. Implicaciones L´ogicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.4.5. Argumentaci´on mediante implicaciones l´ogicas . . . . . . . . . . 25
3.2. L´ogica de predicados . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.1. Cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.2. Sem´antica de los cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.3. Leyes de De Morgan para cuantificadores . . . . . . . . . . . . . . . . . . . . . 28
3.2.4. Reglas de inferencia sobref´ormulas cuantificadas . . . . . . . . . . . . . . . 28
3.2.4.1. Particularizaci´on universal . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.4.2. Generalizaci´on universal . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.4.3. Particularizaci´on existencial . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.4.4. Generalizaci´on existencial . . . . . . . . . . . . . . . . . . . . .. . . . . 29
3.2.5. L´ogica de predicados en programaci´on . . . . . . . . . . . . . . . . . . . . . . . 30
3.3. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4. Teor´ıa de conjuntos

35

4.1. Conceptos b´asicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.1. Conjunto y elemento. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.1.2. Especificaci´on de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.2.1. Extensi´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.2.2. Comprensi´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1.3. El conjunto vac´ıo .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.4. Representaci´on 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 . . . . . . . . . . . . . . . . . . . . . ....