Lógica Proposicional 1: Rafael Ramirez

Lgica Proposicional 1
rafael ramirez
rafael@iua.upf.es Ocata 320
Lgica proposicional
Un conjunto de variables p, q, r, que representan afirmaciones tales como

Esta caja es roja La luna es de queso La pelota es de plomo La pelota se undira
Cada una toma uno de los valores T (verdadero) o F (falso) Estas variables pueden conectarse usando conectivos lgicos , , , Ejercicio: p1-#1
2
Negacin
Si p representa pau esta en casa, p representa pau no esta en casa
Conjuncin
Si p representa el objeto es rojo y q representa el objeto es redondo, entonces p q represents el objeto es rojo y el objeto es redondo.
es conmutativa: para cualquier valor de p y q, p q tiene el mismo valor que q p

y asociativa: para cualquier valor de p, q y r, p(qr) tiene el mismo valor que (qp)r
4
Disjuncin
Si p representa el objeto es rojo y q representa el objeto es redondo, entonces p q represents el objeto es rojo o el objeto es redondo (o ambas cosas).
es conmutativa? y asociativa?
5
Implicacin
Si p representa el coche no esta en casa y q representa Pau esta fuera (de casa), entonces p q represents si el coche no esta en casa, Pau esta fuera. Si el coche esta en casa, no podemos concluir nada: Pau puede o no estar en casa en todo caso la afirmacin p q es T.
6
Equivalencia
p es equivalente a q si y solo si p y q tienen el mismo valor de verdad Escribimos p q
p q es lo mismo que (p q q p)
Ejercicio: p1-#2
7
Prioridades
Para evitar parentesis exesivos, por convencion los conectivos se aplican Siguiendo el siguiente orden:
, , ,
Por ejemplo la frmula, pqrs Es interpretada como (p q) (r s)
Tablas de verdad
La tabla de verdad de una formula puede determinarse tomando todos las posibles combinaciones de valores de verdad para las variables en la formula, y evaluando el efecto de cada conectivo. Por ejemplo: ((p) q) Tendria la tabla de verdad p T T F F q T F T F ((p) q) T F T T
9
Tablas de verdad
10
Typos de formulas
Tautologa: formula que toma siempre el valor de verdad T (tambien se les llama formula vlida) Contradiccin: formula que toma siempre el valor de verdad F Formula mixta: formula que puede tomar T o F.
Ejercicio: p1-#3
11
Tablas de verdad identicas

Dos formulas A y B son equivalentes sus tablas de verdad son idnticas. Ejemplo p =T (p)
Donde A = p, y B = (p)
Ejercicio: p1-#4 Ejercicio: p1-#5

12
Interpretaciones y modelos
Una interpretacin de una frmula P es una asignacin de valores verdad a todas las variables de P. Entonces, una interpretacion es una linea en la tabla de verdad. Si I es una interpretacion, decimos que P es T o F con respecto a I Un modelo de una formula P es una interpretacin de P si P es T con respecto a esa interpretacion.
13
Satisfacibilidad
Una frmula proposicional es satisfacible si toma el valor T para alguna interpretacion Una formula proposicional es insatisfacible si no es satisfacible, e.d. si su valor es F para todas las interpretaciones, e.d. si es una contradiccin.
Todas la formulas Satisfacibles Tautologias (validas)
Ejercicio: clasifica las siguentes formulas (entre validas, satisfacibles, insatisfacibles) p, (pq), (pp), (pp), (pp), (pp), ((pq)p), (pp)
14
Satisfacibilidad
Una formula A es tautologa (valida) si y solo si A es insatisfacible
A es satisfacible si y solo si A es falsificable.*
* A es falsificable si existe una interpretacion que hace que A valga F

15
La validez de un argumento
Si riego mi jardin, entonces las flores creceran; (premisa) Si las flores no crecen, entonces las malasyerbas lo haran; (premisa) Sabemos que las malasyerbas creceran en mi jardin; (premisa) Por lo tanto, yo riego mi jardin. (conclusion)
16
Si riego mi jardin, entonces las flores creceran; (premisa) Si las flores no crecen, entonces las malasyerbas lo haran; (premisa) Sabemos que las malasyerbas creceran en mi jardin; (premisa) Por lo tanto, yo riego mi jardin. (conclusion) p: riego mi jardin q: las flores creceran r: las malasyerbas creceran
(p q), (q r), r por lo tanto p Que se escribe: (p q), (q r), r | =p

17
Si riego mi jardin, entonces las flores creceran; (premisa) Si las flores no crecen, entonces las malasyerbas lo haran; (premisa) Sabemos que las malasyerbas creceran en mi jardin; (premisa) Por lo tanto, yo riego mi jardin. (conclusion) p: riego mi jardin q: las flores creceran r: las malasyerbas creceran
(p q), (q r), r por lo tanto p
18
Si no hay control de nacimientos, entonces la poblacion crece ilimitadamente. Pero si la poblacion crece ilimitadamente, aumentara el indice de pobreza. Por consiguiente, si no hay control de nacimientos, aumentara el indice de pobreza.
Ejercicio: verificar si el argumento es valido.
Si los jovenes socialistas espaoles apoyan a Almunia, entonces renuncian a su programa de reivindicaciones. Y si combaten a Almunia, entonces favorecen a Aznar. Pero una de dos: o apoyan a Almunia o lo combaten. Por consiguiente, habran de renunciar a su programa de reivindicaciones o favorecer a Aznar
19
Tableaux Semanticos
El tableau semantico es un algorithmo para probar la satisfacibilidad de formulas Una literal es una variable (p.e. p, q,) o la negacion de una variable {p, p} es una pareja de literales complementarias {A, A} es una pareja de formulas complementarias. A es el complemento de A y A es el complemento de A. Considera la formula A = p (q p)
A es T si y solo si ambos p es T y (q p) es T entonces A es T si y solo si 1. P es T y q es T, o 2. P es T y p es T
20
Tableaux Semanticos
A = p (q p)
A es T si y solo si ambos p es T y (q p) es T entonces A es T si y solo si 1. p es T y q es T, o 2. p es T y p es T
A es satisfacible sii existe una interpretacion tal que 1. pasa, o existe una interpretacion tal que 2. pasa. Es A satisfacible? Se reduce a una pregunta sobre la satisfacibilidad de un conjunto de literales Un conjunto de literales es satisfacible sii no contiene una pareja de literales complementarias En el ejemplo, el primer conjunto {p, q} de literales no contiene una pareja de literales complementarias por lo que el conjunto es satisfacible y por lo tanto A es satisfacible. Es mas facil de razonar si representamos la busqueda graficamente.
21
Tableaux Semanticos
A = p (q p)
A es T si y solo si ambos p es T y (q p) es T entonces A es T si y solo si 1. p es T y q es T, o 2. p es T y p es T p (q p) p, q p p, q p, p
Arbol: la raiz es la formula original Las hojas que contengan una pareja de literales compl. se marcan con X mientras que una hoja satisfacible se marca con O El arbol resultante se llama tableau semantico Ejercicio: hacer el mismo analisis para la formula B = (p q) (p q)
22
Tableaux Semanticos
Formulas son conjuciones y son satisfacibles sii ambas formulas 1 y 2 son satisfechas Formulas son disyunciones y son satisfacibles si al menos una de las subformulas 1 o 2 es satisfacha.
23
Manipulacion de formulas
Identidades
24
Manipulacion de formulas
Ejemplo: sin usar tablas de verdad prueba la siguiente formula.
Ejercicio: sin usar tablas de verdad prueba p (p q) =T p
[hint: (p F) (p q)] 25
Conectivos suficientes
Se dice que un conjunto de conectivos es completo si puede ser usado para definir todas las formulas posibles Por ejemplo {, } es un conjunto completo
e.d. podemos definir los otros conectivos a partir de estos dos: p q =def p q p q =def (p q)
26
Normal Forms
Forma normal disyuntiva
Simplificando:
Forma normal conjuntiva
27
La negacin de una frmula

Dada una frmula P, la negacin de P es simplemente
Si la criatura tiene orejas largas y dientes grandes, entonces es un conejo

Solucin: p = la criatura tiene orejas largas q = la criatura tiene dientes grandes r = la criatura es un conejo
Ejercicio: Traducir la afirmacin de conejo a lgica proposicional, negar la formula y traducirla otra vez a lenguaje natural.
28

Lógica Proposicional 1: Rafael Ramirez

Cargado por

Copyright:

Formatos disponibles

Lógica Proposicional 1: Rafael Ramirez

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Lógica Proposicional 1: Rafael Ramirez

Cargado por

Copyright:

Formatos disponibles

Lgica Proposicional 1

Un conjunto de variables p, q, r, que representan afirmaciones tales como

Esta caja es roja La luna es de queso La pelota es de plomo La pelota se undira

Si p representa pau esta en casa, p representa pau no esta en casa

es conmutativa: para cualquier valor de p y q, p q tiene el mismo valor que q p

Tablas de verdad identicas

Ejercicio: p1-#4 Ejercicio: p1-#5

Una formula A es tautologa (valida) si y solo si A es insatisfacible

A es satisfacible si y solo si A es falsificable.*

* A es falsificable si existe una interpretacion que hace que A valga F

(p q), (q r), r por lo tanto p Que se escribe: (p q), (q r), r | =p

Ejercicio: verificar si el argumento es valido.

Ejercicio: sin usar tablas de verdad prueba p (p q) =T p

Forma normal disyuntiva

Forma normal conjuntiva

La negacin de una frmula

Si la criatura tiene orejas largas y dientes grandes, entonces es un conejo

También podría gustarte