אלגברה בוליאנית: היסטוריה, משפטים ותנוחות, דוגמאות - מתמטיקה - 2025

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

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

מקור: pexels.com

הִיסטוֹרִיָה

אלגברה בוליאית הוצגה בשנת 1854 על ידי המתמטיקאי האנגלי ג'ורג 'בולי (1815 - 1864), שהיה מלומד בעצמו באותה תקופה. דאגתו נבעה מסכסוך קיים בין אוגוסטוס דה מורגן וויליאם המילטון, לגבי הפרמטרים המגדירים מערכת לוגית זו.

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

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

בשנת 1854 פורסמו החלקים המשמעותיים ביותר של האלגברה הבוליתית בספר "חקירת חוקי המחשבה עליהם מתבססות התיאוריות המתמטיות של ההיגיון וההסתברות."

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

בשנת 1948 קלוד שאנון יישם את זה על תכנון מעגלי מיתוג חשמליים הניתנים לבלתי-נסה. זה שימש כמבוא ליישום האלגברה הבוליאנית במסגרת כל התוכנית האלקטרונית-דיגיטלית.

מִבְנֶה

הערכים היסודיים בסוג זה של אלגברה הם 0 ו- 1, התואמים FALSE ו- TRUE בהתאמה. הפעולות הבסיסיות באלגברה הבולית הן 3:

- ותפעול או שילוב. מיוצג על ידי תקופה (.). שם נרדף למוצר.

- או פעולה או הפרדה. מיוצג על ידי צלב (+) .שם נרדף של הסכום.

- לא פעולה או שלילה. מיוצג על ידי הקידומת NOT (NOT A). זה ידוע גם כהשלמה.

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

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

. הוא מחלק ביחס לסכום + א. (b + c) = (a. b) + (a. c)

+ מפיץ ביחס למוצר. a + (b. c) = (a + b). (a + c)

האלמנטים המרכיבים את סט A חייבים להיות בינאריים, ובכך להיות בעלי ערכים יקומיים או ריקים.

יישומים

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

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

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

מוצבים

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

סכום (+)

המפעיל OR שהרכיב הלוגי שלו הוא האיחוד (U) מוגדר עבור משתנים בינאריים כדלקמן:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

מוצר (.)

מפעיל ה- AND שהמרכיב הלוגי שלו הוא הצומת (∩) מוגדר עבור משתנים בינאריים כדלקמן:

0. 0 = 0

0. 1 = 0

אחד . 0 = 0

אחד . 1 = 1

ממול (לא)

המפעיל NOT שהרכיב הלוגי שלו הוא השלמה (X) 'מוגדר עבור משתנים בינאריים כדלקמן:

לא 0 = 1

לא 1 = 0

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

משפטים

כלל אפס ואחדות

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

0 + A = A

1 + A = 1

0. A = 0

אחד . א = א

כוחות שווים או חוסר יכולת

פעולות בין משתנים שווים מוגדרים כ:

A + A = A

ל . א = א

השלמה

כל פעולה בין משתנה והשלמה שלו מוגדרת כ:

A + NOT A = 1

ל . לא A = 0

החלטה או שלילה כפולה

כל שלילה כפולה תיחשב כמשתנה הטבעי.

לא (לא א) = א

חִלוּפִי

A + B = B + A; קומיטטיביות של הסכום.

ל . ב = ב. ל ; קומיטטיביות של המוצר.

אסוציאטיבי

A + (B + C) = (A + B) + C = A + B + C; אסוציאטיביות של הסכום.

ל . (B.C) = (A. B). ג = א. ב. ג; אסוציאטיביות למוצרים.

חלוקת

A + (B. C) = (A + B). (A + C); חלוקת הסכום ביחס למוצר.

ל . (B + C) = (A. B) + (A + C); חלוקת המוצר ביחס לסכום.

חוקי קליטה

ישנם חוקי קליטה רבים בין אזכורים מרובים, חלק מהידועים שבהם הם:

ל . (A + B) = A

ל . (לא A + B) = א. ב

NOT A (A + B) = לא A. ב

(A + B). (A + NOT B) = A

א + א. ב = א

א + לא א. B = A + B

לא A + A. B = לא A + B

ל . ב + א. לא B = A

משפט מורגן

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

NOT (A. B) = לא A + NOT B

לא (A + B) = לא A. לא ב

A + B = לא (לא A + לא B)

ל . B = לא (לא A. לא B)

שְׁנִיוּת

כל העמדות והמשפטים מחזיקים בפקולטה לדואליות. פירוש הדבר הוא כי על ידי החלפת המשתנים והפעולות אומדת ההצעה המתקבלת. כלומר, כאשר מחליפים 0 עבור 1 ו- AND עבור OR או להפך; נוצר ביטוי שיהיה תקף לחלוטין.

לדוגמה אם התנוחה נלקחת

אחד . 0 = 0

ודואליות מוחלת

0 + 1 = 1

מתקבל תנוחה אחרת בתוקף לחלוטין.

מפת קארנאגו

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

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

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

דוגמאות

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

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

לא (AB + A + B). לא (A + לא B)

לֹא. לא (A + לא B); פקטורינג A עם גורם משותף.

לֹא. לא (A + לא B); לפי משפט A + 1 = 1.

לא (A + B). לא (A + לא B); מאת משפט א. 1 = א

(לא A. לא B). ;

לפי משפט מורגן לא (A + B) = לא A. לא ב

(לא A. לא B). (לא א. ב); על פי משפט השלילה הכפול NOT (NOT A) = A

לא א. לא ב. לא א. ב; קיבוץ אלגברי.

לא א. לא א. לא ב. ב; קומיטטיביות של מוצר א. ב = ב. ל

לא א. לא ב. ב; מאת משפט א. א = א

לא א. 0; מאת משפט א. לא A = 0

0; מאת משפט א. 0 = 0

ל . ב. C + NOT A + A. לא ב. ג

ל . ג. (B + לא B) + לא A; פקטורינג (A. C) עם גורם משותף.

ל . ג. (1) + לא A; לפי משפט A + NOT A = 1

ל . C + לא A; לפי כלל אפס משפט ואחדות 1. א = א

לא A + C ; על פי חוק מורגן A + NOT A. B = A + B

לצורך פיתרון זה, יש להרחיב את החוק של מורגן כדי להגדיר:

לא (לא א). C + לא A = לא A + C

כי לא (לא A) = A על ידי מעורבות.

פשט את פונקציית ההיגיון

לא א. לא ב. לא C + לא A. לא ב. ג + לא א. לא C עד לביטוי המינימלי שלו

לא א. לא ב. (לא C + C) + לא A. לא ג; פקטורינג (לא A. לא B) עם גורם משותף

לא א. לא ב. (1) + לא א. לא ג; לפי משפט A + NOT A = 1

(לא A. לא B) + (לא A. לא C); לפי כלל אפס משפט ואחדות 1. א = א

לא A (לא B + לא C); פקטורינג לא A עם גורם משותף

לא א. לא (B. C); לפי חוקי מורגן NOT (A. B) = NOT A + NOT B

לא על פי חוקי מורגן לא (א. ב) = לא א + לא ב

כל אחת מארבע האפשרויות המודגשות מייצגת פתרון אפשרי להפחתת רמת המעגל

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

(A. לא B. C + A. לא B. B. D + לא A. לא B). ג

(A. NOT B. C + A. 0. D + NOT A. NOT B). ג; מאת משפט א. לא A = 0

(A. לא B. C + 0 + לא A. לא B). ג; מאת משפט א. 0 = 0

(A. לא B. C + לא A. לא B). ג; לפי משפט A + 0 = A

ל . לא ב. ג. ג + לא א. לא ב. ג; על ידי חלוקת המוצר ביחס לסכום

ל . לא ב. ג + לא א. לא ב. ג; מאת משפט א. א = א

לא ב. C (A + לא A) ; פקטורינג (לא B.C) עם גורם משותף

לא ב. ג (1); לפי משפט A + NOT A = 1

לא ב. ג; לפי כלל אפס משפט ואחדות 1. א = א

הפניות

1. אלגברה בוליאנית ויישומיה ג'יי אלדון וויטסיט. חברת הוצאת קונטיננטל, 1980.
2. מתמטיקה והנדסה במדעי המחשב. כריסטופר ג'. ואן וויק. המכון למדעי המחשב וטכנולוגיה. הלשכה הלאומית לתקנים. וושינגטון די.סי. 20234
3. מתמטיקה למדעי המחשב. אריק להמן. Google Inc.
   F תומסון לייטון המחלקה למתמטיקה ומעבדת מדעי המחשב ומעבדת AI, מכון מסצ'וסטס לטכנולוגיה; אקאמאי טכנולוגיות.
4. אלמנטים של ניתוח מופשט. ד"ר Mícheál O'Searcoid. החוג למתמטיקה. מכללת האוניברסיטה דבלין, בלדפילד, דבלינד.
5. מבוא ללוגיקה ולמתודולוגיה של מדעי הדדוקציה. אלפרד טרסקי, ניו יורק אוקספורד. עיתונות באוניברסיטת אוקספורד.