שינויים

באלגברה בוליאנית מסמנים <math>\mathrm T1</math> כפסוק אמת ו־<math>\mathrm F0</math> כפסוק שקר. באופן דומה, אם תושב <math>A</math> הוא אביר אז נסמנו כ־<math>\mathrm T1</math> ואם נוכל – <math>\mathrm F0</math>. אם הוא מרגל נסמן <math>\mathrm Sp</math>. אם תושב <math>B</math> יכול להיות מרגל אז נסמן את נכונות הטענה ה־<math>i</math> במספר שלו כ־<math>b_i</math>. כלומר, אם הטענה נכונה אז <math>b_i\Leftrightarrow\mathrm TLeftrightarrow1</math> ואחרת <math>b_i\Leftrightarrow\mathrm FLeftrightarrow0</math>. מכך נובע שאם הטענה ה־<math>i</math> של <math>B</math> היא <math>P</math> אז <math>b_i\Leftrightarrow P</math>, ומסיבות שיובנו בהמשך נעדיף את הסימון השקול <math>b_i\leftrightarrow P\Leftrightarrow\mathrm TLeftrightarrow1</math>. מובן שאם <math>B</math> אביר או נוכל אז <math>\forall i:\ b_i\Leftrightarrow B</math>, ולכן אם אנו כבר יודעים שתושב <math>B</math> אינו מרגל אז נסמן את טענותיו פשוט כ־<math>B</math>.

(1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&\mathrm T1\\(2)&B\leftrightarrow A\leftrightarrow\mathrm Fleftrightarrow0&\Leftrightarrow&\mathrm T1\\(3)&C\leftrightarrow C\leftrightarrow D&\Leftrightarrow&\mathrm T1\\(4)&A\leftrightarrow C&\Leftrightarrow&\mathrm F0\end{array}</math>}}

(1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&\mathrm T1\\(2)&A\leftrightarrow B&\Leftrightarrow&\mathrm F0\\(3)&D&\Leftrightarrow&\mathrm T1\\(4)&A\leftrightarrow C&\Leftrightarrow&\mathrm F0\end{array}</math>}}עתה נציב את (2) ב־(1) ונקבל <math>\mathrm F0\leftrightarrow C\Leftrightarrow\mathrm TLeftrightarrow1</math>, כלומר <math>C\Leftrightarrow\mathrm FLeftrightarrow0</math>. נציב זאת ב־(4) ונקבל <math>A\Leftrightarrow\mathrm TLeftrightarrow1</math>, ואם נציב את התוצאה ב־(2) נקבל <math>B\Leftrightarrow\mathrm FLeftrightarrow0</math>. לסיכום, <math>A,D</math> אבירים ו־<math>B,C</math> נוכלים.

{| class="wikitable" style="float:left; clear:left; direction:ltr;"|+ טבלה 1|-! <math>x</math> !! <math>y</math> !! <math>\varphi(x+y)</math> !! <math>\varphi(x)\leftrightarrow\varphi(y)</math>|-| 0 || 0 || T || T|-| 0 || 1 || F || F|-| 1 || 0 || F || F|-| 1 || 1 || T || T|}{| class="wikitable" style="float:left; clear:left; direction:ltr;"|+ טבלה 2|-! <math>x</math> !! <math>y</math> !! <math>\varphi(x\cdot y)</math> !! <math>\varphi(x)\or\varphi(y)</math>|-| 0 || 0 || T || T|-| 0 || 1 || T || T|-| 1 || 0 || T || T|-| 1 || 1 || F || F|}אלו חידות שניתן לפתור כמערכת משוואות לינאריות. ניצור איזומורפיזם מהשדה <math>(\mathbb Z_2,+,\cdot)</math> ל־<math>(\{\mathrm T1,\mathrm F0\},\leftrightarrow,\or)</math> ע״י <math>\varphineg:x\mapsto\begin{cases}\mathrm T1,&x=0\\\mathrm F0,&x=1\end{cases}</math>. נראה שזהו אכן איזומורפיזם:

* <math>\varphineg(x+y)\Leftrightarrow\varphineg(x\nleftrightarrow y)\Leftrightarrow x\leftrightarrowy\varphi(Leftrightarrow\neg x\leftrightarrow\neg y)</math>: טבלה 1.* <math>\varphineg(x\cdot y)\Leftrightarrow\varphineg(x\and y)\Leftrightarrow\neg x\or\varphi(neg y)</math>: טבלה 2.

מכך נובע ש־<math>(\{1,0\mathrm T},\mathrm Fleftrightarrow,\}or)</math> שדה. נגדיר סכום <math>\sum_{i=1}^m P_i</math> (כאשר <math>\forall i:\ P_i\in\{\mathrm T1,\mathrm F0\}</math>) בתור <math>P_1\leftrightarrow\dots\leftrightarrow P_m</math> ומכפלה <math>\prod_{i=1}^m P_i</math> בתור <math>P_1\or\dots\or P_m</math>. כפל מטריצות מוגדר בהתאם.

כעת, אם התושבים הם <math>X_1,\dots,X_n</math> אז נגדיר <math>\mathbf x:=\begin{pmatrix}X_1\\\vdots\\X_n\end{pmatrix}</math>. אם כל <math>P_i</math> מייצג נעלם <math>X_j</math> או קבוע <math>\mathrm T1,\mathrm F0</math> אז נוכל להציג כל שרשור <math>P_1\leftrightarrow\dots\leftrightarrow P_n\Leftrightarrow P_{n+1}</math> בתור סכום של נעלמים שונים השווה לקבוע. (לדוגמה, <math>B\leftrightarrow A\leftrightarrow\mathrm F\Leftrightarrowleftrightarrow0\mathrm TLeftrightarrow1</math> מפתרון דוגמה 1 שקול ל־<math>A\leftrightarrow B\Leftrightarrow\mathrm FLeftrightarrow0</math>, ששקול ל־<math>\sum_{X_i\in\{A,B\}}X_i\Leftrightarrow\mathrm FLeftrightarrow0</math>). לכן נוכל להגדיר מטריצת מקדמים <math>\mathbf A</math> ווקטור מקדמים חופשיים <math>\mathbf b</math> כך ש־<math>\mathbf{Ax}\Leftrightarrow\mathbf b</math>. למשל, את דוגמה 1 ניתן להציג באופן הבא:{{left|<math>\underbrace\begin{pmatrix}\mathrm F0&\mathrm F0&\mathrm F0&1\mathrm T\\\mathrm F0&\mathrm F0&\mathrm T1&1\mathrm T\\\mathrm T1&\mathrm T1&\mathrm T1&0\mathrm F\\\mathrm F0&\mathrm T1&\mathrm F0&\mathrm T1\end{pmatrix}_\mathbf A\underbrace\begin{pmatrix}A\\B\\C\\D\end{pmatrix}_\mathbf x\Leftrightarrow\underbrace\begin{pmatrix}1\mathrm T\0\\mathrm F\\\mathrm T\1\\mathrm F0\end{pmatrix}_\mathbf b</math>}}

הצגה זו מאפשרת לנו למצוא מה הסוג של כל תושב ע״י פתרון מערכת משוואות לינאריות. יתרה מזאת, לפי משפט רושה–קפלי (Rouché–Capelli) יש פתרון ל־<math>\mathbf{Ax}=\mathbf b</math> אם״ם <math>\mathbf b\in\operatorname{span}\left\{\operatorname{Col}_i(\mathbf A)\right\}_{i=1}^n</math> כאשר <math>\operatorname{Col}_i(\mathbf A)</math> העמודה ה־<math>i</math> של <math>\mathbf A</math>, ואם כן אז מרחב הפתרונות הוא ממימד <math>n-\operatorname{rank}(\mathbf A)</math>. מכאן נובע שאנו יכולים לבדוק האם קיים פתרון לחידה, ואם כן אז כמה פתרונות ישלחשב את מספר הפתרונות בתור <math>2^{n-\operatorname{rank}(\mathbf A)}</math>. מובן שבד״כ יש רק פתרון אחד, כלומר <math>\mathbf A</math> הפיכה.