Chap 2
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Chap 2 as PDF for free.
More details
- Words: 6,381
- Pages: 24
١
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ٢-١ﺗﻌﺮﯾﻒ اﺻﻮﻟﯽ ﺟﺒﺮ ﺑﻮل
در ﺳﺎل ١٨۵۴ﺟﻮرج ﺑﻮل روش اﺻﻮﻟﯽ ﺑﺮاﯼ ﻣﻨﻄﻖ ﻣﻌﺮﻓﯽ ﻧﻤﻮد و ﺑﺪﯾﻦ ﻃﺮﯾﻖ ﯾﮏ ﺳﻴﺴﺘﻢ ﺟﺒﺮﯼ را ﭘﺎﯾﻪ رﯾﺰﯼ ﮐﺮد ﮐﻪ اﻣﺮوز ﺟﺒﺮ ﺑﻮل ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮد .ﺑﺮاﯼ ﺗﻌﺮﯾﻒ ﻣﺴﺘﺪل ﺟﺒﺮ ﺑﻮل ،ﻣﺎ اﺻﻮل ﻓﺮﻣﻮﻟﻪ ﺷﺪﻩ ﺑﻮﺳﻴﻠﻪ هﺎﻧﺘﻴﻨﮕﺘﻮن در ١٩٠۴را ﺑﻪ ﮐﺎر ﺧﻮاهﻴﻢ ﺑﺮد .اﯾﻦ اﺻﻮل ﺑﺮاﯼ ﺗﻌﺮﯾﻒ ﺟﺒﺮ ﺑﻮل ﻣﻨﺤﺼﺮ ﺑﻪ ﻓﺮد ﻧﻴﺴﺘﻨﺪ و اﺻﻮل دﯾﮕﺮﯼ ﻧﻴﺰ در ﺁن ﺑﮑﺎر رﻓﺘﻪ اﻧﺪ . ﺟﺒﺮ ﺑﻮل ﯾﮏ ﺳﺎﺧﺘﺎر ﺟﺒﺮﯼ اﺳﺖ ﮐﻪ ﺑﺎ ﻋﻨﺎﺻﺮ ﻣﺠﻤﻮﻋﻪ Bهﻤﺮاﻩ ﺑﺎ دو ﻋﻤﻠﮕﺮ ) (+و )(. ﺗﻌﺮﯾﻒ ﺷﺪﻩ و داراﯼ اﺻﻮل زﯾﺮ ) اﺻﻮل هﺎﻧﺘﻴﻨﮕﺘﻮن ( ﺑﺎﺷﺪ : ( a) -١ﻣﺠﻤﻮﻋﻪ ﻧﺴﺒﺖ ﺑﻪ ﻋﻤﻠﮕﺮ ) (.ﺑﺴﺘﻪ ﺑﺎﺷﺪ . ) ( bﻣﺠﻤﻮﻋﻪ ﻧﺴﺒﺖ ﺑﻪ ﻋﻤﻠﮕﺮد ) (.ﺑﺴﺘﻪ ﺑﺎﺷﺪ . ( a) -٢ﻋﻨﺼﺮ ﺧﻨﺜﯽ در ﻣﺠﻤﻮﻋﻪ ﺑﺮاﯼ ) (+ﺑﺮاﺑﺮ ﺑﺎ ٠ﺑﺎﺷﺪ .
x+0=0+ x= x (b) -٣ﻋﻨﺼﺮ ﺧﻨﺜﯽ در ﻣﺠﻤﻮﻋﻪ ﺑﺮاﯼ ) (.ﺑﺮاﺑﺮ ١ﺑﺎﺷﺪ .
x.1 = 1.x = x (a) -۴ﻣﺠﻤﻮﻋﻪ ﻧﺴﺒﺖ ﺑﻪ ) (+داراﯼ ﺧﺎﺻﻴﺖ ﺟﺎﺑﺠﺎﯾﯽ ﺑﺎﺷﺪ .
x+ y= y+ x ) (bﻣﺠﻮﻋﻪ ﻧﺴﺒﺖ ﺑﻪ ) (.داراﯼ ﺧﺎﺻﻴﺖ ﺟﺎﺑﺠﺎﯾﯽ ﺑﺎﺷﺪ :
x. y = y..x (.) ( a) -۴روﯼ ) (+داراﯼ ﺧﺎﺻﻴﺖ ﭘﺨﺸﯽ اﺳﺖ . ) (+) (bروﯼ ) (.داراﯼ ﺧﺎﺻﻴﺖ ﭘﺨﺸﯽ اﺳﺖ .
)x.( y + z) = ( x. y) + ( x.z
)x + ( y.z) = ( x + y).( x + z
٢
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ -۵ﺑﻪ ازاﯼ هﺮ ﻋﻨﺼﺮ
x∈ B
ﻋﻨﺼﺮﯼ ﻣﺜﻞ
x∈ B
وﺟﻮد داﺷﺘﻪ ﺑﺎﺷﺪ ) اﯾﻦ ﻋﻨﺼﺮ
ﻣﮑﻤﻞ ﺧﻮاﻧﺪﻩ ﻣﯽ ﺷﻮد ( ﺑﻄﻮرﯼ ﮐﻪ : )( a
x + x′ =1
)( b
x.x ′ = 0
-۶ﺣﺪاﻗﻞ دو ﻋﻨﺼﺮ ﻣﺎﻧﻨﺪ x, y ∈ Bﻣﻮﺟﻮد ﺑﺎﺷﻨﺪ ﺑﻄﻮرﯾﮑﻪ x ≠ y :
ازﻣﻘﺎﯾﺴﻪ ﺟﺒﺮ
ﺑﻮل ﺑﺎ رﯾﺎﺿﻴﺎت ﺟﺒﺮﯼ ﻣﻌﻤﻮﻟﯽ ) ﻣﻴﺪان اﻋﺪاد ﺣﻘﻴﻘﯽ ( اﺧﺘﻼﻓﺎت زﯾﺮ ﻣﻼﺣﻈﻪ ﻣﯽ ﮔﺮدﻧﺪ : -١اﺻﻮل هﺎﻧﺘﻴﻨﮕﺘﻮن ﺷﺎﻣﻞ اﺻﻞ اﺷﺘﺮاﮎ ﭘﺬﯾﺮﯼ ﻧﻴﺴﺘﻨﺪ .اﯾﻦ ﻗﺎﻧﻮن ﺑﺮاﯼ ﺟﺒﺮ ﺑﻮل ﻧﻴﺰ وﺟﻮد دارد و ﻣﯽ ﺗﻮان ﺁن را ﺑﺮاﯼ هﺮ دو ﻋﻤﻠﮕﺮ از ﺳﺎﯾﺮ اﺻﻮل ﺑﺪﺳﺖ ﺁورد . -٢ﻗﺎﻧﻮن ﺗﻮزﯾﻊ ﭘﺬﯾﺮﯼ ) (+و ) ( .اﺧﺘﻼف ﺑﻌﺪﯼ اﺳﺖ .راﺑﻄﻪ :
)x + ( y.z) = ( x + y).) x + z ﺑﺮاﯼ ﺟﺒﺮ ﺑﻮل ﻣﻌﺘﺒﺮ وﻟﯽ ﺑﺮاﯼ ﺟﺒﺮ ﻣﻌﻤﻮﻟﯽ ﻗﺎﺑﻞ ﻗﺒﻮل ﻧﻴﺴﺖ . -٣ﺟﺒﺮ ﺑﻮل ﻣﻌﮑﻮس ﺟﻤﻊ و ﺿﺮب را ﻧﺪارد ،ﺑﻨﺎﺑﺮاﯾﻦ ﺗﻔﺮﯾﻖ و ﺗﻘﺴﻴﻢ ﻣﻔﻬﻮم ﻧﺨﻮاهﻨﺪ داﺷﺖ . -۴اﺻﻞ ۵ﻋﻤﻠﮕﺮد دﯾﮕﺮﯼ ﺑﻨﺎم ﻣﮑﻤﻞ را ﻣﻌﺮﻓﯽ ﻣﯽ ﻧﻤﺎﯾﺪ ﮐﻪ در ﺟﺒﺮ ﻣﻌﻤﻮﻟﯽ وﺟﻮد ﻧﺪارد . -۵ﺟﺒﺮ ﻣﻌﻤﻮﻟﯽ در ﻣﻮرد اﻋﺪاد ﺣﻘﻴﻘﯽ اﺳﺖ ﮐﻪ ﺑﯽ ﻧﻬﺎﯾﺖ ﻋﻨﺼﺮ را ﺷﺎﻣﻞ ﻣﯽ ﺷﻮد . ﺟﺒﺮ ﺑﻮل ﺑﺎ ﻋﻨﺎﺻﺮﯼ از ﻣﺠﻤﻮﻋﻪ Bﮐﻪ اﻟﺒﺘﻪ ﺗﺎ ﮐﻨﻮن ﻣﻌﺮﻓﯽ ﻧﺸﺪﻩ اﻧﺪ ﺳﺮو ﮐﺎر داﺷﺖ وﻟﯽ درﺟﺒﺮ ﺑﻮل دو ارزﺷﯽ ﯾﺎ دو ﻣﻘﺪارﯼ ﮐﻪ در زﯾﺮ ﺗﻌﺮﯾﻒ ﺷﺪﻩ B ،ﯾﮏ ﻣﺠﻤﻮﻋﻪ دو ﻋﻨﺼﺮﯼ اﺳﺖ ﮐﻪ اﯾﻦ دو ﻋﻨﺼﺮ ٠و ١ﻣﯽ ﺑﺎﺷﻨﺪ . ٢-٢ﻗﻀﻴﻪ هﺎﯼ اﺻﻠﯽ و ﺧﻮاص ﺟﺒﺮ ﺑﻮل
٣
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
اﺻﻮل هﺎﻧﺘﻴﮕﺘﻮن ﺑﺼﻮرت ﺟﻔﺖ ﺟﻔﺖ ﻟﻴﺴﺖ و ﺑﺎ ﻗﺴﻤﺖ هﺎﯼ ) ( aو ) ( bﻣﺸﺨﺺ ﺷﺪ .هﺮ ﯾﮏ از اﯾﻦ دو را ﻣﯽ ﺗﻮان از دﯾﮕﺮﯼ ﺑﺪﺳﺖ ﺁورد ﺑﺸﺮط اﯾﻨﮑﻪ ﻋﻤﻠﮕﺮهﺎ و ﻧﻴﺰ ﻋﻨﺎﺻﺮ ﺧﻨﺜﯽ ﺗﻌﻮﯾﺾ ﺷﻮﻧﺪ .اﯾﻦ ﺧﺎﺻﻴﺖ ﻣﻬﻢ درﺟﺒﺮ ﺑﻮل ﺑﻪ اﺻﻞ دوﮔﺎﻧﮕﯽ ﻣﻌﺮوف اﺳﺖ و ﺑﻴﺎن ﻣﯽ دارد ﮐﻪ هﺮ ﻋﺒﺎرت ﺟﺒﺮﯼ ﻣﻨﺘﺠﻪ از اﺻﻮل ﺟﺒﺮ ﺑﻮل ﺣﺘﯽ ﺑﺎ ﺗﻌﻮﯾﺾ ﻋﻤﻠﮕﺮ هﺎ و ﻋﻨﺎﺻﺮ ﺧﻨﺜﯽ ﺑﺎز هﻢ ﻣﻌﺘﺒﺮ ﻣﯽ ﺑﺎﺷﺪ .در ﺟﺒﺮ ﺑﻮل دو ارزﺷﯽ ﻋﻨﺎﺻﺮ ﺧﻨﺜﯽ و ﺧﻮد ﻋﻨﺎﺻﺮ ﻣﺤﻤﻮﻋﻪ Bﯾﮑﺴﺎﻧﻨﺪ ١ :و ٠اﺻﻞ دوﮔﺎﻧﮕﯽ ﮐﺎرﺑﺮدهﺎﯼ ﻓﺮاواﻧﯽ دارد .اﮔﺮ دو ﮔﺎن ﯾﮏ ﻋﺒﺎرت ﺟﺒﺮﯼ ،ﻣﻮرد ﻧﻈﺮ ﺑﺎﺷﺪ ﺗﻨﻬﺎ ﮐﺎﻓﯽ اﺳﺖ ﻋﻤﻠﮕﺮهﺎﯼ ORو ANDﺗﻌﻮﯾﺾ ﺷﺪﻩ و ٠هﺎ ﺑﻪ ١هﺎ و هﻤﭽﻨﻴﻦ ١هﺎ ﺑﻪ ٠هﺎ ﺗﺒﺪﯾﻞ ﮔﺮدﻧﺪ . ﺗﺌﻮرﯼ هﺎﯼ اﺳﺎﺳﯽ ﺟﺪول ) (٢-١ﺷﺶ ﺗﺌﻮرﯼ و ﭼﻬﺎر اﺻﻞ از ﺟﺒﺮ ﺑﻮل را در ﺑﺮ دارد .در ﺳﻤﺖ ﭼﭗ رواﺑﻂ ، ﺷﻤﺎرﻩ اﺻﻮل ﺑﮑﺎر رﻓﺘﻪ ﻧﻮﺷﺘﻪ ﺷﺪﻩ اﺳﺖ . ﺟﺪول ) (٢-١اﺻﻮل و ﻗﻀﺎﯾﺎﯼ ﺟﺒﺮ ﺑﻮل (
(b) xy = yx (b) x (yz) = (xy)z )(b) x+yz = (x+y)(x+z
(a) x + 0 = x ( a) x + xَ = ١ (a) x + x = x (a) x + 1 = 1 (xَ )َ =x (a) x+y=y+x (a) x+(y+z) = (x+y)+z (a) x(y+z) = xy+xz
(b) x.1 = x (b) x.x = 0 (b) x.x = x (b) x .0 = 0
)(b) (xy) = x+y (b) x(x+y) = x
(a) (x+y) = x y (a) x + xy = x
اﺻﻞ ٢ اﺻﻞ ۵ ﺗﺌﻮرﯼ ١ ﺗﺌﻮرﯼ ٢ ﺗﺌﻮرﯼ ٣رﺟﻌﺖ اﺻﻞ ٣ﺟﺎﺑﺠﺎﯾﯽ ﺗﺌﻮرﯼ ۴ﺷﺮﮐﺖ ﭘﺬﯾﺮﯼ اﺻﻞ ۴ﺗﻮزﯾﻊ ﭘﺬﯾﺮﯼ ﯾﺎ ﭘﺨﺶ ﺗﺌﻮرﯼ ۵دﻣﻮرﮔﺎن ﺗﺌﻮرﯼ ۶ﺟﺬب
٢-٣ﺗﻮاﺑﻊ ﺑﻮل ﯾﮏ ﻣﺘﻐﻴﻴﺮ دودوﯾﯽ ﻣﯽ ﺗﻮاﻧﺪ ﯾﮑﯽ از دو ﻣﻘﺪار ٠ﯾﺎ ١را اﺧﺘﻴﺎر ﮐﻨﺪ .ﯾﮏ ﺗﺎﺑﻊ ﺑﻮل ﻋﺒﺎرﺗﯽ اﺳﺖ ﮐﻪ از ﻣﺘﻐﻴﺮهﺎﯼ دودوﯾﯽ ،ﻋﻤﻠﮕﺮ هﺎﯼ NOT ، AND ، ORﭘﺮاﻧﺘﺰ هﺎ و
٤
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﻋﻼﻣﺖ ﺗﺴﺎوﯼ ﺗﺸﮑﻴﻞ ﺷﺪﻩ اﺳﺖ .ﺑﻪ ازاﯼ ﻣﻘﺎدﯾﺮ ﻣﻔﺮوﺿﯽ از ﻣﺘﻐﻴﺮهﺎ ﺗﺎﺑﻊ ﻓﻘﻂ ﻣﯽ ﺗﻮاﻧﺪ ٠ﯾﺎ ١ﺑﺎﺷﺪ .ﻣﺜﻼً ﺗﺎﺑﻊ ﺑﻮل F = xyz ′را در ﻧﻈﺮ ﺑﮕﻴﺮﯾﺪ .ﺗﺎﺑﻊ f1ﺑﺮاﺑﺮ ﺑﺎ ١اﺳﺖ
1
ﺑﺸﺮﻃﯽ ﮐﻪ y=1 ، x=1و zَ =1ﺑﺎﺷﺪ ،در ﻏﻴﺮ اﯾﻦ ﺻﻮرت F = 0ﺧﻮاهﺪ ﺑﻮد .ﺑﺮاﯼ
1
ﻧﻤﺎﯾﺶ ﯾﮏ ﺗﺎﺑﻊ ﺑﻔﺮم ﺟﺪول درﺳﺘﯽ ﻧﻴﺎز ﺑﻪ 2nﺗﺮﮐﻴﺐ از ١هﺎ و ٠هﺎ ﻣﺮﺑﻮط ﺑﻪ nﺑﻪ ﺗﻐﻴﻴﺮ دودوﯾﯽ و ﺳﺘﻮﻧﯽ ﯾﮑﻪ در ﺁن ﻣﻘﺪار ﺗﺎﺑﻊ ﺑﺮاﺑﺮ ٠ﯾﺎ ١اﺳﺖ ،دارﯾﻢ .از ﺟﺪول )(٢-٢ دﯾﺪﻩ ﻣﯽ ﺷﻮد وﮐﻪ ﺑﺮاﯼ ﺳﻪ ﻣﺘﻐﻴﺮ ٨ﺣﺎﻟﺖ ﺟﺪا ﻣﯽ ﺗﻮان در ﻧﻈﺮ ﮔﺮﻓﺖ .در ﺟﺪول )-٢ ، (٢ﭼﻬﺎر ردﯾﻒ ﺁﺧﺮ ﻣﺴﺎوﯼ ١و xyدر ردﯾﻔﻬﺎﯼ ٠٠١و ١٠١ﺑﺮاﺑﺮ ٠١اﺳﺖ .ﺗﺮﮐﻴﺐ ﺁﺧﺮﯼ دﻻﻟﺖ ﺑﺮ x=١ﻧﻴﺰ دارد .ﺑﻨﺎﺑﺮاﯾﻦ ﺑﺮاﯼ F2=١ﭘﻨﺞ ﺣﺎﻟﺖ وﺟﻮد دارد . ﺟﺪول ) (٢-٢ﺟﺪول درﺳﺘﯽ ﺑﺮاﯼ , F = xy ′ + xz 4
F = xyz F = x + y ′z , F = x ′y ′z + x ′yz + xy 1 2 3
F4
F3
F2
F1
Z
y
x
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
1
0
1
1
0
0
1
1
0
1
1
1
0
0
0
1
1
1
1
0
1
0
1
0
0
1
0
0
1
1
0
0
1
1
1
1
1
٥
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ﻋﻤﻠﻴﺎت ﺟﺒﺮﯼ
ﻟﻴﺘﺮال ،ﯾﮏ ﻣﺘﻐﻴﺮ ﺑﺎ ﭘﺮﯾﻢ ﯾﺎ ﺑﺪون ﭘﺮﯾﻢ اﺳﺖ .وﻗﺘﯽ ﮐﻪ ﯾﮏ ﺗﺎﺑﻊ ﺑﻮﺳﻴﻠﻪ ﮔﻴﺖ ﻣﻨﻄﻘﯽ ﭘﻴﺎدﻩ ﺷﻮد هﺮ ﻟﻴﺘﺮال در ﺗﺎﺑﻊ ﻣﻌﺮوف ﯾﮏ ورودﯼ ﺑﻪ ﯾﮏ ﮔﻴﺖ و هﺮ ﺟﻤﻠﻪ ﻣﻨﻄﻘﯽ ﻧﻴﺰ ﺗﻮﺳﻂ ﯾﮏ ﮔﻴﺖ ﺳﺎﺧﺘﻪ ﻣﯽ ﺷﻮد .ﻣﯽ ﻧﻴﻤﻢ ﮐﺮدن ﺗﻌﺪاد ﻣﺘﻐﻴﺮهﺎ و ﺟﻤﻼت ،ﻧﺘﻴﺠﻪ اش ﺳﺎﺧﺖ دﺳﺘﮕﺎهﯽ ﺑﺎ ﻗﻄﻌﺎت ﮐﻤﺘﺮ اﺳﺖ . اﻟﺒﺘﻪ هﻤﻴﺸﻪ ﻣﻤﮑﻦ ﻧﻴﺴﺖ ﮐﻪ هﺮ دو را ﺑﺎ هﻢ ﮐﺎهﺶ داد .ﻓﻌﻼً ﻣﺎ ﻣﯽ ﻧﻴﻤﻢ ﺳﺎزﯼ را ﻓﻘﻂ ﺑﻪ ﻣﺘﻐﻴﺮهﺎ ﻣﺤﺪود ﻣﻴﮑﻨﻴﻢ ﺗﻌﺪاد ﻣﺘﻐﻴﺮ هﺎ در ﺗﺎﺑﻊ ﺑﻮل ﻣﯽ ﺗﻮاﻧﺪ ﺑﺎ ﯾﮏ ﺳﺮﯼ اﻋﻤﺎل ﺟﺒﺮﯼ ﻣﯽ ﻧﻴﻤﻢ ﮔﺮدد ،ﻣﺘﺎﺳﻔﺎﻧﻪ ﻗﻮاﻧﻴﻦ ﻣﺸﺨﺺ و ﻣﻌﻴﻨﯽ ﮐﻪ ﺗﻀﻤﻴﻦ ﮐﻨﻨﺪﻩ ﻓﺮم ﻧﻬﺎﯾﯽ ﺑﺎﺷﺪ وﺟﻮد ﻧﺪارد .ﺗﻨﻬﺎ روش ﻣﻮﺟﻮد ﺳﻌﯽ در ﮐﺎهﺶ ﻣﺪار و ﺗﺪاوم اﯾﻦ ﻋﻤﻞ ﺑﺎ اﺳﺘﻔﺎدﻩ از اﺻﻮل اوﻟﻴﻪ ،ﺗﺌﻮرﯼ هﺎﯼ اﺻﻠﯽ و هﺮ روش ﻋﻤﻠﻴﺎﺗﯽ دﯾﮕﺮﯼ ،ﮐﻪ ﺿﻤﻦ ﻋﻤﻞ ﺑﺎ ﺁﻧﻬﺎ ﺣﺎﺻﻞ ﻣﯽ ﮔﺮدد ،ﻣﯽ ﺑﺎﺷﺪ . ﻣﺜﺎل : ٢-١ﺗﺎﺑﻊ ﺑﻮﻟﯽ زﯾﺮ را از ﻧﻈﺮ ﺗﻌﺪاد ﻣﺘﻐﻴﺮهﺎ ﻣﯽ ﻧﻴﻤﻢ ﮐﻨﻴﺪ .
1. x + x′y = ( x + x′)( x + y) = 1.( x + y) = x + y 2. x( x′ + y) = xx′ + xy = 0 + xy = xy 3. x′y′z + x′yz + yz = x′z( y′ + y) + xy′ = x′z + xy′ )4.xy + x′z + yz = xy + x′z + yz( x + x′ = xy + x′z + xyz + x′yz )= xy(1 + z) + x′z (1 + y = xy + x′z )5. ( x + y)( x′ + z )( y + z) = ( x + y)( x′ + z ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ دو ﮔﺎﻧﻪ ﺑﻮدن ﺗﺎﺑﻊ ۴ ﺗﺎﺑﻊ ١و ٢دوﮔﺎن ﯾﮑﺪﯾﮕﺮﻧﺪ و ﻋﺒﺎرت دوﮔﺎﻧﯽ رادر ﻣﺮاﺣﻞ ﻣﺮﺑﻮط ﺑﻪ ﺧﻮد ﺑﮑﺎر ﻣﯽ ﺑﺮﻧﺪ . ﺗﺎﺑﻊ ٣هﻢ ارزﯼ ﺗﻮاﺑﻊ F4,F3ﺑﺤﺚ ﺷﺪﻩ در ﻗﺒﻞ را ﻧﺸﺎن ﻣﯽ دهﺪ .ﭼﻬﺎرﻣﻴﻦ ﺗﺎﺑﻊ روﺷﻨﮕﺮ اﯾﻦ واﻗﻌﻴﺖ اﺳﺖ ﮐﻪ اﻓﺰاﯾﺶ در ﺗﻌﺪاد ﻣﺘﻔﻴﺮهﺎ ﮔﺎهﯽ اوﻗﺎت ﺳﺒﺐ ﺳﺎدﻩ ﺗﺮ
٦
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺷﺪن ﻋﺒﺎرت ﻧﻬﺎﯾﯽ ﻣﯽ ﮔﺮدد .ﺗﺎﺑﻊ ۵۴ﻣﺴﺘﻘﻴﻤﺎً ﺳﺎدﻩ ﻧﺸﺪﻩ اﺳﺖ وﻟﯽ ﺑﺎ اﺳﺘﻔﺎدﻩ از دوﮔﺎن ﻣﺮاﺣﻞ رﻣﺮﺑﻮط ﺑﻪ ﺗﺎﺑﻊ ۴ﻣﯽ ﺗﻮاﻧﺪ ﺣﺎﺻﻞ ﮔﺮدد . ﻣﮑﻤﻞ ﯾﮏ ﺗﺎﺑﻊ ﻣﮑﻤﻞ ﯾﮏ ﺗﺎﺑﻊ Fﺗﺎﺑﻌﯽ اﺳﺖ ﻣﺎﻧﻨﺪ َ Fﮐﻪ ﺑﺎ ﺗﻌﻮﯾﺾ ٠هﺎ ﺑﻪ ١هﺎ و ١هﺎ ﺑﻪ ٠هﺎ در ﻣﻘﺪار Fﺣﺎﺻﻞ ﻣﯽ ﮔﺮدد .ﻣﮑﻤﻞ ﯾﮏ ﺗﺎﺑﻊ ﻣﻤﮑﻦ اﺳﺖ ﺑﺎ اﺳﺘﻔﺎدﻩ از ﺗﺌﻮرﯼ دﻣﻮرﮔﺎن ﻧﻴﺰ ﺑﺪﺳﺖ ﻣﯽ ﺁﯾﺪ .زوج ﻗﻮاﻧﻴﻦ دﻣﻮرﮔﺎن ﺑﺮاﯼ دو ﻣﺘﻐﻴﻴﺮ در ﺟﺪول ) (٢-١ﻟﻴﺴﺖ ﺷﺪﻩ اﻧﺪ .ﺗﺌﻮرﯼ هﺎﯼ دﻣﻮرﮔﺎن ﻗﺎﺑﻞ ﺗﻌﻤﻴﻢ ﺑﺮاﯼ ﺳﻪ ﻣﺘﻐﻴﺮ و ﯾﺎ ﺑﻴﺸﺘﺮ از ﺁن ﻧﻴﺰ هﺴﺘﻨﺪ . ﻓﺮم ﺳﻪ ﻣﺘﻐﻴﺮ ﺗﺌﻮرﯼ اول دﻣﻮرﮔﺎن در زﯾﺮ ﺁﻣﺪﻩ اﺳﺖ .اﺻﻮل و ﺗﺌﻮرﯼ هﺎﯼ ﺑﮑﺎر رﻓﺘﻪ هﻤﺎن هﻤﺎﯾﯽ هﺴﺘﻨﺪ ﮐﻪ در ﺟﺪول ) (٢-١ﺁوردﻩ ﺷﺪﻩ اﻧﺪ .
( A + B + C)′ = ( A + X )′
ﺑﺎ ﻓﺮض B + C = A ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺗﺌﻮرﯼ ( a) -۵دﻣﻮرﮔﺎن ﺑﺎ ﺟﺎﯾﮕﺰﯾﻨﯽ B + C = X
= A′X ′
= A′.( B + C )′
ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺗﺌﻮرﯼ ( a) -۴ﺷﺮﮐﺖ ﭘﺬﯾﺮﯼ
= A′B ′C ′
ﺗﺌﻮرﯼ هﺎﯼ دﻣﻮرﮔﺎن ﺑﺮاﯼ هﺮ ﺗﻌﺪاد از ﻣﺘﻐﻴﺮ هﺎ اﺑﺘﺪ ﺑﻪ ﺷﮑﻞ دو ﻣﺘﻐﻴﺮﻩ در ﺁﻣﺪﻩ و ﺳﭙﺲ ﺑﺎ ﺟﺎﯾﮕﺰﯾﻨﯽ هﺎﯼ ﻣﺘﻮاﻟﯽ ،ﻣﺸﺎﺑﻪ ﺑﺎ ﺁﻧﭽﻪ در ﻓﻮق دﯾﺪﻩ ﺷﺪ ،ﻧﺘﻴﺠﻪ ﻧﻬﺎﯾﯽ ﺣﺎﺻﻞ ﻣﯽ ﮔﺮدد . اﯾﻦ ﺗﺌﻮرﯾﻬﺎ ﻣﯽ ﺗﻮاﻧﺪ ﺑﻪ ﺻﻮرت زﯾﺮ ﻋﻤﻮﻣﻴﺖ دادﻩ ﺷﻮﻧﺪ .
( A + B + C + D + ... + F )′ = A′B ′C ′D ′...F ′ ( ABCD...F )′ = A′ + B ′ + C ′ + D ′ + ... + F ′ ﻓﺮم هﺎﯼ ﮐﻠﯽ ﺗﺌﻮرﯼ دﻣﻮرﮔﺎن ﺑﻴﺎن ﻣﯽ ﮐﻨﺪ ﮐﻪ ﻣﮑﻤﻞ هﺮ ﺗﺎﺑﻊ ﺑﺎ ﺗﻌﻮﯾﺾ ﻋﻤﻠﮕﺮهﺎﯼ ANDو ORو ﻣﮑﻤﻞ ﻧﻤﻮدن هﺮ ﻣﺘﻐﻴﺮ ﺣﺎﺻﻞ ﻣﯽ ﺷﻮد .
٧
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ﻣﺜﺎل : ٢-٢ﻣﮑﻤﻞ ﺗﻮاﺑﻊ F = x( y ′z ′ + yz) , F = x ′yz ′ + x ′y ′zرا ﺑﺪﺳﺖ ﺁورﯾﺪ .
2
1
ﺗﺌﻮرﯼ دﻣﻮرﮔﺎن را هﺮ ﭼﻨﺪ ﺑﺎر ﮐﻪ ﻻزم ﺑﺎﺷﺪ ﺑﮑﺎر ﺑﺒﺮﯾﺪ .ﻣﮑﻤﻞ هﺎ ﺑﻔﺮم زﯾﺮ ﺣﺎﺻﻞ ﻣﯽ ﮔﺮدﻧﺪ
)F ′ = ( x′yz′ + x′y′z )′ = ( x′yz′)( x′y′z ) = ( x + y′ + z )( x + y + z′ 1 F ′ = [ x( y′z′ + yz)]′ = x′ + ( y′z′) + y′z′ + yz)′ = x′ + ( y′z′)′.( yz)′ 2 )= x′ + ( y + z )( y′ + z′ روش ﺳﺎدﻩ ﺗﺮﯼ ﺑﺮاﯼ ﺑﺪﺳﺖ ﺁوردن ﻣﮑﻤﻞ ﯾﮏ ﺗﺎﺑﻊ اﯾﻦ اﺳﺖ ﮐﻪ اﺑﺘﺪا دوﮔﺎن ﺁﻧﺮا ﺑﺪﺳﺖ ﺁوردﻩ و ﺳﭙﺲ ﻣﺘﻐﻴﺮهﺎﯾﺶ را ﻣﮑﻤﻞ ﻧﻤﺎﯾﻴﻢ .اﯾﻦ روش ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﻓﺮم ﮐﻠﯽ ﺗﺌﻮرﯼ دﻣﻮرﮔﺎن ﻧﺘﻴﺠﻪ ﻣﯽ ﺷﻮد .ﺑﺨﺎﻃﺮ داﺷﺘﻪ ﺑﺎﺷﻴﺪ ﮐﻪ دوﮔﺎن ﯾﮏ ﺗﺎﺑﻊ ﺑﺎ ﺗﺒﺪﯾﻞ ﻋﻤﻠﮕﺮ ANDو ORوﺗﺒﺪﯾﻞ ١هﺎ و ٠هﺎ ﺑﻪ ﯾﮑﺪﯾﮕﺮ ﺑﺪﺳﺖ ﻣﯽ ﺁﯾﺪ . ﻣﺜﺎل : ٢-٣ﻣﮑﻤﻞ هﺎﯼ ﺗﻮاﺑﻊ F2 , F1ﻣﺜﺎل ٢-٢را ﺑﺎﺗﻮﺟﻪ ﺑﻪ دوﮔﺎن ﺁﻧﻬﺎ و ﻣﮑﻤﻞ ﮐﺮدن هﺮ ﻣﺘﻐﻴﺮ ﺑﺪﺳﺖ ﺁورد .
F x ′yz ′ + x ′y ′z 1 دوﮔﺎن ﺗﺎﺑﻊ F1ﺑﺮاﺑﺮ اﺳﺖ ﺑﺎ ﭘﺲ
1.
)( x ′ + y + z ′)( x ′ + y ′ + z
از ﻣﮑﻤﻞ ﮐﺮدن هﺮ ﻣﺘﻐﻴﺮ دارﯾﻢ ( x + y ′ + z)( x + y + z ′) = F ′ 1
F = x( y′z′ + yz ) . 2 دوﮔﺎن ﺗﺎﺑﻊ F2ﺑﺮاﺑﺮ اﺳﺖ ﺑﺎ ) x + ( y ′ + z ′ )( y + z
ﭘﺲ از ﻣﮑﻤﻞ ﮐﺮدن هﺮ ﻣﺘﻐﻴﺮ دارﯾﻢ x ′ + ( y + z )( y ′ + z ′) = F ′ 2
2.
٨
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ٢-۴ﺣﺎﻻت ﻣﺘﻌﺎرف و اﺳﺘﺎﻧﺪارد
ﯾﮏ ﻣﺘﻐﻴﺮ دودوﯾﯽ ﻣﻤﮑﻦ اﺳﺖ ﺑﻔﺮم ﻣﻌﻤﻮﻟﯽ ) ( xﯾﺎ ﻣﮑﻤﻠﺶ ) َ ( xﻇﺎهﺮ ﺷﻮد .ﺣﺎل ﻓﺮض ﮐﻨﻴﻢ ﮐﻪ ﻣﺘﻐﻴﺮهﺎﯼ دودوﯾﯽ xو yﺑﻮﺳﻴﻠﻪ ﻋﻤﻠﮕﺮ ANDﺑﺎ ﯾﮑﺪﯾﮕﺮ ﺗﺮﮐﻴﺐ ﺷﻮﻧﺪ . ﭼﻮن هﺮ ﻣﺘﻐﻴﺮ ﻣﻤﮑﻦ اﺳﺖ ﺑﻪ هﺮ ﯾﮏ از دو ﺷﮑﻞ ﻓﻮق ﻇﺎهﺮ ﮔﺮدد ﭼﻬﺎر ﺗﺮﮐﻴﺐ ﺑﺮاﯼ
ﺁن دو ﻣﺘﻐﻴﺮ وﺟﻮد دارﻧﺪ xy′, x′y , x′y′و `xy
.هﺮ ﯾﮏ از اﯾﻦ ﭼﻬﺎر ﺟﻤﻠﻪ ﻧﺸﺎن
دهﻨﺪﻩ ﯾﮏ ﻧﺎﺣﻴﻪ در دﯾﺎﮔﺮام ون ،ﺷﮑﻞ ) (٢-١ﺑﻮدﻩ و ﻣﻴﻨﺘﺮم ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮد .ﺑﺮوﺷﯽ ﻣﺸﺎﺑﻪ n ،ﻣﺘﻐﻴﻴﺮ ﻣﯽ ﺗﻮاﻧﺪ روﺷﯽ ﻣﺸﺎﺑﻪ ﯾﺎ ﺁﻧﭽﻪ در ﺟﺪول ) (٢-٣ﺑﺮاﯼ ﺳﻪ ﻣﺘﻐﻴﺮ ﺣﺎﺻﻞ ﺷﺪﻩ ﺑﺪﺳﺖ ﺁﯾﻨﺪ .اﻋﺪاد دودوﯾﯽ از ﺻﻔﺮ ﺗﺎ
2 n −1
ﺑﺮاﯼ nﻣﺘﻐﻴﺮ در زﯾﺮ ﺳﺘﻮن
ﻣﺘﻐﻴﺮ هﺎ در ﺟﺪول ﻧﻮﺷﺘﻪ ﻣﯽ ﺷﻮﻧﺪ .هﺮ ﻣﻴﻨﺘﺮم از اﺟﺰاﯼ ﻋﻤﻠﮕﺮ ANDروﯼ nﻣﺘﻐﻴﺮ ﺑﺪﺳﺖ ﻣﯽ ﺁﯾﺪ و هﺮ ﻣﺘﻐﻴﺮ در ﺁن ﺑﺎ ﻣﻘﺪار ٠ﺑﺎ ﻋﻼﻣﺖ ﭘﺮﯾﻢ و ﺑﺎ ﻣﻘﺪار ١ﺑﺪون ﭘﺮﯾﻢ ﺧﻮاهﺪ ﺑﻮد .ﺳﻤﺒﻞ ﻣﻴﻨﺘﺮم ﻧﻴﺰ درﺟﺪول ﺑﻔﺮم mjﺁوردﻩ ﺷﺪﻩ اﺳﺖ ﮐﻪ jﻣﻌﺎدل دهﺪهﯽ ﺟﻤﻠﻪ ﻣﺮﺑﻮﻃﻪ ﻣﯽ ﺑﺎﺷﺪ . ﺟﺪول ) (٢-٣ﻣﻴﻨﺘﺮم و ﻣﺎﮐﺴﺘﺮم هﺎ ﺑﺮاﯼ ﺳﻪ ﻣﺘﻐﻴﻴﺮ دودوﯾﯽ
ﻣﺎﮐﺴﺘﺮم ﺟﻤﻠﻪ ﻋﻼﻣﺖ M0
ﻣﻴﻨﺘﺮم ﺟﻤﻠﻪ ﻋﻼﻣﺖ m0 x′y ′z ′
M1
x+ y+ z x + y + z′
m1
M2
x + y′ + z
m2
x′y′z x′yz′
M3
x + y′ + z ′
m3
M4
x′ + y + z
m4
M5
x′ + y + z ′
m5
M6
x′ + y′ + z
m6
M7
x′ + y′ + z′
x′yz xy′z′ xy′z xyz′
m7
xyz
z 0
y 0
x 0
1
0
0
0
1
0
1
1
0
0
0
1
1
0
1
0
1
1
1
1
1
٩
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺑﻄﺮﯾﻖ ﻣﺸﺎﺑﻬﯽ nﻣﺘﻐﻴﺮ در ﯾﮏ ﺟﻤﻠﻪ ، ORﮐﻪ هﺮ ﯾﮏ ﻣﯽ ﺗﻮاﻧﻨﺪ ﺑﺎ ﭘﺮﯾﻢ و ﯾﺎ ﺑﺪون ﭘﺮﯾﻢ ﺑﺎﺷﻨﺪ 2n ،ﺗﺮﮐﻴﺐ ﻣﻤﮑﻦ را اﯾﺠﺎد ﻣﯽ ﻧﻤﺎﯾﻨﺪ ﮐﻪ هﺮ ﯾﮏ از ﺁﻧﻬﺎ ﻣﺎﮐﺴﺘﺮم ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮد .هﺸﺖ ﺟﻤﻠﻪ ﻣﺎﮐﺴﺘﺮم ﻣﺮﺑﻮط ﺑﻪ ﺳﻪ ﻣﺘﻐﻴﺮ ﺑﺎ ﺳﻤﺒﻞ ﺁﻧﻬﺎ درﺟﺪول )(٢-٣ ﻟﻴﺴﺖ ﺷﺪﻩ اﻧﺪ .هﺮ 2nﺟﻤﻠﻪ ﻣﺎﮐﺴﺘﺮم ﺑﺮاﯼ nﻣﺘﻐﻴﺮ ﻣﺸﺎﺑﻬﯽ ﺗﻌﻴﻴﻦ ﻣﯽ ﺷﻮﻧﺪ .هﺮ ﻣﺎﮐﺴﺘﺮم از ﯾﮏ ﺟﻤﻠﻪ ORﻣﺮﺑﻮط ﺑﻪ nﻣﺘﻐﻴﺮ داراﯼ ﻣﺘﻐﻴﺮ هﺎﯼ ﺑﺪون ﭘﺮﯾﻢ اﺳﺖ ﺑﺸﺮﻃﯽ ﮐﻪ ﺁن ﻣﺘﻐﻴﺮهﺎ ٠ﺑﺎﺷﻨﺪ وﻟﯽ هﺮ ﮔﺎﻩ ﻣﻘﺪار ﻣﺘﻐﻴﺮ ١ﺑﺎﺷﺪ در اﯾﻨﺼﻮرت ﺁن ﻣﺘﻐﻴﺮ ﭘﺮﯾﻢ دار ﻧﻤﺎﯾﺶ دادﻩ ﻣﯽ ﺷﻮد .ﺗﻮﺟﻪ داﺷﺘﻪ ﺑﺎﺷﻴﺪ ﮐﻪ هﺮ ﺟﻤﻠﻪ ﻣﺎﮐﺴﺘﺮم ﻣﮑﻤﻞ ﻣﻴﻨﺘﺮم ﻣﺮﺑﻮﻃﻪ اش ﻣﯽ ﺑﺎﺷﺪ و ﺑﺎﻟﻌﮑﺲ . ﯾﮏ ﺗﺎﺑﻊ ﺑﻮل ﻣﯽ ﺗﻮاﻧﺪ ﺑﺎ اﺳﺘﻔﺎدﻩ از ﺟﺪول درﺳﺘﯽ ﺑﻔﺮم ﺟﺒﺮﯼ ﺑﺎ در ﻧﻈﺮ ﮔﺮﻓﺘﻦ ﻣﻴﻨﺘﺮم هﺎﯾﯽ ﮐﻪ ﺗﺎﺑﻊ ﺑﻪ ازاﯼ ﺁﻧﻬﺎ ﺑﺮاﺑﺮ ١اﺳﺖ و اﺟﺮاﯼ ﻋﻤﻠﮕﺮ ORروﯼ ﺁﻧﻬﺎ ﺗﺸﮑﻴﻞ ﮔﺮدد . ﻣﺜﻼً ﺗﺎﺑﻊ F1در ﺟﺪول ) (٢-۴ﺑﺪﯾﻦ ﻃﺮﯾﻖ ﻣﻌﻴﻦ ﻣﯽ ﺷﻮد ﮐﻪ ٠٠١و ١٠٠و ١١١را ﺑﻔﺮم
xy′z , x′y′z
و xyzﻧﺸﺎن دادﻩ و ﺳﭙﺲ ﺑﺎ ﯾﮑﺪﯾﮕﺮ ﺗﺮﮐﻴﺐ ﮐﻨﻴﻢ .ﭼﻮن هﺮ ﯾﮏ از اﯾﻦ
ﻣﻴﻨﺘﺮم هﺎ ﺑﺮاﺑﺮ ١اﺳﺖ ﺑﺎﯾﺪ راﺑﻄﻪ زﯾﺮ را داﺷﺘﻪ ﺑﺎﺷﻴﻢ :
f = x′y′z + xy′z′ + xyz = m + m + m 1 1 4 7 ﺑﻄﻮر ﻣﺸﺎﺑﻪ ﺑﺴﺎدﮔﯽ ﻣﯽ ﺗﻮان ﻧﺸﺎن داد ﮐﻪ :
f = x′yz + xy′z + xyz = m + m + m + m 2 3 5 6 7 اﯾﻦ ﻣﺜﺎﻟﻬﺎ ﻧﺸﺎن دهﺪﻩ ﯾﮏ ﺧﺎﺻﻴﺖ ﻣﻬﻢ ﺟﺒﺮ ﺑﻮل ﻣﯽ ﺑﺎﺷﻨﺪ ﮐﻪ ﻋﺒﺎرﺗﺴﺖ از :هﺮ ﺗﺎﺑﻊ ﺑﻮل ﻣﯽ ﺗﻮاﻧﺪ ﺑﺼﻮرت ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎ ) در اﯾﻨﺠﺎ ﺑﻤﻌﻨﯽ ORاﺳﺖ ( ﺑﻴﺎن ﺷﻮد .ﺣﺎل ﻣﮑﻤﻞ ﯾﮏ ﺗﺎﺑﻊ ﺑﻮل را در ﻧﻈﺮ ﺑﮕﻴﺮد .اﯾﻦ ﻣﮑﻤﻞ را ﻣﯽ ﺗﻮان ﺑﺎ اﺳﺘﻔﺎدﻩ از ﺟﺪول وﺑﮑﺎرﮔﻴﺮﯼ ﺟﻤﻼت ﻣﻴﻨﺘﺮم ﮐﻪ در ﺟﺪول ﺑﺮاﯼ ﺗﺎﺑﻊ ٠هﺴﺘﻨﺪ و اﻋﻤﺎل ﻋﻤﻠﮕﺮد ORروﯼ ﺁﻧﻬﺎ ﺑﻮﺟﻮد ﺁورد .ﻟﺬا ﻣﮑﻤﻞ ﺗﺎﺑﻊ f1ﺑﺮاﺑﺮ ﺧﻮاهﺪ ﺑﻮد ﺑﺎ .
١٠
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
f ′ = x′y′z′ + x′yz′ + x′yz + xy′z + xyz′ 1 اﮔﺮ ﻣﺎ ﻣﮑﻤﻞ f1را ﭘﻴﺪا ﮐﻨﻴﻢ ﻧﺘﻴﺠﻪ هﻤﺎن ﺗﺎﺑﻊ f1ﺧﻮاهﺪ ﺷﺪ .
) f = ( x + y + z )( x + y ′ + z )( x + y ′ + z ′)( x′ + y + z ′)( x′ + y ′ + z 1 = M .M .M .M .M 0 2 3 5 6 ﺑﻄﻮر ﻣﺸﺎﺑﻪ ﻋﺒﺎرت ﻣﺮﺑﻮط ﺑﻪ f2را ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺟﺪول ﻣﯽ ﺗﻮان ﻧﻮﺷﺖ :
) f = ( x + y + z )( x + y + z′)( x + y′ + z )( x′ + y + z 2 = M .M .M .M 0 1 2 4 اﯾﻦ ﻣﺜﺎﻟﻬﺎ ﺑﻴﺎﻧﮑﺮ دوﻣﻴﻦ ﺧﺎﺻﻴﺖ ﻣﻬﻢ ﺟﺒﺮ ﺑﻮل ﻣﯽ ﺑﺎﺷﻨﺪ .ﯾﻌﻨﯽ هﺮ ﺗﺎﺑﻊ ﻣﯽ ﺗﻮاﻧﺪ ﺑﺼﻮرت ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ ) ﺣﺎﺻﻠﻀﺮب ﺑﻪ ﻣﻌﻨﯽ اﻋﻤﺎل ﻋﻤﻠﮕﺮد ANDﻣﯽ ﺑﺎﺷﺪ ( ﻧﻮﺷﺘﻪ ﺷﻮد .روش ﺑﺪﺳﺖ ﺁوردن ﻣﺴﺘﻘﻴﻢ ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ ﺑﺎ اﺳﺘﻔﺎدﻩ از ﺟﺪول رﺑﻄﺮﯾﻖ زﯾﺮ اﺳﺖ :اﺑﺘﺪا ﺟﻤﻼت ﻣﺎﺳﮑﺘﺮﻣﯽ ﮐﻪ از ﺗﺮﮐﻴﺐ ﻣﺘﻐﻴﺮهﺎ ﺗﺸﮑﻴﻞ ﺷﺪﻩ و ﺑﺮاﯼ ﺗﺎﺑﻊ ﺗﻮﻟﻴﺪ ٠ﻣﯽ ﻧﻤﺎﯾﺪ اﻧﺘﺨﺎب ﺷﺪﻩ و ﺳﭙﺲ ﺑﺎ اﺟﺮاﯼ ﻋﻤﻠﮕﺮ ANDروﯼ ﺗﻤﺎم ﺁﻧﻬﺎ ﻣﯽ ﺗﻮان ﺑﻪ ﻧﺘﻴﺠﻪ ﻣﻮرد ﻧﻈﺮ رﺳﻴﺪ .هﺮ ﮔﺎﻩ ﺗﻮاﺑﻊ ﺑﻮل ﺑﺼﻮرت ﻣﺠﻤﻮﻋﻤﻴﻨﺘﺮم هﺎ ﯾﺎ ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ در ﺁﯾﻨﺪ ﮔﻮﯾﻨﺪ ﺑﻪ ﺷﮑﻞ ﻣﺘﻌﺎرف ﻣﯽ ﺑﺎﺷﻨﺪ . ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎ ﻗﺒﻼً ﮔﻔﺘﻪ ﺷﺪﻩ ﮐﻪ ﺑﺮاﯼ nﻣﺘﻐﻴﺮ 2nﻣﻴﻨﺘﺮم ﻣﺴﺘﻘﻞ ﺑﺪﺳﺖ ﺁوردﻩ و هﺮ ﺗﺎﺑﻊ ﺑﻮل را ﻣﻴﺘﻮان ﺑﺼﻮرت ﻣﺤﻤﻮع ﺁﻧﻬﺎ ﺑﻴﺎن ﮐﺮد .ﺗﺎﺑﻊ ﺑﻮل از ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎﯾﯽ ﮐﻪ ﻣﻘﺪارﺷﺎن در ﺟﺪول درﺳﺘﯽ ﺑﺮاﺑﺮ ١اﺳﺖ ﺗﺸﮑﻴﻞ ﻣﯽ ﮔﺮدد .ﭼﻮن ﻣﻘﺪار هﺮ ﻣﻴﻨﺘﺮم ﻣﯽ ﺗﻮاﻧﺪ ١ﯾﺎ ٠ﺑﺎﺷﺪ و ﻧﻴﺰ . 2nﮔﺎهﯽ اوﻗﺎت ﺑﻬﺘﺮ اﺳﺖ ﮐﻪ ﺗﺎﺑﻊ را ﺑﺼﻮرت ﻣﺠﻤﻮع ﻣﻴﻨﺘﻢ هﺎ ﻧﺸﺎن داد .ﭼﻨﺎﻧﭽﻪ ﺗﺎﺑﻊ ﺑﻪ اﯾﻦ ﺷﮑﻞ ﻧﺒﺎﺷﺪ ﻣﯽ ﺗﻮان ﺁن را ﺑﺎ اﺟﺮاﯼ اﻋﻤﺎل زﯾﺮ ﺑﻔﺮم ﻣﻮرد ﻧﻈﺮ در ﺁورد .اﺑﺘﺪا ﻣﺠﻤﻮﻋﻪ ﺟﻤﻼت ANDﺷﺪﻩ را ﺑﺪﺳﺖ ﻣﯽ ﺁورﯾﻢ و ﺳﭙﺲ ﺟﻤﻼت را از
١١
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﻧﻈﺮ وﺟﻮد ﮐﻠﻴﻪ ﻣﺘﻐﻴﺮ هﺎ ﻣﻮرد ﺑﺎزرﺳﯽ ﻗﺮار ﻣﯽ دهﻴﻢ .در ﺻﻮرت ﻋﺪم وﺟﻮد ﺑﺮﺧﯽ ﻣﺘﻐﻴﺮهﺎ ،ﺑﺎﯾﺪ ﺁﻧﻬﺎ رادر ﻋﺒﺎراﺗﯽ ﻣﺎﻧﻨﺪ َ x+xو ﻏﻴﺮﻩ ANDﮐﺮد .ﮐﻪ xﯾﮑﯽ از ﻣﺘﻐﻴﺮهﺎﯾﯽ اﺳﺖ ﮐﻪ در ﺟﻤﻠﻪ وﺟﻮد ﻧﺪارد .ﻣﺜﺎل زﯾﺮ ﻣﻄﻠﺐ را روﺷﻦ ﻣﻴﮑﻨﺪ : ﻣﺜﺎل : -٢-۴ﺗﺎﺑﻊ
F = A + B′C
را ﺑﺼﻮرت ﻣﺠﻮع ﻣﻴﻨﺘﺮم ﻧﺸﺎن دهﻴﺪ .
ﺗﺎﺑﻊ داراﯼ ﺳﻪ ﻣﺘﻐﻴﺮ A,B,Cﻣﯽ ﺑﺎﺷﺪ .در اوﻟﻴﻦ ﺟﻤﻠﻪ دو ﻣﺘﻐﻴﺮ وﺟﻮد ﻧﺪارد ،ﺑﻨﺎﺑﺮاﯾﻦ
A = A(B + B′) + AB + AB هﻨﻮز هﻢ ﯾﮏ ﻣﺘﻐﻴﺮ ﮐﺴﺮ اﺳﺖ .
)A = AB(C + C ′) + AB′(C + C ′ = ABC + ABC ′+ AB′C + AB′C ′ ﺟﻤﻠﻪ دوم
B′C
ﯾﮏ ﻣﺘﻐﻴﺮ ﮐﺴﺮ دارد .
B′C = B′C ( A + A′) = AB′C + A′B′C ′ از ﺗﺮﮐﻴﺐ ﻧﺘﺎﯾﺞ ﻓﻮق دارﯾﻢ
F = A + B′C = ABC + ABC ′+ AB′C + AB′C ′ + AB′C + A′B′C از ﻃﺮﻓﯽ
AB′Cدوﺑﺎرﻩ ﺗﮑﺮار ﺷﺪﻩ اﺳﺖ و ﺑﺮ ﻃﺒﻖ ﺗﺌﻮرﯼ ( x = x + x) ، ١
ﻣﯽ ﺗﻮان
ﯾﮑﯽ از ﺁﻧﻬﺎ را ﺣﺬف ﮐﺮد .ﺑﺎ ﻣﺮﺗﺐ ﻧﻤﻮدن ﻣﻴﻨﺘﺮم هﺎ ﺑﺘﺮﺗﻴﺐ ﺻﻌﻮدﯼ ﭼﻨﻴﻦ ﻧﺘﻴﺠﻪ ﻣﯽ ﺷﻮد .
F = A′B′C + AB′C ′ + AB′C + ABC =m + m + m + m + m 5 7 1 4 6 هﻨﮕﺎﻣﯽ ﮐﻪ ﺗﺎﺑﻊ ﺑﻮل ﺑﻔﺮم ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎ اﺳﺖ ﻣﻨﺎﺳﺐ ﺗﺮ اﺳﺖ ﺗﺎ ﺁن ﺑﻔﺮم ﺧﻼﺻﻪ زﯾﺮ ﻧﺸﺎن دهﻴﻢ .
١٢
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
) F ( A, B, C) = ∑ (1,4,5,6,7 ﺳﻤﺒﻞ ∑ ﺑﻪ ﻣﻌﻨﯽ اﺟﺮاﯼ ﻋﻤﻠﮕﺮ ORروﯼ ﺟﻤﻼت اﺳﺖ .ﺣﺮوﻓﯽ ﮐﻪ در داﺧﻞ ﭘﺮاﻧﺘﺰ ﻗﺮار دارﻧﺪ ﻟﻴﺴﺖ ﻣﺘﻐﻴﺮهﺎﯼ ﺑﮑﺎر رﻓﺘﻪ را ﺑﻬﻨﮕﺎم ﺗﺸﮑﻴﻞ ﺟﻤﻼت ﻣﻴﻨﺘﺮم و ﺟﻤﻊ ﺁﻧﻬﺎ ﻣﻌﻴﻦ ﻣﯽ ﮐﻨﻨﺪ .روش دﯾﮕﺮﯼ ﺑﺮاﯼ ﺗﺸﮑﻴﻞ ﻣﻴﻨﺘﺮم هﺎﯼ ﺗﺎﺑﻊ ﺑﻮل ﺗﻬﻴﻪ ﺟﺪول درﺳﺘﯽ ﺗﺎﺑﻊ ﻣﺴﺘﻘﻴﻤﺎً از ﻋﺒﺎرت ﺟﺒﺮﯼ اﺳﺖ ﮐﻪ از روﯼ ﺁن ﻣﻴﻨﺘﺮم هﺎ ﺧﻮاﻧﺪﻩ ﻣﯽ ﺷﻮﻧﺪ .ﺗﺎﺑﻊ ﺑﻮل ﻣﺜﺎل ٢-۴را در ﻧﻈﺮ ﺑﮕﻴﺮد :
F = A + B′C ﺟﺪول درﺳﺘﯽ ﺷﮑﺐ ) (٢-۵ﻣﺴﺘﻘﻴﻤﺎً از ﻋﺒﺎرت ﺟﺒﺮﯼ ﺑﺎ هﺸﺖ ﺗﺮﮐﻴﺐ دودوﯾﯽ ﻣﺘﻐﻴﺮ هﺎﯼ A , B , Cﺣﺎﺻﻞ ﻣﯽ
ﺷﻮد ﮐﻪ ﺑﺮاﯼ ﻣﻴﻨﺘﺮم هﺎﯾﯽ ﮐﻪ در ﺁﻧﻬﺎ BC = 01 , A =1
ﺑﺎﺷﺪ ١ﻗﺮار ﻣﯽ دهﻴﻢ .ﺳﭙﺲ ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺣﺠﺪول درﺳﺘﯽ ﭘﻨﺞ ﻣﻴﻨﺘﺮم ﺗﺎﺑﻌﯽ را ﮐﻪ ١،۴،۵،۶،٧ﻣﯽ ﺑﺎﺷﻨﺪ ﻣﯽ ﺧﻮاﻧﻴﻢ.
ﺿﺮب ﻣﺎﮐﺴﺘﺮم هﺎ
n هﺮ ﯾﮏ از 22ﺗﺎﺑﻊ ﻣﺘﺸﮑﻞ از nﻣﺘﻐﻴﺮ را هﻤﭽﻨﻴﻦ ﻣﯽ ﺗﻮان ﺑﺼﻮرت ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ ﺑﻴﺎن داﺷﺖ .ﺑﺮاﯼ ﭼﻨﻴﻦ ﻓﺮﻣﯽ ﺑﺎﯾﺪ اول ﺟﻤﻠﻪ هﺎﯼ ORرا ﺗﺸﮑﻴﻞ داد .
اﯾﻦ ﻋﻤﻞ را ﻣﯽ ﺗﻮان ﺑﺎ اﺳﺘﻔﺎدﻩ از ﻗﺎﻧﻮن ﺗﻮزﯾﻊ ÷ذﯾﺮﯼ )x + yz = ( x + y)( x + z
ﻧﻴﺰ
اﻧﺠﺎم داد .ﺳﭙﺲ هﺮ ﻣﺘﻐﻴﺮ ﻏﺎﯾﺐ در هﺮ ﺟﻤﻠﻪ ORﺑﺎ OR ، xxﻣﯽ ﺷﻮد .اﯾﻦ روش ﺑﺎ ﻣﺜﺎل زﯾﺮ واﺿﺤﺘﺮ ﺧﻮاهﺪ ﺷﺪ :
١٣
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ﺟﺪول ) (٢-۵ﺟﺪول درﺳﺘﯽ ﺑﺮاﯼ F ٠ ١ ٠ ٠ ١ ١ ١ ١
C ٠ ١ ٠ ١ ٠ ١ ٠ ١
B ٠ ٠ ١ ١ ٠ ٠ ١ ١
F = A + B′C A ٠ ٠ ٠ ٠ ١ ١ ١ ١
ﻣﺜﺎل : ٢-۵ﺗﺎﺑﻊ F = xy + x′zرا ﺑﺼﻮرت ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم ﺑﻨﻮﯾﺴﻴﺪ : اﺑﺘﺪا ﺑﺎ اﺳﺘﻔﺎدﻩ از ﻗﺎﻧﻮن ﺗﻮزﯾﻊ ﭘﺬﯾﺮﯼ ﺗﺎﺑﻊ را ﺑﻪ ﺻﻮرت ﺟﻤﻼ ORدر ﻣﯽ ﺁورﯾﻢ :
) F = xy + x′z = ( xy + x′)( xy + z ) = ( x + x′)( y + x′)( x + z )( y + z ) = ( x′ + y)( x + z )( y + z ﺗﺎﺑﻊ داراﯼ ﺳﻪ ﻣﺘﻐﻴﺮ z,y,xاﺳﺖ .هﺮ ﺟﻤﻠﻪ ORﻓﺎﻗﺪ ﯾﮏ ﻣﺘﻐﻴﺮ اﺳﺖ .ﺑﻨﺎﺑﺮاﯾﻦ .
)x′ + y = x′ + y + zz′ = ( x′ + y + z )( x′ + y + z′ ) x + z = x + z + yy′ = ( x + y + z )( x6 y′ + z ) y + z = − y + z + xx′ = ( x + y + z )( x′ + y + z ﺑﺎ ﺗﺮﮐﻴﺐ ﻋﺒﺎرت ﻓﻮق و ﺣﺬف ﺁﻧﻬﺎﯾﯽ ﮐﻪ ﺑﻴﺶ از ﯾﮑﺒﺎر ﺗﮑﺮار ﺷﺪﻩ اﻧﺪ ﺧﻮاهﻴﻢ داﺷﺖ :
)F = ( x + y + z )( x + y′ + z )( x′ + y + z )( x′ + y + z′ =M M M M 0 2 4 5 روش ﻣﻨﺎﺳﺐ ﺗﺮﯼ ﺑﺮاﯼ ﻧﻤﺎﯾﺶ ﺗﺎﺑﻊ ﺑﻘﺮار زﯾﺮ اﺳﺖ :
)F ( x, y, z) = ∏(0,2,4,5
١٤
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ﺳﻤﺒﻞ ﺿﺮب ،
∏
ﺑﻴﺎﻧﮕﺮ ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ ﻣﯽ ﺑﺎﺷﺪ و اﻋﺪاد ،ﺷﻤﺎرﻩ ﺟﻤﻼت
ﻣﺎﮐﺴﺘﺮم را ﻣﺸﺨﺺ ﻣﯽ ﺳﺎزد . ﺗﺒﺪﯾﻞ ﻓﺮﻣﻬﺎﯼ ﻣﺘﻌﺎرف ﺑﻪ ﯾﮑﺪﯾﮕﺮ ﻣﮑﻤﻞ ﯾﮏ ﺗﺎﺑﻊ ﮐﻪ ﺑﺼﻮرت ﻣﺠﻤﻮع ﻣﻨﻴﺘﺮم هﺎ ﻧﺸﺎن دادﻩ ﺷﺪﻩ ﺑﺮاﺑﺮ اﺳﺖ ﺑﺎ ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎﯾﯽ ﮐﻪ در ﻓﺮم اﺻﻠﯽ ﺗﺎﺑﻊ وﺟﻮد ﻧﺪارد .زﯾﺮا ﺗﺎﺑﻊ اﺻﻠﯽ از ﺟﻤﻼت ﻣﻴﻨﺘﺮﻣﯽ ﺗﺸﮑﻴﻞ ﺷﺪﻩ ﮐﻪ ﺗﺎﺑﻊ را ﺑﺮاﺑﺮ ١ﻣﯽ ﻧﻤﺎﯾﺪ ،در ﺣﺎﻟﻴﮑﻪ ﻣﮑﻤﻞ ﺁن ﺗﺎﺑﻊ ﺑﻪ ازاﯼ ﺟﻤﻼﺗﯽ ﺑﺮاﺑﺮ ١اﺳﺖ ﮐﻪ ﺗﺎﺑﻊ اﺻﻠﯽ ﺑﻪ ازاﯼ ﺁﻧﻬﺎ ٠ﻣﯽ ﺑﺎﺷﺪ .ﺑﻌﻨﻮان ﻣﺜﺎل ﺗﺎﺑﻊ زﯾﺮ را در ﻧﻈﺮ ﺑﮕﻴﺮﯾﺪ :
)F = ( A, B, C ) = ∑ (1,4,5,6,7 ﻣﮑﻞ اﯾﻦ ﺗﺎﺑﻊ ﺑﻪ ﺷﮑﻞ زﯾﺮ اﺳﺖ :
F ′( A, B, C ) = ∑ (0,2,3) = m + m + m 0 2 3 ﺣﺎل ،اﮔﺮ ﻣﮑﻤﻞ ` Fرا ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺗﺌﻮرﯼ دﻣﻮرﮔﺎن ﺑﺪﺳﺖ ﺁورﯾﻢ ﻓﺮم ﺟﺪﯾﺪﯼ ﺑﺮاﯼ F ﺑﺪﺳﺖ ﻣﯽ ﺁﯾﺪ.
) F = m + m + m ) = m .m .m = M M M = ∏ ( 0 , 2 , 3 0 2 3 0 2 3 0 2 3 ﺁﺧﺮﯾﻦ ﺗﺒﺪﯾﻞ در راﺑﻄﻪ ﻓﻮق ﻧﺘﻴﺠﻪ ﺗﻌﺎرﯾﻒ ﺟﺪول ) (٢-٣ﻣﯽ ﺑﺎﺷﺪ .ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺟﺪول درﺳﺘﯽ راﺑﻄﻪ زﯾﺮ ﻣﺴﻠﻢ اﺳﺖ .
m′j = M j ﯾﻌﻨﯽ ،ﺟﻤﻠﻪ ﻣﺎﮐﺴﺘﺮم ﺑﺎ اﻧﺪﯾﺲ jﻣﮑﻤﻞ ﺟﻤﻠﻪ ﻣﻴﻨﺘﺮم ﺑﺎ هﻤﺎن اﻧﺪﯾﺲ اﺳﺖ و ﺑﺎﻟﻌﮑﺲ .
١٥
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺁﺧﺮﯾﻦ ﻣﺜﺎل ،ﺗﺒﺪﯾﻞ ﯾﮏ ﺗﺎﺑﻊ ﺑﺼﻮرت ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎ ﺑﻴﺎن ﺷﺪﻩ ﺑﻪ ﻣﻌﺎدل ﺁن ﮐﻪ ﺑﺼﻮرت ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ اﺳﺖ را ﺑﻴﺎن ﻣﯽ دارد .ﺑﺤﺚ ﻣﺸﺎﺑﻬﯽ ﻧﺸﺎن ﻣﯽ دهﺪ ﮐﻪ ﺗﺒﺪﯾﻞ ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ ﺑﻪ ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎ ﺑﻄﺮﯾﻖ ﻓﻮق اﺳﺖ .ﺣﺎل ﯾﮏ روش ﮐﻠﯽ را ﺑﺮاﯼ ﺗﺒﺪﯾﻞ ﺑﻴﺎن ﻣﯽ ﮐﻨﻴﻢ : ﺑﺮاﯼ ﺗﺒﺪﯾﻞ ﯾﮏ ﻓﺮم ﻣﺘﻌﺎرف ﺑﻪ دﯾﮕﺮﯼ ﺳﻤﺒﻞ هﺎﯼ ∑ ∏ ,را ﺑﺎ ﯾﮑﺪﯾﮕﺮ ﻋﻮض ﻧﻤﻮدﻩ و ﺟﻤﻼﺗﯽ ﮐﻪ در ﺗﺎﺑﻊ اﺻﻠﯽ وﺟﻮد ﻧﺪارد را ﻧﻴﺰ ﻟﻴﺴﺖ ﻣﯽ ﻧﻤﺎﯾﻴﻢ .ﺑﺮاﯼ ﯾﺎﻓﺘﻦ ﺟﻤﻼت ﮔﻢ ﺷﺪﻩ ﺑﺎﯾﺪ ﺑﻴﺎد ﺑﻴﺎورﯾﻢ ﮐﻪ ﺗﻌﺪاد ﮐﻞ ﺟﻤﻼت 2nاﺳﺖ ﮐﻪ در ﺁن nﺗﻌﺪاد ﻣﺘﻐﻴﺮهﺎ در ﺗﺎﺑﻊ اﺳﺖ . ﯾﮏ ﺗﺎﺑﻊ ﺑﻮل ﺑﻔﺮم ﻋﺒﺎرت ﺟﺒﺮﯼ ﺑﻮﺳﻴﻠﻪ ﺟﺪول درﺳﺘﯽ و روش ﺗﺒﺪﯾﻞ ﻣﺘﻌﺎرف ﻗﺎﺑﻞ ﺗﺒﺪﯾﻞ ﺑﻪ ﺿﺮب ﻣﺎﮐﺴﺘﺮم هﺎ اﺳﺖ .ﻣﺜﻼً ﻋﺒﺎرت ﺑﻮل زﯾﺮ را در ﻧﻈﺮ ﺑﮕﻴﺮﯾﺪ : F = xy + x ′ z
اﺑﺘﺪا ﺟﺪول درﺳﺘﯽ را ﺑﺪﺳﺖ ﻣﯽ ﺁورﯾﻢ ،ﺷﮑﻞ ) ١ . (٢-۶هﺎﯼ زﯾﺮ ﺳﺘﻮن Fاز ﺗﺮﮐﻴﺐ ﻣﺘﻐﻴﺮهﺎ ﺑﺎ x=11و xz=01ﺣﺎﺻﻞ ﻣﯽ ﺷﻮد ﻣﻴﻨﺘﺮم هﺎﯼ ﺗﺎﺑﻊ از روﯼ ﺟﺪول درﺳﺘﯽ ﻋﺒﺎرﺗﻨﺪ از . ١،٣،۶،٧ﺗﺎﺑﻊ ﺑﺮ ﺣﺴﺐ ﻣﻴﻨﺘﺮم هﺎ ﺑﺮاﺑﺮﺳﺖ ﺑﺎ
)F ( x, y, z) = ∑ (1,3,6,7 ﭼﻮن ﺟﻤﻌﺎً هﺸﺖ ﻣﻴﻨﺘﺮم ﯾﺎ ﻣﺎﮐﺴﺘﺮم در ﯾﮏ ﺗﺎﺑﻊ ﺳﻪ ﻣﺘﻐﻴﺮﻩ وﺟﻮد دارد ،ﻣﺎ ﺟﻤﻼت ﻏﻴﺮ ﻣﻮﺟﻮد در ﻓﻮق را ﻣﯽ ﯾﺎﺑﻴﻢ ﮐﻪ ﻋﺒﺎرﺗﻨﺪ از ۴ ، ٢ ، ٠و . ۵ﺗﺎﺑﻊ ﺑﺮ ﺣﺴﺐ ﺿﺮب ﻣﺎﮐﺴﺘﺮم هﺎ ﭼﻨﻴﻦ ﺧﻮاهﺪ ﺷﺪ .
)F ( x, y, z) = ∏(0,2,4,5 اﯾﻦ هﻤﺎن ﻣﺜﺎﻟﯽ اﺳﺖ ﮐﻪ در ﻣﺜﺎل ٢-۵دﯾﺪﯾﻢ .
١٦
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ﺟﺪول ) (٢-۶ﺟﺪول درﺳﺘﯽ ﺑﺮاﯼ
ﻓﺮم هﺎﯼ اﺳﺘﺎﻧﺪارد
f 0 1 ٠ ١ ٠ ٠ ١ ١
z 0 1 ٠ ١ ٠ ١ ٠ ١
y 0 0 ١ ١ ٠ ٠ ١ ١
F = xy + x′z x 0 0 ٠ ٠ ١ ١ ١ ١
دو ﻓﺮم ﻣﺘﻌﺎرف ﺟﺒﺮ ﺑﻮل ،ﻓﺮم هﺎﯾﯽ اﺑﺘﺪاﯾﯽ هﺴﺘﻨﺪ ﮐﻪ هﺮ ﮐﺲ ﻣﯽ ﺗﻮاﻧﺪ ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺟﺪول درﺳﺘﯽ ﺑﻪ ﺁﻧﻬﺎ دﺳﺘﺮﺳﯽ ﭘﻴﺪا ﮐﻨﺪ .اﯾﻦ ﻓﺮم هﺎ ﻣﻌﻤﻮﻻً داراﯼ ﺣﺪاﻗﻞ ﻣﺘﻐﻴﺮهﺎ ﻧﻴﺴﺘﻨﺪ ،زﯾﺮا هﺮ ﻣﻴﻨﺘﺮم ﯾﺎ ﻣﺎﮐﺴﺘﺮم ﺑﺎﯾﺴﺘﯽ ﺑﻨﺎ ﺑﻪ ﺗﻌﺮﯾﻒ داراﯼ ﺗﻤﺎم ﻣﺘﻐﻴﺮهﺎ اﻋﻢ از ﻣﮑﻤﻞ و ﻏﻴﺮ ﻣﮑﻤﻞ ﺑﺎﺷﻨﺪ .راﻩ دﯾﮕﺮﯼ ﺑﺮاﯼ ﺑﻴﺎن ﺗﺎﺑﻊ ﺑﻮل ،ﻓﺮم اﺳﺘﺎﻧﺪارد اﺳﺖ .در اﯾﻦ ﻓﺮم ،ﺟﻤﻠﻪ هﺎﯾﯽ ﮐﻪ ﺗﺎﺑﻊ را ﺗﺸﮑﻴﻞ ﻣﯽ دهﻨﺪ ﻣﻤﮑﻦ اﺳﺖ ﯾﮏ ﻳﺎ دو ﯾﺎ هﺮ ﺗﻌﺪادﯼ از ﻣﺘﻐﻴﺮهﺎ را داراﺑﺎﺷﻨﺪ .دو ﻧﻮع ﻓﺮم اﺳﺘﺎﻧﺪارد وﺟﻮد دارد .ﯾﮑﯽ ﺟﻤﻊ ﺣﺎﺻﻠﻀﺮب هﺎ و دﯾﮕﺮﯼ ﺿﺮب ﺣﺎﺻﻞ ﺟﻤﻊ هﺎ . ﺟﻤﻊ ﺣﺎﺻﻠﻀﺮب هﺎ ،ﯾﮏ ﻋﺒﺎرت ﺑﻮل اﺳﺖ ﮐﻪ ﺷﺎﻣﻞ ﺟﻤﻼت ) ANDﺑﺎ ﻧﺎم ﺟﻤﻼت ﺣﺎﺻﻠﻀﺮب (از ﯾﮏ ﯾﺎ ﭼﻨﺪﻣﺘﻐﻴﺮ ﻣﯽ ﺑﺎﺷﺪ .ﮐﻠﻤﻪ ﺟﻤﻊ دراﯾﻨﺠﺎ ﺑﻪ ﻣﻌﻨﯽ ﻋﻤﻠﮕﺮ ORروﯼ اﯾﻦ ﺟﻤﻼت اﺳﺖ . ﻣﺜﺎﻟﯽ از اﯾﻦ ﻧﻮع ﺑﻘﺮار زﯾﺮ ﻣﯽ ﺑﺎﺷﺪ :
F = y′ + xy + x′yz′ 1 ﻋﺒﺎرت داراﯼ ﺳﻪ ﺟﻤﻠﻪ ﺣﺎﺻﻠﻀﺮب از ﯾﮏ ،دو و ﺳﻪ ﻣﺘﻐﻴﺮ اﺳﺖ .ﺟﻤﻊ ﺁﻧﻬﺎ در واﻗﻊ اﺟﺮاﯼ ﻋﻤﻞ ORاﺳﺖ ﮐﻪ ﺟﻤﻊ ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮﻧﺪ .هﺮ ﺟﻤﻠﻪ هﺮ ﺗﻌﺪاد ﻣﺘﻐﻴﺮ را ﻣﻤﮑﻦ
١٧
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
اﺳﺖ دارا ﺑﺎﺷﺪ .ﺿﺮب ﺑﻴﺎﻧﮕﺮ ﻋﻤﻠﮕﺮ ANDروﯼ ﺁﻧﻬﺎ اﺳﺖ .ﻣﺜﺎﻟﯽ از ﯾﮏ ﺗﺎﺑﻊ ﮐﻪ ﺑﺼﻮرت ﺿﺮب ﺣﺎﺻﻞ ﺟﻤﻊ هﺎ ﺑﻴﺎن ﺷﺪﻩ ﻋﺒﺎرﺗﺴﺖ از :
)F = x( y′ + z)( x′ + y + z′ + w 2 اﯾﻦ ﻋﺒﺎرت ﺑﻪ ﺗﺮﺗﻴﺐ داراﯼ ﺳﻪ ﺟﻤﻠﻪ ،ﺑﺎ ﯾﮏ ،دو ﭼﻬﺎر ﻣﺘﻐﻴﺮ اﺳﺖ .ﺿﺮب ﺁﻧﻬﺎ در واﻗﻊ اﺟﺮاﯼ ﻋﻤﻞ ANDﻣﯽ ﺑﺎﺷﺪ .ﮐﺎرﺑﺮد ﮐﻠﻤﻪ ﺿﺮب و ﺟﻤﻊ ﺑﻴﺎﻧﮕﺮ ﺷﺒﺎهﺖ ANDﺑﺎ ﺿﺮب و ﻋﻤﻠﮕﺮ ORﺑﺎ ﺟﻤﻊ در ﺣﺴﺎب ﻣﯽ ﺑﺎﺷﺪ . ﯾﮏ ﺗﺎﺑﻊ ﺑﻮل ﻣﻤﮑﻦ اﺳﺖ ﺑﻔﺮم ﻏﻴﺮ اﺳﺘﺎﻧﺪارد ﻧﻴﺰ ﺑﻴﺎن ﺷﻮد .ﺑﻌﻨﻮان ﻣﺜﺎل ﺗﺎﺑﻊ :
)F = ( AB + CD)( A′B′ + C ′D′ 3 ﻧﻪ ﺑﺸﮑﻞ ﺟﻤﻊ ﺣﺎﺻﻠﻀﺮب هﺎ و ﻧﻪ ﺑﺸﮑﻞ ﺿﺮب ﺣﺎﺻﻞ ﺟﻤﻊ هﺎ اﺳﺖ .اﻟﺒﺘﻪ ﻣﯽ ﺗﻮان ﺑﺎ اﺳﺘﻔﺎدﻩ از ﻗﺎﻧﻮن ﺗﻮزﯾﻊ ﭘﺬﯾﺮﯼ ﺁن را ﺑﻔﺮم اﺳﺘﺎﻧﺪارد در ﺁورد :
F = A′B′CD + ABC ′D′ 3 ٢-۵ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ دﯾﺠﻴﺘﺎل ﻣﺪارهﺎﯼ دﯾﺠﻴﺘﺎل اﻟﮑﺘﺮوﻧﻴﮑﯽ ،ﻣﺪارهﺎﯼ ﻣﻨﻄﻘﯽ ﻧﻴﺰ ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮﻧﺪ .زﯾﺮا اﯾﻨﮕﻮﻧﻪ ﻣﺪارهﺎﯼ در ﻣﻘﺎﺑﻞ ورودﯼ ﻣﻨﺎﺳﺒﯽ ،ﺗﻮﻟﻴﺪ ﮐﻨﻨﺪﻩ ﯾﮏ ﺳﺮﯼ اﻋﻤﺎل ﻣﻨﻄﻘﯽ ﻣﯽ ﺑﺎﺷﻨﺪ .هﺮ ﮔﻮﻧﻪ اﻃﻼﻋﺎت ﻣﺤﺎﺳﺒﺎﺗﯽ ﯾﺎ ﮐﻨﺘﺮﻟﯽ ﻣﻮرد ﻧﻈﺮ را ﻣﯽ ﺗﻮان ﺑﺎ ﻋﺒﻮر ﺳﻴﮕﻨﺎل هﺎﯼ دودوﯾﯽ از ﻣﻴﺎن دﺳﺘﻪ هﺎﯼ ﻣﺘﻔﺎوت ﻣﺪارهﺎﯼ ﻣﻨﻄﻘﯽ ﻣﻮرد اﺳﺘﻔﺎدﻩ ﻗﺮار داد ، ﮐﻪ هﺮ ﺳﻴﮕﻨﺎل ﻧﺸﺎن دهﻨﺪﻩ ﯾﮏ ﻣﺘﻐﻴﺮ ﺑﻮدﻩ و ﯾﮏ ﺑﻴﺖ از اﻃﻼﻋﺎت راﺣﻤﻞ ﻣﯽ ﮐﻨﺪ . ﻣﺪارهﺎﯼ ﻣﻨﻄﻘﯽ ﮐﻪ اﻋﻤﺎل ﻣﻨﻄﻘﯽ ANDو ORو NOTرا اﺟﺮا ﻣﯽ ﮐﻨﺪ ﺑﻪ هﻤﺮاﻩ ﺳﻤﺒﻞ هﺎﯼ ﻣﺮﺑﻮﻃﻪ در ﺷﮑﻞ ) (٢-١ﻧﺸﺎن دادﻩ ﺷﺪﻩ اﻧﺪ .اﯾﻦ ﻣﺪارهﺎ ﮐﻪ ﮔﻴﺖ ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮﻧﺪ ﺑﻠﻮﮐﻬﺎﯼ ﺳﺨﺖ اﻓﺰارﯼ هﺴﺘﻨﺪ ﮐﻪ ﺑﺎ ورودﯼ ﻣﻨﻄﻘﯽ ﻣﻨﺎﺳﺒﯽ در ﺧﺮوﺟﯽ
١٨
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺧﻮد ٠ﯾﺎ ١ﻣﻨﻄﻘﯽ ﺗﻮﻟﻴﺪ ﻣﯽ ﮐﻨﻨﺪ .ﺗﻮﺟﻪ ﮐﻨﻴﺪ ﮐﻪ ﭼﻬﺎر ﻧﺎم ﻣﺨﺘﻠﻒ ﺑﺮاﯼ اﯾﻦ ﻣﺪارهﺎ ﺑﮑﺎر رﻓﺘﻪ اﺳﺖ .ﻣﺪارهﺎﯼ دﯾﺠﻴﺘﺎل ،ﻣﺪارهﺎﯼ ﺳﻮﺋﻴﭽﻴﻨﮓ ،ﻣﺪارهﺎﯼ ﻣﻨﻄﻘﯽ و ﮔﻴﺖ هﺎ .هﻤﻪ اﯾﻦ اﺳﺎس ﺑﻄﻮر ﮔﺴﺘﺮدﻩ اﯼ اﺳﺘﻔﺎدﻩ ﻣﻴﺸﻮﻧﺪ وﻟﯽ ﺑﻬﺘﺮ اﺳﺖ ﻣﺎ اﯾﻦ ﻣﺪارهﺎﯼ را ANDو ORو NOTﮔﺎهﯽ ﻣﺪار واروﻧﮕﺮ ﯾﺎ ﻣﻌﮑﻮس ﮐﻨﻨﺪﻩ ﻧﻴﺰ ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮد زﯾﺮا ﺳﻴﮕﻨﺎل دودوﯾﯽ را ﻣﻌﮑﻮس ﻣﯽ ﮐﻨﺪ .
x
Z=x+y
Z=x.y
y
)اﻟﻒ( ﮔﻴﺖ ANDدو ورودﯼ
)ب( ﮔﻴﺖ ORدو ورودﯼ
َx
x y
x
A
F=ABC
B
C
)پ( ﮔﻴﺖ NOTﺑﺮاﯼ ﻣﻌﮑﻮس ﮐﺮدن ) واروﮔﺮ (
)ت( ﮔﻴﺖ ANDﺳﻪ ورودﯼ
G=A+B+C+D )ث( ﮔﻴﺖ ORﭼﻬﺎر ورودﯼ
A B
C
D
ﺷﮑﻞ ) :(٢-١ﮔﻴﺘﻬﺎﯼ NOR ،NANDو NOT
ﺳﻴﮕﻨﺎل هﺎﯼ ورودﯼ Xو Yدر ﮔﻴﺖ هﺎﯾﯽ ﺑﺎ دو ورودﯼ ،ﻃﺒﻖ ﺷﮑﻞ ) (٢-٢ﻣُﯽ ﺗﻮاﻧﻨﺪ ﺑﻪ ﯾﮑﯽ از ﭼﻬﺎر ﺣﺎﻟﺖ ﻣﻤﮑﻦ ١١ ، ١٠ ، ٠١ ، ٠٠ﺑﺎﺷﻨﺪ .اﯾﻦ ﺳﻴﮕﻨﺎل هﺎﯼ ورودﯼ ﺑﻪ هﻤﺮاﻩ ﺳﻴﮕﻨﺎل هﺎﯼ ﺧﺮوﺟﯽ ﺷﺎن ﺑﺮاﯼ ﮔﻴﺖ هﺎﯼ ANDو ORدر ﺷﮑﻞ ) (٢-٢ﻧﺸﺎن دادﻩ ﺷﺪﻩ اﻧﺪ .ﻧﻤﻮدار زﻣﺎﻧﯽ ﺷﮑﻞ ) (٢-٢ﭘﺎﺳﺦ هﺮ ﻣﺪار را ﺑﻪ هﺮ ﯾﮏ از ﭼﻬﺎر ﺗﺮﮐﻴﺐ ﻣﻤﮑﻦ ورودﯼ ﻧﺸﺎن ﻣﯽ دهﺪ .دﻟﻴﻞ اﻧﺘﺨﺎب ﻧﺎم واروﻧﮕﺮ ﺑﺮاﯼ ﮔﻴﺖ NOTاز ﻣﻘﺎﯾﺴﻪ ﭘﺎﻟﺲ ) Xورودﯼ واروﻧﮕﺮ ( و ) Xﺧﺮوﺟﯽ واروﻧﮕﺮ ( ﺑﺨﻮﺑﯽ ﺁﺷﮑﺎر ﻣﯽ ﺷﻮد .
١٩
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﮔﻴﺖ هﺎﯼ ANDو ORﻣﻤﮑﻦ اﺳﺖ ﺑﻴﺶ از دو ورودﯼ داﺷﺘﻪ ﺑﺎﺷﻨﺪ .ﯾﮏ ﮔﻴﺖ ANDﺑﺎ ﺳﻪ ورودﯼ و ﯾﮏ ﮔﻴﺖ ANDﺑﺎ ﺳﻪ ورودﯼ و ﯾﮏ ﮔﻴﺖ ORﺑﺎ ﭼﻬﺎر ورودﯼ در ﺷﮑﻞ )-١ (٢ﻧﺸﺎن دادﻩ ﺷﺪﻩ اﻧﺪ .ﮔﻴﺖ ANDﺳﻪ ورودﯼ ،ﺑﺸﺮﻃﯽ در ﺧﺮوﺟﯽ ﺧﻮد داراﯼ ﭘﺎﺳﺦ ١ﻣﻨﻄﻘﯽ ﺑﺎﺷﺪ ،ﺧﺮوﺟﯽ ﮔﻴﺖ ٠ﻣﻨﻄﻘﯽ اﺳﺖ .ﮔﻴﺖ ORﺑﺎ ﭼﻬﺎر ورودﯼ داراﯼ ﺧﺮوﺟﯽ ١ﻣﻨﻄﻘﯽ اﺳﺖ ﺑﺸﺮﻃﯽ ﮐﻪ ﺣﺪاﻗﻞ ﯾﮏ ورودﯾﻬﺎ ١،ﻣﻨﻄﻘﯽ ﺑﺎﺷﺪ و اﮔﺮ هﻤﻪ ﺳﻴﮕﻨﺎل هﺎﯼ ورودﯼ ٠ﻣﻨﻄﻘﯽ ﺑﺎﺷﻨﺪ ﺧﺮوﺟﯽ ٠ﻣﻨﻄﻘﯽ ﺧﻮاهﺪ ﺑﻮد . ﻓﺮم رﯾﺎﺿﯽ ﻣﻨﻄﻖ دودوﯾﯽ ،اﻏﻠﺐ ﺟﺒﺮ ﺑﻮل و ﯾﺎ ﺟﺒﺮ ﺳﻮﺋﻴﭽﻴﻨﮓ ﺧﻮاﻧﺪﻩ ﻣﯽ ﺷﻮد .اﯾﻦ ﺟﺒﺮ ﺑﺮاﯼ ﺗﺸﺮﯾﺢ ﻋﻤﻠﻴﺎت ﺷﺒﮑﻪ هﺎﯼ ﭘﻴﭽﻴﺪﻩ در ﻣﺪارهﺎﯼ دﯾﺠﻴﺘﺎل اﺳﺘﻔﺎدﻩ ﻣﯽ ﮔﺮدد . ﻃﺮاﺣﺎن ﺳﻴﺴﺘﻤﻬﺎﯼ دﯾﺠﻴﺘﺎل از ﺟﺒﺮ ﺑﻮل ﺑﺮاﯼ ﺗﺒﺪﯾﻞ اﺷﮑﺎل ﻣﺪارهﺎ ﺑﻪ ﻋﺒﺎرت ﺟﺒﺮﯼ و ﺑﺎﻟﻌﮑﺲ اﺳﺘﻔﺎدﻩ ﻣﯽ ﮐﻨﻨﺪ . 0
0
1 1
0
0
1
1
0
0
0 0
1
0
1
0
1
1
x
1 0
1 0
0 1
y AND : x.y OR : x+y َNOT : x
ﺷﮑﻞ ) (٢-٢ﺳﻴﮕﻨﺎﻟﻬﺎﯼ ورودﯼ – ﺧﺮوﺟﯽ ﺑﺮاﯼ ﮔﻴﺖ هﺎﯼ ) اﻟﻒ( )ب( )پ ( از ﺷﮑﻞ )(٢-١
ﮔﻴﺘﻬﺎﯼ دﯾﮕﺮﯼ ﯾﻌﻨﯽ ﺑﻌﻨﻮان ﮔﻴﺖ هﺎﯼ اﺳﺘﺎﻧﺪارد در ﻃﺮاﺣﯽ ﺳﻴﺴﺘﻢ هﺎﯼ دﯾﺠﻴﺘﺎل ﺑﮑﺎر ﻣﯽ روﻧﺪ .اﯾﻦ ﮔﻴﺘﻬﺎ ﻋﺒﺎرﺗﻨﺪ ازXNOR ، XOR ، NOR ، NAND : .
٢٠
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺗﺎﺑﻊ ، NANDﻣﮑﻤﻞ ANDﻣﯽ ﺑﺎﺷﺪ و ﻣﺘﺸﮑﻞ از ﯾﮏ ﺳﻤﺒﻞ ANDﮐﻪ ﺑﺪﻧﺒﺎل ﺁن داﯾﺮﻩ ﮐﻮﭼﮑﯽ ﻗﺮار ﮔﺮﻓﺘﻪ اﺳﺖ .ﺗﺎﺑﻊ NORﻣﮑﻤﻞ ﺗﺎﺑﻊ ORﺑﻮدﻩ و ﺑﻮﺳﻴﻠﻪ ﺳﻤﺒﻞ ORﮐﻪ ﺑﺪﻧﺒﺎل ﺁن داﯾﺮﻩ ﮐﻮﭼﮏ ﻧﻤﺎﯾﺶ دادﻩ ﻣﯽ ﺷﻮد .ﮔﻴﺖ هﺎﯼ NANDو NORﺑﺴﺎدﮔﯽ ﺑﻮﺳﻴﻠﻪ ﻣﺪارات ﺗﺮاﻧﺰﯾﺴﺘﻮرﯼ ﻗﺎﺑﻞ ﺗﻮﻟﻴﺪ ﺑﻮدﻩ و ﻣﯽ ﺗﻮان ﺑﺮاﺣﺘﯽ ﺗﻮاﺑﻊ ﺑﻮل را ﺑﺎ ﺁﻧﻬﺎ ﭘﻴﺎدﻩ ﻧﻤﻮد . ﮔﺒﺖ XORداراﯼ ﺳﻤﺒﻞ ﻣﺸﺎﺑﻬﯽ ﺑﺎ ORﻣﯽ ﺑﺎﺷﺪ ،ﺑﺠﺰ ﯾﮏ ﺧﻂ ﻣﻨﺤﻨﯽ ﮐﻪ در ﺳﻤﺖ ورودﯼ اش ﮐﺸﻴﺪﻩ ﺷﺪﻩ اﺳﺖ .ﮔﻴﺖ XNORﻣﮑﻤﻞ XORاﺳﺖ و ﻟﺬا ﯾﮏ داﯾﺮﻩ ﮐﻮﭼﮏ اﺿﺎﻓﯽ در ﺳﻤﺖ ﺧﺮوﺟﯽ ﺳﻤﺒﻞ ﺁن وﺟﻮد دارد .
x
( xy)′
x
( x + y)′
y
)اﻟﻒ ( ﮔﻴﺖ NAND
F = x⊕ y
y )ب( ﮔﻴﺖ NOR
X y
F = xΘ y
)پ( ﮔﻴﺖ XOR
X y )ت( ﮔﻴﺖ XNOR
ﺷﮑﻞ ) (٢-3ﮔﻴﺖ هﺎﯼ XNOR ، XOR ، NOR ، NAND ﮔﺴﺘﺮش ورودﯼ ﮔﻴﺖ هﺎ ﮔﻴﺖ هﺎﯼ ﻧﺸﺎن دادﻩ ﺷﺪﻩ ﺑﺠﺮ ﻣﻌﮑﻮس ﮐﻨﻨﺪﻩ و ﺑﺎﻓﺮ ،ﻗﺎﺑﻞ ﮔﺴﺘﺮش ﺑﻪ ﺣﺎﻟﺘﯽ ﺑﻴﺶ از دو ورودﯼ هﺴﺘﻨﺪ ﺑﺸﺮط اﯾﻨﮑﻪ ﻋﻤﻞ دودوﯾﯽ اراﺋﻪ ﺷﺪﻩ ﺑﻮﺳﻴﻠﻪ ﺁﻧﻬﺎ ﺧﻮاص ﺟﺎﺑﺠﺎﯾﯽ و ﺷﺮﮐﺖ ﭘﺬﯾﺮﯼ را داﺷﺘﻪ ﺑﺎﺷﺪ .اﻋﻤﺎل ANDو ORﮐﻪ در ﺟﺒﺮ ﺑﻮل ﺗﻌﺮﯾﻒ ﺷﺪﻧﺪ داراﯼ اﯾﻦ دو ﺧﺎﺻﻴﺖ هﺴﺘﻨﺪ .ﺑﺮاﯼ ﺗﺎﺑﻊ ORدارﯾﻢ : ﺟﺎﺑﺠﺎﯾﯽ
x+ y = y+ x
٢١
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
( x + y) + z = x + ( y + z) = x + y + z
و ﺷﺮﮐﺖ ﭘﺬﯾﺮﯼ
اﯾﻦ رواﺑﻂ ﺑﻴﺎﻧﮕﺮ ﺁﻧﻨﺪ ﮐﻪ ورودﯼ ﻗﺎﺑﻞ ﺗﻌﻮﯾﺾ ﺑﻮدﻩ و ﺑﻨﺎﺑﺮاﯾﻦ ﺗﺎﺑﻊ ORﻗﺎﺑﻞ ﮔﺴﺘﺮش ﺑﻪ ﺳﻪ ﻣﺘﻐﻴﺮ و ﺑﻴﺸﺘﺮ اﺳﺖ . ﺗﻮاﺑﻊ NANDو NORﺧﺎﺻﻴﺖ ﺟﺎﺑﺠﺎﯾﯽ دارﻧﺪ و ورودﯼ ﮔﻴﺖ ﺁﻧﻬﺎ ﻗﺎﺑﻞ ﮔﺴﺘﺮش اﺳﺖ ، ﺑﺸﺮط اﯾﻨﮑﻪ ﺗﻌﺮﯾﻒ ﻋﻤﻞ ﺁﻧﻬﺎ ﺗﺼﺤﻴﺢ ﺷﻮد .ﻣﺸﮑﻞ اﯾﻦ اﺳﺖ ﮐﻪ ﻋﻤﻠﮕﺮهﺎﯼ ، NAND NORﺷﺮﮐﺖ ﭘﺬﯾﺮﯼ ﻧﻴﺴﺘﻨﺪ .ﯾﻌﻨﯽ :
)( x ↓ y) ↓ z ≠ x ↓ ( y ↓ z زﯾﺮا ﻃﺒﻖ ﺷﮑﻞ ) ( ٢-4دارﯾﻢ :
( x ↓ y) ↓ z = [( x − y)′ + z]′ = ( x + y) z′ = xz′ + yz′ x ↓ ( y ↓ z) = [ x + ( y + z)′]′ = x′( y + z) = x′y + x′z
x y ( x ↓ y) ↓ z = ( x +
x ↓ ( y ↓ z ) = x′( y +
x y z
ﺷﮑﻞ ) (٢-4ﻧﻤﺎﯾﺶ ﺷﺮﮐﺖ ﭘﺬﯾﺮ ﻧﺒﻮدن ( x ↓ y) ↓ z ≠ x( y ↓ z) ،NOR
z
٢٢
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺑﺮاﯼ ﻏﻠﺒﻪ ﺑﺮاﯾﻦ ﻣﺸﮑﻞ ﮔﻴﺖ هﺎﯼ ( NAND) NORﭼﻨﺪ ورودﯼ را ﺑﻌﻨﻮان ﻣﮑﻤﻞ OR ) ( ANDﺁن ﺗﻌﺮﯾﻒ ﻣﯽ ﮐﻨﻴﻢ ،ﺑﻨﺎﺑﺮاﯾﻦ دارﯾﻢ :
x ↓ y ↓ z = ( x + y + z)′ x ↑ y ↑ z = ( xyz)′ ﺳﻤﺒﻞ هﺎﯼ ﮔﺮاﻓﻴﮑﯽ ﺑﺮاﯼ ﮔﻴﺖ هﺎﯼ ﺳﻪ ورودﯼ در ﺷﮑﻞ ) (٢-5ﻧﺸﺎن دادﻩ ﺷﺪﻩ اﻧﺪ .در ﻧﻮﺷﺘﻦ ﻣﺘﻮاﻟﯽ اﻋﻤﺎل NORو NANDﺑﺎﯾﺴﺘﯽ ﭘﺮاﻧﺘﺰهﺎ ﺑﻔﺮم ﺻﺤﻴﺢ اﻧﺘﺨﺎب ﺷﻮﻧﺪ ،ﺗﺎ ﺑﻴﺎﻧﮕﺮ ﺗﺮﺗﻴﺐ ﺻﺤﻴﺢ ﮔﻴﺖ هﺎ ﺑﺎﺷﻨﺪ .ﺑﺮاﯼ ﻧﻤﺎﯾﺶ اﯾﻦ ﻣﻄﻠﺐ ﻣﺪار ﺷﮑﻞ )-5 -٢پ( راﻣﻼﺣﻈﻪ ﮐﻨﻴﺪ .ﺗﺎﺑﻊ ﺑﻮل ﺑﺮاﯼ اﯾﻦ ﻣﺪر ﺑﺎﯾﺴﺘﯽ ﺑﻔﺮم زﯾﺮ ﻧﻮﺷﺘﻪ ﺷﻮد :
F = [( ABC)′(DE)′]′ = ABC + DE دوﻣﻴﻦ ﻋﺒﺎرت از راﺑﻄﻪ دﻣﻮرﮔﺎن ﻧﺘﻴﺠﻪ ﺷﺪﻩ اﺳﺖ .اﯾﻦ راﺑﻄﻪ هﻤﭽﻨﻴﻦ ﺑﻴﺎﻧﮕﺮ ﺁﻧﺴﺖ ﮐﻪ ﺟﻤﻊ ﺣﺎﺻﻠﻀﺮب هﺎ ﻗﺎﺑﻞ ﭘﻴﺎدﻩ ﺷﺪن ﺑﻮﺳﻴﻠﻪ ﮔﻴﺖ هﺎ NANDاﺳﺖ . ﮔﻴﺖ هﺎ XORو XNORهﺮ دو داراﯼ ﺧﻮاص ﺟﺎﺑﺠﺎﯾﯽ و ﺷﺮﮐﺖ ﭘﺬﯾﺮﯼ ﺑﻮدﻩ ،ورودﯼ ﺷﺎن ﻗﺎﺑﻞ ﺗﻮﺳﻌﻪ ﺑﻪ ﺑﻴﺸﺘﺮ از دو ﻣﯽ ﺑﺎﺷﺪ .ﻣﻌﻬﺬا ﻣﺪارهﺎﯼ XORﺑﺎ ﭼﻨﺪ ورودﯼ ،از ﻧﻘﻄﻪ ﻧﻈﺮ ﺳﺨﺖ اﻓﺰارﯼ ﻣﺘﺪاول ﻧﻴﺴﺘﻨﺪ .در واﻗﻊ ﺣﺘﯽ ﻓﺮم دو ورودﯼ ﺁن ﻧﻴﺰ ﻣﻌﻤﻮﻻً از ﺳﺎﯾﺮ ﮔﻴﺖ هﺎ ﺳﺎﺧﺘﻪ ﻣﯽ ﺷﻮد .ﻋﻼوﻩ ﺑﺮ اﯾﻦ ﺗﻌﺮﯾﻒ اﯾﻦ ﺗﻮاﺑﻊ ﺑﺎﯾﺴﺘﯽ ﺑﻬﻨﮕﺎم ﮔﺴﺘﺮش ورودﯼ ﺁﻧﻬﺎ ﺗﺼﺤﻴﺢ ﮔﺮدد .ﺗﺎﺑﻊ XORﯾﮏ ﺗﺎﺑﻪ ﻓﺮد اﺳﺖ ﯾﻌﻨﯽ هﺮﮔﺎﻩ ورودﯼ هﺎ ﺗﻌﺪاد ﻏﺮدﯼ ١را دارا ﺑﺎﺷﻨﺪ اﯾﻦ ﺗﺎﺑﻊ ﺑﺮاﺑﺮ ١ﺧﻮاهﺪ ﺑﻮد .ﺳﺎﺧﺘﻤﺎن ﯾﮏ ﮔﻴﺖ XORﺑﺎ ﺳﻪ ورودﯼ در ﺷﮑﻞ ) (٢-۶دﯾﺪﻩ ﻣﯽ ﺷﻮد .اﯾﻦ ﻣﺪار ﻣﻌﻤﻮﻻً ﺑﺎ ﮔﻴﺖ هﺎﯼ دو ورودﯼ ﺗﻬﻴﻪ ﻣﯽ ﮔﺮدد .ﺷﮑﻞ )اﻟﻒ( ﻓﺮم ﮔﺮاﻓﻴﮑﯽ ﺁن را ﺑﺎ ﮔﻴﺖ ﺳﻪ ورودﯼ ﻧﻴﺰ ﻣﯽ ﺗﻮان ﻧﺸﺎن داد ،ﺷﮑﻞ ب ( ﺟﺪول درﺳﺘﯽ در ) پ( ﺑﻄﻮر ﺁﺷﮑﺎر ﻣﺸﺨﺺ ﻣﯽ ﻧﻤﺎﯾﺪ ﮐﻪ ﺧﺮوﺟﯽ F
٢٣
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺑﺮاﺑﺮ ١ﺧﻮاهﺪ ﺑﻮد ،اﮔﺮ ﻓﻘﻂ ﯾﮑﯽ از ورودﯼ هﺎ و ﯾﺎ هﺮ ﺳﻪ ورودﯼ ﺑﺮاﺑﺮ ﺑﺎﺷﺪ .ﺑﻪ ﺑﻴﺎن دﯾﮕﺮ وﻗﺘﯽ ﺗﻌﺪاد ١هﺎ درورودﯼ ﻓﺮد اﺳﺖ Fﻣﺴﺎوﯼ ١اﺳﺖ . اﺿﺎﻓﻪ ﻣﯽ ﻧﻤﺎﯾﺪ ﮐﻪ ﺗﺎﺑﻊ NORﯾﮏ ﺗﺎﺑﻊ زوج اﺳﺖ .ﯾﻌﻨﯽ هﺮﮔﺎﻩ ﺗﻌﺪاد ٠هﺎ در ورودﯼ زوج ﺑﺎﺷﺪ اﯾﻦ ﺗﺎﺑﻊ ﻣﺴﺎوﯼ ١اﺳﺖ .
x
( xyz)′
y
z
)اﻟﻒ ( ﮔﻴﺖ NORﺳﻪ ورودﯼ
x
( x + y + z )′
y
z
)ب( ﮔﻴﺖ NORﺳﻪ ورودﯼ
A
B
C
F = [( ABC )′.( DE )′]′ = ABC + DE
)پ( ﮔﻴﺖ هﺎﯼ ﻣﺘﻮاﻟﯽ NAND
D E
ﺷﮑﻞ ) (٢-5ﮔﻴﺖ هﺎﯼ NANDو NORﭘﺸﺖ ﺳﺮ هﻢ و ﭼﻨﺪ ورودﯼ
X y F = x⊕ y⊕ z
Z )اﻟﻒ( ﺑﺎ ﮔﻴﺖ هﺎﯼ دو ورودﯼ
F = x⊕ y⊕ z )ب( ﯾﮏ ﮔﻴﺖ ﺳﻪ ورودﯼ
ﺷﮑﻞ ) (٢-۶ﮔﻴﺖ XORﺳﻪ ورودﯼ
X y z
٢٤
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ﻣﻨﻄﻖ ﻣﺜﺒﺖ و ﻣﻨﻔﯽ
ﺳﻴﮕﻨﺎل دودوﯾﯽ در ورودﯼ ﯾﺎ ﺧﺮوﺟﯽ هﺮ ﮔﻴﺖ ﯾﮑﯽ از دو ﻣﻘﺪار را ﺑﺠﺰ در ﺣﺎﻟﺖ ﮔﺬرا ، دارد .ﯾﮏ ﻣﻘﺪار ﺳﻴﮕﻨﺎل ﻣﻨﻄﻖ ١-و دﯾﮕﺮﯼ ﻣﻨﻄﻖ ٠-را ﻧﻤﺎﯾﺶ ﻣﯽ دهﺪ .ﭼﻮن دو ﻣﻘﺪار ﺳﻴﮕﻨﺎل ﻣﺘﻌﻠﻖ ﺑﻪ دو ارزش ﻣﻨﻄﻘﯽ اﺳﺖ ،ﻟﺬا دو اﻧﺘﺴﺎب ﻣﺘﻔﺎوت ﺑﺮاﯼ دو ارزش ﻣﻨﻄﻘﯽ ﻣﯽ ﺗﻮان اﺧﺘﻴﺎر ﮐﺮد ،ﺷﮑﻞ ) (٢-٧اﻧﺘﺨﺎب ﺳﻄﺢ ﺑﺎﻻﺗﺮ Hﺑﺮاﯼ ﻧﻤﺎﯾﺶ ﻣﻨﻄﻖ ١ﻣﻄﺎﺑﻖ ﺷﮑﻞ )-٢-٧اﻟﻒ( ،ﺳﻴﺴﺘﻢ ﻣﻨﻄﻖ ﻣﺜﺒﺖ را ﻣﻌﺮﻓﯽ ﻣﯽ ﻧﻤﺎﯾﺪ و اﻧﺘﺨﺎب ﺳﻄﺢ ﭘﺎﯾﻴﻦ Lﺑﻌﻨﻮان ﻣﻨﻄﻖ .١ ﻣﻘﺪار ﻣﻨﻄﻘﯽ
ﻣﻘﺪار ﺳﻴﮕﻨﺎل H
٠ L
١ )ب( ﻣﻨﻄﻖ ﻣﻨﻔﯽ
ﻣﻘﺪار ﺳﻴﮕﻨﺎل
ﻣﻘﺪار ﻣﻨﻄﻘﯽ
H
٠
L
١ )اﻟﻒ (ﻣﻨﻄﻖ ﻣﺜﺒﺖ
ﺷﮑﻞ ) (٢-٧ﻋﻼﻣﺖ داﻣﻨﻪ ﺳﻴﮕﻨﺎل و ﻧﻮع ﻣﻨﻄﻖ
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ٢-١ﺗﻌﺮﯾﻒ اﺻﻮﻟﯽ ﺟﺒﺮ ﺑﻮل
در ﺳﺎل ١٨۵۴ﺟﻮرج ﺑﻮل روش اﺻﻮﻟﯽ ﺑﺮاﯼ ﻣﻨﻄﻖ ﻣﻌﺮﻓﯽ ﻧﻤﻮد و ﺑﺪﯾﻦ ﻃﺮﯾﻖ ﯾﮏ ﺳﻴﺴﺘﻢ ﺟﺒﺮﯼ را ﭘﺎﯾﻪ رﯾﺰﯼ ﮐﺮد ﮐﻪ اﻣﺮوز ﺟﺒﺮ ﺑﻮل ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮد .ﺑﺮاﯼ ﺗﻌﺮﯾﻒ ﻣﺴﺘﺪل ﺟﺒﺮ ﺑﻮل ،ﻣﺎ اﺻﻮل ﻓﺮﻣﻮﻟﻪ ﺷﺪﻩ ﺑﻮﺳﻴﻠﻪ هﺎﻧﺘﻴﻨﮕﺘﻮن در ١٩٠۴را ﺑﻪ ﮐﺎر ﺧﻮاهﻴﻢ ﺑﺮد .اﯾﻦ اﺻﻮل ﺑﺮاﯼ ﺗﻌﺮﯾﻒ ﺟﺒﺮ ﺑﻮل ﻣﻨﺤﺼﺮ ﺑﻪ ﻓﺮد ﻧﻴﺴﺘﻨﺪ و اﺻﻮل دﯾﮕﺮﯼ ﻧﻴﺰ در ﺁن ﺑﮑﺎر رﻓﺘﻪ اﻧﺪ . ﺟﺒﺮ ﺑﻮل ﯾﮏ ﺳﺎﺧﺘﺎر ﺟﺒﺮﯼ اﺳﺖ ﮐﻪ ﺑﺎ ﻋﻨﺎﺻﺮ ﻣﺠﻤﻮﻋﻪ Bهﻤﺮاﻩ ﺑﺎ دو ﻋﻤﻠﮕﺮ ) (+و )(. ﺗﻌﺮﯾﻒ ﺷﺪﻩ و داراﯼ اﺻﻮل زﯾﺮ ) اﺻﻮل هﺎﻧﺘﻴﻨﮕﺘﻮن ( ﺑﺎﺷﺪ : ( a) -١ﻣﺠﻤﻮﻋﻪ ﻧﺴﺒﺖ ﺑﻪ ﻋﻤﻠﮕﺮ ) (.ﺑﺴﺘﻪ ﺑﺎﺷﺪ . ) ( bﻣﺠﻤﻮﻋﻪ ﻧﺴﺒﺖ ﺑﻪ ﻋﻤﻠﮕﺮد ) (.ﺑﺴﺘﻪ ﺑﺎﺷﺪ . ( a) -٢ﻋﻨﺼﺮ ﺧﻨﺜﯽ در ﻣﺠﻤﻮﻋﻪ ﺑﺮاﯼ ) (+ﺑﺮاﺑﺮ ﺑﺎ ٠ﺑﺎﺷﺪ .
x+0=0+ x= x (b) -٣ﻋﻨﺼﺮ ﺧﻨﺜﯽ در ﻣﺠﻤﻮﻋﻪ ﺑﺮاﯼ ) (.ﺑﺮاﺑﺮ ١ﺑﺎﺷﺪ .
x.1 = 1.x = x (a) -۴ﻣﺠﻤﻮﻋﻪ ﻧﺴﺒﺖ ﺑﻪ ) (+داراﯼ ﺧﺎﺻﻴﺖ ﺟﺎﺑﺠﺎﯾﯽ ﺑﺎﺷﺪ .
x+ y= y+ x ) (bﻣﺠﻮﻋﻪ ﻧﺴﺒﺖ ﺑﻪ ) (.داراﯼ ﺧﺎﺻﻴﺖ ﺟﺎﺑﺠﺎﯾﯽ ﺑﺎﺷﺪ :
x. y = y..x (.) ( a) -۴روﯼ ) (+داراﯼ ﺧﺎﺻﻴﺖ ﭘﺨﺸﯽ اﺳﺖ . ) (+) (bروﯼ ) (.داراﯼ ﺧﺎﺻﻴﺖ ﭘﺨﺸﯽ اﺳﺖ .
)x.( y + z) = ( x. y) + ( x.z
)x + ( y.z) = ( x + y).( x + z
٢
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ -۵ﺑﻪ ازاﯼ هﺮ ﻋﻨﺼﺮ
x∈ B
ﻋﻨﺼﺮﯼ ﻣﺜﻞ
x∈ B
وﺟﻮد داﺷﺘﻪ ﺑﺎﺷﺪ ) اﯾﻦ ﻋﻨﺼﺮ
ﻣﮑﻤﻞ ﺧﻮاﻧﺪﻩ ﻣﯽ ﺷﻮد ( ﺑﻄﻮرﯼ ﮐﻪ : )( a
x + x′ =1
)( b
x.x ′ = 0
-۶ﺣﺪاﻗﻞ دو ﻋﻨﺼﺮ ﻣﺎﻧﻨﺪ x, y ∈ Bﻣﻮﺟﻮد ﺑﺎﺷﻨﺪ ﺑﻄﻮرﯾﮑﻪ x ≠ y :
ازﻣﻘﺎﯾﺴﻪ ﺟﺒﺮ
ﺑﻮل ﺑﺎ رﯾﺎﺿﻴﺎت ﺟﺒﺮﯼ ﻣﻌﻤﻮﻟﯽ ) ﻣﻴﺪان اﻋﺪاد ﺣﻘﻴﻘﯽ ( اﺧﺘﻼﻓﺎت زﯾﺮ ﻣﻼﺣﻈﻪ ﻣﯽ ﮔﺮدﻧﺪ : -١اﺻﻮل هﺎﻧﺘﻴﻨﮕﺘﻮن ﺷﺎﻣﻞ اﺻﻞ اﺷﺘﺮاﮎ ﭘﺬﯾﺮﯼ ﻧﻴﺴﺘﻨﺪ .اﯾﻦ ﻗﺎﻧﻮن ﺑﺮاﯼ ﺟﺒﺮ ﺑﻮل ﻧﻴﺰ وﺟﻮد دارد و ﻣﯽ ﺗﻮان ﺁن را ﺑﺮاﯼ هﺮ دو ﻋﻤﻠﮕﺮ از ﺳﺎﯾﺮ اﺻﻮل ﺑﺪﺳﺖ ﺁورد . -٢ﻗﺎﻧﻮن ﺗﻮزﯾﻊ ﭘﺬﯾﺮﯼ ) (+و ) ( .اﺧﺘﻼف ﺑﻌﺪﯼ اﺳﺖ .راﺑﻄﻪ :
)x + ( y.z) = ( x + y).) x + z ﺑﺮاﯼ ﺟﺒﺮ ﺑﻮل ﻣﻌﺘﺒﺮ وﻟﯽ ﺑﺮاﯼ ﺟﺒﺮ ﻣﻌﻤﻮﻟﯽ ﻗﺎﺑﻞ ﻗﺒﻮل ﻧﻴﺴﺖ . -٣ﺟﺒﺮ ﺑﻮل ﻣﻌﮑﻮس ﺟﻤﻊ و ﺿﺮب را ﻧﺪارد ،ﺑﻨﺎﺑﺮاﯾﻦ ﺗﻔﺮﯾﻖ و ﺗﻘﺴﻴﻢ ﻣﻔﻬﻮم ﻧﺨﻮاهﻨﺪ داﺷﺖ . -۴اﺻﻞ ۵ﻋﻤﻠﮕﺮد دﯾﮕﺮﯼ ﺑﻨﺎم ﻣﮑﻤﻞ را ﻣﻌﺮﻓﯽ ﻣﯽ ﻧﻤﺎﯾﺪ ﮐﻪ در ﺟﺒﺮ ﻣﻌﻤﻮﻟﯽ وﺟﻮد ﻧﺪارد . -۵ﺟﺒﺮ ﻣﻌﻤﻮﻟﯽ در ﻣﻮرد اﻋﺪاد ﺣﻘﻴﻘﯽ اﺳﺖ ﮐﻪ ﺑﯽ ﻧﻬﺎﯾﺖ ﻋﻨﺼﺮ را ﺷﺎﻣﻞ ﻣﯽ ﺷﻮد . ﺟﺒﺮ ﺑﻮل ﺑﺎ ﻋﻨﺎﺻﺮﯼ از ﻣﺠﻤﻮﻋﻪ Bﮐﻪ اﻟﺒﺘﻪ ﺗﺎ ﮐﻨﻮن ﻣﻌﺮﻓﯽ ﻧﺸﺪﻩ اﻧﺪ ﺳﺮو ﮐﺎر داﺷﺖ وﻟﯽ درﺟﺒﺮ ﺑﻮل دو ارزﺷﯽ ﯾﺎ دو ﻣﻘﺪارﯼ ﮐﻪ در زﯾﺮ ﺗﻌﺮﯾﻒ ﺷﺪﻩ B ،ﯾﮏ ﻣﺠﻤﻮﻋﻪ دو ﻋﻨﺼﺮﯼ اﺳﺖ ﮐﻪ اﯾﻦ دو ﻋﻨﺼﺮ ٠و ١ﻣﯽ ﺑﺎﺷﻨﺪ . ٢-٢ﻗﻀﻴﻪ هﺎﯼ اﺻﻠﯽ و ﺧﻮاص ﺟﺒﺮ ﺑﻮل
٣
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
اﺻﻮل هﺎﻧﺘﻴﮕﺘﻮن ﺑﺼﻮرت ﺟﻔﺖ ﺟﻔﺖ ﻟﻴﺴﺖ و ﺑﺎ ﻗﺴﻤﺖ هﺎﯼ ) ( aو ) ( bﻣﺸﺨﺺ ﺷﺪ .هﺮ ﯾﮏ از اﯾﻦ دو را ﻣﯽ ﺗﻮان از دﯾﮕﺮﯼ ﺑﺪﺳﺖ ﺁورد ﺑﺸﺮط اﯾﻨﮑﻪ ﻋﻤﻠﮕﺮهﺎ و ﻧﻴﺰ ﻋﻨﺎﺻﺮ ﺧﻨﺜﯽ ﺗﻌﻮﯾﺾ ﺷﻮﻧﺪ .اﯾﻦ ﺧﺎﺻﻴﺖ ﻣﻬﻢ درﺟﺒﺮ ﺑﻮل ﺑﻪ اﺻﻞ دوﮔﺎﻧﮕﯽ ﻣﻌﺮوف اﺳﺖ و ﺑﻴﺎن ﻣﯽ دارد ﮐﻪ هﺮ ﻋﺒﺎرت ﺟﺒﺮﯼ ﻣﻨﺘﺠﻪ از اﺻﻮل ﺟﺒﺮ ﺑﻮل ﺣﺘﯽ ﺑﺎ ﺗﻌﻮﯾﺾ ﻋﻤﻠﮕﺮ هﺎ و ﻋﻨﺎﺻﺮ ﺧﻨﺜﯽ ﺑﺎز هﻢ ﻣﻌﺘﺒﺮ ﻣﯽ ﺑﺎﺷﺪ .در ﺟﺒﺮ ﺑﻮل دو ارزﺷﯽ ﻋﻨﺎﺻﺮ ﺧﻨﺜﯽ و ﺧﻮد ﻋﻨﺎﺻﺮ ﻣﺤﻤﻮﻋﻪ Bﯾﮑﺴﺎﻧﻨﺪ ١ :و ٠اﺻﻞ دوﮔﺎﻧﮕﯽ ﮐﺎرﺑﺮدهﺎﯼ ﻓﺮاواﻧﯽ دارد .اﮔﺮ دو ﮔﺎن ﯾﮏ ﻋﺒﺎرت ﺟﺒﺮﯼ ،ﻣﻮرد ﻧﻈﺮ ﺑﺎﺷﺪ ﺗﻨﻬﺎ ﮐﺎﻓﯽ اﺳﺖ ﻋﻤﻠﮕﺮهﺎﯼ ORو ANDﺗﻌﻮﯾﺾ ﺷﺪﻩ و ٠هﺎ ﺑﻪ ١هﺎ و هﻤﭽﻨﻴﻦ ١هﺎ ﺑﻪ ٠هﺎ ﺗﺒﺪﯾﻞ ﮔﺮدﻧﺪ . ﺗﺌﻮرﯼ هﺎﯼ اﺳﺎﺳﯽ ﺟﺪول ) (٢-١ﺷﺶ ﺗﺌﻮرﯼ و ﭼﻬﺎر اﺻﻞ از ﺟﺒﺮ ﺑﻮل را در ﺑﺮ دارد .در ﺳﻤﺖ ﭼﭗ رواﺑﻂ ، ﺷﻤﺎرﻩ اﺻﻮل ﺑﮑﺎر رﻓﺘﻪ ﻧﻮﺷﺘﻪ ﺷﺪﻩ اﺳﺖ . ﺟﺪول ) (٢-١اﺻﻮل و ﻗﻀﺎﯾﺎﯼ ﺟﺒﺮ ﺑﻮل (
(b) xy = yx (b) x (yz) = (xy)z )(b) x+yz = (x+y)(x+z
(a) x + 0 = x ( a) x + xَ = ١ (a) x + x = x (a) x + 1 = 1 (xَ )َ =x (a) x+y=y+x (a) x+(y+z) = (x+y)+z (a) x(y+z) = xy+xz
(b) x.1 = x (b) x.x = 0 (b) x.x = x (b) x .0 = 0
)(b) (xy) = x+y (b) x(x+y) = x
(a) (x+y) = x y (a) x + xy = x
اﺻﻞ ٢ اﺻﻞ ۵ ﺗﺌﻮرﯼ ١ ﺗﺌﻮرﯼ ٢ ﺗﺌﻮرﯼ ٣رﺟﻌﺖ اﺻﻞ ٣ﺟﺎﺑﺠﺎﯾﯽ ﺗﺌﻮرﯼ ۴ﺷﺮﮐﺖ ﭘﺬﯾﺮﯼ اﺻﻞ ۴ﺗﻮزﯾﻊ ﭘﺬﯾﺮﯼ ﯾﺎ ﭘﺨﺶ ﺗﺌﻮرﯼ ۵دﻣﻮرﮔﺎن ﺗﺌﻮرﯼ ۶ﺟﺬب
٢-٣ﺗﻮاﺑﻊ ﺑﻮل ﯾﮏ ﻣﺘﻐﻴﻴﺮ دودوﯾﯽ ﻣﯽ ﺗﻮاﻧﺪ ﯾﮑﯽ از دو ﻣﻘﺪار ٠ﯾﺎ ١را اﺧﺘﻴﺎر ﮐﻨﺪ .ﯾﮏ ﺗﺎﺑﻊ ﺑﻮل ﻋﺒﺎرﺗﯽ اﺳﺖ ﮐﻪ از ﻣﺘﻐﻴﺮهﺎﯼ دودوﯾﯽ ،ﻋﻤﻠﮕﺮ هﺎﯼ NOT ، AND ، ORﭘﺮاﻧﺘﺰ هﺎ و
٤
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﻋﻼﻣﺖ ﺗﺴﺎوﯼ ﺗﺸﮑﻴﻞ ﺷﺪﻩ اﺳﺖ .ﺑﻪ ازاﯼ ﻣﻘﺎدﯾﺮ ﻣﻔﺮوﺿﯽ از ﻣﺘﻐﻴﺮهﺎ ﺗﺎﺑﻊ ﻓﻘﻂ ﻣﯽ ﺗﻮاﻧﺪ ٠ﯾﺎ ١ﺑﺎﺷﺪ .ﻣﺜﻼً ﺗﺎﺑﻊ ﺑﻮل F = xyz ′را در ﻧﻈﺮ ﺑﮕﻴﺮﯾﺪ .ﺗﺎﺑﻊ f1ﺑﺮاﺑﺮ ﺑﺎ ١اﺳﺖ
1
ﺑﺸﺮﻃﯽ ﮐﻪ y=1 ، x=1و zَ =1ﺑﺎﺷﺪ ،در ﻏﻴﺮ اﯾﻦ ﺻﻮرت F = 0ﺧﻮاهﺪ ﺑﻮد .ﺑﺮاﯼ
1
ﻧﻤﺎﯾﺶ ﯾﮏ ﺗﺎﺑﻊ ﺑﻔﺮم ﺟﺪول درﺳﺘﯽ ﻧﻴﺎز ﺑﻪ 2nﺗﺮﮐﻴﺐ از ١هﺎ و ٠هﺎ ﻣﺮﺑﻮط ﺑﻪ nﺑﻪ ﺗﻐﻴﻴﺮ دودوﯾﯽ و ﺳﺘﻮﻧﯽ ﯾﮑﻪ در ﺁن ﻣﻘﺪار ﺗﺎﺑﻊ ﺑﺮاﺑﺮ ٠ﯾﺎ ١اﺳﺖ ،دارﯾﻢ .از ﺟﺪول )(٢-٢ دﯾﺪﻩ ﻣﯽ ﺷﻮد وﮐﻪ ﺑﺮاﯼ ﺳﻪ ﻣﺘﻐﻴﺮ ٨ﺣﺎﻟﺖ ﺟﺪا ﻣﯽ ﺗﻮان در ﻧﻈﺮ ﮔﺮﻓﺖ .در ﺟﺪول )-٢ ، (٢ﭼﻬﺎر ردﯾﻒ ﺁﺧﺮ ﻣﺴﺎوﯼ ١و xyدر ردﯾﻔﻬﺎﯼ ٠٠١و ١٠١ﺑﺮاﺑﺮ ٠١اﺳﺖ .ﺗﺮﮐﻴﺐ ﺁﺧﺮﯼ دﻻﻟﺖ ﺑﺮ x=١ﻧﻴﺰ دارد .ﺑﻨﺎﺑﺮاﯾﻦ ﺑﺮاﯼ F2=١ﭘﻨﺞ ﺣﺎﻟﺖ وﺟﻮد دارد . ﺟﺪول ) (٢-٢ﺟﺪول درﺳﺘﯽ ﺑﺮاﯼ , F = xy ′ + xz 4
F = xyz F = x + y ′z , F = x ′y ′z + x ′yz + xy 1 2 3
F4
F3
F2
F1
Z
y
x
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
1
0
1
1
0
0
1
1
0
1
1
1
0
0
0
1
1
1
1
0
1
0
1
0
0
1
0
0
1
1
0
0
1
1
1
1
1
٥
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ﻋﻤﻠﻴﺎت ﺟﺒﺮﯼ
ﻟﻴﺘﺮال ،ﯾﮏ ﻣﺘﻐﻴﺮ ﺑﺎ ﭘﺮﯾﻢ ﯾﺎ ﺑﺪون ﭘﺮﯾﻢ اﺳﺖ .وﻗﺘﯽ ﮐﻪ ﯾﮏ ﺗﺎﺑﻊ ﺑﻮﺳﻴﻠﻪ ﮔﻴﺖ ﻣﻨﻄﻘﯽ ﭘﻴﺎدﻩ ﺷﻮد هﺮ ﻟﻴﺘﺮال در ﺗﺎﺑﻊ ﻣﻌﺮوف ﯾﮏ ورودﯼ ﺑﻪ ﯾﮏ ﮔﻴﺖ و هﺮ ﺟﻤﻠﻪ ﻣﻨﻄﻘﯽ ﻧﻴﺰ ﺗﻮﺳﻂ ﯾﮏ ﮔﻴﺖ ﺳﺎﺧﺘﻪ ﻣﯽ ﺷﻮد .ﻣﯽ ﻧﻴﻤﻢ ﮐﺮدن ﺗﻌﺪاد ﻣﺘﻐﻴﺮهﺎ و ﺟﻤﻼت ،ﻧﺘﻴﺠﻪ اش ﺳﺎﺧﺖ دﺳﺘﮕﺎهﯽ ﺑﺎ ﻗﻄﻌﺎت ﮐﻤﺘﺮ اﺳﺖ . اﻟﺒﺘﻪ هﻤﻴﺸﻪ ﻣﻤﮑﻦ ﻧﻴﺴﺖ ﮐﻪ هﺮ دو را ﺑﺎ هﻢ ﮐﺎهﺶ داد .ﻓﻌﻼً ﻣﺎ ﻣﯽ ﻧﻴﻤﻢ ﺳﺎزﯼ را ﻓﻘﻂ ﺑﻪ ﻣﺘﻐﻴﺮهﺎ ﻣﺤﺪود ﻣﻴﮑﻨﻴﻢ ﺗﻌﺪاد ﻣﺘﻐﻴﺮ هﺎ در ﺗﺎﺑﻊ ﺑﻮل ﻣﯽ ﺗﻮاﻧﺪ ﺑﺎ ﯾﮏ ﺳﺮﯼ اﻋﻤﺎل ﺟﺒﺮﯼ ﻣﯽ ﻧﻴﻤﻢ ﮔﺮدد ،ﻣﺘﺎﺳﻔﺎﻧﻪ ﻗﻮاﻧﻴﻦ ﻣﺸﺨﺺ و ﻣﻌﻴﻨﯽ ﮐﻪ ﺗﻀﻤﻴﻦ ﮐﻨﻨﺪﻩ ﻓﺮم ﻧﻬﺎﯾﯽ ﺑﺎﺷﺪ وﺟﻮد ﻧﺪارد .ﺗﻨﻬﺎ روش ﻣﻮﺟﻮد ﺳﻌﯽ در ﮐﺎهﺶ ﻣﺪار و ﺗﺪاوم اﯾﻦ ﻋﻤﻞ ﺑﺎ اﺳﺘﻔﺎدﻩ از اﺻﻮل اوﻟﻴﻪ ،ﺗﺌﻮرﯼ هﺎﯼ اﺻﻠﯽ و هﺮ روش ﻋﻤﻠﻴﺎﺗﯽ دﯾﮕﺮﯼ ،ﮐﻪ ﺿﻤﻦ ﻋﻤﻞ ﺑﺎ ﺁﻧﻬﺎ ﺣﺎﺻﻞ ﻣﯽ ﮔﺮدد ،ﻣﯽ ﺑﺎﺷﺪ . ﻣﺜﺎل : ٢-١ﺗﺎﺑﻊ ﺑﻮﻟﯽ زﯾﺮ را از ﻧﻈﺮ ﺗﻌﺪاد ﻣﺘﻐﻴﺮهﺎ ﻣﯽ ﻧﻴﻤﻢ ﮐﻨﻴﺪ .
1. x + x′y = ( x + x′)( x + y) = 1.( x + y) = x + y 2. x( x′ + y) = xx′ + xy = 0 + xy = xy 3. x′y′z + x′yz + yz = x′z( y′ + y) + xy′ = x′z + xy′ )4.xy + x′z + yz = xy + x′z + yz( x + x′ = xy + x′z + xyz + x′yz )= xy(1 + z) + x′z (1 + y = xy + x′z )5. ( x + y)( x′ + z )( y + z) = ( x + y)( x′ + z ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ دو ﮔﺎﻧﻪ ﺑﻮدن ﺗﺎﺑﻊ ۴ ﺗﺎﺑﻊ ١و ٢دوﮔﺎن ﯾﮑﺪﯾﮕﺮﻧﺪ و ﻋﺒﺎرت دوﮔﺎﻧﯽ رادر ﻣﺮاﺣﻞ ﻣﺮﺑﻮط ﺑﻪ ﺧﻮد ﺑﮑﺎر ﻣﯽ ﺑﺮﻧﺪ . ﺗﺎﺑﻊ ٣هﻢ ارزﯼ ﺗﻮاﺑﻊ F4,F3ﺑﺤﺚ ﺷﺪﻩ در ﻗﺒﻞ را ﻧﺸﺎن ﻣﯽ دهﺪ .ﭼﻬﺎرﻣﻴﻦ ﺗﺎﺑﻊ روﺷﻨﮕﺮ اﯾﻦ واﻗﻌﻴﺖ اﺳﺖ ﮐﻪ اﻓﺰاﯾﺶ در ﺗﻌﺪاد ﻣﺘﻔﻴﺮهﺎ ﮔﺎهﯽ اوﻗﺎت ﺳﺒﺐ ﺳﺎدﻩ ﺗﺮ
٦
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺷﺪن ﻋﺒﺎرت ﻧﻬﺎﯾﯽ ﻣﯽ ﮔﺮدد .ﺗﺎﺑﻊ ۵۴ﻣﺴﺘﻘﻴﻤﺎً ﺳﺎدﻩ ﻧﺸﺪﻩ اﺳﺖ وﻟﯽ ﺑﺎ اﺳﺘﻔﺎدﻩ از دوﮔﺎن ﻣﺮاﺣﻞ رﻣﺮﺑﻮط ﺑﻪ ﺗﺎﺑﻊ ۴ﻣﯽ ﺗﻮاﻧﺪ ﺣﺎﺻﻞ ﮔﺮدد . ﻣﮑﻤﻞ ﯾﮏ ﺗﺎﺑﻊ ﻣﮑﻤﻞ ﯾﮏ ﺗﺎﺑﻊ Fﺗﺎﺑﻌﯽ اﺳﺖ ﻣﺎﻧﻨﺪ َ Fﮐﻪ ﺑﺎ ﺗﻌﻮﯾﺾ ٠هﺎ ﺑﻪ ١هﺎ و ١هﺎ ﺑﻪ ٠هﺎ در ﻣﻘﺪار Fﺣﺎﺻﻞ ﻣﯽ ﮔﺮدد .ﻣﮑﻤﻞ ﯾﮏ ﺗﺎﺑﻊ ﻣﻤﮑﻦ اﺳﺖ ﺑﺎ اﺳﺘﻔﺎدﻩ از ﺗﺌﻮرﯼ دﻣﻮرﮔﺎن ﻧﻴﺰ ﺑﺪﺳﺖ ﻣﯽ ﺁﯾﺪ .زوج ﻗﻮاﻧﻴﻦ دﻣﻮرﮔﺎن ﺑﺮاﯼ دو ﻣﺘﻐﻴﻴﺮ در ﺟﺪول ) (٢-١ﻟﻴﺴﺖ ﺷﺪﻩ اﻧﺪ .ﺗﺌﻮرﯼ هﺎﯼ دﻣﻮرﮔﺎن ﻗﺎﺑﻞ ﺗﻌﻤﻴﻢ ﺑﺮاﯼ ﺳﻪ ﻣﺘﻐﻴﺮ و ﯾﺎ ﺑﻴﺸﺘﺮ از ﺁن ﻧﻴﺰ هﺴﺘﻨﺪ . ﻓﺮم ﺳﻪ ﻣﺘﻐﻴﺮ ﺗﺌﻮرﯼ اول دﻣﻮرﮔﺎن در زﯾﺮ ﺁﻣﺪﻩ اﺳﺖ .اﺻﻮل و ﺗﺌﻮرﯼ هﺎﯼ ﺑﮑﺎر رﻓﺘﻪ هﻤﺎن هﻤﺎﯾﯽ هﺴﺘﻨﺪ ﮐﻪ در ﺟﺪول ) (٢-١ﺁوردﻩ ﺷﺪﻩ اﻧﺪ .
( A + B + C)′ = ( A + X )′
ﺑﺎ ﻓﺮض B + C = A ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺗﺌﻮرﯼ ( a) -۵دﻣﻮرﮔﺎن ﺑﺎ ﺟﺎﯾﮕﺰﯾﻨﯽ B + C = X
= A′X ′
= A′.( B + C )′
ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺗﺌﻮرﯼ ( a) -۴ﺷﺮﮐﺖ ﭘﺬﯾﺮﯼ
= A′B ′C ′
ﺗﺌﻮرﯼ هﺎﯼ دﻣﻮرﮔﺎن ﺑﺮاﯼ هﺮ ﺗﻌﺪاد از ﻣﺘﻐﻴﺮ هﺎ اﺑﺘﺪ ﺑﻪ ﺷﮑﻞ دو ﻣﺘﻐﻴﺮﻩ در ﺁﻣﺪﻩ و ﺳﭙﺲ ﺑﺎ ﺟﺎﯾﮕﺰﯾﻨﯽ هﺎﯼ ﻣﺘﻮاﻟﯽ ،ﻣﺸﺎﺑﻪ ﺑﺎ ﺁﻧﭽﻪ در ﻓﻮق دﯾﺪﻩ ﺷﺪ ،ﻧﺘﻴﺠﻪ ﻧﻬﺎﯾﯽ ﺣﺎﺻﻞ ﻣﯽ ﮔﺮدد . اﯾﻦ ﺗﺌﻮرﯾﻬﺎ ﻣﯽ ﺗﻮاﻧﺪ ﺑﻪ ﺻﻮرت زﯾﺮ ﻋﻤﻮﻣﻴﺖ دادﻩ ﺷﻮﻧﺪ .
( A + B + C + D + ... + F )′ = A′B ′C ′D ′...F ′ ( ABCD...F )′ = A′ + B ′ + C ′ + D ′ + ... + F ′ ﻓﺮم هﺎﯼ ﮐﻠﯽ ﺗﺌﻮرﯼ دﻣﻮرﮔﺎن ﺑﻴﺎن ﻣﯽ ﮐﻨﺪ ﮐﻪ ﻣﮑﻤﻞ هﺮ ﺗﺎﺑﻊ ﺑﺎ ﺗﻌﻮﯾﺾ ﻋﻤﻠﮕﺮهﺎﯼ ANDو ORو ﻣﮑﻤﻞ ﻧﻤﻮدن هﺮ ﻣﺘﻐﻴﺮ ﺣﺎﺻﻞ ﻣﯽ ﺷﻮد .
٧
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ﻣﺜﺎل : ٢-٢ﻣﮑﻤﻞ ﺗﻮاﺑﻊ F = x( y ′z ′ + yz) , F = x ′yz ′ + x ′y ′zرا ﺑﺪﺳﺖ ﺁورﯾﺪ .
2
1
ﺗﺌﻮرﯼ دﻣﻮرﮔﺎن را هﺮ ﭼﻨﺪ ﺑﺎر ﮐﻪ ﻻزم ﺑﺎﺷﺪ ﺑﮑﺎر ﺑﺒﺮﯾﺪ .ﻣﮑﻤﻞ هﺎ ﺑﻔﺮم زﯾﺮ ﺣﺎﺻﻞ ﻣﯽ ﮔﺮدﻧﺪ
)F ′ = ( x′yz′ + x′y′z )′ = ( x′yz′)( x′y′z ) = ( x + y′ + z )( x + y + z′ 1 F ′ = [ x( y′z′ + yz)]′ = x′ + ( y′z′) + y′z′ + yz)′ = x′ + ( y′z′)′.( yz)′ 2 )= x′ + ( y + z )( y′ + z′ روش ﺳﺎدﻩ ﺗﺮﯼ ﺑﺮاﯼ ﺑﺪﺳﺖ ﺁوردن ﻣﮑﻤﻞ ﯾﮏ ﺗﺎﺑﻊ اﯾﻦ اﺳﺖ ﮐﻪ اﺑﺘﺪا دوﮔﺎن ﺁﻧﺮا ﺑﺪﺳﺖ ﺁوردﻩ و ﺳﭙﺲ ﻣﺘﻐﻴﺮهﺎﯾﺶ را ﻣﮑﻤﻞ ﻧﻤﺎﯾﻴﻢ .اﯾﻦ روش ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﻓﺮم ﮐﻠﯽ ﺗﺌﻮرﯼ دﻣﻮرﮔﺎن ﻧﺘﻴﺠﻪ ﻣﯽ ﺷﻮد .ﺑﺨﺎﻃﺮ داﺷﺘﻪ ﺑﺎﺷﻴﺪ ﮐﻪ دوﮔﺎن ﯾﮏ ﺗﺎﺑﻊ ﺑﺎ ﺗﺒﺪﯾﻞ ﻋﻤﻠﮕﺮ ANDو ORوﺗﺒﺪﯾﻞ ١هﺎ و ٠هﺎ ﺑﻪ ﯾﮑﺪﯾﮕﺮ ﺑﺪﺳﺖ ﻣﯽ ﺁﯾﺪ . ﻣﺜﺎل : ٢-٣ﻣﮑﻤﻞ هﺎﯼ ﺗﻮاﺑﻊ F2 , F1ﻣﺜﺎل ٢-٢را ﺑﺎﺗﻮﺟﻪ ﺑﻪ دوﮔﺎن ﺁﻧﻬﺎ و ﻣﮑﻤﻞ ﮐﺮدن هﺮ ﻣﺘﻐﻴﺮ ﺑﺪﺳﺖ ﺁورد .
F x ′yz ′ + x ′y ′z 1 دوﮔﺎن ﺗﺎﺑﻊ F1ﺑﺮاﺑﺮ اﺳﺖ ﺑﺎ ﭘﺲ
1.
)( x ′ + y + z ′)( x ′ + y ′ + z
از ﻣﮑﻤﻞ ﮐﺮدن هﺮ ﻣﺘﻐﻴﺮ دارﯾﻢ ( x + y ′ + z)( x + y + z ′) = F ′ 1
F = x( y′z′ + yz ) . 2 دوﮔﺎن ﺗﺎﺑﻊ F2ﺑﺮاﺑﺮ اﺳﺖ ﺑﺎ ) x + ( y ′ + z ′ )( y + z
ﭘﺲ از ﻣﮑﻤﻞ ﮐﺮدن هﺮ ﻣﺘﻐﻴﺮ دارﯾﻢ x ′ + ( y + z )( y ′ + z ′) = F ′ 2
2.
٨
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ٢-۴ﺣﺎﻻت ﻣﺘﻌﺎرف و اﺳﺘﺎﻧﺪارد
ﯾﮏ ﻣﺘﻐﻴﺮ دودوﯾﯽ ﻣﻤﮑﻦ اﺳﺖ ﺑﻔﺮم ﻣﻌﻤﻮﻟﯽ ) ( xﯾﺎ ﻣﮑﻤﻠﺶ ) َ ( xﻇﺎهﺮ ﺷﻮد .ﺣﺎل ﻓﺮض ﮐﻨﻴﻢ ﮐﻪ ﻣﺘﻐﻴﺮهﺎﯼ دودوﯾﯽ xو yﺑﻮﺳﻴﻠﻪ ﻋﻤﻠﮕﺮ ANDﺑﺎ ﯾﮑﺪﯾﮕﺮ ﺗﺮﮐﻴﺐ ﺷﻮﻧﺪ . ﭼﻮن هﺮ ﻣﺘﻐﻴﺮ ﻣﻤﮑﻦ اﺳﺖ ﺑﻪ هﺮ ﯾﮏ از دو ﺷﮑﻞ ﻓﻮق ﻇﺎهﺮ ﮔﺮدد ﭼﻬﺎر ﺗﺮﮐﻴﺐ ﺑﺮاﯼ
ﺁن دو ﻣﺘﻐﻴﺮ وﺟﻮد دارﻧﺪ xy′, x′y , x′y′و `xy
.هﺮ ﯾﮏ از اﯾﻦ ﭼﻬﺎر ﺟﻤﻠﻪ ﻧﺸﺎن
دهﻨﺪﻩ ﯾﮏ ﻧﺎﺣﻴﻪ در دﯾﺎﮔﺮام ون ،ﺷﮑﻞ ) (٢-١ﺑﻮدﻩ و ﻣﻴﻨﺘﺮم ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮد .ﺑﺮوﺷﯽ ﻣﺸﺎﺑﻪ n ،ﻣﺘﻐﻴﻴﺮ ﻣﯽ ﺗﻮاﻧﺪ روﺷﯽ ﻣﺸﺎﺑﻪ ﯾﺎ ﺁﻧﭽﻪ در ﺟﺪول ) (٢-٣ﺑﺮاﯼ ﺳﻪ ﻣﺘﻐﻴﺮ ﺣﺎﺻﻞ ﺷﺪﻩ ﺑﺪﺳﺖ ﺁﯾﻨﺪ .اﻋﺪاد دودوﯾﯽ از ﺻﻔﺮ ﺗﺎ
2 n −1
ﺑﺮاﯼ nﻣﺘﻐﻴﺮ در زﯾﺮ ﺳﺘﻮن
ﻣﺘﻐﻴﺮ هﺎ در ﺟﺪول ﻧﻮﺷﺘﻪ ﻣﯽ ﺷﻮﻧﺪ .هﺮ ﻣﻴﻨﺘﺮم از اﺟﺰاﯼ ﻋﻤﻠﮕﺮ ANDروﯼ nﻣﺘﻐﻴﺮ ﺑﺪﺳﺖ ﻣﯽ ﺁﯾﺪ و هﺮ ﻣﺘﻐﻴﺮ در ﺁن ﺑﺎ ﻣﻘﺪار ٠ﺑﺎ ﻋﻼﻣﺖ ﭘﺮﯾﻢ و ﺑﺎ ﻣﻘﺪار ١ﺑﺪون ﭘﺮﯾﻢ ﺧﻮاهﺪ ﺑﻮد .ﺳﻤﺒﻞ ﻣﻴﻨﺘﺮم ﻧﻴﺰ درﺟﺪول ﺑﻔﺮم mjﺁوردﻩ ﺷﺪﻩ اﺳﺖ ﮐﻪ jﻣﻌﺎدل دهﺪهﯽ ﺟﻤﻠﻪ ﻣﺮﺑﻮﻃﻪ ﻣﯽ ﺑﺎﺷﺪ . ﺟﺪول ) (٢-٣ﻣﻴﻨﺘﺮم و ﻣﺎﮐﺴﺘﺮم هﺎ ﺑﺮاﯼ ﺳﻪ ﻣﺘﻐﻴﻴﺮ دودوﯾﯽ
ﻣﺎﮐﺴﺘﺮم ﺟﻤﻠﻪ ﻋﻼﻣﺖ M0
ﻣﻴﻨﺘﺮم ﺟﻤﻠﻪ ﻋﻼﻣﺖ m0 x′y ′z ′
M1
x+ y+ z x + y + z′
m1
M2
x + y′ + z
m2
x′y′z x′yz′
M3
x + y′ + z ′
m3
M4
x′ + y + z
m4
M5
x′ + y + z ′
m5
M6
x′ + y′ + z
m6
M7
x′ + y′ + z′
x′yz xy′z′ xy′z xyz′
m7
xyz
z 0
y 0
x 0
1
0
0
0
1
0
1
1
0
0
0
1
1
0
1
0
1
1
1
1
1
٩
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺑﻄﺮﯾﻖ ﻣﺸﺎﺑﻬﯽ nﻣﺘﻐﻴﺮ در ﯾﮏ ﺟﻤﻠﻪ ، ORﮐﻪ هﺮ ﯾﮏ ﻣﯽ ﺗﻮاﻧﻨﺪ ﺑﺎ ﭘﺮﯾﻢ و ﯾﺎ ﺑﺪون ﭘﺮﯾﻢ ﺑﺎﺷﻨﺪ 2n ،ﺗﺮﮐﻴﺐ ﻣﻤﮑﻦ را اﯾﺠﺎد ﻣﯽ ﻧﻤﺎﯾﻨﺪ ﮐﻪ هﺮ ﯾﮏ از ﺁﻧﻬﺎ ﻣﺎﮐﺴﺘﺮم ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮد .هﺸﺖ ﺟﻤﻠﻪ ﻣﺎﮐﺴﺘﺮم ﻣﺮﺑﻮط ﺑﻪ ﺳﻪ ﻣﺘﻐﻴﺮ ﺑﺎ ﺳﻤﺒﻞ ﺁﻧﻬﺎ درﺟﺪول )(٢-٣ ﻟﻴﺴﺖ ﺷﺪﻩ اﻧﺪ .هﺮ 2nﺟﻤﻠﻪ ﻣﺎﮐﺴﺘﺮم ﺑﺮاﯼ nﻣﺘﻐﻴﺮ ﻣﺸﺎﺑﻬﯽ ﺗﻌﻴﻴﻦ ﻣﯽ ﺷﻮﻧﺪ .هﺮ ﻣﺎﮐﺴﺘﺮم از ﯾﮏ ﺟﻤﻠﻪ ORﻣﺮﺑﻮط ﺑﻪ nﻣﺘﻐﻴﺮ داراﯼ ﻣﺘﻐﻴﺮ هﺎﯼ ﺑﺪون ﭘﺮﯾﻢ اﺳﺖ ﺑﺸﺮﻃﯽ ﮐﻪ ﺁن ﻣﺘﻐﻴﺮهﺎ ٠ﺑﺎﺷﻨﺪ وﻟﯽ هﺮ ﮔﺎﻩ ﻣﻘﺪار ﻣﺘﻐﻴﺮ ١ﺑﺎﺷﺪ در اﯾﻨﺼﻮرت ﺁن ﻣﺘﻐﻴﺮ ﭘﺮﯾﻢ دار ﻧﻤﺎﯾﺶ دادﻩ ﻣﯽ ﺷﻮد .ﺗﻮﺟﻪ داﺷﺘﻪ ﺑﺎﺷﻴﺪ ﮐﻪ هﺮ ﺟﻤﻠﻪ ﻣﺎﮐﺴﺘﺮم ﻣﮑﻤﻞ ﻣﻴﻨﺘﺮم ﻣﺮﺑﻮﻃﻪ اش ﻣﯽ ﺑﺎﺷﺪ و ﺑﺎﻟﻌﮑﺲ . ﯾﮏ ﺗﺎﺑﻊ ﺑﻮل ﻣﯽ ﺗﻮاﻧﺪ ﺑﺎ اﺳﺘﻔﺎدﻩ از ﺟﺪول درﺳﺘﯽ ﺑﻔﺮم ﺟﺒﺮﯼ ﺑﺎ در ﻧﻈﺮ ﮔﺮﻓﺘﻦ ﻣﻴﻨﺘﺮم هﺎﯾﯽ ﮐﻪ ﺗﺎﺑﻊ ﺑﻪ ازاﯼ ﺁﻧﻬﺎ ﺑﺮاﺑﺮ ١اﺳﺖ و اﺟﺮاﯼ ﻋﻤﻠﮕﺮ ORروﯼ ﺁﻧﻬﺎ ﺗﺸﮑﻴﻞ ﮔﺮدد . ﻣﺜﻼً ﺗﺎﺑﻊ F1در ﺟﺪول ) (٢-۴ﺑﺪﯾﻦ ﻃﺮﯾﻖ ﻣﻌﻴﻦ ﻣﯽ ﺷﻮد ﮐﻪ ٠٠١و ١٠٠و ١١١را ﺑﻔﺮم
xy′z , x′y′z
و xyzﻧﺸﺎن دادﻩ و ﺳﭙﺲ ﺑﺎ ﯾﮑﺪﯾﮕﺮ ﺗﺮﮐﻴﺐ ﮐﻨﻴﻢ .ﭼﻮن هﺮ ﯾﮏ از اﯾﻦ
ﻣﻴﻨﺘﺮم هﺎ ﺑﺮاﺑﺮ ١اﺳﺖ ﺑﺎﯾﺪ راﺑﻄﻪ زﯾﺮ را داﺷﺘﻪ ﺑﺎﺷﻴﻢ :
f = x′y′z + xy′z′ + xyz = m + m + m 1 1 4 7 ﺑﻄﻮر ﻣﺸﺎﺑﻪ ﺑﺴﺎدﮔﯽ ﻣﯽ ﺗﻮان ﻧﺸﺎن داد ﮐﻪ :
f = x′yz + xy′z + xyz = m + m + m + m 2 3 5 6 7 اﯾﻦ ﻣﺜﺎﻟﻬﺎ ﻧﺸﺎن دهﺪﻩ ﯾﮏ ﺧﺎﺻﻴﺖ ﻣﻬﻢ ﺟﺒﺮ ﺑﻮل ﻣﯽ ﺑﺎﺷﻨﺪ ﮐﻪ ﻋﺒﺎرﺗﺴﺖ از :هﺮ ﺗﺎﺑﻊ ﺑﻮل ﻣﯽ ﺗﻮاﻧﺪ ﺑﺼﻮرت ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎ ) در اﯾﻨﺠﺎ ﺑﻤﻌﻨﯽ ORاﺳﺖ ( ﺑﻴﺎن ﺷﻮد .ﺣﺎل ﻣﮑﻤﻞ ﯾﮏ ﺗﺎﺑﻊ ﺑﻮل را در ﻧﻈﺮ ﺑﮕﻴﺮد .اﯾﻦ ﻣﮑﻤﻞ را ﻣﯽ ﺗﻮان ﺑﺎ اﺳﺘﻔﺎدﻩ از ﺟﺪول وﺑﮑﺎرﮔﻴﺮﯼ ﺟﻤﻼت ﻣﻴﻨﺘﺮم ﮐﻪ در ﺟﺪول ﺑﺮاﯼ ﺗﺎﺑﻊ ٠هﺴﺘﻨﺪ و اﻋﻤﺎل ﻋﻤﻠﮕﺮد ORروﯼ ﺁﻧﻬﺎ ﺑﻮﺟﻮد ﺁورد .ﻟﺬا ﻣﮑﻤﻞ ﺗﺎﺑﻊ f1ﺑﺮاﺑﺮ ﺧﻮاهﺪ ﺑﻮد ﺑﺎ .
١٠
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
f ′ = x′y′z′ + x′yz′ + x′yz + xy′z + xyz′ 1 اﮔﺮ ﻣﺎ ﻣﮑﻤﻞ f1را ﭘﻴﺪا ﮐﻨﻴﻢ ﻧﺘﻴﺠﻪ هﻤﺎن ﺗﺎﺑﻊ f1ﺧﻮاهﺪ ﺷﺪ .
) f = ( x + y + z )( x + y ′ + z )( x + y ′ + z ′)( x′ + y + z ′)( x′ + y ′ + z 1 = M .M .M .M .M 0 2 3 5 6 ﺑﻄﻮر ﻣﺸﺎﺑﻪ ﻋﺒﺎرت ﻣﺮﺑﻮط ﺑﻪ f2را ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺟﺪول ﻣﯽ ﺗﻮان ﻧﻮﺷﺖ :
) f = ( x + y + z )( x + y + z′)( x + y′ + z )( x′ + y + z 2 = M .M .M .M 0 1 2 4 اﯾﻦ ﻣﺜﺎﻟﻬﺎ ﺑﻴﺎﻧﮑﺮ دوﻣﻴﻦ ﺧﺎﺻﻴﺖ ﻣﻬﻢ ﺟﺒﺮ ﺑﻮل ﻣﯽ ﺑﺎﺷﻨﺪ .ﯾﻌﻨﯽ هﺮ ﺗﺎﺑﻊ ﻣﯽ ﺗﻮاﻧﺪ ﺑﺼﻮرت ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ ) ﺣﺎﺻﻠﻀﺮب ﺑﻪ ﻣﻌﻨﯽ اﻋﻤﺎل ﻋﻤﻠﮕﺮد ANDﻣﯽ ﺑﺎﺷﺪ ( ﻧﻮﺷﺘﻪ ﺷﻮد .روش ﺑﺪﺳﺖ ﺁوردن ﻣﺴﺘﻘﻴﻢ ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ ﺑﺎ اﺳﺘﻔﺎدﻩ از ﺟﺪول رﺑﻄﺮﯾﻖ زﯾﺮ اﺳﺖ :اﺑﺘﺪا ﺟﻤﻼت ﻣﺎﺳﮑﺘﺮﻣﯽ ﮐﻪ از ﺗﺮﮐﻴﺐ ﻣﺘﻐﻴﺮهﺎ ﺗﺸﮑﻴﻞ ﺷﺪﻩ و ﺑﺮاﯼ ﺗﺎﺑﻊ ﺗﻮﻟﻴﺪ ٠ﻣﯽ ﻧﻤﺎﯾﺪ اﻧﺘﺨﺎب ﺷﺪﻩ و ﺳﭙﺲ ﺑﺎ اﺟﺮاﯼ ﻋﻤﻠﮕﺮ ANDروﯼ ﺗﻤﺎم ﺁﻧﻬﺎ ﻣﯽ ﺗﻮان ﺑﻪ ﻧﺘﻴﺠﻪ ﻣﻮرد ﻧﻈﺮ رﺳﻴﺪ .هﺮ ﮔﺎﻩ ﺗﻮاﺑﻊ ﺑﻮل ﺑﺼﻮرت ﻣﺠﻤﻮﻋﻤﻴﻨﺘﺮم هﺎ ﯾﺎ ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ در ﺁﯾﻨﺪ ﮔﻮﯾﻨﺪ ﺑﻪ ﺷﮑﻞ ﻣﺘﻌﺎرف ﻣﯽ ﺑﺎﺷﻨﺪ . ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎ ﻗﺒﻼً ﮔﻔﺘﻪ ﺷﺪﻩ ﮐﻪ ﺑﺮاﯼ nﻣﺘﻐﻴﺮ 2nﻣﻴﻨﺘﺮم ﻣﺴﺘﻘﻞ ﺑﺪﺳﺖ ﺁوردﻩ و هﺮ ﺗﺎﺑﻊ ﺑﻮل را ﻣﻴﺘﻮان ﺑﺼﻮرت ﻣﺤﻤﻮع ﺁﻧﻬﺎ ﺑﻴﺎن ﮐﺮد .ﺗﺎﺑﻊ ﺑﻮل از ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎﯾﯽ ﮐﻪ ﻣﻘﺪارﺷﺎن در ﺟﺪول درﺳﺘﯽ ﺑﺮاﺑﺮ ١اﺳﺖ ﺗﺸﮑﻴﻞ ﻣﯽ ﮔﺮدد .ﭼﻮن ﻣﻘﺪار هﺮ ﻣﻴﻨﺘﺮم ﻣﯽ ﺗﻮاﻧﺪ ١ﯾﺎ ٠ﺑﺎﺷﺪ و ﻧﻴﺰ . 2nﮔﺎهﯽ اوﻗﺎت ﺑﻬﺘﺮ اﺳﺖ ﮐﻪ ﺗﺎﺑﻊ را ﺑﺼﻮرت ﻣﺠﻤﻮع ﻣﻴﻨﺘﻢ هﺎ ﻧﺸﺎن داد .ﭼﻨﺎﻧﭽﻪ ﺗﺎﺑﻊ ﺑﻪ اﯾﻦ ﺷﮑﻞ ﻧﺒﺎﺷﺪ ﻣﯽ ﺗﻮان ﺁن را ﺑﺎ اﺟﺮاﯼ اﻋﻤﺎل زﯾﺮ ﺑﻔﺮم ﻣﻮرد ﻧﻈﺮ در ﺁورد .اﺑﺘﺪا ﻣﺠﻤﻮﻋﻪ ﺟﻤﻼت ANDﺷﺪﻩ را ﺑﺪﺳﺖ ﻣﯽ ﺁورﯾﻢ و ﺳﭙﺲ ﺟﻤﻼت را از
١١
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﻧﻈﺮ وﺟﻮد ﮐﻠﻴﻪ ﻣﺘﻐﻴﺮ هﺎ ﻣﻮرد ﺑﺎزرﺳﯽ ﻗﺮار ﻣﯽ دهﻴﻢ .در ﺻﻮرت ﻋﺪم وﺟﻮد ﺑﺮﺧﯽ ﻣﺘﻐﻴﺮهﺎ ،ﺑﺎﯾﺪ ﺁﻧﻬﺎ رادر ﻋﺒﺎراﺗﯽ ﻣﺎﻧﻨﺪ َ x+xو ﻏﻴﺮﻩ ANDﮐﺮد .ﮐﻪ xﯾﮑﯽ از ﻣﺘﻐﻴﺮهﺎﯾﯽ اﺳﺖ ﮐﻪ در ﺟﻤﻠﻪ وﺟﻮد ﻧﺪارد .ﻣﺜﺎل زﯾﺮ ﻣﻄﻠﺐ را روﺷﻦ ﻣﻴﮑﻨﺪ : ﻣﺜﺎل : -٢-۴ﺗﺎﺑﻊ
F = A + B′C
را ﺑﺼﻮرت ﻣﺠﻮع ﻣﻴﻨﺘﺮم ﻧﺸﺎن دهﻴﺪ .
ﺗﺎﺑﻊ داراﯼ ﺳﻪ ﻣﺘﻐﻴﺮ A,B,Cﻣﯽ ﺑﺎﺷﺪ .در اوﻟﻴﻦ ﺟﻤﻠﻪ دو ﻣﺘﻐﻴﺮ وﺟﻮد ﻧﺪارد ،ﺑﻨﺎﺑﺮاﯾﻦ
A = A(B + B′) + AB + AB هﻨﻮز هﻢ ﯾﮏ ﻣﺘﻐﻴﺮ ﮐﺴﺮ اﺳﺖ .
)A = AB(C + C ′) + AB′(C + C ′ = ABC + ABC ′+ AB′C + AB′C ′ ﺟﻤﻠﻪ دوم
B′C
ﯾﮏ ﻣﺘﻐﻴﺮ ﮐﺴﺮ دارد .
B′C = B′C ( A + A′) = AB′C + A′B′C ′ از ﺗﺮﮐﻴﺐ ﻧﺘﺎﯾﺞ ﻓﻮق دارﯾﻢ
F = A + B′C = ABC + ABC ′+ AB′C + AB′C ′ + AB′C + A′B′C از ﻃﺮﻓﯽ
AB′Cدوﺑﺎرﻩ ﺗﮑﺮار ﺷﺪﻩ اﺳﺖ و ﺑﺮ ﻃﺒﻖ ﺗﺌﻮرﯼ ( x = x + x) ، ١
ﻣﯽ ﺗﻮان
ﯾﮑﯽ از ﺁﻧﻬﺎ را ﺣﺬف ﮐﺮد .ﺑﺎ ﻣﺮﺗﺐ ﻧﻤﻮدن ﻣﻴﻨﺘﺮم هﺎ ﺑﺘﺮﺗﻴﺐ ﺻﻌﻮدﯼ ﭼﻨﻴﻦ ﻧﺘﻴﺠﻪ ﻣﯽ ﺷﻮد .
F = A′B′C + AB′C ′ + AB′C + ABC =m + m + m + m + m 5 7 1 4 6 هﻨﮕﺎﻣﯽ ﮐﻪ ﺗﺎﺑﻊ ﺑﻮل ﺑﻔﺮم ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎ اﺳﺖ ﻣﻨﺎﺳﺐ ﺗﺮ اﺳﺖ ﺗﺎ ﺁن ﺑﻔﺮم ﺧﻼﺻﻪ زﯾﺮ ﻧﺸﺎن دهﻴﻢ .
١٢
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
) F ( A, B, C) = ∑ (1,4,5,6,7 ﺳﻤﺒﻞ ∑ ﺑﻪ ﻣﻌﻨﯽ اﺟﺮاﯼ ﻋﻤﻠﮕﺮ ORروﯼ ﺟﻤﻼت اﺳﺖ .ﺣﺮوﻓﯽ ﮐﻪ در داﺧﻞ ﭘﺮاﻧﺘﺰ ﻗﺮار دارﻧﺪ ﻟﻴﺴﺖ ﻣﺘﻐﻴﺮهﺎﯼ ﺑﮑﺎر رﻓﺘﻪ را ﺑﻬﻨﮕﺎم ﺗﺸﮑﻴﻞ ﺟﻤﻼت ﻣﻴﻨﺘﺮم و ﺟﻤﻊ ﺁﻧﻬﺎ ﻣﻌﻴﻦ ﻣﯽ ﮐﻨﻨﺪ .روش دﯾﮕﺮﯼ ﺑﺮاﯼ ﺗﺸﮑﻴﻞ ﻣﻴﻨﺘﺮم هﺎﯼ ﺗﺎﺑﻊ ﺑﻮل ﺗﻬﻴﻪ ﺟﺪول درﺳﺘﯽ ﺗﺎﺑﻊ ﻣﺴﺘﻘﻴﻤﺎً از ﻋﺒﺎرت ﺟﺒﺮﯼ اﺳﺖ ﮐﻪ از روﯼ ﺁن ﻣﻴﻨﺘﺮم هﺎ ﺧﻮاﻧﺪﻩ ﻣﯽ ﺷﻮﻧﺪ .ﺗﺎﺑﻊ ﺑﻮل ﻣﺜﺎل ٢-۴را در ﻧﻈﺮ ﺑﮕﻴﺮد :
F = A + B′C ﺟﺪول درﺳﺘﯽ ﺷﮑﺐ ) (٢-۵ﻣﺴﺘﻘﻴﻤﺎً از ﻋﺒﺎرت ﺟﺒﺮﯼ ﺑﺎ هﺸﺖ ﺗﺮﮐﻴﺐ دودوﯾﯽ ﻣﺘﻐﻴﺮ هﺎﯼ A , B , Cﺣﺎﺻﻞ ﻣﯽ
ﺷﻮد ﮐﻪ ﺑﺮاﯼ ﻣﻴﻨﺘﺮم هﺎﯾﯽ ﮐﻪ در ﺁﻧﻬﺎ BC = 01 , A =1
ﺑﺎﺷﺪ ١ﻗﺮار ﻣﯽ دهﻴﻢ .ﺳﭙﺲ ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺣﺠﺪول درﺳﺘﯽ ﭘﻨﺞ ﻣﻴﻨﺘﺮم ﺗﺎﺑﻌﯽ را ﮐﻪ ١،۴،۵،۶،٧ﻣﯽ ﺑﺎﺷﻨﺪ ﻣﯽ ﺧﻮاﻧﻴﻢ.
ﺿﺮب ﻣﺎﮐﺴﺘﺮم هﺎ
n هﺮ ﯾﮏ از 22ﺗﺎﺑﻊ ﻣﺘﺸﮑﻞ از nﻣﺘﻐﻴﺮ را هﻤﭽﻨﻴﻦ ﻣﯽ ﺗﻮان ﺑﺼﻮرت ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ ﺑﻴﺎن داﺷﺖ .ﺑﺮاﯼ ﭼﻨﻴﻦ ﻓﺮﻣﯽ ﺑﺎﯾﺪ اول ﺟﻤﻠﻪ هﺎﯼ ORرا ﺗﺸﮑﻴﻞ داد .
اﯾﻦ ﻋﻤﻞ را ﻣﯽ ﺗﻮان ﺑﺎ اﺳﺘﻔﺎدﻩ از ﻗﺎﻧﻮن ﺗﻮزﯾﻊ ÷ذﯾﺮﯼ )x + yz = ( x + y)( x + z
ﻧﻴﺰ
اﻧﺠﺎم داد .ﺳﭙﺲ هﺮ ﻣﺘﻐﻴﺮ ﻏﺎﯾﺐ در هﺮ ﺟﻤﻠﻪ ORﺑﺎ OR ، xxﻣﯽ ﺷﻮد .اﯾﻦ روش ﺑﺎ ﻣﺜﺎل زﯾﺮ واﺿﺤﺘﺮ ﺧﻮاهﺪ ﺷﺪ :
١٣
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ﺟﺪول ) (٢-۵ﺟﺪول درﺳﺘﯽ ﺑﺮاﯼ F ٠ ١ ٠ ٠ ١ ١ ١ ١
C ٠ ١ ٠ ١ ٠ ١ ٠ ١
B ٠ ٠ ١ ١ ٠ ٠ ١ ١
F = A + B′C A ٠ ٠ ٠ ٠ ١ ١ ١ ١
ﻣﺜﺎل : ٢-۵ﺗﺎﺑﻊ F = xy + x′zرا ﺑﺼﻮرت ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم ﺑﻨﻮﯾﺴﻴﺪ : اﺑﺘﺪا ﺑﺎ اﺳﺘﻔﺎدﻩ از ﻗﺎﻧﻮن ﺗﻮزﯾﻊ ﭘﺬﯾﺮﯼ ﺗﺎﺑﻊ را ﺑﻪ ﺻﻮرت ﺟﻤﻼ ORدر ﻣﯽ ﺁورﯾﻢ :
) F = xy + x′z = ( xy + x′)( xy + z ) = ( x + x′)( y + x′)( x + z )( y + z ) = ( x′ + y)( x + z )( y + z ﺗﺎﺑﻊ داراﯼ ﺳﻪ ﻣﺘﻐﻴﺮ z,y,xاﺳﺖ .هﺮ ﺟﻤﻠﻪ ORﻓﺎﻗﺪ ﯾﮏ ﻣﺘﻐﻴﺮ اﺳﺖ .ﺑﻨﺎﺑﺮاﯾﻦ .
)x′ + y = x′ + y + zz′ = ( x′ + y + z )( x′ + y + z′ ) x + z = x + z + yy′ = ( x + y + z )( x6 y′ + z ) y + z = − y + z + xx′ = ( x + y + z )( x′ + y + z ﺑﺎ ﺗﺮﮐﻴﺐ ﻋﺒﺎرت ﻓﻮق و ﺣﺬف ﺁﻧﻬﺎﯾﯽ ﮐﻪ ﺑﻴﺶ از ﯾﮑﺒﺎر ﺗﮑﺮار ﺷﺪﻩ اﻧﺪ ﺧﻮاهﻴﻢ داﺷﺖ :
)F = ( x + y + z )( x + y′ + z )( x′ + y + z )( x′ + y + z′ =M M M M 0 2 4 5 روش ﻣﻨﺎﺳﺐ ﺗﺮﯼ ﺑﺮاﯼ ﻧﻤﺎﯾﺶ ﺗﺎﺑﻊ ﺑﻘﺮار زﯾﺮ اﺳﺖ :
)F ( x, y, z) = ∏(0,2,4,5
١٤
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ﺳﻤﺒﻞ ﺿﺮب ،
∏
ﺑﻴﺎﻧﮕﺮ ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ ﻣﯽ ﺑﺎﺷﺪ و اﻋﺪاد ،ﺷﻤﺎرﻩ ﺟﻤﻼت
ﻣﺎﮐﺴﺘﺮم را ﻣﺸﺨﺺ ﻣﯽ ﺳﺎزد . ﺗﺒﺪﯾﻞ ﻓﺮﻣﻬﺎﯼ ﻣﺘﻌﺎرف ﺑﻪ ﯾﮑﺪﯾﮕﺮ ﻣﮑﻤﻞ ﯾﮏ ﺗﺎﺑﻊ ﮐﻪ ﺑﺼﻮرت ﻣﺠﻤﻮع ﻣﻨﻴﺘﺮم هﺎ ﻧﺸﺎن دادﻩ ﺷﺪﻩ ﺑﺮاﺑﺮ اﺳﺖ ﺑﺎ ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎﯾﯽ ﮐﻪ در ﻓﺮم اﺻﻠﯽ ﺗﺎﺑﻊ وﺟﻮد ﻧﺪارد .زﯾﺮا ﺗﺎﺑﻊ اﺻﻠﯽ از ﺟﻤﻼت ﻣﻴﻨﺘﺮﻣﯽ ﺗﺸﮑﻴﻞ ﺷﺪﻩ ﮐﻪ ﺗﺎﺑﻊ را ﺑﺮاﺑﺮ ١ﻣﯽ ﻧﻤﺎﯾﺪ ،در ﺣﺎﻟﻴﮑﻪ ﻣﮑﻤﻞ ﺁن ﺗﺎﺑﻊ ﺑﻪ ازاﯼ ﺟﻤﻼﺗﯽ ﺑﺮاﺑﺮ ١اﺳﺖ ﮐﻪ ﺗﺎﺑﻊ اﺻﻠﯽ ﺑﻪ ازاﯼ ﺁﻧﻬﺎ ٠ﻣﯽ ﺑﺎﺷﺪ .ﺑﻌﻨﻮان ﻣﺜﺎل ﺗﺎﺑﻊ زﯾﺮ را در ﻧﻈﺮ ﺑﮕﻴﺮﯾﺪ :
)F = ( A, B, C ) = ∑ (1,4,5,6,7 ﻣﮑﻞ اﯾﻦ ﺗﺎﺑﻊ ﺑﻪ ﺷﮑﻞ زﯾﺮ اﺳﺖ :
F ′( A, B, C ) = ∑ (0,2,3) = m + m + m 0 2 3 ﺣﺎل ،اﮔﺮ ﻣﮑﻤﻞ ` Fرا ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺗﺌﻮرﯼ دﻣﻮرﮔﺎن ﺑﺪﺳﺖ ﺁورﯾﻢ ﻓﺮم ﺟﺪﯾﺪﯼ ﺑﺮاﯼ F ﺑﺪﺳﺖ ﻣﯽ ﺁﯾﺪ.
) F = m + m + m ) = m .m .m = M M M = ∏ ( 0 , 2 , 3 0 2 3 0 2 3 0 2 3 ﺁﺧﺮﯾﻦ ﺗﺒﺪﯾﻞ در راﺑﻄﻪ ﻓﻮق ﻧﺘﻴﺠﻪ ﺗﻌﺎرﯾﻒ ﺟﺪول ) (٢-٣ﻣﯽ ﺑﺎﺷﺪ .ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺟﺪول درﺳﺘﯽ راﺑﻄﻪ زﯾﺮ ﻣﺴﻠﻢ اﺳﺖ .
m′j = M j ﯾﻌﻨﯽ ،ﺟﻤﻠﻪ ﻣﺎﮐﺴﺘﺮم ﺑﺎ اﻧﺪﯾﺲ jﻣﮑﻤﻞ ﺟﻤﻠﻪ ﻣﻴﻨﺘﺮم ﺑﺎ هﻤﺎن اﻧﺪﯾﺲ اﺳﺖ و ﺑﺎﻟﻌﮑﺲ .
١٥
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺁﺧﺮﯾﻦ ﻣﺜﺎل ،ﺗﺒﺪﯾﻞ ﯾﮏ ﺗﺎﺑﻊ ﺑﺼﻮرت ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎ ﺑﻴﺎن ﺷﺪﻩ ﺑﻪ ﻣﻌﺎدل ﺁن ﮐﻪ ﺑﺼﻮرت ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ اﺳﺖ را ﺑﻴﺎن ﻣﯽ دارد .ﺑﺤﺚ ﻣﺸﺎﺑﻬﯽ ﻧﺸﺎن ﻣﯽ دهﺪ ﮐﻪ ﺗﺒﺪﯾﻞ ﺣﺎﺻﻠﻀﺮب ﻣﺎﮐﺴﺘﺮم هﺎ ﺑﻪ ﻣﺠﻤﻮع ﻣﻴﻨﺘﺮم هﺎ ﺑﻄﺮﯾﻖ ﻓﻮق اﺳﺖ .ﺣﺎل ﯾﮏ روش ﮐﻠﯽ را ﺑﺮاﯼ ﺗﺒﺪﯾﻞ ﺑﻴﺎن ﻣﯽ ﮐﻨﻴﻢ : ﺑﺮاﯼ ﺗﺒﺪﯾﻞ ﯾﮏ ﻓﺮم ﻣﺘﻌﺎرف ﺑﻪ دﯾﮕﺮﯼ ﺳﻤﺒﻞ هﺎﯼ ∑ ∏ ,را ﺑﺎ ﯾﮑﺪﯾﮕﺮ ﻋﻮض ﻧﻤﻮدﻩ و ﺟﻤﻼﺗﯽ ﮐﻪ در ﺗﺎﺑﻊ اﺻﻠﯽ وﺟﻮد ﻧﺪارد را ﻧﻴﺰ ﻟﻴﺴﺖ ﻣﯽ ﻧﻤﺎﯾﻴﻢ .ﺑﺮاﯼ ﯾﺎﻓﺘﻦ ﺟﻤﻼت ﮔﻢ ﺷﺪﻩ ﺑﺎﯾﺪ ﺑﻴﺎد ﺑﻴﺎورﯾﻢ ﮐﻪ ﺗﻌﺪاد ﮐﻞ ﺟﻤﻼت 2nاﺳﺖ ﮐﻪ در ﺁن nﺗﻌﺪاد ﻣﺘﻐﻴﺮهﺎ در ﺗﺎﺑﻊ اﺳﺖ . ﯾﮏ ﺗﺎﺑﻊ ﺑﻮل ﺑﻔﺮم ﻋﺒﺎرت ﺟﺒﺮﯼ ﺑﻮﺳﻴﻠﻪ ﺟﺪول درﺳﺘﯽ و روش ﺗﺒﺪﯾﻞ ﻣﺘﻌﺎرف ﻗﺎﺑﻞ ﺗﺒﺪﯾﻞ ﺑﻪ ﺿﺮب ﻣﺎﮐﺴﺘﺮم هﺎ اﺳﺖ .ﻣﺜﻼً ﻋﺒﺎرت ﺑﻮل زﯾﺮ را در ﻧﻈﺮ ﺑﮕﻴﺮﯾﺪ : F = xy + x ′ z
اﺑﺘﺪا ﺟﺪول درﺳﺘﯽ را ﺑﺪﺳﺖ ﻣﯽ ﺁورﯾﻢ ،ﺷﮑﻞ ) ١ . (٢-۶هﺎﯼ زﯾﺮ ﺳﺘﻮن Fاز ﺗﺮﮐﻴﺐ ﻣﺘﻐﻴﺮهﺎ ﺑﺎ x=11و xz=01ﺣﺎﺻﻞ ﻣﯽ ﺷﻮد ﻣﻴﻨﺘﺮم هﺎﯼ ﺗﺎﺑﻊ از روﯼ ﺟﺪول درﺳﺘﯽ ﻋﺒﺎرﺗﻨﺪ از . ١،٣،۶،٧ﺗﺎﺑﻊ ﺑﺮ ﺣﺴﺐ ﻣﻴﻨﺘﺮم هﺎ ﺑﺮاﺑﺮﺳﺖ ﺑﺎ
)F ( x, y, z) = ∑ (1,3,6,7 ﭼﻮن ﺟﻤﻌﺎً هﺸﺖ ﻣﻴﻨﺘﺮم ﯾﺎ ﻣﺎﮐﺴﺘﺮم در ﯾﮏ ﺗﺎﺑﻊ ﺳﻪ ﻣﺘﻐﻴﺮﻩ وﺟﻮد دارد ،ﻣﺎ ﺟﻤﻼت ﻏﻴﺮ ﻣﻮﺟﻮد در ﻓﻮق را ﻣﯽ ﯾﺎﺑﻴﻢ ﮐﻪ ﻋﺒﺎرﺗﻨﺪ از ۴ ، ٢ ، ٠و . ۵ﺗﺎﺑﻊ ﺑﺮ ﺣﺴﺐ ﺿﺮب ﻣﺎﮐﺴﺘﺮم هﺎ ﭼﻨﻴﻦ ﺧﻮاهﺪ ﺷﺪ .
)F ( x, y, z) = ∏(0,2,4,5 اﯾﻦ هﻤﺎن ﻣﺜﺎﻟﯽ اﺳﺖ ﮐﻪ در ﻣﺜﺎل ٢-۵دﯾﺪﯾﻢ .
١٦
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ﺟﺪول ) (٢-۶ﺟﺪول درﺳﺘﯽ ﺑﺮاﯼ
ﻓﺮم هﺎﯼ اﺳﺘﺎﻧﺪارد
f 0 1 ٠ ١ ٠ ٠ ١ ١
z 0 1 ٠ ١ ٠ ١ ٠ ١
y 0 0 ١ ١ ٠ ٠ ١ ١
F = xy + x′z x 0 0 ٠ ٠ ١ ١ ١ ١
دو ﻓﺮم ﻣﺘﻌﺎرف ﺟﺒﺮ ﺑﻮل ،ﻓﺮم هﺎﯾﯽ اﺑﺘﺪاﯾﯽ هﺴﺘﻨﺪ ﮐﻪ هﺮ ﮐﺲ ﻣﯽ ﺗﻮاﻧﺪ ﺑﺎ ﺗﻮﺟﻪ ﺑﻪ ﺟﺪول درﺳﺘﯽ ﺑﻪ ﺁﻧﻬﺎ دﺳﺘﺮﺳﯽ ﭘﻴﺪا ﮐﻨﺪ .اﯾﻦ ﻓﺮم هﺎ ﻣﻌﻤﻮﻻً داراﯼ ﺣﺪاﻗﻞ ﻣﺘﻐﻴﺮهﺎ ﻧﻴﺴﺘﻨﺪ ،زﯾﺮا هﺮ ﻣﻴﻨﺘﺮم ﯾﺎ ﻣﺎﮐﺴﺘﺮم ﺑﺎﯾﺴﺘﯽ ﺑﻨﺎ ﺑﻪ ﺗﻌﺮﯾﻒ داراﯼ ﺗﻤﺎم ﻣﺘﻐﻴﺮهﺎ اﻋﻢ از ﻣﮑﻤﻞ و ﻏﻴﺮ ﻣﮑﻤﻞ ﺑﺎﺷﻨﺪ .راﻩ دﯾﮕﺮﯼ ﺑﺮاﯼ ﺑﻴﺎن ﺗﺎﺑﻊ ﺑﻮل ،ﻓﺮم اﺳﺘﺎﻧﺪارد اﺳﺖ .در اﯾﻦ ﻓﺮم ،ﺟﻤﻠﻪ هﺎﯾﯽ ﮐﻪ ﺗﺎﺑﻊ را ﺗﺸﮑﻴﻞ ﻣﯽ دهﻨﺪ ﻣﻤﮑﻦ اﺳﺖ ﯾﮏ ﻳﺎ دو ﯾﺎ هﺮ ﺗﻌﺪادﯼ از ﻣﺘﻐﻴﺮهﺎ را داراﺑﺎﺷﻨﺪ .دو ﻧﻮع ﻓﺮم اﺳﺘﺎﻧﺪارد وﺟﻮد دارد .ﯾﮑﯽ ﺟﻤﻊ ﺣﺎﺻﻠﻀﺮب هﺎ و دﯾﮕﺮﯼ ﺿﺮب ﺣﺎﺻﻞ ﺟﻤﻊ هﺎ . ﺟﻤﻊ ﺣﺎﺻﻠﻀﺮب هﺎ ،ﯾﮏ ﻋﺒﺎرت ﺑﻮل اﺳﺖ ﮐﻪ ﺷﺎﻣﻞ ﺟﻤﻼت ) ANDﺑﺎ ﻧﺎم ﺟﻤﻼت ﺣﺎﺻﻠﻀﺮب (از ﯾﮏ ﯾﺎ ﭼﻨﺪﻣﺘﻐﻴﺮ ﻣﯽ ﺑﺎﺷﺪ .ﮐﻠﻤﻪ ﺟﻤﻊ دراﯾﻨﺠﺎ ﺑﻪ ﻣﻌﻨﯽ ﻋﻤﻠﮕﺮ ORروﯼ اﯾﻦ ﺟﻤﻼت اﺳﺖ . ﻣﺜﺎﻟﯽ از اﯾﻦ ﻧﻮع ﺑﻘﺮار زﯾﺮ ﻣﯽ ﺑﺎﺷﺪ :
F = y′ + xy + x′yz′ 1 ﻋﺒﺎرت داراﯼ ﺳﻪ ﺟﻤﻠﻪ ﺣﺎﺻﻠﻀﺮب از ﯾﮏ ،دو و ﺳﻪ ﻣﺘﻐﻴﺮ اﺳﺖ .ﺟﻤﻊ ﺁﻧﻬﺎ در واﻗﻊ اﺟﺮاﯼ ﻋﻤﻞ ORاﺳﺖ ﮐﻪ ﺟﻤﻊ ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮﻧﺪ .هﺮ ﺟﻤﻠﻪ هﺮ ﺗﻌﺪاد ﻣﺘﻐﻴﺮ را ﻣﻤﮑﻦ
١٧
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
اﺳﺖ دارا ﺑﺎﺷﺪ .ﺿﺮب ﺑﻴﺎﻧﮕﺮ ﻋﻤﻠﮕﺮ ANDروﯼ ﺁﻧﻬﺎ اﺳﺖ .ﻣﺜﺎﻟﯽ از ﯾﮏ ﺗﺎﺑﻊ ﮐﻪ ﺑﺼﻮرت ﺿﺮب ﺣﺎﺻﻞ ﺟﻤﻊ هﺎ ﺑﻴﺎن ﺷﺪﻩ ﻋﺒﺎرﺗﺴﺖ از :
)F = x( y′ + z)( x′ + y + z′ + w 2 اﯾﻦ ﻋﺒﺎرت ﺑﻪ ﺗﺮﺗﻴﺐ داراﯼ ﺳﻪ ﺟﻤﻠﻪ ،ﺑﺎ ﯾﮏ ،دو ﭼﻬﺎر ﻣﺘﻐﻴﺮ اﺳﺖ .ﺿﺮب ﺁﻧﻬﺎ در واﻗﻊ اﺟﺮاﯼ ﻋﻤﻞ ANDﻣﯽ ﺑﺎﺷﺪ .ﮐﺎرﺑﺮد ﮐﻠﻤﻪ ﺿﺮب و ﺟﻤﻊ ﺑﻴﺎﻧﮕﺮ ﺷﺒﺎهﺖ ANDﺑﺎ ﺿﺮب و ﻋﻤﻠﮕﺮ ORﺑﺎ ﺟﻤﻊ در ﺣﺴﺎب ﻣﯽ ﺑﺎﺷﺪ . ﯾﮏ ﺗﺎﺑﻊ ﺑﻮل ﻣﻤﮑﻦ اﺳﺖ ﺑﻔﺮم ﻏﻴﺮ اﺳﺘﺎﻧﺪارد ﻧﻴﺰ ﺑﻴﺎن ﺷﻮد .ﺑﻌﻨﻮان ﻣﺜﺎل ﺗﺎﺑﻊ :
)F = ( AB + CD)( A′B′ + C ′D′ 3 ﻧﻪ ﺑﺸﮑﻞ ﺟﻤﻊ ﺣﺎﺻﻠﻀﺮب هﺎ و ﻧﻪ ﺑﺸﮑﻞ ﺿﺮب ﺣﺎﺻﻞ ﺟﻤﻊ هﺎ اﺳﺖ .اﻟﺒﺘﻪ ﻣﯽ ﺗﻮان ﺑﺎ اﺳﺘﻔﺎدﻩ از ﻗﺎﻧﻮن ﺗﻮزﯾﻊ ﭘﺬﯾﺮﯼ ﺁن را ﺑﻔﺮم اﺳﺘﺎﻧﺪارد در ﺁورد :
F = A′B′CD + ABC ′D′ 3 ٢-۵ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ دﯾﺠﻴﺘﺎل ﻣﺪارهﺎﯼ دﯾﺠﻴﺘﺎل اﻟﮑﺘﺮوﻧﻴﮑﯽ ،ﻣﺪارهﺎﯼ ﻣﻨﻄﻘﯽ ﻧﻴﺰ ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮﻧﺪ .زﯾﺮا اﯾﻨﮕﻮﻧﻪ ﻣﺪارهﺎﯼ در ﻣﻘﺎﺑﻞ ورودﯼ ﻣﻨﺎﺳﺒﯽ ،ﺗﻮﻟﻴﺪ ﮐﻨﻨﺪﻩ ﯾﮏ ﺳﺮﯼ اﻋﻤﺎل ﻣﻨﻄﻘﯽ ﻣﯽ ﺑﺎﺷﻨﺪ .هﺮ ﮔﻮﻧﻪ اﻃﻼﻋﺎت ﻣﺤﺎﺳﺒﺎﺗﯽ ﯾﺎ ﮐﻨﺘﺮﻟﯽ ﻣﻮرد ﻧﻈﺮ را ﻣﯽ ﺗﻮان ﺑﺎ ﻋﺒﻮر ﺳﻴﮕﻨﺎل هﺎﯼ دودوﯾﯽ از ﻣﻴﺎن دﺳﺘﻪ هﺎﯼ ﻣﺘﻔﺎوت ﻣﺪارهﺎﯼ ﻣﻨﻄﻘﯽ ﻣﻮرد اﺳﺘﻔﺎدﻩ ﻗﺮار داد ، ﮐﻪ هﺮ ﺳﻴﮕﻨﺎل ﻧﺸﺎن دهﻨﺪﻩ ﯾﮏ ﻣﺘﻐﻴﺮ ﺑﻮدﻩ و ﯾﮏ ﺑﻴﺖ از اﻃﻼﻋﺎت راﺣﻤﻞ ﻣﯽ ﮐﻨﺪ . ﻣﺪارهﺎﯼ ﻣﻨﻄﻘﯽ ﮐﻪ اﻋﻤﺎل ﻣﻨﻄﻘﯽ ANDو ORو NOTرا اﺟﺮا ﻣﯽ ﮐﻨﺪ ﺑﻪ هﻤﺮاﻩ ﺳﻤﺒﻞ هﺎﯼ ﻣﺮﺑﻮﻃﻪ در ﺷﮑﻞ ) (٢-١ﻧﺸﺎن دادﻩ ﺷﺪﻩ اﻧﺪ .اﯾﻦ ﻣﺪارهﺎ ﮐﻪ ﮔﻴﺖ ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮﻧﺪ ﺑﻠﻮﮐﻬﺎﯼ ﺳﺨﺖ اﻓﺰارﯼ هﺴﺘﻨﺪ ﮐﻪ ﺑﺎ ورودﯼ ﻣﻨﻄﻘﯽ ﻣﻨﺎﺳﺒﯽ در ﺧﺮوﺟﯽ
١٨
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺧﻮد ٠ﯾﺎ ١ﻣﻨﻄﻘﯽ ﺗﻮﻟﻴﺪ ﻣﯽ ﮐﻨﻨﺪ .ﺗﻮﺟﻪ ﮐﻨﻴﺪ ﮐﻪ ﭼﻬﺎر ﻧﺎم ﻣﺨﺘﻠﻒ ﺑﺮاﯼ اﯾﻦ ﻣﺪارهﺎ ﺑﮑﺎر رﻓﺘﻪ اﺳﺖ .ﻣﺪارهﺎﯼ دﯾﺠﻴﺘﺎل ،ﻣﺪارهﺎﯼ ﺳﻮﺋﻴﭽﻴﻨﮓ ،ﻣﺪارهﺎﯼ ﻣﻨﻄﻘﯽ و ﮔﻴﺖ هﺎ .هﻤﻪ اﯾﻦ اﺳﺎس ﺑﻄﻮر ﮔﺴﺘﺮدﻩ اﯼ اﺳﺘﻔﺎدﻩ ﻣﻴﺸﻮﻧﺪ وﻟﯽ ﺑﻬﺘﺮ اﺳﺖ ﻣﺎ اﯾﻦ ﻣﺪارهﺎﯼ را ANDو ORو NOTﮔﺎهﯽ ﻣﺪار واروﻧﮕﺮ ﯾﺎ ﻣﻌﮑﻮس ﮐﻨﻨﺪﻩ ﻧﻴﺰ ﻧﺎﻣﻴﺪﻩ ﻣﯽ ﺷﻮد زﯾﺮا ﺳﻴﮕﻨﺎل دودوﯾﯽ را ﻣﻌﮑﻮس ﻣﯽ ﮐﻨﺪ .
x
Z=x+y
Z=x.y
y
)اﻟﻒ( ﮔﻴﺖ ANDدو ورودﯼ
)ب( ﮔﻴﺖ ORدو ورودﯼ
َx
x y
x
A
F=ABC
B
C
)پ( ﮔﻴﺖ NOTﺑﺮاﯼ ﻣﻌﮑﻮس ﮐﺮدن ) واروﮔﺮ (
)ت( ﮔﻴﺖ ANDﺳﻪ ورودﯼ
G=A+B+C+D )ث( ﮔﻴﺖ ORﭼﻬﺎر ورودﯼ
A B
C
D
ﺷﮑﻞ ) :(٢-١ﮔﻴﺘﻬﺎﯼ NOR ،NANDو NOT
ﺳﻴﮕﻨﺎل هﺎﯼ ورودﯼ Xو Yدر ﮔﻴﺖ هﺎﯾﯽ ﺑﺎ دو ورودﯼ ،ﻃﺒﻖ ﺷﮑﻞ ) (٢-٢ﻣُﯽ ﺗﻮاﻧﻨﺪ ﺑﻪ ﯾﮑﯽ از ﭼﻬﺎر ﺣﺎﻟﺖ ﻣﻤﮑﻦ ١١ ، ١٠ ، ٠١ ، ٠٠ﺑﺎﺷﻨﺪ .اﯾﻦ ﺳﻴﮕﻨﺎل هﺎﯼ ورودﯼ ﺑﻪ هﻤﺮاﻩ ﺳﻴﮕﻨﺎل هﺎﯼ ﺧﺮوﺟﯽ ﺷﺎن ﺑﺮاﯼ ﮔﻴﺖ هﺎﯼ ANDو ORدر ﺷﮑﻞ ) (٢-٢ﻧﺸﺎن دادﻩ ﺷﺪﻩ اﻧﺪ .ﻧﻤﻮدار زﻣﺎﻧﯽ ﺷﮑﻞ ) (٢-٢ﭘﺎﺳﺦ هﺮ ﻣﺪار را ﺑﻪ هﺮ ﯾﮏ از ﭼﻬﺎر ﺗﺮﮐﻴﺐ ﻣﻤﮑﻦ ورودﯼ ﻧﺸﺎن ﻣﯽ دهﺪ .دﻟﻴﻞ اﻧﺘﺨﺎب ﻧﺎم واروﻧﮕﺮ ﺑﺮاﯼ ﮔﻴﺖ NOTاز ﻣﻘﺎﯾﺴﻪ ﭘﺎﻟﺲ ) Xورودﯼ واروﻧﮕﺮ ( و ) Xﺧﺮوﺟﯽ واروﻧﮕﺮ ( ﺑﺨﻮﺑﯽ ﺁﺷﮑﺎر ﻣﯽ ﺷﻮد .
١٩
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﮔﻴﺖ هﺎﯼ ANDو ORﻣﻤﮑﻦ اﺳﺖ ﺑﻴﺶ از دو ورودﯼ داﺷﺘﻪ ﺑﺎﺷﻨﺪ .ﯾﮏ ﮔﻴﺖ ANDﺑﺎ ﺳﻪ ورودﯼ و ﯾﮏ ﮔﻴﺖ ANDﺑﺎ ﺳﻪ ورودﯼ و ﯾﮏ ﮔﻴﺖ ORﺑﺎ ﭼﻬﺎر ورودﯼ در ﺷﮑﻞ )-١ (٢ﻧﺸﺎن دادﻩ ﺷﺪﻩ اﻧﺪ .ﮔﻴﺖ ANDﺳﻪ ورودﯼ ،ﺑﺸﺮﻃﯽ در ﺧﺮوﺟﯽ ﺧﻮد داراﯼ ﭘﺎﺳﺦ ١ﻣﻨﻄﻘﯽ ﺑﺎﺷﺪ ،ﺧﺮوﺟﯽ ﮔﻴﺖ ٠ﻣﻨﻄﻘﯽ اﺳﺖ .ﮔﻴﺖ ORﺑﺎ ﭼﻬﺎر ورودﯼ داراﯼ ﺧﺮوﺟﯽ ١ﻣﻨﻄﻘﯽ اﺳﺖ ﺑﺸﺮﻃﯽ ﮐﻪ ﺣﺪاﻗﻞ ﯾﮏ ورودﯾﻬﺎ ١،ﻣﻨﻄﻘﯽ ﺑﺎﺷﺪ و اﮔﺮ هﻤﻪ ﺳﻴﮕﻨﺎل هﺎﯼ ورودﯼ ٠ﻣﻨﻄﻘﯽ ﺑﺎﺷﻨﺪ ﺧﺮوﺟﯽ ٠ﻣﻨﻄﻘﯽ ﺧﻮاهﺪ ﺑﻮد . ﻓﺮم رﯾﺎﺿﯽ ﻣﻨﻄﻖ دودوﯾﯽ ،اﻏﻠﺐ ﺟﺒﺮ ﺑﻮل و ﯾﺎ ﺟﺒﺮ ﺳﻮﺋﻴﭽﻴﻨﮓ ﺧﻮاﻧﺪﻩ ﻣﯽ ﺷﻮد .اﯾﻦ ﺟﺒﺮ ﺑﺮاﯼ ﺗﺸﺮﯾﺢ ﻋﻤﻠﻴﺎت ﺷﺒﮑﻪ هﺎﯼ ﭘﻴﭽﻴﺪﻩ در ﻣﺪارهﺎﯼ دﯾﺠﻴﺘﺎل اﺳﺘﻔﺎدﻩ ﻣﯽ ﮔﺮدد . ﻃﺮاﺣﺎن ﺳﻴﺴﺘﻤﻬﺎﯼ دﯾﺠﻴﺘﺎل از ﺟﺒﺮ ﺑﻮل ﺑﺮاﯼ ﺗﺒﺪﯾﻞ اﺷﮑﺎل ﻣﺪارهﺎ ﺑﻪ ﻋﺒﺎرت ﺟﺒﺮﯼ و ﺑﺎﻟﻌﮑﺲ اﺳﺘﻔﺎدﻩ ﻣﯽ ﮐﻨﻨﺪ . 0
0
1 1
0
0
1
1
0
0
0 0
1
0
1
0
1
1
x
1 0
1 0
0 1
y AND : x.y OR : x+y َNOT : x
ﺷﮑﻞ ) (٢-٢ﺳﻴﮕﻨﺎﻟﻬﺎﯼ ورودﯼ – ﺧﺮوﺟﯽ ﺑﺮاﯼ ﮔﻴﺖ هﺎﯼ ) اﻟﻒ( )ب( )پ ( از ﺷﮑﻞ )(٢-١
ﮔﻴﺘﻬﺎﯼ دﯾﮕﺮﯼ ﯾﻌﻨﯽ ﺑﻌﻨﻮان ﮔﻴﺖ هﺎﯼ اﺳﺘﺎﻧﺪارد در ﻃﺮاﺣﯽ ﺳﻴﺴﺘﻢ هﺎﯼ دﯾﺠﻴﺘﺎل ﺑﮑﺎر ﻣﯽ روﻧﺪ .اﯾﻦ ﮔﻴﺘﻬﺎ ﻋﺒﺎرﺗﻨﺪ ازXNOR ، XOR ، NOR ، NAND : .
٢٠
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺗﺎﺑﻊ ، NANDﻣﮑﻤﻞ ANDﻣﯽ ﺑﺎﺷﺪ و ﻣﺘﺸﮑﻞ از ﯾﮏ ﺳﻤﺒﻞ ANDﮐﻪ ﺑﺪﻧﺒﺎل ﺁن داﯾﺮﻩ ﮐﻮﭼﮑﯽ ﻗﺮار ﮔﺮﻓﺘﻪ اﺳﺖ .ﺗﺎﺑﻊ NORﻣﮑﻤﻞ ﺗﺎﺑﻊ ORﺑﻮدﻩ و ﺑﻮﺳﻴﻠﻪ ﺳﻤﺒﻞ ORﮐﻪ ﺑﺪﻧﺒﺎل ﺁن داﯾﺮﻩ ﮐﻮﭼﮏ ﻧﻤﺎﯾﺶ دادﻩ ﻣﯽ ﺷﻮد .ﮔﻴﺖ هﺎﯼ NANDو NORﺑﺴﺎدﮔﯽ ﺑﻮﺳﻴﻠﻪ ﻣﺪارات ﺗﺮاﻧﺰﯾﺴﺘﻮرﯼ ﻗﺎﺑﻞ ﺗﻮﻟﻴﺪ ﺑﻮدﻩ و ﻣﯽ ﺗﻮان ﺑﺮاﺣﺘﯽ ﺗﻮاﺑﻊ ﺑﻮل را ﺑﺎ ﺁﻧﻬﺎ ﭘﻴﺎدﻩ ﻧﻤﻮد . ﮔﺒﺖ XORداراﯼ ﺳﻤﺒﻞ ﻣﺸﺎﺑﻬﯽ ﺑﺎ ORﻣﯽ ﺑﺎﺷﺪ ،ﺑﺠﺰ ﯾﮏ ﺧﻂ ﻣﻨﺤﻨﯽ ﮐﻪ در ﺳﻤﺖ ورودﯼ اش ﮐﺸﻴﺪﻩ ﺷﺪﻩ اﺳﺖ .ﮔﻴﺖ XNORﻣﮑﻤﻞ XORاﺳﺖ و ﻟﺬا ﯾﮏ داﯾﺮﻩ ﮐﻮﭼﮏ اﺿﺎﻓﯽ در ﺳﻤﺖ ﺧﺮوﺟﯽ ﺳﻤﺒﻞ ﺁن وﺟﻮد دارد .
x
( xy)′
x
( x + y)′
y
)اﻟﻒ ( ﮔﻴﺖ NAND
F = x⊕ y
y )ب( ﮔﻴﺖ NOR
X y
F = xΘ y
)پ( ﮔﻴﺖ XOR
X y )ت( ﮔﻴﺖ XNOR
ﺷﮑﻞ ) (٢-3ﮔﻴﺖ هﺎﯼ XNOR ، XOR ، NOR ، NAND ﮔﺴﺘﺮش ورودﯼ ﮔﻴﺖ هﺎ ﮔﻴﺖ هﺎﯼ ﻧﺸﺎن دادﻩ ﺷﺪﻩ ﺑﺠﺮ ﻣﻌﮑﻮس ﮐﻨﻨﺪﻩ و ﺑﺎﻓﺮ ،ﻗﺎﺑﻞ ﮔﺴﺘﺮش ﺑﻪ ﺣﺎﻟﺘﯽ ﺑﻴﺶ از دو ورودﯼ هﺴﺘﻨﺪ ﺑﺸﺮط اﯾﻨﮑﻪ ﻋﻤﻞ دودوﯾﯽ اراﺋﻪ ﺷﺪﻩ ﺑﻮﺳﻴﻠﻪ ﺁﻧﻬﺎ ﺧﻮاص ﺟﺎﺑﺠﺎﯾﯽ و ﺷﺮﮐﺖ ﭘﺬﯾﺮﯼ را داﺷﺘﻪ ﺑﺎﺷﺪ .اﻋﻤﺎل ANDو ORﮐﻪ در ﺟﺒﺮ ﺑﻮل ﺗﻌﺮﯾﻒ ﺷﺪﻧﺪ داراﯼ اﯾﻦ دو ﺧﺎﺻﻴﺖ هﺴﺘﻨﺪ .ﺑﺮاﯼ ﺗﺎﺑﻊ ORدارﯾﻢ : ﺟﺎﺑﺠﺎﯾﯽ
x+ y = y+ x
٢١
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
( x + y) + z = x + ( y + z) = x + y + z
و ﺷﺮﮐﺖ ﭘﺬﯾﺮﯼ
اﯾﻦ رواﺑﻂ ﺑﻴﺎﻧﮕﺮ ﺁﻧﻨﺪ ﮐﻪ ورودﯼ ﻗﺎﺑﻞ ﺗﻌﻮﯾﺾ ﺑﻮدﻩ و ﺑﻨﺎﺑﺮاﯾﻦ ﺗﺎﺑﻊ ORﻗﺎﺑﻞ ﮔﺴﺘﺮش ﺑﻪ ﺳﻪ ﻣﺘﻐﻴﺮ و ﺑﻴﺸﺘﺮ اﺳﺖ . ﺗﻮاﺑﻊ NANDو NORﺧﺎﺻﻴﺖ ﺟﺎﺑﺠﺎﯾﯽ دارﻧﺪ و ورودﯼ ﮔﻴﺖ ﺁﻧﻬﺎ ﻗﺎﺑﻞ ﮔﺴﺘﺮش اﺳﺖ ، ﺑﺸﺮط اﯾﻨﮑﻪ ﺗﻌﺮﯾﻒ ﻋﻤﻞ ﺁﻧﻬﺎ ﺗﺼﺤﻴﺢ ﺷﻮد .ﻣﺸﮑﻞ اﯾﻦ اﺳﺖ ﮐﻪ ﻋﻤﻠﮕﺮهﺎﯼ ، NAND NORﺷﺮﮐﺖ ﭘﺬﯾﺮﯼ ﻧﻴﺴﺘﻨﺪ .ﯾﻌﻨﯽ :
)( x ↓ y) ↓ z ≠ x ↓ ( y ↓ z زﯾﺮا ﻃﺒﻖ ﺷﮑﻞ ) ( ٢-4دارﯾﻢ :
( x ↓ y) ↓ z = [( x − y)′ + z]′ = ( x + y) z′ = xz′ + yz′ x ↓ ( y ↓ z) = [ x + ( y + z)′]′ = x′( y + z) = x′y + x′z
x y ( x ↓ y) ↓ z = ( x +
x ↓ ( y ↓ z ) = x′( y +
x y z
ﺷﮑﻞ ) (٢-4ﻧﻤﺎﯾﺶ ﺷﺮﮐﺖ ﭘﺬﯾﺮ ﻧﺒﻮدن ( x ↓ y) ↓ z ≠ x( y ↓ z) ،NOR
z
٢٢
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺑﺮاﯼ ﻏﻠﺒﻪ ﺑﺮاﯾﻦ ﻣﺸﮑﻞ ﮔﻴﺖ هﺎﯼ ( NAND) NORﭼﻨﺪ ورودﯼ را ﺑﻌﻨﻮان ﻣﮑﻤﻞ OR ) ( ANDﺁن ﺗﻌﺮﯾﻒ ﻣﯽ ﮐﻨﻴﻢ ،ﺑﻨﺎﺑﺮاﯾﻦ دارﯾﻢ :
x ↓ y ↓ z = ( x + y + z)′ x ↑ y ↑ z = ( xyz)′ ﺳﻤﺒﻞ هﺎﯼ ﮔﺮاﻓﻴﮑﯽ ﺑﺮاﯼ ﮔﻴﺖ هﺎﯼ ﺳﻪ ورودﯼ در ﺷﮑﻞ ) (٢-5ﻧﺸﺎن دادﻩ ﺷﺪﻩ اﻧﺪ .در ﻧﻮﺷﺘﻦ ﻣﺘﻮاﻟﯽ اﻋﻤﺎل NORو NANDﺑﺎﯾﺴﺘﯽ ﭘﺮاﻧﺘﺰهﺎ ﺑﻔﺮم ﺻﺤﻴﺢ اﻧﺘﺨﺎب ﺷﻮﻧﺪ ،ﺗﺎ ﺑﻴﺎﻧﮕﺮ ﺗﺮﺗﻴﺐ ﺻﺤﻴﺢ ﮔﻴﺖ هﺎ ﺑﺎﺷﻨﺪ .ﺑﺮاﯼ ﻧﻤﺎﯾﺶ اﯾﻦ ﻣﻄﻠﺐ ﻣﺪار ﺷﮑﻞ )-5 -٢پ( راﻣﻼﺣﻈﻪ ﮐﻨﻴﺪ .ﺗﺎﺑﻊ ﺑﻮل ﺑﺮاﯼ اﯾﻦ ﻣﺪر ﺑﺎﯾﺴﺘﯽ ﺑﻔﺮم زﯾﺮ ﻧﻮﺷﺘﻪ ﺷﻮد :
F = [( ABC)′(DE)′]′ = ABC + DE دوﻣﻴﻦ ﻋﺒﺎرت از راﺑﻄﻪ دﻣﻮرﮔﺎن ﻧﺘﻴﺠﻪ ﺷﺪﻩ اﺳﺖ .اﯾﻦ راﺑﻄﻪ هﻤﭽﻨﻴﻦ ﺑﻴﺎﻧﮕﺮ ﺁﻧﺴﺖ ﮐﻪ ﺟﻤﻊ ﺣﺎﺻﻠﻀﺮب هﺎ ﻗﺎﺑﻞ ﭘﻴﺎدﻩ ﺷﺪن ﺑﻮﺳﻴﻠﻪ ﮔﻴﺖ هﺎ NANDاﺳﺖ . ﮔﻴﺖ هﺎ XORو XNORهﺮ دو داراﯼ ﺧﻮاص ﺟﺎﺑﺠﺎﯾﯽ و ﺷﺮﮐﺖ ﭘﺬﯾﺮﯼ ﺑﻮدﻩ ،ورودﯼ ﺷﺎن ﻗﺎﺑﻞ ﺗﻮﺳﻌﻪ ﺑﻪ ﺑﻴﺸﺘﺮ از دو ﻣﯽ ﺑﺎﺷﺪ .ﻣﻌﻬﺬا ﻣﺪارهﺎﯼ XORﺑﺎ ﭼﻨﺪ ورودﯼ ،از ﻧﻘﻄﻪ ﻧﻈﺮ ﺳﺨﺖ اﻓﺰارﯼ ﻣﺘﺪاول ﻧﻴﺴﺘﻨﺪ .در واﻗﻊ ﺣﺘﯽ ﻓﺮم دو ورودﯼ ﺁن ﻧﻴﺰ ﻣﻌﻤﻮﻻً از ﺳﺎﯾﺮ ﮔﻴﺖ هﺎ ﺳﺎﺧﺘﻪ ﻣﯽ ﺷﻮد .ﻋﻼوﻩ ﺑﺮ اﯾﻦ ﺗﻌﺮﯾﻒ اﯾﻦ ﺗﻮاﺑﻊ ﺑﺎﯾﺴﺘﯽ ﺑﻬﻨﮕﺎم ﮔﺴﺘﺮش ورودﯼ ﺁﻧﻬﺎ ﺗﺼﺤﻴﺢ ﮔﺮدد .ﺗﺎﺑﻊ XORﯾﮏ ﺗﺎﺑﻪ ﻓﺮد اﺳﺖ ﯾﻌﻨﯽ هﺮﮔﺎﻩ ورودﯼ هﺎ ﺗﻌﺪاد ﻏﺮدﯼ ١را دارا ﺑﺎﺷﻨﺪ اﯾﻦ ﺗﺎﺑﻊ ﺑﺮاﺑﺮ ١ﺧﻮاهﺪ ﺑﻮد .ﺳﺎﺧﺘﻤﺎن ﯾﮏ ﮔﻴﺖ XORﺑﺎ ﺳﻪ ورودﯼ در ﺷﮑﻞ ) (٢-۶دﯾﺪﻩ ﻣﯽ ﺷﻮد .اﯾﻦ ﻣﺪار ﻣﻌﻤﻮﻻً ﺑﺎ ﮔﻴﺖ هﺎﯼ دو ورودﯼ ﺗﻬﻴﻪ ﻣﯽ ﮔﺮدد .ﺷﮑﻞ )اﻟﻒ( ﻓﺮم ﮔﺮاﻓﻴﮑﯽ ﺁن را ﺑﺎ ﮔﻴﺖ ﺳﻪ ورودﯼ ﻧﻴﺰ ﻣﯽ ﺗﻮان ﻧﺸﺎن داد ،ﺷﮑﻞ ب ( ﺟﺪول درﺳﺘﯽ در ) پ( ﺑﻄﻮر ﺁﺷﮑﺎر ﻣﺸﺨﺺ ﻣﯽ ﻧﻤﺎﯾﺪ ﮐﻪ ﺧﺮوﺟﯽ F
٢٣
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ
ﺑﺮاﺑﺮ ١ﺧﻮاهﺪ ﺑﻮد ،اﮔﺮ ﻓﻘﻂ ﯾﮑﯽ از ورودﯼ هﺎ و ﯾﺎ هﺮ ﺳﻪ ورودﯼ ﺑﺮاﺑﺮ ﺑﺎﺷﺪ .ﺑﻪ ﺑﻴﺎن دﯾﮕﺮ وﻗﺘﯽ ﺗﻌﺪاد ١هﺎ درورودﯼ ﻓﺮد اﺳﺖ Fﻣﺴﺎوﯼ ١اﺳﺖ . اﺿﺎﻓﻪ ﻣﯽ ﻧﻤﺎﯾﺪ ﮐﻪ ﺗﺎﺑﻊ NORﯾﮏ ﺗﺎﺑﻊ زوج اﺳﺖ .ﯾﻌﻨﯽ هﺮﮔﺎﻩ ﺗﻌﺪاد ٠هﺎ در ورودﯼ زوج ﺑﺎﺷﺪ اﯾﻦ ﺗﺎﺑﻊ ﻣﺴﺎوﯼ ١اﺳﺖ .
x
( xyz)′
y
z
)اﻟﻒ ( ﮔﻴﺖ NORﺳﻪ ورودﯼ
x
( x + y + z )′
y
z
)ب( ﮔﻴﺖ NORﺳﻪ ورودﯼ
A
B
C
F = [( ABC )′.( DE )′]′ = ABC + DE
)پ( ﮔﻴﺖ هﺎﯼ ﻣﺘﻮاﻟﯽ NAND
D E
ﺷﮑﻞ ) (٢-5ﮔﻴﺖ هﺎﯼ NANDو NORﭘﺸﺖ ﺳﺮ هﻢ و ﭼﻨﺪ ورودﯼ
X y F = x⊕ y⊕ z
Z )اﻟﻒ( ﺑﺎ ﮔﻴﺖ هﺎﯼ دو ورودﯼ
F = x⊕ y⊕ z )ب( ﯾﮏ ﮔﻴﺖ ﺳﻪ ورودﯼ
ﺷﮑﻞ ) (٢-۶ﮔﻴﺖ XORﺳﻪ ورودﯼ
X y z
٢٤
ﻓﺼﻞ دوم :ﺟﺒﺮ ﺑﻮل و ﮔﻴﺖ هﺎﯼ ﻣﻨﻄﻘﯽ ﻣﻨﻄﻖ ﻣﺜﺒﺖ و ﻣﻨﻔﯽ
ﺳﻴﮕﻨﺎل دودوﯾﯽ در ورودﯼ ﯾﺎ ﺧﺮوﺟﯽ هﺮ ﮔﻴﺖ ﯾﮑﯽ از دو ﻣﻘﺪار را ﺑﺠﺰ در ﺣﺎﻟﺖ ﮔﺬرا ، دارد .ﯾﮏ ﻣﻘﺪار ﺳﻴﮕﻨﺎل ﻣﻨﻄﻖ ١-و دﯾﮕﺮﯼ ﻣﻨﻄﻖ ٠-را ﻧﻤﺎﯾﺶ ﻣﯽ دهﺪ .ﭼﻮن دو ﻣﻘﺪار ﺳﻴﮕﻨﺎل ﻣﺘﻌﻠﻖ ﺑﻪ دو ارزش ﻣﻨﻄﻘﯽ اﺳﺖ ،ﻟﺬا دو اﻧﺘﺴﺎب ﻣﺘﻔﺎوت ﺑﺮاﯼ دو ارزش ﻣﻨﻄﻘﯽ ﻣﯽ ﺗﻮان اﺧﺘﻴﺎر ﮐﺮد ،ﺷﮑﻞ ) (٢-٧اﻧﺘﺨﺎب ﺳﻄﺢ ﺑﺎﻻﺗﺮ Hﺑﺮاﯼ ﻧﻤﺎﯾﺶ ﻣﻨﻄﻖ ١ﻣﻄﺎﺑﻖ ﺷﮑﻞ )-٢-٧اﻟﻒ( ،ﺳﻴﺴﺘﻢ ﻣﻨﻄﻖ ﻣﺜﺒﺖ را ﻣﻌﺮﻓﯽ ﻣﯽ ﻧﻤﺎﯾﺪ و اﻧﺘﺨﺎب ﺳﻄﺢ ﭘﺎﯾﻴﻦ Lﺑﻌﻨﻮان ﻣﻨﻄﻖ .١ ﻣﻘﺪار ﻣﻨﻄﻘﯽ
ﻣﻘﺪار ﺳﻴﮕﻨﺎل H
٠ L
١ )ب( ﻣﻨﻄﻖ ﻣﻨﻔﯽ
ﻣﻘﺪار ﺳﻴﮕﻨﺎل
ﻣﻘﺪار ﻣﻨﻄﻘﯽ
H
٠
L
١ )اﻟﻒ (ﻣﻨﻄﻖ ﻣﺜﺒﺖ
ﺷﮑﻞ ) (٢-٧ﻋﻼﻣﺖ داﻣﻨﻪ ﺳﻴﮕﻨﺎل و ﻧﻮع ﻣﻨﻄﻖ
