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

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

לוגיקה בוליאנית הנו ענף מתחום הלוגיקה המתמטית והאלגברה הבוליאנית. ענף זה עוסק בפסוקים אלגבריים בשדה דו ערכי של $'0'\$ ו- $'1'\$ כאשר שני ערכים אלו מיצגים בהתאמה 'שקר' ו-'אמת'. לענף זה שימוש רב בתחשיב פסוקים, באלקטרוניקה ובמדעי המחשב.

תוכן עניינים

1 מבוא
2 היחוד לפונקציה בוליאנית
- 2.1 הוכחת ביטויים באינדוקציה שלמה
3 רשימת פעולות נפוצות
4 פישוט ביטויים בוליאניים- לוגיים
- 4.1 זהויות חשובות
  - 4.1.1 כללי דה-מורגן
- 4.2 מפת קרנו
5 יישומים

[עריכה] מבוא

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

[עריכה] היחוד לפונקציה בוליאנית

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

[עריכה] הוכחת ביטויים באינדוקציה שלמה

ערך מורחב – אינדוקציה מתמטית

למספר הצירופים הסופי השלכה נוספת: בעוד וברב ענפי המתמטיקה האחרים יש להוכיח טענה על ידי הצגת ביטויים המיצגים את כל המצבים האפשריים, דבר שהוא באופן יחסי אבסטרקטי משהו, כאשר מספר המבואות הוא סופי נתן להוכיח טענה בוליאנית-לוגית על ידי אינדוקציה שלמה, קרי- הצבת כל הצירופים האפשריים ובדיקה כי הטענה אכן מתקימת בנוגע אליהם. נוכיח בדרך זו את הזהות הבאה: $A\ \cdot \bar{A} = 0$ .

נציב: $A\ = 1$ :

$1\ \cdot \bar{1} = 0$

נציב: $A\ = 0$ :

$0\ \cdot \bar{0} = 0$

בכך הוכחנו את נכונות הזהות עבור כל $A\$ לוגי כלשהו: '0', '1', או ביטוי בוליאני-לוגי. באופן דומה, נתן להוכיח זהויות גם עבור יותר ממשתנה בוליאני-לוגי אחד.

[עריכה] רשימת פעולות נפוצות

ערך מורחב – פעולה בוליאנית

בנוסף לשלושת הפעילויות הבסיסיות, ישנן עוד מספר פעולות בוליאניות שימושיות נוספות אשר את כולן נתן "לבנות" מן הפעולות הבסיסיות יותר, והן:

כותרת הטבלה: פעולות בוליאניות נוספות
שם הפעולה	סוג הפעולה	סימון הפעולה
NOR	פעולה בינארית	$\overline{A + B}$
NAND	פעולה בינארית	$\overline{A \cdot B}$
XOR	פעולה בינארית	$A\ \oplus B\$
XNOR	פעולה בינארית	$\overline{ A\ \oplus B\ }$
שלילה כפולה	פעולה יונארית	$\overline{\overline{A}} = A\$

נתן להוכיח כי בעזרת כללי דה-מורגן והזהות עבור $\overline{\overline{A}} = A\$ , נתן להרכיב את כל הביטויים הבוליאניים-לוגיים על ידי שימוש ב- NAND לוגי ו- NOR לוגי בלבד.

[עריכה] פישוט ביטויים בוליאניים- לוגיים

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

[עריכה] זהויות חשובות

ישנן מספר זהויות שימושיות בהן נתן לעשות שימוש על מנת לצמצם ולפשט ביטויים לוגיים:

$A\ \cdot \bar{A} = 0$

$A\ + \bar{A} = 1$

$A\ \cdot A\ = A\ + A\ = A\$

$A\ \oplus B\ = A \cdot \bar{B} + \ B \cdot \bar{A}$

$\overline{ A\ \oplus B\ }= \overline{A \cdot \bar{B} + \ B \cdot \bar{A}}= A\ \cdot B\ + \bar{A} \cdot \bar{B}\$

[עריכה] כללי דה-מורגן

ערך מורחב – כללי דה-מורגן

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

$\overline{p + q}=\bar{p}\cdot \bar{q}$

$\overline{p \cdot q}=\bar{p} + \bar{q}$

בעזרת פעולות אלה נתן להמיר כל ביטוי כך שיתבסס על פעולות NAND ו- NOR בלבד על ידי הפעלת שלילה כפולה (שאיננה משנה את ערך הביטוי) על כל הביטוי ושימוש בזהויות אלה עבור אחת מפעולות השלילה.

[עריכה] מפת קרנו

ערך מורחב – מפת קרנו

מפת קרנו

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

[עריכה] יישומים

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

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

מקור: http://he.wikipedia.org../../../%D7%9C/%D7%95/%D7%92/%D7%9C%D7%95%D7%92%D7%99%D7%A7%D7%94_%D7%91%D7%95%D7%9C%D7%99%D7%90%D7%A0%D7%99%D7%AA.html

קטגוריות: לוגיקה בוליאנית | לוגיקה | מתמטיקה | מעגלים ספרתיים