בעולם של היום, אנו משתמשים יותר ויותר במגוון של מכוניות וגאדג'טים. ולא רק כשצריך להפעיל כוח ממש לא אנושי: להזיז את המטען, להרים אותו לגובה, לחפור תעלה ארוכה ועמוקה וכו'. מכוניות כיום מורכבות על ידי רובוטים, אוכל מכינים על ידי רב כיריים, וחישובים אריתמטיים בסיסיים הם מבוצע על ידי מחשבונים. לעתים קרובות יותר ויותר אנו שומעים את הביטוי "אלגברה בוליאנית". אולי הגיע הזמן להבין את תפקיד האדם ביצירת רובוטים ואת היכולת של מכונות לפתור לא רק בעיות מתמטיות, אלא גם לוגיות.
לוגיקה
מתורגמת מיוונית, לוגיקה היא מערכת חשיבה מסודרת היוצרת קשרים בין תנאים נתונים ומאפשרת להסיק מסקנות על סמך הנחות יסוד והנחות. לעתים קרובות אנו שואלים אחד את השני: "האם זה הגיוני?" התשובה שהתקבלה מאששת את הנחותינו או מבקרת את הלך המחשבה. אבל התהליך לא עוצר: אנחנו ממשיכים לחשוב.
לפעמים מספר התנאים (הקדמה) כל כך גדול, והיחסים ביניהם כל כך מורכבים ומורכבים עד שהמוח האנושי לא מסוגל "לעכל" הכל בבת אחת. זה עשוי לקחת יותר מחודש אחד (שבוע, שנה) להבין מה קורה. אבלהחיים המודרניים אינם נותנים לנו מרווחי זמן כאלה לקבלת החלטות. ואנחנו נעזרים במחשבים. וכאן מופיעה האלגברה של ההיגיון, עם חוקים ותכונות משלה. על ידי הורדת כל הנתונים הראשוניים, אנו מאפשרים למחשב לזהות את כל הקשרים, לבטל סתירות ולמצוא פתרון מספק.
מתמטיקה והיגיון
גוטפריד וילהלם לייבניץ המפורסם ניסח את המושג "לוגיקה מתמטית", שבעיותיו היו מובנות רק למעגל מצומצם של מדענים. כיוון זה לא עורר עניין מיוחד, ועד אמצע המאה ה-19, מעט אנשים ידעו על לוגיקה מתמטית.
התעניינות רבה בקהילה המדעית גרמה למחלוקת שבה הכריז האנגלי ג'ורג' בול על כוונתו ליצור ענף של מתמטיקה שאין לו יישום מעשי לחלוטין. כזכור מההיסטוריה, הייצור התעשייתי התפתח באותה תקופה באופן פעיל, כל מיני מכונות עזר וכלי מכונות פותחו, כלומר, לכל התגליות המדעיות היה מיקוד מעשי.
במבט קדימה, נניח שהאלגברה הבוליאנית היא החלק הנפוץ ביותר במתמטיקה בעולם המודרני. אז בול איבד את הטיעון שלו.
ג'ורג' בוהל
עצם אישיותו של המחבר ראויה לתשומת לב מיוחדת. גם בהתחשב בכך שבעבר אנשים גדלו לפנינו, עדיין אי אפשר שלא לציין שבגיל 16, ג'יי בוהל לימד בבית ספר בכפר, ועד גיל 20 הוא פתח בית ספר משלו בלינקולן. המתמטיקאי שלט בחמש שפות זרות, ובזמנו הפנוי קרא יצירותניוטון ולגרנז'. וכל זה על בנו של פועל פשוט!
בשנת 1839 הגיש בולה לראשונה את מאמריו המדעיים ל-Cambridge Mathematical Journal. המדען בן 24. עבודתו של בולה כל כך עניינה את חברי החברה המלכותית שבשנת 1844 הוא קיבל מדליה על תרומתו לפיתוח הניתוח המתמטי. עוד כמה יצירות שפורסמו, שתיארו את מרכיבי ההיגיון המתמטי, אפשרו למתמטיקאי הצעיר לקחת את תפקיד הפרופסור בקורק קאונטי קולג'. נזכיר שלבוהל עצמו לא היה השכלה.
Idea
באופן עקרוני, האלגברה הבוליאנית פשוטה מאוד. ישנן הצהרות (ביטויים לוגיים) שמבחינת המתמטיקה ניתן להגדיר רק בשתי מילים: "נכון" או "שקר". למשל, באביב העצים פורחים - נכון, בקיץ יורד שלג - שקר. היופי במתמטיקה הזו הוא שאין צורך קפדני להשתמש רק במספרים. כל אמירה בעלת משמעות חד משמעית מתאימה למדי לאלגברה של שיפוטים.
לכן, ניתן להשתמש באלגברה של הלוגיקה ממש בכל מקום: בתזמון וכתיבת הוראות, ניתוח מידע סותר על אירועים וקביעת רצף הפעולות. הדבר החשוב ביותר הוא להבין שזה לגמרי לא חשוב איך אנחנו קובעים את האמת או השקר של האמירה. ה"איך" וה"למה" הללו צריכים להיות מופשטים. רק הצהרת עובדה חשובה: נכון-לא נכון.
כמובן, לתכנות חשובות הפונקציות של האלגברה של הלוגיקה, שנכתבות על ידי התואםסימנים וסמלים. וללמוד אותם פירושו לשלוט בשפה זרה חדשה. שום דבר אינו בלתי אפשרי.
מושגים והגדרות בסיסיות
מבלי להיכנס לעומק, בואו נעסוק בטרמינולוגיה. אז אלגברה בוליאנית מניחה:
- statements;
- פעולות לוגיות;
- פונקציות וחוקים.
הצהרות הן כל ביטוי חיובי שלא ניתן לפרש בצורה מעורפלת. הם כתובים כמספרים (5 > 3) או מנוסחים במילים מוכרות (פיל הוא היונק הגדול ביותר). יחד עם זאת, גם לביטוי "לג'ירפה אין צוואר" יש זכות קיום, רק אלגברה בוליאנית תגדיר אותו כ"שקר".
כל ההצהרות חייבות להיות חד-משמעיות, אבל הן יכולות להיות יסודיות ומורכבות. האחרונים משתמשים בחיבורים לוגיים. כלומר, באלגברה של שיפוטים, הצהרות מורכבות נוצרות על ידי הוספת הצהרות אלמנטריות באמצעות פעולות לוגיות.
פעולות אלגברה בוליאנית
אנחנו כבר זוכרים שפעולות באלגברה של שיפוטים הן הגיוניות. בדיוק כפי שאלגברת מספרים משתמשת בחשבון כדי להוסיף, להחסיר או להשוות מספרים, אלמנטים של לוגיקה מתמטית מאפשרים לך לעשות הצהרות מורכבות, לשלול או לחשב את התוצאה הסופית.
פעולות לוגיות לפורמליזציה ופשטות נכתבות על ידי נוסחאות המוכרות לנו בחשבון. תכונות האלגברה הבוליאנית מאפשרות לכתוב משוואות ולחשב לא ידועים. פעולות לוגיות נכתבות בדרך כלל באמצעות טבלת אמת. העמודים שלומגדירים את מרכיבי החישוב ואת הפעולה המתבצעת עליהם, והקווים מציגים את תוצאת החישוב.
פעולות לוגיות בסיסיות
הפעולות הנפוצות ביותר באלגברה בוליאנית הן שלילה (NOT) ו-AND ו-OR לוגיות. ניתן לתאר כך כמעט את כל הפעולות באלגברה של שיפוטים. בואו נלמד כל אחת משלוש הפעולות ביתר פירוט.
שלילה (לא) חלה רק על אלמנט אחד (אופרנד). לכן פעולת השלילה נקראת unary. כדי לכתוב את המושג "לא A" השתמש בסמלים הבאים: ¬A, A¯¯ או !A. בצורת טבלה זה נראה כך:
פונקציית השלילה מאופיינת במשפט הבא: אם A נכון, אז B הוא שקר. לדוגמה, הירח סובב סביב כדור הארץ - נכון; כדור הארץ מסתובב סביב הירח - שקר.
כפל וחיבור לוגי
ה-AND הלוגי נקרא פעולת הצירוף. מה זה אומר? ראשית, שניתן להחיל אותה על שני אופרנדים, כלומר, והיא פעולה בינארית. שנית, שרק במקרה של האמת של שני האופרנדים (גם א' וגם ב') הביטוי עצמו נכון. הפתגם "סבלנות ועבודה יטחנו הכל" מציע שרק שני הגורמים יעזרו לאדם להתמודד עם קשיים.
סמלים המשמשים לכתיבה: A∧B, A⋅B או A&&B.
צירוף דומה לכפל בחשבון. לפעמים אומרים את זה - כפל לוגי. אם נכפיל את מרכיבי הטבלה שורה אחר שורה, נקבל תוצאה הדומה להיגיון לוגי.
Disjunction היא פעולת OR הגיונית. זה לוקח את הערך של האמתכאשר לפחות אחת מהמשפטים נכונה (או A או B). כתוב כך: A∨B, A+B או A||B. טבלאות האמת לפעולות אלו הן:
ניתוק הוא כמו חיבור אריתמטי. לפעולת החיבור הלוגית יש מגבלה אחת בלבד: 1+1=1. אבל אנחנו זוכרים שבפורמט דיגיטלי, הלוגיקה המתמטית מוגבלת ל-0 ו-1 (כאשר 1 נכון, 0 הוא שקר). לדוגמה, האמירה "במוזיאון אתה יכול לראות יצירת מופת או לפגוש בן שיח מעניין" פירושה שאתה יכול לראות יצירות אמנות, או שאתה יכול לפגוש אדם מעניין. יחד עם זאת, לא נשללת האפשרות ששני האירועים יתרחשו בו-זמנית.
פונקציות וחוקים
אז, אנחנו כבר יודעים באילו פעולות לוגיות משתמשת האלגברה הבוליאנית. פונקציות מתארות את כל המאפיינים של אלמנטים של לוגיקה מתמטית ומאפשרות לך לפשט תנאים מורכבים מורכבים של בעיות. נראה שהמאפיין המובן והפשוט ביותר הוא דחיית פעולות נגזרות. הנגזרות הן OR בלעדי, השלכה ושקילות. מכיוון שלמדנו רק את הפעולות הבסיסיות, נשקול גם את המאפיינים רק שלהן.
אסוציאטיביות פירושה שבהצהרות כמו "ו-A, ו-B, ו-C", סדר האופרנדים אינו משנה. הנוסחה כתובה כך:
(A∧B)∧V=A∧(B∧V)=A∧B∧V, (A∨B)∨C=A∨(B∨C)=A∨B∨C.
כפי שאתה יכול לראות, זה מאפיין לא רק לצירוף, אלא גם לניתוק.
קומוטטיביות קובעת שהתוצאהצירוף או ניתוק אינם תלויים באיזה רכיב נחשב ראשון:
A∧B=B∧A; A∨B=B∨A.
Distributivity מאפשר הרחבת סוגריים בביטויים לוגיים מורכבים. הכללים דומים לסוגריים פותחים בכפל ובחיבור באלגברה:
A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
המאפיינים של אחד ואפס, שיכולים להיות אחד מהאופרנדים, דומים גם לכפל אלגברי באפס או באחד וחיבור עם אחד:
A∧0=0, A∧1=A; A∨0=A, A∨1=1.
Idempotency אומר לנו שאם, ביחס לשני אופרנדים שווים, התוצאה של פעולה מתבררת כדומה, אז נוכל "לזרוק" את האופרנדים הנוספים שמסבכים את מהלך ההיגיון. הן הצירוף והן הניתוק הן פעולות אימפוטנטיות.
B∧B=B; B∨B=B.
ספיגה מאפשרת לנו גם לפשט משוואות. ספיגה קובעת שכאשר מופעלת פעולה נוספת עם אותו אלמנט על ביטוי עם אופרנד אחד, התוצאה היא האופרנד מפעולת הקליטה.
A∧B∨B=B; (A∨B)∧B=B.
רצף פעולות
לרצף הפעולות יש חשיבות לא קטנה. למעשה, באשר לאלגברה, ישנה עדיפות של פונקציות שבהן משתמשת האלגברה הבוליאנית. ניתן לפשט נוסחאות רק אם נבחנת המשמעות של הפעולות. בדירוג מהמשמעותי ביותר לפחות, נקבל את הרצף הבא:
1. הכחשה.
2. צירוף.
3. ניתוק, בלעדיאו.
4. משמעות, שקילות.
כפי שאתה יכול לראות, רק לשלילה ולצירוף אין עדיפות שווה. והעדיפות של ניתוק ו-XOR שווים, כמו גם סדרי העדיפויות של השלכה ושקילות.
פונקציות השלכה ושקילות
כפי שכבר אמרנו, בנוסף לפעולות הלוגיות הבסיסיות, לוגיקה מתמטית ותורת האלגוריתמים משתמשות בנגזרות. השימושים הנפוצים ביותר הם השלכה ושקילות.
השלכה, או תוצאה לוגית, היא אמירה שבה פעולה אחת היא תנאי, והשנייה היא תוצאה של יישומו. במילים אחרות, זהו משפט עם מילות יחס "אם…אז". "אם אתה אוהב לרכוב, אוהב לשאת מזחלות." כלומר, עבור סקי, אתה צריך להדק את המזחלת במעלה הגבעה. אם אין רצון לזוז במורד ההר, אז אתה לא צריך לשאת את המזחלת. כתוב כך: A→B או A⇒B.
מקביליות מניחה שהפעולה המתקבלת מתרחשת רק כאשר שני האופרנדים נכונים. לדוגמה, הלילה הופך ליום כאשר (ורק כאשר) השמש זורחת מעל האופק. בשפת הלוגיקה המתמטית, משפט זה כתוב כך: A≡B, A⇔B, A==B.
חוקים אחרים של האלגברה הבוליאנית
אלגברה של שיפוטים מתפתחת, ומדענים מתעניינים רבים ניסחו חוקים חדשים. ההנחות של המתמטיקאי הסקוטי או דה מורגן נחשבות המפורסמות ביותר. הוא הבחין והגדיר מאפיינים כמו שלילה קרובה, השלמה ושלילה כפולה.
שלילה קרובה פירושה שאין שלילה לפני הסוגריים:לא (A או B)=לא A או NOT B.
כאשר אופרנד נשלל, ללא קשר לערכו, מדברים על משלים:
B∧¬B=0; B∨¬B=1.
ולבסוף, השלילה הכפולה מפצה על עצמה. הָהֵן. או שהשלילה נעלמת לפני האופרנד, או שרק אחד נשאר.
איך לפתור מבחנים
היגיון מתמטי מרמז על פישוט של משוואות נתונות. בדיוק כמו באלגברה, תחילה עליך להפוך את התנאי לקל ככל האפשר (להיפטר איתם מתשומות ופעולות מורכבות), ולאחר מכן להתחיל לחפש את התשובה הנכונה.
מה אפשר לעשות כדי לפשט? המר את כל הפעולות הנגזרות לפשוטות. לאחר מכן פתחו את כל הסוגריים (או להיפך, הוציאו אותו מהסוגריים כדי לקצר את האלמנט הזה). השלב הבא צריך להיות ליישם את המאפיינים של האלגברה הבוליאנית בפועל (קליטה, מאפיינים של אפס ואחד וכו').
בסופו של דבר, המשוואה צריכה להיות מורכבת ממספר המינימום של לא ידועים בשילוב פעולות פשוטות. הדרך הקלה ביותר למצוא פתרון היא להשיג מספר רב של שליליים קרובים. אז התשובה תצוץ כאילו מעצמה.
