בפישוט הביטוי הבוליאני, החוקים והכללים של האלגברה הבוליאנית משחקים תפקיד חשוב. לפני הבנת החוקים והכללים הללו של האלגברה הבוליאנית, הבן את מושג החיבור והכפל של פעולות בוליאניות.
תוספת בוליאנית
פעולת ההוספה של אלגברה בוליאנית דומה לפעולת OR. במעגלים דיגיטליים, פעולת ה-OR משמשת לחישוב מונח הסכום, מבלי להשתמש בפעולת AND. A + B, A + B', A + B + C', ו-A' + B + + D' הן חלק מהדוגמאות של 'מונח סכום'. הערך של מונח הסכום נכון כאשר אחד או יותר ממילולי אחד הם אמת ושקר כאשר כל המילולי הם שקריים.
כפל בוליאני
פעולת הכפל של אלגברה בוליאנית דומה לפעולת AND. במעגלים דיגיטליים, פעולת ה-AND מחשבת את התוצר, מבלי להשתמש בפעולת OR. AB, AB, ABC ו-ABCD הם חלק מהדוגמאות למונח המוצר. הערך של מונח המוצר נכון כאשר כל המילולים נכונים ושקריים כאשר כל אחד מהמילים הוא שקר.
חוקי האלגברה הבוליאנית
ישנם את החוקים הבאים של האלגברה הבוליאנית:
חוק חלופי
החוק הזה קובע שלא משנה באיזה סדר אנחנו משתמשים במשתנים. זה אומר שסדר המשתנים לא משנה. באלגברה בוליאנית, פעולות ה-OR וההוספה דומות. בתרשים שלהלן, שער ה-OR מציג שסדר משתני הקלט אינו משנה כלל.
כמה מקשים יש למקלדות
עבור שני משתנים, החוק הקומוטטיבי של החיבור נכתב כך:
A+B = B+A
עבור שני משתנים, החוק הקומוטטיבי של הכפל נכתב כך:
A.B = B.A
משפט אסוציאטיבי
חוק זה קובע שניתן לבצע את הפעולה בכל סדר כאשר עדיפות המשתנים זהה. כמו '*' ו-'/' יש אותה עדיפות. בתרשים שלהלן, החוק האסוציאטיבי מוחל על שער OR בעל 2 כניסות.
עבור שלושה משתנים, חוק החיבור האסוציאטיבי נכתב כך:
עבודה פנימית של hashmapA + (B + C) = (A + B) + C
עבור שלושה משתנים, החוק האסוציאטיבי של הכפל נכתב כך:
A(BC) = (AB)Cלפי חוק זה, לא משנה באיזה סדר מקובצים המשתנים כאשר AND מבצעים יותר משני משתנים. בתרשים שלהלן, החוק האסוציאטיבי מוחל על שער ו-2 כניסות.
עץ בינארי חציית הזמנה בדואר
חוק חלוקתי:
לפי חוק זה, אם נבצע את פעולת ה-OR של שני משתנים או יותר ולאחר מכן נבצע את פעולת ה-AND של התוצאה עם משתנה בודד, אז התוצאה תהיה דומה לביצוע פעולת ה-AND של אותו משתנה בודד עם כל שניים או יותר. משתנה ולאחר מכן בצע את פעולת ה-OR של אותו מוצר. חוק זה מסביר את תהליך הפקטורינג.
עבור שלושה משתנים, החוק החלוקתי נכתב כך:
A(B + C) = AB + AC
כללי האלגברה הבוליאנית
ישנם הכללים הבאים של אלגברה בוליאנית, המשמשים בעיקר במניפולציה ופישוט של ביטויים בוליאניים. כללים אלה ממלאים תפקיד חשוב בפישוט ביטויים בוליאניים.
| 1. | A+0=A | 7. | A.A=A |
| 2. | A+1=1 | 8. | A.A'=0 |
| 3. | A.0=0 | 9. | א''=א |
| 4. | A.1=A | 10. | A+AB=A |
| 5. | A+A=A | אחד עשר. | A+A'B=A+B |
| 6. | A+A'=1 | 12. | (A+B)(A+C)=A+BC |
כלל 1: A + 0 = A
בואו נניח; יש לנו משתנה קלט A שהערך שלו הוא 0 או 1. כאשר אנו מבצעים פעולת OR עם 0, התוצאה תהיה זהה למשתנה הקלט. לכן, אם ערך המשתנה הוא 1, אז התוצאה תהיה 1, ואם ערך המשתנה הוא 0, אז התוצאה תהיה 0. באופן דיאגרמטי, ניתן להגדיר כלל זה כך:
כלל 2: (A + 1) = 1
בואו נניח; יש לנו משתנה קלט A שהערך שלו הוא 0 או 1. כאשר אנו מבצעים פעולת OR עם 1, התוצאה תמיד תהיה 1. לכן, אם ערך המשתנה הוא 1 או 0, אז התוצאה תמיד תהיה 1. באופן דיאגרמטי , ניתן להגדיר כלל זה כ:
כלל 3: (A.0) = 0
בואו נניח; יש לנו משתנה קלט A שהערך שלו הוא 0 או 1. כאשר אנו מבצעים את פעולת ה-AND עם 0, התוצאה תמיד תהיה 0. כלל זה קובע שמשתנה קלט ANDed עם 0 שווה ל-0 תמיד. באופן דיאגרמטי, ניתן להגדיר כלל זה כך:
מעבר לא-סדר של עץ בינארי
כלל 4: (A.1) = A
בואו נניח; יש לנו משתנה קלט A שהערך שלו הוא 0 או 1. כאשר אנו מבצעים את פעולת ה-AND עם 1, התוצאה תמיד תהיה שווה למשתנה הקלט. כלל זה קובע שמשתנה קלט ANDed עם 1 שווה למשתנה הקלט תמיד. באופן דיאגרמטי, ניתן להגדיר כלל זה כך:
כלל 5: (A + A) = A
בואו נניח; יש לנו משתנה קלט A שהערך שלו הוא 0 או 1. כאשר אנו מבצעים את פעולת OR עם אותו משתנה, התוצאה תמיד תהיה שווה למשתנה הקלט. כלל זה קובע שמשתנה קלט OR עם עצמו שווה למשתנה הקלט תמיד. באופן דיאגרמטי, ניתן להגדיר כלל זה כך:
כלל 6: (A + A') = 1
בואו נניח; יש לנו משתנה קלט A שהערך שלו הוא 0 או 1. כאשר אנו מבצעים את פעולת OR עם ההשלמה של אותו משתנה, התוצאה תמיד תהיה שווה ל-1. כלל זה קובע שמשתנה ORed עם המשלים שלו שווה ל-1 תמיד. באופן דיאגרמטי, ניתן להגדיר כלל זה כך:
כלל 7: (A.A) = א
בואו נניח; יש לנו משתנה קלט A שהערך שלו הוא 0 או 1. כאשר אנו מבצעים את פעולת ה-AND עם אותו משתנה, התוצאה תמיד תהיה שווה למשתנה זה בלבד. כלל זה קובע שמשתנה ANDed עם עצמו שווה למשתנה הקלט תמיד. באופן דיאגרמטי, ניתן להגדיר כלל זה כך:
יסודות הבנייה של אובונטו
כלל 8: (A.A') = 0
בואו נניח; יש לנו משתנה קלט A שהערך שלו הוא 0 או 1. כאשר אנו מבצעים את פעולת AND עם ההשלמה של אותו משתנה, התוצאה תמיד תהיה שווה ל-0. כלל זה קובע שמשתנה ANDed עם המשלים שלו שווה ל-0 תמיד. באופן דיאגרמטי, ניתן להגדיר כלל זה כך:
כלל 9: A = (A')'
כלל זה קובע שאם נבצע את ההשלמה הכפולה של המשתנה, התוצאה תהיה זהה למשתנה המקורי. לכן, כאשר אנו מבצעים את ההשלמה של משתנה A, התוצאה תהיה A'. יתרה מכך, אם נבצע שוב את ההשלמה של A', נקבל את A, כלומר המשתנה המקורי.
כלל 10: (A + AB) = A
אנו יכולים להוכיח כלל זה באמצעות כלל 2, כלל 4, והחוק החלוקתי כ:
A + AB = A(1 + B) פקטורינג (חוק חלוקתי)A + AB = A.1 כלל 2: (1 + B)= 1
A + AB = A כלל 4: A .1 = A
כלל 11: A + AB = A + B
אנו יכולים להוכיח כלל זה על ידי שימוש בכללים לעיל כ:
A + AB = (A + AB)+ AB כלל 10: A = A + ABA+AB= (AA + AB)+ AB כלל 7: A = AA
A+AB=AA +AB +AA +AB כלל 8: הוספת AA = 0
A+AB= (A + A)(A + B) פקטורינג
A+AB= 1.(A + B) כלל 6: A + A = 1
A+AB=A + B כלל 4: שחרר את ה-1
כלל 12: (A + B)(A + C) = A + BC
אנו יכולים להוכיח כלל זה על ידי שימוש בכללים לעיל כ:
(A + B)(A + C)= AA + AC + AB + BC חוק חלוקתי(A + B)(A + C)= A + AC + AB + BC כלל 7: AA = A
(A + B)(A + C)= A( 1 + C)+ AB + BC כלל 2: 1 + C = 1
(A + B)(A + C)= A.1 + AB + BC פקטורינג (חוק חלוקתי)
(A + B)(A + C)= A(1 + B)+ BC כלל 2: 1 + B = 1
(A + B)(A + C)= A.1 + BC כלל 4: A .1 = A
(A + B)(A + C)= A + BC
