Labor für logische Widersprüche

Löse ein neues Widerspruchsrätsel, dessen eindeutige Antwort durch vollständige Suche geprüft wurde.

Rechenbeispiel — Labor für logische Widersprüche

Gelöst	0 / 0
Mögliche Welten	8 von 8 übrig
Schlusskette	0/3 Sprechergleichungen angewendet

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Ein Rätsel ist ein System boolescher Gleichungen

Kodiere Wahrheitsredner als 1 und Lügner als 0. Ein Sprecher ist genau dann konsistent, wenn der Wahrheitswert seines Satzes seinem Rollenbit entspricht.

S_X(R) = R_X

Das Labor prüft Sₓ(R) = Rₓ für jeden Sprecher X. Rollen getrennt zu raten reicht nicht: Alle Gleichungen teilen denselben Rollenvektor R und müssen gleichzeitig gelten.

Jeder Satz ist eine boolesche Funktion der vollständigen Rollenzuweisung.

Ein Widerspruch eliminiert eine ganze mögliche Welt

Nimm eine Rollenzuweisung an, werte jeden Satz aus und vergleiche das Ergebnis mit der Rolle des Sprechers.

S_X(R) ≠ R_X ⇒ reject R

Eine einzige Abweichung verwirft die komplette Zuweisung. Dynamische Hinweise nutzen genau diese Methode: Sie nennen eine Annahme und die Sprechergleichung, die ihren Zweig unmöglich macht.

Ein Widerspruchsbeweis zeigt nicht, dass eine Welt unwahrscheinlich wirkt, sondern dass sie die Regeln nicht erfüllen kann.

Lösbar reicht nicht: Die Antwort muss eindeutig sein

Ein Rätsel kann konsistent sein und trotzdem mehrere gültige Rollenzuweisungen besitzen.

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

Jedes erzeugte Rätsel wird vor der Anzeige vollständig geprüft. Der Generator akzeptiert es nur, wenn genau eine mögliche Welt alle Sprechergleichungen überlebt.

Die grüne Welt ist das einzige Modell des vollständigen logischen Systems.

Starke Hinweise entfernen viele Welten

Ein nützlicher Satz teilt die aktuellen Kandidaten; ein schwacher ist in fast allen wahr oder falsch.

candidates: 2ⁿ → … → 1

Die Hinweislogik wählt die noch nicht angewendete Gleichung, die die meisten aktuellen Welten entfernt. Diese kleine Informationsgewinn-Strategie reduziert Unsicherheit, ohne direkt zur Antwort zu springen.

Die Zahl der Kandidaten schrumpft mit jeder informativen Gleichung.

Selbstbezug ist nicht automatisch ein nützlicher Hinweis

„Ich sage die Wahrheit“ passt zu beiden Rollen: Ein Wahrheitsredner sagt es wahr, ein Lügner falsch. Der Satz liefert keine neue Information.

S_X(R) = R_X

„Ich lüge“ ist unter strengen Ritter-und-Schurken-Regeln schlimmer: Keine Rolle kann es konsistent sagen. Der Generator schließt beide Muster aus und verwendet Beziehungen, die andere Teilnehmer einschränken.

Eine Selbstaussage ist eine tautologische Identität; die andere erzeugt eine unerfüllbare Gleichung.

Aufgaben vollständig gelöst

Drei Teilnehmer nach Ritter/Schurke-Regeln bei der Wahl zwischen Aufgaben 7 Schritte
Drei Teilnehmer nach Ritter-und-Knappen-Regeln: Die Aussage eines Ritters muss wahr sein, die eines Knappen falsch. Das Lab gibt bei jedem Besuch ein neues Rätsel aus; lösen Sie dieses also auf dem Papier — A sagt, C lügt; B sagt, A und C haben dieselbe Rolle; C sagt, mindestens 2 von uns sagen die Wahrheit. Zählen Sie, bevor Sie jemanden benennen, die Belegungen, zwischen denen Sie wählen, und reduzieren Sie diese dann Aussage für Aussage.
1. Über die Anzahl der Ritter wird nichts vorausgesetzt, sodass jeder Teilnehmer ein unabhängiges Bit ist: Ritter 1, Knappe 0. Eine Welt ist der gesamte Vektor aus 3 Bits, und jedes davon beginnt als aktiv. Das ist die Zahl, mit der das Welten-Panel öffnet, und sie ist eine Eigenschaft der Besetzung, nicht dessen, was irgendjemand gesagt hat.
  
  $2^{3} = 8$
2. Eine Aussage ist keine Tatsache über den Raum; sie ist eine Gleichung über ihren Sprecher. Die Aussage von Sprecher X ist eine boolesche Funktion des gesamten Rollenvektors R, und die Konsistenz verlangt, dass ihr Wahrheitswert dem eigenen Bit von X entspricht — wahr bei einem Ritter, falsch bei einem Knappen, eine Gleichung in beiden Fällen. Alle 3 Gleichungen teilen sich dasselbe R, weshalb man A, dann B, dann C nicht getrennt bestimmen kann.
  
  $S_{X} (R) = R_{X}, X \in {A, B, C}$
3. Beginnen Sie mit A. Ist A ein Ritter, gilt die Aussage und C lügt; ist A ein Knappe, trifft die Aussage nicht zu und C sagt die Wahrheit. Jeder Zweig lässt A und C mit unterschiedlichen Bits zurück, und das sind 4 der 8 Welten, wobei B noch frei ist.
  
  $R_{A} = \neg R_{C} ⟹ 8 \to 4$
4. B behauptet, A und C stimmen überein. Das tun sie nicht, also ist B's Aussage falsch, somit ist B ein Knappe. Zwei Welten überleben: A ein Ritter mit C als Knappe, oder A ein Knappe mit C als Ritter.
  
  $R_{B} = [R_{A} = R_{C}] = 0 ⟹ 4 \to 2$
5. C entscheidet es. In beiden überlebenden Welten sagt genau 1 Teilnehmer die Wahrheit, sodass mindestens 2 von uns falsch ist; folglich muss das eigene Bit von C 0 sein. Die Welt mit C als Ritter behauptet etwas, das ihre eigene Rolle verbietet, und scheidet aus. Eine Welt bleibt übrig.
  
  $Σ R = 1 < 2 ⟹ S_{C} = 0 ⟹ R_{C} = 0$
6. Gehen Sie zurück und fragen Sie sich, warum A und B jeweils genau die Hälfte entfernt haben. Keine der beiden Aussagen erwähnt ihren eigenen Sprecher, sodass es für jede Belegung der anderen 2 Bits genau 1 Wert des Sprecher-Bits gibt, der die Gleichung erfüllt. Eine Aussage über andere Personen lässt immer 2^n-1 Welten übrig — nie mehr, nie weniger, was auch immer sie besagt.
  
  $R_{X} = S_{X} (R_{- X}) ⟹ 2^{n - 1} = 2^{2} = 4$
7. C's Aussage ist nicht von dieser Art: mindestens 2 von uns zählt auch C, sodass das Bit des Sprechers auf beiden Seiten der Gleichung steht und das Halbierungsargument zusammenbricht. Für sich genommen auf alle 8 Welten angewendet, lässt C's Gleichung 6 übrig — sie eliminiert 2 Welten, wo jene von A und B jeweils 4 eliminieren.
  
  $# {R : R_{C} = S_{C} (R)} = 6 \neq = 4$
Antwort

A ist ein Ritter, B und C sind Knappen — 1 Welt von den 8, mit denen das Panel öffnet. Die Eindeutigkeit ist Arithmetik statt Glück: 3 Sprecher, die jeweils nur über andere sprechen, halbieren das Feld 3-mal, und wenn die Schnitte unabhängig sind, ist 2³ 3-mal halbiert genau 1. Deshalb lassen Rätsel dieser Form jeden über jeden anderen klatschen. C fällt aus dem Rahmen, und das hat seinen Preis: Eine Gleichung, die ihren eigenen Sprecher mitzählt, lässt 6 von 8 statt 4 übrig; sie räumt also ein Viertel des Feldes ab, wo die anderen die Hälfte abräumen. Sie können diese Zahl für jede Kandidaten-Aussage berechnen, bevor Sie eine einzige Rolle kennen, was sie zum ehrlichen Maß für einen Hinweis macht — nicht wie schlau er klingt, sondern wie viel vom Feld er entfernt.

$2^{n} \cdot (\frac{1}{2})^{n} = 1$
Vier Teilnehmer in einem Werwolf-Szenario, die die lebenden Welten zählen 6 Schritte
Dasselbe Lab, Werwolf-Thema, 4 Teilnehmer. Genau 1 der 4 ist der Werwolf, und der Werwolf ist der Einzige, der lügt. Zählen Sie die aktiven Welten, bevor jemand spricht, und vergleichen Sie das dann mit der 3-Personen-Ritter-Runde.
1. Rollen sind weiterhin Bits — Dorfbewohner 1, Werwolf 0 — und 4 freie Bits würden 16 Vektoren ergeben. Das ist die Zahl, die das Thema unterbieten muss.
  
  $2^{4} = 16$
2. Das Thema ist eine Einschränkung, keine Dekoration: Genau 1 Bit ist 0. Die Wahl, welches Bit das ist, bedeutet die Wahl von 1 Teilnehmer aus 4, sodass sich nur 4 der 16 Vektoren qualifizieren. Das Welten-Raster listet sie auf, wobei das einzelne W in jeder Zeile eine Position weiter rückt.
  
  $(1 4) = 4$
3. Die Verkleinerung des Raumes um einen Faktor von 4 ist 2 Bits wert, und diese wurden Ihnen übergeben, bevor ein Wort gesprochen wurde.
  
  $lo g_{2} \frac{16}{4} = 2$
4. Nun der entscheidende Vergleich. Die Ritter-Runde mit 3 Teilnehmern öffnet bei 8 Welten; diese Runde hat einen zusätzlichen Verdächtigen und öffnet bei 4. Mehr Personen, kleinere Suche — der Prior läuft dem Bit davon, das der zusätzliche Teilnehmer hinzugefügt hat.
  
  $2^{3} = 8 > 4$
5. Ein Lügner bedeutet auch genau 1 Lüge. Alle 4 Teilnehmer sprechen und nur die Aussage des Werwolfs ist falsch, sodass 3 der 4 Aussagen auf dem Bildschirm wahr sind — etwas, das Sie wissen, bevor Sie irgendeine davon lesen.
  
  $# {X : R_{X} = 0} = 1 ⟹ # {X : S_{X} (R) = 0} = 1$
6. Was Brute-Force hier wirklich günstig macht: 4 Welten mal 4 Sprecher-Gleichungen sind 16 Konsistenzprüfungen, und die könnten Sie auf dem Papier durchführen. Dieselben 4 Personen unter Ritter/Knappen-Regeln wären 16 Welten mal 4 Gleichungen, was 64 ergibt.
  
  $4 \times 4 = 16 2^{4} \times 4 = 64$
Antwort

4 von 4, nicht 16 von 16 — das Thema hat 75% des Feldes vor der ersten Aussage gelöscht. Skalieren Sie es hoch, und die zwei Spiele sind nicht mehr dasselbe Spiel. Bei n Teilnehmern ist der Werwolf-Raum n und der Ritter-Raum 2ⁿ: Bei 10 Spielern sind das 10 Welten gegenüber 1024, und der Prior ist nun 10 − log₂10 = 6,68 Bits wert. Der Grund ist, dass eine Werwolf-Runde immer nur fragt, welcher eine, sodass ihre Antwort höchstens log₂ n Bits breit ist, wie viele Stühle man auch hinzufügt, während eine Ritter-Runde n unabhängige Ja-oder-Nein-Fragen stellt und sich jedes Mal verdoppelt, wenn sich jemand hinsetzt. Einen Spieler zu einer Werwolf-Runde hinzuzufügen, fügt 1 Welt hinzu; einen zu einer Ritter-Runde hinzuzufügen, verdoppelt sie.

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

Quellen (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.

Vom 42Math-Team · Aktualisiert 2026-07-22

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Mathematik →

Labor für logische Widersprüche

Beispielaufgaben