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

דוגמא לפתרון בעזרת טבלת אמת ומפת קרנו

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

A – חיישן שמוצאו "1" לוגי כאשר אדם יושב במושב הנהג.

B - חיישן שמוצאו "1" לוגי כאשר חגורת הנהג נחגרה

C - חיישן שמוצאו "1" לוגי כאשר אדם יושב במושב הנוסע

D - חיישן שמוצאו "1" לוגי כאשר חגורת הנוסע נחגרה

Y – מצב מערכת ההתרעה (מופעלת / כבויה)

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

השלימו את עמודת התוצאה (עמודה Y). שימו לב, אין לסמן בטבלה מצבי לא אכפת (don't care).
מצא את הפונקציה הקנונית המתארת את המערכת.

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

פתרון:

טבלת אמת המייצגת את התנאים הלוגיים בבבעיה נראית כך:

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

מפת קרנו תראה כך:

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

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

ספריה מקיפה של ניסים אוחנה

מהי טבלת אמת?

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

עבור משתנה 1 יהיו 2 אפשרויות. עבור 2 משתנים 4 אפשרויות .עבור 3 משתנים 8 אפשרויות ועבור 4 משתנים 16 אפשרויות.

לדוגמא, טבלת אמת של שני משתנים נראית כך:

אם נחבר את התוצאה המתקבלת מכל שורה (עבורה הפונקציה מקבלת ערך 1) נקבל את הפונקציה הבאה:

מהי מפת קרנו?

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

מפת קרנו המתארת את הפונקציה הנ"ל תיבנה באופן הבא:

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

בתוך כל תא נרשום את תוצאות המכפלה:

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

ייצוג הפונקציה באמצעות ערכים: עבור A,B נרשום 1 ועבור , נרשום 0 כלומר נקבל:

העתקת הפונקציה נתונה למפת קרנו:

בכל תא המתאים למכפלה שבביטוי – נרשום את הערך "1". ביתר התאים נרשום "0". ייצוג הפונקציה באמצעות ערכים : 00 + 01 + 11

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

ובהמשך נסמן את התאים 1 ו 3 כתאים סמוכים:

בסוף תהליך הצמצום, במקום הביטוי: f(A,B)=A×B+A×B+A×B נקבל ביטוי מצוצמם:

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

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

מפה ל 4 משתנים:

שלבים לצימצום מפת קרנו

שבץ בתוך המפה את המצבים בהם הפונקציה 1.
הקף את כל הבתים המסומנים לקבוצות לפי התנאים הבאים:

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

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

Page updated

Google Sites

Report abuse