Faça um algoritmo (pseudo-código) que receba como entrada duas sentenças quaisquer na linguagem da lógica proposicional, verificando e informando se elas duas são logicamente equivalentes. A verificação deverá ser feita com o uso de tabela verdade (mas se preferer, faça analiticamente). Teste o seu algoritmo com 3 exemplos diferentes e mais as duas da questão 1).
Obs.: Caso não queira algoritmo, faça um programa em C ou em Python ou em …
Passo 1
O que o exercício pede e o que é fornecido:
- Pedido: criar um algoritmo (pseudocódigo) que receba como entrada duas sentenças quaisquer da lógica proposicional e informe se elas são logicamente equivalentes. A verificação deve ser feita usando tabela verdade (ou analiticamente, mas aqui usaremos tabela verdade).
- Entrada do algoritmo: duas sentenças proposicionais quaisquer, por exemplo
e . - Saída do algoritmo: resposta booleana ou mensagem indicando se
e são logicamente equivalentes (ou seja, têm a mesma coluna de verdade para todas as atribuições das variáveis proposicionais). - Restrições e observações dadas: usar tabela verdade; não há limite de tamanho das fórmulas especificado, portanto o algoritmo precisa lidar com fórmulas com qualquer número finito de variáveis proposicionais e operadores usuais (
etc.). - Vamos testar o algoritmo com três exemplos próprios e com mais duas sentenças extras (total de cinco pares de testes).
Passo 2
Conceitos básicos e definição que vou usar (aulas rápidas e essenciais):
- Valores de verdade: cada proposição atômica pode ser verdadeira (
) ou falsa ( ). No cálculo com tabela verdade costuma-se usar para e para , mas aqui usarei e para ficar claro. - Definição de equivalência lógica: duas fórmulas
e são logicamente equivalentes se, para toda atribuição de verdade às suas variáveis atômicas, e têm o mesmo valor de verdade. Em símbolos: para toda atribuição , . - Operadores proposicionais (semântica/verdade):
- Negação:
é quando é ; é quando é . - Conjunção:
é somente se e ; caso contrário é . - Disjunção:
é somente se e ; caso contrário é . - Implicação material:
é equivalente a . Sua tabela é: só é quando e ; nos outros casos é . - Bicondicional:
é quando e têm o mesmo valor; é equivalente a .
- Negação:
- Tabela verdade: enumerar todas as combinações possíveis de
variáveis atômicas (são linhas) e calcular o valor de cada fórmula em cada linha.
Passo 3
Estratégia do algoritmo (visão geral passo a passo, sem código ainda):
- Ler as duas fórmulas
e (strings). - Fazer o pré-processamento: tokenizar e transformar em uma estrutura interna (árvore sintática) que permita avaliação para qualquer atribuição.
- Encontrar o conjunto
de variáveis atômicas presentes em ou . Seja . - Gerar todas as
atribuições de verdade para . - Para cada atribuição
: - Avaliar
com ; obter . - Avaliar
com ; obter . - Se
, então terminar e retornar “não equivalentes”.
- Avaliar
- Se todas as atribuições produziram
, retornar “equivalentes”.
Observação: é suficiente encontrar uma única atribuição que difira para provar não equivalência (podemos parar cedo).
Passo 4
Explicação didática sobre como representar e avaliar fórmulas (detalhes que você precisa para implementar/entender):
- Representação: converter a fórmula textual para uma árvore sintática (AST). Cada nó é um operador e cada folha é uma variável atômica.
- Por que árvore? Porque a avaliação recursiva fica simples: o valor de um nó operador é função dos valores de seus filhos.
- Prioridades típicas (para a conversão):
tem maior prioridade, depois , depois , depois , por último . Parênteses sobrescrevem prioridades. - Converter usando o algoritmo “shunting-yard” (Dijkstra) que transforma infixa para pós-fixa (postfix), e depois construir a árvore a partir do postfix. Isso evita escrever um parser completo.
Passo 5
Pseudocódigo do algoritmo completo (detalhado, passo a passo). Notação: funções e estruturas explicadas logo depois. Usei nomes autoexplicativos para facilitar implementar em qualquer linguagem.
Tokenização e utilitários:
- Tokens válidos: variáveis atômicas (ex.:
), parênteses e , operadores . - Função auxiliar: is_variable(token) → verdadeiro se token é variável atômica.
Pseudocódigo principal:
Algoritmo VerificarEquivalencia(F1_string, F2_string)
1. tokens1 <- Tokenizar(F1_string)
2. tokens2 <- Tokenizar(F2_string)
3. postfix1 <- InfixToPostfix(tokens1) // shunting-yard
4. postfix2 <- InfixToPostfix(tokens2)
5. tree1 <- PostfixToAST(postfix1)
6. tree2 <- PostfixToAST(postfix2)
7. V <- ConjuntoVariaveis(tree1) ∪ ConjuntoVariaveis(tree2)
8. lista_vars <- ordenar(V) // para consistência, ex.: [p,q,r]
9. n <- tamanho(lista_vars)
10. Para cada k de 0 até 2^n - 1 faça:
11. atrib <- AtribuicaoFromIndex(k, lista_vars) // gera mapa var->T/F
12. v1 <- AvaliarAST(tree1, atrib)
13. v2 <- AvaliarAST(tree2, atrib)
14. Se v1 ≠ v2 então:
15. retornar "NAO EQUIVALENTES" (opcionalmente retornar também a atribuição contra-exemplo)
16. Fim Para
17. retornar "EQUIVALENTES"
Explicação das funções usadas:
- Tokenizar(s): remove espaços e separa variáveis, parênteses e operadores em uma lista de tokens.
- InfixToPostfix(tokens): aplica o algoritmo shunting-yard usando precedências:
> > > > . Parênteses controlam. Saída: lista postfix. - PostfixToAST(postfix): percorre postfix; para token:
- se variável: empilha nó folha;
- se operador unário (
): desempilha um nó, cria nó com esse filho, empilha; - se operador binário (
): desempilha dois nós (direita então esquerda), cria nó com esses filhos (esquerda, direita), empilha; - ao final o topo da pilha é a raiz da AST.
- ConjuntoVariaveis(tree): percorre árvore e coleta nomes de folhas (variáveis).
- AtribuicaoFromIndex(k, lista_vars): converte inteiro
em representação binária de bits; por exemplo, se e (binário ), então retorna mapa . - AvaliarAST(tree, atrib): avalia recursivamente:
- Se nó é variável
: retorna atrib[x]. - Se nó é
com filho : retorna NOT(AvaliarAST(A,atrib)). - Se nó é
: retorna AvaliarAST(left,atrib) AND AvaliarAST(right,atrib). - Se nó é
: retorna OR. - Se nó é
: retorna (NOT AvaliarAST(left) ) OR AvaliarAST(right). (equivalente a ). - Se nó é
: retorna equivalência (iguais).
- Se nó é variável
- Notação de retorno: usar
/ internamente.
Passo 6
Explicando cada operador com exemplos numéricos para você entender como avaliar na prova (sem programar):
- Exemplo simples: avaliar
em todas as linhas de : -
→ . -
→ . -
→ . -
→ .
-
- Observação prática: se
é falso, é sempre verdadeiro (material implication). Isso é útil na prova para preencher linhas da tabela rapidamente. - Para
: é quando os valores são iguais. Por exemplo, dá nas linhas e .
Passo 7
Complexidade e comentários práticos para a prova:
- Se houver
variáveis diferentes, gera-se linhas; cada avaliação de fórmula custa tempo proporcional ao tamanho da AST (digamos ). Então tempo total . - Na prova: normalmente
pequeno ( , ou ); tabelas verdade são fáceis de fazer à mão. Se , tabela fica grande; então vale tentar simplificações analíticas (identidades) para reduzir ou usar contra-exemplo se possível. - Dica: sempre primeiro encontre o conjunto de variáveis e calcule
para saber quantas linhas a tabela terá; isso evita surpresas.
Passo 8
Agora vou testar o algoritmo com cinco pares de sentenças. Para cada par vou listar as variáveis, montar a tabela com todas as linhas e comparar as colunas. Ser bem claro e mostrar todos os passos de cálculo (mastigado).
Teste 1 (exemplo clássico — equivalentes):
- Fórmulas:
-
- Variáveis:
. Há linhas. - Tabela e avaliação linha a linha:
-
: . , então . -
: . , . -
: . , . -
: . , .
-
- Colunas finais (em ordem das linhas): ambas
. São idênticas → são equivalentes.
Teste 2 (não equivalentes):
- Fórmulas:
-
- Variáveis:
. linhas. - Tabela:
-
: . . -
: . . -
: . . -
: . .
-
- Colunas:
= ; = . Difere (por exemplo na linha : vs ) → NÃO equivalentes.
Teste 3 (distributiva — equivalentes):
- Fórmulas:
-
- Variáveis:
. linhas. - Tabela (avaliando de forma direta):
Liste as 8 linhas e calcule:-
: -
: . -
: .
-
-
: -
: . -
: .
-
-
: -
: . -
: .
-
-
: -
: . -
: .
-
-
: -
: . -
: .
-
-
: -
: . -
: .
-
-
: -
: . -
: .
-
-
: -
: . -
: .
-
-
- Resultado: ambas colunas têm
exatamente nas mesmas três primeiras linhas e nas outras → equivalentes (essa é a propriedade distributiva).
Teste 4 (De Morgan — equivalentes) — uma das duas “da questão 1)” que eu criei como exemplo extra:
- Fórmulas:
-
- Variáveis:
. linhas. - Tabela:
-
: . . -
: . . -
: simetricamente dá e . -
: . .
-
- Colunas idênticas → equivalentes (Lei de De Morgan).
Teste 5 (implicações trocadas — não equivalentes) — outra “da questão 1)” fictícia:
- Fórmulas:
-
- Variáveis:
. linhas. - Tabela:
-
: ambos . -
: , . Já aqui difere. -
: , . -
: ambos .
-
- Como há linhas com valores diferentes (por exemplo linha
), NÃO equivalentes.
Passo 9
Resumo prático do que você deve fazer na prova (passo a passo rápido e informal, como um checklist):
- Identificar variáveis atômicas em
e . Calcular . - Fazer tabela com todas as combinações (ordem comum: contar binário de
a ou listar lexicograficamente). - Preencher colunas de
e avaliando subfórmulas em ordem (primeiro parênteses internos, depois operadores de maior prioridade). - Se encontrar uma linha onde as colunas diferem, escreva “não equivalentes” e copie a linha como contra-exemplo — muito eficaz em prova.
- Se terminar todas as linhas sem diferença, escreva “equivalentes” (pode também justificar dizendo que as colunas coincidem em todas as
linhas).
Dica emocional: se você estiver cansado, comece tentando encontrar um contra-exemplo (às vezes é bem rápido); só faça a tabela completa se não achar um contra-exemplo fácil.
Resposta
Teste 1: EQUIVALENTES
Teste 2: NAO EQUIVALENTES
Teste 3: EQUIVALENTES
Teste 4: EQUIVALENTES
Teste 5: NAO EQUIVALENTES
Teste 2: NAO EQUIVALENTES
Teste 3: EQUIVALENTES
Teste 4: EQUIVALENTES
Teste 5: NAO EQUIVALENTES