´ Matematica ´ Ampliacion Discreta ´ Justo Peralta Lopez U  A´ı ´ D  A  A´ M´

´ Teor´ıa Semantica

1

´ Introduccion

2

´ semantica ´ Definicion de las proposiciones

3

Diagrama de valores de certeza

4

´ de formulas. ´ Evaluacion Tablas de verdad

5

´ ´ Concepto semantico de deduccion

6

´ correcta Tautolog´ıa asociada a una deduccion

7

´ Algebra de Boole

8

Forma disyuntiva normal

´ Matematica ´ Ampliacion Discreta

´ Teor´ıa Semantica

´ Teor´ıa Semantica ´ Introduccion

´ ´ ´ que en los La teor´ıa semantica del calculo proposicional utiliza la misma simbolizacion ´ natural, una estructura deductiva era valida ´ cap´ıtulos anteriores. En deduccion (razomaiento correcto), si a partir de las premisas, usando los axiomas y reglas de ´ Ahora, para discutir sobre la validez de una inferencia, pod´ıamos llegar a la conclusion. ´ de significados a las estructura deductiva, lo haremos mediante la asignacion proposiciones. ´ de este sistema esta´ formado por: La descripcion Conjunto de significados de las proposiciones. ´ semantica ´ Definicion de las conectivas. ´ semantica ´ ´ correcta. Definicion de deduccion

´ Matematica ´ Ampliacion Discreta

´ Teor´ıa Semantica

´ Teor´ıa Semantica ´ semantica ´ Definicion de las proposiciones

´ de las proposiciones atomicas ´ Definicion ´ solo ´ se le puede asignar dos valores A una proposicion

V

´ es verdadera Si la proposicion

F

´ es falsa Si la proposicion

´ semantica ´ Definicion de las conectivas ´ Negacion A V F

´ Matematica ´ Ampliacion Discreta

¬A F V

´ Teor´ıa Semantica

´ Teor´ıa Semantica ´ semantica ´ Definicion de las proposiciones

´ de las conectivas Definicion A V ´ Conjuncion V F F

B V F V F

A ∧B V F F F

A V ´ Disyuncion V F F

B V F V F

A ∨B V V V F

A V ´ o condicional simple V Implicacion F F

B V F V F

A →B V F V V

A V Equivalencia o deble condicional V F F

B V F V F

A ↔B V F F V

´ Matematica ´ Ampliacion Discreta

´ Teor´ıa Semantica

´ Teor´ıa Semantica Diagrama de valores de certeza

´ ´ Debemos conocer el valor semantico de cada una de las proposiciones atomicas. Ejemplo

(

P

∨

´ Matematica ´ Ampliacion Discreta

Q

)

∧

R

´ Teor´ıa Semantica

´ Teor´ıa Semantica ´ de formulas. ´ Evaluacion Tablas de verdad

Ejemplo p ∧(q∨r )↔(p ∧q)∨(p ∧r )

p V V V V F F F F

q V V F F V V F F

r V F V F V F V F

q∨r V V V F V V V F

A p ∧(q∨r ) V V V F F F F F

´ Matematica ´ Ampliacion Discreta

p ∧q V V F F F F F F

B (p ∧q)∨(p ∧r ) V V V F F F F F

´ Teor´ıa Semantica

A ↔B V V V V V V V V

´ Teor´ıa Semantica ´ de formulas. ´ Evaluacion Tablas de verdad

´ Una asignacion ´ particular de significados. Se corresponde con una Interpretacion: l´ınea de la tabla. ´ cuyo resultado es V. Modelo: Interpretacion Tautolog´ıa: Si el significado es siempre verdad. ´ Si el significado es siempre falso. Contradiccion: ´ la interpretacion. ´ Falacia: Si el significado es diferente segun

´ Matematica ´ Ampliacion Discreta

´ Teor´ıa Semantica

´ Teor´ıa Semantica ´ ´ Concepto semantico de deduccion

´ Definicion Dada una estructura deductiva P1 , P2 , . . . , Pn ⇒ Q ´ que simultaneamente decimos que es correcta cuando no existe ninguna interpretacion ´ Q falsa. haga a las premisas P1 , P2 , . . . , Pn verdaderas y a la conclusion Ejemplo A , A →B ⇒ B A V V F F

B V F V F

´ Matematica ´ Ampliacion Discreta

A →B V F V V

B V F V F

´ Teor´ıa Semantica

´ Teor´ıa Semantica ´ correcta Tautolog´ıa asociada a una deduccion

´ es que si la estructura deductiva Lo que nos dice el teorema de la deduccion P1 , P2 , . . . , Pn ⇒ Q ´ ´ lo es (demostrar) es correcta o valida, entonces tambien P1 , P2 , . . . , Pn−1 ⇒ Pn →Q ´ sucesivamente, tambien ´ seran ´ validas las Si seguimos realizando la misma operacion estructuras P1 , P2 , . . . , Pn−2 ⇒ Pn−1 →(Pn →Q ) P1 , P2 , . . . , Pn−3 ⇒ Pn−2 →(Pn−1 →(Pn →Q ))

. . . P1 ⇒ P2 →(P3 →(P4 → . . . (Pn →Q ) . . . ) ⇒ P1 →(P2 →(P3 →(P4 → . . . (Pn →Q ) . . . ))

Y cuando tenemos algo de la forma ⇒ A , quiere decir que no hace falta ninguna premisa para que se deduzca A , o lo que es lo mismo, A siempre es verdad y por lo tanto debe ser una tautolog´ıa.

´ Matematica ´ Ampliacion Discreta

´ Teor´ıa Semantica

´ Teor´ıa Semantica ´ Algebra de Boole

A partir de los significados {V , F } o {0, 1} definimos las siguientes operaciones:

+ 0 1

0 0 1

1 1 1

∗ 0 1

´ Matematica ´ Ampliacion Discreta

0 0 10

1 0 1

´ Teor´ıa Semantica

0

0 1

1 0

´ Teor´ıa Semantica ´ Algebra de Boole

´ Definicion ´ de boole con las siguientes propiedades: < {0, 1}, +, ∗,0 > es un algebra 1

Conmutativa: x +y =y +x yx ∗ xy

2

Existencia de Elemento Neutro. x +0=x

3

x ∗1=x

Distributiva x + (yz ) = (x + y )(x + z ) x (y + z ) = xy + xz

4

Complementario x + x0 = 1

5

Idempotencia x +x =x

6

xx 0 = 0 x ∗x =x

´ Absorcion x + xz = x x (x + y ) = x ´ Matematica ´ Ampliacion Discreta

´ Teor´ıa Semantica

´ Teor´ıa Semantica ´ Algebra de Boole

1

´ Dominacion

2

´ Doble negacion

x +1=1

x ∗0=0

(x 0 )0 = x 3

Asociativa x (yz ) = (xy )z x + (y + z ) = (x + y ) + z

4

Morgan

(x + y )0 = x 0 y 0 (xy )0 = x 0 + y 0

´ Matematica ´ Ampliacion Discreta

´ Teor´ıa Semantica

´ Teor´ıa Semantica Forma disyuntiva normal

´ Definicion ´ booleana E en estas variables, Sea x1 , . . . , xn un conjunto de variables. Por una expresion ´ construida a partir de las escrita como E (x1 , . . . , xn ), significamos cualquier expresion variables, usando las operaciones booleanas conocidas. ´ Definicion Un literal es una variable o variable complementada ´ Definicion ´ literales, en los que dos Un producto fundamental es un literal o producto de dos o mas literales no contengan la misma variable. ´ Definicion Un producto fundamental se dice que esta´ incluido en otro producto fundamental si los literales del primer producto P1 esta´ incluido en el segundo P2 . ´ Definicion ´ booleana E se dice que esta´ en que esta´ en forma disyuntiva normal si E es Una expresion ´ productos fundamentales, tales que un producto fundamental o suma de dos o mas ninguno este´ incluido en los otros. ´ Matematica ´ Ampliacion Discreta

´ Teor´ıa Semantica

´ Teor´ıa Semantica Forma disyuntiva normal

Algoritmo Forma Disyuntiva Normal 1

´ (D.N), podemos mover la operacion ´ Usando las leyes de Morgan y la involucion ´ complementaria a cualquier parentesis hasta que finalmente se aplique a variables simples.

2

Usando la ley distributiva, podemos a su vez transformar E en una suma de ´ productos; y entonces usando la ley conmutativa, idempotente y de absorcion podemos transformar E a su f.d.n.

´ Definicion ´ E esta´ en su forma disyuntiva normal completa, si esta´ en f.d.n . y cada Una expresion producto fundamental implica a todas las variables. Ejemplo ´ Pasar a su f.d.n.c. la expresion E (a , b , c ) = ((ab )0 c )0 ((a 0 + c )(b 0 + c 0 ))0

´ Matematica ´ Ampliacion Discreta

´ Teor´ıa Semantica

´ Teor´ıa Semantica Forma disyuntiva normal

Teorema ´ booleana E (x1 , . . . , xn ) no nula puede ser puesta en su f.d.n o f.d.n.c y tal Toda expresion ´ es unica ´ representacion

´ Matematica ´ Ampliacion Discreta

´ Teor´ıa Semantica