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 F_1 e F_2.
  • Saída do algoritmo: resposta booleana ou mensagem indicando se F_1 e F_2 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 ( \neg,\land,\lor,\to,\leftrightarrow 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 ( T) ou falsa ( F). No cálculo com tabela verdade costuma-se usar 1 para T e 0 para F, mas aqui usarei T e F para ficar claro.
  • Definição de equivalência lógica: duas fórmulas F_1 e F_2 são logicamente equivalentes se, para toda atribuição de verdade às suas variáveis atômicas, F_1 e F_2 têm o mesmo valor de verdade. Em símbolos: F_1 \equiv F_2 \iff para toda atribuição v, v(F_1)=v(F_2).
  • Operadores proposicionais (semântica/verdade):
    • Negação: \neg p é T quando p é F; é F quando p é T.
    • Conjunção: p\land q é T somente se p=T e q=T; caso contrário é F.
    • Disjunção: p\lor q é F somente se p=F e q=F; caso contrário é T.
    • Implicação material: p\to q é equivalente a \neg p \lor q. Sua tabela é: só é F quando p=T e q=F; nos outros casos é T.
    • Bicondicional: p\leftrightarrow q é T quando p e q têm o mesmo valor; é equivalente a (p\to q)\land(q\to p).
  • Tabela verdade: enumerar todas as combinações possíveis de n variáveis atômicas (são 2^n 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):
  1. Ler as duas fórmulas F_1 e F_2 (strings).
  2. Fazer o pré-processamento: tokenizar e transformar em uma estrutura interna (árvore sintática) que permita avaliação para qualquer atribuição.
  3. Encontrar o conjunto V de variáveis atômicas presentes em F_1 ou F_2. Seja n=|V|.
  4. Gerar todas as 2^n atribuições de verdade para V.
  5. Para cada atribuição a:
    • Avaliar F_1 com a; obter v_1\in\{T,F\}.
    • Avaliar F_2 com a; obter v_2\in\{T,F\}.
    • Se v_1\neq v_2, então terminar e retornar “não equivalentes”.
  6. Se todas as atribuições produziram v_1=v_2, 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): \neg tem maior prioridade, depois \land, depois \lor, depois \to, por último \leftrightarrow. 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.: p,q,r,p_1), parênteses ( e ), operadores \neg,\land,\lor,\to,\leftrightarrow.
  • 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: \neg > \land > \lor > \to > \leftrightarrow. Parênteses controlam. Saída: lista postfix.
  • PostfixToAST(postfix): percorre postfix; para token:
    • se variável: empilha nó folha;
    • se operador unário ( \neg): desempilha um nó, cria nó com esse filho, empilha;
    • se operador binário ( \land,\lor,\to,\leftrightarrow): 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 k em representação binária de n bits; por exemplo, se lista\_vars=[p,q,r] e k=5 (binário 101), então retorna mapa \{p=T,q=F,r=T\}.
  • AvaliarAST(tree, atrib): avalia recursivamente:
    • Se nó é variável x: retorna atrib[x].
    • Se nó é \neg com filho A: retorna NOT(AvaliarAST(A,atrib)).
    • Se nó é \land: retorna AvaliarAST(left,atrib) AND AvaliarAST(right,atrib).
    • Se nó é \lor: retorna OR.
    • Se nó é \to: retorna (NOT AvaliarAST(left) ) OR AvaliarAST(right). (equivalente a \neg p \lor q).
    • Se nó é \leftrightarrow: retorna equivalência (iguais).
  • Notação de retorno: usar T/ F internamente.

Passo 6

Explicando cada operador com exemplos numéricos para você entender como avaliar na prova (sem programar):
  • Exemplo simples: avaliar \,p\to q\, em todas as linhas de p,q:
    • p=T,q=T p\to q = T.
    • p=T,q=F p\to q = F.
    • p=F,q=T p\to q = T.
    • p=F,q=F p\to q = T.
  • Observação prática: se p é falso, p\to q é sempre verdadeiro (material implication). Isso é útil na prova para preencher linhas da tabela rapidamente.
  • Para \leftrightarrow: é T quando os valores são iguais. Por exemplo, p\leftrightarrow q T nas linhas (T,T) e (F,F).

Passo 7

Complexidade e comentários práticos para a prova:
  • Se houver n variáveis diferentes, gera-se 2^n linhas; cada avaliação de fórmula custa tempo proporcional ao tamanho da AST (digamos m). Então tempo total O(2^n \cdot m).
  • Na prova: normalmente n pequeno ( 1, 2 ou 3); tabelas verdade são fáceis de fazer à mão. Se n>4, 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 2^n 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:
    • F_{1,1} = p \to q
    • F_{1,2} = \neg p \lor q
  • Variáveis: \{p,q\}. Há 2^2=4 linhas.
  • Tabela e avaliação linha a linha:
    1. p=T,\;q=T: p\to q = T. \neg p = F, então \neg p \lor q = F \lor T = T.
    2. p=T,\;q=F: p\to q = F. \neg p = F, \neg p \lor q = F \lor F = F.
    3. p=F,\;q=T: p\to q = T. \neg p = T, \neg p \lor q = T \lor T = T.
    4. p=F,\;q=F: p\to q = T. \neg p = T, \neg p \lor q = T \lor F = T.
  • Colunas finais (em ordem das linhas): ambas T, F, T, T. São idênticas → são equivalentes.
Teste 2 (não equivalentes):
  • Fórmulas:
    • F_{2,1} = p \land q
    • F_{2,2} = p \lor q
  • Variáveis: \{p,q\}. 2^2=4 linhas.
  • Tabela:
    1. p=T,q=T: p\land q = T. p\lor q = T.
    2. p=T,q=F: p\land q = F. p\lor q = T.
    3. p=F,q=T: p\land q = F. p\lor q = T.
    4. p=F,q=F: p\land q = F. p\lor q = F.
  • Colunas: p\land q = T,F,F,F; p\lor q = T,T,T,F. Difere (por exemplo na linha p=T,q=F: F vs T) → NÃO equivalentes.
Teste 3 (distributiva — equivalentes):
  • Fórmulas:
    • F_{3,1} = (p\land q)\lor(p\land r)
    • F_{3,2} = p \land (q\lor r)
  • Variáveis: \{p,q,r\}. 2^3=8 linhas.
  • Tabela (avaliando de forma direta):
    Liste as 8 linhas e calcule:
    1. p=T,q=T,r=T:
      • F_{3,1}: (T\land T)\lor(T\land T) = T \lor T = T.
      • F_{3,2}: T \land (T\lor T) = T \land T = T.
    2. p=T,q=T,r=F:
      • F_{3,1}: (T\land T)\lor(T\land F) = T \lor F = T.
      • F_{3,2}: T \land (T\lor F) = T \land T = T.
    3. p=T,q=F,r=T:
      • F_{3,1}: (T\land F)\lor(T\land T) = F \lor T = T.
      • F_{3,2}: T \land (F\lor T) = T \land T = T.
    4. p=T,q=F,r=F:
      • F_{3,1}: (T\land F)\lor(T\land F) = F \lor F = F.
      • F_{3,2}: T \land (F\lor F) = T \land F = F.
    5. p=F,q=T,r=T:
      • F_{3,1}: (F\land T)\lor(F\land T) = F \lor F = F.
      • F_{3,2}: F \land (T\lor T) = F \land T = F.
    6. p=F,q=T,r=F:
      • F_{3,1}: F.
      • F_{3,2}: F.
    7. p=F,q=F,r=T:
      • F_{3,1}: F.
      • F_{3,2}: F.
    8. p=F,q=F,r=F:
      • F_{3,1}: F.
      • F_{3,2}: F.
  • Resultado: ambas colunas têm T exatamente nas mesmas três primeiras linhas e F 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:
    • F_{4,1} = \neg (p \land q)
    • F_{4,2} = \neg p \lor \neg q
  • Variáveis: \{p,q\}. 2^2=4 linhas.
  • Tabela:
    1. p=T,q=T: \neg(p\land q)=\neg T = F. \neg p \lor \neg q = F \lor F = F.
    2. p=T,q=F: \neg(p\land q)=\neg F = T. \neg p \lor \neg q = F \lor T = T.
    3. p=F,q=T: simetricamente dá T e T.
    4. p=F,q=F: \neg(p\land q)=\neg F = T. \neg p \lor \neg q = T \lor T = T.
  • 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:
    • F_{5,1} = p \to q
    • F_{5,2} = q \to p
  • Variáveis: \{p,q\}. 2^2=4 linhas.
  • Tabela:
    1. p=T,q=T: ambos T.
    2. p=T,q=F: p\to q = F, q\to p = T. Já aqui difere.
    3. p=F,q=T: p\to q = T, q\to p = F.
    4. p=F,q=F: ambos T.
  • Como há linhas com valores diferentes (por exemplo linha p=T,q=F), 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):
  1. Identificar variáveis atômicas em F_1 e F_2. Calcular 2^n.
  2. Fazer tabela com todas as combinações (ordem comum: contar binário de 0 a 2^n-1 ou listar lexicograficamente).
  3. Preencher colunas de F_1 e F_2 avaliando subfórmulas em ordem (primeiro parênteses internos, depois operadores de maior prioridade).
  4. Se encontrar uma linha onde as colunas diferem, escreva “não equivalentes” e copie a linha como contra-exemplo — muito eficaz em prova.
  5. Se terminar todas as linhas sem diferença, escreva “equivalentes” (pode também justificar dizendo que as colunas coincidem em todas as 2^n 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

Exercícios relacionados