Laboratório de contradições lógicas

Resolva um novo enigma cuja resposta única foi verificada por pesquisa exaustiva.

Exemplo resolvido — Laboratório de contradições lógicas

Resolvidos	0 / 0
Cadeia de dedução	0/3 equações aplicadas

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Um enigma é um sistema de equações booleanas

Codifique quem diz a verdade como 1 e o mentiroso como 0. Há consistência quando o valor da frase coincide com o bit do papel.

S_X(R) = R_X

O laboratório verifica Sₓ(R) = Rₓ para cada X. Todas as equações partilham o mesmo vetor R e devem valer simultaneamente.

Cada frase é uma função booleana da atribuição completa.

Uma contradição elimina um mundo possível inteiro

Assuma uma atribuição, avalie cada frase e compare o resultado com o papel do orador.

S_X(R) ≠ R_X ⇒ reject R

Uma discrepância basta para rejeitar a atribuição. As pistas identificam a hipótese e a equação que torna o ramo impossível.

A contradição demonstra que um mundo não satisfaz as regras.

Ser resolúvel não basta: a resposta deve ser única

Um enigma pode ser consistente e ter várias atribuições válidas.

|{R : ∀X, S_X(R)=R_X}| = 1

Cada enigma é testado exaustivamente e aceite apenas se sobreviver um único mundo.

O mundo verde é o único modelo do sistema.

Pistas fortes eliminam muitos mundos

Uma frase útil divide os candidatos; uma fraca pode valer igual em quase todos.

candidates: 2ⁿ → … → 1

O motor escolhe a equação ainda não aplicada que remove mais mundos, reduzindo a incerteza sem dar logo a resposta.

Os candidatos diminuem com equações informativas.

A autorreferência não é automaticamente útil

«Digo a verdade» é compatível com os dois papéis e não acrescenta informação.

S_X(R) = R_X

«Estou a mentir» não pode ser dito consistentemente por nenhum papel estrito. O gerador exclui ambos e usa relações entre participantes.

Uma autoafirmação é tautológica; a outra cria uma equação impossível.

Problemas resolvidos na íntegra

Três participantes sob as regras de Cavaleiro/Valete a escolher entre tarefas 7 passos
Três participantes sob as regras de Cavaleiro/Mentiroso: a afirmação de um Cavaleiro tem de ser verdadeira, a de um Mentiroso tem de ser falsa. O laboratório apresenta um enigma novo a cada visita, por isso resolva este no papel — A diz que C está a mentir; B diz que A e C têm o mesmo papel; C diz que pelo menos 2 de nós dizem a verdade. Antes de nomear alguém, conte as atribuições entre as quais está a escolher e, em seguida, reduza-as uma afirmação de cada vez.
1. Não se assume nada sobre quantos Cavaleiros existem, pelo que cada participante é um bit independente: Cavaleiro 1, Mentiroso 0. Um mundo é todo o vetor de 3 bits, e cada um deles começa vivo. Esse é o número com que o painel de mundos abre, e é uma propriedade do elenco, não do que alguém disse.
  
  $2^{3} = 8$
2. Uma afirmação não é um facto sobre a sala; é uma equação sobre quem a profere. A afirmação do orador X é uma função booleana de todo o vetor de papéis R, e a consistência exige que o seu valor de verdade seja igual ao próprio bit de X — verdadeiro para um Cavaleiro, falso para um Mentiroso, uma equação em qualquer dos casos. Todas as 3 equações partilham o mesmo R, razão pela qual não pode determinar A, depois B, depois C separadamente.
  
  $S_{X} (R) = R_{X}, X \in {A, B, C}$
3. Comece por A. Se A for um Cavaleiro, a afirmação confirma-se e C mente; se A for um Mentiroso, a afirmação falha e C diz a verdade. Qualquer um dos ramos deixa A e C com bits diferentes, o que corresponde a 4 dos 8 mundos, estando B ainda livre.
  
  $R_{A} = \neg R_{C} ⟹ 8 \to 4$
4. B afirma que A e C coincidem. Não coincidem, logo a afirmação de B é falsa, pelo que B é um Mentiroso. Sobrevivem dois mundos: A um Cavaleiro com C um Mentiroso, ou A um Mentiroso com C um Cavaleiro.
  
  $R_{B} = [R_{A} = R_{C}] = 0 ⟹ 4 \to 2$
5. C decide a questão. Em ambos os sobreviventes, exatamente 1 participante diz a verdade, pelo que pelo menos 2 de nós é falsa, pelo que o próprio bit de C tem de ser 0. O mundo com C como Cavaleiro afirma algo que o seu próprio papel proíbe e morre. Resta um mundo.
  
  $Σ R = 1 < 2 ⟹ S_{C} = 0 ⟹ R_{C} = 0$
6. Volte atrás e pergunte-se por que razão A e B removeram cada um exatamente metade. Nenhuma das afirmações menciona o seu próprio orador, pelo que, para cada configuração dos outros 2 bits, existe exatamente 1 valor do bit do orador que satisfaz a equação. Uma afirmação sobre outras pessoas deixa sempre 2^n-1 mundos — nunca mais, nunca menos, diga ela o que disser.
  
  $R_{X} = S_{X} (R_{- X}) ⟹ 2^{n - 1} = 2^{2} = 4$
7. A afirmação de C não é desse tipo: pelo menos 2 de nós também conta C, pelo que o bit do orador fica em ambos os lados da equação e o argumento da divisão por metade colapsa. Aplicada isoladamente a todos os 8 mundos, a equação de C deixa 6 — elimina 2 mundos onde as de A e B eliminam cada uma 4.
  
  $# {R : R_{C} = S_{C} (R)} = 6 \neq = 4$
Resposta

A é um Cavaleiro, B e C são Mentirosos — 1 mundo dos 8 com que o painel abre. A unicidade é aritmética e não sorte: 3 oradores que falam cada um apenas sobre outras pessoas reduzem o campo para metade 3 vezes e, se os cortes forem independentes, 2³ reduzido para metade 3 vezes é exatamente 1. É por isso que enigmas desta forma têm toda a gente a mexericar sobre toda a gente. C é a exceção, e isso tem um custo: uma equação que conta o seu próprio orador deixa 6 de 8 em vez de 4, pelo que limpa um quarto do tabuleiro onde as outras limpam metade. Pode calcular esse número para qualquer afirmação candidata antes de conhecer um único papel, o que faz dele a medida honesta de uma pista — não quão astuta soa, mas quanto do tabuleiro remove.

$2^{n} \cdot (\frac{1}{2})^{n} = 1$
Quatro participantes num tema de Lobisomem a contar os mundos vivos 6 passos
Mesmo laboratório, tema do Lobisomem, 4 participantes. Exatamente 1 dos 4 é o Lobisomem, e o Lobisomem é o único que mente. Conte os mundos vivos antes de alguém falar e, em seguida, compare isso com a ronda de 3 pessoas do Cavaleiro.
1. Os papéis continuam a ser bits — Aldeão 1, Lobisomem 0 — e 4 bits livres dariam 16 vetores. Esse é o número que o tema tem de superar.
  
  $2^{4} = 16$
2. O tema é uma restrição, não uma decoração: exatamente 1 bit é 0. Escolher qual é esse bit significa escolher 1 participante em 4, pelo que apenas 4 dos 16 vetores se qualificam. A grelha de mundos lista-os, com o W único a avançar uma posição em cada linha.
  
  $(1 4) = 4$
3. Reduzir o espaço por um fator de 4 vale 2 bits, e estes foram-lhe entregues antes de uma única palavra ser dita.
  
  $lo g_{2} \frac{16}{4} = 2$
4. Agora a comparação que importa. A ronda do Cavaleiro com 3 participantes abre em 8 mundos; esta ronda tem um suspeito extra e abre em 4. Mais pessoas, uma pesquisa menor — o prior ultrapassa o bit que o participante extra adicionou.
  
  $2^{3} = 8 > 4$
5. Um mentiroso também significa exatamente 1 mentira. Todos os 4 participantes falam e apenas a afirmação do Lobisomem é falsa, pelo que 3 das 4 afirmações no ecrã são verdadeiras — algo que sabe antes de ler qualquer uma delas.
  
  $# {X : R_{X} = 0} = 1 ⟹ # {X : S_{X} (R) = 0} = 1$
6. O que torna a força bruta genuinamente simples aqui: 4 mundos vezes 4 equações de oradores são 16 verificações de consistência, e poderia fazê-las no papel. As mesmas 4 pessoas sob as regras de Cavaleiro/Mentiroso seriam 16 mundos vezes 4 equações, o que dá 64.
  
  $4 \times 4 = 16 2^{4} \times 4 = 64$
Resposta

4 de 4, não 16 de 16 — o tema eliminou 75% do tabuleiro antes da primeira afirmação. Aumente a escala e os dois jogos deixam de ser o mesmo jogo. Com n participantes, o espaço do Lobisomem é n e o espaço do Cavaleiro é 2ⁿ: com 10 jogadores, são 10 mundos contra 1024, e o prior vale agora 10 − log₂10 = 6,68 bits. A razão é que uma ronda do Lobisomem apenas pergunta qual deles, pelo que a sua resposta tem no máximo log₂ n bits de largura, por mais cadeiras que se adicionem, enquanto uma ronda do Cavaleiro faz n perguntas independentes de sim ou não e duplica de cada vez que alguém se senta. Adicionar um jogador a uma ronda do Lobisomem adiciona 1 mundo; adicionar um a uma ronda do Cavaleiro duplica-os.

$\frac{2 ^{n}}{n}_{n = 10} = \frac{1024}{10} = 102.4$

Referências (1)

The book that made logic something you can compute with, which is what this lab does: G. Boole, An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities. Walton and Maberly, London, 1854.

Pela equipa 42Math · Atualizado 2026-07-22

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Matemática →

Laboratório de contradições lógicas

Problemas de exemplo