جدول درستی و ساده‌سازی عبارت منطقی

هر مدار منطقی ترکیبی، هرقدر هم پیچیده به نظر برسد، در نهایت یک قول ساده می‌دهد: به ازای هر ترکیب ممکن از ورودی‌ها، یک خروجی مشخص. اگر همهٔ آن ترکیب‌ها را در یک جدول بنویسی، رفتار مدار کاملاً و بدون ابهام توصیف شده است. این جدول، جدول درستی نام دارد و زبان مشترک طراح و آزمایشگر است.

ساختن جدول درستی

اگر مداری n ورودی داشته باشد، تعداد سطرهای جدول درستی برابر ۲ به توان n است. با دو ورودی چهار سطر، با سه ورودی هشت سطر و با چهار ورودی شانزده سطر خواهی داشت. سطرها را به ترتیب شمارش دودویی می‌نویسند تا هیچ حالتی جا نیفتد. نکتهٔ جالب اینکه تعداد توابع منطقی متمایزی که با n ورودی می‌توان تعریف کرد، ۲ به توان تعداد سطرهاست؛ پس با دو ورودی شانزده تابع متفاوت و با سه ورودی ۲۵۶ تابع متفاوت وجود دارد. AND و OR و XOR تنها سه عضو از آن شانزده عضو‌اند.

از جدول به عبارت: مجموع مین‌ترم‌ها

برای تبدیل جدول به یک عبارت جبری، به سطرهایی نگاه کن که خروجی‌شان ۱ است. برای هر سطر یک مین‌ترم بنویس: ضرب منطقی همهٔ ورودی‌ها، به این شکل که هر ورودی با مقدار ۱ را خودش و هر ورودی با مقدار ۰ را وارونه‌اش بگذاری. سپس همهٔ مین‌ترم‌ها را با OR کنار هم بگذار. این عبارت همیشه درست است، اما تقریباً هیچ‌وقت کوتاه‌ترین شکل ممکن نیست؛ کار ساده‌سازی از همین‌جا شروع می‌شود.

جدول درستی هرگز دروغ نمی‌گوید. هر وقت به درستی یک ساده‌سازی شک کردی، هر دو عبارت را روی همهٔ سطرها بیازما؛ اگر حتی یک سطر فرق داشت، ساده‌سازی غلط است.

مثال عددی حل‌شده

عبارت زیر را در نظر بگیر: وارونهٔ A ضربدر B، بعلاوهٔ A ضربدر B، بعلاوهٔ A ضربدر وارونهٔ B. این عبارت سه جمله و شش حرف دارد و پیاده‌سازی مستقیمش به دو وارونگر، سه گیت AND و دو گیت OR نیاز دارد؛ یعنی هفت گیت. حالا ساده‌اش کن: دو جملهٔ اول در B مشترک‌اند، پس B را فاکتور بگیر و به B ضربدر «وارونهٔ A بعلاوهٔ A» می‌رسی؛ چون هر متغیر بعلاوهٔ وارونه‌اش برابر ۱ است، این تکه فقط به B تبدیل می‌شود. حالا عبارت شده B بعلاوهٔ A ضربدر وارونهٔ B، که طبق قاعدهٔ جذب برابر A بعلاوهٔ B است. یعنی کل آن مدار هفت‌گیتی، در واقع فقط یک گیت OR بوده است. برای اطمینان چهار سطر را بررسی کن: برای A=۰ و B=۰ عبارت اصلی ۰ می‌دهد و A بعلاوهٔ B هم ۰ است؛ برای A=۰ و B=۱ جملهٔ اول ۱ می‌شود و نتیجه ۱ است؛ برای A=۱ و B=۰ جملهٔ سوم ۱ می‌شود و نتیجه ۱ است؛ و برای A=۱ و B=۱ جملهٔ دوم ۱ می‌شود و نتیجه باز هم ۱. هر چهار سطر یکسان است، پس ساده‌سازی درست بوده است.

یک مثال سه‌متغیره

تابع F با سه ورودی A و B و C را در نظر بگیر که در سطرهای شمارهٔ ۱، ۳، ۵ و ۷ خروجی ۱ دارد. اگر شمارهٔ سطرها را به دودویی بنویسی می‌بینی در هر چهار سطر، بیت کم‌ارزش یعنی C برابر ۱ است و A و B همهٔ ترکیب‌های ممکن را می‌گیرند. پس خروجی اصلاً به A و B وابسته نیست و F ساده می‌شود به C. عبارت خام دوازده حرف داشت و نتیجهٔ ساده‌شده حتی یک گیت هم لازم ندارد؛ فقط یک سیم. در نقشهٔ کارنو این چهار خانه یک ستون کامل و مجاور می‌سازند و همین گروه‌بندی، پاسخ را مستقیم نشان می‌دهد.

کاربرد واقعی

در طراحی صنعتی، ابزارهای سنتز خودکار همین کار را برای مدارهایی با ده‌ها ورودی انجام می‌دهند. کم‌شدن هر گیت یعنی مساحت کمتر روی سیلیکون، مصرف توان کمتر و تأخیر کوتاه‌تر. در یک تراشهٔ پرشمار، همین صرفه‌جویی‌های کوچک در میلیون‌ها تکرار ضرب می‌شود و به تفاوت چند وات در مصرف باتری می‌انجامد.