חוקי המגע של מעגל אלגברה, אלגברה בוליאנית

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

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

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

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

אלגברה בוליאנית מציגה:

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

2) פעולות לוגיות בסיסיות:

• חיבור לוגי (או ניתוק, לוגי OR, מסומן בסימן ?), המוגדר כך: התוצאה של הפעולה היא 0 אם ורק אם כל הארגומנטים של הפעולה שווים ל-0, אחרת התוצאה היא 1;

• כפל לוגי (או שרשור, לוגי AND, מסומן ב-?, או לא מצוין בכלל) המוגדר כך: התוצאה של הפעולה היא 1 אם ורק אם כל הארגומנטים של הפעולה שווים ל-1, אחרת התוצאה הוא 0;

• שלילה (או להיפך, לא לוגי, מסומן בפס מעל הארגומנט), המוגדר באופן הבא: לתוצאה של הפעולה יש ערך הפוך מהארגומנט;

3) אקסיומות (חוקי האלגברה הבוליאנית), המגדירים את הכללים להמרת ביטויים לוגיים.

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

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

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

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

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

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

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

טבלה 1 מציגה את הייעודים הגרפיים הקונבנציונליים של כמה אלמנטים לוגיים בהתאם ל-GOST 2.743-91, כמו גם את עמיתיהם הזרים.

בנוסף לאלמנטים שמבצעים את שלוש הפעולות של האלגברה הבוליאנית (AND, OR, NOT), ב-tab. 1 מציג את האלמנטים המבצעים פעולות הנגזרות מהעיקר:

— AND -NOT — שלילה של כפל לוגי, הנקרא גם מהלך שייפר (מסומן על ידי |)

- OR -NOT - שלילה של משלים לוגי, הנקרא גם החץ של פירס (מסומן ב-?)

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

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

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

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

חוקי נסיעות

כדי להוסיף: x + y = y + x

הסכמטיקה התואמת לביטויים אלה מוצגת באיור. 1, א.

המעגלים השמאלי והימני הם בדרך כלל מעגלים פתוחים, שכל אחד מהם נסגר כאשר אחד האלמנטים (X או Y) מופעל, כלומר, מעגלים אלו שווים. לכפל: x ·y = y ·NS.

הסכמטיקה התואמת לביטויים אלה מוצגת באיור. 1b, גם השקילותם ברורה.

אורז. 1

חוקי השילוב

לחיבור: (x + y) + z = x + (y + z)

לכפל: (x ·y) ·z = x ·(y ·z)

זוגות המעגלים השווים המתאימים לביטויים אלה מוצגים באיור. 2, א, ב

אורז. 2

חוקי הפצה

כפל מול חיבור: (x + y) +z = x + (y + z)

חיבור מול כפל. x ·y + z = (x + z) ·(y + z)

הסכמטיקה התואמת לביטויים אלה מוצגת באיור. 3, א, ב.

אורז. 3.

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

חוקי היפוך

בתוספת: NS + c = NS·c

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

אורז. 4.

הדיאגרמה השמאלית מתאימה לביטוי x + y, והימנית ל-NS ·c

שני המעגלים הללו מנוגדים זה לזה בפעולה, כלומר: אם המעגל השמאלי עם אלמנטים X שאינם נרגשים, Y הוא מעגל פתוח, אז המעגל הימני סגור. אם במעגל השמאלי, כאשר אחד האלמנטים מופעל, המעגל נסגר, ובמעגל הימני, להיפך, הוא נפתח.

מכיוון שלפי ההגדרה של סימן שלילי, הפונקציה x + y היא היפוך של הפונקציה x + y, אז ברור ש-x + y = NS·in.

לגבי כפל: NS · c = NS + c

התוכניות המתאימות מוצגות באיור. 4, ב.

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