1. কার্নো মানচিত্র কী
কার্নো মানচিত্র হলো সত্যক সারণিকে ছক আকারে নতুন করে আঁকা রূপ। মরিস কার্নো ১৯৫৩ সালে বেল ল্যাবসে এটি উপস্থাপন করেন, যাতে সুইচিং বর্তনী চোখে দেখেই সরল করা যায়; ছোট বুলিয়ান ফাংশন হাতে-কলমে ন্যূনতম করার এটিই আজও দ্রুততম উপায় - বীজগণিত নয়, মুখস্থ সূত্রও নয়, কেবল আয়তক্ষেত্র।
মানচিত্রের প্রতিটি ঘর সত্যক সারণির একটি সারি ধরে রাখে। একে নিছক পুনর্বিন্যাসের চেয়ে বেশি করে তোলে সেই সারিগুলির সাজানোর ক্রম: পাশাপাশি ঘরগুলি ঠিক একটি চলকে ভিন্ন হয়।
এই একটি ধর্মই সব কাজ করে দেয়। পাশাপাশি দুটি ঘর যদি দুটোই সত্য হয়, তবে তাদের মধ্যে যে চলকটি বদলায় সেটি অভিব্যক্তিকে সত্য করার কারণ হতে পারে না; তাই সেটি বাদ পড়ে আর একটি পদই দুটি ঘর ঢেকে দেয়। সরলীকরণ তখন হয়ে দাঁড়ায় যত বড় সম্ভব আয়তক্ষেত্র আঁকা।
2. কলামের ক্রম অদ্ভুত লাগে কেন
কার্নো মানচিত্রের কলাম ০০, ০১, ১০, ১১ গোনে না। সেগুলি চলে 00, 01, 11, 10 - প্রতিফলিত গ্রে কোড, যেখানে প্রতিটি মান পরেরটির থেকে মাত্র এক বিটে আলাদা। দ্বিমিক গোনায় 01-এর পাশে 10 পড়ত, যারা দুই বিটে আলাদা, আর তখন পাশাপাশি ঘর কিছুই জানাত না।
| A \ BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 3 | 2 |
| 1 | 4 | 5 | 7 | 6 |
প্রান্তগুলিও প্রতিবেশী। বাঁ দিকের প্রথম আর ডান দিকের শেষ কলাম এক চলকে আলাদা, উপরের ও নিচের সারিও তাই; ফলে একটি দল এক প্রান্ত পেরিয়ে অন্য প্রান্তে চলতে পারে - এ কারণেই চার চলকের মানচিত্রের চার কোণ মিলে একটিই দল হয়। কার্নো মানচিত্র আসলে একটি টোরাসের উপর আঁকা; সমতল পাতা কেবল সুবিধার জন্য।
3. এক-গুলিকে দলবদ্ধ করা
মানচিত্র থেকে ন্যূনতম গুণফলের যোগ পড়তে হলে 1 আছে এমন প্রতিটি ঘর আয়তাকার দল দিয়ে ঢাকুন, চারটি নিয়ম মেনে:
- দল হলো 1, 2, 4, 8 … ঘরের আয়তক্ষেত্র - প্রতিটি বাহু দুইয়ের ঘাত।
- দল মানচিত্রের প্রান্ত পেরিয়ে ঘুরে আসতে পারে - আড়াআড়ি, খাড়াখাড়ি, কিংবা দুই দিকেই।
- দলগুলি পরস্পরের উপরে পড়তে পারে। একটি ঘর দুবার ঢাকা পড়লে কোনো ক্ষতি নেই; একটি ঘর না ঢাকলে ফাংশনই বদলে যায়।
- প্রতিটি দলকে যতটা বড় করা যায় ততটা করুন, তারপর সব এক ঢাকতে যত কম দল লাগে ততগুলিই নিন।
প্রতিটি দল একটি পদে পরিণত হয়। পড়ার নিয়ম: গোটা দলে কোন চলকগুলি একই থাকে তা দেখুন - সেগুলিই পদে আসে (যেখানে 1 সেখানে যেমন আছে তেমন, যেখানে 0 সেখানে নিষেধসহ) - আর যে চলক বদলায় সেটি বাদ পড়ে। দুই ঘরের দল একটি চলক হারায়, চার ঘরের দুটি, আট ঘরের তিনটি। ন্যূনতম অভিব্যক্তি এই পদগুলির বিয়োজন।
4. একটি সমাধান করা উদাহরণ
ধরুন (A ∧ B) ∨ (¬A ∧ C) ∨ (B ∧ C ∧ D)। এর মানচিত্রে চারটি চলক: সারিতে A ও B, কলামে C ও D।
| AB \ CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 0 | 0 | 1 | 1 |
| 01 | 0 | 0 | 1 | 1 |
| 11 | 1 | 1 | 1 | 1 |
| 10 | 0 | 0 | 0 | 0 |
দুটি দলই সব এক ঢেকে দেয়। একটি হলো চার ঘরের সেই ব্লক, যেখানে A = 0 এর দুই সারি আর C = 1 এর দুই কলাম মেলে: এর ভিতরে B আর D দুটোই বদলায়, তাই বাদ পড়ে এবং পদটি হয় ¬A ∧ C। অন্যটি হলো A আর B দুটোই 1 এমন গোটা সারি, চারটি কলাম জুড়ে: এর সঙ্গে C আর D বদলায়, থেকে যায় A ∧ B।
তাই ন্যূনতম রূপ হলো (¬A ∧ C) ∨ (A ∧ B)। মূল অভিব্যক্তির তৃতীয় পদ B ∧ C ∧ D মিলিয়ে গেছে: সেটি যে ঘরগুলি ঢাকত, সেগুলি আগেই ওই দুই দলের কোনো একটির ভিতরে ছিল। শোষণ যখন চোখে দেখা যায়, তখন সেটি ঠিক এমনই দেখায়।
5. মুখ্য ও অপরিহার্য অন্তর্ভাবক
যে দলকে আর বড় করা যায় না তাকে বলে মুখ্য অন্তর্ভাবক (প্রাইম ইমপ্লিক্যান্ট)। মুখ্য অন্তর্ভাবকগুলি তালিকাভুক্ত করা সমস্যার সহজ অর্ধেক; তার মধ্যে কোনগুলি রাখা হবে তা বাছা হলো সেই অর্ধেক যেখানে ভুল হয়।
কোনো ঘর যদি একটিমাত্র মুখ্য অন্তর্ভাবক দিয়েই ঢাকা পড়ে, তবে সেই অন্তর্ভাবকটি অপরিহার্য: কোনো ন্যূনতম রূপই তাকে বাদ দিতে পারে না, কারণ ওই ঘরটি আর কিছুই ঢাকে না। আগে অপরিহার্যগুলি নিন, তারপর বাকিটা যতটা সম্ভব কম সংখ্যক অবশিষ্ট দল দিয়ে ঢাকুন।
লোভী পথ - প্রতিবার হাতের সবচেয়ে বড় দলটি তুলে নেওয়া - প্রলোভনীয়, কিন্তু সবসময় কাজ করে না। চক্রাকার ছকে, যেখানে কোনো অন্তর্ভাবকই অপরিহার্য নয় এবং প্রতিটি ঘর দুবার ঢাকা পড়ে, লোভী বাছাই সেরা উত্তরের চেয়ে একটি পদ বেশি নিয়ে শেষ হতে পারে। এই সাইটের মানচিত্র বরং বাকি সব সম্ভাবনা ঘেঁটে দেখে, যা চার চলকে কার্যত বিনামূল্যে।
6. বদলে শূন্যগুলিকে দলবদ্ধ করা
উপরের সবকিছুই শূন্যের ক্ষেত্রেও সমানভাবে খাটে। একই আয়তক্ষেত্র দিয়ে সেগুলি ঢাকুন, প্রতিটি দল পড়ুন নিষেধসহ - গোটা দলে যে চলক 1 সেটি নিষেধসহ আসে, যেটি 0 সেটি যেমন আছে তেমনই - আর দলগুলি ∨ নয়, ∧ দিয়ে জোড়া দিন।
ফল হলো যোগফলের গুণ: বিয়োজনগুলির একটি সংযোজন, যা ঠিক সেই ঘরগুলিতেই মিথ্যা যেখানে অভিব্যক্তি মিথ্যা, আর তাই বাকি সর্বত্র সত্য। কোন রূপটি ছোট হবে তা ফাংশনের উপর নির্ভর করে - কম 1 থাকলে গুণফলের যোগ ছোট হয়, কম 0 থাকলে যোগফলের গুণ - তাই বেছে নেওয়ার আগে মানচিত্র থেকে দুটোই পড়ে নেওয়া ভালো।
7. বড় মানচিত্র এবং ডোন্ট-কেয়ার ঘর
পাঁচ ও ছয় চলককে চার-চলকের দুটি বা চারটি মানচিত্র একটির উপরে আরেকটি সাজিয়ে আঁকা যায়, যেখানে পাশাপাশি স্তরের একই অবস্থানের ঘরগুলিকে সন্নিহিত ধরা হয়। এতে কাজ চলে, কিন্তু যে সন্নিহিততা পদ্ধতিটিকে দৃশ্যমান করেছিল তা এখন দেখার নয়, মনে রাখার বিষয় হয়ে দাঁড়ায়। তার পরে কোয়াইন-ম্যাক্লাস্কি অ্যালগরিদম একই কাজ সারণির আকারে করে: এটি ঠিক এই দলবদ্ধকরণেরই যান্ত্রিক রূপ, আর এখানকার মানচিত্রের পিছনেও সেটিই চলে।
হার্ডওয়্যার নকশা আরও একটি ধারণা যোগ করে। কিছু ইনপুট সমাবেশ কখনোই ঘটে না - দ্বিমিক-সংকেতায়িত দশমিক অঙ্ক কখনো 1010 হয় না - তাই বর্তনী সেগুলি নিয়ে কী করে তাতে নকশাকারের কিছু যায়-আসে না। ওই ঘরগুলিতে X বসে এবং যে মান দল বড় করে সেই মান ধরেই পড়া যায়। এই ক্যালকুলেটরের মানচিত্র একটি সূত্র থেকে তৈরি, যা প্রতিটি বিন্যাসকে একটি মান দেয়, তাই এখানে কোনো ঘরই ডোন্ট-কেয়ার নয়।
8. নিজে চেষ্টা করুন
ক্যালকুলেটরে দুই থেকে চার চলকের একটি অভিব্যক্তি লিখুন, তার মানচিত্র সত্যক সারণির নিচে আঁকা হবে - প্রতিটি দল নিজের রঙে ঘেরা আর নিচে লেখা ন্যূনতম রূপ। শূন্যগুলিকে দলবদ্ধ দেখতে যোগফলের গুণে পাল্টে নিন।