مدارهای منطقی(فصل دوم)
فصل دوم
گيت هاي منطقي، جبر بول و توابع بولي
هدف كلي
در اين فصل مباحث كلي مربوط به منطق دودويي به همراه مفاهيم اساسي جبر بول
مورد بحث و بررسي قرار خواهند گرفت. در ادامه مفاهيم و تئوري هاي اساسي جبر
بول بررسي شده و در ادامه توابع بول نيز به صورت كامل مورد نقد و بررسي قرار
خواهند گرفت. در ادامه نيز انواع گيت هاي منطقي به همراه جداول درستي هر يك
بررسي خواهند شد.
هدف ساختاري
در اين فصل عناوين زير مورد بحث و بررسي قرار مي گيرند:
• منطق دودويي
• انواع گيت هاي منطقي
• اصول اساسي جبر بول
• تئوري هاي اساسي جبر بول
• تقدم عمل گرها در جبر بول
• توابع بول
• متمم توابع بول
• مدارهاي مجتمع
44 مدار منطقي
1 منطق دودويي -2
منطق دودويي با متغيرهايي كه دو ارزش گسسته و عملياتي كه مفهوم منطقي دارند،
سرو كار دارد و ارزشي كه متغيرها اختيار مي كنند ممكن است با اسامي مختلفي
نام گذاري شوند (مثل صحيح و غلط، بله و خير و غيره)، اما براي ما بهتر است آن را بر
حسب بيت تصور كنيم و مقادير 1 و 0 را به آن تخصيص دهيم. منطق دودويي معرفي
شده در اين بخش معادل با جبري به نام جبر بول است. در اين بخش جبر بول به
روشي غير مستدل بوده و ارتباط آن با مدارهاي منطقي ديجيتال و سيگنال هاي دودويي
بيان شده است.
1 تعريف منطق دودويي -1 -2
منطق دودويي شامل متغيرهاي دودويي و عمليات منطقي است. متغيرها با حروف
و غيره نام گذاري مي شوند، كه هر متغير فقط و فقط دو Z ،Y ،X ،C ،B ،A الفبايي مانند
و OR ،AND : مقدار مجزاي 0 و 1 دارد. سه نوع عمليات منطقي اصلي وجود دارند
در ادامه به شرح هر يك از عمليات مي پردازيم: .NOT
اين عمل به وسيله يك "."يا بدون ذكر هر عملگري نمايش داده مي شود. :AND -1
." z برابر است با x AND y " را چنين مي خوانيم x y = z يا x.y = z مثلاً
y= و 1 x= است اگر و فقط اگر 1 z= چنين تفسير مي شود كه، 1 AND عمل منطقي
متغيرهاي z و y و x است. (به ياد داشته باشيد كه z= باشد؛ در غير اين صورت 0
دودويي هستند و نمي توانند به جز 1 و 0 چيز ديگري باشند.)
را چنين x+y=z عملي است كه با علامت بعلاوه نشان داده مي شود. مثلاً :OR -2
است به شرطي كه z= و به اين معني است كه 1 " z برابر است با x OR y " مي خوانيم
z= باشد آنگاه 0 y= و 0 x= باشند. اگر هر دو 0 y= و 1 x= و يا هر دو 1 y= و 1 x=1
خواهد بود.
گيت هاي منطقي، جبر بول و توابع بولي 45
اين علامت با يك علامت پريم نشان داده مي شود (و گاهي با يك خط :NOT -3
و به اين " z برابر است با NOT x " ، و چنين خوانده مي شود (x=z يا ) x´=z بار). مثلاً
اما ؛ z= باشد آنگاه 0 x= نيست. به بيان ديگر اگر 1 x چيزي است كه z معني است كه
را متمم هم مي گويند چون 1 را به 0 و 0 را NOT است. عمل z= باشد، آنگاه 1 x= اگر 0
به 1 تبديل مي كند.
به ترتيب به اعمال OR و AND منطق دودويي شبيه حساب دودويي است، و اعمال
همان OR و AND ضرب و جمع شباهت دارند. در حقيقت سمبل هاي به كار رفته براي
هايي هستند كه براي ضرب و جمع مورد استفاده قرار مي گيرند. معهذا منطق دودويي
را نبايد با حساب دودويي اشتباه كرد. مسئله اي كه بايد مورد توجه قرار گيرد اين است
كه يك متغير حسابي، عددي را مشخص مي كند كه ممكن است داراي چندين رقم
باشد. يك متغير منطقي هميشه 0 و يا 1 است.
1 (مي خوانيم: "يك بعلاوه يك برابر است با +10= مثلاً در حساب دودويي داريم 1
يك، برابر OR 1 (مي خوانيم: "يك + 1 = 2")، در صورتيكه در منطق دودويي، داريم 1
.(" است با 1
AND OR
x y x. y x y x + y
0 0 0 0 0 0
0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1
NOT
x x'
0 1
1 0
1: جدول درستي عمليات منطقي - شكل 2
46 مدار منطقي
وجود دارد كه اين مقدار پس z مقدار معيني براي ،y و x براي هر تركيبي از مقادير
از اعمال يا تعريف عمل منطقي مشخص مي گردد. اين تعاريف را مي توان به صورت
خلاصه يا استفاده از جدول درستي فهرست كرد. يك جدول درستي، جدولي است
متشكل از تمام تركيبات ممكن متغيرها و بيانگر ارتباط بين مقادير آنها و نتايج حاصل
از عمل مربوطه روي آنها مي باشد. به عنوان مثال جداول درستي براي عملگرهاي
با ليست كردن همه مقادير ممكن آنها وقتي به ، y و x با متغيرها ي OR و AND
صورت زوج تركيب شده اند، حاصل مي شود. نتيجه عمل براي هر تركيب به طور
در جدول زير نشان داده NOT و OR و AND جداگانه آمده است. جداول درستي
شده اند. اين جداول تعريف عمليات مذكور را به طور شفاف بيان مي دارند.
2 گيت هاي منطقي -1 -2
گيت هاي منطقي، مدارهايي الكترونيك هستند كه روي يك يا چند سيگنال ورودي
عمل مي كنند تا يك سيگنال خروجي توليد نمايند. سيگنال هاي الكترونيكي مانند
ولتاژها يا جريانهايي كه در سرتاسر يك سيستم ديجيتال وجود دارند دو مقدار جدا از
هم را اختيار مي كنند. مدارهايي كه با ولتاژ كار مي كنند به دو سطح ولتاژ كه نمايشگر
2
3
1
4
0
ولت
انحراف مجاز براي
منطق 1
انحراف مجاز براي
منطق 0
انتقال در محدوده اين
دو ناحيه رخ مي دهد
2: محدوده انتقال سيگنال 0 و 1 - شكل 2
گيت هاي منطقي، جبر بول و توابع بولي 47
يك متغير دودويي و برابر با منطق 1 و منطق 0 اند واكنش نشان مي دهند. مثلاً يك
سيستم ديجيتال خاص ممكن است منطق 0 را به عنوان سيگنالي برابر با 0 ولت و منطق
1 را به صورت سيگنالي برابر با 4 ولت تعريف كند. در عمل، هر سطح ولتاژ، محدوده
2 را داراست. - مورد قبولي مانند شكل 2
پايانه هاي ورودي مدارهاي ديجيتال سيگنال هاي دودويي را در محدوده مجازي
مي پذيرند و در پايانه هاي خروجي در محدوده مجازي پاسخ مي دهند. ناحيه مياني بين
دو ناحيه مجاز تنها هنگام گذر از يك حالت به حالت ديگر قطع مي شود. هر اطلاعات
محاسباتي يا كنترلي مورد نظر را مي توان با عبور سيگنال هايي دودويي از ميان تركيباتي
از گيت ها مورد استفاده قرار داد، كه هر سيگنال بيانگر يك متغير دودويي بوده و يك
بيت از اطلاعات را حمل مي كند.
3 ديده مي شوند: - سمبل هاي گرافيكي مورد استفاده براي سه نوع گيت در شكل 2
گيت ها، بلوكهايي سخت افزاري اند كه با ورودي منطقي مناسبي، در خروجي خود 0
در يكي از چهار OR و AND در گيت هاي y و x يا 1 توليد مي نمايند. سيگنال ورودي
x x' NOT گيت
AND گيت
x
y
z = x. y
x
y
z = x + y
OR گيت
3: سمبلهاي مداري منطقي ديجيتال - شكل 2
48 مدار منطقي
10 و 11 . اين سيگنال ها همراه با خروجي خود در ،01 ، حالت ممكن قرار دارند: 00
4 ديده مي شوند. نمودارهاي زماني پاسخ هر گيت را براي چهار گيت فوق - شكل 2
نشان مي دهند. محور افقي نمودار زمان، و محور عمودي سيگنال ها را ضمن تغيير بين
دو سطح ولتاژ ممكن نمايش مي دهد. سطح پايين منطق 0 و سطح بالا منطق 1 را نشان
منطق 1 وجود دارد كه هر دو سيگنال ورودي AND مي دهد. هنگامي در خروجي گيت
هنگامي خروجي 1 دارد كه يكي از سيگنال هاي ورودي در OR در منطق 1 باشند. گيت
را معمولاً وارون گر يا معكوس گر هم مي گويند. دليل انتخاب NOT منطق 1 باشد. گيت
اين نام با توجه به پاسخ سيگنال در نمودار زماني مشخص است، و در آن نشان داده
شده است كه سيگنال خروجي مفهوم منطق ورودي را معكوس كرده است.
با چهار ورودي OR با سه ورودي ب- گيت AND الف- گيت
5: مدار سوئيچينگ نمايش دهنده منطق دودويي - شكل 2
F = ABC AB
C
F = A+B+C+D
A
B
C
D
X 0 1 1 0 0
Y 0 0 1 1 0
AND : x . y 0 0 1 0 0
OR : x + y 0 1 1 1 0
NOT : x´ 1 0 0 1 1
AND , OR ,NOT 4: سيگنال هاي ورودي- خروجي براي گيت هاي - شكل 2
گيت هاي منطقي، جبر بول و توابع بولي 49
AND ممكن است بيش از دو ورودي داشته باشند. يك گيت OR و AND گيت هاي
سه AND 5 ملاحظه مي شود. گيت - با چهار ورودي در شكل 2 OR با سه ورودي و يك
ورودي به شرطي خروجي 1 دارد كه هر سه ورودي آن 1 باشد. اگر هر يك از
چهار ورودي OR برابر 0 خواهد بود. گيت AND ورودي ها 0 باشند، خروجي
هنگامي خروجي 1 توليد مي كند كه يكي از ورودي ها در 1 منطقي باشد. خروجي
هنگامي 0 مي شود كه همه ورودي ها در منطق 0 باشند.
-2 جبر بول -2
جبر بول را مي توان مانند هر سيستم منتجه رياضي، به وسيله مجموعه اي از عناصر، يك
مجموعه از الگوها و تعدادي اصول اثبات نشده يا بديهيات تعريف نمود. يك مجموعه
يك s از عناصر كلكسيوني از اشياء است كه داراي خواص مشتركي باشند. اگر
x به اين معني است كه x ∈ s عناصر مشخصي از آن باشند، آنگاه y و x مجموعه و
نيست. يك مجموعه s عضوي از مجموعه y يعني y ∉ s است و s عضوي از مجموعه
A = { با تعداد قابل شمارشي از عناصر با يك جفت آكولاد مشخص مي شود: { 1,2,3,4
عبارتند از 4,3,2,1 . يك عملگر دودويي روي يك مجموعه A يعني عناصر مجموعه
S يك عنصر منحصر به فرد از ،S قانوني است كه به هر جفت از عناصر ،S ، از عناصر
را در نظر بگيريد. (*) را يك عملگر a ∗b= c را تخصيص دهد. به عنوان مثال رابطه
منتسب نمايد b وa را به جفت عنصر c دودويي مي خوانيم به شرطي كه بتواند عنصر
c∉S و a,b∈S معتبر باشد. با اين وجود اگر a,b,c∈S ضمن اينكه رابطه
باشد، (*) يك عملگر دودويي نيست.
اصول يك سيستم رياضي، فرضيات اوليه را تشكيل مي دهند كه با استفاده از آنها
مي توان قوانين و تئوري ها و خواص سيستم را نتيجه گرفت. مهمترين اصول به كار رفته
در فرموله كردن ساختارهاي جبري عبارتند از:
1. بسته بودن
50 مدار منطقي
2. عنصر شناسه
3. عنصر معكوس
4. اصل شركت پذيري
5. اصل جابجايي
6. اصل توزيع پذيري
نسبت به عملگر دودويي بسته است به شرطي كه s -1 بسته بودن: يك مجموعه
اين عملگر عنصر منحصر به فردي از آن را به جفت عنصر ،s براي هر جفت عنصر از
را نسبت به N = {1,2,3,4,K} منتسب نمايد. به عنوان مثال، مجموعه اعداد طبيعي
عنصر ديگري a,b∈N عملگر جمع (+) بسته گوييم زيرا براي هر دو عنصر
باشد. مجموعه اعداد طبيعي نسبت به a + b = c مي توان يافت بطوري كه c∈N مانند
−1∉N 2,3 و ∈N 2 در حالي كه − 3 = − عملگر تفريق بسته نيست چون داريم 1
است.
داراي عنصر S نسبت به عملگر (*) روي مجموعه S -2 عنصر شناسه: مجموعه
با خاصيت زير موجود باشد. e ∈ S شناسه است، اگر عنصر
e *x = x*e = x: داشته باشيم x∈ S به ازاي هر
يك عنصر شناسه نسبت به عملگر (+) روي مجموعه اعداد صحيح o مثال: عنصر
است، چون I={…,—3,—2,—1,0,1,2,3,…}
x + 0 = 0 + x = x : داشته باشيم x∈ I به ازاي هر
داراي عنصر شناسه نيست زيرا 0 جزو مجموعه نمي باشد. N مجموعه اعداد طبيعي
گيت هاي منطقي، جبر بول و توابع بولي 51
نسبت به عملگر (*) e با عنصر شناسه S -3 عنصر معكوس: مجموعه اي چون
وجود داشته باشد به y∈S يك ، x∈ S داراي معكوس است به شرطي كه براي هر
نحوي كه:
x * y = e
است چون ( - a) برابر a معكوس عنصر ،e = با 0 ،I مثال: در مجموعه اعداد صحيح
a + ( - a) = 0
شركت پذير S -4 اصل شركت پذيري: يك عملكرد دودويي (*) روي مجموعه
است اگر داشته باشيم:
(x*y) * z =x* (y*z) : داشته باشيم x,y ,z∈ S به ازاي همه مقادير
-5 اصل جابجايي: يك عملگر (*) روي مجموعه داراي خاصيت جابجايي است
هرگاه:
x*y = y*x : داشته باشيم y,x ∈ S به ازاي هر
باشند، (*) را S -6 اصل توزيع پذيري: اگر (*) و (.) دو عملگر روي مجموعه
روي (.) توزيع پذير گوييم هرگاه:
x ∗ ( y.z) = (x ∗ y).(x ∗ z)
مثالي جبري در اين مورد ميدان يا حوزه است. ميدان مجموعه اي از عناصر است،
همراه با دو عملگر دودويي، كه هر يك داراي خواص 1 تا 5 بوده و هر دو عملگر
براي تشكيل خاصيت 6 با يكديگر تركيب مي شوند. مجموعه اعداد حقيقي، همراه با
عملگرهاي دودويي (+) و (.)، ميدان اعداد حقيقي را تشكيل مي دهند. ميدان اعداد
حقيقي مبناي جبر معمولي و حساب است. عملگرها و اصول داراي مفاهيم زير هستند:
عملگر دودويي (+) جمع را تعريف مي كند.
معكوس جمع، تفريق مي باشد..
52 مدار منطقي
شناسه جمع، 0 است
شناسه ضرب 1 مي باشد.
عملگر دودويي (.) ضرب را تعريف مي نمايد.
تقسيم را تعريف مي كند، يعني a = 1/a معكوس ضرب
a.(1/a) = 1
تنها اصل توزيع پذيري قابل اعمال مربوط به عملگر (.) روي (+) است:
a. (b + c) = (a. b) + (a. c)
1 تعريف اصول اساسي جبر بول -2 -2
در سال 1854 جورج بول يك سيستم جبري را كه امروزه آن را جبر بول مي ناميم
پايه ريزي كرد. در سال 1938 نيز شانون يك جبر بول دو مقداري به نام جبر
سوئيچينگ را معرفي كرد كه در آن خواص مدارهاي سوئيچينگ با اين جبر قابل ارائه
است. براي تعريف مستدل جبر بول، ما اصول فرموله شده به وسيله هانتينگتون در سال
1904 را به كار مي بريم. اصول هانتيگتون به شرح زير بودند:
مجموعه نسبت به عملگر (+) بسته باشد. (a) -1
مجموعه نسبت به عملگر (.) بسته باشد. (b)
يك عنصر شناسه 0 براي (+) وجود داشته باشد. (a) -2
يك عنصر شناسه 1 براي (.) وجود داشته باشد. (b)
مي گوييم) x وجود دارد (به آن متمم x´∈ B عنصري مثل ،x∈ B -3 براي هر عنصر
x´. x = (b) و x´+x= I (a) : به نحوي كه
باشد. x≠ y وجود دارد به نحوي كه x,y∈ B -4 حداقل دو عنصر
x + y = y + x : مجموعه نسبت به (+) داراي خاصيت جابجايي باشد (a) -5
گيت هاي منطقي، جبر بول و توابع بولي 53
x. y = y. x : مجموعه نسبت به (.) داراي خاصيت جابجايي باشد (b)
x. (y+z) = (x.y) + (x.z) : نسبت به (+) توزيع پذير است (.) (a) -6
x+ (y.z) = (x+y) + (x+y) : نسبت به (.) توزيع پذير است (+) (b)
همراه با دو ،B جبر بول يك ساختار جبري است كه با عناصر مجموعه، يعني
عملگر دودويي (+) و (.) تعريف مي شود به شرطي كه اصول زير (هانتينگتون) در آن
معتبر باشد. به بياني ديگر به منظور داشتن يك جبر بول بايد:
مشخص باشند. B -1 عناصر مجموعه
-2 قوانين عمل دو عملگر دودويي معين باشند.
همراه با دو عملگر، براي شش اصل هانتينگتون معتبر باشد. ،B ، -3 مجموعه عناصر
1 تفاوت هاي جبر بول با جبر معمولي -1 -2 -2
با مقايسه جبر بول با حساب و جبر معمولي (حوزه يا ميدان اعداد حقيقي) تفاوت هاي
زير قابل ملاحظه اند:
-1 اصول هانتينگتون فاقد اصل شركت پذيري است. با اين وجود، اين اصول براي
جبر بول معتبر و براي هر دو عملگر از ديگر اصول قابل استنتاج است.
براي جبر بول ، x+(y.z) = (x+y). (x+z) -2 اصل توزيع پذيري (+) روي (.)، يعني
معتبر است، ولي در جبر معمولي قابل قبول نيست.
-3 جبر بول داراي معكوس هاي جمع و ضرب نيست؛ بنابراين عملگرهاي تفريق و
تقسيم وجود ندارند.
-4 اصل 3 عملگري به نام متمم را معرفي مي نمايد كه در جبر معمولي وجود
ندارد.
54 مدار منطقي
-5 جبر معمولي در مورد اعداد حقيقي بحث مي كند، كه يك مجموعه با بي نهايت
بحث مي نمايد كه ،B ، عنصر را شامل مي شود. جبر بول در مورد مجموعه اي از عناصر
هنوز آن را معرفي نكرده ايم، ولي بعداً در جبر بول دو مقداري يا دو ارزشي معرفي
به صورت B خواهد شد (كاربرد بعدي ما از اين جبر مورد توجه است)، و در آن
مجموعه اي از دو عنصر 0 و 1 تعريف مي شود.
لازم است تا اختلاف بين يك مجموعه از عناصر متعلق به يك ساختار جبري و
متغيرهاي يك سيستم جبري را بدانيم. مثلاً اجزاء حوزه اعداد حقيقي، اعداد هستند، در
كه در جبر معمولي به كار مي روند، سمبل هايي c و b ،a صورتي كه متغيرهايي مانند
B هستند كه به جاي اعداد حقيقي به كار مي روند. به طور مشابه در جبر بول مجموعه
مي باشد كه صرفاً سمبل هستند و عناصر را نشان z و y ،x داراي متغيرهايي مانند
مي دهند.
و قوانين عمليات، مي توان چندين جبر بول را فرموله B بسته به انتخاب عناصر
كرد. در ادامه كار ما فقط با جبر دو ارزشي كه تنها دو عنصر دارد، سرو كار خواهيم
داشت. جبر بول دو ارزشي در تئوري مجموعه ها و منطق كاربرد دارد. هدف ما در اين
كتاب كاربرد جبر بول در مدار منطقي گيتي است.
2 جبر بول دو ارزشي -1 -2 -2
0 }، به همراه قوانين براي دو = B جبر بول دو ارزشي روي مجموعه دو عنصري، { 1و
x y x. y x y x + y X x´
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1
عملگر دودويي (+) و (.) كه در جدول زير نشان داده شده تعريف مي شود (قانون
و OR ، AND عملگر متمم براي تصديق اصل 3 است):اين قوانين دقيقاً مثل اعمال
گيت هاي منطقي، جبر بول و توابع بولي 55
1 مي باشند. اكنون نشان مي دهيم كه اصول هانتينگتون براي مجموعه، - در شكل 2 NOT
0 } و دو عملگرهاي دودويي كه قبلاً تعريف شده اند، معتبر است. = B 1و }
-1 با توجه به جداول، بسته بودن كاملاً روشن است زيرا نتيجه هر عملگر 1 يا 0
1 مي باشند. 0 , ∈ B بوده و
-2 با توجه به جداول مي بينيم كه:
(a) 1+ 1 = 0 + 1 = 1 + 0 = 1
(b) 1. 0 = 0. 1= 0. 0 = 0
اين روابط بيانگر وجود عناصر شناسه 0 براي (+) و 1 براي (.)، طبق تعريف
مي باشند.
-3 اصول جابجايي با توجه به تقارن جداول عملگرها آشكار است.
را با ايجاد جدول براي x. (y + z) = (x. y) + (x. z) صحت اصل توزيع پذيري (a) -4
را به دست x. (y + z) ، مي توان تحقيق كرد. براي هر تركيب ، z,y,x تمام مقادير ممكن
است. (x. y) + (x. z) آورده و نشان مي دهيم كه برابر
صحت اصل توزيع پذيري (+) روي (.) را نيز مي توان مانند بند قبل تحقيق (b)
نمود.
-5 با استفاده از جدول متمم، به سادگي مي توان ديد كه:
x.y x.z (x . y) + (x . z )
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 1 1
1 0 1
1 1 1
y +z x . ( y + z )
0 0
1 0
1 0
1 0
0 0
1 1
1 1
1 1
x y z
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
56 مدار منطقي
1+1 است. ´=1+0=1 , 0+0´=0+1= زيرا 1 ، x+x´=1 (a)
1.1 است، كه اصل 5 را تصديق مي كند. ´=1.0=0 , 0.0´=0.1= زيرا 0 ، x.x´=0 (b)
-6 اصل 6 نيز صادق است زيرا جبر بول دو ارزشي داراي دو مقدار مجزاي 0 و 1
1است. ≠ با 0
و يك عملگر متمم معادل OR , AND تا اينجا ما يك جبر دو ارزشي با عملگرهاي
ايجاد كرديم. بنابراين جبر بول به روش مستدل رياضي بنا گرديد و نشان داده NOT با
شد كه معادل با منطق دودويي غير مستدل است. بيان غير مستدل براي درك كاربرد
جبر بول در مدارهاي گيتي مفيد است. روش مستدل براي بيان و ايجاد تئوري ها و
خواص سيستم جبري مورد توجه است. جبر بول دو ارزشي تعريف شده در اين بخش
را "جبر سوئيچينگ" نيز مي نامند. براي تاكيد بر تشابه بين جبر بول دو ارزشي و ديگر
سيستم هاي دودويي، اين جبر در بخش قبل "منطق دودويي" ناميده شد. از اين پس،
كلمه "دو ارزشي" را در بحث هاي بعدي از جبر بول حذف مي كنيم.
2 قضاياي اصلي و خواص جبر بول -2 -2
(b) و (a) اصول هانتينگتون به صورت جفت جفت ليست شده اند و به صورت بخشهاي
مشخص شدند. هر يك از اين دو را با تعويض عملگرها و عنصر شناسه مي توان از
ديگري به دست آورد. اين خاصيت در جبر بول به اصل دوگانگي معروف است.
خصوصيات فوق بيان مي دارد كه هر عبارت جبري منتج از اصول جبر بول با تعويض
عملگرها و شناسه ها باز هم معتبر باقي مي ماند. در جبر بول دو ارزشي، عناصر شناسه
يكسانند: يعني 1 و 0اند. اصل دوگانگي كاربردهاي متعددي دارد. B و عناصر مجموعه
OR و AND اگر دوگان يك عبارت جبري مورد نظر باشد تنها كافي است عملگرهاي
تعويض و 0ها به 1 و 1ها به 0 تبديل گردند.
گيت هاي منطقي، جبر بول و توابع بولي 57
1 تئوري هاي اساسي جبر بول -2 -2 -2
تئوري ها و اصول ليست شده اساسي ترين روابط در جبر بول اند. تئوري ها نيز مانند
اصول به صورت جفت جفت ارائه شده اند و هر رابطه دوگان زوج خود است. اصول،
بديهيات ساختار جبري بوده و اثباتي لازم ندارند. تئوري ها بايد با توجه به اصول ثابت
شوند، اثبات تئوري ها با يك متغير در زير نشان داده شده اند. در سمت مقابل روابط،
شماره اصل به كار رفته نوشته شده است.
x+x=x :(a) تئوري 1
=(x+x).1
x+x
=(x+x)(x+x´)
=x+xx´
=x+0
=x
x.x=x:(b) تئوري 1
=xx+0
x.x
=xx+xx´
=x(x+x´)
=x.1
=x
(b) است و هر مرحله از اثبات در بخش (a) دوگان 1 (b) توجه كنيد كه تئوري 1
مي باشد. به اين ترتيب هر تئوري دوگان از اثبات زوجش حاصل (a) دوگان بخش
مي گردد.
x+1=1 :(a) تئوري 2
=1.(x+1)
x+1
=(x+x´)(x+1)
= x+x´.1
= x+x´
=1
58 مدار منطقي
x.0= بر اساس دوگانگي 0 :( b) تئوري 2
را x كه متمم ، x.x´=0 , x+x´= با توجه به اصل 3 ، داريم 1 . x = (x´)´ : تئوري 3
مي باشد. بنابراين، چون (x´)´ است و در نتيجه همان x برابر x´ تعريف مي كند . متمم
.(x´)´ = x متمم منحصر به فرد است داريم
با استفاده از اصول و تئوري هاي اثبات شده قبلي مي توان تئوري هاي دو يا سه
متغيره را به صورت جبري ثابت كرد. مثلاً: تئوري جذب را در نظر بگيريد.
تئوري 4: شركت پذيري
(a): x + (y + z) = (x + y) + z
(b): x (y z) = (x y) z
: تئوري 5
(a): (x + y)´ = x´ y´
(b): (x y)´ = x´ + y´
= x.1+xy
x+xy
=x(1+y)
=x(y+1)
=x.1
=x
x+xy=x :(a) تئوري 6
x(x+y)=x بر اساس دوگانگي :( b) تئوري 6
2 تقدم عملگرها -2 -2 -2
و چهارم AND سوم با ،NOT در ارزيابي عبارت جبر بول تقدم اول با پرانتز، دوم با
است. به بيان ديگر، عبارت داخل پرانتز بايد قبل از ساير عملگرها ارزيابي شود. OR
قرار دارد. به عنوان OR و بالاخره AND عملگر مقدم بعدي متمم است. پس از آن
مثال، جدول درستي را براي تئوري دمورگان تشكيل مي دهيم سمت چپ عبارت
گيت هاي منطقي، جبر بول و توابع بولي 59
است. بنابراين داخل پرانتز ابتدا ارزيابي مي شود و سپس نتيجه متمم مي گردد. (x+y)´
هر دو ابتدا ارزيابي شده و حاصل y و x است. بنابراين متمم x´y´ سمت راست عبارت
مي گردد. توجه كنيد كه در محاسبات معمولي هم روال مشابهي (به جز براي AND
برقرار است. OR و AND متمم) براي ضرب و جمع به ترتيب به جاي
3 توابع بول -2
جبر بول جبري است كه با متغيرهاي دودويي و عمليات منطقي سروكار دارد. يك تابع
به وسيله يك عبارت جبري متشكل از متغيرهاي دودويي، ثابت هاي 0 يا 1 و سمبل هاي
عملياتي منطقي تشكيل شده است. براي مقدار مفروضي از متغيرهاي دودويي، تابع
مي تواند 1 يا 0 باشد. يك تابع بول رابطه اي منطقي را بين متغيرها بيان مي كند. اين تابع
با تعيين مقدار دودويي عبارت بر حسب همه مقادير ممكن متغيرها ارزيابي مي شود.
يك جدول بولي به صورت يك جدول درستي هم مي تواند نشان داده شود. جدول
درستي ليستي از 1ها و 0 ها است كه به متغيرهاي دودويي تخصيص مي يابد، و ستوني
كه مقدار نتايج را براي هر تركيب نشان مي دهد. تعداد سطر ها در جدول درستي ^ 2 n
تعداد متغيرها در تابع است. تركيبات دودويي براي جدول درستي از n است، كه
2^ - شمارش اعداد دودويي و از 0 تا 1 به n دست مي آيد. يك تابع بول را مي توان از يك
عبارت جبري به يك نمودار مداري متشكل از گيت هاي منطقي تبديل كرد. براي درك
بهتر موضوع دو تابع زير را در نظر بگيريد:
F1 = x + y´ z
F2 = x´ y´ z +x´ y z +x y´
را نشان مي دهد: F و 2 F 6، درستي دو تابع 1 - جدول شكل 2
60 مدار منطقي
x y z F1 F2
0 0 0 0 0
0 0 1 1 1
0 1 0 0 0
0 1 1 0 1
1 0 0 1 1
1 0 1 1 1
1 1 0 1 0
1 1 1 1 0
F و 2 F 6: جدول درستي توابع سه متغيره 1 - شكل 2
z,y,x در اين جدول هشت تركيب دودويي ممكن براي تخصيص بيتي به سه متغير
دارد در ازاء هر تركيب 0 يا 1 است. جدول نشان F وجود دارد. ستوني كه بر چسب 1
برابر 1 است. در غير اين صورت 0 خواهد F باشد تابع 1 yz= يا 1 x= مي دهد كه وقتي 1
در يك جدول درستي تنها يك راه وجود دارد. با اين وجود، وقتي F بود. براي نمايش 1
تابع به فرم يك عبارت جبري است، مي تواند به فرم هاي متفاوتي نشان داده شود.
عبارت خاصي كه براي مشخص كردن تابع مورد استفاده قرار مي گيرد اتصالات ميان
در F گيت ها در نمودار مدار منطقي را ديكته مي نمايد. نمودار مدار منطقي تابع بولي 1
7 نشان داده شده است: - شكل 2
يك y´z استفاده شده است. براي جمله NOT از گيت y براي توليد متمم ورودي
به كار رفته است. در نمودارهاي مدار OR وبراي تركيب آن دو يك گيت AND گيت
x F1
y
z
F1 = x + y´ z 7:پيادهسازي با گيت - شكل 2
گيت هاي منطقي، جبر بول و توابع بولي 61
به عنوان خروجي F منطقي، متغيرها ي تابع به عنوان ورودي مدار و متغير دودويي 1
مدار در نظر گرفته مي شوند.
به كمك x,y كه جدول درستي آن در بالا آمده است، متغيرهاي F در تابع بولي 2
AND به دست آيند. سه جمله در عبارت با سه گيت y´ , x´ وارون گر متمم شده اند تا
منطقي سه جمله را فراهم مي سازد. نمودار مدار OR ، نيز OR پياده سازي شده اند. گيت
8 نشان داده شده است: - در شكل 2 F منطقي تابع بولي 2
1 متمم يك تابع -3 -2
به دست F است و از تعويض 0 ها با 1 و 1ها با 0 در مقدار F´ برابر F متمم يك تابع
مي آيد. متمم يك تابع را مي توان به صورت جبري از تئوري دمورگان نيز به دست آورد.
تئوري هاي دمورگان به سه يا چند متغير هم قابل گسترش اند. با استفاده از اصول و
تئوري هاي ارائه شده، فرم سه متغيره اولين تئوري دمورگان به طريق زير ثابت مي شود.
(A + B + C)´ = (A + x)´ : داريم (B + C = x) با فرض
F2
x
y
z
با گيت F 8: پيادهسازي تابع بول 2 - شكل 2
62 مدار منطقي
(A + B + C)´ = A´x´ دمورگان (a) با تئوري 5
(A + B + C)´ = A´ (B + C)´ را جايگزين كنيد B + C = x
(A + B + C)´ = A´(B´C´) دمورگان (a) با تئوري 5
= A´B´C´ شركت پذيري (b) با تئوري 4
تئوري هاي دمورگان براي هرتعدادي از متغيرها، مشابه حالت دو متغيره بوده و با
روش جايگزيني متوالي، مشابه روشي كه در فوق مشاهده شد، مي توان آن را به دست
آورد. فرم عمومي تئوري دمورگان به صورت زير است:
(A + B + C + D + … + F)´ = A´B´C´D´…F´
(ABCD…F)´= A´ + B´ + C´ + D´ + … + F´
و OR و AND اين تئوري بيان مي دارد كه متمم يك تابع با تعويض عملگرهاي
متمم كردن هر ليترال حاصل مي شود.
را به دست آوريد. F2 = x(y´ z´ + y z) و F1 = x´ y z´ +x´ y´ z مثال 1: متمم توابع
متمم ها را با اعمال هر تعداد تئوري دمورگان به صورت زير به دست آوريد:
F´1 =(x´y z´+ x´y´z)´
=(x´y z´)´(x´y´z)´
=(x + y´+z)(x + y + z´)
F´2 =[x(y´z´+yz)]´
=x´+(y´z´+yz)´
= x´+(y´z´)´(yz)´
=x´+ (y +z)(y´+ z´)
گيت هاي منطقي، جبر بول و توابع بولي 63
روال ساده تري براي به دست آوردن متمم يك تابع اين است كه دوگان تابع و متمم
هر ليترال به دست آيد. اين روش با توجه به فرم عمومي تئوري دمورگان نتيجه مي شود.
و تبديل 1ها و OR به AND به خاطر داشته باشيد كه دوگان يك تابع با تبديل عملگر
0 ها به يكديگر به دست مي آيد.
2 را با استفاده از دوگان ها و متمم هاي هر - مثال 2 F و 2 F مثال 2: متمم توابع 1
ليترال به دست آوريد.
1)F1=x´yz´+x´y´z´
(x´+y+z´)(x´+y´+z´) : برابر است با F دوگان تابع 1
(x+y´+z)(x+y+z´)=F´ متمم هر ليترال برابر است با: 1
2) F2= x(y z´+yz)
x+(y´+z´)(y+z) : برابر است با F دوگان تابع 1
x´+(y+z)(y´+z´) =F´ متمم هر ليترال برابر است با: 2
2 ساير اعمال منطقي -3 -2
قرار مي گيرند، به ترتيب دو تابع y,x بين دو متغير OR و AND وقتي كه عملگرهاي
2^ متغير 2 n را تشكيل مي دهند. قبلاً بيان شد كه براي x+y , x.y بولي ^n
تابع دودويي
و تعداد توابع بولي ممكن 16 است. بنابراين توابع n= وجود دارد. براي دو متغير، 2
تنها دو تابع از 16 تابع ممكن با دو متغير دودويي هستند. جدول درستي OR و AND
تشكيل گرديده در جدول زير ليست شده است. y , x 16 تابع كه با دو متغير دودويي
را نشان y,x جدول درستي يك تابع ممكن براي دو متغير ، F15 , F هر يك از 16 ستون 0
معين F مي دهد. توجه داشته باشيد كه توابع از 16 تركيب ممكن تخصيص يافته به
.(9 - مي گردند. 16 تابع را مي توان با توابع بول نشان داد (شكل 2
64 مدار منطقي
بيان كرد، NOT,OR,AND اگر چه هر تابع را مي توان بر حسب عملگرهاي دودويي
اما دليلي وجود ندارد كه كسي عملگر خاصي را براي بيان ساير توابع تعيين ننمايد.
10 ليست شده اند. با اين وجود همه - چنين عملگرهايي در ستون دوم جدول شكل 2
انحصاري (⊕)كاربرد OR سمبل هاي جديد كه در جدول نشان داده شده اند، بجز
چنداني به وسيله طراحان ندارند.
به دنبال هر يك از توابع در جدول زير، نام و توضيحي كه تابع را به نحوي تشريح
مي كند، آورده شده است. 16 تابع ليست شده فوق به سه گروه زير تقسيم مي شوند.
(Identity , Null) -1 دو تابع كه ثابت هاي 1,0 را توليد مي كنند
9- 10 : عبارات بولي 16 تابع تعريف شده در شكل 2 - شكل 2
توضيحات نام سمبل عملگر توابع بول
F0=0 . Null Binary constant 0
F1=xy x.y AND x and y
F2=xy´ x/y Inhibition x, but not y
F3=x . Transfer x´
F4=x´y y/x Inhibition y , but not x
F5=y . Transfer y
F6=xy´ + x´y x⊕y Exclusive-OR x or y , but not both
F7=x+y x+y OR x or y
F8=(x+y) ´ x↓y NOR Not-OR
F9=xy+x´y´ (x⊕y) ´ Equivalence x equals y
F10=y´ y´ Complement Not y
F11=x+y´ xy Implication If y , then x
F12=x´ x´ Complement Not x
F13=x´+y xy Implication If x , than y
F14=(xy) ´ x↑y NAND Not-AND
F15=1 . Identity Binary constant 1
9: جدول درستي براي 16 تابع از دو متغير دودويي - شكل 2
x y F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
گيت هاي منطقي، جبر بول و توابع بولي 65
-2 چهار تابع يكاني از نوع متمم 1 و انتقال 2
-3 ده تابع باقيمانده شامل هشت عمل مختلف به شرح زير مي باشد:
AND •
OR •
NAND •
NOR •
انحصاري) OR يا ) XOR •
يا هم ارزي) ) XNOR •
• نهي 3
• استلزام (استنباط) 4
ثابت ها براي توابع دودويي فقط مي توانند 0 يا 1 باشند. تابع متمم، متمم هر متغير
دودويي را توليد مي نمايند. تابعي كه براي يك متغير ورودي است را انتقال 5 مي نامند،
از طريق يك گيت بدون تغيير مقدار عبور كرده است. از هشت y يا x زيرا متغير
عملگر دودويي، دوتاي آنها (نهي و استلزام) به وسيله طراحان مدارات منطقي به كار
و AND مي روند، ولي به ندرت در منطق كامپيوتر از آنها استفاده مي شود. عملگرهاي
قبلاً در جبر بول ذكر شدند. چهار تابع ديگر به طور گسترده در طراحي دستگاه هاي OR
ديجيتال مورد استفاده اند.
اخذ شده است. به طور مشابه NOT -OR بوده و نام آن از OR متمم NOR تابع
XOR انحصاري يا OR . مشتق مي شود NOT -AND است و از AND متمم ،NAND
1 _ Complement
2 _ Transfer
3 Inhibition
4 Implication
5 Transfer - Buffer
66 مدار منطقي
متفقا برابر 1 باشند، را شامل y,x است ولي حالتي كه در آن هر دو متغير OR مشابه با
يا هم ارزي تابعي است كه هنگام مساوي بودن دو متغير برابر 1 XNOR نمي شود. تابع
متمم يكديگرند XNOR و XOR مي شود، يعني وقتي هر دو 0 يا هر دو 1 باشند. توابع
9 قابل تشخيص است. جدول درستي - و اين خاصيت بسادگي با ملاحظه جدول شكل 2
است. اين دو تابع متمم يكديگرند. F نيز 9 XNOR و براي F عبارت است از 6 OR براي
نشان مي دهند. XNOR انحصاري هم مي گويند و با NOR به اين دليل تابع هم ارزي را
و يك عملگر يكاني با نام OR , AND جبر بول دو عملگر دودويي با نام هاي
متمم) دارد. ما با توجه به تعاريف، برخي از خواص آنها را استنتاج نموديم و در ) NOT
اين بخش تعدادي از عملگرهاي دودويي ديگر را برحسب آنها معرفي كرديم. اين روال
را تعريف كرده و (↓) NOR منحصر به فرد نيست. به عنوان مثال مي توانستيم ابتدا
را بر حسب آنها تعريف كنيم. به هر حال دلايل مكفي براي NOT , OR , AND سپس
بيشتر بين مردم مصطلح NOT , OR , AND روش منتخب وجود دارد و در واقع مفاهيم
بوده و بر تفكرات حاكم هستند. علاوه بر آن اصول هانتينگتون منعكس كننده طبيعت
دوگاني اين جبر است و اين خود بر خاصيت تقارن (+) و (.) نسبت به يكديگر دلالت
دارد.
4 گيت هاي منطقي ديجيتال -2
بيان شده اند، پياده NOT , OR , AND • چون توابع بول بر حسب عملگرهاي
كردن آنها با استفاده از اينگونه گيت ها ساده تر خواهد بود. امكان ساخت
گيت ها براي ديگر اعمال منطقي در عمل مورد توجه است. فاكتورهايي كه
بايد به هنگام ساخت آنها در نظر گرفته شوند عبارتند از:
• امكان سنجي و اقتصادي بودن روش ساخت به هنگام استفاده از قطعات
فيزيكي
• امكان گسترش ورودي گيت ها به بيش از دو
گيت هاي منطقي، جبر بول و توابع بولي 67
• در نظر گرفتن خواص اصلي عملگرهاي دودويي مثل جابجايي و
شركت پذيري
• توانايي گيت در پياده سازي توابع به تنهايي يا همراه با ساير گيت ها
از شانزده تابع معرفي شده در قسمت قبل، دو تابع برابر با مقدار ثابت و چهار تاي
ديگر دوبار تكرار شده اند. بنابراين تنها ده تابع براي تهيه گيت هاي منطقي كانديد
هستند. دو تابع نهي و استلزام داراي خاصيت جابجايي يا شركت پذيري نيستند و لذا به
عنوان گيت هاي منطقي استاندارد مورد استفاده نمي باشند.
XNOR و XOR ،NOR ،NAND ،OR ،AND ،NOT ،Buffer : هشت تابع ديگر يعني
به عنوان گيت هاي استاندارد در طراحي سيستم هاي ديجيتال به كار مي روند.
11 نشان داده - سمبل هاي گرافيكي و جدول درستي هشت گيت فوق در شكل 2
و يك متغير y,x شده اند. هر گيت موجود در شكل، داراي دو متغير ورودي دودويي
از قبل تعريف شده بودند. NOR,OR,AND مي باشد. مدارهاي F خروجي دودويي
يا وارون گر وضعيت منطقي يك متغير دودويي را معكوس مي نمايد و در NOT مدار
واقع متمم متغير را توليد مي كند. دايره كوچك در خروجي سمبل گرافيكي يك
وارون گر (كه به آن حباب مي گويند) بيانگر متمم شدن است.
سمبل مثبت به تنهايي علامت بافر مي باشد. يك بافر عمل انتقال را انجام مي دهد،
ولي يك عمل منطقي توليد نمي كند زيرا مقدار دودويي خروجي برابر مقدار ورودي
دودويي است. اين مدار صرفاً در تقويت توان سيگنال ها استفاده شده و معادل با دو
مدار متوالي وارون گر (معكوس گر) است.
است و همانطور كه از سمبل گرافيكي آن مشخص است از AND متمم NAND تابع
و يك حباب تشكيل شده است. AND يك سمبل
68 مدار منطقي
11 : گيت هاي منطقي به همراه مشخصات و جدول درستي - شكل 2
و به دنبال آن يك حباب نمايش OR است و با يك سمبل OR هم متمم NOR تابع
داده مي شود.
جدول درستي تابع جبري سمبل گرافيكي نام
x y F
0 0 0
0 1 0
1 0 0
1 1 1
F=XY
AND
x y F
0 0 0
0 1 1
1 0 1
1 1 1
F=x+y
OR
x F
0 1
1 0
F = x´
Inverter
x F
0 0
1 1
F=x
Buffer
x y F
0 0 1
0 1 1
1 0 1
1 1 0
F=(xy) ´
NAND
x y F
0 0 1
0 1 0
1 0 0
1 1 0
F= (x+y) ´
NOR
x y F
0 0 0
0 1 1
1 0 1
1 1 0
F= xy´ + x´y = x⊕y
Exclusive-OR
(XOR)
x y F
0 0 1
0 1 0
1 0 0
1 1 1
F=xy+ x´y´= (x⊕y) ´
Exclusive-NOR or
equivalence
گيت هاي منطقي، جبر بول و توابع بولي 69
به طور گسترده اي به عنوان گيت هاي استاندارد مورد NOR و NAND گيت هاي
مورد توجه اند. اين بدان علت است كه AND و OR استفاده قرار گرفته و بيشتر
به سادگي به وسيله مدارات ترانزيستوري قابل توليد بوده و NOR و NAND گيت هاي
مي توان به راحتي توابع بول را با آنها پياده سازي كرد.
است، بجز اينكه يك خط منحني در سمت OR داراي سمبل مشابهي با NOR گيت
است و لذا حباب كوچكي در XOR متمم XNOR ورودي اش كشيده شده است. گيت
خروجي آن وجود دارد.
1 گسترش ورودي گيت ها -4 -2
11 نشان داده شدند، بجز براي وارون گر و انتقال، قابل - گيت هايي كه در شكل 2
گسترش به بيش از دو ورودي مي باشند. اگر عمل دودويي يك گيت جابجا و
كه در OR و AND شركت پذير باشد، مي توان ورودي هاي آن را گسترش داد. اعمال
OR جبر بول تعريف شده اند اين خاصيت را از خود به نمايش گذاشته اند. براي تابع
داريم:
x + y = y + x ( (جابجايي
و
(x+y) + z = x + (y + z) = x + y + z ( (شركت پذير
اين روابط بيانگر تعويض پذيري ورودي هاي گيت و قابل گسترش بودن متغيرهاي
است. OR ورودي به بيش از دو در تابع
NOR و NAND توابع
جابجا پذيرند و ورودي آنها مي تواند به بيش از دو افزايش NOR و NAND توابع
يابد، مشروط بر اين كه در تعريف تابع مختصر تغييري صورت گيرد. مشكل اين است
شركت پذير نيستند. يعني: NOR و NAND كه
70 مدار منطقي
[(x↓y)↓z ≠ x(y↓z) ]
12 و معادلات زير مشاهده مي گردد: - اين نكته در شكل 2
( x↓y)↓z = [ (x + y)´+ z ]´ = (x + y)z´= xz´+ yz´
x ↓(y↓ z) = [ x + (y + z)´]´= x´(y + z) = x´y+ x´z
چند ورودي را به عنوان متمم (NAND يا ) NOR براي غلبه بر اين مشكل، گيت
آن تعريف مي كنيم. بنابراين: (AND يا ) OR
x↓y↓z = (x+y+z)´
x↑y↑z = (xyz)´
13 نشان داده شده اند. در - سمبل هاي گرافيكي گيت هاي سه ورودي در شكل 2
بايد پرانتزها به فرم صحيحي انتخاب شوند تا بيانگر NAND,NOR نوشتن متوالي اعمال
ترتيب صحيح گيت ها باشند.
(x ↓ y) ↓ z = (x + y) z´
x ↓ (y ↓ z) = x´ (y + z)
x
x
y
y
z
z
(x↓y)↓ z≠ x↓(y↓ z) - NOR 12 شركتناپذيري عملگر - شكل 2
x
y
z
(x+y+z) ´
(xyz) ´
y
x
z
گيت هاي منطقي، جبر بول و توابع بولي 71
XNOR و XOR گيت هاي
هر دو خواص جابجايي و شركت پذيري را دارند و ورودي هايشان XNOR و XOR
چند ورودي از نقطه XOR قابل توسعه به بيش از دو مي باشد. با اين وجود گيت هاي
نظر سخت افزاري متداول نيستند. در واقع حتي فرم دو ورودي آن نيز معمولاً از ساير
گيت ها ساخته مي شود. علاوه بر اين، تعريف اين توابع بايد به هنگام گسترش
يك تابع فرد است يعني هرگاه ورودي ها تعداد XOR ورودي ها تصحيح گردد. تابع
XOR فردي 1 داشته باشند، اين تابع (خروجي) برابر 1 خواهد بود. ساختمان يك گيت
13 ديده مي شود. - با سه ورودي در شكل 2
13 (الف). به صورت - اين مدار معمولاً با گيت هاي دو ورودي تهيه مي شود، شكل 2
13 (ب). جدول - گرافيكي، آن را مي توان با يك گيت سه ورودي نشان داد، شكل 2
برابر 1 است به شرطي كه فقط F درستي (پ) آشكارا مشخص مي نمايد كه خروجي
يكي از ورودي ها و يا هر سه ورودي برابر 1، باشند ؛ يعني وقتي تعداد كل 1ها در
متغيرهاي ورودي فرد است، تابع 1 است.
x
y
z
z⊕ y ⊕F = x
y
z
x
z⊕ y ⊕F = x
(الف) با گيتهاي دوورودي
(ب) با گيت سه ورودي
(پ) جدول درستي
XOR 13 : گيت - شكل 2
x y z F
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
72 مدار منطقي
2 مدارهاي مجتمع -4 -2
با گسترش علم الكترونيك و طراحي مدارات تركيبي و پيچيده نياز به طراحي بسته هاي
يك (IC) يكپارچه و كوچكتر از مدارها بيش از پيش احساس مي شد. يك مدار مجتمع
كريستال نيمه هادي از جنس سيليكان است كه به آن تراشه مي گويند و حاوي اجزاء
الكترونيكي در ساخت گيت هاي ديجيتال مي باشد و انواع گيت ها در داخل تراشه به هم
وصل مي شوند تا مدار مورد نياز ايجاد گردد. تراشه روي يك محفظه سراميك يا
پلاستيك نصب شده و اتصالات به پايه هاي بيرون براي ايجاد مدار مجتمع، متصل
مي گردند. تعدادپايه ها ممكن است گاه چند هزار در يك بسته بزرگ برسد. در روي هر
يك شماره براي شناسايي چاپ مي شود. IC
1 سطوح مجتمع سازي -2 -4 -2
هاي ديجيتال اغلب بر اساس پيچيدگي مدار دروني شان كه به تعداد گيت هاي IC
منطقي مرتبط است دسته بندي مي شوند. تفكيك تراشه هايي كه تنها چند يا چند صد و
يا چندين هزار گيت دارند با ارجاع به بسته و دسته بندي آنها به وسايل مجتمع با
فشردگي كم،متوسط، زياد و خيلي زياد صورت مي گيرد.
داراي چند گيت مستقل در بسته اند. (SSI) مدارهاي مجتمع با فشردگي كم
ورودي ها خروجي هاي گيت ها مستقيماً به پايه هاي بسته متصل مي شوند. تعداد گيت ها
محدود مي گردند. IC معمولاً كمتر از 10 بوده و به وسيله پايه هاي موجود در
داراي فشردگي بين 10 تا 1000 (MSI) مدارهاي مجتمع با فشردگي متوسط
گيت در يك بسته دارند. اين دسته از مدارات معمولاً اعمال ديجيتال خاصي را اجرا
با عناوين ديكدر ها، جمع كننده ها و مولتي پلكسرها در MSI مي كنند. توابع ديجيتال
فصل 4 و ثبات ها و شمارنده ها در فصل 6 مطرح شده اند.
گيت هاي منطقي، جبر بول و توابع بولي 73
حاوي هزاران گيت در يك بسته (LSI) مدارهاي مجتمع با فشردگي زياد
مي باشند. اين دسته از مدارات، پردازنده ها، حافظه ها و مدارات منطقي برنامه پذير را
در فصل 8 معرفي شده اند. LSI شامل مي شوند. بعضي از اجزا
صدها هزار گيت در يك بسته (VLSI) مدارهاي مجتمع با فشردگي خيلي زياد
دارند. از جمله مثالها مي توان از آرايه هاي حافظه، تراشه ميكرو كامپيوتر هاي پيچيده
تكنولوژي طراحي سيستم كامپيوتر را VLSI نام برد. به دليل كوچكي و ارزاني، وسايل
متحول ساخته و به طراح قابليت ساخت وسايلي را مي دهد كه قبلاً اقتصادي نبودند.
2 منطق مثبت و منفي -2 -4 -2
سيگنال دودويي در ورودي ها يا خروجي هر گيت، بجز در حالت گذرا، يكي از دو
مقدار را دارد. يك مقدار سيگنال، منطق 1 و ديگري منطق 0 را نمايش مي دهد. چون
دو مقدار سيگنال متعلق به دو ارزش منطقي است، لذا دو انتساب متفاوت براي دو
و سطح سيگنال H 14 سطح سيگنال بالاتر با - ارزش منطقي مي توان اختيار كرد، شكل 2
مقدار سيگنال مقدار منطقي مقدار سيگنال مقدار منطقي
0 H 1 H
1 L 0 L
(الف) منطق مثبت (ب) منطق منفي
14 : تخصيص سيگنال و قطبيت منطق - شكل 2
براي منطق 1 به كار رود يك ،H ، مشخص شده است. اگر سطح بالا L پايين تر با
براي منطق 1 سيستم منطقي منفي را L سيستم منطق مثبت تعريف شده است. انتخاب
معرفي مي نمايد.
كلمات مثبت يا منفي گاهي گمراه كننده هستند زيرا هر دو سيگنال ممكن است
مثبت يا منفي باشند. در واقع، اين قطب هاي سيگنال نيستند كه بيانگر نوع منطق
74 مدار منطقي
مي باشند، بلكه انتخاب مقادير منطقي بر حسب سطوح نسبي سيگنال ها نسبت به هم،
نوع منطق را مشخص مي كنند.
تعريف مي شوند. از L , H گيت هاي ديجيتال سخت افزاري بر حسب مقادير سيگنال
اين پس انتخاب منطق مثبت و منفي به عهده كاربر است. به عنوان مثال گيت
الكترونيك شكل زير را به همراه جدول درستي آن در نظر بگيريد:
برابر 0 ولت است نشان L 3 و V برابر H اين جدول رفتار فيزيكي گيت را وقتي
L= و 0 H= 15 جدول درستي منطق مثبت را فرض مي كند كه در آن 1 - مي دهد. شكل 2
با منطق مثبت در شكل زير ديده AND است. اين جدول درستي همانند جدول عمل
مي شود.
در نظر H= و 0 L= اكنون تخصيص منطق منفي را براي همان گيت فيزيكي با 1
بگيريد. نتيجه جدول درستي شكل زير خواهد بود. گرچه داده ها معكوس شده اند ولي
گيت
ديجيتال
x
y
z
نمودار بلوكي گيت
x y z
L L L
L H L
H L L
H H H
H و L جدول درستي با
x
y
z
با منطق مثبت AND گيت
x y z
0 0 0
0 1 0
1 0 0
1 1 1
جدول درستي منطق مثبت
با منطق مثبت AND 15 : نمايش جدول درستي گيت - شكل 2
گيت هاي منطقي، جبر بول و توابع بولي 75
با منطق منفي در OR را نشان مي دهد. سمبل گرافيكي گيت OR جدول عمل
16 ديده مي شود. - شكل 2
مثلث هاي كوچك در ورودي ها و خروجي نشانگر قطبيت هستند. وجود علائم
قطبيت همراه با مشخصات پايانه بيانگر فرض منطق منفي براي سيگنال است. بنابراين
با منطق OR با منطق مثبت و نيز يك گيت AND گيت فيزيكي فوق مي تواند يك گيت
منفي باشد. تبديل منطق مثبت به منفي و بالعكس، عملي است كه طي آن در ورودي و
خروجي يك گيت 0 ها به 1 و 1ها به 0 تبديل مي شوند. چون اين عمل دوگان تابع را
توليد مي كند، تعويض پايانه ها از يك قطبيت به قطبيت ديگر نتيجه اش همان يافتن
دوگان تابع است.
و بالعكس تبديل شوند. OR به AND نتيجه اين تبديل اين است كه همه عملگرهاي
به علاوه نبايد از ذكر مثلث در سمبل هاي گرافيكي كه بيانگر قطبيت است در منطق
منفي، فراموش كرد. در اين كتاب از گيت ها با منطق منفي استفاده نمي كنيم و فرض
خواهيم كه همه گيت ها با منطق مثبت كار كنند.
3 خانواده هاي منطقي ديجيتال -2 -4 -2
جدا از بحث پيچيدگي و عمل منطقي مدارهاي مجتمع ديجيتال كه باعث دسته بندي
آنها نيز مي گردد، اين مدارات بر اساس تكنولوژي مدار خاصي كه به آن تعلق دارند نيز
دسته بندي مي گردند. تكنولوژي مدار به نام خانواده مدار منطقي خوانده مي شود. هر
z
با منطق منفي OR گيت
x y z
1 1 1
1 0 1
0 1 1
0 0 0
با منطق منفي OR 16 : نمايش جدول درستي گيت - شكل 2
y
x
76 مدار منطقي
خانواده منطقي داراي مدار الكترونيك مبناي خاص خود بوده و ساير توابع و مدارات
پيچيده ديجيتال با استفاده از آنها ساخته مي شوند. مدار مبنا در هر خانواده، گيت
است. قطعات الكترونيك به كار رفته در ساخت مدار مبنا معمولاً NOT يا NOR ،NAND
براي نام گذاري تكنولوژي مورد استفاده قرار مي گيرد. به لحاظ تجاري انواع متفاوتي از
خانواده هاي منطقي مدارات مجتمع معرفي شده اند. انواع رايج آنها در زير ليست
شده اند.
emitter-coupled logic ECL
transistor-transistor logic TTL
metal-oxide semiconductor MOS
complementary metal- oxide semiconductor CMOS
در سيستم هايي كه به سرعت بالا نياز دارد ارجحيت دارد. :ECL
مدت مديدي است كه مورد استفاده بوده و به عنوان يك گيت استاندارد :TTL
شناخته شده است.
در مدارهايي كه نياز به چگالي قطعه بالايي دارند مورد استفاده است. :MOS
در مواقعي كه توان مصرفي بايد كم باشد مورد توجه مي باشد. :CMOS
تبديل به CMOS ، از اصول است VLSI نظر به اينكه توان مصرفي كم در طراحي
به ECL,TTL يك خانواده منطقي غالب شده است در حالي كه از كاربرد خانواده هاي
تدريج كاسته مي شود.
گيت هاي منطقي، جبر بول و توابع بولي 77
گيت هاي منطقي، جبر بول و توابع بولي
هدف كلي
در اين فصل مباحث كلي مربوط به منطق دودويي به همراه مفاهيم اساسي جبر بول
مورد بحث و بررسي قرار خواهند گرفت. در ادامه مفاهيم و تئوري هاي اساسي جبر
بول بررسي شده و در ادامه توابع بول نيز به صورت كامل مورد نقد و بررسي قرار
خواهند گرفت. در ادامه نيز انواع گيت هاي منطقي به همراه جداول درستي هر يك
بررسي خواهند شد.
هدف ساختاري
در اين فصل عناوين زير مورد بحث و بررسي قرار مي گيرند:
• منطق دودويي
• انواع گيت هاي منطقي
• اصول اساسي جبر بول
• تئوري هاي اساسي جبر بول
• تقدم عمل گرها در جبر بول
• توابع بول
• متمم توابع بول
• مدارهاي مجتمع
44 مدار منطقي
1 منطق دودويي -2
منطق دودويي با متغيرهايي كه دو ارزش گسسته و عملياتي كه مفهوم منطقي دارند،
سرو كار دارد و ارزشي كه متغيرها اختيار مي كنند ممكن است با اسامي مختلفي
نام گذاري شوند (مثل صحيح و غلط، بله و خير و غيره)، اما براي ما بهتر است آن را بر
حسب بيت تصور كنيم و مقادير 1 و 0 را به آن تخصيص دهيم. منطق دودويي معرفي
شده در اين بخش معادل با جبري به نام جبر بول است. در اين بخش جبر بول به
روشي غير مستدل بوده و ارتباط آن با مدارهاي منطقي ديجيتال و سيگنال هاي دودويي
بيان شده است.
1 تعريف منطق دودويي -1 -2
منطق دودويي شامل متغيرهاي دودويي و عمليات منطقي است. متغيرها با حروف
و غيره نام گذاري مي شوند، كه هر متغير فقط و فقط دو Z ،Y ،X ،C ،B ،A الفبايي مانند
و OR ،AND : مقدار مجزاي 0 و 1 دارد. سه نوع عمليات منطقي اصلي وجود دارند
در ادامه به شرح هر يك از عمليات مي پردازيم: .NOT
اين عمل به وسيله يك "."يا بدون ذكر هر عملگري نمايش داده مي شود. :AND -1
." z برابر است با x AND y " را چنين مي خوانيم x y = z يا x.y = z مثلاً
y= و 1 x= است اگر و فقط اگر 1 z= چنين تفسير مي شود كه، 1 AND عمل منطقي
متغيرهاي z و y و x است. (به ياد داشته باشيد كه z= باشد؛ در غير اين صورت 0
دودويي هستند و نمي توانند به جز 1 و 0 چيز ديگري باشند.)
را چنين x+y=z عملي است كه با علامت بعلاوه نشان داده مي شود. مثلاً :OR -2
است به شرطي كه z= و به اين معني است كه 1 " z برابر است با x OR y " مي خوانيم
z= باشد آنگاه 0 y= و 0 x= باشند. اگر هر دو 0 y= و 1 x= و يا هر دو 1 y= و 1 x=1
خواهد بود.
گيت هاي منطقي، جبر بول و توابع بولي 45
اين علامت با يك علامت پريم نشان داده مي شود (و گاهي با يك خط :NOT -3
و به اين " z برابر است با NOT x " ، و چنين خوانده مي شود (x=z يا ) x´=z بار). مثلاً
اما ؛ z= باشد آنگاه 0 x= نيست. به بيان ديگر اگر 1 x چيزي است كه z معني است كه
را متمم هم مي گويند چون 1 را به 0 و 0 را NOT است. عمل z= باشد، آنگاه 1 x= اگر 0
به 1 تبديل مي كند.
به ترتيب به اعمال OR و AND منطق دودويي شبيه حساب دودويي است، و اعمال
همان OR و AND ضرب و جمع شباهت دارند. در حقيقت سمبل هاي به كار رفته براي
هايي هستند كه براي ضرب و جمع مورد استفاده قرار مي گيرند. معهذا منطق دودويي
را نبايد با حساب دودويي اشتباه كرد. مسئله اي كه بايد مورد توجه قرار گيرد اين است
كه يك متغير حسابي، عددي را مشخص مي كند كه ممكن است داراي چندين رقم
باشد. يك متغير منطقي هميشه 0 و يا 1 است.
1 (مي خوانيم: "يك بعلاوه يك برابر است با +10= مثلاً در حساب دودويي داريم 1
يك، برابر OR 1 (مي خوانيم: "يك + 1 = 2")، در صورتيكه در منطق دودويي، داريم 1
.(" است با 1
AND OR
x y x. y x y x + y
0 0 0 0 0 0
0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1
NOT
x x'
0 1
1 0
1: جدول درستي عمليات منطقي - شكل 2
46 مدار منطقي
وجود دارد كه اين مقدار پس z مقدار معيني براي ،y و x براي هر تركيبي از مقادير
از اعمال يا تعريف عمل منطقي مشخص مي گردد. اين تعاريف را مي توان به صورت
خلاصه يا استفاده از جدول درستي فهرست كرد. يك جدول درستي، جدولي است
متشكل از تمام تركيبات ممكن متغيرها و بيانگر ارتباط بين مقادير آنها و نتايج حاصل
از عمل مربوطه روي آنها مي باشد. به عنوان مثال جداول درستي براي عملگرهاي
با ليست كردن همه مقادير ممكن آنها وقتي به ، y و x با متغيرها ي OR و AND
صورت زوج تركيب شده اند، حاصل مي شود. نتيجه عمل براي هر تركيب به طور
در جدول زير نشان داده NOT و OR و AND جداگانه آمده است. جداول درستي
شده اند. اين جداول تعريف عمليات مذكور را به طور شفاف بيان مي دارند.
2 گيت هاي منطقي -1 -2
گيت هاي منطقي، مدارهايي الكترونيك هستند كه روي يك يا چند سيگنال ورودي
عمل مي كنند تا يك سيگنال خروجي توليد نمايند. سيگنال هاي الكترونيكي مانند
ولتاژها يا جريانهايي كه در سرتاسر يك سيستم ديجيتال وجود دارند دو مقدار جدا از
هم را اختيار مي كنند. مدارهايي كه با ولتاژ كار مي كنند به دو سطح ولتاژ كه نمايشگر
2
3
1
4
0
ولت
انحراف مجاز براي
منطق 1
انحراف مجاز براي
منطق 0
انتقال در محدوده اين
دو ناحيه رخ مي دهد
2: محدوده انتقال سيگنال 0 و 1 - شكل 2
گيت هاي منطقي، جبر بول و توابع بولي 47
يك متغير دودويي و برابر با منطق 1 و منطق 0 اند واكنش نشان مي دهند. مثلاً يك
سيستم ديجيتال خاص ممكن است منطق 0 را به عنوان سيگنالي برابر با 0 ولت و منطق
1 را به صورت سيگنالي برابر با 4 ولت تعريف كند. در عمل، هر سطح ولتاژ، محدوده
2 را داراست. - مورد قبولي مانند شكل 2
پايانه هاي ورودي مدارهاي ديجيتال سيگنال هاي دودويي را در محدوده مجازي
مي پذيرند و در پايانه هاي خروجي در محدوده مجازي پاسخ مي دهند. ناحيه مياني بين
دو ناحيه مجاز تنها هنگام گذر از يك حالت به حالت ديگر قطع مي شود. هر اطلاعات
محاسباتي يا كنترلي مورد نظر را مي توان با عبور سيگنال هايي دودويي از ميان تركيباتي
از گيت ها مورد استفاده قرار داد، كه هر سيگنال بيانگر يك متغير دودويي بوده و يك
بيت از اطلاعات را حمل مي كند.
3 ديده مي شوند: - سمبل هاي گرافيكي مورد استفاده براي سه نوع گيت در شكل 2
گيت ها، بلوكهايي سخت افزاري اند كه با ورودي منطقي مناسبي، در خروجي خود 0
در يكي از چهار OR و AND در گيت هاي y و x يا 1 توليد مي نمايند. سيگنال ورودي
x x' NOT گيت
AND گيت
x
y
z = x. y
x
y
z = x + y
OR گيت
3: سمبلهاي مداري منطقي ديجيتال - شكل 2
48 مدار منطقي
10 و 11 . اين سيگنال ها همراه با خروجي خود در ،01 ، حالت ممكن قرار دارند: 00
4 ديده مي شوند. نمودارهاي زماني پاسخ هر گيت را براي چهار گيت فوق - شكل 2
نشان مي دهند. محور افقي نمودار زمان، و محور عمودي سيگنال ها را ضمن تغيير بين
دو سطح ولتاژ ممكن نمايش مي دهد. سطح پايين منطق 0 و سطح بالا منطق 1 را نشان
منطق 1 وجود دارد كه هر دو سيگنال ورودي AND مي دهد. هنگامي در خروجي گيت
هنگامي خروجي 1 دارد كه يكي از سيگنال هاي ورودي در OR در منطق 1 باشند. گيت
را معمولاً وارون گر يا معكوس گر هم مي گويند. دليل انتخاب NOT منطق 1 باشد. گيت
اين نام با توجه به پاسخ سيگنال در نمودار زماني مشخص است، و در آن نشان داده
شده است كه سيگنال خروجي مفهوم منطق ورودي را معكوس كرده است.
با چهار ورودي OR با سه ورودي ب- گيت AND الف- گيت
5: مدار سوئيچينگ نمايش دهنده منطق دودويي - شكل 2
F = ABC AB
C
F = A+B+C+D
A
B
C
D
X 0 1 1 0 0
Y 0 0 1 1 0
AND : x . y 0 0 1 0 0
OR : x + y 0 1 1 1 0
NOT : x´ 1 0 0 1 1
AND , OR ,NOT 4: سيگنال هاي ورودي- خروجي براي گيت هاي - شكل 2
گيت هاي منطقي، جبر بول و توابع بولي 49
AND ممكن است بيش از دو ورودي داشته باشند. يك گيت OR و AND گيت هاي
سه AND 5 ملاحظه مي شود. گيت - با چهار ورودي در شكل 2 OR با سه ورودي و يك
ورودي به شرطي خروجي 1 دارد كه هر سه ورودي آن 1 باشد. اگر هر يك از
چهار ورودي OR برابر 0 خواهد بود. گيت AND ورودي ها 0 باشند، خروجي
هنگامي خروجي 1 توليد مي كند كه يكي از ورودي ها در 1 منطقي باشد. خروجي
هنگامي 0 مي شود كه همه ورودي ها در منطق 0 باشند.
-2 جبر بول -2
جبر بول را مي توان مانند هر سيستم منتجه رياضي، به وسيله مجموعه اي از عناصر، يك
مجموعه از الگوها و تعدادي اصول اثبات نشده يا بديهيات تعريف نمود. يك مجموعه
يك s از عناصر كلكسيوني از اشياء است كه داراي خواص مشتركي باشند. اگر
x به اين معني است كه x ∈ s عناصر مشخصي از آن باشند، آنگاه y و x مجموعه و
نيست. يك مجموعه s عضوي از مجموعه y يعني y ∉ s است و s عضوي از مجموعه
A = { با تعداد قابل شمارشي از عناصر با يك جفت آكولاد مشخص مي شود: { 1,2,3,4
عبارتند از 4,3,2,1 . يك عملگر دودويي روي يك مجموعه A يعني عناصر مجموعه
S يك عنصر منحصر به فرد از ،S قانوني است كه به هر جفت از عناصر ،S ، از عناصر
را در نظر بگيريد. (*) را يك عملگر a ∗b= c را تخصيص دهد. به عنوان مثال رابطه
منتسب نمايد b وa را به جفت عنصر c دودويي مي خوانيم به شرطي كه بتواند عنصر
c∉S و a,b∈S معتبر باشد. با اين وجود اگر a,b,c∈S ضمن اينكه رابطه
باشد، (*) يك عملگر دودويي نيست.
اصول يك سيستم رياضي، فرضيات اوليه را تشكيل مي دهند كه با استفاده از آنها
مي توان قوانين و تئوري ها و خواص سيستم را نتيجه گرفت. مهمترين اصول به كار رفته
در فرموله كردن ساختارهاي جبري عبارتند از:
1. بسته بودن
50 مدار منطقي
2. عنصر شناسه
3. عنصر معكوس
4. اصل شركت پذيري
5. اصل جابجايي
6. اصل توزيع پذيري
نسبت به عملگر دودويي بسته است به شرطي كه s -1 بسته بودن: يك مجموعه
اين عملگر عنصر منحصر به فردي از آن را به جفت عنصر ،s براي هر جفت عنصر از
را نسبت به N = {1,2,3,4,K} منتسب نمايد. به عنوان مثال، مجموعه اعداد طبيعي
عنصر ديگري a,b∈N عملگر جمع (+) بسته گوييم زيرا براي هر دو عنصر
باشد. مجموعه اعداد طبيعي نسبت به a + b = c مي توان يافت بطوري كه c∈N مانند
−1∉N 2,3 و ∈N 2 در حالي كه − 3 = − عملگر تفريق بسته نيست چون داريم 1
است.
داراي عنصر S نسبت به عملگر (*) روي مجموعه S -2 عنصر شناسه: مجموعه
با خاصيت زير موجود باشد. e ∈ S شناسه است، اگر عنصر
e *x = x*e = x: داشته باشيم x∈ S به ازاي هر
يك عنصر شناسه نسبت به عملگر (+) روي مجموعه اعداد صحيح o مثال: عنصر
است، چون I={…,—3,—2,—1,0,1,2,3,…}
x + 0 = 0 + x = x : داشته باشيم x∈ I به ازاي هر
داراي عنصر شناسه نيست زيرا 0 جزو مجموعه نمي باشد. N مجموعه اعداد طبيعي
گيت هاي منطقي، جبر بول و توابع بولي 51
نسبت به عملگر (*) e با عنصر شناسه S -3 عنصر معكوس: مجموعه اي چون
وجود داشته باشد به y∈S يك ، x∈ S داراي معكوس است به شرطي كه براي هر
نحوي كه:
x * y = e
است چون ( - a) برابر a معكوس عنصر ،e = با 0 ،I مثال: در مجموعه اعداد صحيح
a + ( - a) = 0
شركت پذير S -4 اصل شركت پذيري: يك عملكرد دودويي (*) روي مجموعه
است اگر داشته باشيم:
(x*y) * z =x* (y*z) : داشته باشيم x,y ,z∈ S به ازاي همه مقادير
-5 اصل جابجايي: يك عملگر (*) روي مجموعه داراي خاصيت جابجايي است
هرگاه:
x*y = y*x : داشته باشيم y,x ∈ S به ازاي هر
باشند، (*) را S -6 اصل توزيع پذيري: اگر (*) و (.) دو عملگر روي مجموعه
روي (.) توزيع پذير گوييم هرگاه:
x ∗ ( y.z) = (x ∗ y).(x ∗ z)
مثالي جبري در اين مورد ميدان يا حوزه است. ميدان مجموعه اي از عناصر است،
همراه با دو عملگر دودويي، كه هر يك داراي خواص 1 تا 5 بوده و هر دو عملگر
براي تشكيل خاصيت 6 با يكديگر تركيب مي شوند. مجموعه اعداد حقيقي، همراه با
عملگرهاي دودويي (+) و (.)، ميدان اعداد حقيقي را تشكيل مي دهند. ميدان اعداد
حقيقي مبناي جبر معمولي و حساب است. عملگرها و اصول داراي مفاهيم زير هستند:
عملگر دودويي (+) جمع را تعريف مي كند.
معكوس جمع، تفريق مي باشد..
52 مدار منطقي
شناسه جمع، 0 است
شناسه ضرب 1 مي باشد.
عملگر دودويي (.) ضرب را تعريف مي نمايد.
تقسيم را تعريف مي كند، يعني a = 1/a معكوس ضرب
a.(1/a) = 1
تنها اصل توزيع پذيري قابل اعمال مربوط به عملگر (.) روي (+) است:
a. (b + c) = (a. b) + (a. c)
1 تعريف اصول اساسي جبر بول -2 -2
در سال 1854 جورج بول يك سيستم جبري را كه امروزه آن را جبر بول مي ناميم
پايه ريزي كرد. در سال 1938 نيز شانون يك جبر بول دو مقداري به نام جبر
سوئيچينگ را معرفي كرد كه در آن خواص مدارهاي سوئيچينگ با اين جبر قابل ارائه
است. براي تعريف مستدل جبر بول، ما اصول فرموله شده به وسيله هانتينگتون در سال
1904 را به كار مي بريم. اصول هانتيگتون به شرح زير بودند:
مجموعه نسبت به عملگر (+) بسته باشد. (a) -1
مجموعه نسبت به عملگر (.) بسته باشد. (b)
يك عنصر شناسه 0 براي (+) وجود داشته باشد. (a) -2
يك عنصر شناسه 1 براي (.) وجود داشته باشد. (b)
مي گوييم) x وجود دارد (به آن متمم x´∈ B عنصري مثل ،x∈ B -3 براي هر عنصر
x´. x = (b) و x´+x= I (a) : به نحوي كه
باشد. x≠ y وجود دارد به نحوي كه x,y∈ B -4 حداقل دو عنصر
x + y = y + x : مجموعه نسبت به (+) داراي خاصيت جابجايي باشد (a) -5
گيت هاي منطقي، جبر بول و توابع بولي 53
x. y = y. x : مجموعه نسبت به (.) داراي خاصيت جابجايي باشد (b)
x. (y+z) = (x.y) + (x.z) : نسبت به (+) توزيع پذير است (.) (a) -6
x+ (y.z) = (x+y) + (x+y) : نسبت به (.) توزيع پذير است (+) (b)
همراه با دو ،B جبر بول يك ساختار جبري است كه با عناصر مجموعه، يعني
عملگر دودويي (+) و (.) تعريف مي شود به شرطي كه اصول زير (هانتينگتون) در آن
معتبر باشد. به بياني ديگر به منظور داشتن يك جبر بول بايد:
مشخص باشند. B -1 عناصر مجموعه
-2 قوانين عمل دو عملگر دودويي معين باشند.
همراه با دو عملگر، براي شش اصل هانتينگتون معتبر باشد. ،B ، -3 مجموعه عناصر
1 تفاوت هاي جبر بول با جبر معمولي -1 -2 -2
با مقايسه جبر بول با حساب و جبر معمولي (حوزه يا ميدان اعداد حقيقي) تفاوت هاي
زير قابل ملاحظه اند:
-1 اصول هانتينگتون فاقد اصل شركت پذيري است. با اين وجود، اين اصول براي
جبر بول معتبر و براي هر دو عملگر از ديگر اصول قابل استنتاج است.
براي جبر بول ، x+(y.z) = (x+y). (x+z) -2 اصل توزيع پذيري (+) روي (.)، يعني
معتبر است، ولي در جبر معمولي قابل قبول نيست.
-3 جبر بول داراي معكوس هاي جمع و ضرب نيست؛ بنابراين عملگرهاي تفريق و
تقسيم وجود ندارند.
-4 اصل 3 عملگري به نام متمم را معرفي مي نمايد كه در جبر معمولي وجود
ندارد.
54 مدار منطقي
-5 جبر معمولي در مورد اعداد حقيقي بحث مي كند، كه يك مجموعه با بي نهايت
بحث مي نمايد كه ،B ، عنصر را شامل مي شود. جبر بول در مورد مجموعه اي از عناصر
هنوز آن را معرفي نكرده ايم، ولي بعداً در جبر بول دو مقداري يا دو ارزشي معرفي
به صورت B خواهد شد (كاربرد بعدي ما از اين جبر مورد توجه است)، و در آن
مجموعه اي از دو عنصر 0 و 1 تعريف مي شود.
لازم است تا اختلاف بين يك مجموعه از عناصر متعلق به يك ساختار جبري و
متغيرهاي يك سيستم جبري را بدانيم. مثلاً اجزاء حوزه اعداد حقيقي، اعداد هستند، در
كه در جبر معمولي به كار مي روند، سمبل هايي c و b ،a صورتي كه متغيرهايي مانند
B هستند كه به جاي اعداد حقيقي به كار مي روند. به طور مشابه در جبر بول مجموعه
مي باشد كه صرفاً سمبل هستند و عناصر را نشان z و y ،x داراي متغيرهايي مانند
مي دهند.
و قوانين عمليات، مي توان چندين جبر بول را فرموله B بسته به انتخاب عناصر
كرد. در ادامه كار ما فقط با جبر دو ارزشي كه تنها دو عنصر دارد، سرو كار خواهيم
داشت. جبر بول دو ارزشي در تئوري مجموعه ها و منطق كاربرد دارد. هدف ما در اين
كتاب كاربرد جبر بول در مدار منطقي گيتي است.
2 جبر بول دو ارزشي -1 -2 -2
0 }، به همراه قوانين براي دو = B جبر بول دو ارزشي روي مجموعه دو عنصري، { 1و
x y x. y x y x + y X x´
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1
عملگر دودويي (+) و (.) كه در جدول زير نشان داده شده تعريف مي شود (قانون
و OR ، AND عملگر متمم براي تصديق اصل 3 است):اين قوانين دقيقاً مثل اعمال
گيت هاي منطقي، جبر بول و توابع بولي 55
1 مي باشند. اكنون نشان مي دهيم كه اصول هانتينگتون براي مجموعه، - در شكل 2 NOT
0 } و دو عملگرهاي دودويي كه قبلاً تعريف شده اند، معتبر است. = B 1و }
-1 با توجه به جداول، بسته بودن كاملاً روشن است زيرا نتيجه هر عملگر 1 يا 0
1 مي باشند. 0 , ∈ B بوده و
-2 با توجه به جداول مي بينيم كه:
(a) 1+ 1 = 0 + 1 = 1 + 0 = 1
(b) 1. 0 = 0. 1= 0. 0 = 0
اين روابط بيانگر وجود عناصر شناسه 0 براي (+) و 1 براي (.)، طبق تعريف
مي باشند.
-3 اصول جابجايي با توجه به تقارن جداول عملگرها آشكار است.
را با ايجاد جدول براي x. (y + z) = (x. y) + (x. z) صحت اصل توزيع پذيري (a) -4
را به دست x. (y + z) ، مي توان تحقيق كرد. براي هر تركيب ، z,y,x تمام مقادير ممكن
است. (x. y) + (x. z) آورده و نشان مي دهيم كه برابر
صحت اصل توزيع پذيري (+) روي (.) را نيز مي توان مانند بند قبل تحقيق (b)
نمود.
-5 با استفاده از جدول متمم، به سادگي مي توان ديد كه:
x.y x.z (x . y) + (x . z )
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 1 1
1 0 1
1 1 1
y +z x . ( y + z )
0 0
1 0
1 0
1 0
0 0
1 1
1 1
1 1
x y z
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
56 مدار منطقي
1+1 است. ´=1+0=1 , 0+0´=0+1= زيرا 1 ، x+x´=1 (a)
1.1 است، كه اصل 5 را تصديق مي كند. ´=1.0=0 , 0.0´=0.1= زيرا 0 ، x.x´=0 (b)
-6 اصل 6 نيز صادق است زيرا جبر بول دو ارزشي داراي دو مقدار مجزاي 0 و 1
1است. ≠ با 0
و يك عملگر متمم معادل OR , AND تا اينجا ما يك جبر دو ارزشي با عملگرهاي
ايجاد كرديم. بنابراين جبر بول به روش مستدل رياضي بنا گرديد و نشان داده NOT با
شد كه معادل با منطق دودويي غير مستدل است. بيان غير مستدل براي درك كاربرد
جبر بول در مدارهاي گيتي مفيد است. روش مستدل براي بيان و ايجاد تئوري ها و
خواص سيستم جبري مورد توجه است. جبر بول دو ارزشي تعريف شده در اين بخش
را "جبر سوئيچينگ" نيز مي نامند. براي تاكيد بر تشابه بين جبر بول دو ارزشي و ديگر
سيستم هاي دودويي، اين جبر در بخش قبل "منطق دودويي" ناميده شد. از اين پس،
كلمه "دو ارزشي" را در بحث هاي بعدي از جبر بول حذف مي كنيم.
2 قضاياي اصلي و خواص جبر بول -2 -2
(b) و (a) اصول هانتينگتون به صورت جفت جفت ليست شده اند و به صورت بخشهاي
مشخص شدند. هر يك از اين دو را با تعويض عملگرها و عنصر شناسه مي توان از
ديگري به دست آورد. اين خاصيت در جبر بول به اصل دوگانگي معروف است.
خصوصيات فوق بيان مي دارد كه هر عبارت جبري منتج از اصول جبر بول با تعويض
عملگرها و شناسه ها باز هم معتبر باقي مي ماند. در جبر بول دو ارزشي، عناصر شناسه
يكسانند: يعني 1 و 0اند. اصل دوگانگي كاربردهاي متعددي دارد. B و عناصر مجموعه
OR و AND اگر دوگان يك عبارت جبري مورد نظر باشد تنها كافي است عملگرهاي
تعويض و 0ها به 1 و 1ها به 0 تبديل گردند.
گيت هاي منطقي، جبر بول و توابع بولي 57
1 تئوري هاي اساسي جبر بول -2 -2 -2
تئوري ها و اصول ليست شده اساسي ترين روابط در جبر بول اند. تئوري ها نيز مانند
اصول به صورت جفت جفت ارائه شده اند و هر رابطه دوگان زوج خود است. اصول،
بديهيات ساختار جبري بوده و اثباتي لازم ندارند. تئوري ها بايد با توجه به اصول ثابت
شوند، اثبات تئوري ها با يك متغير در زير نشان داده شده اند. در سمت مقابل روابط،
شماره اصل به كار رفته نوشته شده است.
x+x=x :(a) تئوري 1
=(x+x).1
x+x
=(x+x)(x+x´)
=x+xx´
=x+0
=x
x.x=x:(b) تئوري 1
=xx+0
x.x
=xx+xx´
=x(x+x´)
=x.1
=x
(b) است و هر مرحله از اثبات در بخش (a) دوگان 1 (b) توجه كنيد كه تئوري 1
مي باشد. به اين ترتيب هر تئوري دوگان از اثبات زوجش حاصل (a) دوگان بخش
مي گردد.
x+1=1 :(a) تئوري 2
=1.(x+1)
x+1
=(x+x´)(x+1)
= x+x´.1
= x+x´
=1
58 مدار منطقي
x.0= بر اساس دوگانگي 0 :( b) تئوري 2
را x كه متمم ، x.x´=0 , x+x´= با توجه به اصل 3 ، داريم 1 . x = (x´)´ : تئوري 3
مي باشد. بنابراين، چون (x´)´ است و در نتيجه همان x برابر x´ تعريف مي كند . متمم
.(x´)´ = x متمم منحصر به فرد است داريم
با استفاده از اصول و تئوري هاي اثبات شده قبلي مي توان تئوري هاي دو يا سه
متغيره را به صورت جبري ثابت كرد. مثلاً: تئوري جذب را در نظر بگيريد.
تئوري 4: شركت پذيري
(a): x + (y + z) = (x + y) + z
(b): x (y z) = (x y) z
: تئوري 5
(a): (x + y)´ = x´ y´
(b): (x y)´ = x´ + y´
= x.1+xy
x+xy
=x(1+y)
=x(y+1)
=x.1
=x
x+xy=x :(a) تئوري 6
x(x+y)=x بر اساس دوگانگي :( b) تئوري 6
2 تقدم عملگرها -2 -2 -2
و چهارم AND سوم با ،NOT در ارزيابي عبارت جبر بول تقدم اول با پرانتز، دوم با
است. به بيان ديگر، عبارت داخل پرانتز بايد قبل از ساير عملگرها ارزيابي شود. OR
قرار دارد. به عنوان OR و بالاخره AND عملگر مقدم بعدي متمم است. پس از آن
مثال، جدول درستي را براي تئوري دمورگان تشكيل مي دهيم سمت چپ عبارت
گيت هاي منطقي، جبر بول و توابع بولي 59
است. بنابراين داخل پرانتز ابتدا ارزيابي مي شود و سپس نتيجه متمم مي گردد. (x+y)´
هر دو ابتدا ارزيابي شده و حاصل y و x است. بنابراين متمم x´y´ سمت راست عبارت
مي گردد. توجه كنيد كه در محاسبات معمولي هم روال مشابهي (به جز براي AND
برقرار است. OR و AND متمم) براي ضرب و جمع به ترتيب به جاي
3 توابع بول -2
جبر بول جبري است كه با متغيرهاي دودويي و عمليات منطقي سروكار دارد. يك تابع
به وسيله يك عبارت جبري متشكل از متغيرهاي دودويي، ثابت هاي 0 يا 1 و سمبل هاي
عملياتي منطقي تشكيل شده است. براي مقدار مفروضي از متغيرهاي دودويي، تابع
مي تواند 1 يا 0 باشد. يك تابع بول رابطه اي منطقي را بين متغيرها بيان مي كند. اين تابع
با تعيين مقدار دودويي عبارت بر حسب همه مقادير ممكن متغيرها ارزيابي مي شود.
يك جدول بولي به صورت يك جدول درستي هم مي تواند نشان داده شود. جدول
درستي ليستي از 1ها و 0 ها است كه به متغيرهاي دودويي تخصيص مي يابد، و ستوني
كه مقدار نتايج را براي هر تركيب نشان مي دهد. تعداد سطر ها در جدول درستي ^ 2 n
تعداد متغيرها در تابع است. تركيبات دودويي براي جدول درستي از n است، كه
2^ - شمارش اعداد دودويي و از 0 تا 1 به n دست مي آيد. يك تابع بول را مي توان از يك
عبارت جبري به يك نمودار مداري متشكل از گيت هاي منطقي تبديل كرد. براي درك
بهتر موضوع دو تابع زير را در نظر بگيريد:
F1 = x + y´ z
F2 = x´ y´ z +x´ y z +x y´
را نشان مي دهد: F و 2 F 6، درستي دو تابع 1 - جدول شكل 2
60 مدار منطقي
x y z F1 F2
0 0 0 0 0
0 0 1 1 1
0 1 0 0 0
0 1 1 0 1
1 0 0 1 1
1 0 1 1 1
1 1 0 1 0
1 1 1 1 0
F و 2 F 6: جدول درستي توابع سه متغيره 1 - شكل 2
z,y,x در اين جدول هشت تركيب دودويي ممكن براي تخصيص بيتي به سه متغير
دارد در ازاء هر تركيب 0 يا 1 است. جدول نشان F وجود دارد. ستوني كه بر چسب 1
برابر 1 است. در غير اين صورت 0 خواهد F باشد تابع 1 yz= يا 1 x= مي دهد كه وقتي 1
در يك جدول درستي تنها يك راه وجود دارد. با اين وجود، وقتي F بود. براي نمايش 1
تابع به فرم يك عبارت جبري است، مي تواند به فرم هاي متفاوتي نشان داده شود.
عبارت خاصي كه براي مشخص كردن تابع مورد استفاده قرار مي گيرد اتصالات ميان
در F گيت ها در نمودار مدار منطقي را ديكته مي نمايد. نمودار مدار منطقي تابع بولي 1
7 نشان داده شده است: - شكل 2
يك y´z استفاده شده است. براي جمله NOT از گيت y براي توليد متمم ورودي
به كار رفته است. در نمودارهاي مدار OR وبراي تركيب آن دو يك گيت AND گيت
x F1
y
z
F1 = x + y´ z 7:پيادهسازي با گيت - شكل 2
گيت هاي منطقي، جبر بول و توابع بولي 61
به عنوان خروجي F منطقي، متغيرها ي تابع به عنوان ورودي مدار و متغير دودويي 1
مدار در نظر گرفته مي شوند.
به كمك x,y كه جدول درستي آن در بالا آمده است، متغيرهاي F در تابع بولي 2
AND به دست آيند. سه جمله در عبارت با سه گيت y´ , x´ وارون گر متمم شده اند تا
منطقي سه جمله را فراهم مي سازد. نمودار مدار OR ، نيز OR پياده سازي شده اند. گيت
8 نشان داده شده است: - در شكل 2 F منطقي تابع بولي 2
1 متمم يك تابع -3 -2
به دست F است و از تعويض 0 ها با 1 و 1ها با 0 در مقدار F´ برابر F متمم يك تابع
مي آيد. متمم يك تابع را مي توان به صورت جبري از تئوري دمورگان نيز به دست آورد.
تئوري هاي دمورگان به سه يا چند متغير هم قابل گسترش اند. با استفاده از اصول و
تئوري هاي ارائه شده، فرم سه متغيره اولين تئوري دمورگان به طريق زير ثابت مي شود.
(A + B + C)´ = (A + x)´ : داريم (B + C = x) با فرض
F2
x
y
z
با گيت F 8: پيادهسازي تابع بول 2 - شكل 2
62 مدار منطقي
(A + B + C)´ = A´x´ دمورگان (a) با تئوري 5
(A + B + C)´ = A´ (B + C)´ را جايگزين كنيد B + C = x
(A + B + C)´ = A´(B´C´) دمورگان (a) با تئوري 5
= A´B´C´ شركت پذيري (b) با تئوري 4
تئوري هاي دمورگان براي هرتعدادي از متغيرها، مشابه حالت دو متغيره بوده و با
روش جايگزيني متوالي، مشابه روشي كه در فوق مشاهده شد، مي توان آن را به دست
آورد. فرم عمومي تئوري دمورگان به صورت زير است:
(A + B + C + D + … + F)´ = A´B´C´D´…F´
(ABCD…F)´= A´ + B´ + C´ + D´ + … + F´
و OR و AND اين تئوري بيان مي دارد كه متمم يك تابع با تعويض عملگرهاي
متمم كردن هر ليترال حاصل مي شود.
را به دست آوريد. F2 = x(y´ z´ + y z) و F1 = x´ y z´ +x´ y´ z مثال 1: متمم توابع
متمم ها را با اعمال هر تعداد تئوري دمورگان به صورت زير به دست آوريد:
F´1 =(x´y z´+ x´y´z)´
=(x´y z´)´(x´y´z)´
=(x + y´+z)(x + y + z´)
F´2 =[x(y´z´+yz)]´
=x´+(y´z´+yz)´
= x´+(y´z´)´(yz)´
=x´+ (y +z)(y´+ z´)
گيت هاي منطقي، جبر بول و توابع بولي 63
روال ساده تري براي به دست آوردن متمم يك تابع اين است كه دوگان تابع و متمم
هر ليترال به دست آيد. اين روش با توجه به فرم عمومي تئوري دمورگان نتيجه مي شود.
و تبديل 1ها و OR به AND به خاطر داشته باشيد كه دوگان يك تابع با تبديل عملگر
0 ها به يكديگر به دست مي آيد.
2 را با استفاده از دوگان ها و متمم هاي هر - مثال 2 F و 2 F مثال 2: متمم توابع 1
ليترال به دست آوريد.
1)F1=x´yz´+x´y´z´
(x´+y+z´)(x´+y´+z´) : برابر است با F دوگان تابع 1
(x+y´+z)(x+y+z´)=F´ متمم هر ليترال برابر است با: 1
2) F2= x(y z´+yz)
x+(y´+z´)(y+z) : برابر است با F دوگان تابع 1
x´+(y+z)(y´+z´) =F´ متمم هر ليترال برابر است با: 2
2 ساير اعمال منطقي -3 -2
قرار مي گيرند، به ترتيب دو تابع y,x بين دو متغير OR و AND وقتي كه عملگرهاي
2^ متغير 2 n را تشكيل مي دهند. قبلاً بيان شد كه براي x+y , x.y بولي ^n
تابع دودويي
و تعداد توابع بولي ممكن 16 است. بنابراين توابع n= وجود دارد. براي دو متغير، 2
تنها دو تابع از 16 تابع ممكن با دو متغير دودويي هستند. جدول درستي OR و AND
تشكيل گرديده در جدول زير ليست شده است. y , x 16 تابع كه با دو متغير دودويي
را نشان y,x جدول درستي يك تابع ممكن براي دو متغير ، F15 , F هر يك از 16 ستون 0
معين F مي دهد. توجه داشته باشيد كه توابع از 16 تركيب ممكن تخصيص يافته به
.(9 - مي گردند. 16 تابع را مي توان با توابع بول نشان داد (شكل 2
64 مدار منطقي
بيان كرد، NOT,OR,AND اگر چه هر تابع را مي توان بر حسب عملگرهاي دودويي
اما دليلي وجود ندارد كه كسي عملگر خاصي را براي بيان ساير توابع تعيين ننمايد.
10 ليست شده اند. با اين وجود همه - چنين عملگرهايي در ستون دوم جدول شكل 2
انحصاري (⊕)كاربرد OR سمبل هاي جديد كه در جدول نشان داده شده اند، بجز
چنداني به وسيله طراحان ندارند.
به دنبال هر يك از توابع در جدول زير، نام و توضيحي كه تابع را به نحوي تشريح
مي كند، آورده شده است. 16 تابع ليست شده فوق به سه گروه زير تقسيم مي شوند.
(Identity , Null) -1 دو تابع كه ثابت هاي 1,0 را توليد مي كنند
9- 10 : عبارات بولي 16 تابع تعريف شده در شكل 2 - شكل 2
توضيحات نام سمبل عملگر توابع بول
F0=0 . Null Binary constant 0
F1=xy x.y AND x and y
F2=xy´ x/y Inhibition x, but not y
F3=x . Transfer x´
F4=x´y y/x Inhibition y , but not x
F5=y . Transfer y
F6=xy´ + x´y x⊕y Exclusive-OR x or y , but not both
F7=x+y x+y OR x or y
F8=(x+y) ´ x↓y NOR Not-OR
F9=xy+x´y´ (x⊕y) ´ Equivalence x equals y
F10=y´ y´ Complement Not y
F11=x+y´ xy Implication If y , then x
F12=x´ x´ Complement Not x
F13=x´+y xy Implication If x , than y
F14=(xy) ´ x↑y NAND Not-AND
F15=1 . Identity Binary constant 1
9: جدول درستي براي 16 تابع از دو متغير دودويي - شكل 2
x y F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
گيت هاي منطقي، جبر بول و توابع بولي 65
-2 چهار تابع يكاني از نوع متمم 1 و انتقال 2
-3 ده تابع باقيمانده شامل هشت عمل مختلف به شرح زير مي باشد:
AND •
OR •
NAND •
NOR •
انحصاري) OR يا ) XOR •
يا هم ارزي) ) XNOR •
• نهي 3
• استلزام (استنباط) 4
ثابت ها براي توابع دودويي فقط مي توانند 0 يا 1 باشند. تابع متمم، متمم هر متغير
دودويي را توليد مي نمايند. تابعي كه براي يك متغير ورودي است را انتقال 5 مي نامند،
از طريق يك گيت بدون تغيير مقدار عبور كرده است. از هشت y يا x زيرا متغير
عملگر دودويي، دوتاي آنها (نهي و استلزام) به وسيله طراحان مدارات منطقي به كار
و AND مي روند، ولي به ندرت در منطق كامپيوتر از آنها استفاده مي شود. عملگرهاي
قبلاً در جبر بول ذكر شدند. چهار تابع ديگر به طور گسترده در طراحي دستگاه هاي OR
ديجيتال مورد استفاده اند.
اخذ شده است. به طور مشابه NOT -OR بوده و نام آن از OR متمم NOR تابع
XOR انحصاري يا OR . مشتق مي شود NOT -AND است و از AND متمم ،NAND
1 _ Complement
2 _ Transfer
3 Inhibition
4 Implication
5 Transfer - Buffer
66 مدار منطقي
متفقا برابر 1 باشند، را شامل y,x است ولي حالتي كه در آن هر دو متغير OR مشابه با
يا هم ارزي تابعي است كه هنگام مساوي بودن دو متغير برابر 1 XNOR نمي شود. تابع
متمم يكديگرند XNOR و XOR مي شود، يعني وقتي هر دو 0 يا هر دو 1 باشند. توابع
9 قابل تشخيص است. جدول درستي - و اين خاصيت بسادگي با ملاحظه جدول شكل 2
است. اين دو تابع متمم يكديگرند. F نيز 9 XNOR و براي F عبارت است از 6 OR براي
نشان مي دهند. XNOR انحصاري هم مي گويند و با NOR به اين دليل تابع هم ارزي را
و يك عملگر يكاني با نام OR , AND جبر بول دو عملگر دودويي با نام هاي
متمم) دارد. ما با توجه به تعاريف، برخي از خواص آنها را استنتاج نموديم و در ) NOT
اين بخش تعدادي از عملگرهاي دودويي ديگر را برحسب آنها معرفي كرديم. اين روال
را تعريف كرده و (↓) NOR منحصر به فرد نيست. به عنوان مثال مي توانستيم ابتدا
را بر حسب آنها تعريف كنيم. به هر حال دلايل مكفي براي NOT , OR , AND سپس
بيشتر بين مردم مصطلح NOT , OR , AND روش منتخب وجود دارد و در واقع مفاهيم
بوده و بر تفكرات حاكم هستند. علاوه بر آن اصول هانتينگتون منعكس كننده طبيعت
دوگاني اين جبر است و اين خود بر خاصيت تقارن (+) و (.) نسبت به يكديگر دلالت
دارد.
4 گيت هاي منطقي ديجيتال -2
بيان شده اند، پياده NOT , OR , AND • چون توابع بول بر حسب عملگرهاي
كردن آنها با استفاده از اينگونه گيت ها ساده تر خواهد بود. امكان ساخت
گيت ها براي ديگر اعمال منطقي در عمل مورد توجه است. فاكتورهايي كه
بايد به هنگام ساخت آنها در نظر گرفته شوند عبارتند از:
• امكان سنجي و اقتصادي بودن روش ساخت به هنگام استفاده از قطعات
فيزيكي
• امكان گسترش ورودي گيت ها به بيش از دو
گيت هاي منطقي، جبر بول و توابع بولي 67
• در نظر گرفتن خواص اصلي عملگرهاي دودويي مثل جابجايي و
شركت پذيري
• توانايي گيت در پياده سازي توابع به تنهايي يا همراه با ساير گيت ها
از شانزده تابع معرفي شده در قسمت قبل، دو تابع برابر با مقدار ثابت و چهار تاي
ديگر دوبار تكرار شده اند. بنابراين تنها ده تابع براي تهيه گيت هاي منطقي كانديد
هستند. دو تابع نهي و استلزام داراي خاصيت جابجايي يا شركت پذيري نيستند و لذا به
عنوان گيت هاي منطقي استاندارد مورد استفاده نمي باشند.
XNOR و XOR ،NOR ،NAND ،OR ،AND ،NOT ،Buffer : هشت تابع ديگر يعني
به عنوان گيت هاي استاندارد در طراحي سيستم هاي ديجيتال به كار مي روند.
11 نشان داده - سمبل هاي گرافيكي و جدول درستي هشت گيت فوق در شكل 2
و يك متغير y,x شده اند. هر گيت موجود در شكل، داراي دو متغير ورودي دودويي
از قبل تعريف شده بودند. NOR,OR,AND مي باشد. مدارهاي F خروجي دودويي
يا وارون گر وضعيت منطقي يك متغير دودويي را معكوس مي نمايد و در NOT مدار
واقع متمم متغير را توليد مي كند. دايره كوچك در خروجي سمبل گرافيكي يك
وارون گر (كه به آن حباب مي گويند) بيانگر متمم شدن است.
سمبل مثبت به تنهايي علامت بافر مي باشد. يك بافر عمل انتقال را انجام مي دهد،
ولي يك عمل منطقي توليد نمي كند زيرا مقدار دودويي خروجي برابر مقدار ورودي
دودويي است. اين مدار صرفاً در تقويت توان سيگنال ها استفاده شده و معادل با دو
مدار متوالي وارون گر (معكوس گر) است.
است و همانطور كه از سمبل گرافيكي آن مشخص است از AND متمم NAND تابع
و يك حباب تشكيل شده است. AND يك سمبل
68 مدار منطقي
11 : گيت هاي منطقي به همراه مشخصات و جدول درستي - شكل 2
و به دنبال آن يك حباب نمايش OR است و با يك سمبل OR هم متمم NOR تابع
داده مي شود.
جدول درستي تابع جبري سمبل گرافيكي نام
x y F
0 0 0
0 1 0
1 0 0
1 1 1
F=XY
AND
x y F
0 0 0
0 1 1
1 0 1
1 1 1
F=x+y
OR
x F
0 1
1 0
F = x´
Inverter
x F
0 0
1 1
F=x
Buffer
x y F
0 0 1
0 1 1
1 0 1
1 1 0
F=(xy) ´
NAND
x y F
0 0 1
0 1 0
1 0 0
1 1 0
F= (x+y) ´
NOR
x y F
0 0 0
0 1 1
1 0 1
1 1 0
F= xy´ + x´y = x⊕y
Exclusive-OR
(XOR)
x y F
0 0 1
0 1 0
1 0 0
1 1 1
F=xy+ x´y´= (x⊕y) ´
Exclusive-NOR or
equivalence
گيت هاي منطقي، جبر بول و توابع بولي 69
به طور گسترده اي به عنوان گيت هاي استاندارد مورد NOR و NAND گيت هاي
مورد توجه اند. اين بدان علت است كه AND و OR استفاده قرار گرفته و بيشتر
به سادگي به وسيله مدارات ترانزيستوري قابل توليد بوده و NOR و NAND گيت هاي
مي توان به راحتي توابع بول را با آنها پياده سازي كرد.
است، بجز اينكه يك خط منحني در سمت OR داراي سمبل مشابهي با NOR گيت
است و لذا حباب كوچكي در XOR متمم XNOR ورودي اش كشيده شده است. گيت
خروجي آن وجود دارد.
1 گسترش ورودي گيت ها -4 -2
11 نشان داده شدند، بجز براي وارون گر و انتقال، قابل - گيت هايي كه در شكل 2
گسترش به بيش از دو ورودي مي باشند. اگر عمل دودويي يك گيت جابجا و
كه در OR و AND شركت پذير باشد، مي توان ورودي هاي آن را گسترش داد. اعمال
OR جبر بول تعريف شده اند اين خاصيت را از خود به نمايش گذاشته اند. براي تابع
داريم:
x + y = y + x ( (جابجايي
و
(x+y) + z = x + (y + z) = x + y + z ( (شركت پذير
اين روابط بيانگر تعويض پذيري ورودي هاي گيت و قابل گسترش بودن متغيرهاي
است. OR ورودي به بيش از دو در تابع
NOR و NAND توابع
جابجا پذيرند و ورودي آنها مي تواند به بيش از دو افزايش NOR و NAND توابع
يابد، مشروط بر اين كه در تعريف تابع مختصر تغييري صورت گيرد. مشكل اين است
شركت پذير نيستند. يعني: NOR و NAND كه
70 مدار منطقي
[(x↓y)↓z ≠ x(y↓z) ]
12 و معادلات زير مشاهده مي گردد: - اين نكته در شكل 2
( x↓y)↓z = [ (x + y)´+ z ]´ = (x + y)z´= xz´+ yz´
x ↓(y↓ z) = [ x + (y + z)´]´= x´(y + z) = x´y+ x´z
چند ورودي را به عنوان متمم (NAND يا ) NOR براي غلبه بر اين مشكل، گيت
آن تعريف مي كنيم. بنابراين: (AND يا ) OR
x↓y↓z = (x+y+z)´
x↑y↑z = (xyz)´
13 نشان داده شده اند. در - سمبل هاي گرافيكي گيت هاي سه ورودي در شكل 2
بايد پرانتزها به فرم صحيحي انتخاب شوند تا بيانگر NAND,NOR نوشتن متوالي اعمال
ترتيب صحيح گيت ها باشند.
(x ↓ y) ↓ z = (x + y) z´
x ↓ (y ↓ z) = x´ (y + z)
x
x
y
y
z
z
(x↓y)↓ z≠ x↓(y↓ z) - NOR 12 شركتناپذيري عملگر - شكل 2
x
y
z
(x+y+z) ´
(xyz) ´
y
x
z
گيت هاي منطقي، جبر بول و توابع بولي 71
XNOR و XOR گيت هاي
هر دو خواص جابجايي و شركت پذيري را دارند و ورودي هايشان XNOR و XOR
چند ورودي از نقطه XOR قابل توسعه به بيش از دو مي باشد. با اين وجود گيت هاي
نظر سخت افزاري متداول نيستند. در واقع حتي فرم دو ورودي آن نيز معمولاً از ساير
گيت ها ساخته مي شود. علاوه بر اين، تعريف اين توابع بايد به هنگام گسترش
يك تابع فرد است يعني هرگاه ورودي ها تعداد XOR ورودي ها تصحيح گردد. تابع
XOR فردي 1 داشته باشند، اين تابع (خروجي) برابر 1 خواهد بود. ساختمان يك گيت
13 ديده مي شود. - با سه ورودي در شكل 2
13 (الف). به صورت - اين مدار معمولاً با گيت هاي دو ورودي تهيه مي شود، شكل 2
13 (ب). جدول - گرافيكي، آن را مي توان با يك گيت سه ورودي نشان داد، شكل 2
برابر 1 است به شرطي كه فقط F درستي (پ) آشكارا مشخص مي نمايد كه خروجي
يكي از ورودي ها و يا هر سه ورودي برابر 1، باشند ؛ يعني وقتي تعداد كل 1ها در
متغيرهاي ورودي فرد است، تابع 1 است.
x
y
z
z⊕ y ⊕F = x
y
z
x
z⊕ y ⊕F = x
(الف) با گيتهاي دوورودي
(ب) با گيت سه ورودي
(پ) جدول درستي
XOR 13 : گيت - شكل 2
x y z F
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
72 مدار منطقي
2 مدارهاي مجتمع -4 -2
با گسترش علم الكترونيك و طراحي مدارات تركيبي و پيچيده نياز به طراحي بسته هاي
يك (IC) يكپارچه و كوچكتر از مدارها بيش از پيش احساس مي شد. يك مدار مجتمع
كريستال نيمه هادي از جنس سيليكان است كه به آن تراشه مي گويند و حاوي اجزاء
الكترونيكي در ساخت گيت هاي ديجيتال مي باشد و انواع گيت ها در داخل تراشه به هم
وصل مي شوند تا مدار مورد نياز ايجاد گردد. تراشه روي يك محفظه سراميك يا
پلاستيك نصب شده و اتصالات به پايه هاي بيرون براي ايجاد مدار مجتمع، متصل
مي گردند. تعدادپايه ها ممكن است گاه چند هزار در يك بسته بزرگ برسد. در روي هر
يك شماره براي شناسايي چاپ مي شود. IC
1 سطوح مجتمع سازي -2 -4 -2
هاي ديجيتال اغلب بر اساس پيچيدگي مدار دروني شان كه به تعداد گيت هاي IC
منطقي مرتبط است دسته بندي مي شوند. تفكيك تراشه هايي كه تنها چند يا چند صد و
يا چندين هزار گيت دارند با ارجاع به بسته و دسته بندي آنها به وسايل مجتمع با
فشردگي كم،متوسط، زياد و خيلي زياد صورت مي گيرد.
داراي چند گيت مستقل در بسته اند. (SSI) مدارهاي مجتمع با فشردگي كم
ورودي ها خروجي هاي گيت ها مستقيماً به پايه هاي بسته متصل مي شوند. تعداد گيت ها
محدود مي گردند. IC معمولاً كمتر از 10 بوده و به وسيله پايه هاي موجود در
داراي فشردگي بين 10 تا 1000 (MSI) مدارهاي مجتمع با فشردگي متوسط
گيت در يك بسته دارند. اين دسته از مدارات معمولاً اعمال ديجيتال خاصي را اجرا
با عناوين ديكدر ها، جمع كننده ها و مولتي پلكسرها در MSI مي كنند. توابع ديجيتال
فصل 4 و ثبات ها و شمارنده ها در فصل 6 مطرح شده اند.
گيت هاي منطقي، جبر بول و توابع بولي 73
حاوي هزاران گيت در يك بسته (LSI) مدارهاي مجتمع با فشردگي زياد
مي باشند. اين دسته از مدارات، پردازنده ها، حافظه ها و مدارات منطقي برنامه پذير را
در فصل 8 معرفي شده اند. LSI شامل مي شوند. بعضي از اجزا
صدها هزار گيت در يك بسته (VLSI) مدارهاي مجتمع با فشردگي خيلي زياد
دارند. از جمله مثالها مي توان از آرايه هاي حافظه، تراشه ميكرو كامپيوتر هاي پيچيده
تكنولوژي طراحي سيستم كامپيوتر را VLSI نام برد. به دليل كوچكي و ارزاني، وسايل
متحول ساخته و به طراح قابليت ساخت وسايلي را مي دهد كه قبلاً اقتصادي نبودند.
2 منطق مثبت و منفي -2 -4 -2
سيگنال دودويي در ورودي ها يا خروجي هر گيت، بجز در حالت گذرا، يكي از دو
مقدار را دارد. يك مقدار سيگنال، منطق 1 و ديگري منطق 0 را نمايش مي دهد. چون
دو مقدار سيگنال متعلق به دو ارزش منطقي است، لذا دو انتساب متفاوت براي دو
و سطح سيگنال H 14 سطح سيگنال بالاتر با - ارزش منطقي مي توان اختيار كرد، شكل 2
مقدار سيگنال مقدار منطقي مقدار سيگنال مقدار منطقي
0 H 1 H
1 L 0 L
(الف) منطق مثبت (ب) منطق منفي
14 : تخصيص سيگنال و قطبيت منطق - شكل 2
براي منطق 1 به كار رود يك ،H ، مشخص شده است. اگر سطح بالا L پايين تر با
براي منطق 1 سيستم منطقي منفي را L سيستم منطق مثبت تعريف شده است. انتخاب
معرفي مي نمايد.
كلمات مثبت يا منفي گاهي گمراه كننده هستند زيرا هر دو سيگنال ممكن است
مثبت يا منفي باشند. در واقع، اين قطب هاي سيگنال نيستند كه بيانگر نوع منطق
74 مدار منطقي
مي باشند، بلكه انتخاب مقادير منطقي بر حسب سطوح نسبي سيگنال ها نسبت به هم،
نوع منطق را مشخص مي كنند.
تعريف مي شوند. از L , H گيت هاي ديجيتال سخت افزاري بر حسب مقادير سيگنال
اين پس انتخاب منطق مثبت و منفي به عهده كاربر است. به عنوان مثال گيت
الكترونيك شكل زير را به همراه جدول درستي آن در نظر بگيريد:
برابر 0 ولت است نشان L 3 و V برابر H اين جدول رفتار فيزيكي گيت را وقتي
L= و 0 H= 15 جدول درستي منطق مثبت را فرض مي كند كه در آن 1 - مي دهد. شكل 2
با منطق مثبت در شكل زير ديده AND است. اين جدول درستي همانند جدول عمل
مي شود.
در نظر H= و 0 L= اكنون تخصيص منطق منفي را براي همان گيت فيزيكي با 1
بگيريد. نتيجه جدول درستي شكل زير خواهد بود. گرچه داده ها معكوس شده اند ولي
گيت
ديجيتال
x
y
z
نمودار بلوكي گيت
x y z
L L L
L H L
H L L
H H H
H و L جدول درستي با
x
y
z
با منطق مثبت AND گيت
x y z
0 0 0
0 1 0
1 0 0
1 1 1
جدول درستي منطق مثبت
با منطق مثبت AND 15 : نمايش جدول درستي گيت - شكل 2
گيت هاي منطقي، جبر بول و توابع بولي 75
با منطق منفي در OR را نشان مي دهد. سمبل گرافيكي گيت OR جدول عمل
16 ديده مي شود. - شكل 2
مثلث هاي كوچك در ورودي ها و خروجي نشانگر قطبيت هستند. وجود علائم
قطبيت همراه با مشخصات پايانه بيانگر فرض منطق منفي براي سيگنال است. بنابراين
با منطق OR با منطق مثبت و نيز يك گيت AND گيت فيزيكي فوق مي تواند يك گيت
منفي باشد. تبديل منطق مثبت به منفي و بالعكس، عملي است كه طي آن در ورودي و
خروجي يك گيت 0 ها به 1 و 1ها به 0 تبديل مي شوند. چون اين عمل دوگان تابع را
توليد مي كند، تعويض پايانه ها از يك قطبيت به قطبيت ديگر نتيجه اش همان يافتن
دوگان تابع است.
و بالعكس تبديل شوند. OR به AND نتيجه اين تبديل اين است كه همه عملگرهاي
به علاوه نبايد از ذكر مثلث در سمبل هاي گرافيكي كه بيانگر قطبيت است در منطق
منفي، فراموش كرد. در اين كتاب از گيت ها با منطق منفي استفاده نمي كنيم و فرض
خواهيم كه همه گيت ها با منطق مثبت كار كنند.
3 خانواده هاي منطقي ديجيتال -2 -4 -2
جدا از بحث پيچيدگي و عمل منطقي مدارهاي مجتمع ديجيتال كه باعث دسته بندي
آنها نيز مي گردد، اين مدارات بر اساس تكنولوژي مدار خاصي كه به آن تعلق دارند نيز
دسته بندي مي گردند. تكنولوژي مدار به نام خانواده مدار منطقي خوانده مي شود. هر
z
با منطق منفي OR گيت
x y z
1 1 1
1 0 1
0 1 1
0 0 0
با منطق منفي OR 16 : نمايش جدول درستي گيت - شكل 2
y
x
76 مدار منطقي
خانواده منطقي داراي مدار الكترونيك مبناي خاص خود بوده و ساير توابع و مدارات
پيچيده ديجيتال با استفاده از آنها ساخته مي شوند. مدار مبنا در هر خانواده، گيت
است. قطعات الكترونيك به كار رفته در ساخت مدار مبنا معمولاً NOT يا NOR ،NAND
براي نام گذاري تكنولوژي مورد استفاده قرار مي گيرد. به لحاظ تجاري انواع متفاوتي از
خانواده هاي منطقي مدارات مجتمع معرفي شده اند. انواع رايج آنها در زير ليست
شده اند.
emitter-coupled logic ECL
transistor-transistor logic TTL
metal-oxide semiconductor MOS
complementary metal- oxide semiconductor CMOS
در سيستم هايي كه به سرعت بالا نياز دارد ارجحيت دارد. :ECL
مدت مديدي است كه مورد استفاده بوده و به عنوان يك گيت استاندارد :TTL
شناخته شده است.
در مدارهايي كه نياز به چگالي قطعه بالايي دارند مورد استفاده است. :MOS
در مواقعي كه توان مصرفي بايد كم باشد مورد توجه مي باشد. :CMOS
تبديل به CMOS ، از اصول است VLSI نظر به اينكه توان مصرفي كم در طراحي
به ECL,TTL يك خانواده منطقي غالب شده است در حالي كه از كاربرد خانواده هاي
تدريج كاسته مي شود.
گيت هاي منطقي، جبر بول و توابع بولي 77
سؤالات فصل دوم
هر يك با ) NOR و NAND -1 با استفاده از جدول درستي نشان دهيد كه گيتهاي
سه ورودي) متمم يكديگر هستند يا خير؟
-2 جداول درستي توابع ذيل را تهيه كنيد.
F1 = (x+y). (x´+z).(x+y´+z´)
F2 = x´ + yz´
-3 متمم توابع زير را به دست آوريد.
F1 = x´ y z´ + x´ y´
F2 = x (y´ z´ + y z)
F3 =(xy´ + z) x´z´
هر يك ) X-NOR و X-OR -4 با استفاده از جدول درستي نشان دهيد كه گيت هاي
متمم يكديگرند. (y و x با دو ورودي
-5 نمودار منطقي عبارات ذيل را رسم نماييد.
F1 = (x + y). (x´ + y´ + z)
F2 = x + (y. z´) + (x´. y´. z) + x´z´