חזור לתיקייה: 00440252 - מערכות ספרתיות ומבנה המחשב

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

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • כללי
  • זהויות מיתוג
  • עקרון הדואליות
  • זהויות מיתוג בסיסיות
  • דה מורגן
  • דה-מורגן המוכלל
  • סיכום הזהויות
  • פונקציות מיתוג
  • צורות ייצוג לפונקציות
  • ביטוי מיתוג
  • צורות קנוניות
  • הקשרים בין הצורות הקנוניות השונות
  • העברת ביטוי מיתוג לצורה קנונית מבלי טבלת אמת
  • צורות ייצוג לפונקציות
  • משפט הפיתוח של Shannon-Bool
  • הפונקציה XOR
  • ביטוי מינימלי של פונקציה
  • מערכת פעולות שלמה
  • מערכת פעולות חצי-שלמה
  • מפת קרנו
  • צמצום פונקציות בעזרת מפת קרנו
  • צירופי ברירה - Don't Care

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

00440252

מערכות ספרתיות ומבנה המחשב

רשימות הרצאה לקריאה בשבת

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

הופק מתוך תקיית התואר של שקד

uni-folder.vercel.app

אלגברת מיתוג(או אלגברה בוליאנית) הוא תחום באלגברה המשתמש בערכי משתנים של אמת(1) ושקר(0) עליהם אנחנו יכולים לבצע כמה פעולות.
הפעולות שאנו יכולים לבצע הן:

OR(+,∣)AND(⋅,&)NOT(′,‾)0+0=00⋅0=00′=10+1=10⋅1=01′=01+0=11⋅0=01+1=11⋅1=1\begin{array}{|c|c|c|} \hline OR(+,|) & AND(\cdot,\&) & NOT(',\overline{}) \\ \hline 0+0=0 & 0\cdot 0=0 & 0'=1 \\ \hline 0+1=1 & 0\cdot 1=0 & 1'=0 \\ \hline 1+0=1 & 1\cdot 0=0 \\ \hline 1+1=1 & 1\cdot 1=1 \\ \hline \end{array}OR(+,∣)0+0=00+1=11+0=11+1=1​AND(⋅,&)0⋅0=00⋅1=01⋅0=01⋅1=1​NOT(′,)0′=11′=0​​

כל פעולה כזו מיוצגת על ידי שער לוגי:

הגדרה 1 (קבועי מיתוג)

כל אחד משני הערכים 000 ו-111.

הגדרה 2 (משתנה מיתוג)

משתנה שיכול לקבל אחד משני הערכים 000 או 111 כאשר x≠0  ⟺  x=1x\neq0\iff x=1x=0⟺x=1 ו-x≠1  ⟺  x=0x\neq1\iff x=0x=1⟺x=0.

הגדרה 3 (ביטוי מיתוג)

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

  • כל משתנה מיתוג או קבוע מיתוג הינו ביטוי מיתוג
  • אם T1,T2T_{1},T_{2}T1​,T2​ הינם ביטויי מיתוג, כך גם T1+T2,T1⋅T2,(T1)′T_{1}+T_{2},T_{1}\cdot T_{2},(T_{1})'T1​+T2​,T1​⋅T2​,(T1​)′.
  • צירוף סימנים שאינו מתגבל כך איננו ביטוי מיתוג.
דוגמה

נניח הביטוי x+y⋅z⋅yx+y\cdot z\cdot yx+y⋅z⋅y יראה כך:

סדר הפעולות:

  • לפני הסוגריים
  • בהעדר סוגריים:
    1. קדימות ראשונה: שלילה NOTNOTNOT
    2. קדימות שניה: ANDANDAND
    3. קדימות שלישית: OROROR
הגדרה 4

ערך (האמת) של ביטוי מיתוג TTT תחת השמת ערכי אמת (אמיתי או שקרי) הערך שמקבל הביטוי כאשר מציבים לכל משתנה מיתוג בו את ערך האמת שלו בהשמה.

דוגמה

A′+C+B′C+AC′A'+C+B'C+AC'A′+C+B′C+AC′

נחשב את הביטוי הנתון כאשר A=0,B=0,C=1A=0,B=0,C=1A=0,B=0,C=1.

הגדרה 5 (זהות מיתוג)

יהיו T1,T2T_{1},T_{2}T1​,T2​ ביטויי מיתוג. השוויון T1=T2T_{1}=T_{2}T1​=T2​ הינו זהות מיתוג אם תחת כל השמה מקבלים T1,T2T_{1},T_{2}T1​,T2​ ערכים שווים.

דוגמה

זהויות:

  • x=xx=xx=x
  • x⋅y=y⋅xx\cdot y=y\cdot xx⋅y=y⋅x

לא זהוית:

  • x=yx=yx=y
  • x⋅y=y+xx\cdot y=y+xx⋅y=y+x

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

הערה

בזהות מיתוג ניתן להחליף כל משתנה בביטוי מיתוג.
למשל נחליף את xxx ב-(w+zq)(w+zq)(w+zq) כך

xy=yx  ⟹  (w+zq)y=y(w+zq)xy=yx \implies (w+zq)y=y(w+zq)xy=yx⟹(w+zq)y=y(w+zq)

זהויות מיתוג

עקרון הדואליות

בכל זהות, אם נחליף AND↔ORAND\leftrightarrow ORAND↔OR נבצע גם 1↔01\leftrightarrow01↔0 נקבל זהות חדשה דואלית.

משפט (עקרון הדואליות)

אם מתקיימת הזהות:

P(x,y,…,0,1,AND,OR,NOT)=Q(x,y,…,0,1,AND,OR,NOT)P(x,y,\dots,0,1,AND,OR,NOT)=Q(x,y,\dots,0,1,AND,OR,NOT)P(x,y,…,0,1,AND,OR,NOT)=Q(x,y,…,0,1,AND,OR,NOT)

אזי מתקיימת גם הזהות:

P(x,y,…,1,0,OR,AND,NOT)=Q(x,y,…,1,0,OR,AND,NOT)P(x,y,\dots,1,0,OR,AND,NOT)=Q(x,y,\dots,1,0,OR,AND,NOT)P(x,y,…,1,0,OR,AND,NOT)=Q(x,y,…,1,0,OR,AND,NOT)
מסקנה

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

זהויות מיתוג בסיסיות

משפט (הזהויות הבסיסיות)

  1. אדישות: x+x=xx⋅x=x\begin{matrix}x+x=x \\ x\cdot x=x\end{matrix}x+x=xx⋅x=x​
  2. ערכים אדישים ושולטים:
  • 1 שולט ב-OROROR. כלומר: x+1=1x+1=1x+1=1.
  • 0 שולט ב-ANDANDAND, כלומר: x⋅0=0x\cdot 0=0x⋅0=0.
  • 000 אדיש ב-OROROR. כלומר, x+0=xx+0=xx+0=x.
  • 111 אדיש ב-ANDANDAND. כלומר: x⋅1=xx\cdot 1=xx⋅1=x.
  1. חילוף (קומוטטיביות): x+y=y+xx⋅y=y⋅x\begin{matrix}x+y=y+x \\ x\cdot y=y\cdot x\end{matrix}x+y=y+xx⋅y=y⋅x​
  2. קיבוץ (אסוציטיביות): (x+y)+z=x+(y+z)(x⋅y)⋅z=x⋅(y⋅z)\begin{matrix}(x+y)+z=x+(y+z)\\(x\cdot y)\cdot z=x\cdot(y\cdot z)\end{matrix}(x+y)+z=x+(y+z)(x⋅y)⋅z=x⋅(y⋅z)​
  3. השלמה: x+x′=1x⋅x′=0\begin{matrix}x+x'=1\\x\cdot x'=0\end{matrix}x+x′=1x⋅x′=0​

הוכחה: (1)

0+0=0,  1+1=1,  0⋅0=0,  1⋅1=10+0=0,\; 1+1=1,\;0\cdot0=0,\;1\cdot1=10+0=0,1+1=1,0⋅0=0,1⋅1=1

אין עוד אפשרויות ולכן זה מתקיים.
∎

הערה

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

משפט (6 - פילוג (דיסטריבודיטיביות))

כמו באלגברה רגילה מתקיים: x(y+z)=xy+xzx(y+z)=xy+xzx(y+z)=xy+xz.
אך בניגוד לאלגברה רגילה:

x+(y⋅z)=(x+y)⋅(x+z)x+(y\cdot z)=(x+y)\cdot(x+z)x+(y⋅z)=(x+y)⋅(x+z)
הערה

זה הדבר היחיד שאינו טריוויאלי פה ולכן חשוב לזכור אותו.

הערה

ניתן להוכיח באינדוקציה שלמה אך לא הספקתי לכתוב את זה.

משפט (הזהויות הבסיסיות חלק ב')

7. חוק הבליעה: x+xy=xx(x+y)=x\begin{matrix}x+xy=x \\ x(x+y)=x\end{matrix}x+xy=xx(x+y)=x​ ובנוסף מתקיים גם x+x′y=x+yx(x′+y)=xy\begin{matrix}x+x'y=x+y\\ x(x'+y)=xy\end{matrix}x+x′y=x+yx(x′+y)=xy​.
8. חוק ההסכמה: xy+x′z+yz=xy+x′zxy+x'z+yz=xy+x'zxy+x′z+yz=xy+x′z.

הוכחת (7) תעשה באמצעות אינדוקציה שלמה וגם על מסך זהויות קודמות:

x+xy=x⋅1+xy=x(1+y)=xx+xy=x\cdot1+xy=x(1+y)=xx+xy=x⋅1+xy=x(1+y)=x x(x+y)=(x+0)(x+y)=x+0⋅y=xx(x+y)=(x+0)(x+y)=x+0\cdot y=xx(x+y)=(x+0)(x+y)=x+0⋅y=x x+x′y=(x+x′)⋅(x+y)=1⋅(x+y)=x+yx+x'y=(x+x')\cdot(x+y)=1\cdot(x+y)=x+yx+x′y=(x+x′)⋅(x+y)=1⋅(x+y)=x+y x(x′+y)=xx′+xy=0+xy=xyx(x'+y)=xx'+xy=0+xy=xyx(x′+y)=xx′+xy=0+xy=xy

∎

הוכחה (8):

xy+x′z+yz=  xy+x′z+yz⋅1לפי ערכים אדישים=  xy+x′z+yz(x+x′)לפי השלמה=  xy+x′z+yzx+yzx′לפי פילוג=  xy+x′zלפי בליעה פעמיים\begin{align*} & xy+x'z+yz \\ =\; & xy+x'z+yz\cdot 1 & \R{\text{לפי ערכים אדישים}} \\ =\; & xy+x'z+yz(x+x') & \R{\text{לפי השלמה}} \\ =\; & xy+x'z+yzx+yzx' & \R{\text{לפי פילוג}} \\ =\; & xy+x'z & \R{\text{לפי בליעה פעמיים}} \end{align*}====​xy+x′z+yzxy+x′z+yz⋅1xy+x′z+yz(x+x′)xy+x′z+yzx+yzx′xy+x′z​לפי ערכים אדישיםלפי השלמהלפי פילוגלפי בליעה פעמיים​

∎

הערה (על צמצום)

אין באלגברת מיתוג פעולות הופכיות ל-AND/ORAND/ORAND/OR. בכך אסור לצמצם!
למשל, עבור A+B=A+CA+B=A+CA+B=A+C לא מתקיים B=CB=CB=C.
נסתכל על דוגמה נגדית בדמות A=1,B=0,C=1A=1,B=0,C=1A=1,B=0,C=1 ואז 1+0=1+11+0=1+11+0=1+1 לא גורר 0=10=10=1.

דה מורגן

משפט (היפוך עצמי)

(x′)′=x(x')'=x(x′)′=x
משפט (חוקי דה-מורגן)

(x+y)′=x′⋅y′(x+y)'=x'\cdot y'(x+y)′=x′⋅y′ (xy)′=x′+y′(xy)'=x'+y'(xy)′=x′+y′

ההוכחה נעשית באמצעות אינודקציה שלמה כך:

xyx′y′x+y(x+y)′x′y′0011011011010010011001100100\begin{array}{|c|c|c|c|c|c|c|} \hline x & y & x' & y' & x+y & (x+y)' & x'y' \\ \hline 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ \hline \end{array}x0011​y0101​x′1100​y′1010​x+y0111​(x+y)′1000​x′y′1000​​
דוגמה

(x+y′z)′=(x+(y′z))′=x′(y′z)′=x′((y′)z)′=x′((y′)′+z′)=x′(y+z′)(x+y'z)'=(x+(y'z))'=x'(y'z)'=x'((y')z)'=x'((y')'+z')=x'(y+z')(x+y′z)′=(x+(y′z))′=x′(y′z)′=x′((y′)z)′=x′((y′)′+z′)=x′(y+z′)

דה-מורגן המוכלל

P(x,y,…,0,1,AND,OR)′=P(x′,y′,…,1,0,OR,AND)\boxed{P(x,y,\dots,0,1,AND,OR)'=P(x',y',\dots,1,0,OR,AND)}P(x,y,…,0,1,AND,OR)′=P(x′,y′,…,1,0,OR,AND)​

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

דוגמה

(x′+y+z)′=(x′)′y′z′=xy′z′(x'+y+z)'=(x')'y'z'=xy'z'(x′+y+z)′=(x′)′y′z′=xy′z′
הערה

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

סיכום הזהויות

x+x=xx⋅x=xאדישות.1x+0=xx+1=1x⋅0=0x⋅1=xערכים אדישים.2ושולטיםx+y=y+xx⋅y=y⋅xחילוף.3(x+y)+z=x+(y+z)(x⋅y)z=x(y⋅z)קיבוץ.4x+x′=1x⋅x′=0השלמה.5x(y+z)=xy+xzx+(y⋅z)=(x+y)(x+z)פילוג.6x(x+y)=xx+xy=xבליעה(ראשון).7x(x′+y)=xyx+x′y=x+yבליעה(שני).8xy+x′z+yz=xy+x′zקונצנזוס.9(x′)′=xהיפוך עצמי.10(x+y)′=x′⋅y′(xy)′=x′+y′דה-מורגן.11\begin{array}{|c|c|c|} \hline x+x=x & x\cdot x=x & \R{\text{אדישות}}.1 \\ \hline \begin{matrix} x+0=x \\ x+1=1 \end{matrix} & \begin{matrix} x\cdot 0=0 \\ x\cdot 1=x \end{matrix} & \begin{matrix} \R{\text{ערכים אדישים}}.2 \\ \R{\text{ושולטים}} \end{matrix} \\ \hline x+y=y+x & x\cdot y=y\cdot x & \R{\text{חילוף}}.3 \\ \hline (x+y)+z=x+(y+z) & (x\cdot y)z=x(y\cdot z) & \R{\text{קיבוץ}}.4 \\ \hline x+x'=1 & x\cdot x'=0 & \R{\text{השלמה}}.5 \\ \hline x(y+z)=xy+xz & \colorbox{orange}{$x+(y\cdot z)=(x+y)(x+z)$} & \R{\text{פילוג}}.6 \\ \hline x(x+y)=x & x+xy=x & \R{\text{בליעה(ראשון)}}.7 \\ \hline x(x'+y)=xy & \colorbox{orange}{$x+x'y=x+y$} & \R{\text{בליעה(שני)}}.8 \\ \hline & xy+x'z+yz=xy+x'z & \R{\text{קונצנזוס}}.9 \\ \hline & (x')'=x & \R{\text{היפוך עצמי}}.10 \\ \hline (x+y)'=x'\cdot y' & (xy)'=x'+y' & \R{\text{דה-מורגן}}.11 \\ \hline \end{array}x+x=xx+0=xx+1=1​x+y=y+x(x+y)+z=x+(y+z)x+x′=1x(y+z)=xy+xzx(x+y)=xx(x′+y)=xy(x+y)′=x′⋅y′​x⋅x=xx⋅0=0x⋅1=x​x⋅y=y⋅x(x⋅y)z=x(y⋅z)x⋅x′=0x+(y⋅z)=(x+y)(x+z)​x+xy=xx+x′y=x+y​xy+x′z+yz=xy+x′z(x′)′=x(xy)′=x′+y′​אדישות.1ערכים אדישים.2ושולטים​חילוף.3קיבוץ.4השלמה.5פילוג.6בליעה(ראשון).7בליעה(שני).8קונצנזוס.9היפוך עצמי.10דה-מורגן.11​​
דוגמה

(x+y)[x′(y′+z′)]′+x′y′+x′z′=(x+y)(x+yz)+x′y′+x′z′ מוכלל11+10=x+yz+x′y′+x′z′6+1=x+y′+z′+y8שלוש פעמים =12+5\begin{align*} &(x+y)[x'(y'+z')]'+x'y'+x'z' \\ =&(x+y)(x+yz)+x'y'+x'z' & \R{\text{ מוכלל}}11+10 \\ =&x+yz+x'y'+x'z' & 6+1 \\ =&x+y'+z'+y & 8 \R{\text{שלוש פעמים }} \\ =&1 & 2+5 \end{align*}====​(x+y)[x′(y′+z′)]′+x′y′+x′z′(x+y)(x+yz)+x′y′+x′z′x+yz+x′y′+x′z′x+y′+z′+y1​ מוכלל11+106+18שלוש פעמים 2+5​
דוגמה

בשימוש בדה מורגן המוכלל:

[(x+y)′z′]′=(x′y′)′+z=x+y+z[(x+y)'z']'=(x'y')'+z=x+y+z[(x+y)′z′]′=(x′y′)′+z=x+y+z

בשימוש בדה מורגן הבסיסי(נתייחס ל-x+yx+yx+y כביטוי אחד ולא משהו מורכב):

[(x+y)′z′]′=(x+y)+z[(x+y)'z']'=(x+y)+z[(x+y)′z′]′=(x+y)+z

פונקציות מיתוג

הגדרה 6 (פונקציית מיתוג)

פונקציית מיתוג של nnn משתנים הינה כלל התאמה בין 2n2^n2n הצירופים השונים של המשתנים x1,…,xnx_{1},\dots,x_nx1​,…,xn​ לבין הקבוצה {0,1}\left\{ 0,1 \right\}{0,1}.

f:{0,1}×{0,1}×⋯×{0,1}n→{0,1}f(x1,…,xn)f:\underbracket{\{0,1\}\times \left\{ 0,1 \right\}\times \dots \times \left\{ 0,1 \right\}}_{n}\to \left\{ 0,1 \right\} \qquad \qquad f(x_{1},\dots,x_{n})f:n{0,1}×{0,1}×⋯×{0,1}​→{0,1}f(x1​,…,xn​)

ניתן לתאר פונקצית מיתוג באמצעות טבלת אמת:

x1,…,xnf(x1,…,xn)0,0,…,0f(0,0,…,0)0,0,…,1f(0,0,…,1)⋮⋮1,1,…,1f(1,1,…,1)\begin{array}{|c|c|} \hline x_{1},\dots,x_{n} & f(x_{1},\dots,x_{n}) \\ \hline 0,0,\dots,0 & f(0,0,\dots,0) \\ 0,0,\dots,1 & f(0,0,\dots,1) \\ \vdots & \vdots \\ 1,1,\dots,1 & f(1,1,\dots,1) \\ \hline \end{array}x1​,…,xn​0,0,…,00,0,…,1⋮1,1,…,1​f(x1​,…,xn​)f(0,0,…,0)f(0,0,…,1)⋮f(1,1,…,1)​​
הערה

מספר הפונקציות === מספר הווקטורים בגודל 2n2^n2n = מספר תת הקבוצות האפשריות של 2n2^n2n שורות.
לכן, מספר הפונקציות האפשריות הינו 22n2^{2^n}22n כאשר nnn הוא מספר המשתנים.

דוגמה (n=2n=2n=2)

X1,X20NORX1′X2X1′X1X2′X2′XORNANDANDXNORX2X1′+X2X1X1+X2′OR10,001010101010101010,100110011001100111,000001111000011111,100000000111111110123456789ABCDEF\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline X_1,X_2 & 0 & \text{NOR} & X_1' X_2 & X_1' & X_1 X_2' & X_2' & \text{XOR} & \text{NAND} & \text{AND} & \text{XNOR} & X_2 & X_1'+X_2 & X_1 & X_1+X_2' & \text{OR} & 1 \\ \hline 0,0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \hline 0,1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ \hline 1,0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \hline 1,1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \text{A} & \text{B} & \text{C} & \text{D} & \text{E} & \text{F} \\ \hline \end{array}X1​,X2​0,00,11,01,1​000000​NOR10001​X1′​X2​01002​X1′​11003​X1​X2′​00104​X2′​10105​XOR01106​NAND11107​AND00018​XNOR10019​X2​0101A​X1′​+X2​1101B​X1​0011C​X1​+X2′​1011D​OR0111E​11111F​​

צורות ייצוג לפונקציות

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

ביטוי מיתוג

דוגמה

f(x,y)=x′+yf(x,y)=x'+yf(x,y)=x′+y XYf(x,y)001011100111\begin{array}{|c|c|c|} \hline X & Y & f(x,y) \\ \hline 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \hline \end{array}X0011​Y0101​f(x,y)1101​​

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

הערה

נשים לב שאלגברה בוליאנית לא מוגדרת על שדה, אפילו לא Z2\mathbb{Z}_{2}Z2​ שכן ב-Z2\mathbb{Z}_{2}Z2​ מתקיים 1+1=01+1=01+1=0 ובבוליאנית מתקיים:

1+1=11+1=11+1=1

צורות קנוניות

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

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

מסקנה

בצורה הקנונית סכום מכפלות יש לרשום את סכום המכפלות(mintermmintermminterm) המתאימות לשורות בטבלת האמת בהן הפונקציה מקבלת ערך 1.

הערה

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

דוגמה

Decimal codex,y,zf(x,y,z)0000110010201003011041001510106110071110\begin{array}{|c|c|c|} \hline \text{Decimal code} & x,y,z & f(x,y,z) \\ \hline 0 & 000 & 1 \\ 1 & 001 & 0 \\ 2 & 010 & 0 \\ 3 & 011 & 0 \\ 4 & 100 & 1 \\ 5 & 101 & 0 \\ 6 & 110 & 0 \\ 7 & 111 & 0 \\ \hline \end{array}Decimal code01234567​x,y,z000001010011100101110111​f(x,y,z)10001000​​

עבור טבלת האמת הנ"ל נקבל כי:

f(x,y,z)=x′y′z′+xy′z′f(x,y,z)=x'y'z'+xy'z'f(x,y,z)=x′y′z′+xy′z′ f(x,y,z)=∑(0,4)f(x,y,z)=\sum(0,4)f(x,y,z)=∑(0,4)
דוגמה

Decimal codex,y,zf(x,y,z)0000110010201013011141000510106110171111\begin{array}{|c|c|c|} \hline\text{Decimal code} & x,y,z & f(x,y,z) \\ \hline 0 & 000 & 1 \\ 1 & 001 & 0 \\ 2 & 010 & 1 \\ 3 & 011 & 1 \\ 4 & 100 & 0 \\ 5 & 101 & 0 \\ 6 & 110 & 1 \\ 7 & 111 & 1 \\ \hline \end{array}Decimal code01234567​x,y,z000001010011100101110111​f(x,y,z)10110011​​

עבור טבלת האמת הבאה נקבל את הפונקציה:

f(x,y,z)=∑(0,2,3,6,7)f(x,y,z)=\sum(0,2,3,6,7)f(x,y,z)=∑(0,2,3,6,7)

באופן דומה, ניתן להגדיר ביטוי המתאר את מיקום האפסים בפונקציה. נתחיל בהגדרת ביטוי המקבל 0 עבור צרוף משתנים של שורה מסויימת בלבד.
ביטוי המקבל ערך 0 רק עבור צרוף המשתנים xyz=001xyz=001xyz=001 יהא (x+y+z′)(x+y+z')(x+y+z′).
מספיק שאחד הסכומים במכפלת הסכומים ישווה ל-000 בכדי שכל הביטוי ישתווה ל-0.

הגדרה 7 (maxtermmaxtermmaxterm)

סכום של nnn ליטרלים המתאימים לכל nnn המשתנים השונים.

הגדרה 8 (maxtermmaxtermmaxterm כפונקציה)

מקבל את הערך 0 אך ורק עבור צירוף יחיד של ערכי משתני כניסה.

דוגמה

Decimal codex,y,zf(x,y,z)0000110010201013011141000510106110171111\begin{array}{|c|c|c|} \hline \text{Decimal code} & x,y,z & f(x,y,z) \\ \hline 0 & 000 & 1 \\ 1 & 001 & 0 \\ 2 & 010 & 1 \\ 3 & 011 & 1 \\ 4 & 100 & 0 \\ 5 & 101 & 0 \\ 6 & 110 & 1 \\ 7 & 111 & 1 \\ \hline \end{array}Decimal code01234567​x,y,z000001010011100101110111​f(x,y,z)10110011​​

הפונקציה המתוארת ע"י טבלת האמת הנ"ל תהא:

f(x,y,z)=(x+y+z′)(x′+y+z)(x′+y+z′)=∏(1,4,5)f(x,y,z)=(x+y+z')(x'+y+z)(x'+y+z')=\prod(1,4,5)f(x,y,z)=(x+y+z′)(x′+y+z)(x′+y+z′)=∏(1,4,5)
הקשרים בין הצורות הקנוניות השונות

קל לעבור בין הייצוגים:

f(x,y,z)=∑(0,2,3,6,7)=x′y′z′+x′yz′+x′yz+xyz′+xyz=∏(1,4,5)=(x+y+z′)(x′+y+z)(x′+y+z′)\begin{align*} f(x,y,z)&=\sum(0,2,3,6,7)=x'y'z'+x'yz'+x'yz+xyz'+xyz \\ &=\prod(1,4,5)=(x+y+z')(x'+y+z)(x'+y+z') \end{align*}f(x,y,z)​=∑(0,2,3,6,7)=x′y′z′+x′yz′+x′yz+xyz′+xyz=∏(1,4,5)=(x+y+z′)(x′+y+z)(x′+y+z′)​ f(xyz)=f′′(xyz)=(x+y+z′)(x′+y+z)(x′+y+z′)f(xyz)=f''(xyz)=(x+y+z')(x'+y+z)(x'+y+z')f(xyz)=f′′(xyz)=(x+y+z′)(x′+y+z)(x′+y+z′) f(x,y,z)‾=x′y′z+xy′z′+xy′z\overline{f(x,y,z)}=x'y'z+xy'z'+xy'zf(x,y,z)​=x′y′z+xy′z′+xy′z
העברת ביטוי מיתוג לצורה קנונית מבלי טבלת אמת

נתון ביטוי fff בצורת סכום מכפלות(שאינו קנוני)

  1. בדוק כל מכפלה בביטוי: אם היא מינטרם, עבור למכפלה הבאה.
  2. אחרת:
    1. הרחבה: כפול את המכפלה ב-(xi+xi′)(x_{i}+x_{i}')(xi​+xi′​) עבור כל משתנה xix_{i}xi​ החסר במכפלה.
    2. פתח סוגריים ובטל מכפלות חוזרות.
דוגמה

f(x,y,z)=x′y+z′+xyz=x′y(z+z′)+z′(x+x′)(y+y′)+xyz=x′yz+x′yz′+z′xy+z′x′y+z′xy′+z′x′y′+xyz=x′yz+x′yz′+xyz′+xy′z′+x′y′z′+xyz=x′y′z′+x′yz′+x′yz+xy′z′+xyz′+xyz=∑(0,2,3,4,6,7)=∏(1,5)=(x+y+z′)(x′+y+z′)\begin{align*} f(x,y,z)&=x'y+z'+xyz \\ &=x'y(z+z')+z'(x+x')(y+y')+xyz \\ &=x'yz+x'yz'+z'xy+z'x'y+z'xy'+z'x'y'+xyz \\ &=x'yz+x'yz'+xyz'+xy'z'+x'y'z'+xyz \\ &=x'y'z'+x'yz'+x'yz+xy'z'+xyz'+xyz \\ &=\sum(0,2,3,4,6,7) \\ &=\prod(1,5) \\ &=(x+y+z')(x'+y+z') \end{align*}f(x,y,z)​=x′y+z′+xyz=x′y(z+z′)+z′(x+x′)(y+y′)+xyz=x′yz+x′yz′+z′xy+z′x′y+z′xy′+z′x′y′+xyz=x′yz+x′yz′+xyz′+xy′z′+x′y′z′+xyz=x′y′z′+x′yz′+x′yz+xy′z′+xyz′+xyz=∑(0,2,3,4,6,7)=∏(1,5)=(x+y+z′)(x′+y+z′)​

ניתן בנוסף לקחת את התצורה שקיבלנו: f(x,y,z)=x′y+z′+xyzf(x,y,z)=x'y+z'+xyzf(x,y,z)=x′y+z′+xyz ולבנות ממנה טבלת אמת:

xyzf(x,y,z)00010010010101111001101011011111\begin{array}{|c|c|} \hline xyz & f(x,y,z) \\ \hline 000 & 1 \\ 001 & 0 \\ 010 & 1 \\ 011 & 1 \\ 100 & 1 \\ 101 & 0 \\ 110 & 1 \\ 111 & 1 \\ \hline \end{array}xyz000001010011100101110111​f(x,y,z)10111011​​
דוגמה

g(x,y,z)=x′(y′+z)=(x′+yy′+zz′)(y′+z+xx′)=(x′+y+z)(x′+y+z′)(x′+y′+z)(x′+y′+z′)(y′+z+x)(y′+z+x′)=(x′+y+z)(x′+y+z′)(x′+y′+z)(x′+y′+z′)(x+y′+z)=(x+y′+z)(x′+y+z)(x′+y+z′)(x′+y′+z)(x′+y′+z′)=∏(2,4,5,6,7)=∑(0,1,3)=x′y′z′+x′y′z+x′yz\begin{align*} g(x,y,z)&=x'(y'+z) \\ &=(x'+yy'+zz')(y'+z+xx') \\ &=(x'+y+z)(x'+y+z')(x'+y'+z)(x'+y'+z')(y'+z+x)(y'+z+x') \\ &=(x'+y+z)(x'+y+z')(x'+y'+z)(x'+y'+z')(x+y'+z) \\ &=(x+y'+z)(x'+y+z)(x'+y+z')(x'+y'+z)(x'+y'+z') \\ &=\prod(2,4,5,6,7) \\ &=\sum(0,1,3) \\ &=x'y'z'+x'y'z+x'yz \end{align*}g(x,y,z)​=x′(y′+z)=(x′+yy′+zz′)(y′+z+xx′)=(x′+y+z)(x′+y+z′)(x′+y′+z)(x′+y′+z′)(y′+z+x)(y′+z+x′)=(x′+y+z)(x′+y+z′)(x′+y′+z)(x′+y′+z′)(x+y′+z)=(x+y′+z)(x′+y+z)(x′+y+z′)(x′+y′+z)(x′+y′+z′)=∏(2,4,5,6,7)=∑(0,1,3)=x′y′z′+x′y′z+x′yz​

צורות ייצוג לפונקציות

  1. טבלת אמת
  2. ביטוי מיתוג - f(x,y)=x′+yf(x,y)=x'+yf(x,y)=x′+y
  3. צורה קנונית של סכום מכפלות - f(x,y)=x′y′+x′y+xyf(x,y)=x'y'+x'y+xyf(x,y)=x′y′+x′y+xy
  4. צורה מקוצרת של סכום מכפלות - f(x,y)=∑(0,1,3)f(x,y)=\sum(0,1,3)f(x,y)=∑(0,1,3)
  5. צורה קנונית של מכפלת סכומים - f(x,y)=(x′+y)f(x,y)=(x'+y)f(x,y)=(x′+y)
  6. צורה מקוצרת של מכפלת סכומים - f(x,y)=∏(2)f(x,y)=\prod(2)f(x,y)=∏(2)

משפט הפיתוח של Shannon−BoolShannon-BoolShannon−Bool

משפט (שאנון-בוול)

f=xf(x=1)+x′f(x=0)f=xf(x=1)+x'f(x=0)f=xf(x=1)+x′f(x=0)

בהרחבה:

f(x1,x2,…,xn)=x1f(1,x2,…,xn)+x1′f(0,x2,…,xn)f(x_{1},x_{2},\dots,x_{n})=x_{1}f(1,x_{2},\dots,x_{n})+x_{1}'f(0,x_{2},\dots,x_{n})f(x1​,x2​,…,xn​)=x1​f(1,x2​,…,xn​)+x1′​f(0,x2​,…,xn​)

או: f(x1,…,xn)=(x1+f(0,x2,…,xn))(x1′+f(1,x2,…,xn))f(x_{1},\dots,x_{n})=(x_{1}+f(0,x_{2},\dots,x_{n}))(x_{1}'+f(1,x_{2},\dots,x_{n}))f(x1​,…,xn​)=(x1​+f(0,x2​,…,xn​))(x1′​+f(1,x2​,…,xn​))

ההוכחה היא באינדוקציה שלמה על x1x_{1}x1​.
השוויונות מתקיימים בהצבת x1=0x_{1}=0x1​=0 ובהצבת x1=1x_{1}=1x1​=1.

f(x1,x2,…,xn)=x1f(1,x2,…,xn)+x1′f(0,x2,…,xn)\boxed{f(x_{1},x_{2},\dots,x_{n})=x_{1}f(1,x_{2},\dots,x_{n})+x_{1}'f(0,x_{2},\dots,x_{n})}f(x1​,x2​,…,xn​)=x1​f(1,x2​,…,xn​)+x1′​f(0,x2​,…,xn​)​

באמצעות המשפט נקבל:

f(x1,…,xn)=x1[x2f(1,1,x3,…,xn)+x2′f(1,0,x3,…,xn)]+x1′[x2f(0,1,x3,…,xn)+x2′f(0,0,x3,…,xn)]=x1x2f(1,1,x3,…,xn)+x1x2′f(1,0,x3,…,xn)+x1′x2f(0,1,x33,…,xn)+x1′x2′f(0,0,x3,…,xn)=⋯=x1x2…xnf(1,…,1)+⋯+x1′x2′…xn′f(0,0,…,0)\begin{align*} f(x_{1},\dots,x_{n})&=x_{1}[x_{2}f(1,1,x_{3},\dots,x_{n})+x_{2}'f(1,0,x_{3},\dots,x_{n})] \\ &\quad +x_{1}'[x_{2}f(0,1,x_{3},\dots,x_{n})+x_{2}'f(0,0,x_{3},\dots,x_{n})] \\ &=x_{1}x_{2}f(1,1,x_{3},\dots,x_{n})+x_{1}x_{2}'f(1,0,x_{3},\dots,x_{n}) \\ &\quad +x_{1}'x_{2}f(0,1,x_{3}3,\dots,x_{n})+x_{1}'x_{2}'f(0,0,x_{3},\dots,x_{n}) \\ &=\cdots \\ &=x_{1}x_{2}\dots x_{n}f(1,\dots,1)+\dots+x_{1}'x_{2}'\dots x_{n}'f(0,0,\dots,0) \end{align*}f(x1​,…,xn​)​=x1​[x2​f(1,1,x3​,…,xn​)+x2′​f(1,0,x3​,…,xn​)]+x1′​[x2​f(0,1,x3​,…,xn​)+x2′​f(0,0,x3​,…,xn​)]=x1​x2​f(1,1,x3​,…,xn​)+x1​x2′​f(1,0,x3​,…,xn​)+x1′​x2​f(0,1,x3​3,…,xn​)+x1′​x2′​f(0,0,x3​,…,xn​)=⋯=x1​x2​…xn​f(1,…,1)+⋯+x1′​x2′​…xn′​f(0,0,…,0)​
מסקנה

  • קיבלנו את הצורה הקנונית של סכום המכפלות (מכיוון שאם fff עם קבועים תהיה 1 אזי זה לא יתאפס)
  • לכל פונקציה יש צורה קנונית
משפט

כל פונקציה ניתנת לרישום בצורה הקנונית

f(x1,…,xn)=a0x1′x2′…xn′+⋯+a2n−1x1x2…xnf(x_{1},\dots,x_{n})=a_{0}x_{1}'x_{2}'\dots x_{n}'+\dots+a_{2^n-1}x_{1}x_{2}\dots x_{n}f(x1​,…,xn​)=a0​x1′​x2′​…xn′​+⋯+a2n−1​x1​x2​…xn​

הוכחה: באמצעות הפיתוח של שאנון.

הערה

עבור משתנה אחד נקבל ממשפט הפיתוח: f(x)=a0x′+a1xf(x)=a_{0}x'+a_{1}xf(x)=a0​x′+a1​x.
סה"כ יש 22=42^2=422=4 פונקציות והן:

  • פונקציית הזהות
  • הפונקציה הקבועה 1
  • הפונקציה הקבועה 0
  • הפונקציה NOTNOTNOT

הפונקציה XORXORXOR

חיבור מודולו 2: שארית החיבור לאחר החלוקה ב-222

xyx⊕y000011101110\begin{array}{|cc|c|} \hline x & y & x \oplus y \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \hline \end{array}x0011​y0101​x⊕y0110​​
הגדרה 9 (XORXORXOR)

(y=1∧x=0)∨(y=0∧x=1)  ⟺  x⊕y=1(y=1 \land x=0) \lor (y=0 \land x=1) \iff x \oplus y=1(y=1∧x=0)∨(y=0∧x=1)⟺x⊕y=1
משפט (תכונות XORXORXOR)

A⊕B=B⊕AA⊕(B⊕C)=(A⊕B)⊕CA(B⊕C)=(AB)⊕(AC)A=B  ⟺  A⊕B=0A⊕0=AA⊕A=0A⊕1=A′A⊕A′=1\begin{matrix} A \oplus B=B \oplus A \\ A \oplus(B \oplus C)=(A \oplus B)\oplus C \\ A(B \oplus C)=(AB)\oplus (AC) \\ A=B \iff A \oplus B=0 \\ A \oplus 0=A \qquad A \oplus A=0 \\ A \oplus 1=A' \qquad A \oplus A'=1 \end{matrix}A⊕B=B⊕AA⊕(B⊕C)=(A⊕B)⊕CA(B⊕C)=(AB)⊕(AC)A=B⟺A⊕B=0A⊕0=AA⊕A=0A⊕1=A′A⊕A′=1​
דוגמה

יהיו A,B,C,DA,B,C,DA,B,C,D ביטוי מיתוג שונים. האם תמיד מתקיים ש: A⊕B⊕C⊕D=A⊕B⊕C⊕DA \oplus B \oplus C \oplus D=A \oplus B \oplus C \oplus DA⊕B⊕C⊕D=A⊕B⊕C⊕D

ברור שכן\LARGE \R{\text{ברור שכן}}ברור שכן

האם תמיד מתקיים ש: A‾⊕B⊕C⊕D=A⊕B‾⊕C⊕D\overline{A}\oplus B \oplus C \oplus D=A \oplus \overline{B}\oplus C \oplus DA⊕B⊕C⊕D=A⊕B⊕C⊕D? התשובה היא כן, שכן אם נסתכל על המשוואה בזוגות ונבצע טבלת אמת על A,BA,BA,B:

ABA⊕B‾A‾⊕B0011010010001111\begin{array}{|cc|c|c|} \hline A & B & A \oplus \overline{B} & \overline{A} \oplus B \\ \hline 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ \hline \end{array}A0011​B0101​A⊕B1001​A⊕B1001​​

ביטוי מינימלי של פונקציה

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

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

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

הערה

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

דוגמה

תהי פונקציה קנונית: f(x,y,z)=x′yz′+x′y′z′+xy′z′+x′yz+xyz+xy′zf(x,y,z)=x'yz'+x'y'z'+xy'z'+x'yz+xyz+xy'zf(x,y,z)=x′yz′+x′y′z′+xy′z′+x′yz+xyz+xy′z. נרצה למצוא לה ביטוי מינימלי ונעשה זאת כך:
נוכל תחילה לצמצם איברים:

f(x,y,z)=x′z′(y+y′)1+xy′z′+x′yz+xyz+xy′zf(x,y,z)=x'z'\underbracket{(y+y')}_{1}+xy'z'+x'yz+xyz+xy'zf(x,y,z)=x′z′1(y+y′)​+xy′z′+x′yz+xyz+xy′z f(x,y,z)=z′(x′+xy′)+x′yz+xyz+xy′z=z′(x′+y′)+x′yz+xyz+xy′zf(x,y,z)=z'(x'+xy')+x'yz+xyz+xy'z=z'(x'+y')+x'yz+xyz+xy'zf(x,y,z)=z′(x′+xy′)+x′yz+xyz+xy′z=z′(x′+y′)+x′yz+xyz+xy′z f(x,y,z)=x′z′+y′z′+x′yz+xyz+xy′zf(x,y,z)=x'z'+y'z'+x'yz+xyz+xy'zf(x,y,z)=x′z′+y′z′+x′yz+xyz+xy′z

כעת, לאחר שפיקנו את שלושת הגורמים הראשונים נוכל להמשיך ולפרק את שאר הגורמים:

f(x,y,z)=x′z′+y′z′+yz+xzf(x,y,z)=x'z'+y'z'+yz+xzf(x,y,z)=x′z′+y′z′+yz+xz

מ-6 איברים קיבלנו 4 מכפלות. כעת, כמות הליטרלים הוא 8 ולא כמו מה שהיה לנו קודם.
ניתן לעשות גם מינימיזציות אחרות ולקבל יצורים שונים ומשונים כגון: f(x,y,z)=x′z′+xy′+yzf(x,y,z)=x'z'+xy'+yzf(x,y,z)=x′z′+xy′+yz
קיבלנו פה 3 מכפלות עם 6 ליטרלים ולא 8.

הגדרה 10 (ביטוי בלתי ניתן לצמצום)

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

הערה

  • ביטוי בלתי ניתן לצמצום אינו בהכרח מינימלי. (כמו שראינו בדוגמה ממקודם)
  • ביטוי מינימלי אינו בהכרח יחיד

מערכת פעולות שלמה

הגדרה 11 (מערכת פעולות שלמה)

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

דוגמה

הקבוצה {⋅,+,′}\left\{ \cdot,+,' \right\}{⋅,+,′}. בנוסף, לפי דה-מורגן נקבל כי גם {+,′},{⋅,′}\left\{ +,' \right\},\left\{ \cdot,' \right\}{+,′},{⋅,′} הן שלמות.

משפט

כל קבוצה המממשת {⋅,′}\left\{ \cdot,' \right\}{⋅,′} או {+,′}\left\{ +,' \right\}{+,′} הינה שלמה.

דוגמה

האופרטור NORNORNOR מהווה קבוצה שלמה. נראה זאת:

NOR(x,y)=(x+y)′NOR(x,y)=(x+y)'NOR(x,y)=(x+y)′ NOR(x,x)=(x+x)′=x′NOR(x,x)=(x+x)'=x'NOR(x,x)=(x+x)′=x′ NOR(NOR(x,y),NOR(x,y))=(NOR(x,y))′=(x+y)′′=x+yNOR(NOR(x,y),NOR(x,y))=(NOR(x,y))'=(x+y)''=x+yNOR(NOR(x,y),NOR(x,y))=(NOR(x,y))′=(x+y)′′=x+y

לפי המשפט, זוהי מערכת פעולות שלמה.

באופן דומה גם NANDNANDNAND מהווה קבוצה שלמה.

הגדרה 12 (אופרטור אוניברסלי)

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

הערה

איך מראים שמערכת פעולות SSS אינה שלמה? מראים פונקציה שלא ניתן לממש באמצעותה. איך נעשה זאת?

  1. מראים ע"י בדיקה של כל אפשרויות הרכבת הפונקציות מ-SSS שפונקציה מסוימת אינה ניתנת לתיאור(למשל NOTNOTNOT או ANDANDAND)

  2. מוצאים תכונה PPP שכל הרבה של פונקציות מ-SSS מקיימת אך קיימת פונקציה שאינה מקיימת תכונה זו(למשל ליניאריות)

  3. מוכיחים שמספר האפשרויות להרכבת פונקציות מ-SSS קטן ממספר הפונקציות האפשריות(שיקולי ספירה)

דוגמה

{XOR},{XOR,AND},{XOR,1},…\left\{ XOR \right\},\left\{ XOR,AND \right\},\left\{ XOR,1 \right\},\dots{XOR},{XOR,AND},{XOR,1},…
תרגיל

האם הפונקציה f(x,y,z)=xy′+xz′+y′z′f(x,y,z)=xy'+xz'+y'z'f(x,y,z)=xy′+xz′+y′z′ היא מערכת פעולות שלמה?

F(0,0,0)=1F(1,1,1)=0F(0,0,0)=1 \qquad F(1,1,1)=0F(0,0,0)=1F(1,1,1)=0

נשים לב כי: F(x,x,x)=x′F(x,x,x)=x'F(x,x,x)=x′
במצב זה אנו לא נצליח ליצור OROROR או ANDANDAND. אך אם נשתמש בקבוע 111 או 000 נוכל ליצור:

F(x,y,1)=xy′  ⟹  F(x,y′,1)=xyF(0,y,z)=y′z′=(y+z)′=NOR\begin{matrix} F(x,y,1)=xy'\implies F(x,y',1)=xy \\ F(0,y,z)=y'z'=(y+z)'=NOR \end{matrix}F(x,y,1)=xy′⟹F(x,y′,1)=xyF(0,y,z)=y′z′=(y+z)′=NOR​

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

מערכת פעולות חצי-שלמה

הגדרה 13 (מערכת פעולות חצי שלמה)

מערכת פעולות תקרא חצי שלמה אם כדי שהיא תהיה שלמה נדרש להוסיף אליה את הקבוע 111 או הקבוע 000 או את שניהם.

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

מפת קרנו

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

סדר העמודות במפת קרנו מאורגן לפי גוד GrayGrayGray.

N=1N=2N=30000001010011101110010100111101100\begin{array}{|c|c|c|} \hline N=1 & N=2 & N=3 \\ \hline 0 & 00 & 000 \\ 1 & 01 & 001 \\ & 11 & 011 \\ & 10 & 010 \\ & & 100 \\ & & 111 \\ & & 101 \\ & & 100 \\ \hline \end{array}N=101​N=200011110​N=3000001011010100111101100​​

נסתכל על טבלת אמת:

Decimal codex,y,zf(x,y,z)0000010010201013011041001510106110171111\begin{array}{|c|c|c|} \hline \text{Decimal code} & x,y,z & f(x,y,z) \\ \hline 0 & 000 & 0 \\ 1 & 001 & 0 \\ 2 & 010 & 1 \\ 3 & 011 & 0 \\ 4 & 100 & 1 \\ 5 & 101 & 0 \\ 6 & 110 & 1 \\ 7 & 111 & 1 \\ \hline \end{array}Decimal code01234567​x,y,z000001010011100101110111​f(x,y,z)00101011​​

ונעביר אותה למפת קרנו:

\begin{array}{c|c|c|c|c|c|c|c|} & 00 & 01 & 11 & 10 \\ 0 &\hline 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{array} \implies \begin{array}{|c|c|c|c|} \hline 0 & 2 & 6 & 4 \\ \hline 1 & 3 & 7 & 5 \\ \hline \end{array}

אם יש לנו 4 משתנים: f(w,x,y,z)f(w,x,y,z)f(w,x,y,z) אזי זו תהיה טבלת קרנו שלה:

yz╲wx00011110000412801151391137151110261410\begin{array}{c|c|c|c|c|} _{yz}\diagdown^{wx} & 00 & 01 & 11 & 10 \\ \hline 00 & 0 & 4 & 12 & 8 \\ \hline 01 & 1 & 5 & 13 & 9 \\ \hline 11 & 3 & 7 & 15 & 11 \\ \hline 10 & 2 & 6 & 14 & 10 \\ \hline \end{array}yz​╲wx00011110​000132​014576​1112131514​10891110​​

אם נקבל את הפונקציה f=∑(4,5,8,12,13,14,15)f=\sum(4,5,8,12,13,14,15)f=∑(4,5,8,12,13,14,15) אזי נכניס אחדים במקומות המתאימים:

yz╲wx00011110001110111111101\begin{array}{c|c|c|c|c|} _{yz}\diagdown^{wx} & 00 & 01 & 11 & 10 \\ \hline 00 & & 1 & 1 & 1 \\ \hline 01 & & 1 & 1 & \\ \hline 11 & & & 1 & \\ \hline 10 & & & 1 & \\ \hline \end{array}yz​╲wx00011110​00​0111​111111​101​​

זוהי המפת קרנו שנקבל לפונקציה זו.

הגדרה 14 (משבצות שכנות)

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

משפט

כאשר המפה מייצגת טבלת אמת של nnn משתנים, לכל משבצת nnn שכנים.

דוגמה

z╲xy000111100026411375\begin{array}{c|c|c|c|c|} _{z}\diagdown^{xy} & 00 & 01 & 11 & 10 \\ \hline 0 & 0 & 2 & 6 & 4 \\ \hline 1 & 1 & 3 & 7 & 5 \\ \hline \end{array}z​╲xy01​0001​0123​1167​1045​​

במפת קרנו של שלושה משתנים, לכל משבצת שלושה שכנים.

  • השכנים של 5 הם 4,7,1

צמצום פונקציות בעזרת מפת קרנו

צמצום פונקציות מבוסס על הזהות:

משפט

Ax′+Ax=AAx'+Ax=AAx′+Ax=A

שתי משבצות שכנות המסומנות ב-1, המתאימות לשני מינטרמים הנבדלים בליטרל אחד, ניתנות לליכוד למכפלה של n−1n-1n−1 הליטרלים המשותפים.

z╲xy000111100111\begin{array}{c|c|c|c|c|} _{z}\diagdown^{xy} & 00 & 01 & 11 & 10 \\ \hline 0 \\ \hline 1 & & 1 & 1 \\ \hline \end{array}z​╲xy01​00​011​111​10​

ממפת קרנו ולפי הזהות יתקבל:

x′yz+xyz=yzx'yz+xyz=yzx′yz+xyz=yz
דוגמה

נתונה הפונקציה f(x,y,z)=∑(2,6,7)f(x,y,z)=\sum(2,6,7)f(x,y,z)=∑(2,6,7) וננסה למצוא עבורה ביטוי מינימלי.
באמצעות חוקי האלגברה:

f=x′yz′+xyz′+xyz=↓A+A=Ax′yz′+xyz′+xyz′+xyz=yz′(x′+x)+xy(z′+z)=yz′+xyf=x'yz'+xyz'+xyz \underset{\begin{matrix} \downarrow \\ A+A=A \end{matrix}}{=} x'yz'+xyz'+xyz'+xyz=yz'(x'+x)+xy(z'+z)=yz'+xyf=x′yz′+xyz′+xyz↓A+A=A​=​x′yz′+xyz′+xyz′+xyz=yz′(x′+x)+xy(z′+z)=yz′+xy

באמצעות מפת קרנו:

z╲xy0001111001111\begin{array}{c|c|c|c|c|} _{z}\diagdown^{xy} & 00 & 01 & 11 & 10 \\ \hline 0 & & 1 & 1 \\ \hline 1 & & & 1 \\ \hline \end{array}z​╲xy01​00​011​1111​10​

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

f=yz′+xyf=yz'+xyf=yz′+xy
דוגמה

קובייה mmm מימדית(במפת קרנו של nnn משתנים) ≡\equiv≡ אוסף מקסימלי של 2m2^m2m משבצות שכולן זהות בייצוגן הבינארי ב-n−mn-mn−m מקומות.
נסתכל עבור n=4n=4n=4:

yz╲wx00011110001011111111111011\begin{array}{c|c|c|c|c|} _{yz}\diagdown^{wx} & 00 & 01 & 11 & 10 \\ \hline 00 & & & & 1 \\ \hline 01 & & 1 & 1 & 1 \\ \hline 11 & 1 & 1 & 1 & 1 \\ \hline 10 & 1 & & & 1 \\ \hline \end{array}yz​╲wx00011110​0011​0111​1111​101111​​ f(w,x,y,z)=∑(2,3,5,7,9,11,12,13,14,15)=w′x′y+xz+wx′f(w,x,y,z)=\sum(2,3,5,7,9,11,12,13,14,15)=w'x'y+xz+wx'f(w,x,y,z)=∑(2,3,5,7,9,11,12,13,14,15)=w′x′y+xz+wx′

זהו פתרון לא כל כך טוב!

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

מסקנה

יש עוד מה ללמוד בנושא של מפת קרנו - אך זה לא יהיה בקורס הזה.

צירופי ברירה - Don't Care

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

  • צירופי כניסה מסוימים לא ייתכנו
  • ערך היציאה עבור צירופי כניסה כאלה אינו מעניין

צירופי כניסות כאלה יקראו צירופי ברירה(באנגלית Don't Care Combinations) והיציאה עבורם תסומן ב-∅\Large \varnothing∅.
∅\varnothing∅ יכול לציין 0 או 1 ולכן פונקציה עם KKK צירופי ברירה היא למעשה קבוצה של פונקציות בעוצמה 2k2^k2k.
לצורך מנימיזציה נבחר את הפונקציה מהקבוצה הנ"ל את זו הנותנת את הביטוי הפשוט ביותר(מינימלי)

דוגמה

צמצם את הפונקציה fff שהקלט שלה הוא ספרה עשרונית בקוד BCDBCDBCD והפלט הוא f=1f=1f=1 אם הספרה מתחלקת ב-333 ללא שארית.
נקצה 4 משתני כניסה w,x,y,zw,x,y,zw,x,y,z לציון הספרה. צירופי הכניסה 101010 עד 151515 אינם חוקיים. ערך הפלט יהיה 1 עבור הקלטים: 0,3,6,90,3,6,90,3,6,9:

f=∑(0,3,6,9)+∑∅(10,11,12,13,14,15)f=\sum(0,3,6,9)+\sum_{\varnothing}(10,11,12,13,14,15)f=∑(0,3,6,9)+∅∑​(10,11,12,13,14,15)

נבנה מפת קרנו לצורך מנימיזציה:

yz╲wx00011110001∅01∅1111∅∅101∅∅\begin{array}{c|c|c|c|c|} _{yz}\diagdown^{wx} & 00 & 01 & 11 & 10 \\ \hline 00 & 1 & & \varnothing & \\ \hline 01 & & & \varnothing & 1 \\ \hline 11 & 1 & & \varnothing & \varnothing \\ \hline 10 & & 1 & \varnothing & \varnothing \\ \hline \end{array}yz​╲wx00011110​0011​011​11∅∅∅∅​101∅∅​​

כעת, נוכל לבחור את ה-∅\varnothing∅ כמה שאנחנו רוצים ואז נקבל:

fmin=w′x′y′z′+x′yz+xyz′+wz=∑(0,3,6,9,11,13,14,15)f_{min}=w'x'y'z'+x'yz+xyz'+wz=\sum(0,3,6,9,11,13,14,15)fmin​=w′x′y′z′+x′yz+xyz′+wz=∑(0,3,6,9,11,13,14,15)
דוגמה (דוגמה שנייה לצירופי ברירה)

צמצם את הפונקציה (מרובת היציאות) המתרגמת ספרת BCD לקוד Excess-3, f(A)=A+3f(A)=A+3f(A)=A+3.

פתרון: נסמן את ארבע הכניסות w,x,y,zw,x,y,zw,x,y,z ואת ארבע הפונקציות f1,f2,f3,f4f_1,f_2,f_3,f_4f1​,f2​,f3​,f4​ ונקבל את טבלת האמת הבאה:

ספרהwxyzwxyzwxyzf1f2f3f4f_1 f_2 f_3 f_4f1​f2​f3​f4​
000000011
100010100
200100101
300110110
401000111
501011000
601101001
701111010
810001011
910011100

הצירופים 10 עד 15 (מ-1010 עד 1111) אינם חוקיים בקוד BCD ולכן יהוו צירופי ברירה (Don't Care) שיסומנו ב-∅\varnothing∅. נבנה מפות קרנו עבור כל אחת מהפונקציות לצורך מינימיזציה:

עבור f1f_1f1​:

yz╲wx0001111000∅1011∅1111∅∅101∅∅\begin{array}{c|c|c|c|c|} _{yz}\diagdown^{wx} & 00 & 01 & 11 & 10 \\ \hline 00 & & & \varnothing & 1 \\ \hline 01 & & 1 & \varnothing & 1 \\ \hline 11 & & 1 & \varnothing & \varnothing \\ \hline 10 & & 1 & \varnothing & \varnothing \\ \hline \end{array}yz​╲wx00011110​00​01111​11∅∅∅∅​1011∅∅​​

עבור f2f_2f2​:

yz╲wx00011110001∅011∅1111∅∅101∅∅\begin{array}{c|c|c|c|c|} _{yz}\diagdown^{wx} & 00 & 01 & 11 & 10 \\ \hline 00 & & 1 & \varnothing & \\ \hline 01 & 1 & & \varnothing & 1 \\ \hline 11 & 1 & & \varnothing & \varnothing \\ \hline 10 & 1 & & \varnothing & \varnothing \\ \hline \end{array}yz​╲wx00011110​00111​011​11∅∅∅∅​101∅∅​​

עבור f3f_3f3​:

yz╲wx000111100011∅101∅1111∅∅10∅∅\begin{array}{c|c|c|c|c|} _{yz}\diagdown^{wx} & 00 & 01 & 11 & 10 \\ \hline 00 & 1 & 1 & \varnothing & 1 \\ \hline 01 & & & \varnothing & \\ \hline 11 & 1 & 1 & \varnothing & \varnothing \\ \hline 10 & & & \varnothing & \varnothing \\ \hline \end{array}yz​╲wx00011110​0011​0111​11∅∅∅∅​101∅∅​​

עבור f4f_4f4​:

yz╲wx000111100011∅101∅11∅∅1011∅∅\begin{array}{c|c|c|c|c|} _{yz}\diagdown^{wx} & 00 & 01 & 11 & 10 \\ \hline 00 & 1 & 1 & \varnothing & 1 \\ \hline 01 & & & \varnothing & \\ \hline 11 & & & \varnothing & \varnothing \\ \hline 10 & 1 & 1 & \varnothing & \varnothing \\ \hline \end{array}yz​╲wx00011110​0011​0111​11∅∅∅∅​101∅∅​​

לאחר צמצום הפונקציות מהמפות, נקבל את הביטויים המינימליים הבאים:

f1=w+xz+xyf2=x′z+x′y+xy′z′f3=y′z′+yzf4=z′\begin{align*} f_1 &= w + xz + xy \\ f_2 &= x'z + x'y + xy'z' \\ f_3 &= y'z' + yz \\ f_4 &= z' \end{align*}f1​f2​f3​f4​​=w+xz+xy=x′z+x′y+xy′z′=y′z′+yz=z′​