צמצום ביטויים בעזרת מפת קרנו

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

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

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

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

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

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

מיפוי מטבלת אמת למפת קרנו

מפת קרנו היא טבלה המכילה מספר שורות ועמודות. סך כל התאים שיש בטבלה שווה למספר השורות בטבלת האמת ממנה אנו ממפים – למשל, אם יש לי 3 משתנים לוגיים, אני אבנה טבלת אמת של 8 שורות, וגם מפת קרנו תכיל 8 תאים (ראה ציור בהמשך). באותו אופן לטבלת אמת של 4 משתנים יש 16 שורות, וגם למפת קרנו המתאימה יהיו 16 תאים.

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

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

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

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

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

אנחנו מתעלמים מהשורות בעמודת הפסוק בהן יש ערך אפס (0).

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

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

סימון קבוצות:

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

כללים לסימון קבוצות:

1. קבוצת תאים המכילה את הערך אחד (1) יכולה לכלול כמות של תאים מתוך הגדלים הבאים בלבד: 1,2,4,8,16,32, וכו (חזקות של 2)

2. צריך לזהות ולהקיף קבוצות תאים כמה שיותר גדולות. ככל שהקבוצות גדולות יותר מתקבל ביטוי מצומצם יותר

3. ניתן לכלול תא מסויים ביותר מאשר קבוצה יחידה בכדי להשיג קבוצה גדולה יותר.

4. קבוצת תאים מסומנת צריכה להיות חסומה במלבן.

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

6. למפת קרנו תכונת גליליות/כדוריות – ניתן לכופף את המפה לצורת גליל באופן שהגבול העליון של המפה נוגע בגבול התחתון של המפה או בהתאמה הגבולות מימין ומשמאל. במצב בו הגבולות נוגעים ניתן לסמן קבוצות שחוצות את גבול ובכך להשיג קבוצות גדולות יותר.
מקרה מיוחד הוא מצב שבו 4 הפינות של המפה הופכים לקבוצה אחת.

7. יש סימון מיוחד שנקרא DON'T CARE ??? שמציין מצבים של מערכת הבקרה שלא יכולים להתרחש במציאות אבל כן מופיעים כאחד המצבים בטבלת האמת. תא בו מופיע הסימן המיוחד מתייחסים אליו לפעמים כמו 1 ולפעמים כמו אפס (0). אם הסימן תורם ליצירת קבוצה גדולה יותר אזי מייחסים אליו כמו 1, אם אינו תורם כלום מתייחסים אליו כמו אפס (0).

תהליך הסימון מסתיים כאשר לא נותרו תאים במפה שאינם משוייכים לשום קבוצה.

הוצאת ביטוי לוגי:

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

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

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

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

באופן מעשי התהליך הוא פשוט מאוד. ראה דוגמא להלן:

TBD

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

צמצום ביטויים לוגיים בעזרת חוקים

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

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

חוקי הצמצום מתחלקים למספר קבוצות, והתהליך של הצמצום מתחיל בביטוי המקורי.

  • אם הביטוי המקורי אינו מכיל קטעים עם סוגריים, אז עלינו לנסות למצוא גורם משותף רחב ביותר בין קטעים של הביטוי. על ידי הוצאת הגורם המשותף אנחנו רוצים לקבל בתוך הסוגריים ביטויים פשוטים מתוך רשימת החוקים ועל ידי שימוש בחוק אנחנו נחליף את הביטוי בסוגריים לביטוי פשוט עוד יותר ובכך נקטין את כמות הפעולות הלוגיות בביטוי המקורי. תהליך זה חוזר על עצמו מספר פעמים עד שלא ניתן יותר מצוא גורם משותף שיאפשר לי צמצום בעזרת חוק.
  • אם הביטוי המקורי מכיל סוגריים, אז אנחנו ננסה לפתוח את הסוגריים ולראות מה הביטוי המורחב כולל ובשלב זה להפעיל חוקי צמצום.
  • ישנם 3 חוקים (דה-מורגן) שמתייחסים באופן ספציפי לשערי: NAND, NOR ו- XOR. בביטויים במכילים פעולות אלו, נשתמש בחוקים אלו כדי להפוך את הביטויים כך שיכילו רק פעולות AND, OR ו- NOT ובאופן זה יותר קל להפעיל את חוקי הצמצום.

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

מימוש בעזרת מפסקים חשמליים

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

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

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

אם למפסק אחד נקרא A ולשני נקרא B, והם יקבלו ערך 1 כאשר הם מופעלים (סוגרים מעגל חשמלי), וכן נקרא לנורה F והיא תקבל ערך 1 כאשר היא דולקת, אזי הקשר בין A,B ו- F הוא קשר AND – רק ש-A וגם B יהיו 1 אז F תדלק.

שער OR:

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

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

אם למפסק בענף העליון נקרא A ולמפסק בענף התחתון נקרא B, והם יקבלו ערך 1 כאשר הם מופעלים (סוגרים מעגל חשמלי), וכן נקרא לנורה F והיא תקבל ערך 1 כאשר היא דולקת, אזי הקשר בין A,B ו- F הוא קשר OR – מספיק ש-A או B יהיו 1 אז F תדלק.

שער NOT:

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

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

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

מפסק רגיל סגור הוא האופן בו ממשים פעולה לוגית NOT במעגלים חשמליים.

סימוני מפסקים:

יש מספר סימונים מקובלים למפסקים. בתמונה הבאה ניתן לראות 3 סוגי סימונים מקובלים למפסקים מסוג רגיל פתוח ורגיל סגור.

שרטוט דיאגרמת שערים לוגיים

דוגמא:

נתון הביטוי הבא, ודרוש לבנות את שרטוט השערים הלוגיים של F:

לפי הכותרות של עמודות טבלת האמת ממשים כל פעולה לוגית בעזרת שער – ראה שלבים (לפתוח רמקולים יש קריינות)

אם נפעיל את המפסקים A,B,C,D לפי ערכי טבלת האמת נראה את הנורה דולקת לפי ערכי עמודה F

///

בניית טבלת אמת לפונקציה שאינה קנונית

הגדרה:

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

כמות הצירופים (השורות) בטבלה שווה ל – n2 ,  כאשר n הוא מספר המשתנים הלוגיים במשפט. למשל: עבור 3 משתנים לוגיים יש 8 צירופים.

תהליך בנייה של טבלת אמת:

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

2. מחשבים כמה שורות יהיו בטבלה לפי כמות המשתנים בבעיה ולפי ההגדרה למעלה.

3. מזהים וסופרים כמה פעולות לוגיות יש בביטוי (לכל פעולה לוגית תהיה עמודה בטבלה).

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

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

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

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

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

דוגמא:

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

נבדוק תחילה אילו פעולות לוגיות כלולות בביטוי (ראה 4 פעולות מסומנות באדום):

נבדוק אילו מהפעולות ניתנות לביצוע ישירות על המשתנים A,B,C,D (ראה סימון כחול)

A AND B

NOT C

נחשב את שתי העמודות הללו בטבלה.

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

נחשב את העמודה החדשה מתוך עמודה D והעמודה המחושבת NOT C.

הגענו אל הפעולה הלוגית האחרונה:

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

נוסחאון בית סיפרי לבחינת מתכונת ובגרות

להורדת דף נוסחאות לחץ כאן

בניית טבלת אמת מתוך פונקציה קנונית נתונה

בניית טבלת אמת עבור פונקציה קנונית נתונה

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

שלב 1:

עוברים על כל המשתנים בפונקציה הנתונה. מתחת למשתנה רגיל רושמים 1, ומתחת למשתנה היפוך (NOT – עם "גג") רושמים 0 (אפס)

שלב 2:

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

שלב 3:

לכל מכפלת משתנים יש עכשיו רצף של ספרות 1 ו-0 המייצגים שורה בטבלת האמת. מחפשים את השורה בטבלת האמת שבנינו באופן שבו המספר שרשמנו מתחת למשתנה בפונקציה יהיה הערך של המשתנה בטבלה. למשל: אם יש לנו 4 משתנים A,B,C,D ורשמנו מתחתם את הספרות 1001, עלינו למצוא בטבלת האמת שורה בה A=1 B=0 C=0 D=1. בשורה הזו נרשום 1 בעמודת הפסוק.

עוברים כך על כל המכפלות של המשתנים בפונקציה הקנונית ומסמנים ערכי 1 בעמודת הפסוק בטבלה.

שלב 4:

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

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

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