INGENIERIA EN
SISTEMAS COMPUTACIONALES
INVESTIGACION:
TEORIA DE CONJUNTOS
LOGICA PROPOSICIONAL
HISTORIA DE LOS
LENGUAJES
ING. JOSE ANGEL
TOLEDO ALVAREZ
MINATITLAN VERACRUZ,
09 DE FREBERO DEL 2004
CONTENIDO
TEORIA DE
CONJUNTOS
-
NOTACION
DE CONJUNTOS
-
CONCEPTOS
BASICOS DE TEORIA DE CONJUNTOS
-
DEFINICION
INDUCTIVA DE CONJUNTO
-
OPERACIONES
CON CONJUNTOS
LOGICA
PROPOSICIONAL
-
PROPOSICIONES SIMPLE Y COMPUESTAS
-
OBJETIVOS
-
CONECTIVAS LOGICAS
-
FORMULAS BIEN FORMADAS
-
JERARQUIAS DE CONECTIVAS
-
INTERPRETACION DE FORMULAS
-
FORMULAS NORMALES
HISTORIA DE LOS LENGUAJES
-
TENDENCIAS EN LOS LENGUAJES DE PROGRAMACION
TEORÍA DE CONJUNTOS
La teoría
de conjuntos fue creada por George Cantor, aunque George Boole dio los primeros pasos en su libro
Investigations of the Laws of Thought.
El concepto
de infinito fue tratado por Zenón de Elea y sus célebres
paradojas.
Bolzano
defendió el concepto de conjunto infinito. Bolzano dio ejemplos de como los
elementos de un conjunto infinito podían ponerse en correspondencia 1-1 con
elementos de sus propios subconjuntos.
Cantor publicó varios artículos entre 1867 y
1871 sobre teoría de números de gran calidad pero nada indicaba que su autor
cambiaría el curso de la matemática.
En 1872 Cantor viajó a Suiza y allí conoció a Dedekind. Se hicieron amigos y se cree que Dedekind influyó en las ideas de Cantor.
Cantor empezó a trabajar en series
trigonométricas y aquí aparecen las primeras ideas sobre teoría de conjuntos.
En 1874 publicó un artículo en la revista de Crelle que marca el nacimiento de
la teoría de conjuntos. En este artículo Cantor consideraba dos clases diferentes de
infinitos (hasta entonces se consideraba que todos los infinitos tenían el
mismo tamaño) los que se podían poner en correspondencia uno a uno con los
números naturales (los que se podían numerar) y los que no se podía.
Cantor demostró que los números reales
algebraicos se podían poner en correspondencia uno a uno con los números
naturales pero que esto no se podía hacer con los números reales (que incluyen,
además de los reales algebraicos los transcendentes).
En 1878 Cantor envió otro artículo a la revista pero
la Teoría de Conjuntos era una materia muy discutida, especialmente por
Kronecker, que pertenecía al equipo editor de la revista. Intentaron que Cantor retirase el artículo pero Dedekind convenció a Cantor para que no lo hiciese y Weierstrass respaldó la publicación. El
artículo fue publicado pero Cantor no volvió a enviar más artículos a la
revista de Crelle. En este artículo Cantor introduce la idea de equivalencia de conjuntos
(dos conjuntos son equivalentes, o tienen la misma potencia, si se pueden poner
en correspondencia 1 a 1).
En 1897 se
publica la primera paradoja de la teoría de conjuntos (el ordinal del conjunto
de todos los ordinales debe ser un ordinal y esto es una contradicción). En
1899 Cantor descubre otra paradoja (¿Cual es el
cardinal del conjunto de todos los conjuntos?) . La
última paradoja fue encontrada por Russell y Zermelo en 1902 (Si A = {X|X no es
miembro de X}, ¿A es elemento de A?)
La paradoja
de Russell minaba el edificio de las matemáticas.
Russell junto con Whitehead intentó
fundamentar las matemáticas en la lógica en Principia
Mathematica. Este trabajo tuvo una gran influencia en las
matemáticas.
A pesar de
las paradojas, la Teoría de Conjuntos empezó a influir en otras áreas de las
matemáticas. Lebesgue la utilizó en su integral
El primer
intento de axiomatizar la Teoría de Conjuntos la hizo Zermelo en 1908. Después lo intentaron
Fraenkel, von Neumann, Bernays y Gödel. Gödel mostró las limitaciones de
El concepto de conjunto es de fundamental importancia en
las matemáticas modernas. Muchos matemáticos creen que es posible expresar
todas las matemáticas con un lenguaje de teoría de conjuntos. Otra aplicación
de la teoría de conjuntos la encontramos con el modelado e investigación de
operaciones en las ciencias computacionales.
Los conjuntos fueron
por primera vez formalmente estudiados por G. Cantor. Después de esto la teoría
de conjuntos se ha convertido en un área muy bien establecida de matemáticas,
contradicciones o paradojas que encontramos
en dicha teoría. Eventualmente, los más sofisticados acercamientos al trabajo
original de Cantor hicieron que dichas paradojas desaparecieran. Tratos
introductorios de la teoría de conjuntos usualmente mostraban una “cándida”
teoría de conjuntos, la cuál era bastante similar al trabajo original de
Cantor, mejor dicho, se desarrollaban en el mismo marco teórico necesario para
no caer en paradojas.
El trabajo a
desarrollar mostrará la teoría de conjuntos desde un punto de vista muy amplio,
sin adentrarnos al análisis profundo de las paradojas que se podrían presentar
en el camino.
NOTACIÓN DE CONJUNTOS
Notación:
Ordinariamente
usaremos letras mayúsculas para representar los conjuntos que incluiremos sus
elementos dentro de llaves separados por comas, {}.
El símbolo elementoÎsignifica (es elemento
de). Análogamente,Ïsignifica (no es elemento de).
Ejemplo: Sea S la letra que designa el conjunto descrito precisamente como [a,b,c,d].
Por tanto, S es el
conjunto cuyos elementos son las primeras cuatro letras minusculas del
alfabeto. Podemos entonces escribir a ÎS, b ÎS, c ÎS y d ÎS. Similarmente fÏ S, 3 Ï S, etc.
Conuntos Iguales:
Usamos el signo de
igualdad para indicar que dos símbolos representan al mismo conjunto.
Definición: se dice
que dos conjuntos S y T son iguales si
cada elemento de S es elemento de T y viceversa. Se escribe S=T.
Ejemplo: en el
ejemplo anterior pusimos S = [a,b,c,d]; puesto que
[a.b.c.d] es un símbolo para representar al mismo conjunto que representa S.
Debe notarse que,
según esta definición, no importa el orden en que se expresan los elementos.
Por lo tanto [a,b,c,d] =[b.d,c.a].
Conjuntos Vacios :
Es útil tener el
concepto de un conjunto sin elemento.
Definición: un conjunto sin
elementos recibe el nombre de conjuntos vacios o conjunto nulo y se representa por [ ] o por Æ. Ejemplo: considérese el conjunto S
de todos los elementos que los son tanto [a,b,c] como
de [d,e,f]. El conjunto S no tiene elementos,; luego,
S = [ ].
Subconjuntos:
Definición: se dice que un
conjunto S es subconjunto T, si todos los elementos de S los son T. El símbolo Í se lee (es subconjunto de).
Así, (SÍ T ) se lee (S es subconjunto de T). Decir
que S no es subconjunto de T significa que algun elemento de S no lo es de T.
En tal caso escribimos S Ë T. Ejemplo: sea S =
(a.b.c.d) y T=(a.b.c.d.e). Vemos que S Í T. Sin embargo
si H={a.b.c.f},
notamos que f Ï T, de modo que HË T.
Entenderemos que el conjunto vacío, Æ,
siempre es subconjunto de cualquier conjunto T. Si no fuese así ellos
significaría que algún elemento de Æ, no sería
miembro de T, pero como Æ, no tiene
elementos esto resultaría imposible.
Definición: se dice que S es
un subconjunto propio de T, si S Í T, y además existe
algún elemento de T que no esta en S. Esto lo escribimos S Ì T.
Conjuntos Equivalentes:
Cuando los elementos
de un conjunto se corresponden con los de un segundo conjunto de modo que cada elemento de cada conjunto tenga
uno, y solo uno, asociado en el otro conjunto, decimos que hay una
correspondencia uno a uno entre ambos conjuntos.
Definición: dos conjuntos que
se pueden poner en correspondencia uno a uno entre sí, se dice que son
equivalentes. Si A es equivalente a B, se escribe A~B. Ejemplo:
sean S = {a.b.c.d} y T = {Ù,‘,0,+}. Estos dos conjuntos son
equivalentes puesto que podemos hacer corresponder en forma uno a uno
los elementos de un conjunto con los del otro.
Cardinalidad De Un Conjunto
Todos estamos
familiarizados con el conjunto ordenado de los números naturales, N = {1,2,3,4..} y el conjunto ordenado de los número enteros no
negativos W = {0,1,2,3,4...}.
Contar es el proceso por el cual podemos en
correspondencia los elementos de un conjunto con algún subconjunto propio de N,
comenzando con 1 y usando los elementos de N en orden y sin saltar ninguno. Un
subconjunto así se llama subconjunto estándar de N. Ejemplo: es decir, el
subconjunto estándar de N, {1,2,3,4} es equivalente a
{a,b,c,d}decimos entonces que S tiene cuatro elementos. Estos lleva a la definición siguiente:
Definición: cuando un conjunto
S se equipara con un subconjunto estándar de N, el ultimo elemento de N usado
se llama cardinalidad del conjunto S y se denota por n (S). Ejemplo: en el ejemplo anterior, n(S)=
4.
Definición: la cardinalidad Æ, el conjunto vacío
es cero.
Tenemos que
construir esta definición por separado, puesto que 0ÏN y, por tanto, no tiene sentido hablar de
equiparar elementos que no existen.
La claridad del
conjunto {3} es 1, ya que {3} se puede equiparar con {1}. Es decir que el
conjunto {3} tiene un miembro. Similarmente, la claridad del conjunto {0} es 1.
hay que estar seguro de que entendemos la diferencia
entre {} y {0}.
Dos números enteros
no negativos m y n, son iguales si ambos son la cardinalidad del mismo conjunto
o de conjuntos equivalentes. En tal caso, escribimos m=n..
Definición: si m y n son
números entero no negativos, decir que m es
menor que n significa que n es la cardinalidad de un conjunto que se
puede equipar con un subconjunto propio de un conjunto de cardinalidad n.
Escribiremos entonces m < n. Si m < n podemos decir también que n > m.
Ejemplo: S = {a.b.c} y T ={d,e,f,g,h}. Vemos que hay
una correspondencia uno a uno entre S y el subconjunto propio de T, {d,e,f}. Por tanto, n (S) < n (T), o bien puesto que n (S) =3 y n (T)=5, ponemos 3 < 5.
Conjuntos Finitos E Infinitos:
Si es posible encontrar un
subconjunto estándar de N que se puede
hacer corresponder uno a uno con un
conjunto dado S, o si S es el conjunto vacío,
decimos que S es finito. Si no, decimos que infinitos. Ejemplos:
T = {a,b,c..., x,y,z} es conjunto
finito, puesto que es equivalente
{1,2,3,4,5...,25,26}.
El conjunto N = {1,2,3...}
es infinito, puesto que no es posible equiparar con ningún subconjunto estándar
de N.
Notese que, sin embargo si hay un
equiparamiento de N con uno de sus
subconjuntos que no es un subconjunto estándar: como el conjunto de los números
pares. Vemos que N se puede poner en correspondencia con un subconjunto propio
de si mismo. Esto solo se puede hacer en un conjunto infinito.
CONCEPTOS BÁSICOS TEORÍA DE CONJUNTOS
Un Conjunto
es cualquier colección de objetos el cual pueden ser
tratado como una entidad, y un objeto de la colección se dice que es un elemento
o miembro del conjunto. Dado un objeto x y un conjunto S, si x es un
elemento del conjunto S, lo podemos escribir como x Î S; si x no es
un elemento del conjunto S, podemos escribirlo como Ø(x Î S) o también x Ï S. Los términos conjunto, colección y clase son
usados como sinónimos, así como también los términos elemento o miembro.
Hay que hacer notar
que no hemos dado una definición formal de conjuntos ni una base para decidir
cuando un objeto es un miembro de un conjunto. Como en cualquier otra teoría
matemática, no siempre se hace énfasis en los conceptos básicos o en las
nociones indefinidas (como por ejemplo, punto o línea en geometría); la definición
de conjunto y la relación es un elemento de son conceptos
fundamentales de la teoría de conjuntos. Como consecuencia de no tener
definiciones para estos conceptos, no tenemos una prueba para determinar cuando
algo es un conjunto o cuando, un objeto dado, es un elemento de un conjunto
especificado. Por no tener una prueba, debemos de confiar en un sentido común
del significado de los términos.
Casi cualquier cosa
puede ser puede ser tratada como conjunto, viéndola desde un punto de vista muy
matemático, lo que trataremos de ilustrar con los siguientes ejemplos.
El conjunto de
enteros no negativos menores que 4. Éste es un conjunto finito con cuatro
miembros: 0, 1, 2 y 3.
El conjunto de
libros en la biblioteca del ITQ en este momento. Éste también es un
conjunto finito. Un conjunto que tal vez sea difícil de listar dado que en éste
momento pueden estar prestando y devolviendo libros, es decir hay flujo
constante.
El conjunto de
nombres de las personas que hablaron a Tombuctú el 15 de febrero del año 810 a.
C.
Éste es un conjunto finito que seguramente tendrá por lo menos un elemento.
Aunque éste tiene una característica que tal vez no concuerde con la realidad
por la cual será difícil determinar los miembros del conjunto, muchos
matemáticos dicen que no hay porque no considerarlo un conjunto.
El conjunto de
dinosaurios vivos en el Museo Británico. Asumiendo que no se están realizando
experimentos siniestros en dicho museo, éste conjunto tiene la propiedad de no
tener ningún elemento, a lo que llamamos conjunto nulo o vacío.
El conjunto de
enteros mayores que 3. Como es de suponerse, éste se trata de un conjunto infinito y
no hay ninguna dificultad para definir cualquiera de los miembros de éste
conjunto.
Desde que un
conjunto es caracterizado por sus miembros, un conjunto puede ser especificado
por declaración cuando un objeto está en el conjunto. Un conjunto finito puede
ser especificado explícitamente por una lista de sus elementos. Los elementos
de la lista deben ser separados por comas y la lista encerrada en llaves ( { } ), como lo muestran los siguientes ejemplos:
El conjunto que
contiene los elementos A, B y C está denotado por { A, B, C }.
El conjunto que
contiene todos los enteros pares no negativos menores que 10 es especificado
por { 0, 2, 4, 6, 8 }.
Los elementos de un
conjunto infinito no pueden ser listados explícitamente; en consecuencia,
necesitamos una forma para describirlos implícitamente. La especificación
implícita frecuentemente es hecha por el significado de predicados con una
variable libre. El conjunto es definido de manera que los elementos del
universo establecido por el conjunto hagan el predicado verdadero. De aquí, si
P (x) es un predicado con una variable libre, el conjunto { x
| P(x) } denota el conjunto S tal que c Î S si y sólo si P
(c) es verdadero.
Los siguientes
ejemplos son de especificaciones implícitas de conjuntos. Las dos primeras son
de conjuntos infinitos; la tercera es un conjunto finito.
El conjunto de
enteros mayores que 10 es especificado por
{ x | x Î I
Ù x >10 }
El conjunto de
enteros pares puede ser especificado como
{ x | $y [ y Î I Ù x = 2y ] }
El conjunto { 1, 2, 3, 4, 5 } puede ser especificado como
{ x | x Î I
Ù 1 £ x £ 5 }
Significados menos
formales son usados frecuentemente para describir conjuntos. Una técnica es
colocar las especificaciones del conjunto a la izquierda de una barra vertical,
como lo muestran los siguientes ejemplos:
El conjunto de
enteros múltiplos de 3 puede ser especificado por
{ 3x | x Î I } en lugar de
{ x | $y [ y Î I Ù x = 3y ] }.
El conjunto de
números racionales puede ser especificado por
{ x / y | x, y Î I
Ù y ¹ 0 }.
Si un conjunto es
finito pero muy largo como para listarse fácilmente o si es un conjunto
infinito, las elipses suelen ser usadas para especificar implícitamente un
conjunto. Las siguientes especificaciones usan elipses para caracterizar una
lista de los elementos de un conjunto.
El conjunto de
enteros del 1 al 50 es especificado por
{ 1, 2, 3, …, 50 }
El conjunto de
enteros pares no negativos es especificado por
{ 0, 2, 4, 6, … }
Todas éstas técnicas
informales de especificaciones de conjuntos son convenientes por lo cual
podemos usarlas libremente.
En un desarrollo más
formal de la teoría de conjuntos, el siguiente axioma es usado para establecer
que los conjuntos son completamente especificados por sus elementos. El axioma
nos sirve como una definición de igualdad de conjuntos.
Axioma de Extensión: Dos conjuntos A y B
son iguales si y sólo si tienen los mismos elementos.
El axioma de
extensión puede ser expresado en notación lógica de dos maneras:
A = B Û "x [ x Î A Û x Î B ]
A = B Û { "x [ x Î A Þ x Î B ] Ù "x [ x Î B Þ x Î A ]}
El axioma de
extensión declara que si dos conjuntos tienen los mismos elementos, aún sin
considerar como están especificados, son iguales. Es decir, si un conjunto es
especificado explícitamente con una lista, el orden en el que esté listado es
irrelevante. Por ejemplo: el conjunto denotado por { A,
B, C } es el mismo que (igual a) el conjunto denotado por { C, B, A } y { B, C,
A }. Además, no importa el número de veces que aparezca un elemento en el
conjunto,
{ A, B, A }, { A, B} y
{ A, A, A, B, B }
Son diferentes especificaciones de un
mismo conjunto. Un conjunto finito puede ser caracterizado implícita o
explícitamente, como lo demuestran los conjuntos
{ 1, 2, 3, 4, 5
} y { x | x Î I
Ù 1 £ x £ 5
}
que son el mismo
conjunto. También, el mismo conjunto puede ser especificado implícitamente con
diferentes predicados, por ejemplo: el conjunto { x | x =0 } y { x | x Î I
Ù -1 < x < 1 } son iguales.
OPERACIONES
CON CONJUNTOS
Existen operaciones
que nos permiten crear nuevos conjuntos a partir de otros conocidos. Definimos
la unión A È B y la intersección
A Ç B de dos conjuntos A y B como sigue:
A È B = { x : x Î A o x Î B o
ambas }
A Ç B = { x : x Î A y x Î B }
Añadimos “o ambas”
para dar énfasis y claridad a la definición de A È B. En español la
palabra o tiene dos significados. A veces es el o inclusivo
que significa lo uno, lo otro o ambos. Esta es la interpretación cuando un
programa de estudios dice: se deben incluir dos años de ciencias o dos años de
matemáticas. Otras veces o es el o exclusivo y significa
lo uno o lo otro pero no ambas. Es el o que se utiliza en un menú que ofrece
sopa o ensalada. En matemáticas siempre utilizamos o como el o inclusivo
mientras que no se especifique lo contrario. Dos conjuntos A y B son disjuntos
si no tienen elementos comunes, es decir, si
A Ç B = Æ.
Para dos conjuntos A
y B, el complemento relativo A \ B es el conjunto de elementos que están
en A y no están en B.
A \ B = { x : x Î A y x Ï B } = { x Î A : x Ï B }
Es el conjunto que
se obtiene al quitar de A los elementos que están en B
Existen operaciones
que nos permiten crear nuevos conjuntos a partir de otros conocidos. Definimos
la unión A È B y la intersección A Ç B de dos conjuntos A
y B como sigue:
A È B = { x : x Î A o x Î B o
ambas }
A Ç B = { x : x Î A y x Î B }
Añadimos “o ambas”
para dar énfasis y claridad a la definición de A È B. En español la palabra o tiene dos significados.
A veces es el o inclusivo que significa lo uno, lo otro o ambos. Esta es
la interpretación cuando un programa de estudios dice: se deben incluir dos
años de ciencias o dos años de matemáticas. Otras veces o es el o
exclusivo y significa lo uno o lo otro pero no ambas. Es el o que se
utiliza en un menú que ofrece sopa o ensalada. En matemáticas siempre
utilizamos o como el o inclusivo mientras que no se especifique lo
contrario. Dos conjuntos A y B son disjuntos si no tienen elementos
comunes, es decir, si A Ç B = Æ.
Para dos conjuntos A
y B, el complemento relativo A \ B es el conjunto de elementos que están
en A y no están en B.
A \ B = { x : x Î A y x Ï B } = { x Î A : x Ï B }
Es el conjunto que se obtiene al quitar de A
los elementos que están en B.
La diferencia simétrica A Å
B de
los conjuntos A y B es el conjunto
A Å B = (A È B) \ (A Ç B) = (A \ B) È (B \ A)
A veces es
conveniente ilustrar las relaciones entre conjuntos con dibujos llamados diagramas
de Venn, en donde los conjuntos corresponden a subconjuntos del plano.
Ejemplo:
Sea A = {n Î N : n ≤
7}, B = {n Î N : n es par y n ≤ 16}
y E = {n Î N : n es par}. Entonces tenemos
A È B =
{0,1,2,3,4,5,6,7,8,10,12,14,16},
A Ç B = {0,2,4,6},
A \ B = {1,3,5,7},
B \ A = {8,10,12,14,16},
A Å B = {1,3,5,7,8,10,12,14,16}.
En
general es conveniente trabajar en un conjunto finito como N, R o∑*. Esto es, conviene
fijar un conjunto U que llamamos conjunto universal o universo, y
considerar solamente elementos de U y subconjuntos de U. Para A Í U el complemento
relativo U \ A recibe el nombre de complemento absoluto o
sencillamente complemento y se denota por Ac. Nótese
que el complemento relativo A \ B puede escribirse en términos del complemento
absoluto: A \ B = A Ç Bc
Ejemplo:
Nótese que los dos
últimos diagramas de Venn muestran que AC Ç BC = (A È B)c.
Esta identidad de conjuntos y muchas más son verdaderas en general. A
continuación se muestran algunas identidades para conjuntos y operaciones entre
conjuntos, muchas de ellas son análogas a las leyes de álgebra. Las leyes de
idempotencia son nuevas, se supone que todos los conjuntos de la siguiente
tabla son subconjuntos de algún conjunto universal U.
|
Leyes de álgebra de conjuntos |
|
|
A È B = B È A A Ç B = B Ç A |
Leyes conmutativas |
|
(A È B) È C = A È (B È C) (A Ç B) Ç C = A Ç (B Ç C) |
Leyes asociativas |
|
A È (B Ç C) =
(A È B) Ç (A È C) A Ç (B È C) =
(A Ç B) È (A Ç C) |
Leyes
distributivas |
|
A È A = A A Ç A = A |
Leyes de la
idempotencia |
|
A È Æ = A A È U = U A Ç Æ = Æ A Ç U = A |
Leyes de Identidad |
|
(Ac )c =
A A È Ac = U A Ç Ac = Æ Uc = Æ Æc = U |
Complementación |
|
(A È B)c = (A Ç B)c = |
Leyes de DeMorgan |
Gracias a las leyes
asociativas podemos escribir los conjuntos A È B È C y A Ç B Ç C sin paréntesis y
no causar confusión.
Las pruebas que utilizan
diagramas de Venn parecen mucho más fáciles que las pruebas en las que
analizamos las inclusiones mediante elementos. Los diagramas de Venn para A, B,
C tiene 8
regiones y comprenden todas las posibilidades lógicas por lo que las
demostraciones que utilizan diagramas de Venn son de hecho válidas.
Una objeción mucho más seria para las
demostraciones con diagramas de Venn es que ocultan los procesos de pensamiento
que se requieren para llevarlas a cabo; es decir, no se especifica la lógica
que debe utilizarse para sombrear los diagramas. Otra razón para no utilizar
diagramas de Venn es que son muy difíciles de dibujar cuando hay más de tres
conjuntos.
Las cadenas de
símbolos juegan un papel importante en las ciencias computacionales. Programas
computacionales, documentos escritos en texto, fórmulas matemáticas y teoremas
en un sistema formal son objetos que representamos convencionalmente como
secuencias finitas de símbolos. Así, para poder escribir programas que
manipulen otros programas, programas editores de texto, programas para
manipular fórmulas algebraicas o programas que prueben teoremas debemos de
tener las herramientas necesarias para la manipulación de cadenas individuales
y conjuntos de cadenas.
El símbolo å denotará un
alfabeto finito y å* será el conjunto de
todas las cadenas de longitud finita formados por los símbolos provenientes de å. La principal operación sobre los
elementos de å* es la
concatenación.
Sea å un alfabeto y x y y elementos de å*. Si x =a1
a2… am y y = b1 b2... bn
donde ai, bj Î å y m, n Î N entonces la concatenación
de x con y, denotada x·y, o simplemente xy,
es la cadena xy = a1 a2… am b1
b2... bn. Si x =L, entonces xy = y
para toda x; similarmente si y = L, entonces xy=
x
Lo siguiente es una
notación conveniente para representar la concatenación de una cadena con sí
misma n veces. Esta definición inductiva es basada en la definición de N
y además no requiere cláusula extrema.
Sea x un
elemento de å*. Para cada n Î N, la cadena
xn es definido como sigue:
1. x0 = L
2. xn+1 = x0· x
Como por ejemplo, si
å = {a, b} y x = ab, entonces x0 = L, x1 = ab, x2
= abab, x3 = ababab.
Con frecuencia trataremos colecciones de cadenas en vez
de cadenas individuales. Por ejemplo, en una especificación de lenguaje de
programación, deberemos de caracterizar conjuntos enteros de programas los
cuales pueden ser escritos en el lenguaje. Dada la importancia de estos
elementos, una considerable estructura de terminologías y notaciones han sido
desarrolladas para concordar con esto.
Sea å un alfabeto finito.
Un lenguaje sobre å es un subconjunto de å*. Por ejemplo, el
conjunto {a, ab, abb} es un lenguaje sobre å = {a, b}.
Desde que cada
lenguaje es un conjunto la colección usual de operaciones de conjuntos vistas
en este documento pueden ser aplicadas a los lenguajes. De cualquier modo, dado
que son colecciones de cadena, hay otras operaciones de lenguaje importantes
que pueden ser definidas también, muchas de las cuales son basadas en las
operaciones de concatenación. Estas operaciones son importantes en una variedad
de áreas de aplicación así como también para el estudio de modelos de
computación.
Sea A y B
lenguajes sobre å. El conjunto producto de A con B, denotado
como A · B, o
simplemente AB, es el lenguaje AB = { xy 1 x Î A Ù y Î B }.
El lenguaje AB
consiste en todas las cadenas formadas por la concatenación de un elemento de A
con un elemento de B. Se debe hacer notar que en general AB ¹ BA ya que la
operación de producto de conjunto no es conmutativa.
Sea A, B, C y D
lenguajes arbitrarios sobre å, de lo cual se
obtienen las siguientes relaciones:
a)
AÆ = ÆA = Æ
b)
A{ L } = { L } A = A
c)
( AB) C = A( BC )
d)
Si A Ì B y C Ì D, entonces AC Ì BD
e)
A(B È C) = AB È AC
f)
( B È C ) A =
BA È CA
g)
A ( B Ç C) Ì AB AC
h)
( B Ç C) A Ì BA Ç CA
Sea A un lenguaje sobre å. El lenguaje An es
definido inductivamente como sigue:
A0 = { L }
An+1 = An
· A
El lenguaje An es
un conjunto de productos de A con si mismo n veces. Además si zÎ An con n
³ 1, entonces z = w1w2... wn,
donde wi Î A para cada i desde 1 hasta n.
DEFINICIÓN INDUCTIVA DE CONJUNTOS
Una definición
inductiva de conjuntos consiste en tres componentes distintivos:
1. La base, o cláusula
base, de la definición establece los objetos determinados que están en el
conjunto. Ésta parte de la definición tiene una doble función
2. La inducción,
o cláusula inductiva, de una definición inductiva establece el camino
por el cuál los elementos de un conjunto pueden ser combinados para obtener
nuevos elementos. La cláusula inductiva siempre asegurará que si los objetos x,
y, … , z son elementos de un conjunto, entonces pueden
ser combinados de varias formas de tal manera que podemos obtener un nuevo
elemento que también formará parte de
conjunto. Así, mientras la cláusula base describe la construcción de bloques de
un conjunto, la cláusula inductiva describe las operaciones que se puede llevar
a cabo sobre los objetos para la construcción de nuevos elementos del conjunto.
3. La cláusula
extrema enfatiza que a menos que un objeto pueda ser obtenido por medio de
una aplicación finita de las clausulas base e inductiva, puede ser miembro del
conjunto. La cláusula extrema de la definición inductiva de un conjunto S tiene
una variedad de formas, como lo son:
(i)
Ningún objeto es miembro del conjunto S a menos que se obtenga
de un número finito de aplicaciones de las cláusulas base e inductiva.
(ii)
El conjunto S es el conjunto más pequeño que satisface las
cláusulas base e inductiva.
(iii) El conjunto S es el
conjunto tal que S satisface las cláusulas base e inductiva y no un propio
subconjunto de S que las satisface.
De hecho, todas éstas formas de la cláusula extrema son equivalentes. A
menudo la cláusula extrema no está explícitamente definida en una definición
inductiva.
Si nuestro Universo
es el conjunto de enteros I, entonces una predicado definición del
conjunto E de enteros pares no negativos puede ser dado
como sigue:
E = { x | x ³ 0 Ù $y [ x =
2y ] }
El mismo conjunto
puede ser definido inductivamente como sigue:
1.
(Base) 0 Î E
2.
(Inducción) Si n Î E, entonces (n+2) Î E
(Extrema) Ningún entero es elemento
de E a menos que pueda ser mostrado como un número finito de
aplicaciones de las clausulas 1 y 2.
LÓGICA PROPOSICIONAL
En la Lógica Formal se estudian los
principios y métodos a través de los cuales podemos determinar la validez de
argumentos, desde el punto de vista solamente de su estructura, sin tomar en
cuenta el contenido semántico de las expresiones de los argumentos. De esta
manera si se argumenta que:
Todos los majadistanenses son de Majadistán
Rudistein es Majadistanense
En consecuencia,Rudistein es de
Majadistan.
En este argumento, no tomamos en cuenta si los majadistanenses
son humanos, perros, pericos o un concepto abstracto de cualquier área.
Tampoco nos importa si Rudinstein es un ciudadado de alguna
ciudad del mundo o si es el nombre de un perro.
De esta manera desde el punto de vista de su estructura este
argumento es válido.
Se hace incapié que la Lógica no se hace responsable de su
aplicación a nivel semántico.
Se puede decir que la Lógica es una herramienta para el análisis
de la veracidad de argumentos en base sólo a la estructura de éstos, donde el
significado de los elementos que intervienen no es tomado en cuenta.
El argumento anterior tiene dos partes principales:
A) Las premisas:
Todos los majadistanenses son de Majadistán
Rudistein es Majadistanense
B) La conclusión:
Rudistein es de Majadistán
De esta manera el argumento es válido, ya que de las premisas
sigue la conclusión, lo cual hasta cierto punto nos parece totalmente natural.
Consideremos el siguiente argumento:
Argentina está en Africa o Argentina está en
Asia.
Argentina no está en Asia
En consecuencia, Argentina está en Africa.
Nuevamente este argumento es válido desde el punto de vista
lógico, aún cuando sabemos que la conclusión es falsa.
¿Cómo puede ser ésto? ¿A partir de la Lógica se pueden obtener conclusiones
equivocadas?
La respuesta es afirmativa, ya que la lógica no verifica
el significado de las premisas.
Debido a lo anterior es necesario distinguir entre proposiciones
verdaderas y proposiciones lógicamente verdaderas.
Las primeras son verdaderas independientemente de su estructura,
mientras que las segundos no lo son. De esta manera,
las proposiciones:
Argentina está en Africa o Argentina está en Asia
Argentina está en Africa
Son verdaderas lógicamente debido a que la primera es una
premisa y a que la segunda ha sido derivada lógicamente de sus premisas.
Las proposiciones son expresiones que pueden ser evaluadas
como verdaderas o falsas.
En los lenguajes naturales (Español, Inglés, etc), las
proposiciones sólo pueden ser expresiones declarativas y nunca interrogativas o
imperativas.
De esta manera las siguientes son proposiciones:
Los cantantes no
duermen.
Comer mucho, engorda
Las montañas cantan bonito
Los mosquitos viven menos de un año
El hombre desciende del elefante
Sin embargo, las siguientes no son proposiciones por no poder
ser evaluadas como verdaderas ni falsas:
¡Levántate temprano!
¿Has entendido lo que es una
proposición?
¡Estudia esta lección!
¿Cuál es la dirección de la página
de Lógica Computacional?
En este módulo estudiamos la lógica proposicional, es decir, se
estudian los principios para determinar la validez de argumentos conformados
con proposiciones. Esto involucra los siguientes tipos de proposiciones:
* Proposiciones simples o átomos
* Proposiciones compuestas
Los átomos o proposiciones simples son tales que no es posible
encontrar en ellas otras proposiciones, mientras que las proposiciones
compuestas están conformadas de varias proposicones simples a través de lo que
se denomina conectores lógicos, entre los cuales se encuentran: y, o, implica.
Ejemplo de proposiciones compuestas son:
Las montañas cantan
bonito o Los mosquitos viven menos de un año.
El hombre desciende
del elefante y Comer mucho, engorda.
La lógica proposicional es la más antigua y simple de las formas
de lógica. Utilizando una representación primitiva del lenguaje, permite
representar y manipular aserciones sobre el mundo que nos rodea. La lógica
proposicional permite el razonamiento, a través de un mecanismo que primero
evalúa sentencias simples y luego sentencias complejas, formadas mediante el
uso de conectivos proposicionales, por ejemplo Y (AND), O (OR). Este mecanismo
determina la veracidad de una sentencia compleja, analizando los valores de
veracidad asignados a las sentencias simples que la conforman.
Una proposición es una sentencia simple que tiene un valor
asociado ya sea de verdadero (V), o falso (F). Por ejemplo:
Hoy es Viernes
Ayer llovió
Hace frío
La lógica proposicional, permite la asignación de un valor
verdadero o falso para la sentencia completa, no tiene facilidad par analizar
las palabras individuales que componen la sentencia. Por este motivo, la
representación de las sentencias del ejemplo, como proposiciones, sería:
hoy_es_Viernes
ayer_llovió
hace_frío
La proposiciones pueden combinarse para expresar conceptos más
complejos. Por ejemplo:
hoy_es_Viernes y
hace_frío.
A la proposición anterior dada como ejemplo, se la denomina
fórmula bien formada (well-formed formula, wff). Una fórmula
bien formada puede ser una proposición simple o compuesta que tiene sentido
completo y cuyo valor de veracidad, puede ser determinado. La lógica
proposicional proporciona un mecanismo para asignar valores de veracidad a la
proposición compuesta, basado en los valores de veracidad de las proposiciones
simples y en la naturaleza de los conectores lógicos involucrados.
Los conectadores básicos de la lógica proposicional, se dan en
la Tabla 4.1. Las tablas de verdad para las operaciones básicas, se muestran en
la Tabla 4.2.
|
NOMBRE |
CONECTOR |
SÍMBOLO |
|
Conjunción Disyunción Negación Implicación Equivalencia |
AND OR NOT If-Then Igual |
^ v ~ => = |
Tabla 4.1 Conectores básicos de la lógica proposicional
|
p |
q |
Disyunción p v q |
Conjunción p ^ q |
Negación ~p |
Implicación p => q |
Equivalencia p = q |
|
V |
V |
V |
V |
F |
V |
V |
|
V |
F |
V |
F |
F |
F |
F |
|
F |
V |
V |
F |
V |
V |
F |
|
F |
F |
F |
F |
V |
V |
V |
Tabla 4.2 Tablas de verdad para operadores lógicos
El conectador de implicación, puede ser considerado como un
condicional expresado de la siguiente forma:
Si A => B va a
ser verdadero,
entonces toda vez que A
sea verdadero, B debe ser siempre verdadero.
Para los casos en los cuales A es falso, la expresión A
=> B, es siempre verdadera, independientemente de los valores lógicos
que tome B, ya que el operador de implicación no puede hacer inferencias
acerca de los valores de B.
Existen varias equivalencias en lógica proposicional, similares
a las del álgebra Booleana. Estas se dan en la Tabla 4.3.
|
DENOMINACIÓN |
REPRESENTACIÓN LÓGICA |
|
Leyes
Equipotenciales |
A => B =
~A v B A ^ ~A = F A v ~A = V |
|
Leyes
Conmutativas |
A ^ B = B ^ A A v B = B v A |
|
Leyes
Distributivas |
A ^ (B v C)
= (A ^ B) v (A ^ C) A v (B ^ C) = (A v B) ^ (A v C) |
|
Leyes
Asociativas |
A ^ (B ^ C) = (A ^ B) ^ C A v (B v C) = (A v B) v C |
|
Leyes
Absortivas |
A ^ (A v B)
= A A v (A ^ B)
= A |
|
Leyes de
DeMorgan |
~(A ^ B) =
~A v ~B ~(A v B) =
~A ^ ~B |
Tabla 4.3 Equivalencias en lógica proposicional
En la Lógica Formal se estudian los
principios y métodos a través de los cuales podemos determinar la validez de
argumentos, desde el punto de vista solamente de su estructura, sin tomar en
cuenta el contenido semántico de las expresiones de los argumentos. De esta
manera si se argumenta que:
Todos los majadistanenses son de Majadistán
Rudistein es Majadistanense
En consecuencia,Rudistein es de
Majadistan.
En este argumento, no tomamos en cuenta si los majadistanenses
son humanos, perros, pericos o un concepto abstracto de cualquier área.
Tampoco nos importa si Rudinstein es un ciudadado de alguna
ciudad del mundo o si es el nombre de un perro.
De esta manera desde el punto de vista de su estructura este
argumento es válido.
Se hace incapié que la Lógica no se hace responsable de su
aplicación a nivel semántico.
Se puede decir que la Lógica es una herramienta para el análisis
de la veracidad de argumentos en base sólo a la estructura de éstos, donde el
significado de los elementos que intervienen no es tomado en cuenta.
El argumento anterior tiene dos partes principales:
A) Las premisas:
Todos los majadistanenses son de Majadistán
Rudistein es Majadistanense
B) La conclusión:
Rudistein es de Majadistán
De esta manera el argumento es válido, ya que de las premisas
sigue la conclusión, lo cual hasta cierto punto nos parece totalmente natural.
Consideremos el siguiente argumento:
Argentina está en Africa o Argentina está en
Asia.
Argentina no está en Asia
En consecuencia, Argentina está en Africa.
Nuevamente este argumento es válido desde el punto de vista
lógico, aún cuando sabemos que la conclusión es falsa.
¿Cómo puede ser ésto? ¿A partir de la Lógica se pueden obtener conclusiones
equivocadas?
La respuesta es afirmativa, ya que la lógica no verifica
el significado de las premisas.
Debido a lo anterior es necesario distinguir entre proposiciones
verdaderas y proposiciones lógicamente verdaderas.
Las primeras son verdaderas independientemente de su estructura,
mientras que las segundos no lo son. De esta manera,
las proposiciones:
Argentina está en Africa o Argentina está en Asia
Argentina está en Africa
Son verdaderas lógicamente debido a que la primera es una
premisa y a que la segunda ha sido derivada lógicamente de sus premisas.
Las proposiciones son expresiones que pueden ser evaluadas
como verdaderas o falsas.
En los lenguajes naturales (Español, Inglés, etc), las
proposiciones sólo pueden ser expresiones declarativas y nunca interrogativas o
imperativas.
De esta manera las siguientes son proposiciones:
Los cantantes no
duermen.
Comer mucho, engorda
Las montañas cantan bonito
Los mosquitos viven menos de un año
El hombre desciende del elefante
Sin embargo, las siguientes no son proposiciones por no poder
ser evaluadas como verdaderas ni falsas:
¡Levántate temprano!
¿Has entendido lo que es una
proposición?
¡Estudia esta lección!
¿Cuál es la dirección de la página
de Lógica Computacional?
En este módulo estudiamos la lógica proposicional, es decir, se
estudian los principios para determinar la validez de argumentos conformados
con proposiciones. Esto involucra los siguientes tipos de proposiciones:
* Proposiciones simples o átomos
* Proposiciones compuestas
Los átomos o proposiciones simples son tales que no es posible
encontrar en ellas otras proposiciones, mientras que las proposiciones
compuestas están conformadas de varias proposicones simples a través de lo que
se denomina conectores lógicos, entre los cuales se encuentran: y, o, implica.
Ejemplo de proposiciones compuestas son:
Las montañas cantan
bonito o Los mosquitos viven menos de un año.
El hombre desciende
del elefante y Comer mucho, engorda.
La lógica
proposicional trabaja con sentencias u oraciones a las cuales se les puede
asociar un valor de verdad (cierto o falso); estas sentencias se conocen como
sentencias declarativas o, simplemente, proposiciones. Existen proposiciones
que son simples, así como proposiciones que están construidas por otras
proposiciones usando elementos (conectivas lógicas) que las asocian. Al
construir una proposición, se debe garantizar que esta puede ser evaluada
(fórmula bien formada); de la misma forma, podemos construir proposiciones
usando solo un grupo de conectivas, produciendo fórmulas que se dice están en
su forma normal. Las formas normales son importantes por el hecho que permiten
definir esquemas generales para el tratamiento de estas fórmulas (GSAT, por
ejemplo).
Otro
aspecto importante es el de determinar si una proposición esta construida (o
puede ser deducida) a partir de un conjunto de proposiciones, es decir, si es
una consecuencia lógica de dicho conjunto.
Finalmente,
existen varias formas de representar una fórmula de la lógica proposicional;
aquí se introduce el concepto de circuitos lógicos, donde se asocia a las
conectivas lógicas un símbolo gráfico.
2 Objetivos
Los
objetivos que se persiguen dentro de este módulo son los siguientes:
1.
El alumno distinguirá fórmulas bien formadas a partir de
oraciones en lenguaje natural para especificar y definir formalmente un
conjunto de sentencias.
2.
El alumno probará consecuencias lógicas (CL) para un conjunto de
fórmulas bien formadas, a partir de los teoremas 1 y 2 para distinguir cuando
un enunciado es verdadero ante un conjunto de axiomas, o sigue de ellos.
3 Proposiciones
Al escuchar
algo como La rosa es una flor o El cocodrilo es un mamífero,
fácilmente se puede determinar si estas sentencias son ciertas o falsas; sin
embargo, al escuchar No seas flojo! o Quién
ganará las elecciones?, no es posible asociar a ellas un valor de verdad.
Sentencias como las primeras dos son los elementos fundamentales con los que
trabaja la lógica proposicional.
La lógica
proposicional (o cálculo proposicional) tiene el propósito de simbolizar
cualquier tipo de razonamiento para su análisis y tratamiento. Específicamente,
para simbolizar razonamiento, la lógica proposicional usa sentencias
declarativas a las que se puede asociar un valor de verdad (cierto o falso); es
decir, usa proposiciones.
No existe
una notación generalmente utilizada para representar proposiciones, pero en
este curso se identifica a cada una de ellas con una letra mayúscula (o una
cadena de letras mayúsculas).
Ejemplo:
P y
Q son
proposiciones:
P : La rosa es una flor
Q : El cocodrilo es un mamífero
La
asociación de proposiciones produce otras proposiciones conocidas como
compuestas, por lo que es posible diferenciar a las proposiciones simples
llamándolas fórmulas atómicas o, simplemente átomos y a las compuestas
llamándolas fórmulas compuestas. Del ejemplo, P y Q son átomos.
4 Conectivas lógicas
La
construcción de fórmulas compuestas requiere del uso de elementos que permitan
establecer una relación entre los átomos que la forman; estos elementos se
conocen como conectivas lógicas. En la proposición ''El agua esta fría y el
calentador está descompuesto'' se tienen dos átomos (El agua esta fria,
el calentador está descompuesto), unidos por la partícula ''y''
la cual se dice que es una conectiva lógica. Otro ejemplo sería ''Si Luis es
ingeniero, entonces Luis es inteligente'', donde la conectiva lógica es ''Si ... entonces''.
Las
conectivas lógicas usadas en la lógica proposicional son cinco y son
representadas simbólicamente de varias formas, como se muestra en la tabla 1.
|
Conectiva |
Símbolos asociados |
|
Negación (No) |
~, ¬ , - |
|
Conjunción (Y) |
Ù, &, * |
|
Disyunción (O) |
Ú, |, + |
|
Condicional (Si
... entonces) |
® |
|
Bicondicional (Si
y solo si) |
« , = |
Tabla 1: Conectivas Lógicas.
Así, para
los ejemplos mencionados, se tendría la siguiente representación:
Las conectivas lógicas también se llaman a veces
operadores, y son de dos tipos:
Operadores unarios:
NEGACION:
not, ¬
Operadores binarios:
CONJUNCION: and, &, y
DISYUNCION: or
CONDICIONAL: implies,
==>,
implica
BICONDICIONAL: <==>
Ejemplo: C: ''El
agua esta fría y el calentador está descompuesto'', se representa por AÙB.
donde:
A: El agua esta fría.
B: El calentador esta
descompuesto.
Ejemplo: R: ''Si
Luis es ingeniero, entonces Luis es inteligente'', se representa
por P® Q.
donde:
P: Luis es ingeniero.
Q: Luis es
inteligente.
Como es
posible determinar si una proposición es cierta o falsa, al encontrarse con
proposiciones unidas por conectivas lógicas, es necesario conocer cuales son
las reglas que se aplican para determinar si la proposición completa es cierta
o falsa. La tabla 2 señala los valores resultantes para la evaluación de
proposiciones compuestas a partir de las diferentes combinaciones de valores de
verdad de sus átomos. En esta tabla P y Q son los átomos y se
utiliza V para un valor cierto y F para uno falso.
|
P |
Q |
¬ P |
PÙQ
|
PÚQ
|
P® Q |
P« Q |
|
V |
V |
F |
V |
V |
V |
V |
|
V |
F |
F |
F |
V |
F |
F |
|
F |
V |
V |
F |
V |
V |
F |
|
F |
F |
V |
F |
F |
V |
V |
Tabla 2: Valores de
verdad de proposiciones compuestas.
Ejemplo: Si P tiene un
valor V, Q tiene un valor F y R es
V, el valor de P® R es
V y el valor de P® Q es F.
5 Fórmulas bien formadas
Como se ha
explicado, las proposiciones compuestas son agrupaciones de átomos unidos por
conectivas lógicas; es importante aclarar que al construir proposiciones, se
requiere seguir una serie de reglas que establecen si una fórmula esta bien
formada. De acuerdo a lo anterior, una formula bien formada (fbf) es aquella
que cumple los siguientes cuatro puntos:
1.
Un átomo es una fórmula bien formada.
2.
Si P es una fórmula bien formada, ¬ P también es una fórmula bien formada.
3.
Si P y Q son fórmulas bien formadas, PÙQ, PÚQ, P® Q y P« Q son fórmulas bien formadas.
4.
Todas las fórmulas bien formadas se obtienen aplicando las
reglas 1, 2 y 3.
De lo
anterior, se puede decir que fórmulas están bien formadas y que fórmulas no lo
están:
Ejemplo: Las siguientes
son fórmulas bien formadas:
PÚ¬ Q
PÚ¬ Q® S
Ejemplo: Las siguientes
no son fórmulas bien formadas:
® S
ÚP¬
P¬ R
El Cálculo Proposicional estudia fórmulas
proposicionales simples o compuestas.
Las proposiciones
simples o átomos son representadas por símbolos, generalmente las letras del
alfabeto A,B,C,....
Para obtener
proposiciones compuestas se utilizan, como se dijo antes, conectores lógicos.
Así la proposición compuesta A or B puede corresponder por ejemplo a:
El coronel no tienen quien le escriba
or
La jubilación del Coronel Buendía
es insuficiente para su familia
Una fórmula bien
formada (fbf) es una expresión que representa una proposición simple o
compuesta, la cual esta bien escrita de acuerdo con determinada sintaxis.
Ahora bien, una fbf
del Cálculo Proposicional, es una fórmula que está bien escrita de
acuerdo con la sintaxis del Cálculo Proposicional.
Las reglas de la
sintaxis del Cálculo Proposicional definen de esta manera la forma de escribir
o reconocer susu fbf's. Estas reglas son:
a) Un átomo es una fórmula bien formada.
b) Si G es una fórmula bien formada entonces ¬G también lo
es.
c) Si G y H son fórmulas bien formadas, entonces también lo
son:
G & H
G or H
G
==> H
G <==> H
d) Todas las fbf's se obtienen aplicando a, b y c.
Es necesario
puntualizar en la regla c anterior, que es posible utilizar otras
conectivas, pero sin embargo son reducibles a las que aqui presentamos.
De esta manera,
fijaremos nuestra atención solo a las fbf's que aquí describimos.
Ejemplos de fórmulas
bien formadas son:
P & Q P ==> Q
Ejemplos de fórmulas
que no son bien formadas son: P &, ==>Q.
6 Jerarquía
de conectivas
Como se
estableció anteriormente, para determinar el valor de verdad de una proposición
compuesta, es necesario conocer cuales son las reglas que se aplican para
determinar si la proposición completa es cierta o falsa; asimismo, al tener
fórmulas con dos o más conectivas, se deben conocer las reglas de precedencia y
asociatividad de las conectivas para asegurar que la evaluación es correcta.
Aún cuando existen algunas diferencias en la determinación de una jerarquía de
conectivas, en este texto se utilizará el siguiente orden:
¬ , Ù, Ú, ® ,
«
donde ¬ (negación) es el operador con mayor jerarquía en la
secuencia y « (bicondicional) es el operador con el menor
peso.
Ejemplo: El orden de
evaluación de ¬PÚQÙR es, utilizando
paréntesis, ( (¬ P) Ú( QÙR)
) ;
es decir, primero se evalúa ¬ P,
posteriormente
QR,
y finalmente se aplica al resultado de ambas evaluaciones.
Al tener
una fórmula con la presencia de dos o mas conectivas
iguales, el orden de asociatividad siempre es de izquierda a derecha.
Ejemplo: El orden de
evaluación de P® Q® R es
( ( P® Q) ® R)
.
7 Interpretación de fórmulas
Una
interpretación de una fórmula es una asignación de valores de verdad a un
conjunto de átomos; para una fórmula con dos átomos se tienen dos posibles
interpretaciones, para una con tres se tienen ocho interpretaciones, y en
general para una fórmula con n átomos de tienen 2n
interpretaciones.
Considerando
las condiciones discutidas anteriormente, es posible determinar el valor de
verdad cualquier una fórmula de la lógica proposicional.
Ejemplo: Teniendo que P es
V, Q es F, R es V y S es
V, la interpretación para la fórmula ¬ ( P® Q)
® ( RÙS) es:
|
P |
Q |
R |
S |
P® Q |
¬ ( P® Q) |
RÙS
|
¬ ( P® Q) ® ( RÙS) |
|
V |
F |
V |
V |
F |
V |
V |
V |
En general,
para evaluar una fórmula, se deben considerar todas sus posibles
interpretaciones.
Ejemplo: La evaluación de ¬ ( P® Q) ® ( RÙS) es:
|
P |
Q |
R |
S |
P® Q |
¬ ( P® Q) |
RÙS
|
¬ ( P® Q) ® ( RÙS) |
|
V |
V |
V |
V |
V |
F |
V |
V |
|
V |
V |
V |
F |
V |
F |
F |
V |
|
V |
V |
F |
V |
V |
F |
F |
V |
|
V |
V |
F |
F |
V |
F |
F |
V |
|
V |
F |
V |
V |
F |
V |
V |
V |
|
V |
F |
V |
F |
F |
V |
F |
F |
|
V |
F |
F |
V |
F |
V |
F |
F |
|
V |
F |
F |
F |
F |
V |
F |
F |
|
F |
V |
V |
V |
V |
F |
V |
V |
|
F |
V |
V |
F |
V |
F |
F |
V |
|
F |
V |
F |
V |
V |
F |
F |
V |
|
F |
V |
F |
F |
V |
F |
F |
V |
|
F |
F |
V |
V |
V |
F |
V |
V |
|
F |
F |
V |
F |
V |
F |
F |
V |
|
F |
F |
F |
V |
V |
F |
F |
V |
|
F |
F |
F |
F |
V |
F |
F |
V |
De la
evaluación de una fórmula, se pueden definir los siguientes conceptos:
Tautología o fórmula válida:
Una fórmula es una tautología si es verdadera para todas sus posibles
interpretaciones. Una tautología también se conoce como una fórmula válida.
Contradicción, fórmula
inconsistente o fórmula insatisfactible: Una fórmula es una
contradicción si es falsa para todas sus posibles interpretaciones. Una
contradicción también se conoce como una fórmula inconsistente o una fórmula
insatisfactible.
Fórmula
consistente o fórmula satisfactible: Una fórmula que al menos tiene una
interpretación verdadera se conoce como una fórmula consistente o
satisfactible.
Fórmula
inválida: Una fórmula es inválida si es falsa para al menos una
interpretación.
Ejemplo: La fórmula ( P® Q) ÚP es una tautología,
ya que todas sus interpretaciones son verdaderas.
|
P |
Q |
P® Q |
( P® Q) ÚP |
|
V |
V |
V |
V |
|
V |
F |
F |
V |
|
F |
V |
V |
V |
|
F |
F |
V |
V |
Ejemplo: La fórmula ( P® Q) Ù¬ P es consistente, ya que de sus
interpretaciones, dos son verdaderas.
|
P |
Q |
¬ P |
P® Q |
( P® Q) Ù¬ P |
|
V |
V |
F |
V |
F |
|
V |
F |
F |
F |
F |
|
F |
V |
V |
V |
V |
|
F |
F |
V |
V |
V |
Como
consecuencia de las definiciones anteriores, se tiene que:
- Una fórmula es válida si y
solo si su negación es inconsistente.
- Una fórmula es inconsistente
si y solo si su negación es válida.
- Una fórmula es inválida si y
solo si existe por lo menos una interpretación sobre la cual la fórmula es
falsa.
- Una fórmula es consistente si
y solo si existe por lo menos una interpretación sobre la cual la fórmula
es verdadera.
- Si una fórmula es válida,
entonces es consistente, pero no viceversa.
- Si una fórmula es
inconsistente, entonces es inválida, pero no viceversa.
8 Fórmulas equivalentes
Al evaluar
las fórmulas P® Q y ¬ PÚQ se observa que todas sus interpretaciones son iguales, por lo
que se dice que ambas fórmulas son equivalentes.
Ejemplo: P® Q y ¬ PÚQ son
fórmulas
equivalentes:
|
P |
Q |
¬ P |
P® Q |
¬ PÚQ |
|
V |
V |
F |
V |
V |
|
V |
F |
F |
F |
F |
|
F |
V |
V |
V |
V |
|
F |
F |
V |
V |
V |
Existen
varias equivalencias entre fórmulas de la lógica proposicional, las cuales se
conocen como leyes de equivalencia. La tabla 3 muestra estas leyes. Se utiliza
el símbolo Tautología para indicar una tautología y el símbolo Contradicción
para indicar una contradicción.
|
Ley de
equivalencia |
Fórmula |
|
Doble
Implicación |
F«G = (F® G)Ù(G® H) |
|
Implicación |
F® G = ¬ FÚG |
|
Distribución |
FÚ(GÙH) = (FÚG)Ù(FÚH) |
|
|
FÙ(GÚH) = (FÙG)Ú(FÙH) |
|
Asociación |
(FÚG)ÚH = FÚ(GÚH) |
|
|
(FÙG)ÙH = FÙ(GÙH) |
|
Complementación
|
FÙ¬ F = Contradicción |
|
|
FÚ¬ F = Tautología |
|
|
¬ ¬ F
= F |
|
Conmutación |
FÚG = GÚF |
|
|
FÙG = GÙF |
|
Cero |
FÚTautología = Tautología |
|
|
FÙContradicción = Contradicción |
|
Identidad |
FÚContradicción = F |
|
|
FÙTautología = F |
|
Idempotencia |
FÚF = F |
|
|
FÙF = F |
|
Absorción |
FÚFÙQ
= F |
|
|
FÙ(FÚQ) = F |
|
|
FÚ¬ FÙQ = FÚQ |
|
Leyes de
Morgan |
¬ (FÚQÚH)
= ¬ FÙ¬ QÙ¬ H |
|
|
¬ (FÙQÙH)
= ¬ FÚ¬ QÚ¬ H |
Tabla 3: Leyes
de equivalencias para fórmulas lógicas.
9 Formas normales
Las leyes
de equivalencia permiten transformar fórmulas de la lógica proposicional en
otras fórmulas más simples de evaluar o que estén escritas en alguna forma que
sea útil para su manipulación. En lógica proposicional existen dos formas para
presentar fórmulas que son importantes ya que permiten definir métodos
genéricos de evaluación y análisis; estas formas se conocen como formas
normales, y en particular: forma normal conjuntiva y forma normal disyuntiva.
Forma
Normal Conjuntiva: Una fórmula está en su forma normal conjuntiva (FNC) si es una
conjunción de disyunciones, es decir, tiene la forma:
F1ÙF2Ù...ÙFn, en la cual Fn es
una fórmula construida por una agrupación de átomos unidos por disyunciones;
esto es Fn es P1P2...Pm.
En ambos casos n y m pueden ser mayores o iguales a 1.
Forma
Normal Disyuntiva: Una fórmula está en su forma normal disyuntiva (FND) si es una
disyunción de conjunciones, es decir, tiene la forma: F1F2...Fn , en la cual Fn
es una fórmula construida por una agrupación de átomos unidos por conjunciones;
esto es Fn es
P1ÙP2Ù...ÙPm.
Ejemplo:
La
fórmula ( PÚQÚR) Ù( ¬ PÚR)ÙR está en su forma
normal conjuntiva construida de tres funciones F1:PÚQÚR, F2:¬
PÚR y F3:R. Cada función es una
agrupación de átomos unidos por disyunciones.
Ejemplo:
La
fórmula (
PÙQÚR) Ù( ¬ PÚR)ÙR no está en su forma
normal conjuntiva.
Para poder
transformar cualquier fórmula a su forma normal (conjuntiva o disyuntiva), es
necesario aplicar la siguiente secuencia de operaciones de equivalencia sobre
la fórmula original:
1.
Sustituir todas las ocurrencias de conectivas ® y « en la fórmula usando
las correspondientes leyes de equivalencia.
2.
Asegurarse que las negaciones afecten solo a átomos, usando las
leyes de Morgan y la eliminación de dobles negaciones.
3.
Aplicar las otras leyes para encontrar la forma normal (las
principales leyes que se aplican son las distributivas).
Ejemplo: La forma normal
conjuntiva de P® Q® S es ( PÚS) Ù( ¬ QÚS) ya que aplicando las reglas anteriores:
Se
eliminan las condicionales P® Q por ¬ PÚQ y ( ¬ PÚQ) ® S por
¬ ( ¬ PÚQ) ÚS.
Se pasan
las negaciones a los átomos usando leyes de Morgan produciendo ¬ ¬ PÙ¬ QÚS.
Se
elimina la doble negación resultando PÙ¬ QÚS.
Como la
conjunción tiene mayor prioridad, se distribuye la disyunción, quedando ( PÚS) Ù( ¬ QÚS) , que ya esta en la forma normal conjuntiva.
Ejemplo: La forma normal
disyuntiva de P® Q® S es
PÙ¬ QÚS.
10 Consecuencias lógicas
Otro
concepto importante en la lógica proposicional es el de consecuencia lógica.
Uno de los aspectos a analizar en la lógica proposicional es el de determinar
la validez de argumentos representados por fórmulas bien formadas. Un argumento
esta formado por las premisas, axiomas o postulados y por una conclusión,
objetivo o consecuencia lógica. Las premisas son proposiciones que son base
para la deducción de una conclusión o consecuencia.
Así, en
términos de la lógica proposicional, una consecuencia lógica es aquella fórmula
(G) que es derivada de un grupo de fórmulas (F) cumpliendo la
restricción de ser verdadera para todas las interpretaciones verdaderas del
grupo de fórmulas (F). Esto es, G es una consecuencia lógica de
las premisas F, si y solo si, al ser verdaderas las premisas, G
siempre es verdadera.
Para probar
si una fórmula es una consecuencia lógica de un grupo de fórmulas se tienen dos
métodos, que se producen a partir de los conceptos de validez e inconsistencia.
Estos métodos se conocen en forma de teoremas:
Teorema
1:
Teniendo un grupo de fórmulas F1, F2,...,Fn y otra llamada G, G es
una consecuencia lógica de F1, F2,...,Fn
si y solo si la fórmula ( F1ÙF2Ù¼ÙFn) ® G es válida.
Teorema
2:
Teniendo un grupo de fórmulas F1, F2,...,Fn y otra llamada G, G es
una consecuencia lógica de F1, F2,...,Fn
si y solo si la fórmula F1ÙF2Ù¼ÙFnÙ¬ G es inconsistente.
Para
demostrar si G es una consecuencia lógica se pueden usar tablas de
verdad o aplicar las leyes de equivalencia para encontrar su forma normal.
Ejemplo: U es una
consecuencia lógica de ( ¬ PÚS) Ù( ¬ SÚU) ÙP ya que:
1)
Definición de consecuencia lógica:
Aplicando
la definición de consecuencia lógica y aplicando tablas de verdad se tiene que:
|
P |
S |
U |
¬ P |
¬ S |
¬ PÚS |
¬ SÚU |
( ¬ PÚS) Ù(
¬ SÚU)ÙP |
|
V |
V |
V |
F |
F |
V |
V |
V |
|
V |
V |
F |
F |
F |
V |
F |
F |
|
V |
F |
V |
F |
V |
F |
V |
F |
|
V |
F |
F |
F |
V |
F |
V |
F |
|
F |
V |
V |
V |
F |
V |
V |
F |
|
F |
V |
F |
V |
F |
V |
F |
F |
|
F |
F |
V |
V |
V |
V |
V |
F |
|
F |
F |
F |
V |
V |
V |
V |
F |
Se
observa que U es verdadero para la única interpretación verdadera de ( ¬ PÚS)Ù( ¬ SÚU) ÙP.
2)
Teorema 1:
Usando
tablas de verdad la fórmula
( ( ¬PÚS) Ù( ¬ SÚU) ÙP) ® U es una fórmula válida.
|
( ¬ PÚS) Ù(
¬ SÚU) ÙP |
U |
( ( ¬PÚS) Ù(
¬ SÚU) ÙP) ® U |
|
V |
V |
V |
|
F |
F |
V |
|
F |
V |
V |
|
F |
F |
V |
|
F |
V |
V |
|
F |
F |
V |
|
F |
V |
V |
|
F |
F |
V |
Otra
forma es transformando la fórmula original en su forma normal disyuntiva:
|
( ( ¬ PÚS) Ù(
¬SÚU) ÙP) ® U |
|
|
¬ ( ( ¬ PÚS) Ù(
¬ SÚU) ÙP) ÚU |
eliminado condicional |
|
( ¬ ( ¬ PÚS) Ú¬
( ¬ SÚU) Ú¬ P) ÚU |
aplicando De Morgan |
|
( ( ¬ ¬ PÙ¬ S) Ú( ¬ ¬ SÙ¬ U) Ú¬ P) ÚU |
aplicando De Morgan |
|
( ( PÙ¬ S) Ú( SÙ¬ U) Ú¬ P) ÚU |
aplicando De Morgan |
|
( PÙ¬ S) Ú( SÙ¬ U) Ú¬ PÚU |
eliminando paréntesis innecesarios |
|
( PÙ¬ S) Ú¬ PÚ( SÙ¬ U) ÚU |
aplicando la ley conmutativa |
|
( ( PÚ¬ P) Ù( ¬ SÚ¬ P) ) Ú( SÙ¬ U) ÚU |
distribuyendo ¬ P en P¬ S |
|
( Tautología Ù( ¬ SÚ¬ P) ) Ú( SÙ¬ U) ÚU |
aplicando complementación en P¬ P |
|
( ¬ SÚ¬ P) Ú( SÙ¬ U) ÚU |
aplicando identidad en Tautología ( ¬ S¬
P) |
|
( ¬ SÚ¬ P) Ú( ( SÚU) Ù(
¬ UÚU) ) |
distribuyendo U en S¬ U |
|
( ¬ SÚ¬ P) Ú( ( SÚU) ÙTautología
) |
aplicando complementación en ¬ UU |
|
( ¬ SÚ¬ P) Ú( SÚU) |
aplicando identidad en ( SU)
Tautología |
|
¬ SÚ¬ PÚSÚU
|
eliminando paréntesis innecesarios |
|
Tautología Ú¬ PÚU |
aplicando complementación en ¬ SS |
|
Tautología |
aplicando complementación en Tautología ¬ PU |
2) Teorema 2:
Usando
tablas de verdad la fórmula
( ( ¬PÚS) Ù( ¬ SÚU) ÙP) Ù¬ U es una fórmula inconsistente.
|
( ¬ PÚS) Ù(
¬ SÚU) ÙP |
U |
¬ U |
(( ¬ PÚS) Ù(
¬ SÚU) ÙP) Ù¬ U |
|
V |
V |
F |
F |
|
F |
F |
V |
F |
|
F |
V |
F |
F |
|
F |
F |
V |
F |
|
F |
V |
F |
F |
|
F |
F |
V |
F |
|
F |
V |
F |
F |
|
F |
F |
V |
F |
LAS TENDENCIAS EN
LOS LENGUAJES DE PROGRAMACIÓN
El estudio de los lenguajes de programación agrupa tres
intereses diferentes; el del programador profesional, el del diseñador del
lenguaje y del Implementador del lenguaje.
Además, estos tres trabajos han de realizarse dentro de las
ligaduras y capacidades de la organización de una computadora y de las
limitaciones fundamentales de la propia "calculabilidad". El termino
"el programador" es un tanto amorfo, en el sentido de que camufla
importantes diferencias entre distintos niveles y aplicaciones de la
programación. Claramente el programador que ha realizado un curso de doce
semanas en COBOL y luego entra en el campo del procesamiento de datos es
diferente del programador que escribe un compilador en Pascal, o del
programador que diseña un experimento de inteligencia artificial en LISP, o del
programador que combina sus rutinas de FORTRAN para resolver un problema de
ingeniería complejo, o del programador que desarrolla un sistema operativo
multiprocesador en ADA.
En esta investigación, intentaremos clarificar estas
distinciones tratando diferentes lenguajes de programación en el contexto de
cada área de aplicación diferente. El "diseñador del lenguaje" es
también un termino algo nebuloso. Algunos lenguajes (como APL y LISP) fueron
diseñados por una sola persona con un concepto único, mientras que otros
(FORTRAN y COBOL) son el producto de desarrollo de varios años realizados por
comités de diseño de lenguajes.
El "Implementador del lenguaje" es la persona o grupo
que desarrolla un compilador o interprete para un lenguaje sobre una maquina
particular o tipos de maquinas. Mas frecuentemente, el primer compilador para
el lenguaje Y sobre la maquina X es desarrollada por la corporación que
manufactura la maquina X . Por ejemplo, hay varios
compiladores de Fortran en uso; uno desarrollado por IBM para una maquina IBM,
otro desarrollado por DEC para una maquina DEC, otro por CDC, y así
sucesivamente. Las compañías de software también desarrollan compiladores y
también lo hacen los grupos de investigación de las universidades. Por ejemplo,
la universidad de Waterloo desarrolla compiladores para FORTRAN Y PASCAL, los cuales
son útiles en un entorno de programación de estudiantes debido a su superior
capacidad de diagnostico y velocidad de compilación.
Hay también muchos aspectos compartidos entre los programadores,
diseñadores de un lenguaje implementadores del mismo. Cada uno debe comprender
las necesidades y ligaduras que gobiernan las actividades de los otros dos.
Hay, al menos, dos formas fundamentales desde las que pueden
verse o clasificarse los lenguajes de programación: por su nivel y por
principales aplicaciones. Además, estas visiones están condicionadas por la
visión histórica por la que ha transcurrido el lenguaje. Además, hay cuatro
niveles distintos de lenguaje de programación.
Los "Lenguajes Declarativos" son los mas parecidos al castellano o ingles en su potencia
expresiva y funcionalidad están en el nivel mas alto respecto a los otros. Son
fundamentalmente lenguajes de ordenes, dominados por sentencias que expresan
"Lo que hay que hacer" en ves de "Como hacerlo". Ejemplos
de estos lenguajes son los lenguajes estadísticos como SAS y SPSS y los
lenguajes de búsqueda en base de datos, como NATURAL e IMS. Estos lenguajes se
desarrollaron con la idea de que los profesionales pudieran asimilar mas rápidamente el lenguaje y usarlo en su trabajo, sin
necesidad de programadores o practicas de programación.
Los lenguajes de " Alto Nivel" son los mas utilizados como lenguaje de programación. Aunque no son
fundamentalmente declarativos, estos lenguajes permiten que los algoritmos se
expresen en un nivel y estilo de escritura fácilmente legible y comprensible
por otros programadores. Además, los lenguajes de alto nivel tienen normalmente
las características de " Transportabilidad". Es decir, están
implementadas sobre varias maquinas de forma que un programa puede ser
fácilmente " Transportado " (Transferido) de una maquina a otra sin
una revisión sustancial. En ese sentido se llama "Independientes de la
maquina". Ejemplos de estos lenguajes de alto nivel son PASCAL
, APL y FORTRAN (para aplicaciones científicas ), COBOL (para
aplicaciones de procesamiento de datos), SNOBOL( para aplicaciones de
procesamiento de textos), LISP y PROLOG (para aplicaciones de inteligencia
artificial), C y ADA (para aplicaciones de programación de sistemas) y PL/I
(para aplicaciones de propósitos generales) .
Los "Lenguajes Ensambladores" y los "Lenguajes
Maquina" son dependientes de la maquina. Cada tipo de maquina, tal como
VAX de digital, tiene su propio lenguaje maquina distinto y su lenguaje
ensamblador asociado. El lenguaje Ensamblador es simplemente una representación
simbólica del lenguaje maquina asociado, lo cual permite una programación menos
tediosa que con el anterior. Sin embargo, es necesario un conocimiento de la
arquitectura mecánica subyacente para realizar una programación efectiva en
cualquiera de estos niveles lenguajes.
Los siguiente tres segmentos del programa equivalentes exponen
las distinciones básicas entre lenguajes maquina, ensambladores de alto nivel:
Como muestra este ejemplo, a mas bajo
nivel de lenguaje mas cerca esta de las características de un tipo e maquina
particular y mas alejado de ser comprendido por un humano ordinario. Hay
también una estrecha relación ( correspondencia 1:1 )
entre las sentencias en lenguaje ensamblador y sus formas en lenguaje maquina
codificada. La principal diferencia aquí es que los lenguajes ensambladores se
utilizan símbolos (X,Y,Z,A para " sumar", M
para "multiplicar"), mientras que se requieren códigos numéricos
(OC1A4, etc.) para que lo comprenda la maquina.
La programación de un lenguaje de alto nivel o en un lenguaje
ensamblador requiere, por tanto, algún tipo de interfaz con el lenguaje maquina
para que el programa pueda ejecutarse. Las tres interfaces mas comunes: un
"ensamblador" , un "compilador" y
un "interprete". El ensamblador y el compilador traduce el programa a
otro equivalente en el lenguaje X de la maquina "residente" como un
paso separado antes de la ejecución. Por otra parte, el interprete
ejecuta directamente las instrucciones en un lenguaje Y de alto nivel, sin un
paso de procesamiento previo.
La compilación es, en general, un proceso mas eficiente que la
interpretación para la mayoría de los tipos de maquina. Esto se debe
principalmente a que las sentencias dentro de un "bucle" deben ser
reinterpretadas cada vez que se ejecutan por un interprete.
Con un compilador. Cada sentencia es interpretada y luego traducida a lenguaje
maquina solo una vez.
Algunos lenguajes son lenguajes principalmente interpretados,
como APL, PROLOG y LISP. El resto de los lenguajes -- Pascal, FORTRAN, COBOL,
PL/I, SNOBOL, C, Ada y Modula-2 – son normalmente lenguajes compilados. En
algunos casos, un compilador estará utilizable alternativamente para un
lenguaje interpretado (tal como LISP) e inversamente (tal como el interprete
SNOBOL4 de los laboratorios Bell). Frecuentemente la interpretación es
preferible a la compilación en un entorno de programación experimental o de
educación, donde cada nueva ejecución de un programa implicado un cambio en el
propio texto del programa. La calidad de diagnosis y depuración que soportan
los lenguajes interpretados es generalmente mejor que la de los lenguajes
compilados, puesto que los mensajes de error se refieren directamente a
sentencias del texto del programa original. Además, la ventaja de la eficiencia
que se adjudica tradicionalmente a los lenguajes compilados frente a los
interpretados puede pronto ser eliminado, debido a la evolución de las maquinas
cuyos lenguajes son ellos mismos1lenguajes de alto nivel. Como ejemplo de estos
están las nuevas maquinas LISP, las cuales han sido diseñadas recientemente por
Symbolics y Xerox Corporations.
Los lenguajes de Programación son tomados de diferentes
perspectivas. Es importante para un programador decidir cuales conceptos emitir
o cuales incluir en la programación. Con frecuencia el programador es osado a
usar combinaciones de conceptos que hacen al lenguaje "DURO" de usar,
de entender e implementar. Cada programador tiene en mente un estilo particular
de programación, la decisión de incluir u omitir ciertos tipos de datos que
pueden tener una significativa influencia en la forma en que el Lenguaje es
usado, la decisión de usar u omitir conceptos de programación o modelos.
Existen cinco estilo de programación y
son los siguientes:
1.
Orientados a Objetos.
2.
Imperativa : Entrada, procesamiento y salidas de Datos.
3.
Funcional : "Funciones", los datos son funciones, los resultados
pueden ser un valor o una función.
4.
Lógico : {T,F} + operaciones lógicos (Inteligencia Artificial).
5.
Concurrente : Aún esta en proceso de investigación.
El programador, diseñador e implementador de un lenguaje de
programación deben comprender la evolución histórica de los lenguajes para
poder apreciar por que presentan características diferentes. Por ejemplo, los lenguajes
"mas jóvenes" desaconsejan (o prohiben) el uso de las sentencias GOTO
como mecanismo de control inferior, y esto es correcto en el contexto de las
filosofías actuales de ingeniería del software y programación estructurada.
Pero hubo un tiempo en que la GOTO, combinada con la IF, era la única
estructura de control disponible; el programador no dispone de algo como la
construcción WHILE o un IF-THEN-ELSE para elegir. Por tanto, cuando se ve un
lenguaje como FORTRAN, el cual tiene sus raíces en los comienzos de la historia
de los lenguajes de programación, uno no debe sorprenderse de ver la antigua
sentencia GOTO dentro de su repertorio.
Lo mas importante es que la historia
nos permite ver la evolución de familias de lenguajes de programación, ver la influencia
que ejercer las arquitecturas y aplicaciones de las computadoras sobre el
diseño de lenguajes y evitar futuros defectos de diseño aprendido las lecciones
del pasado. Los que estudian se han elegido debido a su mayor influencia y
amplio uso entre los programadores, así como por sus distintas características
de diseño e implementacion. Colectivamente cubren los aspectos más importantes
con los que ha de enfrentarse el diseñado de lenguajes y la mayoría de las
aplicaciones con las que se enfrenta el programador. Para los lectores que
estén interesados en conocer con mas detalle la
historia de los lenguajes de programación recomendamos las actas de una recién
conferencia (1981) sobre este tema, editadas por Richard Wexelblat. Vemos que
FORTRAN I es un ascendente directo de FORTRAN II, mientras que FORTRAN, COBOL,
ALGO 60, LISP, SNOBOL y los lenguajes ensambladores, influyeron en el diseño de
PL/I.
También varios lenguajes están prefijados por las letras ANS.
Esto significa que el American National Standards Institute ha adoptado esa
versión del lenguaje como el estándar nacional. Una vez que un lenguaje esta
estandarizado, las maquinas que implementan este lenguaje deben cumplir todas
las especificaciones estándares, reforzando así el máximo de transportabilidad
de programas de una maquina a otra. La policía federal de no comprar maquinas
que no cumplan la versión estándar de cualquier lenguaje que soporte tiende a
"fortalecer" el proceso de estandarizacion, puesto que el gobierno
es, con mucho, el mayor comprador de computadoras de la nación.
Finalmente, la notación algebraica ordinaria, por ejemplo,
influyo fuertemente en el diseño de FORTRAN y ALGOL. Por otra parte, el ingles influyo en el desarrollo del COBOL. El lambda calculo de Church dio los fundamentos de la notación
funcional de LISP, mientras que el algoritmo de Markov motivo el estilo de
reconocimiento de formas de SNOBOL. La arquitectura de computadoras de Von
Neumann, la cual fue una evolución de la maquina mas antigua de Turing, es el
modelo básico de la mayoría de los diseños de computadoras de las ultimas tres
décadas. Esta maquina no solo influyeron en los primeros lenguajes sino que
también suministraron el esqueleto operacional sobre el que evoluciono la
mayoría de la programación de sistemas.
Una discusión mas directa de todos
estos primeros modelos no están entre los objetivos de este texto. Sin embargo,
es importante apuntar aquí debido a su fundamental influencia en la evolución
de los primeros lenguajes de programación, por una parte, y por su estado en el
núcleo de la teoría de la computadora, por otra. Mas sobre este punto,
cualquier algoritmo que pueda describirse en ingles o castellano puede
escribirse igualmente como una maquina de Turing (maquina de Von Neumann), un
algoritmo de Markov o una función recursiva. Esta sección, conocida ampliamente
como "tesis de Church", nos permite escribir algoritmos en distintos
estilos de programación (lenguajes) sin sacrificar ninguna medida de
generalidad, o potencia de programación, en la transición.
Los
lenguajes de programación son herramientas que nos permiten crear programas y
software. Entre ellos tenemos Delphi, Visual Basic, Pascal, Java, etc..
Una computadora funciona bajo control de un programa el cual debe estar
almacenado en la unidad de memoria; tales como el disco duro.
Los lenguajes de programación
de una computadora en particular se conoce como código
de máquinas o lenguaje de máquinas.
Estos lenguajes codificados en una computadora específica no podrán ser
ejecutados en otra computadora diferente.
Para que estos programas funcionen para diferentes computadoras hay que
realizar una versión para cada una de ellas, lo que implica el aumento del
costo de desarrollo.
Por otra parte, los lenguajes de programación en código de máquina son
verdaderamente difíciles de entender para una persona, ya que están compuestos
de códigos numéricos sin sentido nemotécnico.
Los lenguajes de programación
facilitan la tarea de programación, ya que disponen de formas adecuadas que
permiten ser leidas y escritas por personas, a su vez resultan independientes
del modelo de computador a utilizar.
Los lenguajes de programación representan en forma simbólica y en manera de un
texto los códigos que podrán ser leidos por una persona.
Los lenguajes de programación son independientes de las computadoras a
utilizar.
Existen
estrategias que permiten ejecutar en una computadora un programa realizado en
un lenguaje de programación simbólico. Los procesadores del lenguaje son los
programas que permiten el tratamiento de la información en forma de texto,
representada en los lenguajes de programación simbólicos.
Hay lenguajes de programación que utilizan compilador.
La ejecución de un programa con compilador requiere de dos etapas:
1) Traducir el programa simbólico a código máquina
2) Ejecución y procesamiento de los datos.
Otros lenguajes de programación utilizan un programa intérprete o traductor, el
cual analiza directamente la descripción simbólica del programa fuente y
realiza las instrucciones dadas.
El intérprete en los
lenguajes de programación simula una máquina virtual, donde el lenguaje de
máquina es similar al lenguaje fuente.
La ventaja del proceso interprete es que no necesita de dos fases para ejecutar
el programa, sin embargo su inconveniente es que la velocidad de ejecución es
más lenta ya que debe analizar e interpretar las instrucciones contenidas en el
programa fuente
BIBLIOGRAFÍA:
Llaccua y Vasquez, Programando con Objetos en Borland Pascal.
Ed.
Schildt , Turbo C/C++, manual de
referencia. , Osborne/McGraw-Hill.
Watt , David A. Programming Languaje
Concepts and Paradigms.
http://www.monografias.com/trabajos/iartificial/pagina4_1.htm
http://www.fciencias.unam.mx/lytc/tc/#1
http://www.terra.es/personal/jftjft/Algebra/Teoria%20de%20Conjuntos/Conjuntos.htm