מפת קרנו

מפת קרנו לפונקציה ${\bar {A}}+B{\bar {C}}D$

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

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

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

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

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

דרך פעולה

מפת קרנו ל-2 משתנים

מפת קרנו ל-3 משתנים

מפת קרנו ל-4 משתנים

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

דוגמה

נניח לדוגמה שנתונה פונקציה בוליאנית של 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). חשוב לשמור על כלל זה בעת שימוש במפת קרנו.

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

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

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

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

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

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

ראו גם

• לוגיקה
• אלגברה בוליאנית
• לוגיקה בוליאנית
• אלקטרוניקה ספרתית

קישורים חיצוניים

מדיה וקבצים בנושא מפת קרנו בוויקישיתוף

• הסבר על שימושי מפת קרנו באתר "עד כדי קבוע"