אלגברה בוליאנית ומפות קרנוף
הוצג| English | משמעות |
|---|---|
| Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | אלגברת בול |
| De Morgan's laws/də ˈmɔːɡənz lɔːz/ | חוקי דה מורגן |
| Karnaugh map/ˈkɑːnɔː mæp/ | מפת קארנו |
| truth table/truːθ ˈteɪbl/ | טבלת אמת |
| absorption/əbˈsɔːpʃn/ | חוק הספיגה |
| Gray code/ɡreɪ kəʊd/ | קוד גריי |
עבודת המאסטר שבנתה את העולם הדיגיטלי
- בשנת 1937, סטודנט בן 21 בשם קלווד שאנון הבחין שהממסרים הטלפוניים שהיה חוקר פעלו באותו אופן כמו אלגברה שג'ורג בול המציא שמונים שנה לפני כן לעיבוד טיעונים על אמת ושקר.
- אם מתג הוא משתנה בוליאני, then המעגל הוא ביטוי, והפשטת הביטוי מסירה שערים מהמעגל. מעט שערים פירוט זול יותר, מהיר יותר וחוסך חשמל.
- עבודת המאסטר שלו נקראה כעבודה החשובה במאה. כל מה שבעמוד הזה הוא רעיון אחד זה שנעשה ככלי.
- שיעור זה עוסק באלגברה בוליאנית, חוקי דה מורגן ובמפת קארנו העושה אותה עבודה באמצעות חיפוי עיניים.
הסימון והחוקים
+מסמל OR,·מסמל AND ולעיתים קרובות נשאר מובן, ומקווקו מעל מסמל NOT. טבלת אמת מתארת את אותו דבר באופן מלא.- זהות: $A + 0 = A$ ו-$A \cdot 1 = A$. אי-נוכחות: $A + 1 = 1$ ו-$A \cdot 0 = 0$.
- אידמפוטנטי: $A + A = A$. הפוך: $A + \overline{A} = 1$ ו-$A \cdot \overline{A} = 0$.
- ספיגה: $A + A\cdot B = A$, משום אם $A$ אמת, הביטוי כולו א unabhängig מ-$B$.
התאם כל חוק בוליאני לכך שהוא אומר.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
חוקים אלו מאפשרים לך לפשט ביטויים בוליאניים אלגברית לפני בניית המעגל.
על פי חוק הספיגה, הביטוי A + A·B מצטמצם ל-____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
אם A אמת, כל הביטוי אמת בשל כל ערך של B, ואם A שגויה, שני האיברים הם שגויים. B אינו יכול להשפיע על התוצאה.
חוקי דה מורגן
- חוקי דה מורגן הם שני החוקים שהבחינה מבקשת ממך להשתמש בהם בשם:
- הטופס במילים: להפוך את הכל, להחליף AND ו-OR, להפוך כל טרמינד.
- הם חשובים מעשייתית משום שהם מאפשרים לכתיבת כל ביטוי באמצעות שערי NAND בלבד או שערי NOR בלבד, ותצוגה המיוצרת משער חוזר היא זולה יותר לייצור.
ביטויים שניים, טבלת אמת אחת
אלגברה בולית
A·B, A+B, Ā …
אלגברה בוליאנית היא פשוט שערים אלו כתובים כביטויים — השוו את טבלאות האמת.
על פי חוק דה מורגן, $\overline{A \cdot B}$ שווה ל:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
להפוך את השליל של כל הביטוי, להחליף AND→OR, ולהפוך את שלילת כל ארגומנט: $\overline{A \cdot B} = \overline{A} + \overline{B}$.
הייתוח חוק דה מורגן לביטוי כולל אילו צעדים? סמן את כולם הנכונים.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
להפוך את שלילת כל הביטוי, להחליף את האופרטור, ולהפוך את שלילת כל חלק. הסדר אינו רלוונטי, שכן AND ו-OR הם קומטטיביים.
דוגמה פותרת: פישוט, וספירת השערים
- פשט את $Z = A\cdot B + A\cdot\overline{B}$ ואמור מה הוא חוסך.
- הוצא גורם משותף $A$: $Z = A\cdot(B + \overline{B})$. לפי חוק ההפוך $B + \overline{B} = 1$, כך $Z = A \cdot 1 = A$.
- המקורי דורש שערי AND שניים, NOT אחד ו-OR אחד: ארבעה שערים. הביטוי המופשט דורש שום שער, רק את הקלט $A$.
- תמיד סיים עם מה הפישוט נותן: פחות שערים, ולכן מעגל זול, מהיר יותר ובוחל פחות אנרגיה.
פשטו $A\cdot B + A\cdot\overline{B}$.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
לפעיל A בחוץ: $A(B + \overline{B}) = A \cdot 1 = A$.
הביטוי A·B + A·NOT B דורש שני שערי AND, אחד NOT ואחד OR. כמה שערים דורש צורתו המצומצמת?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
הוא מצטמצם ל-A פשוט, ולכן הפלט זהה לקלט ואין צורך בשום שער כלל. ארבעה שערים נחסכו.
מפת קארנו
- מפת קארנו מפשטת ביטוי על ידי הרכבת 1s סמוכים הנלקחים מטבלת האמת.
- השורות והעמודות מסומנים בסדר קוד גריי,
00, 01, 11, 10, כדי ש-תאים סמוכים ישתנו בדיוק בטרמינד אחד. זוהי כל התעלול: זה הופך את האלגברה לנראית כסמיכות. - הצב 1 בכל תא בו היציאה היא 1, ולאחר מכן מצא קבוצות מלבניות של 1s שהצדדים שלהם הם חזקות של 2: 1, 2, 4, 8. קבוצות יכולות להסתובב סביב הקצה.
ככל שהמלבן גדול יותר, כך האיבר פשוט יותר
מפת קארנו מסתכמת ביטוי בוליאני באמצעות:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
אתה מקבץ 1s סמוכים (בסדר קוד גרי) למלבנות בעלות גודל כוח של 2; כל קבוצה הופכת למונה מצומצם.
מדוע השורות והעמודות במפת קארנו מסומנים 00, 01, 11, 10 ולא 00, 01, 10, 11?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
סדר קוד גריי הופך שכנות אלגברית לשכנות פיזית. בסדר הספירה הכללי, כלל הקיבוצים פשוט לא יעבוד.
קריאת קבוצה
- בתוך קבוצה, משתנה שנשאר קבוע נשמר באיבר; משתנה שמתחלף נעלם.
- לכן קבוצה של 2 מסירה משתנה אחד, קבוצה של 4 מסירה שניים, וקבוצה של 8 מסירה שלושה. ככל שהקבוצה גדולה יותר, כך האיבר פשוט יותר.
- כיסו כל ה-1ים בשימוש ב-כמה שפחות ובכמה שגדולות הקבוצות האפשריות, ולאחר מכן אגדו את איברי הקבוצות יחד באמצעות OR. קבוצות עשויות לחלוץ, וחילוץ הוא לעיתים קרובות מה שמאפשר ליצור קבוצה גדולה יותר.
במפת קרנוף, קבוצה גדולה יותר של 1s סמוכים מבטלת משתנים רבים יותר, ומניבה ביטוי פשוט יותר (קבוצה בגודל 2 מבטלת משתנה אחד, קבוצה בגודל 4 מבטלת שניים).
Difficulty 1/5 · 100 coins + a small bonus on first completion today
קיבוצים של 1s סמוכים לריבועים בעל כוחות של 2 בסדר קוד גריי; ככל שקבוצה גדולה יותר, כך הביטוי הפשוט יותר שנוצר ממנה.
סדרו את השלבים לפישוט באמצעות מפת קרנוף.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
קוד גריי, אחדים, קבוצות גדולות ביותר, הסרת מה משתנה, OR או המונחים. השתמש בקבוצות כמינימום ובגודל מקסימום שיכסו כל ⟨1⟩.
דוגמה מפורטת: קריאת מפת משתנים זוגית
- מפת קרנוף עבור $A$ ו$B$ מכילה 1ים בתאים $\overline{A}B$ ו$AB$. פשטו.
- שני ה-1ים סמוכים זה לזה: הם חולקים את עמודת $B = 1$, ולכן מתקבצים כמלבן בגודל 2.
- בתוך קבוצה זו, $B$ נשאר 1 לאורך כל הדרך, בעוד ש$A$ משתנה מ-0 ל-1. המשתנה שהתחלף נעלם.
- לכן הביטוי כולו הוא פשוט $Z = B$. השוו זאת לסכום מכפלות שאינו מפושט, $\overline{A}B + AB$, הדורש NOT, שני ANDs ואחד OR.
איזו שיטה לבחור
- אלגברה בוליאנית היא מדויקת ועובדת לכל מספר של משתנים, אך עליכם לזהות איזו חוק חל על המקרה.
- מפת קרנוף היא מכנית וקשה להיכשל בה עבור משתנים שניים עד ארבע, שהוא המספר הנפוץ בשאלות המבחן, והיא מראה לכם ישירות את הקיבוצים הגדולים ביותר.
- שתי השיטות נותנות את אותו תשובה. היתרון במפת קרנוף הוא שהפשט הופך להיות הסתכלות, ולא חיפוש אחר חוק.
סימונים נופלים מהיד
- דה מורגן הוא הפוך את הכל, החלף את האופרטור, הפוך כל חלק. שינוי רק האופרטור הוא התשובה הכסופה הקלאסית.
- שורות מפת קרנוף חייבים להיות בסדר קוד גריי,
00, 01, 11, 10. בסדר ספירה בינארי ההיכרות (הסמיכות) שגויה והקיבוצים נכשלים. - גדלי הקבוצות הן חזקות של 2 ועשויות להתחבר לקצוות. קבוצה בגודל 3 אינה קבוצה תקינה.
- ציינו לפי מה פשטנו: כדי להפחית את מספר השערים, ולכן לחסוך כסף, להגדיל מהירות ולהפחית צריכת חשמל.
הבנתך מושלמת
- אלגברה בוליאנית כותבת מחדש ביטוי למספר פחות של איברים, ולכן המעגל דורש פחות שערים.
- דה מורגן: $\overline{A + B} = \overline{A} \cdot \overline{B}$ ו$\overline{A \cdot B} = \overline{A} + \overline{B}$; ספיגה: $A + AB = A$; $A\cdot B + A\cdot\overline{B} = A$
- טבלת קרנוף מקבצת 1ים סמוכים מטבלת האמת, כאשר השורות והעמודות מסודרות לפי קוד גריי כך שכנים שונים בפרמטר אחד
- משתנה המתחלף בתוך קבוצה נעלם, ולכן קבוצות גדולות יותר מובילות לביטויים פשוטים: כיסו כל ה-1ים בכמות הקטנה ביותר של קבוצות גדולות ככל האפשר