Gerador de TabelaVerdade
Diego Correia Aragão (dca)
Slides adaptados de Luiz Carlos d´Oleron (lcadb)
O Problema
1.
Modelar (sub-conjunto das) expressões
da lógica proposicional (sintaxe e
propriedades)
2.
Interpretar a cadeia com todas as suas
possíveis valorações e construir sua
tabela verdade.
A especificação do projeto está em:
http://www.cin.ufpe.br/~mlogica/tabela
3.
Bem vindo ao mundo Virtual

Desafios:
Adaptar o modelo matemático a
uma realidade virtual
 Para isso usaremos algumas
linguagens que não são
especializadas para isso:

Java, C ou C++
Modelo de Negócios
Exemplo: (x + (-y))
Expressao
Expressao
Expressao
Expressao
x = new ExpressaoAtomica(‘x’);
y = new ExpressaoAtomica(‘y’);
negY = new Negacao(y);
ou = new ExpressaoOU(x, negY);
String e = ou.representacao();
System.out.println(e);
(x+(-y))
Definição recursiva:
representacao()
//na classe ExpressaoAtomica
String representacao(){
return this.simbolo + “”;
}
//na classe Negacao
String representacao(){
return “(-” + this.getE().representacao() +
“)”;
}
//na classe ExpressaoE, bem parecido na
//ExpressaoOU
String representacao(){
return “(” + this.getE1().representacao() +
“.” + this.getE2().representacao() + “)”;
}
Definição recursiva:
listaSubExpressoes()
//na classe ExpressaoAtomica
List listaSubExpressoes (){
List retorno = new ArrayList();
//o conjunto de subexpressões de uma expressão
//atomica é ela mesma
String e = this.representacao();
retorno.add(e);
return retorno;
}
//na classe Negacao
List listaSubExpressoes (){
//pega lista de sua sub-expressão
List retorno =
this.getE().listaSubExpressoes();
//adiciona a si mesma
String e = this.representacao();
retorno.add(e);
return retorno;
}
Definição recursiva:
listaSubExpressoes()
//na classe ExpressaoBinaria
List listaSubExpressoes (){
//pega lista de suas sub-expressões
List retorno =
this.getE1().listaSubExpressoes();
List temp =
this.getE2().listaSubExpressoes();
Object o = null;
Iterator i = temp .iterator();
while(i.hasNext()){
o = i.next();
//Só adiciona se não contiver
if(!retorno.contains(o)){
retorno.add(o);
}
}
//adiciona a si mesma
String e = this.representacao();
retorno.add(e);
return retorno;
}
E agora?

Temos duas missões:
Construir uma Expressão a partir
de uma String
 Interpretá-la, calculando suas
possíveis valorações

Solução


Vamos usar o conceito que nos
foi passado pelo Teorema da
Extensão Homomórfica Única,
utilizando recursão
Usaremos recursão para:

Dada uma expressão φ qualquer,
identificaremos suas subexpressões (se existirem),
construindo/calculando
recursivamente
Construindo a expressão

Dada uma string s:
Se é de tamanho 1, construímos
uma nova ExpressaoAtomica
 Se não, encontramos seu
operador raiz*, e criamos uma
Expressao(Neg, E, Ou ou Imp), a
partir da operação correspondente
a este char, utilizando recursão
nos seus operandos

Encontrando o operador raiz

O operador raiz é o operador que
fica na raiz da árvore da
expressão:

Para encontrá-lo vamos contar
Encontrando o operador raiz
1.
2.
3.
Desconsidere o primeiro ‘(’ e o
último ‘)’
Percorra a expressão e vá
contando sempre a diferença
∆ entre o número de ‘(’ e o
número de ‘)’
O primeiro operador (+,- ou .)
que você encontrar quando (∆
== 0) é o operador raiz.
Interpretando expressões


Para interpretar (i.e. calcular) as
expressões, devemos implementar o
método de calcular obedecendo a
tabela-verdade de cada operador, e
calcular a partir da chamada
recursiva do método com seus
operandos (como na definição do
Teorema de Extensão H.U.)
O método deverá se apoiar num
conjunto de valorações pré-definidos
para os casos base (i.e. v(x) = 1,
onde x é atômica)
Agora é só imprimir


Agora que sabemos modelar uma
Expressao a partir de uma String, e
temos métodos para encontrar suas
sub-expressões, seu valor-verdade,
e sua representação como String, é
só imprimir as tabelas conforme a
especificação do projeto 
Cuidado para não adicionar subexpressões repetidas!
Observações


Para projetos em Java, tirem bem
proveito de conceitos de Orientação
a Objetos
Esta não é a única forma de resolver
o projeto, é possível resolvê-lo
utilizando pilhas e diversas outras
maneiras, fica a critério do aluno
utilizar o método que se sentir mais
à vontade.
Boa Sorte
*Adaptado por Diego Aragão (dca), a partir de slides originais produzidos por Luiz Carlos
(lcadb), para o projeto do Avaliador de Expressões (na época)