הדרך הלא נכונה לתכנן מסיבה מוצלחת – כמה מילים על אלגברה בוליאנית

ד'ארטאניאן עורך מסיבה ומזמין אליה את שלושת חבריו: אתוס, פורתוס ואראמיס. הוא לא בטוח מי משלושתם יוכל להגיע והצלחת המסיבה חשובה לו מאוד. הוא מסביר למשרתו: "מהיכרות ארוכת שנים עם חבריי וניסיוני הרב בעריכת מסיבות אני יודע שכדי שהמסיבה תתרומם מוכרחים להתקיים שני תנאים. האחד, או פורתוס או אראמיס חייבים להיות שם. השני, או אתוס או פורתוס חייבים להיות שם".

משרתו חושב מספר שניות ועונה: "אתה מתכוון בעצם שכדי שהמסיבה תרים את הגג או שפורתוס חייב להיות שם או שגם אתוס וגם אראמיס חייבים להיות שם?"

ד'ארטאניאן מהרהר בעניין ועונה: "כן, ודאי, זה הרי ברור מהגרסה הראשונה של חוק הדיסטריביוטיביות של האלגברה הבוליאנית".

המשרת מגרד בפדחתו, נאנח ועונה: "כן אדוני. שאני אגיש את היין?"

"כן, מוטב שכך". עונה ד'ארטאניאן.

ארבעת המוסקיטרים. איור מתוך מהדורה של 'שלושת המוסקיטרים' שפורסמה ב-1894. המקור: ויקיפדיה.

***

בואו ונדמיין עולם של אמירות שמיוצגות על ידי משתנים. לדוגמה:

האמירה "פורתוס יגיע למסיבה" תסומן על ידי המשתנה A.

אם פורתוס לא יגיע למסיבה האמירה שקרית וערכו של המשתנה A יסומן כ-'שקר', 'false' או פשוט במספר אפס. אם פורתוס אכן יגיע למסיבה האמירה נכונה ולכן ערכו של המשתנה A יסומן כ-'אמת', 'true' או פשוט במספר אחד.

כל משתנה בעולם המוזר הזה יכול לקבל אחד משני ערכים, אפס או אחד, בהתאם להיותו מייצג אמירה שמתקיימת או שאינה מתקיימת.

נסמן את האמירה "אתוס יגיע למסיבה" על ידי המשתנה B, ואת האמירה "אראמיס יגיע למסיבה" במשתנה C.

האם האמירה "המסיבה הצליחה" אמיתית או שקרית? האם נוכל לייצג אותה בעולמנו ולבדוק?

***

ישנן שתי פעולות בלבד שניתן לבצע בין משתנים בעולמנו החדש. האחת פעולת 'וגם' והשניה פעולת 'או'. לדוגמה: "או שפורתוס יגיע למסיבה או שאתוס יגיע למסיבה". האמירה האחרונה למעשה מייצגת פעולת 'או' בין המשתנים A ו-B. כדי שהאמירה המורכבת תהיה נכונה מספיק ש-A יהיה נכון או ש-B יהיה נכון.

בדומה האמירה "גם פורתוס וגם אתוס יגיעו למסיבה" מייצג פעולת 'וגם' בין המשתנים A ו-B. כדי שהאמירה המורכבת תהיה נכונה גם A צריך להיות נכון וגם B צריך להיות נכון.

נסמן את פעולת 'או' בסימן '+' (כמו חיבור במתמטיקה) ואת פעולת 'וגם' בסימן '·' (כמו כפל). כלומר שהרישום A·B משמעו "גם פורתוס וגם אתוס יגיעו למסיבה" והרישום A+B משמעו "או פורתוס או אתוס יגיעו למסיבה".

כעת נוכל לתרגם את אמירתו המורכבת של ד'ארטאניאן לגבי התנאים להצלחת המסיבה: "או פורתוס או אתוס יגיעו למסיבה" וגם "או אראמיס או פורתוס יגיעו למסיבה". נכתוב באמצעות המשתנים: (A+B)·(A+C).

לעומתו טוען המשרת: "או שפורתוס יגיע או שאראמיס וגם אתוס יגיעו". ובמשתנים: (A+(B·C.

האם שתי האמירות מתקיימות או שאינן מתקיימות תחת אותם תנאים? במילים אחרות האם מתקיים:

(A+B)·(A+C)= A+(B·C)

***

לפני שנענה על השאלה, האם הבחנתם שהגדרנו אלגברה מסוג חדש? יש משתנים, ערכים שהם יכולים לקבל והגדרה לפעולות האפשריות ביניהם. שמה של האלגברה היא 'אלגברה בוליאנית' על שמו של ג'ורג' בול, מתמטיקאי, פילוסוף ולוגיקן מהמאה ה-19 שהגה אותה לראשונה בספר שפרסם ב-1854. כמו כן, הוא הופיע בגוגל-דודל לא מזמן. כבוד!

נשים לב שתחת חוקי האלגברה הזאת כל פעולת 'וגם' עם אמירה שקרית תוצאתה אמירה שקרית, כי עבור תוצאת אמת חייבים ששתי האמירות יתקיימו ואחת כבר שקרית. כמו כן, כל פעולת 'או' עם אמירה נכונה תוצאתה אמירה נכונה, כי עבור תוצאת אמת מספיק שאחת תהיה נכונה ואחת כבר נכונה. ובכתב אלגברי:

A·0=0

A+1=1

חישבו לבד מדוע גם ההיגדים הבאים נכונים תמיד:

A·1=A

A+0=A

כעת אנחנו מוכנים לבדוק מדוע החוק שאותו כינה ד'ארטאניאן "חוק הדיסטריביוטיביות הראשון" נכון.

ניצור טבלה של כל התרחישים האפשריים עבור האמירות B, A ו-C. מספר האפשריות הוא 2 בחזקת מספר המשתנים:

תרחיש 1 הוא שאף אחד משלושת החברים לא מגיע. תרחיש 8 הוא שכולם מגיעים וכך הלאה.

כעת נוסיף לטבלה טור חדש עבור B וגם C. נמלא אותה לפי החוקים שלמדנו שאותם נפעיל בין הטורים של B ו-C המסומנים בצהוב.

נוסיף טור נוסף עבור A או (B וגם C). נעקוב אחרי הטורים הצהובים:

נעשה את אותם רצף של פעולות כדי למצוא את הטור עבור (A+B)·(A+C):

קיבלנו תשובות לשתי השאלות שלנו בו זמנית. קודם כל ניתן להבחין בקלות ששני הטורים המייצגים את האמרות של ד'ארטאניאן ומשרתו זהות מבחינה ערכים ולכן ברור שהן זהות מבחינה לוגית.

כמו כן, כעת אנחנו יודעים בדיוק באלו מקרים תצליח המסיבה ובאלו מקרים לא. תרחישים 4 עד 8 מייצגים חמש אפשריות להצלחת המסיבה. ארבע מתוכן הן אלה שבהן פורתוס מגיע למסיבה והחמישית היא זאת שבה למרות שפורתוס לא הגיע, אתוס ואראמיס הגיעו יחדיו.

***

אז למה זה טוב?

למיטב ידיעתי, ואני לא מומחה בנושא, אלגברה בוליאנית שימושית לשני דברים עיקריים: לוגיקה ואלקטרוניקה דיגיטלית.

בלוגיקה אני לא מבין כלום, אבל דעו כי אלקטרוניקה דיגיטלית חוללה מהפך בעולמינו, וכל מעגל שכזה מתחיל מתרגיל באלגברה בוליאנית שהרי אות דיגיטלי הוא או גבוה או נמוך, או אפס או אחד.

אדגים זאת מתישהו ברשימה נפרדת.

העולם דרך עיניהם של מהנדסי חשמל (מטריצות, פרק הסיום) – על ייצוג במרחב המצב

זהו. הגיע רגע האמת.

הרשימה הזאת היא למעשה הסיבה שבגינה התחלתי לכתוב על מטריצות.

הרשימה הבאה, כמו זאת שקדמה לה, עוסקת בטכניקה מתמטית ולכן דוברת מתמטיקה. הפעם התרתי כל רסן בעניין. ראו הוזהרתם!

***

ברשימה הקודמת הצגתי את בעיית האוסילטור ההרמוני, התנודה המחזורית הבסיסית, והראיתי כיצד ניתן לפרק את המשוואה שמתארת אותה, משוואה דיפרנציאלית מסדר שני, לשתי משוואות מסדר ראשון. את שתי המשוואות ניתן לארוז בתוך מטריצה ולתת למחשב לפתור. כלומר נוכל למצוא באמצעות המחשב את המקום ואת המהירות של הגוף בכל רגע.
[הערת שוליים: זאת לא הדרך היחידה, ואולי אפילו לא היעילה ביותר לפתור את הבעיה באמצעות מחשב, אבל זה פחות מעניין אותי כרגע מכיוון שאני אני חותר למקום אחר.]

בעיית האוסילטור ההרמוני יכולה לייצג תנודה של מטוטלת, תנודה של גוף מחובר לקפיץ, תנועה של נדנדה, מעגלי תהודה בחשמל ועוד.

בואו נתעכב לרגע על הנדנדה. ילדה יושבת על כיסא הנדנדה ובכל פעם שהיא מתקרבת לאבא הוא נותן לה דחיפה קלה. הפעולה הזאת של הדחיפה אינה מתוארת במשוואות שעסקתי בהן פעם קודמת. כל הכוחות שפעלו על הגוף היו כוחות שקשורים למשתנים הבסיסיים של המערכת (מקום ומהירות הגוף). דחיפותיו של האב מהוות מקור כוח חיצוני שמופעל על הגוף ואינו תלוי במערכת עצמה.

עבור בעיות אלה (בעגה: אוסילטור מאולץ) נקבל משוואה אחרת שיש בה איבר מסוג חדש שנקרא לו איבר מקור.

הנה המשוואה המקורית:

L הוא המרחק של הגוף מנקודת שיווי משקל, L עם שתי נקודות מעליו מסמל נגזרת שניה בזמן של המרחק מנקודת שיווי משקל.

והנה המשוואה המעודכנת:

F הכוח החיצוני המופעל על הגוף.

הפתרון, אם כך, יהיה תלוי גם בתכונות הבעיה המקורית (בעגה: הבעיה ההומוגנית) וגם בתכונות הכוח החיצוני.

אחד הדברים החדשים והמעניינים שמופיעים במערכות כאלה הוא תופעת התהודה. הפתרון של המערכת תלוי בתדירות הכוח המנדנד. אם האב מתאם את הרגעים שבהם הוא דוחף את הילדה לתדירות מאוד מסוימת, הגובה שתגיע אליו הילדה יגדל מאוד אפילו ללא הגברת כוח הדחיפה. כלומר, ישנם תדרי נדנוד שבהם המערכת, במובן מסוים, יוצאת מכלל שליטה. בתדרים נמוכים וגבוהים מתדרי התהודה פעולת הדחיפה משפיעה באופן מתון או אפילו מפריעה לתנועה. לעומת זאת, בתדר התהודה המערכת משתוללת והילדה עפה מהנדנדה, לא עלינו. ניתן לחשב את תדרי התהודה על ידי פתרון מתמטי של המערכת או לגלות אותם על ידי מדידה.

אבל,

ברשימה זאת אני לא רוצה לעסוק בפתרון המערכת הספציפית הזאת אלא דווקא בדרכים מיוחדות לייצג משפחה שלמה של בעיות דומות. מה שמקשר בין הבעיות הוא שהן מתארות מערכת שלתוכה מוזן אות כניסה (למשל הכוח החיצוני שמופעל על הגוף) ונמדד אות יציאה (למשל מיקום הגוף בכל רגע ביחס לנקודת שיווי משקל).

ככה מהנדסי חשמל רואים את העולם.

***

בואו ונניח שניתן לתאר את המערכת על ידי שתי המשוואות הבאות:

x הוא וקטור משתני המצב, u המקור, כלומר הכוח החיצוני, x עם נקודה למעלה מסמל נגזרת אחת בזמן של וקטור משתני המצב. y מסמל את אות היציאה של המערכת, למשל באוסילטור את המרחק מנקודת שיווי המשקל בכל רגע. A,B,C,D הם קבועים שאינם תלויים בזמן (בעגה מערכת כזאת נקראת LTI, כלומר linear-time-invariant).

המשוואה העליונה מתארת את הפיזיקה של משתני המצב שבחרנו. למשל במקרה של אוסילטור הרמוני הראיתי בסוף הרשימה הקודמת שמשתני העזר שנבחרו היו המקום והמהירות של הגוף. זה לא מקרי שמשתני המצב הם נגזרות אחד של השני.

המשוואה התחתונה מגדירה את אות היציאה שהחלטנו למדוד.

כעת בואו ונראה כיצד ניתן לתרגם למשל את בעיית האוסילטור לתוך הפורמולציה הזאת.

נרשום שוב את המשוואה כולל איבר המקור:

סימנתי את איבר המקור F באות u מטעמי נוחות והרגל.

משתני העזר שלי הם:

לכן שתי המשוואות שמייצגות אותן הן:

נסגור את שתי המשוואות בכתב מטריצי:

נניח שאות היציאה שמעניין אותנו הוא מרחק הגוף מנקודת שיווי משקל בכל רגע. אם כך אנחנו מעוניינים רק באיבר הראשון בווקטור המצב. נתרגם לכתב מטריצי:

ולכן המערכת מתוארת על ידי:

כעת כל המידע על אופייה של המערכת גלום במקדמים שלה A,B,C,D שהם וקטורים ומטריצות. אני אנסה להסביר מדוע דרך דוגמה.

***

התמרת פורייה היא אופרציה מתמטית שמפרקת פונקציה לרכיבי התדר הבסיסיים שמרכיבים אותה. לדוגמה, צג האקולייזר במערכת הסטריאו שלכם מראה בכל רגע מה העוצמה של כל צליל שצריך לחבר כדי לקבל את המוזיקה שאתם שומעים. אם יש למשל הרבה בס אז עוצמת התדרים הנמוכים תהיה גבוהה. הסברתי בעבר על הנושא ברשימה על מוזיקה מרובעת.

אחת התכונות המוזרות של התמרת פורייה היא שאם מפעילים אותה על משתנה תחת נגזרת מקבלים את המשתנה ללא נגזרת כפול קבוע הקשור לתדר. כלומר ניתן להפעיל את ההתמרה על משוואה דיפרנציאלית, להפוך אותה לאלגברית, לפתור אותה בקלות, ואז לנסות להמיר חזרה לתחום הזמן (שזה לא ממש קל). כל עוד המשתנים תחת ההתמרה אנחנו נקרא להם הייצוג בתחום התדר, כי הפונקציות הופכות הרי לפירוק התדרים ולכן הן פונקציות של התדר ולא של הזמן.

בטיפול במערכות אלה נהוג להשתמש בהתמרה שנקראת 'התמרת לפלאס' במקום בהתמרת פורייה. קצרה היריעה מלעמוד על ההבדלים ביניהן, אבל לענייננו זה לא ישנה דבר.

נפעיל את התמרת לפלאס על הייצוג הכללי של מערכת המצב:

נרשום את כל המשתנים באות גדולה כדי לסמן שהם כעת פונקציות של התדר ולא של הזמן. הקבוע s הוא הקבוע שיצא מהנגזרת והוא תלוי בתדר.

קיבלנו שתי משוואות אלגבריות, כאשר אנחנו זוכרים שהמקדמים A,B,C,D הם מטריצות. נבודד את X מתוך המשוואה הראשונה באמצעות אלגברה של מטריצות ונציב אותו במשוואה השניה:

I היא מטריצת היחידה.

קיבלנו ביטוי בתחום התדר עבור מוצא המערכת Y בהינתן המקור U. אם נחלק ביניהם נקבל ביטוי שנקרא פונקצית התמסורת (transfer function) של המערכת, כלומר מה יוצא ביחס למה שנכנס, הכל כתלות בתדר הנדנוד.

בואו ונתרגם את התוצאה למקרה של אוסילטור הרמוני פשוט ללא חיכוך על ידי הצבת המקדמים הרלוונטיים שקיבלנו קודם:

ניתן לראות שקיבלנו במכנה פולינום עבור המשתנה s. נזכר שזה בדיוק הפולינום האופייני של המערכת ששורשיו מכתיבים את התנהגות המערכת כפי שראינו ברשימה הקודמת. אלה נקראים הקטבים של המערכת והם קובעים את התנהגותה. קיבלנו אותם מתוך המטריצה A (בעגה: מצאנו את הערכים העצמיים שלה). למעשה מרגע שניסחנו את הייצוג, יכולנו לגלות חלק חשוב מהתנהגות המערכת מתוך ניתוח המטריצה עצמה, ללא פתרון מלא שלה. למשל, אם אחד מקטבי המערכת ממשי וחיובי אז הפתרון בזמן יהיה תלוי בפונקציה אקספוננציאלית מתפוצצת ולכן המערכת אינה יציבה בזמן.

ישנן עוד תכונות רבות וחשובות שניתן לראות ישירות מתוך הייצוג, ללא פתרון מלא בזמן. ברגע שיש לנו את המקדמים A,B,C,D המערכת הפיזיקלית חשופה בפנינו. חשופה גם לאפיון אך גם לשליטה. למשל את בעיית היציבות שהזכרתי ניתן לתקן על ידי חיבור משוב במערכת, כלומר חיבור אות היציאה לתוך הכניסה, שישנה את הקטבים של המערכת. כמה הגבר יש לקבוע עבור אות המשוב כדי לייצב את המערכת? קל לקבוע בחישוב מתוך הייצוג.

***

ייצוג בעיות פיזיקליות כמערכת של כניסות ויציאות הוא כלי חזק של תכנון ושליטה בידי המהנדס. הוא נקרא 'ייצוג במרחב המצב' (state space representation) והוא חלק חשוב מתוך תורת הבקרה. כל החישוב האמיתי נעשה על גבי המחשב, לתוכו אנחנו מזינים את המטריצות שמייצגות את המערכת, ומבצעים את האפיון והתכנון של המערכת באמצעות כלים ממוחשבים מתוחכמים שנכתבו למטרות אלה.

זהו.

מטריצה אובר-אנד-אאוט.