Download Diapositiva 1


NOMBRE: ABIGAIL ALEJANDRA PIO LARA

MATERIA: LENGUAJES Y AUTOMATAS

TEMA: RESUMEN DE LA I UNIDAD

PROFESOR: M.C. JOSE ANGEL TOLEDO
INTRODUCCION

Según lo leido en este tema la Teoría de conjuntos, es
una rama de las matemáticas a la que el matemático
alemán Georg Cantor dio su primer tratamiento formal
en el siglo XIX. El concepto de conjunto es uno de los
más fundamentales en matemáticas
ALGUNAS DEFINICIONES




Un conjunto es una agrupación, clase o colección de objetos denominados elementos
del conjunto, un conjunto se representa frecuentemente mediante llaves que
contienen sus elementos, ya sea de forma explícita, escribiendo todos y cada uno de
los elementos, o dando una fórmula, regla o proposición que los describa. Por
ejemplo, S1 = {2, 4}; S2 = {2, 4, 6, ..., 2n, ...} = {todos los enteros pares}; S3 = {x |
x2- 6x + 11 3}; S4 = {todos los varones vivos llamados Juan}. S3 se describe como el
conjunto de todas las x tales que x2- 6x + 11 3.
Subconjuntos y superconjuntos Si todo elemento de un conjunto R pertenece
también al conjunto S, R es un subconjunto de S, y S es un superconjunto de R;
utilizando símbolos, R S, o S R. Todo conjunto es un subconjunto y un superconjunto
de sí mismo.
Unión e intersección Si A y B son dos subconjuntos de un conjunto S, los elementos
que pertenecen a A, a B o a ambos forman otro subconjunto de S llamado unión de A
y B Los elementos comunes a A y B forman un subconjunto de S denominado
intersección de A y B .
Diferencia y complementario El conjunto de elementos que pertenecen a A pero
no a B se denomina conjunto diferencia entre A y B, escrito A - B (y a veces A\B). Si A
es un subconjunto del conjunto l, el conjunto de los elementos que pertenecen a l
pero no a A, es decir, l - A, se denomina conjunto complementario de A (con respecto
a l), lo que se escribe l - A = A' (que también puede aparecer como A, Ã o ~A).
ALGEBRA DE CONJUNTOS






















LPara cualquier conjunto A, B, y C:
A ∩ A = A;
A ∪ A = A;
A \ A = {};
A ∩ B = B ∩ A;
A ∪ B = B ∪ A;
(A ∩ B) ∩ C = A ∩ (B ∩ C);
(A ∪ B) ∪ C = A ∪ (B ∪ C);
C \ (A ∩ B) = (C \ A) ∪ (C \ B);
C \ (A ∪ B) = (C \ A) ∩ (C \ B);
C \ (B \ A) = (A ∩ C) ∪ (C \ B);
(B \ A) ∩ C = (B ∩ C) \ A = B ∩ (C \ A);
(B \ A) ∪ C = (B ∪ C) \ (A \ C);
A ⊆ B sí y solamente si A ∩ B = A;
A ⊆ B sí y solamente si A ∪ B = B;
A ⊆ B sí y solamente si A \ B = Ø;
A ∩ B = Ø sí y solamente si B \ A = B;
A ∩ B ⊆ A ⊆ A ∪ B;
A ∩ {} = Ø;
A ∪ {} = A;
{} \ A = Ø;
A \ {} = A.
MULTIPLICACION DE CONJUNTOS

Si A y B son dos conjuntos, el conjunto de todos los posibles pares
ordenados de elementos de la forma (a, b), donde a pertenece a A y b
pertenece a B, se denomina producto cartesiano de A y B, que se escribe
normalmente A × B .
CORRESPONDENCIA ENTRE
CONJUNTOS
Los elementos del conjunto A = {1, 2, 3} se pueden relacionar,
emparejar o hacer corresponder con los elementos del conjunto B =
{x, y, z} de distintas maneras, de forma que: a todo elemento de B le
corresponda uno de A, a todo elemento de A le corresponda uno de
B, elementos distintos de un conjunto están emparejados con
elementos distintos del otro.
DIAGRAMA DE VENN
A cada conjunto se le considera encerrado dentro de una curva (plana)
cerrada. Los elementos del conjunto considerado pueden ser
específicamente
dibujados
o
pueden
quedar
(implícitamente)
sobreentendidos. Los diagramas son empleados, para representar tanto a
los conjuntos como a sus operaciones, y constituyen una poderosa
herramienta geométrica, desprovista de validez lógica
EJEMPLO
PRODUCTO CARTESIANO DE
CONJUNTOS

Se dice que si A y B son dos conjuntos, el conjunto de todos los posibles
pares ordenados de elementos de la forma (a, b), donde a pertenece a A y
b pertenece a B, se denomina producto cartesiano de A y B, que se escribe
normalmente A × B.


Correspondencia entre conjuntos Se dice que existe una correspondencia
de conjuntos si los elementos del conjunto A = {1, 2, 3} se pueden
relacionar o hacer corresponder mediante una correspondencia f con los
del conjunto B = {x, y, z} de modo que a todo elemento de A le
corresponda uno, ninguno o varios elementos de B.
Como nota importante se debe saber que: Cuando una correspondencia es
tal que a cada elemento del primer conjunto le corresponde uno y sólo uno
del segundo conjunto, entonces se llama aplicación
OPERACIONES CON CONJUNTOS

Unión: Dados dos conjuntos cualesquiera A y B llamamos "Unión"
de A y B al conjunto formado por todos los elementos que
pertenecen a A o a B.

Intersección: Dados dos conjuntos cualesquiera A y B llamamos
"Interseccion" de A y B al conjunto formado por todos los elementos
que pertenecen a A y pertenecen a B.

Diferencia:
Dados dos conjuntos cualesquiera A y B llamamos
"Diferencia" de A "menos" B al conjunto formado por los elementos
que pertenecen a A y no pertenecen a B.
INTRODUCCION




Se dice que 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 pueden existir proposiciones que son simples, así como
proposiciones que están construidas por otras proposiciones usando
elementos (conectivas lógicas) que las asocian .
La lógica proposicional (o cálculo proposicional) tiene el propósito de
simbolizar cualquier tipo de razonamiento para su análisis y tratamiento,
esta usa sentencias declarativas a las que se puede asociar un valor de
verdad (cierto o falso); es decir, usa proposiciones. Ejemplo: P y Q son
proposiciones:
P : El aguila es un ave
Q : La ballena es un mamifero
CONECTIVAS LOGICAS

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.
Conectiva
Símbolos asociados
Negación (No)
~, ¬ , -
Conjunción (Y)
, &, *
Disyunción (O)
, |, +
Condicional (Si ... entonces)

Bicondicional (Si y solo si)
,=

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.
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
JERARQUIA DE CONECTIVAS


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.
donde ¬ (negación) es el operador con mayor jerarquía en la
secuencia y « (bicondicional) es el operador con el menor peso.
INTERPRETACION DE FORMULAS

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.
P
Q
R
S
P Q
¬ ( P Q)
RS
¬ ( P Q)  ( RS)
V
F
V
V
F
V
V
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
FORMULAS EQUIVALENTES


Al evaluar las fórmulas P->Q y ¬ PvQ se observa que todas sus
interpretaciones son iguales, por lo que se dice que ambas fórmulas
son equivalentes
EJEMPLO:
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
Fórmula
Ley de equivalencia
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

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
(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
CIRCUITOS LOGICOS


Debido a que una proposición puede ser evaluada y resultar solo
verdadera o falsa, se puede deducir alguna equivalencia con el
álgebra booleana, que maneja solamente dos valores (0 y 1). Las
propiedades del cálculo proposicional son equivalentes a las del
álgebra desarrollada por Boole.
En el álgebra booleana, una proposición es equivalente a una
variables, y las conectivas lógicas se utilizan como compuertas
lógicas. La figura 1 muestra las compuestas lógicas más
representativas de esta álgebra. Los esquemas que resultan de
aplicar las compuertas lógicas se conocen como circuitos lógicos.
INTRODUCCION

Es muy importante, el lenguaje de programación es el medio de
comunicación entre el hombre y la máquina. El modelo general de
las computadoras, desde que fue esbozado por von Neumann, no
ha cambiado mucho, mientras que la invención humana para
proponerse nuevos problemas a resolver, usando la computadora,
parece no tener límites. Un lenguaje es un conjunto de palabras.
Por tanto el conjunto {1,12,123,1234,12345,123456} es un
lenguaje sobre el alfabeto compuesto por digitos. De forma
similar, la colección de palabras inglesas “correctas” es un
lenguaje sobre el alfabeto ingles. Obsérvese que si ∑ es un
alfabeto, también es un lenguaje, el formado por todas las cadenas
con un único símbolo.


En consecuencia, los lenguajes de programación
tienen que adaptarse a éstas crecientes
necesidades y aumentar la expresividad para
poder resolver problemas muy diversos y cada
vez más complejos. Además, tienen que ofrecer
cierta eficiencia en la ejecución. Es un logro difícil
de alcanzar y por lo tanto, se requiere una
búsqueda constante de nuevos lenguajes para
ello.
Aquí se expone un breve panorama de los más
importantes tipos de lenguajes de programación.
AÑO
LENGUAJE
INVENTOR
1900
BINARIO
Bool
primer lenguaje
1946
Plankalkul
Konrad Zuse
creado para jugar al ajedrez
1949
Short Code
lenguaje traducido a mano
1950
ASM (ensamblador)
lenguaje ensamblador
1951
A-0
Grace Hopper
fue el primer compilador
1952
AUTOCODE
Alick E. Glennie
compilador muy
rudimentario
1956
FORTRAN
IBM
sistema de TRAducción de
FORmulas matemáticas
DESCRIPCION
Compilador
1956
COBOL
1958
ALGOL 58
1960
LISP
1961
FORTRAN IV
Interprete orientado a la
Inteligencia Artificial
IBM
sistema de TRAducción de
FORmulas matemáticas
AÑO
LENGUAJE
INVENTOR
DESCRIPCION
1961
COBOL 61 Extendido
1960
ALGOL 60 Revisado
1964
PASCAL
Niklaus Wirth
programacion estructurada
BASIC
Universidad de
Dartmouth
(california)
Beginners All Purpose
Symbolic Instruction Code
1964
1965
SNOBOL
1965
APL
1965
COBOL 65
1966
PL/I
1966
FORTRAN 66
1967
SIMULA 67
solo anotacion
IBM
sistema de TRAducción de
FORmulas matemáticas
AÑO
LENGUAJE
1968
ALGOL 68
1968
SNOBOL4
1970
GW-BASIC
1970
APL/360
INVENTOR
DESCRIPCION
antiguo y clasico BASIC
1972
SMALLTALK
Centro de
Investigación de
Xerox en Palo Alto
1972
C
Laboratorios Bell
1974
COBOL 74
1975
PL /I
1977
FORTRAN 77
IBM
sistema de TRAducción de
FORmulas matemáticas
1980s
SMALLTALK/V
Digitalk
pequeño y rapido
1980
C con clases
Laboratorios Bell
lenguaje con clases
pequeño y rapido
lenguaje con tipos
Lenguaje sencillo
AÑO
LENGUAJE
INVENTOR
DESCRIPCION
PROLOG
Ministerio
Japonés de
Comercio
Internacional e
Industria (MITI)
Lenguaje estandar para la
Inteligencia Artificial
ADA
Ministerio de
Defensa de los
EE.UU
lenguaje muy seguro
1984
C++
AT&T Bell
Laboratories
(Bjarne
Stroustrup)
compilador
1985
CLIPPER
1985
QuickBASIC 1.0
Microsoft®
compilador de BASIC
1986
QuickBASIC 2.0
Microsoft®
soporte de tarjeta gráfica
EGA
1987
QuickBASIC 3.0
Microsoft®
43 lineas con la tarjeta EGA
1987
QuickBASIC 4.0
Microsoft®
tarjetas Hercules, VGA
1981
1982
compilador para bases de
datos
AÑO
LENGUAJE
1987
CLIPPER SUMMER '87
1988
QuickBASIC 4.5
Microsoft®
tarjeta SVGA
1989
QuickBASIC 7.1
Microsoft®
ultima version de
QuickBASIC
1989
ASIC v5.0
1990
VISUAL C++
1990
VISUAL BASICScript
Microsoft®
lenguaje de script
1990
HTML
Tim Berners-Lee
para internet
1993
XML
C. M. SperbergMcQueen
para internet
1993
SGML
Charles F.
Goldfarb
para internet
INVENTOR
DESCRIPCION
compilador para bases de
datos
interprete tipo QBASIC
shareware
AÑO
LENGUAJE
1990
WML
1990
ASP
1990
PHP
1995
JAVA
1995
CLIPPER 5.01
INVENTOR
DESCRIPCION
para internet
Microsoft®
para internet
para internet
Sun
Microsystems
para internet y proposito
general
compilador para bases de
datos
1995
GNAT ADA95
Ministerio de
Defensa de los
EE.UU
1995
FORTRAN 95
IBM
1991
VISUAL BASIC 1.0
Microsoft®
1992
VISUAL BASIC 2.0
Microsoft®
lenguaje muy seguro
sistema de TRAducción de
FORmulas matemáticas
AÑO
LENGUAJE
INVENTOR
1993
VISUAL BASIC 3.0
Microsoft®
1994
VISUAL BASIC 4.0
Microsoft®
1995
VISUAL BASIC 5.0
Microsoft®
1998
VISUAL BASIC 6.0
Microsoft®
1990s
C#
2001
VISUAL BASIC .NET
Microsoft®
DESCRIPCION
La evolución de Visual Basic




Los primeros lenguajes de programación surgieron de la idea de Charles
Babagge a mediados del siglo XIX. Consistía en lo que el denominaba la
maquina analítica, pero que por motivos técnicos no pudo construirse
hasta mediados del siglo XX.
Con el colaboro Ada Lovelace, la cual es considerada como la primera
programadora de la historia, pues realizo programas para aquella supuesta
maquina de Babagge, en tarjetas perforadas. Como la maquina no llego
nunca a construirse, los programas de Ada, lógicamente, tampoco llegaron
a ejecutarse, pero si suponen un punto de partida de la programación.
En 1936, Turing y Post introdujeron un formalismo de manipulación de
símbolos (la denominada máquina de Turing) con el que se puede realizar
cualquier cómputo que hasta ahora podemos imaginar. Los "Lenguajes
Maquina" y los "Lenguajes Ensambladores" (primera y segunda
generación) 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 lenguajes de alto nivel son normalmente fáciles de aprender porque
están formados por elementos de lenguajes naturales, como el inglés.




Lenguajes Imperativos. En este tipo de lenguajes, cuyo origen está ligado
a la propia arquitectura de von Neumann, la arquitectura consta de una
secuencia de celdas, llamadas memoria, en la cual se pueden guardar en
forma codificada, lo mismo datos que instrucciones; y de un procesador, el
cual es capaz de ejecutar de manera secuencial una serie de operaciones,
principalmente aritméticas y booleanas, llamadas comandos. En general,
un lenguaje imperativo ofrece al programador conceptos que se traducen
de forma natural al modelo de la máquina. Los lenguajes imperativos más
destacados de la historia han sido: FORTRAN, Algol, Pascal, C, Modula-2,
Ada.
Lenguajes Funcionales. Una función convierte ciertos datos en resultados.
Si supiéramos cómo evaluar una función, usando la computadora,
podríamos resolver automáticamente muchos problemas. Así pensaron
algunos matemáticos, que no le tenían miedo a la máquina, e inventaron
los lenguajes de programación funcionales.
Aprovecharon la posibilidad que tienen las funciones para manipular datos
simbólicos, y no solamente numéricos, y la propiedad de las funciones que
les permite componer, creando de esta manera, la oportunidad para
resolver problemas complejos a partir de las soluciones a otros más
sencillos. También se incluyó la posibilidad de definir funciones
recursivamente.
El lenguaje funcional más antiguo, y seguramente el más popular hasta la
fecha, es LISP. En la década de los 80 hubo una nueva ola de interés por
los lenguajes funcionales, añadiendo la tipificación y algunos conceptos
modernos de modularización y polimorfismo, como es el caso del lenguaje
ML.








Lenguajes Lógicos. El conocimiento básico de las matemáticas se puede representar
en la lógica en forma de axiomas, a los cuales se añaden reglas formales para deducir
cosas verdaderas (teoremas) a partir de los axiomas. Algunos matemáticos, a finales
de siglo XX y principios de XXI, encontraron la manera de automatizar
computacionalmente el razonamiento lógico que permitió que diera origen a los
lenguajes lógicos.
También se conoce a estos lenguajes, y a los funcionales, como lenguajes
declarativos, porque el programador, parar solucionar un problema, todo lo que tiene
que hacer es describirlo vía axiomas y reglas de deducción en el caso de la
programación lógica y vía funciones en el caso de la programación funcional.
En los lenguajes lógicos se utiliza el formalismo de la lógica para representar el
conocimiento sobre un problema y para hacer preguntas que, si se demuestra que se
pueden deducir a partir del conocimiento dado en forma de axiomas y de las reglas de
deducción estipuladas, se vuelven teoremas. Así se encuentran soluciones a
problemas formulados como preguntas.
El PROLOG es el primer lenguaje lógico y el más conocido y utilizado. También en este
caso, las aplicaciones a la Inteligencia Artificial mantienen el lenguaje vivo y útil.
Lenguajes Orientados a Objetos.
A mediados de los años 60 se empezó a vislumbrar el uso de las computadoras para la
simulación de problemas del mundo real. Pero el mundo real está lleno de objetos.
Así es que a dos noruegos, Dahl y Nygaard, se les ocurrió el concepto de objeto y sus
colecciones, llamadas clases de objetos, que permitieron introducir abstracciones de
datos a los lenguajes de programación. A ellos también les debemos el concepto de
polimorfismo introducido vía procedimientos virtuales.
Todos estos conceptos fueron presentados en el lenguaje Simula 67, desde el año
1967. En los años 80 hubo una verdadera ola de propuestas de lenguajes de
programación con conceptos de objetos encabezada por Smalltalk, C++, Modula-3,
Ada 95 y terminando con Java.




Lenguajes Concurrentes, Paralelos y Distribuidos.
La necesidad de ofrecer concurrencia en el acceso a los recursos
computacionales se remonta a los primeros sistemas operativos. Por
ejemplo, mientras un programa realizaba una operación de entrada o
salida otro podría gozar del tiempo del procesador para sumar dos
números.
Cuando los procesadores cambiaron de tamaño y de precio, se abrió la
posibilidad de contar con varios procesadores en una máquina y ofrecer el
procesamiento en paralelo, es decir, procesar varios programas al mismo
tiempo. Esto dio el impulso a la creación de lenguajes que permitían
expresar el paralelismo. Finalmente, llegaron las redes de computadoras,
que también ofrecen la posibilidad de ejecución en paralelo, pero con
procesadores distantes, lo cual conocemos como la programación
distribuida.
Históricamente encontramos en la literatura soluciones conceptuales y
mecanismos tales como: semáforos, regiones críticas, monitores, envío de
mensajes (CSP), llamadas a procedimientos remotos (RPC), que
posteriormente se incluyeron como partes de los lenguajes de
programación en Concurrent Pascal, Modula, Ada, OCCAM, y últimamente
en Java.