מפת קרנו

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

מפת קרנו היא שיטה לצמצום ביטויים הנהוגה בבעיות באלגברה בוליאנית.

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

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

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

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

דרך פעולה

כאשר רוצים לצמצם פונקציה עם $N$ משתנים, יוצרים טבלה עם $2^{N}$ תאים (לא נהוג לחרוג מעבר ל-4 או 5 משתנים).
הקצאת ערכים בכותרות עמודות ושורות הטבלה. הערכים נכתבים לפי הסדר בקוד גריי.
מילוי הטבלה בערכים על-פי הפונקציה (או טבלת האמת) הנדרשת.
איתור הקבוצות הגדולות ביותר של תאים צמודים שמכילים ערכים מסוג אחד (לרוב 1-לוגי). כל קבוצה צריכה להיות בצורת מרובע (ובכללה מלבן), ויכולה להכיל ערכי "Don't Care" (מצבים בהם תוצאת הפונקציה אינה חשובה. לרוב מסמנים אותם ב- $\varnothing$ או ב- $X$ ).
רישום של כל קבוצה וקבוצה שאותרה כמכפלה של המכנה המשותף הרחב ביותר של כותרות העמודות והשורות שלה.
הפונקציה המצומצמת היא סכום של המכפלות הללו.

דוגמה

נניח לדוגמה שנתונה פונקציה בוליאנית של 4 משתנים מהצורה:

\ f(A,B,C,D)=A'BCD'+AB'C'D'+AB'C'D+\quad \quad

\quad \quad +AB'CD'+AB'CD+ABC'D'+ABCD'+ABC'D

כאשר הסימן ' מציין את פעולת השלילה.

זהו ביטוי מסורבל, ונרצה לצמצם אותו בצורה היעילה ביותר.

נצייר טבלה שמכילה בטורים את המשתנים $A,B$ ובשורות את המשתנים $C,D$ (אין חשיבות לאיזה צירופים בוחרים - היה אפשר לבחור את $A,D$ לטורים ואת $B,C$ לשורות):

כמו שניתן לראות, בין כל שתי עמודות סמוכות או שורות סמוכות רק משתנה אחד עובר שלילה (כלומר העמודה $A'B$ סמוכה לעמודה $AB$ ולעמודה $A'B'$ אבל אסור שתהיה סמוכה לעמודה $AB'$ ). חשוב לשמור על כלל זה בעת שימוש במפת קרנו.

כעת, מסמנים בכל משבצת את הערך הלוגי המתאים (כאשר בין הערכים בטור והערכים בעמודה מתקיים יחס "וגם" - " $\cdot$ "). מכאן, אם הערך הוא 1 עבור הביטוי $A'BCD'$ , נסמן 1 במשבצת של הצטלבות הטורים $A'B$ ו- $CD'$ .

לאחר סימון ערכי האמת, אנו מנסים להקיף את כל התאים שבהם יש ערך 1, בעזרת מספר מינימלי של קבוצות ("בלונים"), המקיימות את התנאים הבאים:

הקבוצות הן בנות מספר תאים שהוא חזקה של 2 (1, 2, 4, 8, 16 וכו').
מותר להקיף רק תאים שסמוכים זה לזה (לא באלכסון), כאשר סמיכות קיימת גם בקצוות הטבלה - תא בשורה הראשונה סמוך לתא בשורה האחרונה, באותו הטור.

לרוב רצוי לקחת תחילה קבוצות מבודדות שאין דרך אחרת להקיף. מותר לכלול תא אחד במספר קבוצות.

בכל קבוצת תאים שהקפנו, האיברים שמשתנים ביניהם נעלמים. לדוגמה, אם הקפנו את התאים $A'BCD$ ו- $ABCD$ , נקבל שהקבוצה היא אמת עבור $BCD$ .