Lógica para Computação - Semântica: cálculo, valoração, Extensão homomórfica única, Valoração-verdade, Satisfabilidade, Tautologia, etc - aula6 log cin

Prévia do material em texto

Lógica Matemática 
Para Computação 
Lógica Prosicional 
Semântica 
 Agora vamos estudar o significado das 
expressões da lógica proposicional. 
 Dado que o conjunto das proposições PROP é 
livremente gerado, sabemos que podemos definir 
funções recursivamente sobre PROP, pois o 
resultado será seguro do ponto de vista 
matemático. 
 Particularmente, estamos interessados em definir 
uma função que calcula o valor de uma 
proposição recursivamente, baseada no fato de 
que o valor das possíveis variáveis que nela 
ocorrem está fixado. 
 
Cálculo do valor de uma expressão numérica 
Definição formal desse processo 
Z 
X 
X+ 
Σ* 
-1 
0 
f+ 
F 
f* 
SOMA 
MULT 
2 
G 
v 
valor 
d 
Cálculo do valor de uma expressão numérica 
Definição formal desse processo 
valor: X+ Z v: XZ d: F  G 
 
valor(((3*x)+(3*y))+8) = 
soma(valor((3*x)+(3*y)),valor(8)) = 
soma(soma((valor(3*x),valor(3*y)),valor(8)) = 
soma(soma(mult(valor(3),valor(x)),mult(valor(3),valor(y))),valor(8)) = 
soma(soma(mult(v(3),v(x)),mult(v(3),v(y))),v(8)) 
Lógica proposicional - Semântica 
Valoração 
 Uma valoração é uma função v: X Z de forma 
que existe uma extensão : X+  Z tal que: 
 
 (e) = v(e), se e for atômica 
 
 ((e1+e2)) = soma( (e1), (e2)) 
 
 ((e1*e2)) = mult( (e1), (e2)) 
 
 
 
^ v 
^ v 
^ v ^ v ^ v 
^ v ^ v ^ v 
Cálculo do valor de uma expressão lógica 
Definição formal desse processo 
Booleano 
X 
X+ 
Σ* 
1 
0 
F G 
v 
valor f 
f 
f 
f 
E 
OU 
SE -ENTÃO 
NÃO 
d 
Semântica: Valoração 
 Uma valoração é uma função v: X B tal que 
 existe uma extensão : X+  B de forma que: 
 
 (e) = v(e), se e for atômica, 
 
 ((e1e2)) = E( (e1), (e2)), 
 
 ((e1e2)) = OU( (e1), (e2)) , ((e)) = NÃO( (e)), 
 
 ((e1e2)) = SE-ENTÃO( (e1), (e2)) 
 
 
^ v 
^ v 
^ v ^ v 
^ v 
^ v ^ v ^ v 
^ v ^ v ^ v 
^ v 
Semântica 
Valor das expressões da lógica proposicional 
 NÃO(x) = 1- x 
 E(x,y) = min(x,y) 
 
 OU(x,y) = max(x,y) 
 
 
TEOREMA 
Extensão homomórfica única 
 Seja A um conjunto e X  A. Suponha que F seja um 
conjunto de funções sobre A, cada uma com a sua 
aridade. Seja B um outro conjunto, G um conjunto de 
funções sobre B, e d uma bijeção de F para G que 
preserva a aridade. 
 Se X+ for livremente gerado, então para toda função h : 
X B, existe uma única função : X+  B tal que: 
 
 (i) (x) = h(x), para todo elemento x X; 
 
 (ii) (f(x1,...,xn)) = g( (x1),..., (xn)), para toda f  F, 
aridade de f = n, g=d(f) e x1...xn  X+ 
 
 
^ 
h
 
^ 
h
 
^ 
h
 
^ 
h
 
^ 
h
 
Lógica Proposicional - Semântica 
Definição da função de valoração-verdade 
 Seja PROP o conjunto de proposições da 
lógica proposicional. Então uma função de 
valoração verdade h é uma função que atribui 
a cada variável um valor booleano, ou valor 
verdade . 
 
Observação: Como PROP é livremente gerado, o 
Teorema da Extensão Homomórfica Única garante 
que para cada valoração-verdade h:X  {0,1}, existe 
uma única extensão ĥ: PROP  {0,1}, que é 
exatamente a função que calcula o valor-verdade de 
uma dada expressão. 
Valoração-verdadade 
Exemplo 
 
 
 Seja h: X  {0,1} a seguinte valoração verdade: 
 h(x) = 0; 
 h(y) = 1; 
 h(z) = 0; 
 
 Vamos calcular o valor-verdade da proposição 
 φ = ( (¬z)  (xy) ) 
 
 
Valoração-verdadade 
Exemplo 
 
 Sabemos que o valor será dado pela extensão única 
de h, dada por ĥ: PROP{0,1} tal que: 
 
 ĥ( (¬z)(xy) ) 
 = E( ĥ((¬z)), ĥ((xy)) ) 
 = E( NÃO(ĥ(z)), OU(ĥ(x), ĥ(y)) ) 
 = E( NÃO(h(z)), OU(h(x), h(y)) ) 
 = E( NÃO(0), OU(0,1) ) 
 = E(1, 1) = 1 
 
 Portanto o valor-verdade de φ é 1. 
 
 
Lógica Proposicional - Semântica 
Valoração que satisfaz uma proposição 
 
 Uma valoração w satisfaz uma proposição φ se a 
sua extensão ŵ aplicada a φ dá como resultado o 
valor-verdade “1”. 
 
 Resumindo: uma w: X  {0,1} satisfaz uma fórmula 
φ se ŵ(φ) = 1. 
 
 
 
 
Lógica Proposicional - Semântica 
Satisfabilidade, Tautologia, etc. 
 
 Seja φ uma proposição: 
 
 φ é dita satisfatível se existe pelo menos uma 
valoração w que a satisfaz. (i.e., ŵ(φ) = 1). 
 φ é chamada de tautologia se toda valoração a 
satisfaz. 
 φ é dita refutável se existe pelo menos uma 
valoração que não a satisfaz. (i.e., ŵ(φ) = 0). 
 φ é chamada de insatisfatível se nenhuma 
valoração a satisfaz. 
 
 
 
Lógica Proposicional - Semântica 
Satisfabilidade, Tautologia, etc. 
 
 Dada uma proposição φ, pergunta-se: 
 
 φ é satisfatível ? (SAT) 
 φ é tautological ? (TAUT) 
 φ é refutável ? (REFUT) 
 φ é insatisfatível ? (INSAT) 
 
 Exemplo: Seja φ = ( (x→(y→z)) → ((¬z)  (x  (¬y))) ) 
 
 Pergunta-se: φ é satisfatível?