Boolean algebra-র গণিত — function, identity আর minimization

১ · Boolean function — {0, 1}ⁿ থেকে {0, 1}

HR-এর নিয়ম: “তিনটি শর্তের অন্তত দুটি পূরণ হলে অনুমতি।” এটি একটি নিয়ম যা প্রতিটি (M, O, T) ত্রয়ীকে 0 বা 1-এ পাঠায়। সাধারণভাবে বললে:

লেখার নিয়ম circuit-এর বইয়ের মতো: x + y মানে OR, xy বা x · y মানে AND, আর x′ মানে NOT (x-এর complement). Logic-এর ভাষায় এরা ∨, ∧, ¬; সেটের ভাষায় ∪, ∩ আর পূরক সেট। তিন ভাষার অভিধান এই:

অভিধানের শেষ সারিটি জরুরি: দুটি Boolean রাশি সমান মানে তাদের truth table এক, যা পর্ব ০৩-এর logical equivalence. তাই সেখানে প্রমাণ করা সব equivalence, যেমন De Morgan, এখানে Boolean সমীকরণ হিসেবে সত্য; প্রমাণগুলো আবার করছি না। এই পর্বের নতুন প্রশ্ন তিনটি: কয়টি function আছে, কোন axiom থেকে সব সূত্র আসে, আর একটি function-কে সবচেয়ে ছোট রাশিতে কীভাবে লেখা যায়।

1. প্রতিটি ইনপুট n-বিটের একটি string, আর প্রতিটি বিটের ২টি মান, তাই ইনপুট-সারি 2ⁿটি। — পর্ব ৩১-এর গুণের নিয়ম
2. একটি function মানে এই 2ⁿটি সারির প্রতিটিতে স্বাধীনভাবে একটি মান 0 বা 1 বসানো; আলাদা বাছাই আলাদা function, কারণ কোনো একটি সারিতে মান আলাদা। — সংজ্ঞা ১.১
3. তাই বাছাইয়ের সংখ্যা 2 · 2 ⋯ 2 (2ⁿ বার) = 2²ⁿ. ∎ — আবার গুণের নিয়ম

সংখ্যাটি দ্রুত বিস্ফোরিত হয়: n = 1-এ 4, n = 2-এ 16, n = 3-এ 256, n = 4-এ 65,536, n = 5-এ 4,294,967,296, আর n = 6-এ প্রায় 1.8 × 10¹⁹. তাই সব function-এর তালিকা করে কিছু খোঁজা ৫ চলকের পরেই অসম্ভব; দরকার গঠন আর উপপাদ্য।

B³-এর আটটি সারিকে একটি ঘনকের আটটি কোণ ভাবা যায়: দুটি কোণ একটি ধার দিয়ে যুক্ত, যদি তারা ঠিক এক বিটে আলাদা। এটি পর্ব ৩৬-এর hypercube Q₃. রিফান্ডের নিয়মে যে চারটি কোণে f = 1, সেগুলো ছবিতে সবুজ।

লক্ষ করুন, “MO” পদটি (ম্যানেজার আর অফিস সময়, 2FA যা-ই হোক) ঠিক দুটি কোণে 1: 110 আর 111, অর্থাৎ ঘনকের একটি ধার। k-টি literal-এর একটি গুণফল-পদ 2^n−kটি কোণের একটি “উপ-ঘনক” ঢাকে। এই ছবিটিই পরে K-map আর minimization-এর ভিত্তি।

২ · বিমূর্ত Boolean algebra — Huntington-এর axiom আর duality

{0, 1}, সেট আর বিটে একই সূত্র কেন খাটে? কারণ তিনটিই একটি সাধারণ কাঠামোর উদাহরণ। গণিতে এমন ক্ষেত্রে আমরা কয়েকটি axiom বেছে নিই, আর শুধু সেগুলো থেকে সব প্রমাণ করি; তখন প্রতিটি প্রমাণ সব উদাহরণে একসঙ্গে খাটে।

এই তালিকা Edward Huntington-এর ১৯০৪ সালের axiom-সেটের রূপ বলে পরিচিত (Huntington postulates). Associativity, অর্থাৎ (x + y) + z = x + (y + z), তালিকায় নেই: এটি axiom থেকেই প্রমাণ করা যায়, তবে প্রমাণটি দীর্ঘ, তাই এখানে বাদ রেখে ব্যবহার করছি। সাধারণ সংখ্যার সঙ্গে তফাত লক্ষ করুন: x + yz = (x + y)(x + z) সংখ্যায় মিথ্যা, এখানে axiom.

1. (ক) x + x = (x + x) · 1 = (x + x)(x + x′) = x + x · x′ = x + 0 = x. — H3, H4, H2-এর দ্বিতীয় রূপ (x + yz), H4, H3
2. (খ) x + 1 = (x + 1) · 1 = (x + 1)(x + x′) = x + 1 · x′ = x + x′ = 1. — H3, H4, H2, H1 আর H3 (1 · x′ = x′), H4
3. (গ) x + xy = x · 1 + xy = x(1 + y) = x(y + 1) = x · 1 = x. ∎ — H3, H2-এর প্রথম রূপ, H1, (খ), H3

1. y = y · 1 = y(x + x′) = yx + yx′. — H3, H4, H2
2. yx = xy = 0 = xx′, তাই y = xx′ + yx′ = x′x + x′y = x′(x + y). — অনুমান, H4, H1, H2
3. x + y = 1, তাই y = x′ · 1 = x′. — অনুমান, H3
4. x′ + x = 1 আর x′x = 0 (H1, H4), অর্থাৎ x নিজেই x′-এর complement-এর শর্ত মানে; অনন্যতায় (x′)′ = x. — ধাপ ১–৩ x′-এর জন্য
5. De Morgan: (x + y) + x′y′ = (x + y + x′)(x + y + y′) = (1 + y)(x + 1) = 1 · 1 = 1, আর (x + y) · x′y′ = (xx′)y′ + (yy′)x′ = 0 + 0 = 0. তাই x′y′ হলো x + y-এর complement. দ্বিতীয় সূত্রটি dual. ∎ — H2, associativity, H4, উপপাদ্য ২.২(খ) আর তার dual x · 0 = 0

শেষ ধাপে “dual” শব্দটি একটি শক্তিশালী নীতির দিকে ইশারা করে। প্রতিটি axiom জোড়ায় আসে: একটিতে + আর · অদলবদল করে, 0 আর 1 অদলবদল করে অন্যটি পাওয়া যায়।

প্রমাণের ধারণা: মূল প্রমাণটি সমীকরণের একটি শিকল, যার প্রতিটি ধাপ একটি axiom (বা আগে প্রমাণিত সূত্র) প্রয়োগ। পুরো শিকলের প্রতিটি রাশির dual নিন। H1–H4-এর প্রতিটি axiom-এর dual-ও তালিকায় আছে, তাই প্রতিটি নতুন ধাপ আবার একটি axiom প্রয়োগ। ফলে dual শিকলটি নিজেই dual সমীকরণের একটি বৈধ প্রমাণ। ∎ যেমন উপপাদ্য ২.২-এর dual বিনা পরিশ্রমে পাওয়া যায়: xx = x, x · 0 = 0, x(x + y) = x. সাবধান: dual নেওয়া আর complement নেওয়া এক কাজ নয়; dual-এ literal উল্টায় না।

৩ · উদাহরণ আর গঠন — power set, ভাজক আর lattice

সংজ্ঞাটি কতটা সাধারণ, তা বোঝা যায় উদাহরণে। প্রতিটি ক্ষেত্রে axiom চারটি যাচাই করতে হয়।

• দুই-উপাদানের algebra {0, 1}: OR, AND, NOT. Circuit আর logic-এর জগৎ।
• Power set P(S): S-এর সব উপসেট, + = ∪, · = ∩, A′ = S − A, 0 = ∅, 1 = S. পর্ব ১৪-এর power set-এর 2^|S|টি উপাদান। Axiom-গুলো পর্ব ১৫-এর set identity.
• বিট-string Bⁿ: প্রতিটি বিটে আলাদা করে OR, AND, NOT. এটি আসলে P({1, …, n}), কারণ n-বিটের mask একটি উপসেট চেনায়।
• সব n-চলকের function: f + g মানে প্রতিটি সারিতে OR. 2²ⁿটি উপাদানের Boolean algebra, যা 2ⁿটি সারির power set-এর মতো।
• ভাজক D₃₀ = {1, 2, 3, 5, 6, 10, 15, 30}: + = lcm, · = gcd, x′ = 30/x, 0 = 1, 1 = 30. পর্ব ৫৬-এর ভাজকের lattice.

D₁₂ = {1, 2, 3, 4, 6, 12} কিন্তু Boolean algebra নয়: 2-এর complement y হতে হলে lcm(2, y) = 12 আর gcd(2, y) = 1 লাগে; lcm 12 হয় শুধু y = 12-এ, আর তখন gcd = 2. সাধারণভাবে D_n Boolean algebra ঠিক তখন, যখন n squarefree (কোনো মৌলিকের বর্গ n-কে ভাগ করে না)। নিচের ব্লক axiom-গুলো সরাসরি যাচাই করে।

from itertools import product
from math import gcd
def check(name, E, join, meet, comp, zero, one):    # Huntington's axioms
    bad = set()
    for x, y, z in product(E, repeat=3):
        if join(x, y) != join(y, x) or meet(x, y) != meet(y, x):
            bad.add("commutative")
        if meet(x, join(y, z)) != join(meet(x, y), meet(x, z)):
            bad.add("distributive")
        if join(x, meet(y, z)) != meet(join(x, y), join(x, z)):
            bad.add("distributive")
    for x in E:
        if join(x, zero) != x or meet(x, one) != x: bad.add("identity")
        c = comp(x)
        if c is None or join(x, c) != one or meet(x, c) != zero:
            bad.add(f"no complement for {x}")
    print(f"{name:10} {len(E):2} elements:", sorted(bad) or "Boolean algebra")
U = 0b111                                   # subsets of {a, b, c} as bitmasks
check("P({a,b,c})", range(8), lambda x, y: x | y, lambda x, y: x & y,
      lambda x: U & ~x, 0, U)
lcm = lambda a, b: a * b // gcd(a, b)
for n in (30, 12):
    D = [d for d in range(1, n + 1) if n % d == 0]
    comp = lambda x, n=n, D=D: next(
        (y for y in D if lcm(x, y) == n and gcd(x, y) == 1), None)
    check(f"D{n}", D, lcm, gcd, comp, 1, n)
E = range(8)                                # derived laws, checked on P({a,b,c})
print("x + xy = x:", all(x | (x & y) == x for x in E for y in E))
print("(x + y)' = x'y':", all(U & ~(x | y) == (U & ~x) & (U & ~y) for x in E for y in E))
print("x + y = x + z => y = z?", all(y == z for x in E for y in E for z in E if x | y == x | z))

P({a,b,c})  8 elements: Boolean algebra
D30         8 elements: Boolean algebra
D12         6 elements: ['no complement for 2', 'no complement for 6']
x + xy = x: True
(x + y)' = x'y': True
x + y = x + z => y = z? False

উদাহরণগুলোর আকার 2, 8, 2ⁿ: সবসময় 2-এর ঘাত। এটি কাকতালীয় নয়। Boolean algebra-য় x ≤ y সংজ্ঞায়িত করুন x + y = y (সমতুল্যভাবে xy = x) দিয়ে; এতে B একটি lattice হয়, যেখানে join = + আর meet = ·. ভাষান্তরে, Boolean algebra মানে এমন distributive lattice যাতে 0 আর 1 আছে আর প্রতিটি উপাদানের complement আছে। একটি অশূন্য উপাদান a-কে atom বলে, যদি 0 আর a-এর মাঝে কিছু না থাকে; P(S)-এ atom মানে একক-উপাদানের সেট।

প্রমাণের রূপরেখা: (১) প্রতিটি অশূন্য x-এর নিচে অন্তত একটি atom আছে, কারণ সসীম সেটে নিচে নামা কোথাও থামে। (২) x হলো তার নিচের সব atom-এর যোগফল; না হলে পার্থক্যের নিচের একটি atom বিরোধ ঘটায়। (৩) a atom আর a ≤ x + y হলে a ≤ x বা a ≤ y, তাই যোগফলের atom-সেট = atom-সেটের union. বাকি অংশ একই ধাঁচের হিসাব। ∎ তাই ৬ বা ১২ উপাদানের কোনো Boolean algebra নেই। অসীম Boolean algebra-র জন্য Marshall Stone ১৯৩৬ সালে দেখান, প্রতিটি Boolean algebra কোনো সেটের উপসেটের একটি algebra-র isomorphic, যদিও পুরো power set নাও হতে পারে।

৪ · SOP আর POS — minterm, maxterm আর Shannon expansion

HR-এর নিয়ম “অন্তত দুটি” truth table-এ ৪টি সারিতে 1: 011, 101, 110, 111. সারি নম্বর হলো বাইনারি মান (M বাঁয়ের বিট): 3, 5, 6, 7. প্রতিটি সারির জন্য একটি পদ লিখুন, যা শুধু ওই সারিতে 1: সারি 3 (M = 0, O = 1, T = 1)-এর পদ M′OT. এমন পদের নাম minterm m₃. সব 1-সারির minterm যোগ করলে পাওয়া যায় f-এর sum of products (SOP) রূপ, সংক্ষেপে f = Σm(3, 5, 6, 7).

1. দুটি function সমান দেখাতে প্রতিটি ইনপুটে মান মেলানোই যথেষ্ট। x₁-এর মান অনুযায়ী দুই ক্ষেত্র। — সংজ্ঞা ১.১, ক্ষেত্রভিত্তিক প্রমাণ
2. x₁ = 1: ডান পাশ = 1 · f(1, …) + 0 · f(0, …) = f(1, …), যা বাঁ পাশ। — H3, x · 0 = 0
3. x₁ = 0: ডান পাশ = 0 · f(1, …) + 1 · f(0, …) = f(0, …), যা বাঁ পাশ। ∎

নামটি Claude Shannon-এর, যদিও একই সূত্র George Boole-এর লেখাতেই আছে বলে উল্লেখ করা হয়। প্রতিটি চলকে বারবার এটি প্রয়োগ করলে f হয়ে যায় 2ⁿটি পদের যোগফল, যার প্রতিটি পদ একটি minterm গুণ একটি ধ্রুবক f(a): যেখানে f(a) = 0 সেই পদ মুছে যায়।

অস্তিত্ব আসে Shannon expansion-এর induction থেকে (পর্ব ১০); পর্ব ০৩-এর উপপাদ্য ৪ একই কথা truth table থেকে প্রমাণ করেছে, তাকে সেখানে DNF আর CNF বলা হয়েছে। অনন্যতা সহজ: minterm m_a ঠিক সারি a-তে 1, তাই কোন minterm যোগফলে আছে তা থেকে ঠিক কোন সারিতে f = 1 তা পড়া যায়; দুটি আলাদা minterm-সেট তাই আলাদা function দেয়। এটি উপপাদ্য ১.২-এর আরেক রূপ: 2ⁿটি minterm-এর উপসেট 2²ⁿটি।

রিফান্ডের নিয়মে maxterm আসে 0-সারি 0, 1, 2, 4 থেকে: f = ΠM(0, 1, 2, 4) = (M + O + T)(M + O + T′)(M + O′ + T)(M′ + O + T). এখন SOP-কে সরল করুন। কৌশল: idempotent সূত্রে MOT-কে তিনবার লেখা যায়।

1. f = M′OT + MO′T + MOT′ + MOT = (MOT + M′OT) + (MOT + MO′T) + (MOT + MOT′). — উপপাদ্য ২.২(ক), commutative আর associative
2. প্রতিটি বন্ধনী একটি চলকের দুই রূপ: MOT + M′OT = OT(M + M′) = OT · 1 = OT. একইভাবে MT আর MO. — H2, H4, H3
3. তাই f = MO + MT + OT. ১২টি literal থেকে ৬টি। ∎

নিচের ব্লক এই কাজগুলো যন্ত্রে করে: HR-এর লম্বা নিয়ম থেকে minterm আর DNF বানায়, সরল রূপের সঙ্গে প্রতিটি সারি মেলায়, আর একটি ভুল “সরলীকরণ”-এর প্রথম ভুল সারি দেখায়। শেষে প্রতিটি minterm-সেট থেকে আলাদা function হয় কি না গুনে উপপাদ্য ১.২ মেলায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import product, combinations
VARS = "MOT"                       # M manager, O office hours, T 2FA done
def hr_rule(m, o, t):              # the long rule as HR wrote it
    return ((m and o and t) or (m and o and not t)
            or (m and not o and t) or (not m and o and t))
def short_rule(m, o, t): return (m and o) or (m and t) or (o and t)
def wrong_rule(m, o, t): return (m and o) or t
def rows(n): return list(product((0, 1), repeat=n))
def minterms(f, n): return [i for i, r in enumerate(rows(n)) if f(*r)]
def dnf(ms, names):                # canonical sum of minterms
    def term(i):
        bits = format(i, f"0{len(names)}b")
        return "".join(v + ("" if b == "1" else "'") for v, b in zip(names, bits))
    return " + ".join(term(i) for i in ms) or "0"
def first_difference(f, g, n):     # None means: equivalent
    return next((r for r in rows(n) if bool(f(*r)) != bool(g(*r))), None)
ms = minterms(hr_rule, 3)
print("minterms:", ms, " maxterms:", [i for i in range(8) if i not in ms])
print("DNF:", dnf(ms, VARS))
print("short vs HR:", first_difference(short_rule, hr_rule, 3))
print("wrong vs HR:", first_difference(wrong_rule, hr_rule, 3))
for n in (1, 2, 3):                # each minterm set -> its own truth table
    R = rows(n)
    tables = {tuple(int(r in [R[i] for i in S]) for r in R)
              for k in range(2 ** n + 1) for S in combinations(range(2 ** n), k)}
    print(n, "variables:", len(tables), "distinct functions; 2^(2^n) =", 2 ** 2 ** n)

minterms: [3, 5, 6, 7]  maxterms: [0, 1, 2, 4]
DNF: M'OT + MO'T + MOT' + MOT
short vs HR: None
wrong vs HR: (0, 0, 1)
1 variables: 4 distinct functions; 2^(2^n) = 4
2 variables: 16 distinct functions; 2^(2^n) = 16
3 variables: 256 distinct functions; 2^(2^n) = 256

৫ · Functional completeness — monotone function আর Post-এর উপপাদ্য

উপপাদ্য ৪.২ বলে ¬, ∧, ∨ দিয়ে যেকোনো function লেখা যায়, অর্থাৎ {¬, ∧, ∨} functionally complete. পর্ব ০৩-এ দেখেছেন {¬, ∧}, একা NAND আর একা NOR-ও complete, আর {∧, ∨} নয়। এখানে দুটি নতুন প্রশ্ন: ¬ ছাড়া ঠিক কোন function-গুলো বানানো যায়, আর কোনো connective-সেট complete কি না তা এক নজরে কীভাবে বলা যায়?

রিফান্ডের নিয়ম MO + MT + OT-এ কোনো ′ নেই। অর্থও স্পষ্ট: কোনো শর্ত পূরণ হলে অনুমতি কখনো কমে না। এই ধর্মের নাম monotone. Bⁿ-এ ক্রম নিন a ≤ b, যদি প্রতিটি বিটে a_i ≤ b_i (পর্ব ৫৬-এর product order).

1. (⇒) রাশির গঠনের ওপর structural induction (পর্ব ১২): চলক x_i আর ধ্রুবক monotone. g, h monotone আর a ≤ b হলে g(a) ≤ g(b) ও h(a) ≤ h(b), তাই g(a)h(a) ≤ g(b)h(b) আর g(a) + h(a) ≤ g(b) + h(b). — ∧ আর ∨ দুই দিকেই ক্রম রক্ষা করে
2. (⇐) f ≡ 0 হলে ধ্রুবক 0. নইলে প্রতিটি 1-বিন্দু a-এর জন্য পদ P_a = (যেসব i-তে a_i = 1, সেই x_i-গুলোর গুণফল) নিন (a = 00…0 হলে P_a = 1), আর g = সব P_a-এর যোগফল। — নির্মাণ, ′ ছাড়া
3. f(x) = 1 হলে a = x নিয়ে P_x(x) = 1, তাই g(x) = 1. — পদের সংজ্ঞা
4. g(x) = 1 হলে কোনো 1-বিন্দু a-এর জন্য P_a(x) = 1, অর্থাৎ a-এর প্রতিটি 1-বিটে x-ও 1: a ≤ x. Monotone বলে f(x) ≥ f(a) = 1. তাই g = f. ∎ — monotone-এর সংজ্ঞা

অনুসিদ্ধান্ত: ¬ monotone নয় (0 ≤ 1 অথচ ¬0 = 1 > 0 = ¬1), তাই {∧, ∨, 0, 1} complete নয়। দুই চলকের ১৬টি function-এর মধ্যে monotone ঠিক ৬টি: 0, 1, x, y, xy, x + y. n চলকের monotone function-এর সংখ্যাকে Dedekind number বলে: n = 0 থেকে 4-এ 2, 3, 6, 20, 168 (scratch-এ ২^১৬টি function পরীক্ষা করে মেলানো)।

Monotonicity একটি “দেয়াল”: কোনো connective-সেটের সব সদস্য monotone হলে তাদের জুড়ে যা-ই বানান, monotone থাকে। Emil Post দেখান, এমন দেয়াল ঠিক পাঁচটি।

প্রয়োজনীয়তার দিকটি সহজ: প্রতিটি শ্রেণি চলক (x_i) ধারণ করে আর জোড়া লাগানোয় বন্ধ, তাই সব connective একটি শ্রেণিতে থাকলে বানানো সব কিছু ওই শ্রেণিতেই থাকে, অথচ ¬ T₀, T₁, M-এর বাইরে ধ্রুবক 0 S ও T₁-এর বাইরে, আর AND L-এর বাইরে। যথেষ্টতার প্রমাণ দীর্ঘ। NAND পাঁচটির কোনোটিতেই নেই: NAND(0, 0) = 1 (T₀ নয়), NAND(1, 1) = 0 (T₁ নয়), monotone নয়, NAND(x′, y′) = x + y অথচ NAND(x, y)′ = xy (self-dual নয়), আর NAND = 1 ⊕ xy-এ গুণফল আছে (affine নয়)। তাই এক NAND-ই যথেষ্ট। XOR আর 1 মিলে সব affine function দেয়, কিন্তু AND দেয় না: {⊕, 1} complete নয়।

Completeness শুধু অস্তিত্বের কথা; কয়টি gate লাগে, সেটাও প্রশ্ন। পর্ব ০৩-এ NAND দিয়ে ¬, ∧, ∨ দেখেছেন। নিচের stepper আরেকটি দরকারি function, XOR, শুধু NAND দিয়ে বানায়।

1লক্ষ্য: x ⊕ y2t = x ↑ y3u = x ↑ t4v = y ↑ t5out = u ↑ v

নিচের ব্লক দুই চলকের ১৬টি function-এর প্রতিটিকে Post-এর পাঁচ শ্রেণিতে বসায়, কোন একক connective complete তা খোঁজে, আর তিনটি connective-সেট থেকে বানানো যায় এমন সব function গুনে উপপাদ্য ৫.১ আর affine-এর দেয়াল মেলায়।

from itertools import product
ROWS = list(product((0, 1), repeat=2))      # x y = 00, 01, 10, 11
ALL = list(product((0, 1), repeat=4))       # all 16 two-variable functions
NAME = {(0,0,0,1): "AND", (0,1,1,1): "OR", (0,1,1,0): "XOR", (1,1,1,0): "NAND",
        (1,0,0,0): "NOR", (1,1,0,1): "IMPLIES", (0,0,1,1): "x", (0,1,0,1): "y"}
def post_classes(f):
    v = dict(zip(ROWS, f)); out = []
    if v[0, 0] == 0: out.append("T0")
    if v[1, 1] == 1: out.append("T1")
    if all(v[1 - a, 1 - b] == 1 - v[a, b] for a, b in ROWS): out.append("S")
    if all(v[a] <= v[b] for a in ROWS for b in ROWS
           if a[0] <= b[0] and a[1] <= b[1]): out.append("M")
    if any(all(v[a, b] == c ^ (p & a) ^ (q & b) for a, b in ROWS)
           for p, q, c in product((0, 1), repeat=3)): out.append("L")
    return out
for f in [(0,0,0,1), (0,1,1,1), (0,1,1,0), (1,1,0,1), (0,0,1,1)]:
    print(f"{NAME[f]:8}", post_classes(f))
print("complete on its own:", [NAME[f] for f in ALL if not post_classes(f)])
def closure(ops, start):                    # everything buildable from ops
    S = set(start)
    while True:
        new = {op(a, b) for op in ops for a in S for b in S} - S
        if not new: return S
        S |= new
x, y, zero, one = (0, 0, 1, 1), (0, 1, 0, 1), (0,) * 4, (1,) * 4
op = lambda g: (lambda a, b: tuple(g(p, q) for p, q in zip(a, b)))
NAND, AND, OR = op(lambda p, q: 1 - (p & q)), op(min), op(max)
XOR = op(lambda p, q: p ^ q)
print("from {NAND}:", len(closure([NAND], [x, y])), "of 16")
mono = closure([AND, OR], [x, y, zero, one])
print("from {AND, OR, 0, 1}:", len(mono), "| monotone:",
      sum("M" in post_classes(f) for f in ALL))
print("from {XOR, 1}:", len(closure([XOR], [x, y, one])), "| affine:",
      sum("L" in post_classes(f) for f in ALL))

AND      ['T0', 'T1', 'M']
OR       ['T0', 'T1', 'M']
XOR      ['T0', 'L']
IMPLIES  ['T1']
x        ['T0', 'T1', 'S', 'M', 'L']
complete on its own: ['NOR', 'NAND']
from {NAND}: 16 of 16
from {AND, OR, 0, 1}: 6 | monotone: 6
from {XOR, 1}: 8 | affine: 8

৬ · Karnaugh map — ঘনককে ছকে বিছানো

একটি রাশি circuit-এ সরাসরি logic gate হয়ে যায়: SOP রূপ মানে প্রথম স্তরে কয়েকটি AND gate, দ্বিতীয় স্তরে একটি OR gate. খরচের সহজ মাপ পদের সংখ্যা আর literal-এর সংখ্যা। তাই প্রশ্ন: সবচেয়ে কম পদ, তারপর সবচেয়ে কম literal-এর SOP কোনটি? এর নাম two-level minimization. Gate, transistor আর delay-এর দিক কম্পিউটার আর্কিটেকচার ও ডিজিটাল লজিক কোর্সের পর্ব ৮-এ; এখানে গণিতটুকু।

§৪-এ দেখেছেন, একটি চলকের দুই রূপওয়ালা দুটি পদ মিশে যায়: pX + pX′ = p. ঘনকের ভাষায়, পাশাপাশি দুটি কোণ মিলে একটি ধার, দুটি সমান্তরাল ধার মিলে একটি তল। Karnaugh map (K-map) 4-চলকের ঘনক Q₄-এর ১৬টি কোণকে একটি 4 × 4 ছকে এমনভাবে বসায় যে ঘনকের প্রতিবেশী ছকেও প্রতিবেশী হয়। চাবি হলো Gray code (পর্ব ৩৬): সারি আর কলামের লেবেল 00, 01, 11, 10 ক্রমে, যেখানে পরপর দুটি লেবেল এক বিটে আলাদা, আর শেষ 10 থেকে প্রথম 00-ও এক বিটে আলাদা।

1. একই সারির দুটি ঘরের AB এক, তাই তফাত শুধু CD-তে। Gray ক্রমের চারটি লেবেল একটি চক্র: 00–01–11–10–00, যেখানে চক্রের পাশের দুটি লেবেল ঠিক এক বিটে আলাদা আর বিপরীত দুটি (00 আর 11, 01 আর 10) দুই বিটে। — সরাসরি তালিকা
2. আলাদা সারি আর আলাদা কলামের দুটি ঘর অন্তত দুই বিটে আলাদা (AB-তে একটি, CD-তে একটি)। তাই প্রতিবেশ ঠিক উপপাদ্যের বর্ণনা। — ক্ষেত্র ভাগ
3. একটি পদ AB-এর ওপর শর্ত দেয় 0, 1 বা 2টি literal দিয়ে, যা চক্রে যথাক্রমে ৪টি, পাশাপাশি ২টি বা ১টি সারি বাছে (যেমন B′ মানে AB = 00 বা 10, চক্রে পাশাপাশি); CD-র ক্ষেত্রেও তাই। সারি-বাছাই আর কলাম-বাছাইয়ের গুণফলই আয়তক্ষেত্র। ∎

তাই K-map-এ দল সবসময় ১, ২, ৪, ৮ বা ১৬টি ঘরের আয়তক্ষেত্র; তিনটি বা ছয়টি ঘরের দল কোনো পদ নয়। এবার একটি 4-চলকের function সরল করি: বাজারঘরের অর্ডার-যাচাই ব্যবস্থার একটি সতর্ক-সংকেত f(A, B, C, D) = Σm(0, 1, 2, 5, 6, 7, 8, 9, 10, 14), যেখানে ঘরের নম্বর 8A + 4B + 2C + D.

K-map ৫–৬ চলকে আরও জটিল হয়ে যায় (একাধিক ছক পাশাপাশি), আর চোখে দেখা দলে ভুলের ঝুঁকি বাড়ে। হাতে-কলমে K-map-এর বহু উদাহরণ কম্পিউটার আর্কিটেকচার কোর্সের পর্ব ৯-এ। গণিতের দিক থেকে দরকার এমন একটি পদ্ধতি, যা চোখের বদলে নিয়ম মেনে চলে।

৭ · Prime implicant আর Quine–McCluskey পদ্ধতি

K-map-এর ভাষায়: implicant = শুধু 1-ভরা একটি বৈধ আয়তক্ষেত্র, prime = যাকে আর দ্বিগুণ করা যায় না। আগের উদাহরণে CD′ আর B′C′ essential, আর B′D′ prime কিন্তু essential নয়।

1. Minimal SOP f = p₁ + ⋯ + p_k-এ প্রতিটি p_i ≤ f, তাই প্রতিটি পদ implicant. — x ≤ x + y
2. ধরুন p₁ prime নয়: একটি literal মুছে পাওয়া q₁ এখনো implicant, আর q₁ ≥ p₁ (কম শর্ত, বেশি সারিতে 1). — বিরোধের অনুমান
3. g = q₁ + p₂ + ⋯ + p_k নিন। সব পদ implicant, তাই g ≤ f; আর q₁ ≥ p₁, তাই g ≥ f. ফলে g = f. — দুই দিকের অসমতা
4. g-তে পদ সমান কিন্তু literal একটি কম, যা minimal হওয়ার বিরোধী। ∎

উল্টোটি সত্য নয়: সব prime implicant উত্তরে লাগে না (B′D′)। তাই minimization দুই ভাগে: (১) সব prime implicant খোঁজা, (২) তাদের মধ্যে সবচেয়ে সস্তা এমন একটি দল বাছা যা প্রতিটি 1-সারি ঢাকে। প্রথম ভাগের পদ্ধতিগত উপায় Quine–McCluskey (Willard Quine ১৯৫২, Edward McCluskey ১৯৫৬)। পদকে লেখা হয় 0, 1, - দিয়ে, যেমন 0-01 মানে A′C′D (B যা-ই হোক)।

• মিলনের নিয়ম: দুটি পদ যদি ঠিক একটি অবস্থানে 0 বনাম 1-এ আলাদা হয় আর '-' একই জায়গায় থাকে, তবে তারা মিশে সেখানে '-' হয়, কারণ pX + pX′ = p.
• সম্পূর্ণতা: 2^k ঘরের যেকোনো implicant-কে যেকোনো একটি '-' বরাবর দুই ভাগ করলে দুটি 2^k−1 ঘরের implicant পাওয়া যায়; তাই k-এর ওপর induction-এ প্রতিটি implicant কোনো এক রাউন্ডে তৈরি হয়।
• Prime চেনা: যে পদ কোনো রাউন্ডে কারও সঙ্গে মেশে না, তাকে আর বড় করা যায় না: সেটিই prime.

1দল ০: 00002দল ১: 0001 0010 10003দল ২: 0101 0110 1001 10104দল ৩: 0111 11105রাউন্ড ২: জোড়া মেলানো6রাউন্ড ৩: চার ঘরের পদ7আর কিছু মেশে না8chart: সবচেয়ে ছোট cover

দ্বিতীয় ভাগ, অর্থাৎ chart থেকে সবচেয়ে ছোট cover বাছা, একটি set cover সমস্যা। ছোট ক্ষেত্রে সব উপসেট পরীক্ষা করা চলে, আর নিচের ব্লক ঠিক তাই করে: Q–M দিয়ে prime implicant, brute force দিয়ে সবচেয়ে কম পদ (সমান হলে কম literal), আর শেষে উত্তরটি truth table-এর প্রতিটি সারিতে মেলানো। দ্বিতীয় উদাহরণে don't care আছে, যা §৮-এ ব্যাখ্যা করা হয়েছে।

from itertools import combinations
def combine(a, b):                      # '0-10' + '0-11' -> '0-1-'
    d = [i for i in range(len(a)) if a[i] != b[i]]
    if len(d) == 1 and '-' not in (a[d[0]], b[d[0]]):
        return a[:d[0]] + '-' + a[d[0] + 1:]
def prime_implicants(n, ones, dc=()):
    terms, primes, rnd = {format(m, f'0{n}b') for m in (*ones, *dc)}, set(), 0
    while terms:
        new, used = set(), set()
        for a, b in combinations(sorted(terms), 2):
            c = combine(a, b)
            if c: new.add(c); used |= {a, b}
        rnd += 1; print(f"  round {rnd}: {len(terms)} terms, {len(terms - used)} prime")
        primes |= terms - used; terms = new
    return sorted(primes)
def covers(p, m):
    return all(c in '-' + b for c, b in zip(p, format(m, f'0{len(p)}b')))
def text(p):
    return ''.join('ABCD'[i] + ("'" if c == '0' else '') for i, c in enumerate(p) if c != '-')
def minimal_cover(n, ones, dc=()):      # brute force over sets of primes
    P = prime_implicants(n, ones, dc)
    for k in range(1, len(P) + 1):
        good = [S for S in combinations(P, k)
                if all(any(covers(p, m) for p in S) for m in ones)]
        if good: return P, min(good, key=lambda S: sum(n - p.count('-') for p in S))
for ones, dc in [((0, 1, 2, 5, 6, 7, 8, 9, 10, 14), ()),
                 ((5, 6, 7, 8, 9), tuple(range(10, 16)))]:
    print("f = sum of m", ones, "dont-care", dc)
    P, best = minimal_cover(4, ones, dc)
    print("  primes :", " ".join(text(p) for p in P))
    print("  minimal:", " + ".join(text(p) for p in best))
    ok = all((m in ones) == any(covers(p, m) for p in best)
             for m in range(16) if m not in dc)
    print("  agrees with the truth table on every cared row:", ok)

f = sum of m (0, 1, 2, 5, 6, 7, 8, 9, 10, 14) dont-care ()
  round 1: 10 terms, 0 prime
  round 2: 13 terms, 3 prime
  round 3: 3 terms, 3 prime
  primes : CD' B'D' B'C' A'C'D A'BD A'BC
  minimal: CD' + B'C' + A'BD
  agrees with the truth table on every cared row: True
f = sum of m (5, 6, 7, 8, 9) dont-care (10, 11, 12, 13, 14, 15)
  round 1: 11 terms, 0 prime
  round 2: 17 terms, 0 prime
  round 3: 8 terms, 2 prime
  round 4: 1 terms, 1 prime
  primes : BD BC A
  minimal: BD + BC + A
  agrees with the truth table on every cared row: True

৮ · Don't care, আর minimization কতটা কঠিন

বাজারঘরের গুদামে প্রতিটি তাকের স্টক-স্তর ০ থেকে ৯-এর একটি অঙ্ক, 4 বিটে ABCD (BCD রূপে) রাখা। স্তর ৫ বা বেশি হলে সবুজ বাতি জ্বলবে: f = Σm(5, 6, 7, 8, 9). কিন্তু 1010 থেকে 1111 (১০–১৫) কখনো আসে না। ওই সারিতে f যা-ই হোক, কারও কিছু যায় আসে না: এগুলো don't care, লেখা হয় d(10, …, 15). Minimization-এ এদের যেটিকে 1 ধরলে দল বড় হয় সেটিকে 1, বাকিগুলোকে 0 ধরা যায়।

• Don't care ছাড়া: f = A′BD + A′BC + AB′C′, ৩টি পদ, ৯টি literal.
• Don't care নিয়ে: f = A + BD + BC, ৩টি পদ, ৫টি literal. যেমন A একাই ঘর 8–15 ঢাকে, যার 8, 9 আসল 1 আর বাকিগুলো don't care.

দুটি উত্তরই Q–M ব্লকে মেলানো, আর শুধু “যত্নের” সারিতে (০–৯) মূল নিয়মের সমান। সাবধান: don't care-কে উত্তরের শর্ত বানাবেন না; সেই সারি সত্যিই এলে (যেমন ত্রুটিপূর্ণ সেন্সর 1100 পাঠাল) circuit-এর আচরণ অনির্ধারিত।

এবার কঠিনতা। Q–M-এর প্রথম ভাগই বিপুল হতে পারে: n চলকে prime implicant-এর সংখ্যা n-এর সঙ্গে exponential হারে বাড়তে পারে, আর ইনপুট হিসেবে truth table নিজেই 2ⁿ সারির। দ্বিতীয় ভাগ set cover, যা সাধারণভাবে NP-hard. Truth table থেকে সবচেয়ে ছোট SOP বের করার সমস্যাটি NP-complete বলে পরিচিত (William Masek-এর ১৯৭৯ সালের একটি অপ্রকাশিত পাণ্ডুলিপিতে প্রমাণ বলে উল্লেখ করা হয়), আর ইনপুট যখন truth table নয় বরং একটি রাশি, তখন সমস্যাটি আরও কঠিন শ্রেণিতে পড়ে (Christopher Umans, ২০০১, বলে উল্লেখ করা হয়)। NP-hardness-এর ধারণা DSA কোর্সের পর্ব ৬৪-এ।

তাই বাস্তবের chip-নকশায় সঠিক minimum নয়, ভালো heuristic আর multi-level রূপ ব্যবহার হয়; বিস্তারিত কম্পিউটার আর্কিটেকচার কোর্সের পর্ব ১০-এ। বাজারঘরের ক্ষেত্রে শিক্ষাটি সরল: permission-এর নিয়ম যত চলকে ছড়ায়, হাতে সরল করা তত ঝুঁকিপূর্ণ, আর প্রতিটি সরল রূপ যন্ত্রে সব সারিতে মেলানো উচিত।

৯ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

অঙ্ক ১: Canonical রূপে রূপান্তর

F(x, y, z) = x + y′z-কে Σm আর ΠM রূপে লিখুন।

1. x = 1-এর চার সারি: 100, 101, 110, 111, অর্থাৎ 4, 5, 6, 7.
2. y′z = 1 মানে y = 0, z = 1: 001 আর 101, অর্থাৎ 1, 5 (5 আগেই আছে)।
3. F = Σm(1, 4, 5, 6, 7), আর বাকি সারি থেকে F = ΠM(0, 2, 3) = (x + y + z)(x + y′ + z)(x + y′ + z′) (scratch-এ ৮টি সারি মিলিয়ে দেখা)।

অঙ্ক ২: Don't care আর একাধিক উত্তর

f(A, B, C, D) = Σm(4, 8, 10, 11, 12, 15) + d(9, 14)-এর minimal SOP বের করুন।

1. Prime implicant (Q–M বা K-map): BC′D′ (4, 12), AD′ (8, 10, 12, 14), AC (10, 11, 14, 15), AB′ (8, 9, 10, 11).
2. ঘর 4 শুধু BC′D′, ঘর 15 শুধু AC ঢাকে: দুটিই essential. এরা 4, 10, 11, 12, 15 ঢাকে; বাকি শুধু 8.
3. 8 ঢাকে AD′ আর AB′, দুটিই ২ literal. তাই দুটি সমান ভালো উত্তর: BC′D′ + AC + AD′ অথবা BC′D′ + AC + AB′, প্রতিটি ৭ literal (scratch-এ brute force-এ মেলানো)। Minimal SOP অনন্য হতে হবে, এমন কোনো নিয়ম নেই।

অঙ্ক ৩: কয়টি function?

৩ চলকের কয়টি Boolean function-এ f(0, 0, 0) = 0? উত্তর: একটি সারির মান বাঁধা, বাকি ৭টি স্বাধীন, তাই 2⁷ = 128. আর f(0, 0, 0) = 0 ও f(1, 1, 1) = 1 দুটিই হলে 2⁶ = 64 (দুটিই scratch-এ ২৫৬টি function গুনে মেলানো)।

প্রমাণের ভুল ধরুন: “সব prime implicant লাগে”

একজন লিখলেন: “উপপাদ্য ৭.২ বলে minimal SOP-এর প্রতিটি পদ prime implicant. প্রতিটি prime implicant একটি সর্বোচ্চ দল, তাই কোনোটি বাদ দিলে কিছু 1 ঢাকা পড়বে না। অতএব minimal SOP = সব prime implicant-এর যোগফল।”

ভুল কোথায়: প্রথম বাক্য “minimal ⇒ সব পদ prime” বলে, উল্টো “prime ⇒ minimal-এ আছে” বলে না; এটি converse-এর ভুল। দ্বিতীয় বাক্যও মিথ্যা: “সর্বোচ্চ” মানে দলটিকে বড় করা যায় না, এর মানে এই নয় যে তার প্রতিটি 1 শুধু সে-ই ঢাকে। পাল্টা-উদাহরণ §৬-এর f: সব ৬টি prime যোগ করলে ১৫টি literal, অথচ B′C′ + CD′ + A′BD-তে ৭টি; B′D′-এর চারটি ঘর অন্য দুটি দল ঢেকে দেয়। শুধু essential prime implicant নিশ্চিতভাবে লাগে।

১০ · AI-এর যুগে — Boolean সরলীকরণ আর প্রমাণ যাচাই

Boolean algebra-র প্রশ্নে AI সহকারী পরিচিত সূত্র ঠিক বলে, কিন্তু বড় রাশি সরল করতে গিয়ে একটি পদ হারায়, K-map-এ অবৈধ দল বাঁধে, আর প্রমাণে উল্টো দিক বা শর্ত গুলিয়ে ফেলে। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

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

• উত্তরটি সব 2ⁿ সারিতে (don't care বাদে) মূল function-এর সমান, কোড চালিয়ে দেখেছি
• প্রতিটি K-map দল আয়তক্ষেত্র, আকার 2-এর ঘাত, আর শুধু 1 বা don't care ঢাকে
• Algebra-র প্রতিটি ধাপের পাশে একটি axiom বা প্রমাণিত সূত্রের নাম আছে, “স্পষ্টত” নেই
• “যদি এবং কেবল যদি” দাবির দুই দিক আলাদা প্রমাণিত, converse গুলিয়ে যায়নি
• Completeness-এর দাবি Post-এর পাঁচ শ্রেণি দিয়ে বা closure গুনে মিলিয়েছি
• নাম, সাল আর উৎস বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

নিয়মটি সহজ: ছোট n-এ Boolean দাবির চূড়ান্ত বিচারক truth table. ৪–৬ চলকে সব সারি মেলাতে এক সেকেন্ডও লাগে না, তাই না মিলিয়ে কোনো সরল রূপ circuit বা permission নিয়মে বসাবেন না।