|
|
עמוד:151
אלגוריתם לשימוש במפת קרנו כדי לקבל את הצורה הפשוטה ביותר של פונקציה בוליאנית , וכדי להימנע מן הבעיה שהוזכרה לעיל , נפעל לפי האלגוריתם המפורט להלן ו . 1 כל תא שלא ניתן לצרפו לקבוצה אחת ( כדי ליצור רכיב ראשוני בן שני תאים , ( יש להקיפו ולהתייחס אליו כאל רכיב ראשוני חיוני . . 2 יש להקיף כל שני תאים המהווים רכיב ראשוני , אם אין רכיבים ראשוניים אחרים המכילים את שני התאים . . 3 יש לזהות כל תא שניתן לצרפו בדרן אחת ויחידה לשלושה תאים אחרים , כך שיתקבל רכיב ראשוני . גם אס חלק מארבעת התאים המעורבים שייכים כבר לרכיבים ראשוניים בני שני תאים , יש להקיף את כל הארבעה . נדגיש פעם נוספת , כי יש להתעלם זמנית מתא שניתן לצרפו לרכיב ראשוני של ארבעה תאים בשתי דרכים ויותר . A יש לחזור על הנאמר לעיל עבור רכיבים ראשוניים של שמונה תאים , שישה-עשר תאים , ובאופן כללי : 2 " תאים . . 5 בגמר תהליך זה , נבדוק אם נותרו עדיין תאים שלא נכללו בשום קבוצה . תאים אלה אפשר לצרף זה לזה , או לרכיבים ראשוניים ( או לחלק מהם ) שכבר סומנו בדרך שרירותית . מובן שנשאף ליצור מתאי שארית אלה מספר קטן ככל האפשר של קבוצות . להלן דוגמה לשימוש באלגוריתם שתואר לעיל . בדוגמה זו מתקבל פתרון יחיד כתוצאה מהשימוש באלגוריתם . I דוגמה 4-7 נתונה הפונקציה ( £ 1 « £ I ( £ I השתמשו במפת קרנו כדי לפשט פונקציה זו . אלגוריתם הוא סדרת הוראות , מוגדרות היטב , לפתרון בעיה .
|
|