הצגת המקור של הדף "מפת קרנו"

{{פירוש נוסף|נוכחי=[[אלגברה בוליאנית (מבנה אלגברי)|אלגברה בוליאנית]]|אחר=[[תרמודינמיקה]]|ראו=[[מנוע קרנו]]}}
[[קובץ:Karnaugh map KV 4mal4 15.svg|שמאל|ממוזער|250px|מפת קרנו לפונקציה <math>\bar{A}+B\bar{C}D</math>]]
'''מפת קרנו''' היא שיטה לצמצום [[ביטוי (מתמטיקה)|ביטויים]] הנהוגה בבעיות ב[[אלגברה בוליאנית]].

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

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

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

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

== דרך פעולה ==
[[קובץ:K-map 2x2 empty.svg|שמאל|ממוזער|150px|מפת קרנו ל-2 משתנים]]
[[קובץ:K-map 2x4 empty.svg|שמאל|ממוזער|150px|מפת קרנו ל-3 משתנים]]
[[קובץ:K-map 4x4 empty.svg|שמאל|ממוזער|150px|מפת קרנו ל-4 משתנים]]
# כאשר רוצים לצמצם פונקציה עם <math>N</math> משתנים, יוצרים טבלה עם <math>2^N</math> תאים (לא נהוג לחרוג מעבר ל-4 או 5 משתנים).
# הקצאת ערכים בכותרות עמודות ושורות הטבלה. הערכים נכתבים לפי הסדר ב[[קוד גריי]].
# מילוי הטבלה בערכים על-פי הפונקציה (או [[טבלת אמת|טבלת האמת]]) הנדרשת.
# איתור הקבוצות הגדולות ביותר של תאים צמודים שמכילים ערכים מסוג אחד (לרוב 1-לוגי). כל קבוצה צריכה להיות בצורת [[מרובע]] (ובכללה מלבן), ויכולה להכיל ערכי "Don't Care" (מצבים בהם תוצאת הפונקציה אינה חשובה. לרוב מסמנים אותם ב-<math>\varnothing</math> או ב-<math>X</math>).
# רישום של כל קבוצה וקבוצה שאותרה כמכפלה של המכנה המשותף הרחב ביותר של כותרות העמודות והשורות שלה.
# הפונקציה המצומצמת היא סכום של המכפלות הללו.

== דוגמה ==
נניח לדוגמה שנתונה פונקציה בוליאנית של 4 משתנים מהצורה:
:::: <math> \ f(A,B, C, D)= A' B C D' + A B' C' D' + A B' C' D + \quad \quad </math>
: <math>\quad \quad + A B' C D' +A B' C D + A B C' D' + A B C D' + A B C' D </math>

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

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

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

[[קובץ:K-map 6,8,9,10,11,12,13,14 anti-race.svg|middle|ממוזער|250px|מפת קרנו]]

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

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

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

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

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

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

== ראו גם ==
* [[לוגיקה]]
* [[אלגברה בוליאנית]]
* [[לוגיקה בוליאנית]]
* [[אלקטרוניקה ספרתית]]

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}

[[קטגוריה:לוגיקה בוליאנית]]
[[קטגוריה:לוגיקה מתמטית]]
[[קטגוריה:מעגלים ספרתיים]]