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

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

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

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

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

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

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

Dartagnan-musketeers
ארבעת המוסקיטרים. איור מתוך מהדורה של 'שלושת המוסקיטרים' שפורסמה ב-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 בחזקת מספר המשתנים:

Picture1

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

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

Picture2

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

Picture3

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

Picture4

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

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

***

אז למה זה טוב?

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

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

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

מודעות פרסומת
  1. אביב קרן
    20/11/2015 ב- 4:26 pm

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

  2. 20/11/2015 ב- 9:03 pm

    הנה שימוש נוסף לאלגברה בולאנית: חישוב הסתברויות כשל למערכות מורכבות. במקרה אני עובד בחברה שמוכרת תוכנה כזאת
    http://www.bqr.com/care/care-dfr-package/care-fta/

  1. No trackbacks yet.

להשאיר תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

%d בלוגרים אהבו את זה: