פרק 4

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

כיתה י׳ · 6 שעות לימוד

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

בסוף הפרק הזה נדע:

נכתוב את המינטרם של כל שורה בטבלת האמת, ונדע את מספרו m_i.
נכתוב פונקציה בצורה הקנונית — סכום מכפלות — מתוך טבלת האמת.
נכתוב פונקציה בייצוג המספרי Σ ונעבור בינו לבין טבלת האמת והביטוי.
נסרטט מפת קרנו לשני משתנים, לשלושה ולארבעה משתנים, ונמספר את משבצותיה.
נזהה את המשבצות הסמוכות, ובהן המשבצות שבקצוות המפה ובארבע פינותיה.
נבנה קבוצות של 1, 2, 4 או 8 משבצות ונקרא את המכפלה שכל קבוצה נותנת.
נמפה במפה פונקציה שאינה נתונה בצורתה הקנונית.
נפשט פונקציה הנתונה כסכום מכפלות ונגיע לביטוי המינימלי.
ננצל את צירופי הברירה כדי לקבל ביטוי קצר יותר.

צורות קנוניות של פונקציות בוליאניות: סכום של מכפלות, ייצוג מספרי של פונקציות קנוניות (Canonical Forms)

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

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

סכום מכפלות: הוא ביטוי הבנוי ממכפלות שפעולת OR מקשרת ביניהן, כמו A·B + C. הביטוי A·(B + C) אינו סכום מכפלות, כי יש בו סכום בתוך סוגריים; אחרי פתיחת הסוגריים נקבל A·B + A·C וזה כבר סכום מכפלות.

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

המינטרם

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

לכל שורה בטבלת האמת יש מינטרם משלה. כך כותבים אותו: משתנה שערכו בשורה 1 נכתוב כמות שהוא, ומשתנה שערכו 0 נכתוב מהופך. נסמן את המינטרם ב-m_i, כאשר i הוא מספר השורה: המספר העשרוני שסיביות המבואות כותבות, ו-A היא הסיבית המשמעותית ביותר.

שמונת המינטרמים של פונקציה בת שלושה משתנים
i	A	B	C	m_i	minterm
0	0	0	0	m₀	A·B·C
1	0	0	1	m₁	A·B·C
2	0	1	0	m₂	A·B·C
3	0	1	1	m₃	A·B·C
4	1	0	0	m₄	A·B·C
5	1	0	1	m₅	A·B·C
6	1	1	0	m₆	A·B·C
7	1	1	1	m₇	A·B·C

ארבעת המינטרמים של פונקציה בת שני משתנים
i	A	B	m_i	minterm
0	0	0	m₀	A·B
1	0	1	m₁	A·B
2	1	0	m₂	A·B
3	1	1	m₃	A·B

מדוע המינטרם שווה 1 בשורה אחת בלבד? ניקח את m₅ = A·B·C. פעולת AND נותנת 1 רק אם כל מבואותיה 1, כלומר A = 1 וגם B = 1 וגם C = 1, וזה קורה רק בשורה 101, שהיא שורה מספר 5.

מספר המינטרמים

N = 2ⁿ

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

תרגול מהיר — נכתוב את מספר המינטרם

1A·B·C

2A·B·C

3A·B·C

4A·B·C·D

5A·B·C·D

6A·B·C·D

7A·B·C·D

8A·B·C·D

9A·B·C·D

תשובות: 1 m₀ 2 m₂ 3 m₅ 4 m₃ 5 m₆ 6 m₉ 7 m₁₀ 8 m₁₂ 9 m₁₅

תרגול מהיר — נכתוב את המינטרם במשתנים A, B, C, D

1m₁

2m₄

3m₇

4m₈

5m₁₁

6m₁₄

תשובות: 1 A·B·C·D 2 A·B·C·D 3 A·B·C·D 4 A·B·C·D 5 A·B·C·D 6 A·B·C·D

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

צורה קנונית: היא כתיבת הפונקציה כסכום מינטרמים: מחברים בפעולת OR את המינטרמים של כל השורות שבהן F = 1. לכל פונקציה יש צורה קנונית אחת בלבד.

נחפש בטבלת האמת את השורות שבהן F = 1. השורות שבהן F = 0 אינן מעניינות אותנו.
נכתוב לכל שורה כזאת את המינטרם שלה: 1 ← המשתנה כמות שהוא, 0 ← המשתנה מהופך.
נחבר את המינטרמים בפעולת OR.

דוגמה 4.1

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

פתרון:

i	A	B	C	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	1
5	1	0	1	1
6	1	1	0	0
7	1	1	1	0

הפונקציה שווה 1 בארבע שורות: 1, 3, 4, 5. נכתוב את המינטרם של כל שורה:

m₁ = A·B·C

m₃ = A·B·C

m₄ = A·B·C

m₅ = A·B·C

נחבר את ארבעת המינטרמים:

F = m₁ + m₃ + m₄ + m₅

F = A·B·C + A·B·C + A·B·C + A·B·C

הערה: מדוע זה נכון? כל מינטרם "מדליק" שורה אחת. פעולת OR נותנת 1 אם לפחות אחד מן המינטרמים שווה 1, ולכן הסכום שווה 1 בדיוק בשורות שבחרנו, ו-0 בשאר — בדיוק כמו בטבלה.

שאלה 4.1: נכתוב בצורה הקנונית את הפונקציה F(A,B,C) השווה 1 בשורות 000, 010, 110, 111 ושווה 0 בשאר השורות.

הייצוג המספרי

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

ייצוג מספרי של פונקציה קנונית

F(A,B,C) = Σ(1,3,4,5)

סימן	משמעות	יחידת מידה
F(A,B,C)	שם הפונקציה ומשתניה לפי הסדר: המשתנה הראשון הוא הסיבית המשמעותית ביותר	—
Σ	סכום (פעולת OR) של המינטרמים	—
1, 3, 4, 5	מספרי השורות שבהן F = 1	—

שימו לב: סדר המשתנים בתוך הסוגריים חשוב. ב-F(A,B,C) המינטרם m₁ הוא A·B·C, אבל ב-F(C,B,A) המינטרם m₁ הוא C·B·A. בספר הזה A היא תמיד הסיבית המשמעותית ביותר.

דוגמה 4.2

נתונה הפונקציה F(A,B,C,D) = Σ(2,7,8,13). נכתוב את הביטוי הקנוני שלה.

פתרון:

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

2 = 0010₂ → m₂ = A·B·C·D

7 = 0111₂ → m₇ = A·B·C·D

8 = 1000₂ → m₈ = A·B·C·D

13 = 1101₂ → m₁₃ = A·B·C·D

F = A·B·C·D + A·B·C·D + A·B·C·D + A·B·C·D

דוגמה 4.3

נכתוב בייצוג מספרי את הפונקציה F = A·B·C + A·B·C + A·B·C.

פתרון:

נכתוב מתחת לכל מינטרם את הסיביות שעושות אותו 1: משתנה רגיל ← 1, משתנה מהופך ← 0.

A·B·C → 010₂ = 2

A·B·C → 100₂ = 4

A·B·C → 111₂ = 7

F(A,B,C) = Σ(2,4,7)

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

10110 1001

21001 0110

30011 0011

41100 0010

50001 1101

61000 0111

תשובות: 1 Σ(1,2,4,7) 2 Σ(0,3,5,6) 3 Σ(2,3,6,7) 4 Σ(0,1,6) 5 Σ(3,4,5,7) 6 Σ(0,5,6,7)

תרגול מהיר — נכתוב את הביטוי הקנוני של הפונקציה F(A,B,C)

1Σ(0,3)

2Σ(1,6,7)

3Σ(2,4,5)

4Σ(0,5,7)

תשובות: 1 A·B·C + A·B·C 2 A·B·C + A·B·C + A·B·C 3 A·B·C + A·B·C + A·B·C 4 A·B·C + A·B·C + A·B·C

תרגול מהיר — נכתוב בייצוג מספרי

1A·B·C + A·B·C

2A·B·C + A·B·C + A·B·C

3A·B·C + A·B·C + A·B·C

4A·B·C + A·B·C + A·B·C + A·B·C

תשובות: 1 Σ(1,2) 2 Σ(0,4,6) 3 Σ(3,5,7) 4 Σ(1,2,4,7)

הצורה הקנונית אינה הצורה הקצרה ביותר

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

דוגמה 4.4

נפשט באופן אלגברי את הפונקציה F(A,B,C) = Σ(4,5,7).

פתרון:

נכתוב את הצורה הקנונית:

F = A·B·C + A·B·C + A·B·C

בשני האיברים הראשונים נוציא את הגורם המשותף A·B, ונשתמש בכלל C + C = 1:

F = A·B·(C + C) + A·B·C

F = A·B + A·B·C

נוציא את הגורם המשותף A:

F = A·(B + B·C)

נשתמש בכלל הצמצום B + B·C = B + C:

F = A·(B + C)

נפתח את הסוגריים (חוק הפילוג):

F = A·B + A·C

לפני הפישוט: F = A·B·C + A·B·C + A·B·C

אחרי הפישוט: F = A·B + A·C

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

פישוט פונקציות בוליאניות באמצעות מפות קרנו (Karnaugh Maps)

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

כל משבצת מייצגת מינטרם אחד. במפה של n משתנים יש 2ⁿ משבצות: 4 משבצות לשני משתנים, 8 לשלושה משתנים ו-16 לארבעה.

א. מפות קרנו ל-2, 3 ו-4 משתנים:

בניית המפה ומספור המשבצות

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

שני משתנים: A לשורות, B לעמודות

שלושה משתנים: A לשורות, B C לעמודות

ארבעה משתנים: A B לשורות, C D לעמודות

שימו לב: העמודות (וגם השורות במפה של ארבעה משתנים) אינן מסודרות לפי הספירה הבינארית, אלא בסדר 00, 01, 11, 10. הסדר הזה נקרא קוד גריי: בין כל שני צירופים עוקבים משתנה סיבית אחת בלבד. לכן העמודה השלישית היא 11 והרביעית 10: בשורה הראשונה המספרים הם 0, 1, 3, 2, ובמפה של ארבעה משתנים השורה השלישית היא 12 – 15 והרביעית 8 – 11. מי ששוכח זאת ממלא את המפה בצורה שגויה.

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

תרגול מהיר — מפה של ארבעה משתנים. נתונות השורה A B והעמודה C D. מהו מספר המשבצת?

1A B = 11, C D = 01

2A B = 01, C D = 11

3A B = 10, C D = 10

4A B = 00, C D = 10

5A B = 11, C D = 11

6A B = 10, C D = 00

7A B = 01, C D = 10

8A B = 11, C D = 10

9A B = 10, C D = 01

תשובות: 1 m₁₃ 2 m₇ 3 m₁₀ 4 m₂ 5 m₁₅ 6 m₈ 7 m₆ 8 m₁₄ 9 m₉

נמלא את המפה

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

דוגמה 4.5

נמפה במפת קרנו את הפונקציה מן הדוגמה הראשונה בפרק, F(A,B,C) = Σ(1,3,4,5).

פתרון:

הפונקציה בת שלושה משתנים ← מפה בת שתי שורות (A) וארבע עמודות (B C). נכתוב 1 במשבצות 1, 3, 4, 5 ו-0 בשאר.

i	A	B	C	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	1	1
4	1	0	0	1
5	1	0	1	1
6	1	1	0	0
7	1	1	1	0

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

נבדוק משבצת אחת: שורה 4 בטבלה היא A B C = 100, כלומר השורה A = 1 והעמודה B C = 00 במפה.

במפה של ארבעה משתנים פועלים באותה דרך. למשל בפונקציה F(A,B,C,D) = Σ(0,2,5,7,8,10,13,15): המספר 13 = 1101₂ נמצא בשורה A B = 11 ובעמודה C D = 01.

הפונקציה Σ(0,2,5,7,8,10,13,15) במפה

שאלה 4.2: נעתיק את שתי המפות למחברת ונמלא אותן:
(א) F(A,B,C) = Σ(0,3,5,6)
(ב) F(A,B,C,D) = Σ(1,4,6,9,11,14). באיזו עמודה של המפה נמצאת כל משבצת שיש בה 1?

(א)

(ב)

משבצות סמוכות

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

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

שכנות המשבצת m₅: m₁, m₄, m₇, m₁₃

שכנות משבצת הפינה m₀: m₁, m₂, m₄, m₈

שכנות משבצת הקצה m₁₄: m₆, m₁₀, m₁₂, m₁₅

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

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

1m₀ ו-m₁

2m₁ ו-m₂

3m₀ ו-m₈

4m₅ ו-m₇

5m₃ ו-m₂

6m₅ ו-m₁₀

7m₄ ו-m₆

8m₁₂ ו-m₈

9m₇ ו-m₈

10m₂ ו-m₁₀

11m₁₃ ו-m₁₄

12m₉ ו-m₁₁

תשובות: 1 כן, D משתנה 2 לא 3 כן, A משתנה 4 כן, C משתנה 5 כן, D משתנה 6 לא 7 כן, C משתנה 8 כן, B משתנה 9 לא 10 כן, A משתנה 11 לא 12 כן, C משתנה

מדוע מחפשים משבצות סמוכות? — הקבוצה

ניקח שתי משבצות סמוכות שבכל אחת מהן 1, למשל m₆ ו-m₇ במפה של שלושה משתנים. סכום שני המינטרמים הוא:

A·B·C + A·B·C = A·B·(C + C)

A·B·(C + C) = A·B

המשתנה שמשתנה בין שתי המשבצות (C) נעלם, ונשאר מה שמשותף לשתיהן (A·B). זה מה שהמפה עושה: היא מסדרת את המשבצות כך שרואים בעין היכן אפשר להפעיל את הכלל X + X = 1.

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

קריאת המכפלה מתוך הקבוצה

L = n − p

סימן	משמעות	יחידת מידה
n	מספר משתני הפונקציה	—
2^p	מספר המשבצות בקבוצה: 1, 2, 4, 8 ...	—
L	מספר הליטרלים במכפלה שהקבוצה נותנת	—

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

שתי משבצות: A = 0, B = 0, C משתנה ← A·B

שתי משבצות: A משתנה, B = 1, C = 1 ← B·C

שתי משבצות בשני הקצוות: A = 1, B משתנה, C = 0 ← A·C

ארבע משבצות: A ו-B משתנים, C = 1 ← C

שורה שלמה: A = 0 ← A

שתי העמודות החיצוניות: C = 0 ← C

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

ריבוע של ארבע משבצות ← B·D

ארבע הפינות ← B·D

שמונה משבצות ← B

למעלה ולמטה ← B·D

עזר לקריאה: נזכור היכן שווה כל משתנה 1 במפה. A = 1 בשתי השורות התחתונות, B = 1 בשתי השורות האמצעיות, C = 1 בשתי העמודות הימניות ו-D = 1 בשתי העמודות האמצעיות.

A = 1

B = 1

C = 1

D = 1

תרגול מהיר — המשבצות הבאות יוצרות קבוצה אחת. נכתוב את המכפלה שהיא נותנת (סעיפים 1–4: פונקציה של A, B, C; סעיפים 5–12: פונקציה של A, B, C, D)

1m₂ , m₃

2m₁ , m₅

3m₄ , m₅ , m₆ , m₇

4m₀ , m₄

5m₁₂ , m₁₃

6m₄ , m₆

7m₀ , m₁ , m₄ , m₅

8m₃ , m₁₁

9m₁₀ , m₁₁ , m₁₄ , m₁₅

10m₀ , m₄ , m₈ , m₁₂

11m₄ , m₆ , m₁₂ , m₁₄

12m₀ , m₁ , m₂ , m₃ , m₄ , m₅ , m₆ , m₇

תשובות: 1 A·B 2 B·C 3 A 4 B·C 5 A·B·C 6 A·B·D 7 A·C 8 B·C·D 9 A·C 10 C·D 11 B·D 12 A

שאלה 4.3: בכל מפה יש קבוצה אחת. נכתוב את המכפלה שכל קבוצה נותנת.

(א)

(ב)

(ג)

(ד)

כללי בניית הקבוצות

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

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

דוגמאות פתורות

דוגמה 4.6

נפשט את הפונקציה F(A,B) = Σ(1,2,3).

פתרון:

נסרטט מפה לשני משתנים ונכתוב 1 במשבצות 1, 2, 3.

שתי קבוצות, כל אחת בת שתי משבצות

שלוש משבצות אינן יוצרות קבוצה אחת. נבנה שתי קבוצות של שתי משבצות, והמשבצת m₃ משותפת לשתיהן.

הקבוצה האנכית (m₁, m₃): A משתנה, B = 1 ← B. הקבוצה האופקית (m₂, m₃): A = 1, B משתנה ← A.

קיבלנו את הפונקציה OR, וזה הגיוני: הפונקציה שווה 0 רק כאשר A = 0 וגם B = 0.

F = B + A

דוגמה 4.7

נפשט את הפונקציה F(A,B,C) = Σ(1,3,4,5) (הפונקציה מן הדוגמה הראשונה בפרק).

פתרון:

מפת הפונקציה עם הקבוצות

בשורה העליונה: m₁ ו-m₃ סמוכות. A = 0, C = 1, ו-B משתנה ← A·C.

בשורה התחתונה: m₄ ו-m₅ סמוכות. A = 1, B = 0, ו-C משתנה ← A·B.

כל המשבצות שבהן 1 מכוסות. אפשר גם לקבץ את m₁ עם m₅, אבל הקבוצה הזאת מיותרת: שתי משבצותיה כבר מכוסות.

בצורה הקנונית יש ארבעה מינטרמים ו-12 ליטרלים; בביטוי המפושט יש שתי מכפלות ו-4 ליטרלים בלבד.

F = A·B + A·C

דוגמה 4.8

נפשט את הפונקציה F(A,B,C) = Σ(0,2,4,5,6).

פתרון:

קבוצה של ארבע משבצות דרך שני הקצוות, וקבוצה של שתי משבצות

העמודה השמאלית (B C = 00) והעמודה הימנית (B C = 10) סמוכות, ויש בהן ארבע משבצות שכולן 1: m₀, m₂, m₄, m₆. בקבוצה הזאת A משתנה וגם B משתנה, ונשאר C = 0 ← C.

נשארה המשבצת m₅. לא נשאיר אותה לבדה: נקבץ אותה עם שכנתה m₄ (אף ש-m₄ כבר מכוסה). A = 1, B = 0 ← A·B.

F = C + A·B

דוגמה 4.9

נפשט את הפונקציה F(A,B,C,D) = Σ(0,2,5,7,8,10,13,15).

פתרון:

ארבע הפינות הן קבוצה אחת

במרכז המפה יש ריבוע של ארבע משבצות: m₅, m₇, m₁₃, m₁₅. בו B = 1 וגם D = 1, ו-A ו-C משתנים ← B·D.

ארבע הפינות m₀, m₂, m₈, m₁₀ סמוכות ויוצרות קבוצה אחת של ארבע משבצות: B = 0 וגם D = 0 ← B·D.

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

F = B·D + B·D

דוגמה 4.10

נפשט את הפונקציה F(A,B,C,D) = Σ(0,1,2,3,4,5,6,7,10,14).

פתרון:

קבוצה של שמונה משבצות וקבוצה של ארבע

שתי השורות העליונות כולן 1: קבוצה של שמונה משבצות. המשתנה היחיד הקבוע בה הוא A = 0 ← A.

המשבצות m₁₀ ו-m₁₄ נמצאות בעמודה הימנית. נגדיל את הקבוצה לעמודה כולה (m₂, m₆, m₁₄, m₁₀): C = 1, D = 0 ← C·D. אילו לקחנו רק את שתי המשבצות היינו מקבלים A·C·D — ליטרל מיותר.

F = C·D + A

דוגמה 4.11

נפשט את הפונקציה F(A,B,C,D) = Σ(0,1,4,5,7,8,9,15).

פתרון:

שלוש קבוצות; המשבצות m₀ ו-m₁ משותפות לשתי קבוצות

נתחיל במשבצת שיש לה אפשרות אחת: השכנה היחידה של m₁₅ שבה 1 היא m₇ ← קבוצה של שתי משבצות: B·C·D.

המשבצות m₈ ו-m₉ נכנסות לקבוצה של ארבע עם m₀ ו-m₁ (השורה העליונה והשורה התחתונה סמוכות): B = 0, C = 0 ← B·C.

המשבצות m₄ ו-m₅ נכנסות לריבוע עם m₀ ו-m₁: A = 0, C = 0 ← A·C.

כל המשבצות מכוסות בשלוש קבוצות.

F = B·C·D + B·C + A·C

תרגול מהיר — נסרטט מפה ונפשט

1F(A,B) = Σ(0,1)

2F(A,B) = Σ(0,1,2)

3F(A,B,C) = Σ(0,1,2,3)

4F(A,B,C) = Σ(2,3,6,7)

5F(A,B,C) = Σ(0,4)

6F(A,B,C) = Σ(2,3,4,5)

7F(A,B,C) = Σ(1,4,5,6,7)

8F(A,B,C) = Σ(0,2,4,6,7)

9F(A,B,C) = Σ(0,1,5,7)

תשובות: 1 F = A 2 F = B + A 3 F = A 4 F = B 5 F = B·C 6 F = A·B + A·B 7 F = B·C + A 8 F = C + A·B 9 F = A·C + A·B

תרגול מהיר — נסרטט מפה לארבעה משתנים ונפשט

1F(A,B,C,D) = Σ(0,1,2,3,12,13,14,15)

2F(A,B,C,D) = Σ(0,4,5,8,12,13)

3F(A,B,C,D) = Σ(2,3,6,7,10,11,14,15)

4F(A,B,C,D) = Σ(0,2,8,10,15)

5F(A,B,C,D) = Σ(4,5,6,7,12,14)

6F(A,B,C,D) = Σ(0,1,4,5,8,9,10,11)

7F(A,B,C,D) = Σ(1,3,5,7,9,11,13,15)

8F(A,B,C,D) = Σ(3,7,11,12,13,15)

תשובות: 1 F = A·B + A·B 2 F = C·D + B·C 3 F = C 4 F = B·D + A·B·C·D 5 F = B·D + A·B 6 F = A·B + A·C 7 F = D 8 F = C·D + A·B·C

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

⚠

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

https://fahed-lab.com/digital/digital_systems_lab?tab=kmap

פתיחת המעבדה בדף נפרד ↗ fahed-lab.com/digital/digital_systems_lab?tab=kmap

ב. מיפוי פונקציה שאיננה נתונה בצורתה הקנונית:

לעיתים קרובות הפונקציה נתונה כסכום מכפלות, למשל F = A·B + C, שבו לא בכל מכפלה מופיעים כל המשתנים. זו אינה צורה קנונית. אין צורך להפוך אותה באופן אלגברי למינטרמים: נקרא את כלל הקבוצות בכיוון ההפוך. כשם שקבוצה של משבצות נותנת מכפלה קצרה, כך מכפלה קצרה ממלאת קבוצה שלמה של משבצות.

מספר המשבצות שמכפלה ממלאת

N = 2^{n − L}

סימן	משמעות	יחידת מידה
N	מספר המשבצות שהמכפלה ממלאת	—
n	מספר משתני הפונקציה	—
L	מספר הליטרלים במכפלה	—

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

דוגמה 4.12

נמפה במפת קרנו את הפונקציה F = A·B + C ונכתוב אותה בייצוג מספרי.

פתרון:

המכפלה A·B: יש בה שני ליטרלים מתוך שלושה ← היא ממלאת 2³⁻² = 2 משבצות. A = 1 היא השורה התחתונה, ו-B = 0 הן העמודות 00 ו-01 ← המשבצות m₄ ו-m₅.

המכפלה C: יש בה ליטרל אחד ← היא ממלאת 2³⁻¹ = 4 משבצות. C = 1 בעמודות 01 ו-11, בשתי השורות ← המשבצות m₁, m₃, m₅, m₇.

כל מכפלה מילאה קבוצה: האדום A·B, הכחול C

המשבצת m₅ הופיעה בשתי המכפלות — נכתוב בה 1 פעם אחת. במשבצות שנשארו (m₀, m₂, m₆) נכתוב 0.

F(A,B,C) = Σ(1,3,4,5,7)

הערה: דרך אלגברית לבדיקה: נכפול כל מכפלה ב-(X + X) לכל משתנה X החסר בה. למשל במכפלה A·B חסר C: A·B = A·B·(C + C) = A·B·C + A·B·C, כלומר m₅ + m₄ — אותן שתי משבצות שמצאנו במפה.

דוגמה 4.13

נמפה במפת קרנו את הפונקציה F = A·C + A·B·D + B·C·D ונכתוב אותה בייצוג מספרי.

פתרון:

המכפלה A·C: שני ליטרלים מתוך ארבעה ← 4 משבצות. A = 1: שתי השורות התחתונות; C = 0: שתי העמודות השמאליות ← m₁₂, m₁₃, m₈, m₉.

המכפלה A·B·D: שלושה ליטרלים ← שתי משבצות. השורה A B = 01, והעמודות שבהן D = 1 ← m₅, m₇.

המכפלה B·C·D: שלושה ליטרלים ← שתי משבצות. העמודה C D = 10, ושתי השורות שבהן B = 1 ← m₆, m₁₄.

האדום A·C, הכחול A·B·D, הירוק B·C·D

F(A,B,C,D) = Σ(5,6,7,8,9,12,13,14)

דוגמה 4.14

נמפה במפת קרנו את הפונקציה F = A + B·C + A·(B + C).

פתרון:

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

כלל דה-מורגן: A + B = A·B. חוק הפילוג: A·(B + C) = A·B + A·C.

F = A·B·C + A·B + A·C

עכשיו נמלא את המפה: A·B·C ← m₁; A·B ← m₆, m₇; A·C ← m₄, m₆.

הפונקציה אחרי פתיחת הסוגריים

F(A,B,C) = Σ(1,4,6,7)

תרגול מהיר — מפה של ארבעה משתנים A, B, C, D. אילו משבצות ממלאת המכפלה?

1A·D

2B·C

3A·C·D

4A·B·C

6B·D

7A·B·C·D

9B·C

תשובות: 1 9 , 11 , 13 , 15 2 2 , 3 , 10 , 11 3 0 , 4 4 12 , 13 5 0 , 1 , 4 , 5 , 8 , 9 , 12 , 13 6 4 , 6 , 12 , 14 7 11 8 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 9 0 , 1 , 8 , 9

תרגול מהיר — נמפה את הפונקציה במפה ונכתוב אותה בייצוג מספרי

1F = A + B·C

2F = A·B + A·C

3F = B + A·B·C

4F = A·C + A·B + B·C

5F = A·B + C·D

6F = A·C + A·B·C·D

7F = B·D + A·B·C

8F = B·D + A·B·D + A·C·D

תשובות: 1 Σ(3,4,5,6,7) 2 Σ(2,3,4,6) 3 Σ(0,1,4,5,7) 4 Σ(1,2,3,4,5,6) 5 Σ(3,7,11,12,13,14,15) 6 Σ(0,1,4,5,15) 7 Σ(5,7,8,9,13,15) 8 Σ(0,2,5,7,8,10,11,15)

שאלה 4.4: נכתוב את הפונקציה F = (A + B)·(B + C) כסכום מכפלות, נמפה אותה במפה ונכתוב אותה בייצוג מספרי.

ג. פישוט פונקציות הנתונות כסכום מכפלות:

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

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

דוגמה 4.15

נפשט את הפונקציה F = A·B·C + A·C + A·B·C + A·B·C + A·B·C.

פתרון:

נמלא את המפה: A·B·C ← m₀; A·C ← m₁, m₃; A·B·C ← m₄; A·B·C ← m₅; A·B·C ← m₇.

F(A,B,C) = Σ(0,1,3,4,5,7)

העמודות 00 ו-01 כולן 1: קבוצה של ארבע משבצות, שבה B = 0 ← B.

העמודות 01 ו-11 כולן 1: קבוצה של ארבע משבצות, שבה C = 1 ← C.

חמש מכפלות שבהן 14 ליטרלים הפכו לשני ליטרלים. בדיקה: בשורה A B C = 010 הפונקציה המקורית שווה 0, והביטוי המפושט: B + C = 0 + 0 = 0.

F = C + B

דוגמה 4.16

מעגל בנוי לפי הפונקציה F = A·B·C·D + A·B·C·D + A·B·D + A·B·D + A·B·D. נפשט את הפונקציה ונשווה בין שני המעגלים.

פתרון:

נמלא את המפה: A·B·C·D ← m₀; A·B·C·D ← m₂; A·B·D ← m₈, m₁₀; A·B·D ← m₁₃, m₁₅; A·B·D ← m₅, m₇.

אותה מפה שכבר פגשנו

ארבע הפינות ← B·D. הריבוע האמצעי ← B·D.

F = B·D + B·D

לפני הפישוט: חמישה שערי AND ושער OR בעל חמישה מבואות

אחרי הפישוט: שני שערי AND ושער OR

מספר הליטרלים ירד מ-17 ל-4, ומספר שערי AND מ-5 ל-2. שני המעגלים נותנים אותו מוצא לכל צירוף מבואות.

F = B·D + B·D

בעיה מילולית: מן התיאור אל המעגל

דוגמה 4.17

ועדה של שלושה שופטים A, B, C. כל שופט לוחץ על לחצן: 1 = בעד, 0 = נגד. נורה F נדלקת אם רוב השופטים בעד. נתכנן את המעגל.

פתרון:

נכתוב את טבלת האמת: F = 1 בכל שורה שבה שניים או שלושה מן המבואות הם 1.

i	A	B	C	F
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	1
6	1	1	0	1
7	1	1	1	1

שלוש קבוצות של שתי משבצות

F = A·B·C + A·B·C + A·B·C + A·B·C

F(A,B,C) = Σ(3,5,6,7)

במפה יש שלוש קבוצות של שתי משבצות, וכולן עוברות במשבצת m₇. אין קבוצה של ארבע משבצות.

נקרא: (m₆, m₇) ← A·B; (m₅, m₇) ← A·C; (m₃, m₇) ← B·C.

מעגל הרוב

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

F = B·C + A·C + A·B

קבוצה מיותרת

הכלל "מתחילים בקבוצה הגדולה ביותר" אינו מספיק תמיד. בפונקציה F(A,B,C,D) = Σ(1,5,6,7,11,12,13,15) יש ריבוע של ארבע משבצות במרכז המפה, ומי שמסרטט אותו ראשון מקבל חמש קבוצות. אבל כל משבצת בריבוע הזה מכוסה גם בקבוצה אחרת הכרחית, ולכן הריבוע מיותר.

שגוי: חמש קבוצות — הריבוע האדום מיותר

נכון: ארבע קבוצות: F = A·C·D + A·B·C + A·C·D + A·B·C

הערה: איך נמנעים מכך? מתחילים במשבצות שיש להן אפשרות אחת. כאן: m₁ מתקבצת רק עם m₅; m₆ רק עם m₇; m₁₁ רק עם m₁₅; m₁₂ רק עם m₁₃. אחרי סרטוט ארבע הקבוצות האלה כל המשבצות מכוסות, ואין צורך בריבוע.

יותר מפתרון מינימלי אחד

לפעמים אפשר לכסות את המשבצות בשתי דרכים שונות, ובשתי הדרכים אותו מספר קבוצות ואותו מספר ליטרלים. אז יש לפונקציה שני פתרונות מינימליים, ושניהם נכונים. בפונקציה F(A,B,C) = Σ(0,1,3,4,7) המשבצת m₁ יכולה להצטרף אל m₀ או אל m₃.

F = B·C + B·C + A·C

F = B·C + B·C + A·B

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

טעויות נפוצות

שגוי: קבוצה של שלוש משבצות

שגוי: קבוצה אלכסונית

שגוי: שתי קבוצות קטנות במקום אחת גדולה: F = B·C + B·C

נכון: שתי קבוצות של שתי משבצות: F = B·C + A·C

נכון: אין פישוט: F = A·B·C + A·B·C

נכון: קבוצה אחת דרך שני הקצוות: F = C

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

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

1F = A·B·C + A·B·C + A·B

2F = A·C + A·B·C + A·B·C

3F = A·B·C + A·B·C + A·B + A·B·C

4F = A·C + A·B·C + A·B·C

5F = A·B + A·B·C + A·B·C + A·B·C

6F = A·B·C + A·B·C + A·B·C + A·B·C

תשובות: 1 F = A 2 F = C 3 F = B·C + A 4 F = C 5 F = C + A·B 6 F = A·C + A·B

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

1F = A·B·C·D + A·B·C·D + A·B·D

2F = A·B + A·B·D + A·B·C·D + A·B·C·D

3F = A·B·D + A·B·D + A·B·C·D + A·B·C·D

4F = B·C·D + B·C·D + A·C·D + A·C·D

5F = A·B·C·D + A·B·C·D + A·B·C·D + A·B·C·D + A·B·C·D + A·B·C·D

6F = A·B·C + A·B·C + A·B·C·D + A·B·C·D + A·B·C·D

תשובות: 1 F = B·D 2 F = A 3 F = B·D + A·B 4 F = B·D + A·D 5 F = C·D + B·D 6 F = C·D + B·C + A·B·D

ד. צירופי ברירה:

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

דוגמה מפרק 1: בקוד BCD מופיעים רק הצירופים 0000 עד 1001. ששת הצירופים 1010 עד 1111 אינם מגיעים לעולם אל המעגל, ולכן לא חשוב לנו מה המעגל מוציא בהם. זהו "חופש" שננצל לפישוט.

פונקציה עם צירופי ברירה

F(A,B,C,D) = Σ(5,6,7,8,9) + d(10,11,12,13,14,15)

סימן	משמעות	יחידת מידה
Σ(...)	המשבצות שבהן F = 1	—
d(...)	משבצות הברירה: כותבים בהן X	—
	בכל המשבצות האחרות F = 0	—

משבצת שבה X נחשיב כ-1 אם הדבר מגדיל קבוצה, ונחשיב כ-0 אם אינה מועילה לנו.
אין צורך לכסות את משבצות X. מכסים רק את כל המשבצות שבהן 1.
לא בונים קבוצה שכולה X — זו קבוצה מיותרת.

דוגמה 4.18

נפשט את הפונקציה F(A,B,C) = Σ(0,4,5) + d(1,6), פעם בלי לנצל את צירופי הברירה ופעם תוך ניצולם.

פתרון:

נחשיב כל X כאפס: F = B·C + A·B

נחשיב את X שב-m₁ כאחד: F = B

בלי צירופי הברירה: שתי קבוצות של שתי משבצות, 4 ליטרלים.

אם נחשיב את המשבצת m₁ כאחד נקבל קבוצה של ארבע משבצות (m₀, m₁, m₄, m₅): B = 0 ← B. המשבצת m₆ אינה מגדילה שום קבוצה, ולכן נחשיב אותה כ-0 ולא נכסה אותה.

F = B

שימו לב: אחרי הפישוט לא נשאר במעגל "X": המעגל הממשי מוציא תמיד 0 או 1. כל X שנכנס לקבוצה הפך ל-1, וכל X שנשאר מחוץ לקבוצות הפך ל-0. בדוגמה הקודמת: אם מגיע הצירוף 001 המוצא הוא 1, ואם מגיע 110 המוצא הוא 0.

דוגמה 4.19

מעגל מקבל ספרה עשרונית בקוד BCD במבואות A B C D (A היא הסיבית המשמעותית ביותר). המוצא F שווה 1 אם הספרה היא 5 או יותר. נתכנן את המעגל.

פתרון:

הספרות 5, 6, 7, 8, 9 נותנות F = 1; הספרות 0 – 4 נותנות F = 0; הצירופים 10 – 15 אינם ספרות BCD ← צירופי ברירה.

F(A,B,C,D) = Σ(5,6,7,8,9) + d(10,11,12,13,14,15)

i	A	B	C	D	F
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	1
7	0	1	1	1	1
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	X
11	1	0	1	1	X
12	1	1	0	0	X
13	1	1	0	1	X
14	1	1	1	0	X
15	1	1	1	1	X

כל ה-X בשתי השורות התחתונות

שתי השורות התחתונות (A = 1): יש בהן m₈, m₉ ושש משבצות X ← קבוצה של שמונה משבצות: A.

המשבצות m₅, m₇ עם X שב-m₁₃, m₁₅ ← ריבוע של ארבע משבצות: B·D.

המשבצות m₆, m₇ עם X שב-m₁₄, m₁₅ ← ריבוע של ארבע משבצות: B·C.

בלי צירופי הברירה היינו מקבלים F = A·B·C + A·B·D + A·B·C — 9 ליטרלים במקום 5.

המעגל אחרי הפישוט

F = B·D + B·C + A

תצוגת 7 מקטעים

בתצוגת 7 מקטעים יש שבעה מקטעי אור ששמותיהם a עד g. לכל מקטע פונקציה משלו: מבואותיה הם ארבע סיביות BCD של הספרה המוצגת, ומוצאה 1 כאשר המקטע צריך לדלוק. הצירופים 10 – 15 הם צירופי ברירה, ולכן הפונקציות האלה הן דוגמה מצוינת — ואהובה בבחינות — לפישוט עם צירופי ברירה.

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

דוגמה 4.20

נמצא את הביטוי המינימלי של המקטע a בתצוגה המקבלת ספרה בקוד BCD במבואות A B C D.

פתרון:

המקטע a דולק בספרות 0, 2, 3, 5, 6, 7, 8, 9, ואינו דולק בספרות 1 ו-4.

a(A,B,C,D) = Σ(0,2,3,5,6,7,8,9) + d(10,11,12,13,14,15)

מפת המקטע a

נקרא את הקבוצות: C (8 משבצות); B·D (4 משבצות); B·D (4 משבצות); A (8 משבצות).

בדיקה: הספרה 1 היא 0001 ← הביטוי נותן 0, והמקטע a אכן כבוי בספרה 1. הספרה 7 היא 0111 ← הביטוי נותן 1.

a = C + B·D + B·D + A

תרגול מהיר — נפשט תוך ניצול צירופי הברירה

1F(A,B,C) = Σ(1,3) + d(5,7)

2F(A,B,C) = Σ(2,6) + d(0,7)

3F(A,B,C) = Σ(0,1) + d(2,5)

4F(A,B,C) = Σ(3,5,7) + d(1,6)

תשובות: 1 F = C 2 F = B·C 3 F = A·B 4 F = C

תרגול מהיר — פונקציה F של המשתנים A, B, C, D עם צירופי ברירה. נפשט

1Σ(1,3,5,7) + d(9,11,13,15)

2Σ(8,9) + d(10,11,12,13,14,15)

3Σ(4,5,6) + d(7,12,13,14,15)

4Σ(0,1,2) + d(10,11,12,13,14,15)

5Σ(3,7,9) + d(10,11,12,13,14,15)

6Σ(0,2,8) + d(5,7,10)

תשובות: 1 F = D 2 F = A 3 F = B 4 F = B·C·D + A·B·C (יש פתרון מינימלי נוסף: F = A·B·D + A·B·C) 5 F = C·D + A·D 6 F = B·D

שאלה 4.5: נפשט את הפונקציה F(A,B,C,D) = Σ(5,7,13) + d(0,2,8,15). בכמה משבצות X השתמשנו, וכמה נשארו מחוץ לקבוצות?

סיכום נוסחאות הפרק:

החוק	הנוסחה
מספר המינטרמים (ומספר משבצות המפה) ל-n משתנים	2ⁿ
המינטרם: 1 ← המשתנה כמות שהוא, 0 ← מהופך	m₅ = A·B·C
הצורה הקנונית והייצוג המספרי	F(A,B,C) = Σ(1,3,4,5) = m₁ + m₃ + m₄ + m₅
סדר העמודות והשורות במפה (קוד גריי)	00 , 01 , 11 , 10
מספר המשבצות הסמוכות לכל משבצת	n
קיבוץ שתי משבצות סמוכות	A·B·C + A·B·C = A·B
גודל הקבוצה המותר	1 , 2 , 4 , 8 , 16
מספר הליטרלים במכפלה של קבוצה בת 2^p משבצות	L = n − p
מספר המשבצות שממלאת מכפלה בת L ליטרלים	N = 2^{n − L}
פונקציה עם צירופי ברירה	F = Σ(...) + d(...)

מילון מונחים:

עברית	English	العربية
פונקציה בוליאנית	Boolean function	دالة بوليانية
פישוט	Simplification / Minimization	التبسيط
מכפלה	Product term	حاصل ضرب
סכום של מכפלות	Sum of products (SOP)	مجموع حواصل الضرب
ליטרל	Literal	حرف
מינטרם	Minterm	الحد الأصغري
צורה קנונית	Canonical form	الصيغة القانونية
ייצוג מספרי	Numerical (Σ) notation	التمثيل العددي
טבלת אמת	Truth table	جدول الصواب
מפת קרנו	Karnaugh map (K-map)	خريطة كارنو
משבצת	Cell	خانة
משבצות סמוכות	Adjacent cells	خانات متجاورة
קוד גריי	Gray code	شيفرة غراي
קבוצה (לולאה)	Group / Loop	مجموعة
ביטוי מינימלי	Minimal expression	التعبير الأصغري
קבוצה מיותרת	Redundant group	مجموعة زائدة
מיפוי פונקציה	Mapping a function	رسم الدالة في الخريطة
צירופי ברירה	Don't-care conditions	حالات اللامبالاة
קוד BCD	Binary Coded Decimal	شيفرة BCD
תצוגת 7 מקטעים	7-segment display	شاشة العرض ذات السبع قطع
רוב	Majority	الأغلبية

שאלות לתרגול:

רמה ראשונה — בסיסי

נכתוב את המינטרמים:
(א) לפונקציה של A, B, C: m₀, m₃, m₅, m₆
(ב) לפונקציה של A, B, C, D: m₂, m₉, m₁₂, m₁₅.

תשובות: (א) A·B·C, A·B·C, A·B·C, A·B·C (ב) A·B·C·D, A·B·C·D, A·B·C·D, A·B·C·D

מהו המספר של כל מינטרם? A·B·C, A·B·C, A·B·C·D, A·B·C·D, A·B·C·D.

תשובות: m₃, m₄, m₆, m₁₁, m₁₃

הפונקציה F נתונה בטבלת האמת.
(א) נכתוב אותה בצורה הקנונית.
(ב) נכתוב אותה בייצוג מספרי.

i	A	B	C	F
0	0	0	0	1
1	0	0	1	1
2	0	1	0	0
3	0	1	1	0
4	1	0	0	0
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

תשובות: (א) F = A·B·C + A·B·C + A·B·C + A·B·C (ב) F(A,B,C) = Σ(0,1,6,7)

נכתוב את הביטוי הקנוני ונסרטט את טבלת האמת של כל פונקציה:
(א) F(A,B,C) = Σ(1,2,7)
(ב) F(A,B,C) = Σ(0,4,5,6).

תשובות: (א) F = A·B·C + A·B·C + A·B·C; עמודת המוצא מן השורה 0 עד 7: 0110 0001 (ב) F = A·B·C + A·B·C + A·B·C + A·B·C; עמודת המוצא: 1000 1110

נכתוב בייצוג מספרי:
(א) F = A·B·C + A·B·C + A·B·C
(ב) F = A·B·C·D + A·B·C·D + A·B·C·D.

תשובות: (א) F(A,B,C) = Σ(0,3,6) (ב) F(A,B,C,D) = Σ(5,10,15)

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

תשובות: (א) 4 מינטרמים, שני ליטרלים (ב) 8, שלושה ליטרלים (ג) 16, ארבעה ליטרלים (ד) 32, חמישה ליטרלים

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

תשובות: העמודה השלישית (11): במפה של שלושה משתנים 3, 7; במפה של ארבעה משתנים 3, 7, 15, 11. השורה השלישית (A B = 11): 12, 13, 15, 14

מפה של ארבעה משתנים. אילו זוגות משבצות סמוכים? m₀ ו-m₂; m₁ ו-m₃; m₅ ו-m₆; m₄ ו-m₁₂; m₃ ו-m₁₁; m₀ ו-m₁₀; m₈ ו-m₁₀; m₇ ו-m₁₃.

תשובות: סמוכות: m₀ , m₂; m₁ , m₃; m₄ , m₁₂; m₃ , m₁₁; m₈ , m₁₀ — אינן סמוכות: m₅ , m₆; m₀ , m₁₀; m₇ , m₁₃

נכתוב את ארבע המשבצות הסמוכות לכל משבצת במפה של ארבעה משתנים: m₅, m₈, m₁₅.

תשובות: m₅: 1 , 4 , 7 , 13; m₈: 0 , 9 , 10 , 12; m₁₅: 7 , 11 , 13 , 14

10.

בכל מפה יש קבוצה אחת. נכתוב את המכפלה שהיא נותנת.

(א)

(ב)

(ג)

(ד)

תשובות: (א) A·C, (ב) B, (ג) B·C, (ד) A·B

11.

נפשט בעזרת מפה לשני משתנים:
(א) F(A,B) = Σ(0,2);
(ב) F(A,B) = Σ(1,2,3);
(ג) F(A,B) = Σ(0,3);
(ד) F(A,B) = Σ(0,1,2,3).

תשובות: (א) F = B; (ב) F = B + A; (ג) F = A·B + A·B; (ד) F = 1 — ב-(ג) שתי המשבצות אלכסוניות ואין פישוט; ב-(ד) כל המשבצות 1

12.

נפשט בעזרת מפה לשלושה משתנים:
(א) F(A,B,C) = Σ(0,1,4,5);
(ב) F(A,B,C) = Σ(3,7);
(ג) F(A,B,C) = Σ(0,2,3,6,7);
(ד) F(A,B,C) = Σ(1,3,4,6).

תשובות: (א) F = B; (ב) F = B·C; (ג) F = B + A·C; (ד) F = A·C + A·C

13.

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

i	A	B	C	F
0	0	0	0	0
1	0	0	1	0
2	0	1	0	1
3	0	1	1	1
4	1	0	0	1
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

תשובות: (א) F(A,B,C) = Σ(2,3,4,6,7) (ג) F = B + A·C (ד) הצורה הקנונית: 15 ליטרלים; הביטוי המינימלי: 3 ליטרלים

14.

מפה של ארבעה משתנים. כמה משבצות ממלאת כל מכפלה, ומהם מספריהן? A, B·D, A·B·D, A·B·C·D, C.

תשובות: A: 8 משבצות (8 , 9 , 10 , 11 , 12 , 13 , 14 , 15); B·D: 4 משבצות (1 , 3 , 9 , 11); A·B·D: שתי משבצות (4 , 6); A·B·C·D: משבצת אחת (12); C: 8 משבצות (2 , 3 , 6 , 7 , 10 , 11 , 14 , 15)

רמה שנייה — בינוני

15.

נפשט בעזרת מפה לארבעה משתנים:
(א) F(A,B,C,D) = Σ(0,1,2,3,6,7,14,15);
(ב) F(A,B,C,D) = Σ(1,5,9,12,13,14);
(ג) F(A,B,C,D) = Σ(0,3,4,7,8,11,12,15).

תשובות: (א) F = B·C + A·B; (ב) F = C·D + A·B·D; (ג) F = C·D + C·D

16.

בפונקציות הבאות יש קבוצות דרך קצוות המפה או בפינותיה. נפשט:
(א) F(A,B,C,D) = Σ(0,2,8,10,12,14);
(ב) F(A,B,C,D) = Σ(0,1,6,8,9,14);
(ג) F(A,B,C,D) = Σ(1,4,6,9,12,14).

תשובות: (א) F = B·D + A·D; (ב) F = B·C·D + B·C; (ג) F = B·D + B·C·D

17.

נעתיק את המפה למחברת, נמלא אותה לפי הפונקציה F(A,B,C,D) = Σ(1,3,5,6,7,9,11,14), נבנה את הקבוצות ונכתוב את הביטוי המינימלי.

תשובות: F = B·C·D + B·D + A·D

18.

הפונקציה F = A·C + A·B + A·B·C אינה נתונה בצורתה הקנונית.
(א) נמפה אותה במפה ונכתוב אותה בייצוג מספרי.
(ב) נכתוב את צורתה הקנונית.
(ג) נפשט אותה.

תשובות: (א) F(A,B,C) = Σ(0,2,5,6,7) (ב) F = A·B·C + A·B·C + A·B·C + A·B·C + A·B·C (ג) F = B·C + A·C + A·C (יש פתרון מינימלי נוסף: F = A·C + A·B + A·C)

19.

נמפה את הפונקציה F = A·C·D + A·C·D + B·C·D + A·B·C·D + A·C·D במפה, נכתוב אותה בייצוג מספרי ונפשט אותה.

תשובות: F(A,B,C,D) = Σ(0,4,6,7,8,11,12,14,15); F = C·D + B·C + A·C·D

20.

הפונקציה F = A·B·(A + C) אינה סכום מכפלות.
(א) נפתח את ההיפוך ואת הסוגריים ונכתוב אותה כסכום מכפלות.
(ב) נכתוב אותה בייצוג מספרי.
(ג) נמצא את הביטוי המינימלי בעזרת המפה.

תשובות: (א) F = (A + B)·(A + C) = A·C + A·B + B·C (ב) F(A,B,C) = Σ(1,3,4,5) (ג) F = A·B + A·C

21.

נכתוב את טבלת האמת של הפונקציה F = (A + B)·(C + D)·A·B (נחשב את הערך בכל שורה), ואחר כך נכתוב אותה בייצוג מספרי ונפשט אותה בעזרת המפה.

תשובות: F(A,B,C,D) = Σ(4,5,7,8,9,11); F = A·B·D + A·B·C + A·B·D + A·B·C

22.

תלמיד פישט את הפונקציה F(A,B,C,D) = Σ(0,2,5,7,8,10,13,15) כמו במפה וכתב: F = A·B·D + A·B·D + A·B·D + A·B·D.
(א) האם הביטוי שלו שווה לפונקציה?
(ב) מה הטעות בפתרון?
(ג) נכתוב את הביטוי המינימלי.

תשובות: (א) כן, הביטוי נכון אבל אינו המינימלי (ב) הקבוצות קטנות: כל שתי קבוצות אפשר לאחד לקבוצה של ארבע משבצות (ארבע הפינות, והריבוע האמצעי) (ג) F = B·D + B·D

23.

תלמידה פישטה את הפונקציה F(A,B,C) = Σ(1,3,5,6,7) וכתבה F = C + B. נסרטט את המפה ונבדוק: האם הפתרון נכון? אם לא — היכן הטעות ומהו הפתרון הנכון?

תשובות: הפתרון שגוי: הקבוצה B כוללת את המשבצת m₂ שבה 0. הפתרון הנכון: F = C + A·B

24.

נפשט תוך ניצול צירופי הברירה:
(א) F(A,B,C) = Σ(0,4,5) + d(1,7);
(ב) F(A,B,C) = Σ(2,3,7) + d(0,6).

תשובות: (א) F = B; (ב) F = B

25.

נפשט תוך ניצול צירופי הברירה:
(א) F(A,B,C,D) = Σ(1,5,7,9) + d(3,11,13,15);
(ב) F(A,B,C,D) = Σ(0,2,4,6,8) + d(10,11,12,13,14,15).

תשובות: (א) F = D; (ב) F = D

26.

לפונקציה F(A,B,C) = Σ(0,1,2,5,6,7) יש יותר מפתרון מינימלי אחד. נסרטט את המפה פעמיים ונמצא שני פתרונות שונים. כמה ליטרלים יש בכל פתרון?

תשובות: F = B·C + A·B + A·C (יש פתרון מינימלי נוסף: F = B·C + A·C + A·B); בכל פתרון 6 ליטרלים

27.

נסרטט את מפת הפונקציה F(A,B,C) = Σ(1,2,4,7).
(א) מדוע אי אפשר לפשט אותה בעזרת המפה?
(ב) נבדוק בטבלת האמת ש-F = A ⊕ B ⊕ C.

תשובות: (א) המשבצות שבהן 1 מסודרות כמו לוח שחמט: אין שתי משבצות סמוכות, ולכן כל משבצת היא קבוצה לבדה ו-F = A·B·C + A·B·C + A·B·C + A·B·C (ב) A ⊕ B ⊕ C שווה 1 כאשר מספר המבואות שערכם 1 אי-זוגי: השורות 1, 2, 4, 7

28.

הביטוי המינימלי של פונקציה בת ארבעה משתנים הוא F = B·D + A·D.
(א) בכמה משבצות יש 1 במפת הפונקציה?
(ב) נכתוב את הפונקציה בייצוג מספרי.

תשובות: (א) 8 משבצות (שתי הקבוצות בנות ארבע משבצות, ואין להן משבצות משותפות) (ב) F(A,B,C,D) = Σ(0,2,4,5,6,7,13,15)

29.

מעגל הרוב מן הדוגמה הפתורה בפרק, F = B·C + A·C + A·B.
(א) כמה שערי AND וכמה שערי OR דרושים למימוש הצורה הקנונית, וכמה מבואות יש לכל שער?
(ב) וכמה דרושים למימוש הביטוי המינימלי?

תשובות: (א) 4 שערי AND בעלי שלושה מבואות, ושער OR בעל 4 מבואות (ושלושה מהפכים) (ב) 3 שערי AND בעלי שני מבואות ושער OR בעל שלושה מבואות, בלי מהפכים

רמה שלישית — אתגר

30.

למערכת אזעקה בבית יש ארבעה מבואות: A — המערכת מופעלת; B — הדלת פתוחה; C — החלון פתוח; D — חיישן התנועה גילה תנועה. צופר האזעקה F פועל אם המערכת מופעלת ונפתחו הדלת או החלון, וגם — אפילו כשהמערכת אינה מופעלת — אם החלון פתוח והתגלתה תנועה.
(א) נכתוב את טבלת האמת ואת הייצוג המספרי.
(ב) נמצא את הביטוי המינימלי בעזרת המפה.
(ג) כמה שערים דרושים?

תשובות: (א) F(A,B,C,D) = Σ(3,7,10,11,12,13,14,15) (ב) F = C·D + A·C + A·B (ג) 3 שערי AND בעלי שני מבואות ושער OR אחד

31.

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

תשובות: F(A,B,C,D) = Σ(7,9,10,11,12,13,14,15); F = B·C·D + A·D + A·C + A·B

32.

מעגל משווה בין שני מספרים בינאריים בני שתי סיביות: N₁ = A B ו-N₂ = C D. המוצא F = 1 אם N₁ > N₂.
(א) נכתוב את הייצוג המספרי.
(ב) נמצא את הביטוי המינימלי.

תשובות: (א) F(A,B,C,D) = Σ(4,8,9,12,13,14) (ב) F = B·C·D + A·C + A·B·D

33.

המבואות A B C D כותבים מספר בינארי מ-0 עד 15. המוצא F = 1 אם המספר ראשוני (2, 3, 5, 7, 11, 13). נמצא את הביטוי המינימלי.

תשובות: F(A,B,C,D) = Σ(2,3,5,7,11,13); F = B·C·D + B·C·D + A·C·D + A·B·C (יש פתרון מינימלי נוסף: F = B·C·D + B·C·D + A·B·D + A·B·C)

34.

אותה שאלה כמו הקודמת, אבל עכשיו המבואות הם ספרה עשרונית בקוד BCD (מ-0 עד 9 בלבד), והמוצא F = 1 אם הספרה ראשונית. נכתוב את הייצוג המספרי עם צירופי הברירה ונמצא את הביטוי המינימלי. כמה ליטרלים חסכו צירופי הברירה בהשוואה לפתרון בלעדיהם?

תשובות: F(A,B,C,D) = Σ(2,3,5,7) + d(10,11,12,13,14,15); F = B·D + B·C; בלי צירופי הברירה: F = A·B·D + A·B·C (6 ליטרלים במקום 4)

35.

מעגל מקבל ספרה בקוד BCD. המוצא F = 1 אם הספרה מתחלקת ב-3 בלי שארית (3, 6, 9). נמצא את הביטוי המינימלי.

תשובות: F(A,B,C,D) = Σ(3,6,9) + d(10,11,12,13,14,15); F = B·C·D + B·C·D + A·D

36.

מעגל מקבל ספרה בקוד BCD. נמצא את הביטוי המינימלי של כל מוצא:
(א) F₁ = 1 אם הספרה אי-זוגית.
(ב) F₂ = 1 אם הספרה גדולה מ-7.
(ג) F₃ = 1 אם הספרה קטנה מ-3.

תשובות: (א) F₁ = D (ב) F₂ = A (ג) F₃ = B·C·D + A·B·C (יש פתרון מינימלי נוסף: F₃ = A·B·D + A·B·C)

37.

תצוגת 7 מקטעים מקבלת ספרה בקוד BCD (כמו בדוגמה הפתורה; צורות הספרות מופיעות באיור). נמצא את הביטוי המינימלי של המקטעים b, c ו-e.

תשובות: Σ(0,1,2,3,4,7,8,9) + d(10,11,12,13,14,15); b = C·D + C·D + B; Σ(0,1,3,4,5,6,7,8,9) + d(10,11,12,13,14,15); c = D + C + B; Σ(0,2,6,8) + d(10,11,12,13,14,15); e = C·D + B·D

38.

לאותה תצוגה נמצא את הביטוי המינימלי של המקטעים d, f ו-g.

תשובות: Σ(0,2,3,5,6,8,9) + d(10,11,12,13,14,15); d = C·D + B·C·D + B·D + B·C + A; Σ(0,4,5,6,8,9) + d(10,11,12,13,14,15); f = C·D + B·D + B·C + A; Σ(2,3,4,5,6,8,9) + d(10,11,12,13,14,15); g = C·D + B·C + B·C + A (יש פתרון מינימלי נוסף: g = B·D + B·C + B·C + A)

39.

במכל מים שלושה חיישני גובה: A למטה, B באמצע, C למעלה. החיישן מוציא 1 כאשר המים מכסים אותו. מכיוון שהמים ממלאים את המכל מלמטה, יש צירופים שאינם יכולים להופיע (למשל C = 1 וגם A = 0).
(א) אילו צירופים אפשריים ואילו הם צירופי ברירה?
(ב) המשאבה P פועלת כאשר המים מתחת לחיישן האמצעי. נמצא את הביטוי המינימלי של P.
(ג) נורת אזהרה W נדלקת כאשר המכל ריק לגמרי או מלא לגמרי. נמצא את הביטוי המינימלי של W.

תשובות: (א) האפשריים: 000, 100, 110, 111; צירופי הברירה: 001, 010, 011, 101 (ב) P(A,B,C) = Σ(0,4) + d(1,2,3,5); P = B (ג) W(A,B,C) = Σ(0,7) + d(1,2,3,5); W = C + A

40.

המבואות A B C D כותבים מספר בינארי מ-0 עד 15. המוצא F = 1 אם המספר הוא ריבוע שלם (0, 1, 4, 9).
(א) נמצא את הביטוי המינימלי.
(ב) נמצא את הביטוי המינימלי אם ידוע שהמספרים 10 – 15 אינם מופיעים לעולם.

תשובות: (א) F = B·C·D + A·C·D (ב) F = B·C·D + A·C·D

41.

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

תשובות: (א) F(A,B,C,D) = Σ(3,5,6,9,10,12) (ב) לא: כל שתי משבצות סמוכות נבדלות במשתנה אחד, ולכן מספר האחדות בהן שונה; אין שתי משבצות סמוכות שבשתיהן 1, והביטוי המינימלי הוא הצורה הקנונית עצמה (6 מינטרמים)

42.

נפשט את הפונקציה F(A,B,C,D) = Σ(0,1,2,3,4,6,8,9,10,11,12,14). אחר כך נענה: איזו פונקציה נקבל אם נכתוב 1 גם במשבצות 5 ו-7?

תשובות: F = D + B; עם המשבצות 5 ו-7: F = D + B + A

מפות קרנו לפתרונות של שאלות נבחרות:

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

שאלה 13

שאלה 15 (א)

שאלה 15 (ב)

שאלה 15 (ג)

שאלה 16 (א)

שאלה 16 (ב)

שאלה 16 (ג)

שאלה 17

שאלה 18

שאלה 19

שאלה 20

שאלה 21

שאלה 23

שאלה 24 (א)

שאלה 24 (ב)

שאלה 25 (א)

שאלה 25 (ב)

שאלה 26

שאלה 30

שאלה 31

שאלה 32

שאלה 33

שאלה 34

שאלה 35

שאלה 36 (א)

שאלה 36 (ב)

שאלה 36 (ג)

שאלה 37 (b)

שאלה 37 (c)

שאלה 37 (e)

שאלה 38 (d)

שאלה 38 (f)

שאלה 38 (g)

שאלה 39 (P)

שאלה 39 (W)

שאלה 40 (א)

שאלה 40 (ב)

שאלה 42

תשובות סופיות לשאלות הפרק

4.1 F = A·B·C + A·B·C + A·B·C + A·B·C

4.2 (א) m₀ בעמודה 00, m₃ בעמודה 11, m₅ בעמודה 01, m₆ בעמודה 10 (ב) m₁ בעמודה 01, m₄ בעמודה 00, m₆ בעמודה 10, m₉ בעמודה 01, m₁₁ בעמודה 11, m₁₄ בעמודה 10

4.3 (א) B·C, (ב) A·D, (ג) A·B, (ד) B·C

4.4 אחרי פתיחת הסוגריים: F = A·B + A·C + B·C; F(A,B,C) = Σ(1,5,6,7)

4.5 F = B·D; השתמשנו ב-1 ממשבצות X, ו-3 נשארו מחוץ לקבוצות

שאלות בגרות לפרק 4

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

בגרות 2026 שאלה 9 — פונקציה בוליאנית מטבלת אמת

סעיף	הנדרש	תשובה סופית
סעיף א	ביטוי הפונקציה (סכום מכפלות)	בפתרון המלא
סעיף ב	מפת קרנו ופישוט	F = A · B + A · C + B · C
סעיף ג	מימוש במערכת מתגים	בפתרון המלא

הפתרון המלא : fahed-lab.com/exams/electricity-845381/solutions/solution-2026

בגרות 2025 שאלה 9 — פישוט פונקציה מטבלת אמת

סעיף	הנדרש	תשובה סופית
סעיף א	הצגה במפת קרנו ופישוט	F = Y + X · Z + X · Z
סעיף ב	מימוש בשערים לוגיים	בפתרון המלא
סעיף ג	מימוש במערכת מתגים	בפתרון המלא

הפתרון המלא : fahed-lab.com/exams/electricity-845381/solutions/solution-2025

בגרות 2023 שאלה 10 — מפת קרנו

סעיף	הנדרש	תשובה סופית
סעיף א	טבלת אמת	בפתרון המלא
סעיף ב	פישוט הפונקציה על-פי מפת קרנו	F = A · C + A · B + A · C
סעיף ג	מימוש הפונקציה המפושטת בשערים לוגיים	בפתרון המלא

הפתרון המלא : fahed-lab.com/exams/electricity-845381/solutions/solution-2023

בגרות 2022 שאלה 10 — טבלת אמת, מפת קרנו ומימוש ברכיבים 7404 / 7408 / 7432

סעיף	הנדרש	תשובה סופית
סעיף א	מפת קרנו ופישוט הפונקציה	F = A · B + B · C
סעיף ב	מימוש על גבי הרכיבים 7404, 7408, 7432	בפתרון המלא

הפתרון המלא : fahed-lab.com/exams/electricity-845381/solutions/solution-2022

בגרות 2022 שאלה 9 — פונקציה בוליאנית ומפת קרנו

סעיף	הנדרש	תשובה סופית
סעיף א	הצגת הפונקציה על גבי מפת קרנו	בפתרון המלא
סעיף ב	צמצום הפונקציה	F = y · z + y · z + x · z
סעיף ג	מימוש הפונקציה המצומצמת בשערים לוגיים	בפתרון המלא

הפתרון המלא : fahed-lab.com/exams/electricity-845381/solutions/solution-2022

בגרות 2021 (מועד מיוחד) שאלה 10 — פונקציה בוליאנית מטבלת אמת

סעיף	הנדרש	תשובה סופית
סעיף א	כתיבת ביטוי לפונקציה F לפי טבלת האמת	F = A · B · C + A · B · C + A · B · C
סעיף ב	פישוט הפונקציה בכללי האלגברה הבוליאנית	F = C(A + B) = A · C + B · C
סעיף ג	מימוש הפונקציה המפושטת בשערים לוגיים	F = C(A + B) = A · B + C

הפתרון המלא : fahed-lab.com/exams/electricity-845381/solutions/solution-2021-makeup

בגרות 2020 שאלה 10 — מפת קרנו ומימוש פונקציה

סעיף	הנדרש	תשובה סופית
סעיף א	פישוט הפונקציה במינימום משתנים	F = B C + B C = B ⊕ C
סעיף ב	מימוש הפונקציה המפושטת בשערים לוגיים	בפתרון המלא
סעיף ג	מימוש על גבי מערך המעגלים המשולבים שבנספח	בפתרון המלא

הפתרון המלא : fahed-lab.com/exams/electricity-845381/solutions/solution-2020

בגרות 2019 שאלה 10 — מפת קרנו ומימוש ברכיבים משולבים

סעיף	הנדרש	תשובה סופית
סעיף א	פישוט הפונקציה F למינימום משתנים	F = B · C + A · C
סעיף ב	מימוש הפונקציה המפושטת בשערים לוגיים	בפתרון המלא
סעיף ג	הביטוי במוצא F של מערך הרכיבים המשולבים	F = A · B + B · C

הפתרון המלא : fahed-lab.com/exams/electricity-845381/solutions/solution-2019

בגרות 2018 שאלה 10 — מפת קרנו, פישוט ומימוש

סעיף	הנדרש	תשובה סופית
סעיף א	טבלת האמת של הפונקציה F	בפתרון המלא
סעיף ב	פישוט הפונקציה במפת קרנו	F = B + A · C + A · C = B + (A ⊕ C)
סעיף ג	מימוש הפונקציה בעזרת הרכיבים שבנספח	בפתרון המלא

הפתרון המלא : fahed-lab.com/exams/electricity-845381/solutions/solution-2018

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

i	A	B	C	D	F
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	1
7	0	1	1	1	1
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	X
11	1	0	1	1	X
12	1	1	0	0	X
13	1	1	0	1	X
14	1	1	1	0	X
15	1	1	1	1	X

i	A	B	C	D	F
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	1
7	0	1	1	1	1
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	X
11	1	0	1	1	X
12	1	1	0	0	X
13	1	1	0	1	X
14	1	1	1	0	X
15	1	1	1	1	X

i	A	B	C	D	F
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	1
7	0	1	1	1	1
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	X
11	1	0	1	1	X
12	1	1	0	0	X
13	1	1	0	1	X
14	1	1	1	0	X
15	1	1	1	1	X