جدول کارنو

جدول کارنو روشی است برای ساده سازی توابع جبر بول که بوسیله موریس کارنو در سال ۱۹۵۳ ارائه شد. این روش کامل شده دیاگرام ویچ است که بوسیله ادوارد ویچ در سال ۱۹۵۲ ارائه شده بود. جدول کارنو نیاز به محاسبات طولانی را کاهش داده و اجازه مشخص کردن و حذف کردن سریع وضعیت رقابتی را می‌دهد.


http://uc-njavan.ir/images/ywzii70osab78jp9kbh1.png

مقادیر بولی از جدول درستی و با توجه به اصول کد گری به جدول کارنو انتقال می‌یابند. داده‌ها در جدول کارنو که ۲سلول دارد چیده می‌شوند و مینترم‌ها بر اساس اصول جبر بول ساخته می‌شوند.
نقشه کارنو نموداری از مربع‌ها است که هر مربع یک مینترم را نمایش می‌دهد. به کمک این مربع‌ها می‌توان یک تابع بول را نمایش داد. نقشه کارنو به چند حالت مختلف دو، سه، چهار و گاها پنج متغیره نمایش می‌یابد. نقشه کارنوی n متغیره، دارای خانه است که هر خانه یک مینترم را نمایش می‌دهد. بعد از اینکه مینترم‌های یک تابع را در نقشه کارنو علامت‌گذاری کردیم، می‌توانیم مربع‌های همجوار را با هم ساده کنیم. در شکل زیر یک نقشه ۴ متیره که ۱۶ مربع یا خانه دارد نمایش داده شده است:


http://commons.wikimedia.org/wiki/Fi...svg?uselang=fa




برای شماره‌گذاری خانه‌ها از کد گری استفاده شده است. چرا که در کد گری، هر عدد با اعداد ماقبل و مابعد خود تنها در یک رقم تفاوت دارد و این خاصیت به ساده کردن توابع بول کمک می‌کند.


مثال زیر یک تابع ساده نشده جبر بول را با متغیرهای بولی A،B،C،D نشان می‌دهد.

f(A, B, C, D) = \sum_{}(6, 8, 9, 10, 11, 12, 13, 14)


برای مشاهده جدول درستی به این لینک مراجعه کنید:

http://fa.wikipedia.org/wiki/%D9%86%...B1%D9%86%D9%88


متغیرها می‌توانند در ۱۶ حالت مختلف ترکیب شوند پس جدول ما ۱۶ سلول دارد. متناظر با مینترم‌هایی که تابع در آنها یک است، خانه‌های جدول را نیز مانند شکل یک می‌کنیم. مابقی خانه‌های جدول را نیز صفر قرار می‌دهیم. سپس باید سلول‌های جدول را به دسته‌های دوتایی، چهارتایی یا هشت تایی تقسیم کنیم. دقت کنید که فقط سلول‌هایی که همسایه هستند قابل انتخاب هستند. در ضمن سلول‌های بالایی با پایینی و سلول‌های راستی با چپی نیز همسایه هستند و قابل دسته بندی هستند. در این مثال سلول‌های قرمز و قهوه‌ای را می‌توان با هم دسته بندی کرد. اگر این عمل را انجام دهیم جواب نهایی ساده تر می‌شود ولی اجباری در این کار نیست.

http://uc-njavan.ir/images/w40ny45al4lelehap8xk.png


پس از عملیات دسته بندی باید مینترم متناظر به هر دسته را بنویسیم که در این مثال:

سلول‌های آبی: 'BCD
سلول های قهوه ای و سبز: 'AB
سلول های قرمز و قهوه ای: 'AC

سپس تابع بولی ساده شده را بر اساس حاصل جمع حاصل ضرب ها می نویسیم:
'f(a،b،c،d)=BCD' + AB' + AC


منبع:ویکی پدیا