אלגוריתם לבניית טבלאות אמת של ביטויים לוגיים

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

אלגברה בוליאנית

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

אלגברה של לוגיקה מבוססת על כמה אקסיומות פשוטה יחסית:

• אסוציאטיבי;
• היא קומוטטיבית;
• קליטה;
• distributivity;
• פוטנציאל הוספה.

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

כללי עריכת השולחן

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

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

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

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

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

הבא, אתה צריך למלא את המכסה של השולחן שלנו. בהמשך לראות דוגמה לכך.

עכשיו להמשיך את המילוי של צירופים אפשריים. עבור שני משתנים, הם כדלקמן: 00, 01, 10, 11. במשך שלושה משתנים: 000, 001, 010, 011, 100, 101, 110, 111.

אחרי הכל את הפריטים הנ"ל יכולים להמשיך החישוב של התאים הנותרים ומילוי בטבלה וכתוצאה מכך.

לדוגמה

כעת נבחנו את הדוגמא של בניית שולחן של הביטוי הלוגי היא נכונה: ההיפוך של A + B * א

1. רוזן משתנה: 2. מספר הקווים: 4 + 1 = 5.
2. הצו מביצוע פעולות: ההיפוך הראשון, בשיתוף שני, ניתק שלישי.
3. מספר עמודות: 3 + 2 = 5.
4. קבלת עקיבה ומילוי שולחן.

ככלל, את העבודה נשמעת ככה: "כמה שילובים עונים F = 0" או "במה שילובי F = 1". על השאלה הראשונה התשובה - 1, השנייה - 00, 01, 11.

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

• הכחשה;
• כפל;
• בנוסף.

משימה

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

מתוך ארבעה ערכים של A: 1), 7 2) 6, 3), 5, 4) 4. חלקם ההצהרה "היפוך (יותר קטן 6) + (פחות מ 5 א)" היא שקרית?

הטור הראשון שלנו יהיה מלא ערכים 7, 6, 5, 4 נדרשו ברצף הזה. בעמודה הבאה, עלינו לענות על השאלה: "? ופחות מ 6" העמודה השלישית למלא אותו, רק עכשיו את התשובה לשאלה: "? ופחות מ 5"

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

שים לב: יש לנו מספרים של תגובות, ביטוי שקרי הוא ערך של A = 5, זו היא הגרסה השלישית של התשובה.