PDF de programación - Teoría 2 - Lógica Proposicional

Teoría Nº 2

Lógica Proposicional

“La lógica es el arte de equivocarse
con confianza”

(J. W. Krutch)

F. de la Informática – Int. a la Programación – Int. a la Computación

Resolución de Problemas y Algoritmos

Segundo Cuatrimestre 2017

1

Lógica Proposicional

Introducción

Casa

Esencia

Casa

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

2

Lógica Proposicional

Concepto

Conceptos son los signos que utilizamos para significar la
esencia de las cosas.

Casa

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

3

Lógica Proposicional

Vagos
Concretos

Conceptos

Abstractos

Imperfectos

Complejos
Simples

¿Cómo nos expresamos los seres humanos?

El lenguaje natural es muy rico, redundante y ambiguo por su relación intrínseca
entre la interpretación del sistema emisor-receptor y el referente del mensaje

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

4

Lógica Proposicional

Introducción

Existen en la realidad un número considerable de problemas con los que una persona
se enfrenta y de los cuales se deben deducir ciertos datos para poder resolverlos.


Una deducción, razonamiento o inferencia, es un tipo de pensamiento que se basa en
la generación de conocimiento nuevo (la conclusión) a partir de un conocimiento
existente (las premisas)

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

5

Ejemplos

Introducción

Todos los hombres son mortales.
Sócrates es un hombre
Por tanto, Sócrates es mortal

PREMISAS

CONCLUSIÓN

Olaf no es español pues es alto, rubio, de tez clara y habla con acento extranjero

CONCLUSIÓN

PREMISAS

Todos los políticos son deshonestos.
Tobías es políticos

Por tanto, Tobías es deshonesto

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

Lógica Proposicional

Si bien la forma en que las personas aplican el poder deductivo es muy personal,
éste podría ser encausado o guiado a través del uso de reglas de deducción.

Es necesario entonces

Lenguaje
natural

Lenguaje
simbólico

Formal

Acotado

Limitado

Transformación

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

7

Lenguaje Natural: Frases y Conjunciones

Si se desea deducir información a partir de nuestro lenguaje cotidiano formado de
frases o expresiones, es necesario poder evaluarlas como verdadera o falsa (aunque
no todas pueden ser evaluadas).
Ejemplos:



Frases categorizables

Lima es la capital de Perú
El cocodrilo es un mamífero
El doble de 3 es 5

Si Juan no tiene dinero entonces
no compra dulces

Frases No categorizables
¡Auxilio!
¿Qué hora es?
Alcánzame el libro

¿Quién ganará las
elecciones?

R e s u m i e n d o :
Toda frase o
expresión que
t i e n e u n a
función de tipo
informativa es
categorizable.

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

8

La misma información se puede transmitir a través de diferentes construcciones gramaticales.

Ejemplo:

1- Socrates es hombre entonces es mortal.
2- Si Socrates es hombre, mortal es.
3- Socrates es hombre.
Socrates es mortal.
4- Socrates es mortal porque todos los
hombres son mortales.

En los casos 2, 3 y 4 se podría llegar a deducir lo mismo que en el caso 1 haciendo
uso de reglas gramaticales y del significado por nosotros conocido asociado a las
palabras.

La diferencia se encuentra en la manera en que se construye la frase.

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

9

Gramaticalmente las frases se pueden distinguir:
•  Frases Simples: constan de un sujeto y un predicado.
•  Frases Compuestas: se conforman a partir de las frases simples unidas por
elementos gramaticales (conjunciones) que las asocian.

Para poder transmitir una misma información por medio de diferentes frases, se
tratará de expresar una idea a través de:

•  una única frase (simple o compuesta).
•  el uso de construcciones gramaticales semejantes.

¿Como poder transmitir información haciendo uso de construcciones
independientemente del significado por nosotros conocido asociado a las palabras?

Mediante el uso de un Lenguaje Simbólico

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

10

Lógica Formal

La Lógica Formal es la ciencia del razonamiento formalmente válido

Se encarga de las formas y de las leyes generales del razonamiento humano

Estudia los principios y métodos a través de los cuales es posible 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.

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

11

Lógica Formal

1.  Todos los snark son bojum
2.  Rufus es un snark
3.  Por tanto, Rufus es bojum.



•  Desde el punto de vista de su estructura este argumento es válido.
•  El significado de los elementos que intervienen no es tomado en cuenta

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

12

Lógica Formal



1- Argentina está en África o Argentina está en Asia.
2- Argentina no está en Asia
3- En consecuencia, Argentina está en África.
El argumento es válido desde el punto de vista lógico, aún cuando sabemos
que la conclusión es falsa.

•  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 segundas no lo son.

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

13

Leng. Simbólico: Enunciados y Conectivas
Medidas para formalizar un lenguaje:
1. Restringir el lenguaje a frases categorizables.
2. Adoptar una nueva terminología. Esto es, llamar:
•  A las frases: enunciados o proposiciones.
•  A los elementos gramaticales que unen frases simples: conectivos.

3. Adoptar una representación simbólica :

•  Para representar los proposiciones: letras mayúsculas.
•  Para representar los conectivos: símbolos tales como ∧ ¬ ∨ ⊕ ⇒ ⇔ .

Una vez que un enunciado del lenguaje natural se representa por medio de la
simbología asociada tenemos una estructura o esqueleto lógico que nos va a permitir
realizar nuestras deducciones. Es decir la forma que tiene dicho enunciado.

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

14

Leng. Formal: Formas Enunciativas



Desde el punto de vista simbólico, es necesario poder lograr deducir información
solamente a través de la forma de los enunciados.
Formas enunciativas: es la forma en que se va a formular una idea de modo que
ésta exprese siempre lo que se desea.
Generalizando:
•  Dados P, Q, R enunciados (proposiciones), se los denomina variables de
enunciado o variables proposicionales.
•  Dado P variable de enunciado, este adquiere valor de: verdadero o falso.
•  Dados P y Q enunciados, la ligadura de ambas a través de un conectivo es también
un enunciado (enunciado compuesto).
•  Dados P y Q enunciados simples (verdaderos o falsos), la ligadura de P con Q, será
también verdadero o falso y sus valores surgen a partir de los valores de las formas
enunciativas que las componen.

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

15

Lógica Proposicional

La construcción de enunciados compuestos requiere del uso de elementos
que permitan establecer una relación entre los enunciados que la componen;
estos elementos se conocen como conectivas lógicas.


Asimismo es necesario poder determinar si un enunciado es Verdadero o
Falso.
La Lógica Proposicional establece las reglas de interpretación de enunciados a
través de Tablas de verdad, y cuales serán las conectivas lógicas básicas a ser
usadas junto con su representación simbólica.


Tabla 1:
Conectivas lógicas

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución de Prob. Y Algortimos

Dpto. de Informática – FCFMyN - 2017

16

Formas Enunciativas Compuestas y Tablas de Verdad
Las formas enunciativas compuestas se forman a partir de enunciados simples
unidos por conectivos.

Ejemplo:


P: ''El agua esta fría y el calentador está descompuesto''



A: El agua está fría
B: El calentador está descompuesto



Conectivo Logico



Donde si:



se representa por



(A ∧ B)

Resta entonces analizar cada una de los conectivos para poder evaluar como
verdadero o falso un enunciado compuesto.

Fund. de la Informática-Int.a la Computación - Int. a la Programación – Resolución d