Aula 9 - Tableaux Semânticos

Prévia do material em texto

Prof. Ricardo Mesquita 
Tableaux Semânticos 
Elementos básicos 
 Definição 
 Os elementos básicos do sistema de tableaux semânticos na 
Lógica Proposicional são definidos pelos conjuntos: 
 o alfabeto da Lógica Proposicional, sem os símbolos de verdade 
false e true; 
 o conjunto das fórmulas da Lógica Proposicional; 
 um conjunto de regras de dedução. 
 
02/19 
Regras de Inferência 
Sejam A e B duas fórmulas da Lógica Proposicional. 
R1: A  B R2: A  B R3: A  B 
 A 
 B A B A B 
 
R4: A  B R5:  A R6: (A  B) 
 A 
A  B  A   B  A  B 
 
R7: (A  B) R8: (A  B ) R9: (A  B) 
  A A 
  B  B  A  B A   B 
03/19 
Heurística 
 Dê sempre preferência para aplicar primeiro as regras que 
não bifurcam o tableau! 
(R1, R5, R7 e R8) 
Motivo: Essa estratégia simplifica a demonstração. 
04/19 
Construção do Tableau 
 Seja {A1, ... , An} um conjunto de fórmulas. 
 A árvore (tab1) a seguir, com apenas um ramo, é um tableau 
iniciado com {A1,...,An}. 
1. A1 
2. A2 
 . . . 
n. An 
Nesse tableau, as fórmulas {A1,...,An} podem ser escritas em 
qualquer ordem. 
 
05/19 
Construção do Tableau 
 Se tab2 é a árvore resultante da aplicação de uma das regras 
(R1, ... , R9) à árvore tab1, então tab2 é também um tableau 
iniciado com {A1, ... , An}. 
 Seja tabi, i ≥ 2, um tableau iniciado com{A1, ... , An}. 
 Se tabi+1 é a árvore resultante da aplicação de uma das regras 
(R1,...,R9) à árvore tabi, então tabi+1 é também um tableau 
iniciado com {A1, ... , An}. 
 
06/19 
Construção do Tableau 
 Ramo: 
 Um ramo em um tableau é uma sequência de fórmulas 
H1, ... , Hn, onde H1 é a primeira fórmula do tableau e, nessa 
sequência, Hi+1 é derivada de Hi, 1 ≤ i < n, utilizando alguma 
regra do sistema de tableau da Lógica Proposicional. 
 
 Ramo fechado: 
 Um ramo em um tableau é fechado se ele contém uma 
fórmula A e sua negação ¬A. 
 
07/19 
Construção do Tableau 
 Ramo saturado: 
 Um ramo em um tableau é saturado se, para toda fórmula 
A do ramo: 
 já foi aplicada alguma regra do sistema Tba à fórmula A, ou seja, 
A já foi expandida por alguma regra; ou 
 não é possível aplicar nenhuma regra do sistema Tba à fórmula 
A, isto é, A é igual a um literal e não é possível expandi-la por 
alguma regra. 
 
 Ramo aberto: 
 Um ramo em um tableau é aberto se ele é saturado e não fechado. 
 
08/19 
Construção do Tableau 
 Tableau fechado: 
 
Um tableau é fechado quando todos os seus ramos são 
fechados. 
 
 Tableau aberto: 
 
Um tableau é aberto se ele possui algum dos seus ramos 
aberto. 
 
09/19 
Prova no Tableau Semântico 
Seja H uma fórmula. 
 Uma prova de H, no sistema Tba, é um tableau fechado 
iniciado com a fórmula ¬H. 
 Nesse caso, H é um teorema do sistema de tableaux 
semânticos Tba. 
 
Exemplo: 
 Verifique se H = (P  Q)  P é uma tautologia. 
 
Atenção: A fórmula deve ser negada ao coloca-la no 
tableau semântico!! 
10/19 
Resolução 
1. ((P  Q)  P) , fórmula H negada 
2. (P  Q) , 1, R7 
3. P , 1, R7 
4. P  Q , 2, R5 
5. P , 3, R5 
6. P  Q P  Q , 4, R4 
7. P P , 6, R1 
8. Q Q , 6, R1 
Ramo FECHADO 
Ramo ABERTO! 
Note que há um ramo aberto. 
Logo, ((P  Q)  P) 
não é tautologia! 11/19 
Outro Exemplo 
 Verifique se a fórmula 
 
 G = ((P  Q)  (P  Q)  P) 
 
 é uma tautologia. 
12/19 
Resolução 
13/19 
Exemplos 
Note que todos os ramos estão 
fechados! Logo, G é tautologia. 14/19 
Satisfatibilidade de Conjuntos 
 Para provar que um conjunto de fórmulas é satisfatível 
utilizando tableau semântico, faça o seguinte: 
 Coloque cada elemento do conjunto de fórmulas no tableau, sem 
negar 
 Caso se obtenha um tableau fechado, o conjunto de fórmulas é 
insatisfatível. 
 Basta que se encontre um ramo aberto (basta um!) e teremos 
um conjunto satisfatível! 
15/19 
Exercícios 
1. Determine se os conjuntos de fórmulas a seguir são ou não 
satisfatíveis: 
a. {S  Q, P  (S  P), S} 
b. {(Q  P), P  R, Q  R} 
c. {P  Q, (Q  R), R  S, (S  P)} 
16/19 
Exercícios 
2. Considere as sentenças a seguir: 
 Guga é determinado. 
 Guga é inteligente. 
 Se Guga é determinado e atleta, ele não é um perdedor. 
 Guga é um atleta se é um amante do tênis. 
 Guga é amante do tênis se é inteligente. 
A afirmação 
 
 “Guga não é um perdedor.” 
 
É uma consequência lógica das sentenças anteriores? 
17/19 
Exercícios 
3. Considere as sentenças: 
 Se Guga joga uma partida de tênis, a torcida comparece se o ingresso é 
barato. 
 Se Guga joga uma partida de tênis, o ingresso é barato. 
A sentença 
 
 Se Guga joga uma partida de tênis, a torcida comparece. 
 
É uma consequência lógica das sentenças anteriores? 
18/19 
Exercícios 
4. Determine se os argumentos a seguir são válidos: 
a. Se Anilton está de férias e o dia está ensolarado, ele irá à 
igreja. Ele irá para a fazenda ou para Goiânia. Não há igreja na 
fazenda. Há igreja em Goiânia. Anilton está de férias e foi para 
a fazenda. Portanto, o dia não está ensolarado. 
b. Se os investimentos na cidade permanecerem constantes, os 
gastos da prefeitura aumentarão ou crescerá o desemprego. Se 
os gastos da prefeitura não aumentarem, os impostos 
municipais poderão ser reduzidos. Se os impostos municipais 
forem reduzidos e os investimentos na cidade permanecerem 
constantes, não haverá desemprego. Portanto, os gastos da 
prefeitura não aumentarão. 
19/19