מרחק המינג - זה סתם מרחק בין 2 מילים בקודמרחק קוד - הוא המרחק המינג המינימלי בכל הקוד.
למדנו שהמחשב "סופר" בבינארית. אבל אנחנו רוצים גם לבצע פעולות חשבוניות, להריץ תוכנות, לקבל החלטות וכו'.
A + A = A A ⋅ A = A A + 1 = 1 A ⋅ 1 = A A + 0 = A A ⋅ 0 = 0 A + A ‾ = 1 A ⋅ A ‾ = 0 O R A N D \begin{matrix}
A+A=A & A\cdot A=A \\
A+1=1 & A\cdot 1=A \\
A+0=A & A\cdot 0=0 \\
A+\overline{A}=1 & A\cdot \overline{A}=0 \\
OR & AND
\end{matrix} A + A = A A + 1 = 1 A + 0 = A A + A = 1 OR A ⋅ A = A A ⋅ 1 = A A ⋅ 0 = 0 A ⋅ A = 0 A N D
A + A ⋅ B = A A+A\cdot B=A A + A ⋅ B = A A + A ‾ ⋅ B = A + B A+\overline{A}\cdot B=A+B A + A ⋅ B = A + B ( A + B ) ( A + C ) = A + B C (A+B)(A+C)=A+BC ( A + B ) ( A + C ) = A + BC הוכחה:
A + A B = A ( B + 1 ⏟ 1 ) = A A+AB=A(\underbrace{B+1}_1)=A A + A B = A ( 1 B + 1 ) = A A + A ‾ B = A + A B A + A ‾ B = A + B ( A + A ‾ ) = A + B A+\overline{A}B=\underbracket{A+AB}_{A}+\overline{A}B=A+B(A+\overline{A})=A+B A + A B = A A + A B + A B = A + B ( A + A ) = A + B ( A + B ) ( A + C ) = A A + A C + A B + B C = A ( 1 + B + C ) + B C = A + B C (A+B)(A+C)=AA+AC+AB+BC=A(1+B+C)+BC=A+BC ( A + B ) ( A + C ) = AA + A C + A B + BC = A ( 1 + B + C ) + BC = A + BC ∎
A ⋅ B ‾ = A ‾ + B ‾ \overline{A\cdot B}=\overline{A}+\overline{B} A ⋅ B = A + B A + B ‾ = A ‾ ⋅ B ‾ \overline{A+B}=\overline{A}\cdot \overline{B} A + B = A ⋅ B
חשוב מאוד לשים לב כי לא ניתן להוציא N O T NOT NOT
צמצמו את הביטוי ( A + B ) ( A + B ‾ ) C (A+B)(A+\overline{B})C ( A + B ) ( A + B ) C
( A + B ) ( A + B ‾ ) C = ( A A + A B ‾ + A B + B B ‾ ) C = [ A + A ( B ‾ + B ⏟ 1 ) ] C = ( A + A ⏟ A ) C = A C \begin{align*}
(A+B)(A+\overline{B})C &=(AA+A\overline{B}+AB+B\overline{B})C \\
&=[A+A(\underbrace{\overline{B}+B}_{1})]C=(\underbrace{A+A}_{A})C \\
&=AC
\end{align*} ( A + B ) ( A + B ) C = ( AA + A B + A B + B B ) C = [ A + A ( 1 B + B )] C = ( A A + A ) C = A C
פשטו את הביטוי הבא:
A ‾ B ‾ C ‾ + A ‾ B C ‾ + A B C ‾ + A B ‾ C ‾ + A B C + A B ‾ C \overline{A}\ \overline{B}\ \overline{C}+\overline{A}B \overline{C}+AB \overline{C}+A \overline{B}\ \overline{C}+ABC+A \overline{B}C A B C + A B C + A B C + A B C + A BC + A B C A ‾ B ‾ C ‾ + A ‾ B C ‾ + A B C ‾ + A B ‾ C ‾ + A B C + A B ‾ C = A ‾ ⋅ C ‾ ( B + B ‾ ) A C ‾ ( B + B ‾ ) + A C ( B + B ‾ ) = A ‾ ⋅ C ‾ + A C ‾ + A C ‾ + A C = C ‾ ( A ‾ + A ) + A ( C + C ‾ ) = A + C ‾ \begin{align*}
\overline{A}\ \overline{B}\ \overline{C}&+\overline{A}B \overline{C}+AB \overline{C}+A \overline{B}\ \overline{C}+ABC+A \overline{B}C \\
&=\overline{A}\cdot\overline{C}(B+\overline{B})A \overline{C}(B+\overline{B})+AC(B+\overline{B}) \\
&=\overline{A}\cdot \overline{C}+\underbracket{A \overline{C}+ A \overline{C}}+AC \\
&=\overline{C}(\overline{A}+A)+A(C+\overline{C}) \\
&=A+\overline{C}
\end{align*} A B C + A B C + A B C + A B C + A BC + A B C = A ⋅ C ( B + B ) A C ( B + B ) + A C ( B + B ) = A ⋅ C + A C + A C + A C = C ( A + A ) + A ( C + C ) = A + C
פשטו את הביטוי A ( B ‾ ⋅ C ‾ + B C ) ‾ \overline{A(\overline{B}\cdot \overline{C}+BC)} A ( B ⋅ C + BC )
כדי לא להתבלבל נתחיל לתת שמות:
X = B ‾ ⋅ C ‾ + B C X=\overline{B}\cdot \overline{C}+BC X = B ⋅ C + BC לפי דה מורגן מתקיים:
A X ‾ = A ‾ + X ‾ \overline{AX}=\overline{A}+\overline{X} A X = A + X כעת, נוכל לפרק את X X X
X ‾ = B ‾ ⋅ C ‾ ⏟ Y + B C Z ‾ \overline{X}=\overline{\underbrace{\overline{B}\cdot \overline{C}}_{Y}+ \underbracket{BC}_{Z}} X = Y B ⋅ C + Z BC Y ‾ = B ‾ ⋅ C ‾ = B + C \overline{Y}=\overline{B}\cdot \overline{C}=B+C Y = B ⋅ C = B + C Z ‾ = B C ‾ = B ‾ + C ‾ \overline{Z}=\overline{BC}=\overline{B}+\overline{C} Z = BC = B + C כעת, נוכל לחזור למשוואה המקורית שלנו:
A ‾ + X ‾ = A ‾ + Y ‾ ⋅ Z ‾ = A ‾ + ( B + C ) ( B ‾ + C ‾ ) = A ‾ + ( B B ‾ + B ‾ C + B C ‾ + C C ‾ ) = ↓ X X ‾ = 0 A ‾ + B ‾ C + B C ‾ \overline{A}+\overline{X}=\overline{A}+\overline{Y}\cdot \overline{Z}=\overline{A}+(B+C)(\overline{B}+\overline{C})=\overline{A}+(B \overline{B}+\overline{B}C+B \overline{C}+C \overline{C}) \underset{\begin{matrix}
\downarrow \\
X \overline{X}=0
\end{matrix}}{=}\overline{A}+\overline{B}C+B \overline{C} A + X = A + Y ⋅ Z = A + ( B + C ) ( B + C ) = A + ( B B + B C + B C + C C ) ↓ X X = 0 = A + B C + B C פונקציות
פונקציה f ( x 1 , K , x n ) f(x_{1},K, x_{n}) f ( x 1 , K , x n ) 2 n 2^n 2 n
f ( 0 , 0 , 1 ) = 1 f(0,0,1)=1 f ( 0 , 0 , 1 ) = 1
קיימות 2 2 n 2^{2^n} 2 2 n n n n
הגדרה 3 (
M i n t e r m Minterm M in t er m - מינטרמם)
מכפלה המכילה את כל n n n
w ‾ x y z ‾ \overline{w}xy \overline{z} w x y z עם w ‾ = 0 , x = 1 , y = 1 , z ‾ = 0 \overline{w}=0,x=1,y=1,\overline{z}=0 w = 0 , x = 1 , y = 1 , z = 0
הגדרה 4 (צורה קנונית של סכום מכפלות)
סכום כל המכפלות(m i n t e r m s minterms min t er m s
הצורה הקנונית אינה בהכרח הצורה המצומצמת או המיטבית ביותר.
הגדרה 5 (
M a x t e r m Maxterm M a x t er m - מקסטרם)
סכום של n n n 0 0 0
הגדרה 6 (צורה קנונית של מכפלת סכומים)
מכפלת כל הסכומים(m a x t e r m maxterm ma x t er m
דרכים לייצג פונקציות
1. טבלת אמת
עבור 3 3 3 x , y , z x,y,z x , y , z 2 3 = 8 2^3=8 2 3 = 8 2 8 = 256 2^8=256 2 8 = 256
x y z f 0 f 1 f 2 f 43 f 255 000 0 0 0 0 1 001 0 0 0 0 1 010 0 0 0 1 1 011 0 0 0 0 1 100 0 0 0 1 1 101 0 0 0 0 1 110 0 0 1 1 1 111 0 1 0 1 1 \begin{matrix}
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline xyz & f_{0} & f_{1} & f_{2} & & f_{43} & & f_{255} \\
\hline 000 & 0 & 0 & 0 & & 0 & & 1 \\
001 & 0 & 0 & 0 & & 0 & & 1 \\
010 & 0 & 0 & 0 & & 1 & & 1 \\
011 & 0 & 0 & 0 & & 0 & & 1 \\
100 & 0 & 0 & 0 & & 1 & & 1 \\
101 & 0 & 0 & 0 & & 0 & & 1 \\
110 & 0 & 0 & 1 & & 1 & & 1 \\
111 & 0 & 1 & 0 & & 1 & & 1 \\
\hline
\end{array}
\end{matrix} x yz 000 001 010 011 100 101 110 111 f 0 0 0 0 0 0 0 0 0 f 1 0 0 0 0 0 0 0 1 f 2 0 0 0 0 0 0 1 0 f 43 0 0 1 0 1 0 1 1 f 255 1 1 1 1 1 1 1 1 2. סכום מכפלות (M i n t e r m Minterm M in t er m
סכום מכפלות x y z f 43 ( x , y , z ) m i n t e r m 000 0 001 0 010 1 x ′ y z ′ 011 0 100 1 x y ′ z ′ 101 0 110 1 x y z ′ 111 1 x y z \begin{array}{|c|c|c|}
\hline && \R{\text{סכום מכפלות}} \\
xyz & f_{43}(x,y,z) \\
&& minterm \\
\hline 000 & 0 \\
001 & 0 \\
010 & 1 & x'yz' \\
011 & 0 \\
100 & 1 & xy'z' \\
101 & 0 \\
110 & 1 & xyz' \\
111 & 1 & xyz \\
\hline
\end{array} x yz 000 001 010 011 100 101 110 111 f 43 ( x , y , z ) 0 0 1 0 1 0 1 1 סכום מכפלות min t er m x ′ y z ′ x y ′ z ′ x y z ′ x yz f 43 ( x , y , z ) = x ′ y z ′ + x y ′ z ′ + x y z ′ + x y z = ∑ ( 2 , 4 , 6 , 7 ) f_{43}(x,y,z)=x'yz'+xy'z'+xyz'+xyz=\sum(2,4,6,7) f 43 ( x , y , z ) = x ′ y z ′ + x y ′ z ′ + x y z ′ + x yz = ∑ ( 2 , 4 , 6 , 7 ) 3. מכפלת סכומים (M a x t e r m Maxterm M a x t er m
מכפלת סכומים x y z f 43 ( x , y , z ) m a x t e r m 000 0 x + y + z 001 0 x + y + z ′ 010 1 011 0 x + y ′ + z ′ 100 1 101 0 x ′ + y + z ′ 110 1 111 1 \begin{array}{|c|c|c|}
\hline && \R{\text{מכפלת סכומים}} \\
xyz & f_{43}(x,y,z) \\
&& maxterm \\
\hline 000 & 0 & x+y+z \\
001 & 0 & x+y+z' \\
010 & 1 \\
011 & 0 & x+y'+z' \\
100 & 1 \\
101 & 0 & x'+y+z'\\
110 & 1 \\
111 & 1 \\
\hline
\end{array} x yz 000 001 010 011 100 101 110 111 f 43 ( x , y , z ) 0 0 1 0 1 0 1 1 מכפלת סכומים ma x t er m x + y + z x + y + z ′ x + y ′ + z ′ x ′ + y + z ′ f 43 ( x , y , z ) = ( x + y + z ) ( x + y + z ′ ) ( x + y ′ + z ′ ) ( x ′ + y + z ′ ) = ∏ ( 0 , 1 , 3 , 5 ) f_{43}(x,y,z)=(x+y+z)(x+y+z')(x+y'+z')(x'+y+z')=\prod (0,1,3,5) f 43 ( x , y , z ) = ( x + y + z ) ( x + y + z ′ ) ( x + y ′ + z ′ ) ( x ′ + y + z ′ ) = ∏ ( 0 , 1 , 3 , 5 ) 4. דיאגרמת מעגל לוגי
A N D N A N D X Y X ⋅ Y 0 0 0 0 1 0 1 0 0 1 1 1 X Y X ⋅ Y ‾ 0 0 1 0 1 1 1 0 1 1 1 0 A N D ( X , Y ) = X ⋅ Y N A N D ( X , Y ) = X ⋅ Y ‾ = X ‾ + Y ‾ \begin{matrix}
AND & NAND \\
\begin{array}{|c|c|c|}
\hline X & Y & X\cdot Y \\
\hline
0 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1 \\
\hline
\end{array} & \begin{array}{|c|c|c|}
\hline X & Y & \overline{X\cdot Y} \\
\hline
0 & 0 & 1 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 \\
\hline
\end{array} \\
AND(X,Y)=X\cdot Y \quad&\quad NAND(X,Y)=\overline{X\cdot Y}=\overline{X}+\overline{Y}
\end{matrix} A N D X 0 0 1 1 Y 0 1 0 1 X ⋅ Y 0 0 0 1 A N D ( X , Y ) = X ⋅ Y N A N D X 0 0 1 1 Y 0 1 0 1 X ⋅ Y 1 1 1 0 N A N D ( X , Y ) = X ⋅ Y = X + Y
O R N O R X Y X + Y 0 0 0 0 1 1 1 0 1 1 1 1 X Y X + Y ‾ 0 0 1 0 1 0 1 0 0 1 1 0 O R ( X , Y ) = X + Y N O R ( X , Y ) = X + Y ‾ = X ‾ ⋅ Y ‾ \begin{matrix}
OR & NOR \\
\begin{array}{|c|c|c|}
\hline X & Y & X+ Y \\
\hline
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 1 \\
\hline
\end{array} & \begin{array}{|c|c|c|}
\hline X & Y & \overline{X+Y} \\
\hline
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 0 \\
\hline
\end{array} \\
OR(X,Y)=X+ Y \quad&\quad NOR(X,Y)=\overline{X+ Y}=\overline{X}\cdot\overline{Y}
\end{matrix} OR X 0 0 1 1 Y 0 1 0 1 X + Y 0 1 1 1 OR ( X , Y ) = X + Y NOR X 0 0 1 1 Y 0 1 0 1 X + Y 1 0 0 0 NOR ( X , Y ) = X + Y = X ⋅ Y
X O R X N O R X Y X ⊕ Y 0 0 0 0 1 1 1 0 1 1 1 0 X Y X ⊕ Y ‾ 0 0 1 0 1 0 1 0 0 1 1 1 X O R ( X , Y ) = X ⊕ Y = X ‾ Y + X Y ‾ X N O R ( X , Y ) = X ⊕ Y ‾ = X ‾ ⋅ Y ‾ + X Y \begin{matrix}
XOR & XNOR \\
\begin{array}{|c|c|c|}
\hline X & Y & X \oplus Y \\
\hline
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 \\
\hline
\end{array} & \begin{array}{|c|c|c|}
\hline X & Y & \overline{X \oplus Y} \\
\hline
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1 \\
\hline
\end{array} \\
XOR(X,Y)=X \oplus Y=\overline{X}Y+X \overline{Y} & XNOR(X,Y)=\overline{X \oplus Y}=\overline{X}\cdot\overline{Y}+XY
\end{matrix} XOR X 0 0 1 1 Y 0 1 0 1 X ⊕ Y 0 1 1 0 XOR ( X , Y ) = X ⊕ Y = X Y + X Y XNOR X 0 0 1 1 Y 0 1 0 1 X ⊕ Y 1 0 0 1 XNOR ( X , Y ) = X ⊕ Y = X ⋅ Y + X Y
N O T X X ‾ 0 1 1 0 \begin{matrix}
NOT \\
\begin{array}{|c|c|}
\hline X & \overline{X} \\
\hline 0 & 1 \\
1 & 0 \\
\hline
\end{array}
\end{matrix} NOT X 0 1 X 1 0
לאחר צמצום:
f 43 ( x , y , z ) = x z ′ + x y + y z ′ f_{43}(x,y,z)=xz'+xy+yz' f 43 ( x , y , z ) = x z ′ + x y + y z ′
זהויות X O R XOR XOR
a ⊕ b = a ‾ b + a b ‾ a \oplus b=\overline{a}b+a \overline{b} a ⊕ b = a b + a b a ⊕ b = b ⊕ a a \oplus b = b \oplus a a ⊕ b = b ⊕ a a ⊕ a ‾ = 1 a \oplus \overline{a}=1 a ⊕ a = 1 a ⊕ 0 = a a \oplus 0 = a a ⊕ 0 = a a ⊕ a = 0 a \oplus a=0 a ⊕ a = 0 a ⊕ 1 = a ‾ a \oplus 1 = \overline{a} a ⊕ 1 = a a ⊕ ( b ⊕ c ) = ( a ⊕ b ) ⊕ c a \oplus (b \oplus c)=(a \oplus b)\oplus c a ⊕ ( b ⊕ c ) = ( a ⊕ b ) ⊕ c a ⊕ c = b ⊕ c ⟹ a = b a \oplus c = b \oplus c \implies a = b a ⊕ c = b ⊕ c ⟹ a = b a ( b ⊕ c ) = a b ⊕ a c a(b \oplus c)=ab \oplus ac a ( b ⊕ c ) = ab ⊕ a c מעבר למכפלת סכומים קנונית
f ( x , y , z ) = x ‾ + y z ‾ = x ‾ ( y + y ‾ ) ( z + z ‾ ) + y z ‾ ( x + 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 ‾ + x y z ‾ = ∑ ( 0 , 1 , 2 , 3 , 6 ) = ∏ ( 4 , 5 , 6 ) \begin{align*}
f(x,y,z)&=\overline{x}+y \overline{z}=\overline{x}(y+\overline{y})(z+\overline{z})+y \overline{z}(x+ \overline{x}) \\
&=\overline{x}yz+\overline{x}y \overline{z}+\overline{x}\cdot \overline{y}z+\overline{x}\cdot \overline{y}\cdot \overline{z}+xy \overline{z}+\overline{x}y \overline{z} \\
&=\overline{x}yz+\overline{x}y \overline{z}+\overline{x}\cdot \overline{y}z+\overline{x}\cdot \overline{y}\cdot \overline{z}+xy \overline{z} \\
&=\sum(0,1,2,3,6) \\
&=\prod(4,5,6)
\end{align*} f ( x , y , z ) = x + y z = x ( y + y ) ( z + z ) + y z ( x + x ) = x yz + x y z + x ⋅ y z + x ⋅ y ⋅ z + x y z + x y z = x yz + x y z + x ⋅ y z + x ⋅ y ⋅ z + x y z = ∑ ( 0 , 1 , 2 , 3 , 6 ) = ∏ ( 4 , 5 , 6 ) בודקים כל איבר. לכל משתנה α \alpha α ( α + α ‾ ) (\alpha+\overline{\alpha}) ( α + α )
מערכת פעולות שלמה
הגדרה 7 (מערכת פעולות שלמה)
קבוצת פעולות נקראת מערכת פעולות שלמה אם ניתן להציג בעזרתה את כל הפונקציות הלוגיות.
{ ⋅ , + , ′ } \LARGE \left\{ \cdot, +, ' \right\} { ⋅ , + , ′ } בעזרת דה-מורגן: { ⋅ , ′ } , { + , ′ } \left\{ \cdot, ' \right\},\left\{ +, ' \right\} { ⋅ , ′ } , { + , ′ } N O R , N A N D NOR,NAND NOR , N A N D
אם לא מתקיים : f ( a , … , a ) = a ′ f(a,\dots,a)=a' f ( a , … , a ) = a ′ אינה מערכת פעולות שלמה .
זה נכון רק לגבי מערכת שבה פונקציה יחידה.
האם הפעולה f ( a , b , c ) = a ′ + b c ′ f(a,b,c)=a'+bc' f ( a , b , c ) = a ′ + b c ′
נשים לב כי f ( a , a , a ) = a ‾ f(a,a,a)=\overline{a} f ( a , a , a ) = a
f ( a ‾ , b , b ‾ ) = a + b ⋅ b = a + b f(\overline{a},b,\overline{b})=a+b\cdot b=a+b f ( a , b , b ) = a + b ⋅ b = a + b קיבלנו כי קיימים השערים: N O T , O R NOT,OR NOT , OR
האם הפעולה f ( a , b , c ) = a ′ + b c f(a,b,c)=a'+bc f ( a , b , c ) = a ′ + b c
נשים לב כי f ( a , a , a ) = a ‾ + a ⋅ a = a ‾ + a = 1 f(a,a,a)=\overline{a}+a\cdot a=\overline{a}+a=1 f ( a , a , a ) = a + a ⋅ a = a + a = 1
f ( a , 0 , 0 ) = a ‾ f ( a ‾ , b , b ‾ ) = a + b \begin{matrix}
f(a,0,0)=\overline{a} \\
f(\overline{a},b, \overline{b})=a+b
\end{matrix} f ( a , 0 , 0 ) = a f ( a , b , b ) = a + b ואז היא תהיה מערכת פעולות כנדרש.
מערכת פעולות חצי שלמה
הגדרה 8 (מערכת פעולות חצי שלמה)
מערכת פעולות תקרא חצי שלמה אם הינה שלמה רק בתוספת קבועים(0 או 1 או שניהם)
תרגול
נתון רכיב צירופי בעל 3 כניסות ויציאה אחת המממש את הפונקציה f f f
f ( x , y , z ) = x y + z f(x,y,z)=xy+z f ( x , y , z ) = x y + z כמה רכיבים כאלה צריך בכדי לממש את הפונקציה g g g
g ( a , b , c ) = c ‾ ( c ‾ + b ) ( a ‾ + b ) g(a,b,c)=\overline{c}(\overline{c}+b)(\overline{a}+b) g ( a , b , c ) = c ( c + b ) ( a + b )
f f f
נתחיל בלפשט את ביטוי התוצאה:
g ( a , b , c ) = c ‾ ( a ‾ c + b c ‾ + a ‾ b + b b ) = c ‾ ( a ‾ ⋅ c ‾ + b ( c ‾ + a ‾ + 1 ⏟ 1 ) ) = ( a ‾ ⋅ c ‾ + b ) c ‾ = c ‾ ( a ‾ + b ) g(a,b,c)=\overline{c}(\overline{a}c+b \overline{c}+\overline{a}b+bb)=\overline{c}(\overline{a}\cdot \overline{c}+b(\underbrace{\overline{c}+\overline{a}+1}_{1}))=(\overline{a}\cdot \overline{c}+b)\overline{c}=\overline{c}(\overline{a}+b) g ( a , b , c ) = c ( a c + b c + a b + bb ) = c ( a ⋅ c + b ( 1 c + a + 1 )) = ( a ⋅ c + b ) c = c ( a + b ) בוודאות אין לנו דרך לייצר שער N O T NOT NOT f f f N O T NOT NOT g g g g g g
נתונה פונקצית המיתוג f ( x , y ) = x ‾ + y f(x,y)=\overline{x}+y f ( x , y ) = x + y f f f f f f { f , 0 } \left\{ f,0 \right\} { f , 0 } f f f { f , 1 } \left\{ f,1 \right\} { f , 1 } { f , 0 } \left\{ f,0 \right\} { f , 0 } { f , 1 } \left\{ f,1 \right\} { f , 1 } { f , 0 , 1 } \left\{ f,0,1 \right\} { f , 0 , 1 }
ננסה לבנות שער N O T NOT NOT
f ( x , x ) = x ‾ + x = 1 f(x,x)=\overline{x}+x=1 f ( x , x ) = x + x = 1 f ( x , 1 ) = x ‾ + 1 = 1 f(x,1)=\overline{x}+1=1 f ( x , 1 ) = x + 1 = 1 f ( 1 , x ) = 1 ‾ + x = 0 + x = x f(1,x)=\overline{1}+x=0+x=x f ( 1 , x ) = 1 + x = 0 + x = x נשים לב כי לא קיבלנו x ‾ \overline{x} x
עבור { f , 0 } \left\{ f,0 \right\} { f , 0 }
f ( x , 0 ) = x ‾ + 0 = x ‾ f(x,0)=\overline{x}+0=\overline{x} f ( x , 0 ) = x + 0 = x f ( x ‾ , y ) = x + y f(\overline{x},y)=x+y f ( x , y ) = x + y יצרנו שערי N O T , O R NOT,OR NOT , OR
f ( x ‾ , y ) = f ( f ( x , 0 ) , y ) = x + y f(\overline{x},y)=f(f(x,0),y)=x+y f ( x , y ) = f ( f ( x , 0 ) , y ) = x + y לכן, ב הוא הנכון.
בתשובה ג', נשים לב כי זה זהה ל-א', שכן אנו נוכל לייצר 1 1 1 f ( x , x ) f(x,x) f ( x , x )
נתונה קבוצת האופרטורים Δ \Delta Δ
את כל הפונקציות הלוגיות בעלות משתנה אחד בלבד .
את הפונקציה f ( x , y , z ) = x ‾ y + y ‾ z f(x,y,z)=\overline{x}y+\overline{y}z f ( x , y , z ) = x y + y z
תזכורת: קבוצה של אופרטורים וקבועים נקראת שלמה , אם ניתן לבטא באמצעותה כל פונקציית מיתוג.
מה ניתן להגיד בוודאות על Δ \Delta Δ Δ \Delta Δ Δ \Delta Δ { Δ , 0 } \left\{ \Delta,0 \right\} { Δ , 0 } Δ \Delta Δ { Δ , 1 } \left\{ \Delta,1 \right\} { Δ , 1 } Δ \Delta Δ { Δ , 0 , 1 } \left\{ \Delta,0,1 \right\} { Δ , 0 , 1 }
נשים לב כי אלו פונקציות בעלות משתנה 1:
f ( x ) = x f ( x ) = x ‾ f ( x ) = 1 f ( x ) = 0 f(x)=x \qquad f(x)=\overline{x} \qquad f(x)=1 \qquad f(x)=0 f ( x ) = x f ( x ) = x f ( x ) = 1 f ( x ) = 0 לכן, קבוצת האופרטורים Δ \Delta Δ Δ \Delta Δ { Δ , 0 , 1 } \left\{ \Delta,0,1 \right\} { Δ , 0 , 1 } Δ \Delta Δ
Δ ‾ : 1. f ( x , y , z ) = x ‾ y + y ‾ z 2. x f 1 f 2 f 3 f 4 0 0 0 1 1 1 0 1 0 1 \begin{matrix}
\underline{\Delta}: \\
1. & f(x,y,z)=\overline{x}y+\overline{y}z \\
2. & \begin{array}{|c|c|c|c|}
\hline x & f_{1} & f_{2} & f_{3} & f_{4} \\
\hline 0 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 \\
\hline
\end{array}
\end{matrix} Δ : 1. 2. f ( x , y , z ) = x y + y z x 0 1 f 1 0 0 f 2 0 1 f 3 1 0 f 4 1 1 כעת, נבדוק האם יש A N D / O R AND/OR A N D / OR f f f
f ( x ‾ , y , 0 ) = x y f(\overline{x},y,0)=xy f ( x , y , 0 ) = x y זהו בדיוק שער A N D AND A N D א היא התשובה הנכונה.
איזו טענה נכונה בדבר פונקצית מיתוג f ( a , b ) f(a,b) f ( a , b ) f ( a ‾ , b ‾ ) = f ( a , b ) f(\overline{a},\overline{b})=f(a,b) f ( a , b ) = f ( a , b ) f f f X O R XOR XOR f f f X N O R XNOR XNOR f f f X O R XOR XOR X N O R XNOR XNOR
נתחיל מלעשות טבלת אמת:
a b f ~ f 1 f 2 f 3 f 4 0 0 α 0 0 1 1 0 1 β 0 1 0 1 1 0 β 0 1 0 1 1 1 α 0 0 1 1 \begin{array}{|c|c|c|cccc|}
\hline a & b & \tilde{f} & f_{1} & f_{2} & f_{3} & f_{4} \\
\hline 0 & 0 & \alpha & 0 & 0 & 1 & 1 \\
0 & 1 & \beta & 0 & 1 & 0 & 1 \\
1 & 0 & \beta & 0 & 1 & 0 & 1 \\
1 & 1 & \alpha & 0 & 0 & 1 & 1 \\
\hline
\end{array} a 0 0 1 1 b 0 1 0 1 f ~ α β β α f 1 0 0 0 0 f 2 0 1 1 0 f 3 1 0 0 1 f 4 1 1 1 1 נשים לב כי תחילה קיימת פונקציה, לכן, א' איננו נכון.f 1 f_{1} f 1 0 0 0 f 2 f_{2} f 2 X O R XOR XOR f 3 f_{3} f 3 X N O R XNOR XNOR f 4 f_{4} f 4 אף תשובה איננה נכונה .
נתונה הפונקציה f ( x , y , z , w ) = ∏ ( 8 , 9 , 10 , 11 ) f(x,y,z,w)=\prod(8,9,10,11) f ( x , y , z , w ) = ∏ ( 8 , 9 , 10 , 11 ) אינה מהווה מערכת פעולות שלמה?{ f , n o t } \left\{ f,not \right\} { f , n o t } { f ‾ , n o t } \left\{ \overline{f},not \right\} { f , n o t } { f , 1 } \left\{ f,1 \right\} { f , 1 } { f , 0 } \left\{ f,0 \right\} { f , 0 } { f ‾ , 1 } \left\{ \overline{f},1 \right\} { f , 1 }
נשים בטבלת אמת(כלומר, נקח את המספרים, שאנחנו יודעים שתוצאתם 0 ונעביר אותם לביטים):
x y z w f 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 \begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline x & y & z & w & f \\
\hline 1 & 0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 \\
\hline
\end{array} x 1 1 1 1 y 0 0 0 0 z 1 1 0 0 w 1 0 0 1 f 0 0 0 0 נשים לב כי אם אנחנו נועלים את x , y x,y x , y 1 , 0 1,0 1 , 0 f = x y ‾ ‾ f=\overline{x \overline{y}} f = x y ( x , y ) = ( 1 , 0 ) (x,y)=(1,0) ( x , y ) = ( 1 , 0 ) f = 0 f=0 f = 0
f = x y ‾ ‾ = x ‾ + y f=\overline{x \overline{y}} =\overline{x}+y f = x y = x + y לכן, נקבל שבתוספת N O T NOT NOT 0 0 0 1 1 1 N O T NOT NOT f f f f ( x , x ) = x ‾ + x = 1 f(x,x)=\overline{x}+x=1 f ( x , x ) = x + x = 1
עם f ‾ \overline{f} f N O T NOT NOT { f ‾ , 1 } \left\{ \overline{f},1 \right\} { f , 1 }
מערכת פעולות שלמה לא בהכרח אומר שהיפוך המערכת הוא מערכת פעולות שלמה.N O R NOR NOR N O R ‾ = O R \overline{NOR}=OR NOR = OR
