ALGEBRA DECLARATIVA

           ÁLGEBRA DECLARATIVA

 

oct24

Lo que algunos llaman álgebra declarativa no es otra cosa que el álgebra proposicional, o sea, la estructura algebraica que se forma con expresiones utilizando los conectivos lógicos.

Empezaremos por definir formalmente cómo se construye una fórmula en lógica. Una expresión sintácticamente correcta se le llama fórmula bien formada (fbf) o simplemente fórmula y su definición es:

Una fórmula en lógica de proposiciones se obtiene al aplicar una ó más veces las siguientes reglas:

(B) si p es una proposición lógica, es una fbf.
(R) si F es una fórmula bien formada (fbf) también lo es (¬F).
(R) si p,q son fbf entonces también lo es (p*q) donde * es uno de los operadores binarios, ^ v → ↔.

Las proposiciones p Þ q y ~ (p Ù ~ q) son equivalentes, como vemos realizando la tabla de valores correspondientes:

p	q	p Þ q	(p Ù ~ q)	~(p Ù ~ q)	p Þ q  ~(p Ù ~ q)
V V F F	V F V F	V F V V	F V F F	V F V V	V V V V

¿Cómo simplificar en lógica?

Hay que utilizar equivalencias lógicas.

Por ejemplo, simplificar: ( p ^ q ) ^ ¬ q.

Para esto utilizamos las siguientes equivalencias lógicas:

( A ^ B ) ^ C <=> A^(B ^C)

A ^ ¬ A <=> F

A ^ F <=> F

( p ^ q ) ^ ¬q <=> F

Se puede observar que no existe distinción entre la equivalencia lógica y el esquema que la genera.

Ejemplo

Demostrar que una vez que p ^ q esta establecida, se puede concluir q.

Esta demostración se puede hacer de dos formas:

A) Se demuestra que p ^ q → q es una tautológica, es decir p ^ q <=> q.

Demostración

¬p V ¬q V q <=> V

B) Se demuestra que ( p ^ q ) ^ ¬q <=> F lo que nos lleva a que ( p ^ q ) ^ ¬q → F debe ser una tautológica 

INDUCCION MATEMATICA

La inducción es un razonamiento que permite demostrar una infinidad de proposiciones, o una proposición que depende de un parámetro n que toma una infinidad de valores, usualmente en el conjunto de los enteros naturales N.

EJEMPLO

Demostraremos que:
1+2+3+…………+n = n(n+1), ” n perteneciente a los naturales (*)
2
1= 1(1+1). Por lo tanto 1 satisface la proposición (*)
2
Supongamos valida la proposición (*) para k perteneciente a los Naturales, es decir supongamos que:
1+2+3+………+k = k (k+1). (Hipótesis de inducción).
2
Demostremos que k – 1 también satisface la proposición (*), es decir, demostremos que:
1+2+3+………+k+(k+1) = (k+1)(k+2).
2
Demostración:
(1+2+3+…….+k)+(k+1) = k(k+1) + (k+1)
2
= k(k+1)+2(k+1)
2
= (k+1)(k+2)
2

Ejemplo:

Demuestre usando inducción que:

2 + 4+ 6 + 8+……….+ 2n = n (n+1)

n

2 i = n (n+1)

i =1

n=1

1

2*1 = 1(1+1)

i =1

= 1*2

= 2

Suponer valido para n = k

k

2i = k (k+1) Esto es la hipótesis

i =1

Demostrar para n = k+1

K+1

2i = (k+1) (k+2)

i =1

k+1 k

2i = 2i + 2(k+1)

i =1 i =1

= k (k+1) + 2(k+1)

= (k+1) (k+2)

APLICACIÓN DE LA LÓGICA EN LAS MATEMÁTICAS DE LA COMPUTACION

La lógica matemática es una parte de la lógica y las matemáticas, que consiste en el estudio matemático de la lógica y en la aplicación de este estudio a otras áreas de las matemáticas. La lógica matemática guarda estrechas conexiones con las ciencias de la computación y la lógica filosófica.

La lógica es ampliamente aplicada en:

·         La filosofía: para determinar si un razonamiento es válido o no, ya que una frase puede tener diferentes interpretaciones.

·         Las matemáticas: para demostrar teoremas e inferir resultados matemáticos que puedan ser aplicados en investigaciones.

·         La computación: para realizar y revisar programas.

·         En general: se aplica en la tarea diaria, ya que cualquier trabajo que se realiza tiene un procedimiento lógico.

 Ejemplos:

  Para ir de compras al supermercado un ama de casa tiene que realizar cierto procedimiento lógico que permita realizar dicha tarea de la mejor forma comprando lo que le hace falta a buen precio.

•   Si una persona desea pintar una pared, este trabajo tiene un procedimiento lógico, ya que no puede pintar si antes no prepara la pintura, o no debe pintar la parte baja de la pared si antes no pintó la parte alta porque se mancharía lo que ya tiene pintado, también dependiendo si es zurdo o derecho, él puede pintar de izquierda a derecha o de derecha a izquierda según el caso, todo esto es la aplicación de la lógica.

El objetivo es apreciar la utilidad que tiene la lógica matemática en la carrera de ingeniería en sistemas computacionales y resolver ejercicios utilizándola.

SUBTEMA : LOGICA DE PREDICADOS

                           LÓGICA DE PREDICADOS

La lógica matemática es una parte de la lógica y las matemáticas, que consiste en el estudio matemático de la lógica y en la aplicación de este estudio a otras áreas de las matemáticas. La lógica matemática tiene estrechas conexiones con la ciencias de la computación y la lógica filosófica.

La lógica matemática estudia los sistemas formales en relación con el modo en el que codifican nociones intuitivas de objetos matemáticos como conjuntos, números,demostraciones y computación.

La lógica de predicados estudia las frases declarativas con mayor grado de detalle, considerando la estructura interna de las proposiciones. Se tomara como elemento basico los objetos y las relaciones entre dichos objetos.Es decir, se distingue:

• Que se afirma(predicado o relacion)
• De quien se afirma(objeto)

Definimos a continuación las reglas sintácticas para construir fórmulas:
Definición 1:El alfabeto de la lógica de predicados estará formado por los siguientes conjuntos simbólicos:
•Conjunto de Símbolos de Variables(VAR): Es un conjunto de las últimas letras del alfabeto en minúsculas. Se utilizan subíndices, por ejemplo: 

•Conjunto de símbolos de Constantes (CONS): Este conjunto lo forman las primeras letras del alfabeto en minúsculas,también utilizaremos subíndices: 

•Conjunto de letras de función(FUNC): Representaremos a este conjunto por las letras f,g,h,L. Incluimos subíndices para poder diferenciar las funciones: 

•Conjunto de letras de Predicado (PRED): Se representan mediante letras mayúsculas, 

Símbolos de conectivas:

¬ = Negación

∨= Conectiva “o”

∧ = Conectiva “y”

→ = implicación

↔ = Doble implicación o equivalencia

Cuantificadores:

∃=existencial

∀=Universal

Cuantificadores

En lógica, teoría de conjuntos y matemáticas en general, los cuantificadores son símbolos utilizados para indicar cuántos elementos de un conjunto dado cumplen con cierta propiedad.

El cuantificador universal indica que algo es cierto para todos los individuos.

Sea A una expresión y sea x una variable. Si deseamos indicar que A es verdadero para todos los posibles valores de x, escribiremos (∀x) A.

Cuantificador Existencial

La cuantificación existencial de P(x) “Es la proposición en que existe un elemento x en el universo de discurso tal que P(x) es verdad”.

Se denota con el símbolo ∃ x y se lee de las siguientes maneras: “hay un x tal que…)”, “hay al menos un x tal que…” o “para algún x…”.

EJEMPLOS:

Todos los humanos respiran

(∀ x) (H(x) → R(x)) donde el predicado H significa humanos, R respiran y x es un elemento de un dominio general que podría ser el de las personas o cualquier subconjunto deseado.

                  Representación y evaluación de predicados

La principal debilidad de la lógica proposicional es su limitada habilidad para expresar conocimiento. Existen varias sentencias complejas que pierden mucho de su significado cuando se las representa en lógica proposicional. Por esto se desarrolló una forma lógica más general, capaz de representar todos los detalles expresados en las sentencias, esta es la lógica de predicados.

Al igual que las proposiciones, los predicados tienen un valor de veracidad, pero a diferencia de las preposiciones, su valor de veracidad, depende de sus términos. Es decir, un predicado puede ser verdadero para un conjunto de términos, pero falso para otro.

La lógica de predicados, se ocupa únicamente de métodos de argumentación sólidos. Tales argumentaciones se denominan Reglas de Inferencia. Si se da un conjunto de axiomas que son aceptados como verdaderos, las reglas de inferencia garantizan que sólo serán derivadas consecuencias verdaderas.

• El cuantificador universal; “ indica que la fórmula bien formada, dentro de su alcance, es verdadera para todos los valores posibles de la variable que es cuantificada. Por ejemplo:

“ X . . . .

Establece que “para todo X, es verdad que . . . “

• El cuantificador existencial;$ , indica que la fórmula bien formada, dentro de su alcance, es verdadera para algún valor o valores dentro del dominio. Por ejemplo:

$ X . . . .

Establece que “existe un X, tal que . . . “

ejemplos de predicados cuantificados:

“ X, [niño (X) => le_gusta (X, helados)].

“ Y, [mamífero (Y) => nace (Y, vivo)].

$ Z, [cartero(Z) ^ mordió (boby, Z)].

TEMAS UNIDAD 3 MATEMATICAS DISCRETAS

3.1 LÓGICA PROPOSICIONAL
3.1.1 Concepto de proposición
3.1.2 Proposiciones compuestas (Disyunción, Conjunción, Negación, Condicional, Bicondicional)
3.1.3 Tablas de Verdad
3.1.4 Tautologías, contradicción y contingencia
3.1.5 Equivalencias Lógicas
3.1.6 Reglas de inferencia
3.1.7 Argumentos válidos y no válidos
3.1.8 Demostración Formal (Directa, Por contradicción)
3.2 LÓGICA DE PREDICADOS
3.2.1 Cuantificadores
3.2.2 Representación y evaluación de predicados
3.3 ÁLGEBRA DECLARATIVA
3.4 INDUCCION MATEMATICA
3.5 APLICACIÓN DE LA LÓGICA MATEMÁTICA EN LA COMPUTACIÓN

3.3 ÁLGEBRA DECLARATIVA

LOGICA PROPOSICIONAL Y SUBTEMAS

 ES un sistema formal diseñado para analizar ciertos tipos de argumentos. En lógica proposicional, las fórmulas representan proposiciones y las conectivas lógicas son operaciones sobre dichas fórmulas, capaces de formar otras fórmulas de mayor complejidad. Como otros sistemas lógicos, la lógica proposicional intenta esclarecer nuestra comprensión de la noción de consecuencia lógica para el rango de argumentos que analiza. También llamada simbólica o matemática es la parte de la lógica que estudia las preposiciones y símbolos utilizados en la formación de nuevas  preposiciones que podran ser verdaderas o falsas

LOGICA PREPOSICIONAL






CONCEPTO DE PROPOSICION

• Secuencia finita de signos con significado y sentido de ser calificado como verdadero o falso.

• Expresión lingüística susceptible de ser calificada de verdadera o falsa. hace referencia explicita a las oraciones aseverativas o enunciativas.

EJEMPLOS:CIERTOS

• La raíz cuadrada de 4 es 2.

• Los bebes lloran.

• Un cuadrado tiene 4 lados.

FALSOS

• Todos los carros tiene 2 ruedas.

• 20 + 20 = 20.

• Ningún hombre sabe leer.   

Proposiciones compuestas

 (Disyunción, Conjunción, Negación, Condicional, Bicondicional)

La disyunción es un operador que opera sobre dos valores de verdad, típicamente los valores de verdad de dos proposiciones, devolviendo el valor de verdad verdadero cuando una de las proposiciones es verdadera, o cuando ambas lo son, y falso cuando ambas son falsa

La conjunción es un operador que opera sobre dos valores de verdad, típicamente los valores de verdad de dos proposiciones, devolviendo el valor de verdad verdadero cuando ambas proposiciones son verdaderas, y falso en cualquier otro caso. Es decir es verdadera cuando ambas son verdaderas.

La negación es un operador que se ejecuta. sobre un único valor de verdad, devolviendo el valor contradictorio de la proposición considerada.

El bicondicional o doble implicación es un operador que funciona sobre dos valores de verdad, típicamente los valores de verdad de dos proposiciones, devolviendo el valor de verdad verdadero cuando ambas proposiciones tienen el mismo valor de verdad, y falso cuando sus valores de verdad difieren.

El condicional material es un operador que opera sobre dos valores de verdad, típicamente los valores de verdad de dos proposiciones, devolviendo el valor de verdad falso sólo cuando la primera proposición es verdadera y la segunda falsa, y verdadero en cualquier otro caso.

Tablas de Verdad

 

oct18

Para empezar debemos de conocer los Símbolos de las conectivas:

• NEGACION: ¬, se lee “No es cierto que …”

• CONJUNCION:^, se lee “… y …”

• DISYUNCION: v, se lee “… o …

• CONDICIONAL: →, se lee “si … entonces …”

• BICONDICIONAL: ↔, se lee “… si y solo si …

la negación es una conectiva lógica que transforma un enunciado en su opuesto lógico y se le llama conectiva singular porque se aplica sobre un solo enunciado


                                                               

Tabla de Verdad Negación

la conjunción es una conectiva lógica que enlaza dos enunciados dando como resultado una fórmula que será verdadera solamente cuando sus enunciados componentes son verdaderos
                                                                   

Tabla de verdad conjunción

la disyunción es una conectiva lógica que enlaza dos enunciados dando como resultado una fórmula que será verdadera solamente cuando al menos uno de sus enunciados componentes es verdaderos, siendo falsa cuando ambos son falsos
                                                                

Tabla de Verdad Disyunción

la condicional es una conectiva lógica que enlaza dos enunciados dando como resultado una fórmula que será verdadera cuando el segundo enunciado sea verdadero o tenga el mismo valor de verdad que el primero. al primer enunciado involucrado se le llama antecedente y al segundo se le llama consecuente
                                                                

Tabla de Verdad Condicional

la doble condicional o bincondicional es una conectiva lógica que enlaza dos enunciados dando como resultado una fórmula que será verdadera solamente cuando sus enunciados componentes tienen el mismo valor de verdad
                                                            

                                                                 Tabla de Verdad Bicondicional

Tautologías, contradicción y contingencia

Tautología

Las tautologías son identidades lógicas que siempre serán verdaderas, no son solo un útil objeto en la lógica son usadas primordialmente para pruebas sentenciales, desempeñan un papel fundamental en los procesos de la deducción dentro de esta lógica (sentencial).
Ejemplo:
La expresión ‘(p ^ q) → (p v r)’ es una tautología.

Contradicción

Si una proposición compuesta es falsa para todas las asignaciones entonces es una contradicción. Son formulas sentencialmente contra-validas o de tercer grado. Ejemplo:
P ∧ ¬P (se lee: P y no P). Su tabla de verdad es la siguiente.

Contingencia

Se utilizan para hacer circuitos de control y automatismo, surgen cuando en dos proposiciones, su equivalencia es verdadera y falsa a la vez. Ejemplo:
A^(BVC)

                             EQUIVALENCIAS LOGICAS  

               

Dos proposiciones s1,s2, son lógicamente equivalentes cuando la proposición s1 es verdadera (respectivamente, falsa) si y solo si la proposición s2 es verdadera (respectivamente, falsa).
Decimos que dos proposiciones son equivalentes cuando cada una de ellas implica a la otra. El camino usual para probar la equivalencia de dos proposiciones consiste en deducir cada una de ellas a partir de la otra.
Ejemplo: Las fórmulas siguientes son equivalentes:
(p → ¬q) ∨ (¬p ∨ r) ¬p ∨ ¬q ∨

                                                      REGLAS DE INFERENCIA

Técnicas fundamentales en el desarrollo de una justificación paso por paso de cómo una conclusión se sigue a partir de las premisas.
Las premisas son cada una de las proposiciones anteriores a la conclusión.
La conclusión es la consecuencia lógica de las premisas.
Reglas:
1. Modus Ponendo Ponens (MPP): Método que afirmando afirma; establece que si una implicación es cierta y además también su antecedente, entonces su consecuente es necesariamente verdadero.

ARGUMENTOS VALIDOS Y NO VALIDOS

                                         

Un argumento es una secuencia de afirmaciones.
Todas las afirmaciones excepto la última se llamarán premisas, o suposiciones o hipótesis. La declaración final se llamará conclusión. Diremos que un argumento es argumento válido si para cualquier valor de las variables proposicionales involucradas en las fórmulas que hacen verdaderas las premisas, también la conclusión es verdadera.
De la propia definición de argumento válido se puede deducir una metodología para verificar la validez de un argumento:
1. Identificar las premisas y la conclusión
2. Construir una tabla de verdad que incluya las premisas y la conclusión
3. Señalar de la tabla sólo aquellos renglones que hacen que todas las premisas sean verdaderas. Estos se llamarán renglones críticos.
4. Verificar que para los renglones críticos, la conclusión es verdadera.Ental caso se tiene un Argumento válido ó
5. Detectar si existe un renglón crítico con conclusión falsa.En cuyo caso se dirá Argumento inválido.

DEMOSTRACIÓN FORMAL 

(DIRECTO POR CONTRADICION)

Contradicción

Contradicción es aquella proposición que siempre es falsa para todos los valores de verdad, una de las mas usadas y mas sencilla es p∧p’ .

Como lo muestra su correspondiente tabla de verdad.
p p’ p^p’
0 0 1
1 0 0

EJEMPLOS:

Pruebe presentado una prueba por contradicción que si X * Y = 0, entonces X= 0 o bien Y = 0. Suponga que si a, b y c son números reales con a * b = a * c y a ≠ o, entonces b = c;

Resolución

XY = 0  entonces x ≠ 0  o bien  Y  ≠ 0;

Con X ≠ 0 entonces XY = X*0 = 0

Siendo a = X, b = Y, C = 0 ab= ac entonces XY = X * 0  con  x ≠ 0 entonces concluimos que Y = 0.

El procedimiento de la demostración por contradicción es semejante a la que se realizó por el método directo con la diferencia de que las líneas iniciales de dicha demostración no son únicamente las hipótesis, sino además se incluye en la demostración una línea con la negación de la conclusión. Por otro lado el objetivo de la demostración es llegar a una contradicción.