Engenharia da Computação 2011.1
Tabela Verdade,
definição de Satisfatibilidade,
conseqüência lógica, e
funções recursivas sob PROP.
Por
Gustavo Cauê (gcsb)
Ricardo Salomão (rssj2)
Propriedade da Extensão
homomórfica única
 Seja A um conjunto, xcA , e F um conjunto de funções
sobre A. Seja B um conjunto, e G um conjunto de
funções sobre B tal que existe uma associação
d: F -> G entre cada função de F com uma função de G
com mesma aridade. Se o fecho indutivo de X sob F,
isto é, X+ for livremente gerado, então, para toda
^
função h: X -> B existe uma única função h: X+ -> B tal
que:
(1) ^v(E) = v(E), se E for um elemento do conjunto base x.
^
(2) ^v(f(E1, ..., En)) = g(v(E1),
..., ^v(En));
onde f E F;
E1,...En E X+;
g = d(f)
Tabela Verdade
 Tabela-verdade é um tipo de tabela matemática usada
em Lógica para determinar se uma fórmula é válida ou se
um seqüente é correto.
Relembrando...
 NEGAÇÃO:
 DISJUNÇÃO:
X
¬X
X
Y
(XvY)
0
1
0
0
0
1
0
0
1
1
1
0
1
1
1
1
 IMPLICAÇÃO:
 CONJUNÇÃO:
X
Y
(X^Y)
X
Y
(X->Y)
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
0
1
1
1
1
1
1
Ф = ((x -> (y -> z)) -> ((¬z) v (x ^ (¬y))))
x
y
z (¬y) (¬z) (y->z) (x->(y->z)) (x^(¬y)) (¬z)v(x^(¬y))
0 00 1
00 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
1
0
1
0
1
0
1
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
0
1
0
1
1
1
0
Ф
1
0
1
0
1
1
1
0
Definição de Satisfatibilidade:
Seja α uma proposição:
 α é dita satisfatível se existe pelo menos uma valoração
que a satisfaz;
 α é dita refutável se existe pelo menos uma valoração que
não a satisfaz;
 α é dita insatisfatível se não existe valoração que a
satisfaz;
 α é dita tautologia se toda valoração a satisfaz;
Ф é satistatível?
x
y
z (¬y) (¬z) (y->z) (x->(y->z)) (x^(¬y)) (¬z)v(x^(¬y))
0 00 1
00 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
1
0
1
0
1
0
1
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
0
1
0
1
1
1
0
Ф
1
0
1
0
1
1
1
0
Ф é refutável?
x
y
z (¬y) (¬z) (y->z) (x->(y->z)) (x^(¬y)) (¬z)v(x^(¬y))
0 00 1
00 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
1
0
1
0
1
0
1
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
0
1
0
1
1
1
0
Ф
1
0
1
0
1
1
1
0
Ф é taulologia?
x
y
z (¬y) (¬z) (y->z) (x->(y->z)) (x^(¬y)) (¬z)v(x^(¬y))
0 00 1
00 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
1
0
1
0
1
0
1
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
0
1
0
1
1
1
0
Ф
1
0
1
0
1
1
1
0
Ф é insatisfatível?
x
y
z (¬y) (¬z) (y->z) (x->(y->z)) (x^(¬y)) (¬z)v(x^(¬y))
0 00 1
00 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
1
0
1
0
1
0
1
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
0
0
1
0
1
0
1
1
1
0
Ф
1
0
1
0
1
1
1
0
Conseqüência lógica:
 Conseqüência lógica é um conceito fundamental na lógica.
Trata-se de uma relação entre um conjunto de sentenças(ou
proposições) e uma sentença (proposição), na qual o
primeiro acarreta no segundo.
Conseqüência lógica:
 EX.:
P
Q
P -> Q
0
0
1
0
1
1
1
0
0
1
1
1
Funções Recursivas sob PROP
 Função que calcula o nº de parênteses;
 Função que calcula o nº total de subexpressões;
 Função que conta o nº total de operadores lógicos;
 Função que monta a árvore sintática;
 Função que calcula o posto de uma prop;
Provas por Indução:
 Teorema: para toda proposição α, o nº de parênteses de
α é par;
 Lema: para todo ф pertencente a PROP, o nº de
subexpressões de ф é no máximo igual a duas vezes o
nº de operadores de ф + 1 (i.e. |s(ф)| = 2xg(ф) +1).
Dúvidas: