Boolean algebra — সূত্র, De Morgan, SOP আর POS

১ · Boole থেকে Shannon — যুক্তির গণিত কীভাবে সুইচে নামল

আগের পর্বগুলোতে আমরা bit-কে দেখেছি তথ্য রাখার একক হিসেবে — সংখ্যা, অক্ষর, রং। এবার একই বিট দিয়ে সিদ্ধান্ত নেওয়ার পালা। “দরজা বন্ধ এবং চাবি ঘোরানো হলে গাড়ি চলবে”, “বৃষ্টি হলে অথবা রোদ চড়া হলে ছাতা নেব”, “লোডশেডিং না হলে পাখা ঘুরবে” — এই প্রতিটি বাক্যের উত্তর হয় “হ্যাঁ” নয়তো “না”। এমন হ্যাঁ-না প্রশ্নের হিসাব করার গণিতের নাম Boolean algebra.

নামটি এসেছে ইংরেজ গণিতবিদ George Boole-এর নাম থেকে। তিনি ১৮৪৭ সালে একটি ছোট বই আর ১৮৫৪ সালে An Investigation of the Laws of Thought প্রকাশ করেন। Boole-এর লক্ষ্য ছিল মানুষের যুক্তিকে বীজগণিতের মতো সমীকরণে লেখা — “সত্য” আর “মিথ্যা”-কে ১ আর ০ ধরে। প্রায় একই সময়ে Augustus De Morgan যুক্তির কিছু নিয়ম নিয়ে কাজ করছিলেন, যার দুটি আজ তাঁর নামে পরিচিত। পরের কয়েক দশকে অন্য গণিতবিদেরা (যেমন Jevons, Peirce, Schröder) এই ব্যবস্থাকে আরও গুছিয়ে তোলেন, আর ১৯০৪ সালে Edward Huntington এর জন্য একটি পরিচ্ছন্ন postulate-সেট লেখেন, যা আমরা অংশ ৪-এ দেখব।

প্রায় আশি বছর এটি ছিল দর্শন আর বিশুদ্ধ গণিতের বিষয়। মোড় ঘোরে ১৯৩৭ সালে। MIT-র তরুণ ছাত্র Claude Shannon তাঁর master's thesis-এ (পরের বছর A Symbolic Analysis of Relay and Switching Circuits নামে প্রকাশিত) দেখান যে টেলিফোন এক্সচেঞ্জের relay-ভরা জটিল switching circuit-কে Boolean algebra দিয়ে লেখা, সরল করা আর নকশা করা যায়। সাধারণভাবে বলা হয়, এই কাজটি digital circuit নকশাকে “অভিজ্ঞতার কারিগরি” থেকে “হিসাবের বিজ্ঞানে” নিয়ে আসে। ইতিহাসবিদেরা অবশ্য মনে করিয়ে দেন, প্রায় একই সময়ে জাপানে Akira Nakashima আর সোভিয়েত ইউনিয়নে Victor Shestakov-ও স্বাধীনভাবে কাছাকাছি ধারণায় পৌঁছেছিলেন বলে জানা যায়।

এই পর্বে আমরা পুরো মডিউল ২-এর ভাষা তৈরি করব। পরের পর্ব ০৮-এ এই কাজগুলো transistor দিয়ে কীভাবে gate হয় (CMOS), পর্ব ০৯ আর ১০-এ বড় expression কীভাবে যন্ত্রের মতো নিয়মে সরল করা হয় (K-map, Quine-McCluskey), আর পর্ব ১১–১৩-এ এগুলো দিয়ে adder, multiplexer আর ALU বানানো হবে। ভিত্তি যদি এখানে শক্ত হয়, বাকিটা অনেক সহজ লাগবে।

২ · তিনটি মৌলিক কাজ — AND, OR, NOT আর সুইচের উপমা

একটি Boolean variable (চলক) এমন একটি নাম — A, B, C বা X — যার মান কেবল 0 অথবা 1. এর বাইরে কোনো মান নেই: ০.৫ নেই, −১ নেই, ২ নেই। চলকগুলো নিয়ে তিনটি মৌলিক কাজ করা যায়। প্রতিটি কাজ পুরোপুরি বোঝানো যায় একটি truth table দিয়ে — যেখানে ইনপুটের সব সম্ভাব্য মান সারি ধরে লেখা থাকে, আর পাশে ফল।

• AND (·): ফল 1 কেবল তখন, যখন সব ইনপুট 1. একে “Boolean গুণ” বলা হয়, কারণ 0 আর 1-এর সাধারণ গুণফলের সাথে হুবহু মেলে।
• OR (+): ফল 1, যদি অন্তত একটি ইনপুট 1. একে “Boolean যোগ” বলা হয় — তবে সাবধান, 1 + 1 = 1, ২ নয়। এখানে “+” মানে “অথবা”, পাটিগণিতের যোগ নয়।
• NOT (′): একটি মাত্র ইনপুট, আর ফল তার উল্টো। A′-কে বলে A-এর complement.

দুইয়ের বেশি ইনপুটেও একই নিয়ম: A · B · C = 1 কেবল তিনটিই 1 হলে; A + B + C = 0 কেবল তিনটিই 0 হলে। n টি ইনপুটের truth table-এ সারি থাকে ২ⁿ টি — ২ ইনপুটে ৪, ৩ ইনপুটে ৮, ৪ ইনপুটে ১৬. সারিগুলো আমরা সবসময় binary গোনার ক্রমে লিখব (000, 001, 010 …), যাতে সারি নম্বর আর ইনপুটের binary মান একই হয় — এই অভ্যাসটি অংশ ৭-এ খুব কাজে লাগবে।

৩ · বাকি চারটি পরিচিত কাজ, আর এই পর্বের চিহ্ন

তিনটি মৌলিক কাজ জুড়ে আরও চারটি কাজ তৈরি হয়, যেগুলো এত বেশি ব্যবহৃত যে প্রতিটির আলাদা নাম আর আলাদা gate আছে:

• XOR (exclusive OR): ফল 1, যদি ইনপুট দুটি আলাদা হয়। মৌলিক কাজে লিখলে A ⊕ B = A′B + AB′. বহু ইনপুটে XOR = 1 হয়, যদি বিজোড় সংখ্যক ইনপুট 1 হয় — তাই parity হিসাবে (Computer Networks কোর্সের error detection পর্ব) আর binary যোগে (পর্ব ১১) এটিই মূল উপাদান।
• XNOR: XOR-এর উল্টো — ইনপুট দুটি সমান হলে 1. তাই একে “equivalence” gate-ও বলা হয়: (A ⊕ B)′ = AB + A′B′. দুটি সংখ্যা সমান কি না তুলনা করার circuit বিট-বিট XNOR দিয়েই শুরু হয়।
• NAND = NOT-AND: AND-এর ফল উল্টে দেওয়া। কেবল দুটিই 1 হলে 0.
• NOR = NOT-OR: OR-এর ফল উল্টে দেওয়া। কেবল দুটিই 0 হলে 1.

NAND আর NOR-কে কেন আলাদা মর্যাদা দেওয়া হয়, তার দুটি কারণ আছে। প্রথমত, এদের যেকোনো একটি দিয়েই সব Boolean function বানানো যায় (অংশ ৮-এ প্রমাণ)। দ্বিতীয়ত, CMOS প্রযুক্তিতে transistor-এর স্বাভাবিক গঠনই উল্টানো ফল দেয়, তাই NAND আর NOR বানাতে AND বা OR-এর চেয়ে কম transistor লাগে, আর এরা দ্রুতও হয় — বিস্তারিত পর্ব ০৮-এ।

চিহ্নের নিয়ম — এই পর্বের convention

বিভিন্ন বই আর দেশে Boolean চিহ্ন আলাদা, তাই শুরুতেই পরিষ্কার করে রাখি এই পর্বে আমরা কী লিখব:

ওপরে দাগ (overbar) বইয়ে সুন্দর দেখায়, কিন্তু ফোনের পর্দায় আর সাধারণ লেখায় ভাঙে; তাই এই কোর্সে আমরা prime (′) ব্যবহার করব। খেয়াল করুন, (AB)′ আর A′B′ সম্পূর্ণ আলাদা জিনিস — প্রথমটিতে পুরো গুণফলের ওপর NOT, দ্বিতীয়টিতে আলাদা দুটি NOT. ওপর-দাগের লেখায় এই পার্থক্য দাগের দৈর্ঘ্য দিয়ে বোঝানো হয়, আমাদের লেখায় বন্ধনী দিয়ে।

Operator precedence (কোন কাজ আগে হবে) সাধারণ বীজগণিতের মতোই: বন্ধনী → NOT → AND → OR. অর্থাৎ A + B · C′ মানে A + (B · (C′)) — আগে C-এর NOT, তারপর B-এর সাথে AND, শেষে A-এর সাথে OR. XOR-এর precedence নিয়ে বইগুলো একমত নয়; C ভাষায় & আগে, তারপর ^, তারপর |. এই পর্বের JS tool-ও সেই ক্রম মানে, তবে নিরাপদ অভ্যাস হলো XOR-এর চারপাশে সবসময় বন্ধনী দেওয়া।

৪ · Postulate আর সূত্র — Huntington থেকে De Morgan

সাধারণ বীজগণিতের মতো Boolean algebra-ও কয়েকটি মৌলিক “মেনে নেওয়া সত্য” দিয়ে শুরু হয় — এগুলোকে বলে postulate বা axiom. বাকি সব সূত্র এগুলো থেকে প্রমাণ করা হয়। Huntington-এর (১৯০৪) পরিচিত একটি সেট, যা বেশিরভাগ digital logic পাঠ্যবই ব্যবহার করে, সংক্ষেপে এমন — একটি সেট B, যাতে অন্তত দুটি আলাদা উপাদান 0 আর 1, আর দুটি কাজ + আর ·:

1. Closure: B-এর যেকোনো দুটি উপাদানের + বা · ফলও B-তেই থাকে।
2. Identity: A + 0 = A এবং A · 1 = A.
3. Commutative: A + B = B + A এবং A · B = B · A.
4. Distributive: A · (B + C) = AB + AC এবং A + BC = (A + B)(A + C).
5. Complement: প্রতিটি A-এর জন্য একটি A′ আছে, যাতে A + A′ = 1 এবং A · A′ = 0.

লক্ষ করুন, associative নিয়ম (A + (B + C) = (A + B) + C) এখানে নেই — Huntington দেখিয়েছিলেন, এটি বাকিগুলো থেকে প্রমাণ করা যায়, তাই একে theorem ধরা হয়। আরও লক্ষ করুন, প্রতিটি postulate জোড়ায় আছে: একটির + আর · এবং 0 আর 1 অদলবদল করলে অন্যটি পাওয়া যায়। এই মজার মিলটির নাম duality, অংশ ৫-এর বিষয়।

প্রধান সূত্রের তালিকা

কয়েকটি সূত্র সাধারণ বীজগণিতের সাথে মেলে (commutative, associative, A(B + C) = AB + AC), আবার কয়েকটি একেবারেই মেলে না। Idempotent বলে A + A = A — সাধারণ বীজগণিতে x + x = 2x. আর সবচেয়ে চমকপ্রদ হলো দ্বিতীয় distributive নিয়ম A + BC = (A + B)(A + C): সাধারণ সংখ্যায় ২ + ৩ × ৪ = ১৪, কিন্তু (২ + ৩)(২ + ৪) = ৩০. সাধারণ বীজগণিতে এর কোনো প্রতিরূপ নেই; Boolean algebra-য় এটি postulate. এর কারণ — এখানে “যোগ” মানে “অথবা”, আর OR-ও AND-এর ওপর বণ্টিত হয়, ঠিক যেমন AND বণ্টিত হয় OR-এর ওপর। এই দুই দিকের সমতাই Boolean algebra-কে সাধারণ বীজগণিত থেকে আলাদা আর সুন্দর করে।

প্রমাণের দুই পথ

পথ ১ — perfect induction (truth table দিয়ে প্রমাণ): চলকের মান যেহেতু শুধু 0 বা 1, n চলকের একটি সূত্রের দুই পাশ সব ২ⁿ টি সারিতে মিলিয়ে দেখলেই প্রমাণ শেষ। এটি “উদাহরণ দিয়ে প্রমাণ” নয় — সব সম্ভাব্য ক্ষেত্র পরীক্ষা করা, তাই সম্পূর্ণ বৈধ প্রমাণ। নিচে De Morgan-এর প্রথম সূত্রটি সারি ধরে প্রমাণ করা হলো — প্রতিটি ধাপে “পরে” চাপুন:

 A B │ A+B │ (A+B)' ║ A' B' │ A'B'
-----┼-----┼--------╫-------┼-----
 0 0 │  ?  │   ?    ║ ?  ?  │  ?
 0 1 │  ?  │   ?    ║ ?  ?  │  ?
 1 0 │  ?  │   ?    ║ ?  ?  │  ?
 1 1 │  ?  │   ?    ║ ?  ?  │  ?
  left side          right side

 A B │ A+B │ (A+B)' ║ A' B' │ A'B'
-----┼-----┼--------╫-------┼-----
 0 0 │  0  │   1    ║ 1  1  │  1   equal
 0 1 │  ?  │   ?    ║ ?  ?  │  ?
 1 0 │  ?  │   ?    ║ ?  ?  │  ?
 1 1 │  ?  │   ?    ║ ?  ?  │  ?

 A B │ A+B │ (A+B)' ║ A' B' │ A'B'
-----┼-----┼--------╫-------┼-----
 0 0 │  0  │   1    ║ 1  1  │  1   equal
 0 1 │  1  │   0    ║ 1  0  │  0   equal
 1 0 │  ?  │   ?    ║ ?  ?  │  ?
 1 1 │  ?  │   ?    ║ ?  ?  │  ?

 A B │ A+B │ (A+B)' ║ A' B' │ A'B'
-----┼-----┼--------╫-------┼-----
 0 0 │  0  │   1    ║ 1  1  │  1   equal
 0 1 │  1  │   0    ║ 1  0  │  0   equal
 1 0 │  1  │   0    ║ 0  1  │  0   equal
 1 1 │  ?  │   ?    ║ ?  ?  │  ?

 A B │ A+B │ (A+B)' ║ A' B' │ A'B'
-----┼-----┼--------╫-------┼-----
 0 0 │  0  │   1    ║ 1  1  │  1   equal
 0 1 │  1  │   0    ║ 1  0  │  0   equal
 1 0 │  1  │   0    ║ 0  1  │  0   equal
 1 1 │  1  │   0    ║ 0  0  │  0   equal

(A+B)' column : 1 0 0 0
A'B'   column : 1 0 0 0   -> identical in all 4 rows
=> (A + B)' = A'B'   proved by perfect induction
dual (swap + and ·):  (AB)' = A' + B'

পথ ২ — বীজগাণিতিক প্রমাণ: postulate আর আগে প্রমাণ করা সূত্র ব্যবহার করে এক পাশ থেকে আরেক পাশে যাওয়া। প্রতিটি ধাপে কোন নিয়ম ব্যবহার করলেন, তা লেখা বাধ্যতামূলক — পরীক্ষায় নম্বর থাকে ঠিক সেখানেই। কয়েকটি উদাহরণ:

• Idempotent, A + A = A: A + A = (A + A) · 1 [identity] = (A + A)(A + A′) [complement] = A + AA′ [distributive, দ্বিতীয় রূপ] = A + 0 [complement] = A [identity].
• Null, A + 1 = 1: A + 1 = (A + 1) · 1 = (A + 1)(A + A′) = A + 1 · A′ [distributive] = A + A′ = 1.
• Absorption, A + AB = A: A + AB = A · 1 + A · B [identity] = A(1 + B) [distributive] = A · 1 [null] = A.
• Redundant literal, A + A′B = A + B: A + A′B = (A + A′)(A + B) [distributive, দ্বিতীয় রূপ] = 1 · (A + B) = A + B.
• দ্বিতীয় distributive-এর যাচাই (ডান থেকে বাঁয়ে): (A + B)(A + C) = AA + AC + AB + BC = A + AC + AB + BC [idempotent] = A(1 + C + B) + BC = A · 1 + BC = A + BC.
• Consensus, AB + A′C + BC = AB + A′C: BC = BC · 1 = BC(A + A′) = ABC + A′BC. তাহলে বাম পাশ = AB + A′C + ABC + A′BC = AB(1 + C) + A′C(1 + B) = AB + A′C. অর্থাৎ BC পদটি (“consensus term”) অপ্রয়োজনীয় — AB আর A′C-এর মধ্যেই এটি লুকিয়ে আছে।

De Morgan — n চলকে সাধারণীকরণ

De Morgan-এর সূত্র যেকোনো সংখ্যক চলকে খাটে:

প্রমাণ (n-এর ওপর induction): n = ২ হলে এটি ওপরে প্রমাণ করা সূত্র। ধরি n − ১ চলকে সত্য। X = A₁ + … + A_n−1 লিখি (associative নিয়মে বন্ধনী যেভাবেই দিই, ফল এক)। তাহলে (X + A_n)′ = X′ A_n′ [দুই চলকের De Morgan] = A₁′ … A_n−1′ A_n′ [ধরে নেওয়া অংশ]। দ্বিতীয় রূপটি duality থেকেই আসে। মুখে মনে রাখার নিয়ম: “দাগ ভাঙুন, চিহ্ন বদলান” — পুরো expression-এর ওপরের NOT ভেঙে প্রতিটি অংশে নামিয়ে দিন, আর + হয়ে যায় ·, · হয়ে যায় +. যেমন (AB + C′D)′ = (AB)′ · (C′D)′ = (A′ + B′)(C + D′).

হাতে প্রমাণ শিখলেন; এবার যন্ত্রকে দিয়ে সব সারি পরীক্ষা করাই। নিচের ছোট “প্রমাণ-যন্ত্র” দুই পাশের function নিয়ে সব ২ⁿ সারি মেলায়, আর না মিললে ঠিক কোন সারিতে ভাঙল — অর্থাৎ counterexample — দেখায়। শেষ দুটি লাইনে ইচ্ছা করে দুটি ভুল “সূত্র” রাখা হয়েছে, যা ছাত্রছাত্রী আর AI দুজনেই প্রায়ই লেখে। Run চাপুন:

// Perfect induction: an identity is true iff both sides agree on ALL 2^n rows.
const N = x => 1 - x;                            // NOT on 0/1
function prove(name, lhs, rhs) {
  const n = lhs.length, bad = [];                // n = number of variables
  for (let r = 0; r < 1 << n; r++) {
    const v = Array.from({ length: n }, (_, j) => (r >> (n - 1 - j)) & 1);
    if (lhs(...v) !== rhs(...v)) bad.push(v.join(""));
  }
  console.log((bad.length ? "FALSE " : "TRUE  ") + name.padEnd(34) +
    `${1 << n} rows` + (bad.length ? `, counterexample ${"ABC".slice(0, n)} = ${bad.join(", ")}` : ""));
}
prove("De Morgan (A+B)' = A'B'",  (A, B) => N(A | B), (A, B) => N(A) & N(B));
prove("De Morgan (AB)' = A'+B'",  (A, B) => N(A & B), (A, B) => N(A) | N(B));
prove("De Morgan 3 vars (A+B+C)'", (A, B, C) => N(A | B | C), (A, B, C) => N(A) & N(B) & N(C));
prove("Absorption A + AB = A",    (A, B) => A | (A & B), (A, B) => A);
prove("Absorption A(A+B) = A",    (A, B) => A & (A | B), (A, B) => A);
prove("A + A'B = A + B",          (A, B) => A | (N(A) & B), (A, B) => A | B);
prove("Consensus AB+A'C+BC",      (A, B, C) => (A & B) | (N(A) & C) | (B & C),
                                  (A, B, C) => (A & B) | (N(A) & C));
prove("A + BC = (A+B)(A+C)",      (A, B, C) => A | (B & C), (A, B, C) => (A | B) & (A | C));
prove("A + BC = AB + C   ?",      (A, B, C) => A | (B & C), (A, B, C) => (A & B) | C);
prove("(AB)' = A'B'   ?",         (A, B) => N(A & B), (A, B) => N(A) & N(B));

TRUE  De Morgan (A+B)' = A'B'           4 rows
TRUE  De Morgan (AB)' = A'+B'           4 rows
TRUE  De Morgan 3 vars (A+B+C)'         8 rows
TRUE  Absorption A + AB = A             4 rows
TRUE  Absorption A(A+B) = A             4 rows
TRUE  A + A'B = A + B                   4 rows
TRUE  Consensus AB+A'C+BC               8 rows
TRUE  A + BC = (A+B)(A+C)               8 rows
FALSE A + BC = AB + C   ?               8 rows, counterexample ABC = 001, 100
FALSE (AB)' = A'B'   ?                  4 rows, counterexample AB = 01, 10

৫ · Duality — এক সূত্রের বদলে দুটি

একটি Boolean expression-এর dual পেতে তিনটি কাজ করুন: প্রতিটি + কে · বানান, প্রতিটি · কে + বানান, আর প্রতিটি 0 কে 1 ও 1 কে 0 বানান। চলক আর তাদের prime যেমন আছে তেমনই থাকবে। Duality principle বলে: কোনো সূত্র সত্য হলে তার dual-ও সত্য।

কেন? কারণ Huntington-এর প্রতিটি postulate নিজেই জোড়ায় আছে, আর প্রতিটি জোড়ার একটি আরেকটির dual (অংশ ৪-এর তালিকা দেখুন)। কোনো সূত্রের প্রমাণের প্রতিটি ধাপে যদি আমরা dual postulate ব্যবহার করি, তাহলে একই দৈর্ঘ্যের একটি প্রমাণ পাই, যা dual সূত্রটি প্রমাণ করে। অর্থাৎ প্রতিটি প্রমাণ বিনা খরচে দুটি সূত্র দেয়।

৬ · বীজগাণিতিক সরলীকরণ — প্রতিটি ধাপের কারণসহ

সূত্র শেখার আসল উদ্দেশ্য circuit ছোট করা। একটি expression-এর প্রতিটি পদ মানে একটি AND gate, প্রতিটি literal (চলক বা তার complement, যেমন A বা B′) মানে সেই gate-এর একটি ইনপুট-তার। কম পদ আর কম literal মানে কম gate, কম transistor, কম জায়গা, কম বিদ্যুৎ, আর প্রায়ই কম delay. কারখানায় একটি chip লক্ষ লক্ষ কপি তৈরি হয় — প্রতিটি কপিতে কয়েকটি gate বাঁচানো মানে বিশাল সাশ্রয়।

নিচের function-টি পরীক্ষায় খুব পরিচিত ধাঁচের — চারটি পদ, প্রতিটিতে তিনটি literal. দেখা যাক এটি আসলে কতটা ছোট:

F = A'B'C + A'BC + AB'C + ABC
    4 terms, 12 literals
    every term contains C

F = (A'B'C + A'BC) + (AB'C + ABC)
     └ both have A'C ┘   └ both have AC ┘
law: commutative + associative

F = A'C(B' + B) + AC(B' + B)
law: distributive  XY + XZ = X(Y + Z)

F = A'C · 1 + AC · 1
law: complement  X + X' = 1
  = A'C + AC
law: identity    X · 1 = X

F = C(A' + A)      distributive
  = C · 1           complement
  = C               identity

original terms = rows 001, 011, 101, 111
               = Σm(1, 3, 5, 7)
these are exactly the rows with C = 1
12 literals -> 1 literal, 4 AND + 1 OR gate -> a wire

এই “পার্থক্য শুধু একটি চলকে” কৌশলটিকে বলে adjacency বা combining: XY + XY′ = X. পর্ব ০৯-এর K-map আসলে এই কৌশলকে চোখে দেখার মতো ছকে সাজিয়ে দেয় — পাশাপাশি দুটি ঘর মানে ঠিক এমন একটি জোড়া।

পরীক্ষার ধাঁচে আরও কয়েকটি উদাহরণ

উদাহরণ ১. সরল করুন: F = AB + A(B + C) + B(B + C)

1. F = AB + AB + AC + BB + BC  [distributive]
2. = AB + AC + B + BC  [idempotent: AB + AB = AB, BB = B]
3. = AB + AC + B  [absorption: B + BC = B]
4. = B + AC  [absorption: B + AB = B]

উত্তর: F = B + AC (৫টি পদ থেকে ২টি)।

উদাহরণ ২. সরল করুন: F = (A + B)(A + B′)

দ্বিতীয় distributive নিয়মে F = A + BB′ = A + 0 = A [distributive, complement, identity]. এটি আগের XY + XY′ = X কৌশলের dual: (X + Y)(X + Y′) = X.

উদাহরণ ৩. সরল করুন: F = (A′ + B)′ + (A + B)′

1. (A′ + B)′ = A″B′ = AB′  [De Morgan, involution]
2. (A + B)′ = A′B′  [De Morgan]
3. F = AB′ + A′B′ = B′(A + A′) = B′  [distributive, complement, identity]

উত্তর: F = B′.

উদাহরণ ৪. সরল করুন: F = XY + X′Z + YZ

X আর X′ দুটি পদে আছে, বাকি অংশ Y আর Z — তাদের গুণফল YZ, যা ঠিক তৃতীয় পদ। Consensus theorem অনুযায়ী এটি মুছে যায়: F = XY + X′Z. পরীক্ষায় শুধু “consensus” লিখলেই চলে না — অংশ ৪-এর মতো YZ = YZ(X + X′) দিয়ে খুলে দেখালে পূর্ণ নম্বর নিশ্চিত।

উদাহরণ ৫ (complement বের করা). F = AB + C′D হলে F′ কত?

F′ = (AB + C′D)′ = (AB)′ · (C′D)′ = (A′ + B′)(C + D′) [De Morgan দুবার, involution]. চাইলে গুণ করে SOP-এ লেখা যায়: A′C + A′D′ + B′C + B′D′.

৭ · Canonical form — minterm, maxterm, SOP আর POS

একই function অসংখ্য রূপে লেখা যায় — A′C + AB, A′B′C + A′BC + ABC′ + ABC, (A + C)(A′ + B) সবই একই truth table দেয়। দুটি expression একই function কি না দ্রুত বোঝার জন্য এমন একটি “প্রমিত” রূপ দরকার, যা প্রতিটি function-এর জন্য অনন্য। এমন রূপকে বলে canonical form, আর তার দুটি ধরন আছে।

Minterm আর maxterm

n চলকের একটি minterm হলো এমন একটি AND-পদ, যাতে প্রতিটি চলক ঠিক একবার আছে (সরল বা উল্টো রূপে), আর যা truth table-এর ঠিক একটি সারিতে 1 হয়। নিয়ম: সারিতে যে চলক 0, তাকে উল্টো (prime) লিখুন; যে চলক 1, তাকে সরল লিখুন। সারি নম্বর i হলে তাকে লেখা হয় m_i.

Maxterm ঠিক উল্টো: এমন একটি OR-পদ, যাতে প্রতিটি চলক একবার আছে, আর যা ঠিক একটি সারিতে 0 হয়। নিয়মও উল্টো: সারিতে যে চলক 0, তাকে সরল লিখুন; যে চলক 1, তাকে উল্টো লিখুন। লেখা হয় M_i. লক্ষ করুন, M_i = (m_i)′ — De Morgan দিয়ে সরাসরি দেখা যায়।

SOP আর POS

• Sum of products (SOP): কয়েকটি AND-পদের OR — যেমন A′C + AB. যদি প্রতিটি পদ একটি পূর্ণ minterm হয়, তাকে বলে canonical SOP (বা sum of minterms), আর সংক্ষেপে লেখা হয় F = Σm(1, 3, 6, 7).
• Product of sums (POS): কয়েকটি OR-পদের AND — যেমন (A + C)(A′ + B). প্রতিটি পদ পূর্ণ maxterm হলে canonical POS (product of maxterms), সংক্ষেপে F = ΠM(0, 2, 4, 5).
• Standard বনাম canonical: standard SOP বা POS-এ পদগুলোতে সব চলক থাকা জরুরি নয় (A′C + AB); canonical-এ প্রতিটি পদে প্রতিটি চলক থাকতেই হবে। canonical রূপ অনন্য কিন্তু বড়; ন্যূনতম standard রূপ ছোট, কিন্তু সবসময় অনন্য নয়।

কেন এটি কাজ করে (প্রমাণের রূপরেখা): F-এর যে সারিগুলোতে F = 1, তাদের minterm-গুলো OR করি। যেকোনো সারি r নিন। যদি F(r) = 1, তাহলে m_r পদটি এই OR-এ আছে আর r-এ 1 দেয়, তাই পুরো OR = 1. যদি F(r) = 0, তাহলে OR-এর প্রতিটি minterm অন্য কোনো সারির, আর r-এ প্রতিটি 0 দেয়, তাই OR = 0. অর্থাৎ OR-টি প্রতিটি সারিতে F-এর সমান — perfect induction. POS-এর যুক্তি হুবহু dual: প্রতিটি maxterm ঠিক নিজের সারিতে 0 দেয়, তাই 0-সারিগুলোর maxterm-এর AND ঠিক সেখানেই 0. এখান থেকে একটি মূল্যবান সিদ্ধান্তও আসে: যেকোনো truth table-কে AND, OR আর NOT দিয়ে লেখা যায় — অংশ ৮-এ এটিই functional completeness.

SOP আর POS-এর সম্পর্কও সরল: যে সারি Σm-তে নেই, সেটি ΠM-এ আছে। n চলকে মোট সারি ২ⁿ, তাই Σm-এর তালিকা জানলে ΠM-এর তালিকা হলো “বাকি সব সংখ্যা”। আর F′-এর Σm হলো F-এর ΠM-এর একই সংখ্যাগুলো। এবার পুরো পথটি একটি তিন চলকের function দিয়ে দেখি:

row │ A B C │ F
----┼-------┼---
 0  │ 0 0 0 │ 0
 1  │ 0 0 1 │ 1
 2  │ 0 1 0 │ 0
 3  │ 0 1 1 │ 1
 4  │ 1 0 0 │ 0
 5  │ 1 0 1 │ 0
 6  │ 1 1 0 │ 1
 7  │ 1 1 1 │ 1

row │ A B C │ F
 1  │ 0 0 1 │ 1
 3  │ 0 1 1 │ 1
 6  │ 1 1 0 │ 1
 7  │ 1 1 1 │ 1
=> F = Σm(1, 3, 6, 7)

rule: 0 -> X' , 1 -> X
 0 0 1  ->  A'B'C   (m1)
 0 1 1  ->  A'BC    (m3)
 1 1 0  ->  ABC'    (m6)
 1 1 1  ->  ABC     (m7)

F = m1 + m3 + m6 + m7
  = A'B'C + A'BC + ABC' + ABC

rule: 0 -> X , 1 -> X'
 0 0 0  ->  (A + B + C)     (M0)
 0 1 0  ->  (A + B' + C)    (M2)
 1 0 0  ->  (A' + B + C)    (M4)
 1 0 1  ->  (A' + B + C')   (M5)

F = ΠM(0, 2, 4, 5)
  = (A+B+C)(A+B'+C)(A'+B+C)(A'+B+C')
{1,3,6,7} and {0,2,4,5} together = all 8 rows

SOP: A'B'C + A'BC = A'C ,  ABC' + ABC = AB
     F = A'C + AB
POS: (A+B+C)(A+B'+C)   = A + C
     (A'+B+C)(A'+B+C') = A' + B
     F = (A + C)(A' + B)
"if A then B else C" -> a 2-to-1 mux

এবার এই কাজ যন্ত্রকে দিয়ে করাই। নিচের simulator একটি ছোট parser — লেখা expression পড়ে গাছের মতো কাঠামো বানায়, প্রতিটি সারিতে মান হিসাব করে truth table ছাপে, আর Σm ও ΠM তালিকা দেয়। নিয়ম: NOT = ' বা !, AND = পাশাপাশি লেখা বা &, XOR = ^, OR = +; বন্ধনী চলবে, চলক বড় হাতের এক অক্ষর (২–৪টি)। শেষ লাইনে নিজের expression বসিয়েও চালাতে পারেন:

// Truth-table generator: ! or ' = NOT, & or juxtaposition = AND, ^ = XOR, + = OR
function parse(src) {
  const t = src.replace(/\s+/g, "").split(""); let i = 0;
  const eat = c => (t[i] === c ? (i++, true) : false);
  function atom() {                                          // highest precedence
    let n; if (eat("!")) n = { op: "!", a: atom() };
    else if (eat("(")) { n = expr(); if (!eat(")")) throw Error("missing )"); }
    else if (/[A-Z01]/.test(t[i] || "")) n = /[01]/.test(t[i]) ? { k: +t[i++] } : { v: t[i++] };
    else throw Error("unexpected '" + (t[i] || "end") + "' at " + i);
    while (eat("'")) n = { op: "!", a: n };                 // postfix prime: A'
    return n;
  }
  const chain = (op, sub, implicit) => () => { let n = sub();       // left-assoc chain
    while (eat(op) || (implicit && /[A-Z01(!]/.test(t[i] || ""))) n = { op, a: n, b: sub() };
    return n; };
  const and = chain("&", atom, true), xor = chain("^", and), expr = chain("+", xor);
  const tree = expr(); if (i < t.length) throw Error("extra '" + t[i] + "'");
  return { tree, vars: [...new Set(src.match(/[A-Z]/g))].sort() };
}
function ev(n, e) { if ("v" in n) return e[n.v]; if ("k" in n) return n.k;
  const a = ev(n.a, e); if (n.op === "!") return 1 - a;
  const b = ev(n.b, e); return n.op === "&" ? a & b : n.op === "^" ? a ^ b : a | b;
}
function table(src, show) {
  const { tree, vars } = parse(src), k = vars.length, on = [], off = [];
  if (show) console.log(vars.join(" ") + " | F    F = " + src);
  for (let r = 0; r < 1 << k; r++) {
    const e = {}; vars.forEach((v, j) => (e[v] = (r >> (k - 1 - j)) & 1));
    const f = ev(tree, e); (f ? on : off).push(r);
    if (show) console.log(vars.map(v => e[v]).join(" ") + " | " + f + "    row " + r);
  }
  console.log(`${src}  =  Σm(${on})  =  ΠM(${off})`);
}
table("A'C + AB", true);
["A'B + AB'", "AB + BC + AC", "(A + B)' ^ C", "!(A&B) + C'D"].forEach(s => table(s));

A B C | F    F = A'C + AB
0 0 0 | 0    row 0
0 0 1 | 1    row 1
0 1 0 | 0    row 2
0 1 1 | 1    row 3
1 0 0 | 0    row 4
1 0 1 | 0    row 5
1 1 0 | 1    row 6
1 1 1 | 1    row 7
A'C + AB  =  Σm(1,3,6,7)  =  ΠM(0,2,4,5)
A'B + AB'  =  Σm(1,2)  =  ΠM(0,3)
AB + BC + AC  =  Σm(3,5,6,7)  =  ΠM(0,1,2,4)
(A + B)' ^ C  =  Σm(0,3,5,7)  =  ΠM(1,2,4,6)
!(A&B) + C'D  =  Σm(0,1,2,3,4,5,6,7,8,9,10,11,13)  =  ΠM(12,14,15)

শেষ simulator-টি উল্টো দিকে যায়: একটি minterm তালিকা থেকে canonical SOP আর POS-এর লেখা তৈরি করে, তারপর সেই লেখা দুটিকেই আবার পড়ে প্রতিটি সারিতে মান হিসাব করে — দেখায় যে দুটি রূপ আর মূল তালিকা সব সারিতে এক:

// Minterm list -> canonical SOP and POS strings, then evaluate the STRINGS back.
const VARS = "ABCD";
function forms(n, ms) {
  const vs = VARS.slice(0, n).split(""), bit = (r, j) => (r >> (n - 1 - j)) & 1;
  const lit = (v, keep) => (keep ? v : v + "'");
  const sop = ms.map(r => vs.map((v, j) => lit(v, bit(r, j))).join("")).join(" + ");
  const Ms = [...Array(1 << n).keys()].filter(r => !ms.includes(r));
  const pos = Ms.map(r => "(" + vs.map((v, j) => lit(v, !bit(r, j))).join("+") + ")").join("");
  return { vs, sop, pos, Ms, bit };
}
function evalSop(s, env) {                       // "A'BC + AB'C" -> OR of ANDs
  return s.split(" + ").some(term => (term.match(/[A-Z]'?/g)).every(l =>
    l.length === 2 ? !env[l[0]] : !!env[l[0]])) ? 1 : 0;
}
function evalPos(s, env) {                       // "(A+B+C)(A'+B+C)" -> AND of ORs
  return s.slice(1, -1).split(")(").every(sum => sum.split("+").some(l =>
    l.length === 2 ? !env[l[0]] : !!env[l[0]])) ? 1 : 0;
}
for (const [n, ms] of [[3, [1, 3, 6, 7]], [3, [0, 2, 5, 7]], [2, [1, 2]]]) {
  const { vs, sop, pos, Ms, bit } = forms(n, ms);
  let col = "", ok = true;
  for (let r = 0; r < 1 << n; r++) {
    const env = {}; vs.forEach((v, j) => (env[v] = bit(r, j)));
    const a = evalSop(sop, env), b = evalPos(pos, env);
    col += a; ok = ok && a === b && a === (ms.includes(r) ? 1 : 0);
  }
  console.log(`F = Σm(${ms}) = ΠM(${Ms})`);
  console.log(`  SOP: ${sop}`);
  console.log(`  POS: ${pos}`);
  console.log(`  F column (row 0..${(1 << n) - 1}) = ${col}  SOP == POS == list: ${ok}`);
}

F = Σm(1,3,6,7) = ΠM(0,2,4,5)
  SOP: A'B'C + A'BC + ABC' + ABC
  POS: (A+B+C)(A+B'+C)(A'+B+C)(A'+B+C')
  F column (row 0..7) = 01010011  SOP == POS == list: true
F = Σm(0,2,5,7) = ΠM(1,3,4,6)
  SOP: A'B'C' + A'BC' + AB'C + ABC
  POS: (A+B+C')(A+B'+C')(A'+B+C)(A'+B'+C)
  F column (row 0..7) = 10100101  SOP == POS == list: true
F = Σm(1,2) = ΠM(0,3)
  SOP: A'B + AB'
  POS: (A+B)(A'+B')
  F column (row 0..3) = 0110  SOP == POS == list: true

৮ · কয়টি function সম্ভব, আর কোন gate-সেট দিয়ে সব বানানো যায়

n চলকের মোট Boolean function: ২^২ⁿ

একটি Boolean function পুরোপুরি ঠিক হয় তার truth table-এর আউটপুট কলাম দিয়ে। n চলকের টেবিলে সারি ২ⁿ টি, আর প্রতিটি সারির আউটপুট স্বাধীনভাবে 0 বা 1 হতে পারে। তাই সম্ভাব্য আউটপুট কলাম — অর্থাৎ আলাদা function — মোট ২^২ⁿ টি। n = ১-এ ৪টি (0, 1, A, A′), n = ২-এ ১৬টি, n = ৩-এ ২৫৬টি, n = ৪-এ ৬৫,৫৩৬টি, আর n = ৫-এ ৪২৯ কোটিরও বেশি (২^৩২)। দুই চলকের ১৬টি function-এর পুরো তালিকা:

এখানে F_k-এর k হলো আউটপুট কলামটিকে ওপর থেকে নিচে binary সংখ্যা হিসেবে পড়লে যা হয় (Mano-র পাঠ্যবইয়ের ধারা)। ১৬টির মধ্যে ২টি constant, ৪টি একটি চলকেরই (A, A′, B, B′), আর বাকি ১০টি সত্যিকারের দুই-চলকের function — যার মধ্যে ৬টি (AND, OR, XOR, NAND, NOR, XNOR) আলাদা gate হিসেবে বাজারে পাওয়া যায়।

Functional completeness — কোন সেট যথেষ্ট

একটি gate-সেটকে functionally complete বলা হয়, যদি শুধু সেই gate-গুলো (যতবার খুশি) জুড়ে যেকোনো Boolean function বানানো যায়।

• {AND, OR, NOT} complete: অংশ ৭-এর প্রমাণ বলে, যেকোনো truth table-কে canonical SOP-এ লেখা যায় — যা শুধু AND, OR আর NOT ব্যবহার করে। (কোনো 1-সারি না থাকলে F = 0 = A · A′.) আসলে De Morgan বলে A + B = (A′B′)′, তাই শুধু {AND, NOT}-ও যথেষ্ট; একইভাবে {OR, NOT}.
• {NAND} একাই complete: NOT A = (A · A)′ = A NAND A. AND = NAND-এর ফল উল্টানো = (A NAND B) NAND (A NAND B). OR = (A′ · B′)′ = (A NAND A) NAND (B NAND B) [De Morgan]. NOT, AND আর OR পেলে বাকি সব আগের যুক্তিতেই পাওয়া যায়।
• {NOR} একাই complete: হুবহু dual যুক্তি — NOT A = A NOR A, OR = NOR-এর ফল উল্টানো, AND = (A′ + B′)′ = (A NOR A) NOR (B NOR B).
• {AND, OR} complete নয়: AND আর OR দুটিই monotone — কোনো ইনপুট 0 থেকে 1 করলে আউটপুট কখনো 1 থেকে 0 হয় না। তাই এদের যেকোনো জোড়াও monotone, আর NOT (যা 0-কে 1 আর 1-কে 0 করে) কখনো বানানো যায় না। শুধু {XOR}-ও complete নয়, তবে কারণটি আলাদা: সব ইনপুট 0 হলে XOR gate-এর যেকোনো জোড়ার আউটপুটও 0, তাই NOT বানানো যায় না।

এজন্যই NAND আর NOR-কে বলে universal gate. বাস্তব chip-এ এর গুরুত্ব বিশাল: নীতিগতভাবে একটি কারখানা কেবল একটি নিখুঁত NAND cell নকশা আর যাচাই করেই পুরো CPU বানাতে পারে। CMOS-এ কেন NAND আর NOR স্বাভাবিকভাবে সবচেয়ে সস্তা, আর NAND-NAND বা NOR-NOR রূপে কীভাবে SOP-POS বসে — পুরো আলোচনা পর্ব ০৮-এ।

৪টি চলকের truth table একটি ১৬-বিটের সংখ্যায়

একটি চমৎকার কৌশল দিয়ে Boolean algebra আর C-র bitwise operator এক হয়ে যায়। চার চলকের truth table-এ ১৬টি সারি, আর একটি ১৬-বিটের সংখ্যায় ১৬টি বিট। ধরি বিট r = সারি r-এ মান। তাহলে চলক A নিজেই একটি ১৬-বিটের “truth table”: যেসব সারিতে A = 1 (সারি ৮–১৫), সেখানে 1 — অর্থাৎ 0xFF00. তেমনি B = 0xF0F0, C = 0xCCCC, D = 0xAAAA. এখন একটি bitwise & একসাথে ১৬টি সারির AND করে! পর্ব ০৬-এ আপনি bit manipulation আর bitmask দেখেছেন; এখানে সেই bitmask-ই truth table:

#include <stdio.h>
#include <stdint.h>

/* Bit r of a mask = value of the function on row r (row r = ABCD in binary).
   One bitwise operation evaluates all 16 rows at once. */
#define A 0xFF00u
#define B 0xF0F0u
#define C 0xCCCCu
#define D 0xAAAAu
#define NOT(x) (~(x) & 0xFFFFu)

static void show(const char *name, uint16_t f) {
    printf("%-22s mask 0x%04X  minterms:", name, (unsigned)f);
    for (int r = 0; r < 16; r++)
        if ((f >> r) & 1u) printf(" %d", r);
    printf("  (%d ones)\n", __builtin_popcount(f));
}

int main(void) {
    show("F = A'C + AB", (uint16_t)((NOT(A) & C) | (A & B)));
    show("majority AB+BC+CA", (uint16_t)((A & B) | (B & C) | (C & A)));
    show("parity A^B^C^D", (uint16_t)(A ^ B ^ C ^ D));
    printf("De Morgan (A+B+C)' == A'B'C' : %s\n",
           NOT(A | B | C) == (NOT(A) & NOT(B) & NOT(C)) ? "yes" : "no");
    printf("Consensus AB+A'C+BC == AB+A'C : %s\n",
           ((A & B) | (NOT(A) & C) | (B & C)) == ((A & B) | (NOT(A) & C)) ? "yes" : "no");
    printf("A + BC == AB + C : %s\n", (A | (B & C)) == ((A & B) | C) ? "yes" : "no");
    for (int n = 1; n <= 5; n++)
        printf("n = %d variables: 2^(2^n) = %llu functions\n", n, 1ULL << (1u << n));
    return 0;
}

F = A'C + AB           mask 0xF0CC  minterms: 2 3 6 7 12 13 14 15  (8 ones)
majority AB+BC+CA      mask 0xFCC0  minterms: 6 7 10 11 12 13 14 15  (8 ones)
parity A^B^C^D         mask 0x6996  minterms: 1 2 4 7 8 11 13 14  (8 ones)
De Morgan (A+B+C)' == A'B'C' : yes
Consensus AB+A'C+BC == AB+A'C : yes
A + BC == AB + C : no
n = 1 variables: 2^(2^n) = 4 functions
n = 2 variables: 2^(2^n) = 16 functions
n = 3 variables: 2^(2^n) = 256 functions
n = 4 variables: 2^(2^n) = 65536 functions
n = 5 variables: 2^(2^n) = 4294967296 functions

৯ · প্রোগ্রামিংয়ে Boolean algebra — short-circuit, bitwise আর De Morgan

প্রতিটি if, while আর ফিল্টার-শর্ত একটি Boolean expression. তাই এই পর্বের সূত্রগুলো প্রোগ্রামারের প্রতিদিনের হাতিয়ার — তবে কয়েকটি বাড়তি নিয়ম মাথায় রাখতে হয়।

Logical বনাম bitwise operator (C)

• Logical &&, ||, !: পুরো সংখ্যাটিকে একটি সত্য-মিথ্যা হিসেবে দেখে (০ = মিথ্যা, বাকি সব = সত্য), আর ফল দেয় 0 বা 1.
• Bitwise &, |, ^, ~: প্রতিটি বিটে আলাদাভাবে Boolean কাজ করে — ৩২টি বিট মানে একসাথে ৩২টি স্বাধীন Boolean algebra. বিস্তারিত অনুশীলন আছে C কোর্সের বিটওয়াইজ অপারেশন পর্বে।

একটি ফাঁদ: a = 2, b = 4 হলে a && b = 1 (দুটিই অশূন্য), কিন্তু a & b = 0 (010 & 100-এ কোনো বিট মেলে না)। আরেকটি: !a = 0, কিন্তু ~a = −৩ — যা C-তে “সত্য”! আর C-র precedence-এ == আগে, & পরে, তাই x & 1 == 0 আসলে x & (1 == 0) = সবসময় 0 — এখানে বন্ধনী বাধ্যতামূলক।

Short-circuit evaluation

C, Java, JavaScript, Python — সব প্রচলিত ভাষায় && আর || হলো short-circuit: বাম পাশ দেখেই ফল নিশ্চিত হলে ডান পাশ আর হিসাবই হয় না। এটি সরাসরি null সূত্রের দুই রূপ: 0 · X = 0 আর 1 + X = 1, X যা-ই হোক। তাই if (p != NULL && p->count > 0) নিরাপদ — p শূন্য হলে p->count কখনো পড়া হয় না। কিন্তু এই কারণে প্রোগ্রামে commutative নিয়ম পুরোপুরি খাটে না: p->count > 0 && p != NULL লিখলে গাণিতিক অর্থ এক, কিন্তু প্রোগ্রাম crash করতে পারে। ডান পাশে side effect (ফাংশন ডাকা, i++) থাকলেও ক্রম বদলালে আচরণ বদলায়। Boolean algebra বলে “মান” কী হবে; প্রোগ্রামিং ভাষা বাড়তি বলে “কোনটি আগে হিসাব হবে”।

De Morgan দিয়ে শর্ত পরিষ্কার করা

শেষ সারির ভুলটি এত পরিচিত যে প্রায় প্রতিটি প্রোগ্রামার একবার করেছেন। ch != ' ' || ch != '\n': ch একসাথে space আর newline দুটি হতে পারে না, তাই দুটি শর্তের অন্তত একটি সবসময় সত্য — লুপ কখনো থামে না। De Morgan সঠিকভাবে প্রয়োগ করলে OR-এর জায়গায় AND আসে। একটি সুখবর: De Morgan শর্তের হিসাবের ক্রম বদলায় না (a আগে, b পরে), তাই short-circuit আচরণও অক্ষত থাকে।

SQL-এর NULL আর তিন-মানের যুক্তি

ডেটাবেসে Boolean algebra-র একটি গুরুত্বপূর্ণ ব্যতিক্রম আছে। SQL-এ কোনো মান NULL (অজানা) হলে x = 5-এর ফল TRUE বা FALSE নয়, UNKNOWN. এই তিন-মানের যুক্তিতে FALSE AND UNKNOWN = FALSE, TRUE OR UNKNOWN = TRUE, কিন্তু TRUE AND UNKNOWN = UNKNOWN, আর NOT UNKNOWN = UNKNOWN. De Morgan আর বেশিরভাগ সূত্র তবু খাটে, কিন্তু complement নিয়ম ভাঙে: x = 5 OR NOT (x = 5) NULL সারিতে UNKNOWN, আর WHERE কেবল TRUE সারি রাখে — ফলে “সব সারি” আসার কথা থাকলেও NULL সারিগুলো হারিয়ে যায়। বিস্তারিত আছে DBMS কোর্সের NULL পর্বে। একই রকম ফাঁদ আছে floating point-এ: NaN-এর সাথে প্রতিটি তুলনা মিথ্যা, তাই !(a < b) আর a >= b সবসময় এক নয় (পর্ব ২৩)।

১০ · AI-এর যুগে — Boolean উত্তর যাচাই করার অভ্যাস

Boolean algebra-র প্রশ্নে AI দ্রুত, সুন্দর করে সাজানো উত্তর দেয় — কিন্তু “দেখতে ঠিক” আর “সত্যিই ঠিক” এক নয়। সরলীকরণের মাঝের একটি ধাপে একটি prime চিহ্ন (′) হারালে পুরো উত্তর ভুল হয়ে যায়, আর ভাষা-মডেল এমন ভুল প্রায়ই করে। সুখবর হলো, এই বিষয়ের প্রতিটি দাবি যন্ত্রে শতভাগ যাচাইযোগ্য: ৪ চলক পর্যন্ত মাত্র ১৬টি সারি।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• শেষ উত্তরের truth table নিজে বের করে মূল Σm তালিকার সাথে প্রতিটি সারিতে মিলিয়েছি (বা অংশ ৭-এর simulator-এ চালিয়েছি)
• প্রতিটি সরলীকরণ ধাপে লেখা সূত্রের নাম সত্যিই সেই ধাপে খাটে কি না দেখেছি — বিশেষ করে De Morgan-এ চিহ্ন বদল
• minterm-এ 0 → prime, maxterm-এ 1 → prime — নিয়মটি অন্তত দুটি সারিতে পরীক্ষা করেছি
• Σm আর ΠM-এর তালিকা মিলে ঠিক ০ থেকে ২ⁿ − ১ পর্যন্ত সব সংখ্যা, কোনোটি বাদ বা দুবার নেই
• “সবচেয়ে ছোট রূপ” দাবিটি K-map (পর্ব ০৯) দিয়ে যাচাই করেছি; কোডের শর্ত বদলালে NULL, NaN আর short-circuit ক্রম পরীক্ষা করেছি