TRABAJO DE INVESTIGACION

MAGDALENA RODRIGUEZ ALEMAN

LENGUAJES Y AUTOMATAS

GRUPO CS51

LOGICA PROPOSICIONAL

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 (formula bien formada); de la misma forma, podemos construir proposiciones usando solo un grupo de conectivas, produciendo formulas que se dice están en su forma normal.

Las formas más normales son importantes por el hecho que permite definir esquemas generales para el tratamiento de estas formulas.

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.

PROPOSICIONES

Proposición: Frase que se puede verificar su veracidad.

Al escuchar algo como "El perro es un mamífero" o "La rosa es una flor", fácilmente se puede determinar si estas sentencias son ciertas o falsas; sin embargo al escuchar "Que equipo ganara hoy?",no es posible asociar a ella un valor de verdad, porque no se puede saber cual es el resultado. Sentencias como las dos primeras son los elementos fundamentales con los que trabaja la lógica proposicional.

La lógica proposicional tiene el propósito de simbolizar cualquier tipo de razonamiento para su análisis y tratamiento. No existe una notación generalmente utilizada para representar proposiciones, pero por lo general se utilizan para representar a cada una de ellas con una letra mayúscula (o una cadena de letras mayúsculas).

Ejemplo:

P y Q son proposiciones

P: El perro es un mamífero.

Q: La rosa es una flor.

La asociación de proposiciones produce otras proposiciones conocidas como compuestas.

La construcción de formulas compuestas requiere del uso de elementos que permitan establecer una relación entre las proposiciones que la conforman; estos elementos se les conoce como CONECTIVAS LOGICAS.

En la proposición "El agua es fría y el calentador esta descompuesto" se tiene dos proposiciones, unidos por la partícula "y" la cual se dice que es una conectiva lógica.

Las conectivas lógicas usadas en la lógica proposicional son cinco y son representadas simbólicamente de varias formas, como se muestra a continuación:

CONECTIVA	SIMBOLOS ASOCIADOS
Negación (No)	7, ~, -
Conjunción (Y)	^,&,*
Disyunción (O)	v, , +
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.

TABLAS DE VERDAD

Señala los valores resultantes para la evaluación de proposiciones compuestas a partir de las diferentes combinaciones de valores de verdad de sus proposiciones.

NEGACION CONJUNCION DISYUNCION

(~P) (Y) (O)

P	Q	~P	P	Q	P^Q	P Q PvQ
V	V	F	V	V	V	V V V
V	F	F	V	F	F	V F V
F	V	V	F	V	F	F V V
F	F	V	F	F	F	F F F

CONDICIONAL BICONDICIONAL

P	Q	P Q	P	Q P Q
V	V	V	V	V V
V	F	F	V	F F
F	V	V	F	V F
F	F	V	F	F V

Las proposiciones compuestas son agrupaciones de proposiciones unidas por conectivas logicas; es importante aclarar que al construir proposiciones, se requiere seguir una serie de reglas que establecen si una formula esta bien formada. De acuerdo a lo anterior una formula bien formada es aquella que cumple los siguientes puntos:

1. - Una proposición es una formula bien formada.

2. - Si P es una formula bien formada, ~P también es una formula bien formada.

3. - Si P y Q son formulas bien formadas. P^Q,PvQ,P Q y P Q son formulas bien formadas

4. - Todas las formulas bien formadas se obtienen aplicando las reglas 1,2,3.

Al tener formulas con dos o mas conectivas, se deben de conocer las reglas de precedencia y asociatividad de las conectivas para asegurar que la evaluación es correcta.

Al tener una formula con la presencia de dos o mas conectivas iguales, el orden de asociatividad siempre va a ser de izquierda a derecha.

Una interpretación de una formula es una asignación de valores de verdad a un conjunto de proposiciones; para una formula con dos proposiciones se tiene dos posibles interpretaciones, para una con tres se tiene ocho interpretaciones, y en general para una formula con n proposiciones se tienen 2ⁿ interpretaciones.

De la evaluación de una formula se pueden definir los siguientes conceptos:

TAUTOLOGIA: Una formula es una tautología si es verdadera para todas sus posibles interpretaciones. Una tautología también se conoce como una formula valida.

CONTRADICCION: Una formula es una contradicción si es falsa para todas sus posibles interpretaciones. Una contradicción también se conoce como una formula inconsistente o una formula insatisfactible.

FORMULA CONSISTENTE: Una formula que al menos tiene una interpretación verdadera se conoce como formula consistente o satisfactible.

FORMULA INVALIDA: Una formula es invalida si es falsa para al menos una interpretación.

EJEMPLOS:

La formula (P Q)vP es una tautología ya que todas sus nterpretaciones son verdaderas.

P	Q	P Q	(P Q )vP
V	V	V	V
V	F	F	V
F	V	V	V
F	F	V	V

La formula (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

Las formulas P Q y ~PvQ son formulas equivalentes.

P	Q	~P	P Q	~PvQ
V	V	F	V	V
V	F	F	F	F
F	V	V	V	V
F	F	V	V	V

Existen varias equivalencias entre formulas de la lógica proposicional, las cuales se conocen como leyes de equivalencia.

FORMAS NORMALES

Las leyes de equivalencia permiten transformar formulas de la lógica proposicional en otras formulas más simples de evaluar o que estén escritas en alguna forma que sea útil para su manipulación. En la lógica proposicional existen dos formas para presentar formulas 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 formula esta en su forma normal conjuntiva si es una conjunción de disyunciones, es decir, tiene la forma: F₁^F₂^……^ F_nen la cual F_n es una formula construida por una agrupación de proposiciones unidos por disyunciones.

FORMA NORMAL DISYUNTIVA: Una formula esta en su forma normal disyuntiva si es una disyunción de conjunciones, es decir, tiene la forma: F₁vF₂v……F_n, en la F_nes una formula construida por una agrupación de proposiciones unidos por conjunciones.

LOGICA ELEMENTAL

La lógica elemental se divide en:

lógica de enunciados

lógica de predicados

Ambas utilizan un lenguaje propio artificial o formalización de un lenguaje natural que permite analizar las proposiciones del lenguaje natural.

El cometido de la lógica clásica elemental es determinar si nuestros razonamientos, independientemente de su contenido, son correctos o incorrectos.

Por razonamientos (o argumentos) se entiende un conjunto de proposiciones de tal manera que, una de las cuales, denominada conclusión del razonamiento, pueda presentarse como consecuencia de las demás proposiciones, llamadas premisas del razonamiento.

En la lógica de enunciados la unidad mínima es el enunciado, es decir, un segmento lingüístico que tiene sentido completo por sí mismo:

Esta fiesta es muy divertida

Esta fiesta es muy divertida y la música es muy buena

Para que un enunciado sea tal, tiene que poder atribuírsele valores de verdad o falsedad.

En el caso de las dos oraciones anteriores, la verdad o falsedad habrá de determinarse empíricamente, comprobando si, de hecho, la fiesta es divertida y buena la música. En este caso, además, la dificultad es aún mayor ya que se trata de una afirmación subjetiva.

La lógica de enunciados (o lógica proposicional), trata del estudio de la composición de enunciados mediante conectores (y, o, si...entonces, etc.) y se fundamenta en el principio de bivalencia, según el cual, todo enunciado es verdadero o falso, pero nunca ambas cosas a la vez..

Podemos decir, por lo tanto, que la lógica de enunciados se dedica a formalizar las proposiciones del lenguaje natural en un lenguaje simbólico y a definir los conectores, estudiando las leyes de combinación o deducción de los enunciados que las contienen.

En la lógica de predicados se formaliza y estudia la oración atendiendo a los dos términos que la componen: el sujeto y el predicado.

CONJUNTOS

Teoría de conjuntos es la rama de las matemáticas a la que el matemático alemán George Cantor dio su primer tratamiento formal en el siglo XIX. El concepto de conjunto es uno de los mas fundamentales en las matemáticas, incluso mas que la operación de contar, pues se puede encontrar implícita o explícita, en todas las ramas de las matemáticas puras y aplicadas. En su forma explícita los principios y terminología de los conjuntos se utilizan para construir proposiciones matemáticas mas claras y precisas y para explicar conceptos abstractos como el infinito.

CONJUNTO: Un conjunto es una agrupación, clase o colección de objetos denominado elementos del conjunto utilizando símbolos a Î S representa que el elemento a pertenece o esta contenido en el conjunto S, o lo que es lo mismo, el conjunto S contiene al elemento a.

Un conjunto se representa frecuentemente con el símbolo S= { }, en donde las llaves engloban los elementos de S, ya sea de forma explícita, escribiendo todos y cada uno de los elementos, o dando una formula regla o proposición que los describa. Por ejemplo: S= {2,4,6,8,10,……} o S={todos los enteros pares}.

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 los símbolos R Í S, o S Ê R. Todo conjunto es un subconjunto y un superconjunto de si mismo. Si R Í S, y al menos un elemento de S no pertenece a R, se dice que R es un subconjunto propio de S, y S es un superconjunto propio de R, lo que se representa con los siguientes símbolos: R Í S, S Ê R. Si R Í S y S Ê R, es decir todo elemento de un conjunto pertenece también al otro, entonces R y S son dos conjuntos iguales, lo que se escribe R=S.

Ejemplo:

A={1,2,3,4,5,6,7,8,9}

A1={4,7,8}

Conjunto A

subconjunto A1 Í A Superconjunto A Ê A1

A Í A

OPERACIONES DE CONJUNTOS

UNION:

Dados dos conjuntos cualesquiera A y B llamados "Unión" de A y B al conjunto formado por todos los elementos que pertenecen a A o a B.

Simbólicamente:

A È B = {x/x Î A y x Î B}

INTERSECCION:

Dados dos conjuntos cualesquiera A y B llamamos intersección de A y B al menos al conjunto formado por todos los elementos que pertenecen a A y pertenecen a B.

Simbólicamente:

A Ç B= {x/x Î A y x ÎB}

DIFERENCIA:

Dados dos conjuntos cualesquiera Ay B llamados "Diferencia" de A "menos" B al conjunto formado por los elementos que pertenecen a A y no pertenecen a B.

Simbólicamente:

A-B= {x/x Î A , x Ï B}

COMPLEMENTO:

Dados dos conjuntos cualesquiera A y B con B Í A (B subconjunto de A) llamamos "complemento de B con respecto a A" al menos al conjunto de elementos que pertenecen a A y no a B, esto es lo que falta a B para ser igual a A.

PRODUCTO CARTESIANO:

Para definir el producto cartesiano de dos conjuntos cualesquiera A y B primero definiremos lo que es un par ordenado.

PAR ORDENADO: un par ordenado es un conjunto de dos elementos donde nos interesa el orden en que estos aparezcan, esto es posee un primer elemento y un segundo elemento.

Se representa con paréntesis y a los elementos se les denominara componentes: (a,b) representa el par ordenado cuya primera componente es A y su segundo componente es b.

Debemos observar que para que dos pares ordenado sean iguales sus componentes deben serlo: (a,b) = (c,d) si y solo si a=c y b = d.

Habiendo definido lo que es un par ordenado podemos decir que:

El producto cartesiano de dos conjuntos a y B es el conjunto de todos los pares ordenados cuya primera componente pertenece a A y cuya segunda componente pertenece a B.

Simbólicamente:

A xB={(a,b)/a Î A y b Î B}

EJEMPLOS DE OPERACIONES DE CONJUNTOS.