Loogiliste vastuolude labor

Lahenda uus vastuolumõistatus, mille ainus vastus on ammendava otsinguga kontrollitud.

Näidisarvutus — Loogiliste vastuolude labor

Lahendatud	0 / 0
Võimalikud maailmad	8/8 alles
Järeldusahel	0/3 kõnelejavõrrandit rakendatud

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Mõistatus on Boole'i võrrandisüsteem

Kodeeri tõerääkija arvuga 1 ja valetaja arvuga 0. Kõneleja on kooskõlaline, kui lause väärtus võrdub tema rollibitiga.

S_X(R) = R_X

Labor kontrollib iga X korral Sₓ(R) = Rₓ. Kõik võrrandid jagavad sama vektorit R ja peavad kehtima korraga.

Iga lause on täieliku rollijaotuse Boole'i funktsioon.

Vastuolu kõrvaldab terve võimaliku maailma

Eelda rollijaotust, hinda iga lauset ja võrdle tulemust kõneleja rolliga.

S_X(R) ≠ R_X ⇒ reject R

Ühest lahknevusest piisab jaotuse hülgamiseks. Vihje nimetab eelduse ja võrrandi, mis muudab haru võimatuks.

Vastuolu tõestab, et maailm ei saa reegleid täita.

Lahenduvusest ei piisa: vastus peab olema ühene

Mõistatus võib olla kooskõlaline, kuid mitme kehtiva jaotusega.

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

Iga mõistatust kontrollitakse ammendavalt ning see võetakse vastu ainult ühe ellujäänud maailma korral.

Roheline maailm on süsteemi ainus mudel.

Tugevad vihjed eemaldavad palju maailmu

Kasulik lause jaotab kandidaate; nõrk võib olla peaaegu kõigis sama väärtusega.

candidates: 2ⁿ → … → 1

Vihjemootor valib rakendamata võrrandi, mis eemaldab enim maailmu, vähendades ebakindlust vastust paljastamata.

Informatiivsed võrrandid vähendavad kandidaatide arvu.

Enesele viitamine pole automaatselt kasulik

„Ma räägin tõtt“ sobib mõlema rolliga ega lisa infot.

S_X(R) = R_X

„Ma valetan“ ei sobi rangete reeglite all kummagi rolliga. Generaator väldib mõlemat ning kasutab osalejate suhteid.

Üks eneseväide on tautoloogia, teine võimatu võrrand.

Ülesanded täielikult lahendatud

Kolm osalejat rüütli/kaabaka reeglite järgi ülesannete vahel valimas 7 sammu
Kolm osalejat rüütlite ja kaabakate reeglite kohaselt: rüütli lause peab osutuma tõeseks, kaabaka oma vääraks. Labor jagab iga külastusega uue mõistatuse, seega lahenda see paberil — A ütleb, et C valetab; B ütleb, et A-l ja C-l on sama roll; C ütleb, et vähemalt 2 meist räägivad tõtt. Enne kellegi nimetamist loenda väärtustused, mille vahel valid, ning seejärel vähenda neid lause haaval.
1. Rüütlite arvu kohta ei tehta ühtegi eeldust, seega on iga osaleja sõltumatu bitt: rüütel 1, kaabakas 0. Maailm on 3 bitist koosnev terviklik vektor ning igaüks neist alustab elusana. See on arv, millega maailmade paneel avaneb, ning see on osalejate koosseisu, mitte kellegi öeldu omadus.
  
  $2^{3} = 8$
2. Lause ei ole fakt ruumi kohta; see on võrrand selle kõneleja kohta. Kõneleja X lause on kogu rollivektori R Boole'i funktsioon ning kooskõlalisus nõuab, et selle tõeväärtus võrduks X-i enda bitiga — rüütli puhul tõene, kaabaka puhul väär, igal juhul üks võrrand. Kõik 3 võrrandit jagavad sama R-i, mis tõttu ei saa määrata eraldi A-d, siis B-d ja siis C-d.
  
  $S_{X} (R) = R_{X}, X \in {A, B, C}$
3. Alusta A-st. Kui A on rüütel, siis lause kehtib ja C valetab; kui A on kaabakas, siis lause ei kehti ja C räägib tõtt. Mõlema haru korral jäävad A-le ja C-le erinevad bitid, mis teeb 4 maailma 8-st, kusjuures B on endiselt vaba.
  
  $R_{A} = \neg R_{C} ⟹ 8 \to 4$
4. B väidab, et A ja C rollid kattuvad. Nad ei kattu, seega on B lause väär ja B on kaabakas. Ellu jääb kaks maailma: A on rüütel ja C kaabakas või A on kaabakas ja C rüütel.
  
  $R_{B} = [R_{A} = R_{C}] = 0 ⟹ 4 \to 2$
5. C otsustab asja. Mõlemas ellujäänus räägib täpselt 1 osaleja tõtt, seega on väide vähemalt 2 meist väär ning C enda bitt peab olema 0. Maailm, kus C on rüütel, väidab midagi, mida tema enda roll keelab, ning langeb välja. Järele jääb üks maailm.
  
  $Σ R = 1 < 2 ⟹ S_{C} = 0 ⟹ R_{C} = 0$
6. Mine tagasi ja küsi, miks A ja B eemaldasid kumbki täpselt poole. Kumbki lause ei maini oma kõnelejat, seega ülejäänud 2 biti iga väärtustuse korral on kõneleja bitil täpselt 1 väärtus, mis rahuldab võrrandi. Teiste inimeste kohta käiv lause jätab alati alles 2^n-1 maailma — mitte kunagi rohkem ega vähem, mida ta ka ei väidaks.
  
  $R_{X} = S_{X} (R_{- X}) ⟹ 2^{n - 1} = 2^{2} = 4$
7. C lause ei ole seda tüüpi: vähemalt 2 meist loendab ka C-d, seega asub kõneleja bitt mõlemal pool võrrandit ja poolitamisargument variseb kokku. Rakendatuna eraldiseisvalt kõigile 8 maailmale jätab C võrrand alles 6 — see eemaldab 2 maailma seal, kus A ja B võrrandid eemaldavad kumbki 4.
  
  $# {R : R_{C} = S_{C} (R)} = 6 \neq = 4$
Vastus

A on rüütel, B ja C on kaabakad — 1 maailm 8-st, millega paneel avaneb. Ainulaadsus on pigem aritmeetiline vältimatus kui õnn: 3 kõnelejat, kes igaüks räägivad vaid teistest inimestest, poolitavad välja 3 korda, ning kui kärped on sõltumatud, on 2³ poolitatuna 3 korda täpselt 1. Sellepärast räägivad sellise kujuga mõistatustes kõik kõigi teiste kohta keelt. C on erand ja see maksab kätte: võrrand, mis loendab oma kõnelejat, jätab 4 asemel alles 6 maailma 8-st, seega eemaldab see veerandi laualt seal, kus teised eemaldavad poole. Selle arvu saab välja arvutada mis tahes kandidaatlause jaoks enne, kui tead ühtegi rolli, mis teeb sellest vihje ausa mõõdupuu — mitte see, kui kaval see kõlab, vaid kui palju laualt see eemaldab.

$2^{n} \cdot (\frac{1}{2})^{n} = 1$
Neli osalejat Libahundi teemas elus maailmu loendamas 6 sammu
Sama labor, libahundi teema, 4 osalejat. Täpselt 1 4-st on libahunt ning libahunt on ainus, kes valetab. Loenda elusad maailmad enne, kui keegi räägib, ning võrdle seda 3 inimesega rüütlivooruga.
1. Rollid on endiselt bitid — külaelanik 1, libahunt 0 — ning 4 vaba bitti annaks 16 vektorit. See on arv, mida teema peab ületama.
  
  $2^{4} = 16$
2. Teema on kitsendus, mitte dekoratsioon: täpselt 1 bitt on 0. Selle valimine, milline bitt see on, tähendab 1 osaleja valimist 4-st, seega vastab tingimustele vaid 4 vektorit 16-st. Maailmade ruudustik loetleb need, kusjuures üksik W liigub iga reaga ühe koha võrra edasi.
  
  $(1 4) = 4$
3. Ruumi kärpimine 4 korda on väärt 2 bitti ning need anti sulle kätte enne, kui öeldi ainustki sõna.
  
  $lo g_{2} \frac{16}{4} = 2$
4. Nüüd oluline võrdlus. Rüütlivoor 3 osalejaga avaneb 8 maailmaga; selles voorus on üks kahtlusalune rohkem ja see avaneb 4 maailmaga. Rohkem inimesi, väiksem otsinguruum — aprioorne teave ületab biti, mille lisanduslik osaleja juurde tõi.
  
  $2^{3} = 8 > 4$
5. Üks valetaja tähendab ühtlasi täpselt 1 valet. Kõik 4 osalejat räägivad ja ainult libahundi lause on väär, seega on ekraanil olevast 4 lausest 3 tõesed — miski, mida tead juba enne neist ühegi lugemist.
  
  $# {X : R_{X} = 0} = 1 ⟹ # {X : S_{X} (R) = 0} = 1$
6. Mis teeb lauskontrolli siin tõeliselt odavaks: 4 maailma korrutatuna 4 kõneleja võrrandiga annab 16 kooskõlalisuse kontrolli, ja need võiks teha paberil. Samad 4 inimest rüütlite ja kaabakate reeglite kohaselt tähendaks 16 maailma korrutatuna 4 võrrandiga, mis teeb kokku 64.
  
  $4 \times 4 = 16 2^{4} \times 4 = 64$
Vastus

4 4-st, mitte 16 16-st — teema kustutas 75% laualt enne esimest lauset. Suurenda seda ja need kaks mängu ei ole enam sama mäng. n osalejaga on libahundi ruum n ja rüütli ruum 2ⁿ: 10 mängija korral on see 10 maailma 1024 vastu ning aprioorne teave on nüüd väärt 10 − log₂10 = 6,68 bitti. Põhjus on selles, et libahundivoor küsib alati vaid seda, milline neist, seega on selle vastus kõige rohkem log₂ n biti laiune hoolimata sellest, kui palju toole lisad, samal ajal kui rüütlivoor küsib n sõltumatut jah-või-ei küsimust ja kahekordistub iga kord, kui keegi maha istub. Mängija lisamine libahundivooru lisab 1 maailma; ühe lisamine rüütlivooru kahekordistab need.

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

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

42Mathi meeskond · Uuendatud 2026-07-22

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Matemaatika õppetunnid →

Loogiliste vastuolude labor

Näiteülesanded