Logical equivalence — De Morgan, normal form আর satisfiability

১ · Tautology, contradiction আর contingency

বাজারঘরের দুই ডেভেলপার, রুমানা আর তানভীর, নতুন গ্রাহকের কুপনের নিয়ম আলাদা আলাদা করে কোডে লিখেছেন। ধরুন a = “গ্রাহক নতুন”, b = “অর্ডার ৫০০ টাকা বা তার বেশি”, c = “অর্ডার app থেকে এসেছে”। রুমানা লিখেছেন: কুপন চলবে, যদি এটি সত্য না হয় যে “গ্রাহক নতুন নয়, অথবা অর্ডার ৫০০ টাকার কম এবং app থেকেও নয়”। তানভীর লিখেছেন: কুপন চলবে, যদি গ্রাহক নতুন হন এবং অর্ডার ৫০০ টাকা বা বেশি হয় অথবা app থেকে আসে।

রুমানা: ¬(¬a ∨ (¬b ∧ ¬c))    তানভীর: a ∧ (b ∨ c)

দুটি নিয়ম কি একই কাজ করে? Code review-তে এই প্রশ্নের উত্তর “মনে হয়” দিয়ে চলে না। একটি গ্রাহকও যদি এক নিয়মে কুপন পান আর অন্য নিয়মে না পান, তাহলে অভিযোগ আসবে। এই পর্বে আপনি দুটি পথে এর নিশ্চিত উত্তর দিতে শিখবেন: truth table-এর প্রতিটি সারি মিলিয়ে, আর সূত্রের শিকল দিয়ে। পর্ব ০২-এ (Propositional logic — proposition, connective আর truth table) যে connective আর truth table শিখেছেন, এখানে সেগুলোকেই হাতিয়ার হিসেবে ব্যবহার করা হবে।

প্রথমে রাশিগুলোকে তিন ভাগে ভাগ করা যাক। চলক বা variable বলতে এখানে p, q, r-এর মতো সাধারণ proposition বোঝায়, যাদের প্রতিটির মান T (সত্য) অথবা F (মিথ্যা)। কয়েকটি চলককে connective দিয়ে জুড়ে যে রাশি হয়, তাকে বলে যৌগিক proposition বা compound proposition.

শেষ কথাটি একটি ছোট উপপাদ্য, আর এই পর্বে বারবার কাজে লাগবে।

প্রমাণ।

1. নতুন রাশির চলকগুলোর যেকোনো একটি মান-বিন্যাস নিন। সেই বিন্যাসে B-এর একটি নির্দিষ্ট মান আছে, ধরুন v (T অথবা F). (B-এর truth table থেকে)
2. নতুন রাশির মান তখন ঠিক সেই মান, যা A পায় যখন p = v আর বাকি চলকগুলো আগের মতো। (প্রতিস্থাপনের সংজ্ঞা; p-এর প্রতিটি জায়গায় একই B বসেছে বলে সব জায়গায় একই v আসে)
3. A-এর truth table-এর প্রতিটি সারিতে মান T, তাই এই সারিতেও T. (A tautology)
4. বিন্যাসটি যেকোনো ছিল, তাই নতুন রাশি প্রতিটি সারিতে T. ∎

উদাহরণ: p ∨ ¬p tautology, তাই p-এর জায়গায় (q ∧ r) বসালে (q ∧ r) ∨ ¬(q ∧ r)-ও tautology, আট সারির টেবিল না বানিয়েই। আরেকটি সহজ পর্যবেক্ষণ: A tautology হলে ¬A contradiction, আর উল্টোটাও সত্য, কারণ ¬ প্রতিটি সারির মান উল্টে দেয়।

২ · Logical equivalence — সংজ্ঞা আর truth table দিয়ে প্রমাণ

দুটি রাশি “একই কথা বলে” কথাটির গাণিতিক রূপ হলো logical equivalence.

দুটি রূপ যে একই, তা সহজেই দেখা যায়: p ↔ q একটি সারিতে T হয় ঠিক তখনই, যখন সেই সারিতে p আর q-এর মান সমান। তাই “p ↔ q প্রতিটি সারিতে T” আর “প্রতিটি সারিতে p আর q-এর মান সমান” একই কথা। খেয়াল করুন, ≡ কোনো connective নয়। p ∧ q একটি proposition, কিন্তু p ≡ q দুটি রাশি সম্পর্কে একটি দাবি, যা সত্য বা মিথ্যা প্রমাণ করা যায়। কিছু বই ≡-এর বদলে ⇔ লেখে।

প্রথম বড় উদাহরণ সবচেয়ে বিখ্যাত দুটি সূত্র, De Morgan-এর সূত্র। “রাফি ক্রিকেট খেলে এবং গান গায়” কথাটি মিথ্যা হলে কী বোঝায়? দুটির অন্তত একটি সত্য নয়: “রাফি ক্রিকেট খেলে না, অথবা গান গায় না।” অনেকে ভুল করে বলেন “খেলেও না, গায়ও না”, যা অনেক বেশি জোরালো দাবি।

প্রমাণ (truth table দিয়ে)। দুই চলকে চারটি সারি; প্রতিটি সারিতে চারটি রাশির মান হিসাব করা হলো:

তৃতীয় আর চতুর্থ কলাম চার সারিতেই সমান, তাই প্রথম সূত্রটি সত্য; পঞ্চম আর ষষ্ঠ কলামও সমান, তাই দ্বিতীয়টিও। ∎

এভাবে truth table দিয়ে প্রমাণকে কখনো perfect induction বলা হয়: সম্ভাব্য সব ক্ষেত্র একে একে দেখা। পদ্ধতিটি সবসময় কাজ করে, কারণ সারির সংখ্যা সসীম। এবার conditional নিয়ে তিনটি দাবি দেখা যাক, যেগুলো পরীক্ষায় সবচেয়ে বেশি আসে। পর্ব ০২-এ দেখেছেন, p → q-এর converse হলো q → p, inverse হলো ¬p → ¬q, আর contrapositive হলো ¬q → ¬p.

প্রমাণ।

1. p → q মিথ্যা শুধু একটি সারিতে: p = T, q = F. (conditional-এর সংজ্ঞা)
2. ¬p ∨ q-ও মিথ্যা শুধু তখন, যখন ¬p = F আর q = F, অর্থাৎ p = T, q = F. (∨-এর সংজ্ঞা) দুই রাশির মিথ্যা সারি একই, তাই বাকি তিন সারিতে দুটিই T; (ক) প্রমাণিত।
3. ¬q → ¬p মিথ্যা শুধু যখন ¬q = T আর ¬p = F, অর্থাৎ q = F, p = T. সেই একই সারি, তাই (খ) প্রমাণিত।
4. (গ)-এর জন্য একটি সারিই যথেষ্ট: p = T, q = F হলে p → q = F কিন্তু q → p = T. দুই কলাম অন্তত এক সারিতে আলাদা, তাই equivalent নয়। Inverse ¬p → ¬q আসলে converse-এর contrapositive, তাই (খ) অনুযায়ী converse-এর সঙ্গে equivalent, ফলে সেটিও p → q-এর সঙ্গে equivalent নয়। ∎

লক্ষ করুন, “equivalent নয়” প্রমাণ করতে পুরো টেবিল লাগে না, একটি counterexample সারিই যথেষ্ট। ≡ সম্পর্কটির আরও তিনটি ধর্ম আছে, যেগুলো পরের অংশের শিকল-প্রমাণকে বৈধ করে: যেকোনো A-এর জন্য A ≡ A; A ≡ B হলে B ≡ A; আর A ≡ B ও B ≡ C হলে A ≡ C (দুটি কলাম সমান, তারপর পরের দুটি সমান, তাই প্রথম আর শেষটিও সমান)। এই তিন ধর্মের নাম reflexive, symmetric আর transitive; পর্ব ৫৫-এ (Equivalence relation আর partition) এদের সাধারণ রূপ দেখবেন।

এবার কম্পিউটারকে দিয়ে সব সারি মিলিয়ে নেওয়া যাক। নিচের ব্লকটি আপনার ব্রাউজারেই Python চালায় (Pyodide, অর্থাৎ WebAssembly-তে compile করা আসল CPython). প্রথমবার চালালে Python লোড হতে কয়েক সেকেন্ড লাগে। itertools.product([True, False], repeat=n) n চলকের 2ⁿটি সারি একটি একটি করে দেয়, ঠিক truth table-এর ক্রমে। Python-এর and, or, not যে ∧, ∨, ¬-এর কাজ করে, তার বিস্তারিত Python প্রোগ্রামিং কোর্সের পর্ব ০৮-এ আছে।

from itertools import product

def imp(a, b):                      # a → b
    return (not a) or b

def check(f, g, n):
    """সব 2**n সারিতে f আর g মেলে কি না; না মিললে প্রথম counterexample"""
    for row in product([True, False], repeat=n):
        if f(*row) != g(*row):
            return "≢  counterexample " + str(row)
    return f"≡  (সব {2**n} সারিতে মিল)"

tests = [
    ("¬(p∧q) , ¬p∨¬q", lambda p, q: not (p and q), lambda p, q: not p or not q, 2),
    ("p→q , ¬p∨q", imp, lambda p, q: not p or q, 2),
    ("p→q , ¬q→¬p", imp, lambda p, q: imp(not q, not p), 2),
    ("p→q , q→p", imp, lambda p, q: imp(q, p), 2),
    ("p∨(q∧r) , (p∨q)∧(p∨r)", lambda p, q, r: p or (q and r),
        lambda p, q, r: (p or q) and (p or r), 3),
    ("(p∧q)→r , (p→r)∧(q→r)", lambda p, q, r: imp(p and q, r),
        lambda p, q, r: imp(p, r) and imp(q, r), 3),
]
for name, f, g, n in tests:
    print(f"{name:<24} {check(f, g, n)}")

def kind(f, n):
    vals = [f(*row) for row in product([True, False], repeat=n)]
    if all(vals): return "tautology"
    if not any(vals): return "contradiction"
    return f"contingency ({sum(vals)}/{len(vals)} সারিতে সত্য)"

print("(p ∧ (p→q)) → q :", kind(lambda p, q: imp(p and imp(p, q), q), 2))
print("p ∧ ¬p          :", kind(lambda p: p and not p, 1))
print("(p→q) → p       :", kind(lambda p, q: imp(imp(p, q), p), 2))

¬(p∧q) , ¬p∨¬q           ≡  (সব 4 সারিতে মিল)
p→q , ¬p∨q               ≡  (সব 4 সারিতে মিল)
p→q , ¬q→¬p              ≡  (সব 4 সারিতে মিল)
p→q , q→p                ≢  counterexample (True, False)
p∨(q∧r) , (p∨q)∧(p∨r)    ≡  (সব 8 সারিতে মিল)
(p∧q)→r , (p→r)∧(q→r)    ≢  counterexample (True, False, False)
(p ∧ (p→q)) → q : tautology
p ∧ ¬p          : contradiction
(p→q) → p       : contingency (2/4 সারিতে সত্য)

৩ · Equivalence-এর সূত্র-তালিকা

প্রতিবার truth table বানানো ক্লান্তিকর, আর চলক বাড়লে অসম্ভব। তাই গণিতবিদরা কিছু মৌলিক equivalence একবার প্রমাণ করে তালিকা বানিয়ে রেখেছেন। প্রতিটি সারি এক বা দুই চলকের ছোট truth table দিয়ে প্রমাণ করা যায় (দুই তালিকার প্রতিটি সূত্র Python দিয়ে সব সারিতে মিলিয়েও দেখা হয়েছে)। এখানে T মানে সবসময়-সত্য রাশি (যেমন p ∨ ¬p), আর F মানে সবসময়-মিথ্যা রাশি।

দুটি কলাম পাশাপাশি রাখার একটি কারণ আছে। যে equivalence-এ শুধু ¬, ∧, ∨, T আর F আছে, তাতে ∧ আর ∨ অদলবদল করে এবং T আর F অদলবদল করলে আরেকটি সঠিক equivalence পাওয়া যায়। একে বলে duality principle, আর এজন্যই প্রায় প্রতিটি সূত্র জোড়ায় জোড়ায় আসে। একটি অভ্যাস ভাঙতে হবে: সাধারণ পাটিগণিতে a + (b × c) আর (a + b) × (a + c) সমান নয়, কিন্তু যুক্তিতে ∨-এর ওপর ∧ এবং ∧-এর ওপর ∨, দুই দিকেই distributive সূত্র খাটে।

Conditional আর biconditional-এর জন্য দ্বিতীয় একটি তালিকা কাজে লাগে। এগুলোর প্রথমটি দিয়ে → সরিয়ে বাকিগুলো উপরের তালিকা থেকেই বের করা যায়।

এই তালিকা দেখতে পাটিগণিতের নিয়মের মতো, আর তা কাকতালীয় নয়। সেটের union, intersection আর complement-এর জন্যও হুবহু একই আকারের সূত্র আছে (পর্ব ১৫, সেটের অপারেশন — union, intersection, Venn diagram আর identity), আর সবগুলোর পেছনে একটিই কাঠামো, Boolean algebra (পর্ব ৬৯)। Hardware-এর দৃষ্টিকোণ থেকে একই সূত্র কম্পিউটার আর্কিটেকচার ও ডিজিটাল লজিক কোর্সের পর্ব ০৭-এ আছে, যেখানে ∧-কে · আর ∨-কে + লেখা হয়।

৪ · সূত্রের শিকল দিয়ে প্রমাণ

সূত্র-তালিকা হাতে থাকলে truth table ছাড়াই equivalence প্রমাণ করা যায়। পদ্ধতিটি সহজ: এক দিক থেকে শুরু করে প্রতিটি ধাপে একটি সূত্র প্রয়োগ করুন, আর পাশে সূত্রের নাম লিখুন। অংশ ২-এর transitive ধর্মের জন্য শুরু আর শেষের রাশি equivalent হয়। একটি গুরুত্বপূর্ণ কথা: সূত্র একটি উপ-রাশিতেও প্রয়োগ করা যায়। A ≡ B হলে বড় কোনো রাশির ভেতরে A-র জায়গায় B বসালে পুরো রাশির মান কোনো সারিতেই বদলায় না, কারণ প্রতিটি সারিতে A আর B-এর মান সমান।

নিচের stepper-এ একটি পরিচিত পরীক্ষার প্রশ্ন: দেখান যে ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q. প্রতিটি ধাপে শেষ সারিতে চার সারির মান (pq = TT, TF, FT, FF ক্রমে) দেওয়া আছে। খেয়াল করুন, রাশির চেহারা বদলায়, কিন্তু এই কলাম একবারও বদলায় না। Equivalence-এর অর্থ ঠিক এটাই।

এবার শুরুর কুপনের প্রশ্ন। রুমানার রাশি থেকে শুরু করি:

1. ¬(¬a ∨ (¬b ∧ ¬c)) ≡ ¬¬a ∧ ¬(¬b ∧ ¬c) (De Morgan)
2. ≡ a ∧ ¬(¬b ∧ ¬c) (double negation)
3. ≡ a ∧ (¬¬b ∨ ¬¬c) (De Morgan, উপ-রাশিতে)
4. ≡ a ∧ (b ∨ c) (double negation, দুবার) ∎

দুই ডেভেলপারের নিয়ম একই; তানভীরের রূপটি পড়তে সহজ, তাই কোডে সেটিই রাখা ভালো। আরেকটি ছোট উদাহরণ পরের অংশে কাজে লাগবে: (p ∧ q) ∨ (p ∧ ¬q) ≡ p ∧ (q ∨ ¬q) (distributive, উল্টো দিকে) ≡ p ∧ T (negation) ≡ p (identity). অর্থাৎ যে দুটি পদ শুধু একটি চলকের চিহ্নে আলাদা, তারা জুড়ে সেই চলকটি বাদ পড়ে।

৫ · DNF আর CNF — truth table থেকে normal form

এ পর্যন্ত আমরা রাশি দিয়ে শুরু করে truth table পেয়েছি। উল্টো প্রশ্নটি সমান গুরুত্বপূর্ণ: একটি truth table দেওয়া আছে (যেমন বাজারঘরের product team একটি টেবিলে নিয়ম লিখে দিয়েছে); এমন একটি রাশি লিখুন যার truth table ঠিক এটি। উত্তর দেয় normal form বা প্রমিত রূপ। কয়েকটি শব্দ আগে জেনে নিন।

উদাহরণ নিয়মটি বাজারঘরের free delivery: p = “অর্ডার ১০০০ টাকার বেশি”, q = “ঠিকানা ঢাকা সিটির ভেতরে”, r = “গ্রাহক প্রিমিয়াম সদস্য”। তিন শর্তের অন্তত দুটি সত্য হলে delivery ফ্রি। ক্রিকেটে তিন আম্পায়ারের সংখ্যাগরিষ্ঠ রায়ের মতো, তাই একে majority function-ও বলে।

তিন চলকের আটটি সারিকে একটি ঘনকের আটটি কোণ হিসেবে আঁকা যায়: প্রতিটি কোণ একটি মান-বিন্যাস, আর পাশাপাশি দুটি কোণ ঠিক একটি চলকে আলাদা। নিচের ছবিতে 1 মানে T আর 0 মানে F.

এবার stepper-এ সত্য সারিগুলো থেকে DNF বানানো দেখুন। নিয়ম: সারিতে যে চলক T, সেটি literal হিসেবে যেমন আছে তেমন বসে; যে চলক F, তার আগে ¬ বসে।

এই কৌশল যে সবসময় কাজ করে, তা একটি উপপাদ্য।

প্রমাণ।

1. ধরুন টেবিলে অন্তত একটি সারিতে T. প্রতিটি সত্য সারি s-এর জন্য minterm m_s নিন: s-এ T চলক literal হিসেবে, F চলক ¬ সহ। (minterm-এর সংজ্ঞা)
2. m_s সারি s-এ T, কারণ সেখানে এর প্রতিটি literal T. অন্য যেকোনো সারি t-তে কোনো একটি চলক s-এর থেকে আলাদা মান পায়; সেই চলকের literal t-তে F, তাই m_s = F. (∧-এর সংজ্ঞা)
3. D = সব m_s-এর ∨. একটি সারিতে D = T ঠিক তখন, যখন কোনো m_s T, অর্থাৎ (ধাপ ২ অনুযায়ী) সারিটি নিজেই একটি সত্য সারি। তাই D-এর টেবিল প্রদত্ত টেবিলের সমান। (∨-এর সংজ্ঞা)
4. কোনো সারিতেই T না থাকলে D = p₁ ∧ ¬p₁ নিন, যা নিজেই একটি DNF (একটি পদ)। (negation সূত্র)
5. CNF-এর জন্য উল্টো টেবিল, অর্থাৎ ¬f-এর টেবিলে ধাপ ১–৪ প্রয়োগ করে DNF D′ বানান। তাহলে f ≡ ¬D′. De Morgan দিয়ে ¬-কে ভেতরে নামালে প্রতিটি minterm একটি maxterm হয়ে যায় (∧ হয় ∨, প্রতিটি literal উল্টে যায়), আর বাইরের ∨ হয় ∧. ফল একটি CNF. (De Morgan, double negation)
6. প্রদত্ত যৌগিক proposition-এর নিজের truth table-এ ধাপগুলো প্রয়োগ করলে equivalent DNF আর CNF পাওয়া যায়। ∎

ধাপ ৫ ব্যবহারে সহজ একটি নিয়ম দেয়: প্রতিটি মিথ্যা সারির জন্য একটি maxterm লিখুন, যেখানে সারিতে T চলকের আগে ¬ বসে আর F চলক যেমন আছে তেমন। নিচের ব্লক দুটি নিয়মই প্রয়োগ করে, তারপর লেখা রাশিগুলোকে আবার Python রাশিতে বদলে সব সারিতে মিলিয়ে দেখে।

from itertools import product

def free_delivery(p, q, r):          # তিনটি শর্তের অন্তত দুটি সত্য
    return p + q + r >= 2

def dnf(f, names):                   # প্রতিটি সত্য সারি → একটি minterm
    terms = []
    for row in product([True, False], repeat=len(names)):
        if f(*row):
            terms.append("(" + "∧".join(x if v else "¬" + x for x, v in zip(names, row)) + ")")
    return " ∨ ".join(terms)

def cnf(f, names):                   # প্রতিটি মিথ্যা সারি → একটি maxterm
    clauses = []
    for row in product([True, False], repeat=len(names)):
        if not f(*row):
            clauses.append("(" + "∨".join("¬" + x if v else x for x, v in zip(names, row)) + ")")
    return " ∧ ".join(clauses)

D, C = dnf(free_delivery, "pqr"), cnf(free_delivery, "pqr")
print("DNF:", D)
print("CNF:", C)

def value(formula, row):             # লেখা সূত্রটিকে Python রাশি বানিয়ে মান বের করা
    py = formula.replace("¬", " not ").replace("∧", " and ").replace("∨", " or ")
    return eval(py, {}, dict(zip("pqr", row)))

rows = list(product([True, False], repeat=3))
print("৮ সারিতেই DNF = CNF = মূল নিয়ম:",
      all(value(D, r) == value(C, r) == free_delivery(*r) for r in rows))

# XOR (parity)-এর DNF-এ কয়টি minterm লাগে?
print("parity, n = 1..8:", [sum(1 for r in product([0, 1], repeat=n) if sum(r) % 2)
                            for n in range(1, 9)])

DNF: (p∧q∧r) ∨ (p∧q∧¬r) ∨ (p∧¬q∧r) ∨ (¬p∧q∧r)
CNF: (¬p∨q∨r) ∧ (p∨¬q∨r) ∧ (p∨q∨¬r) ∧ (p∨q∨r)
৮ সারিতেই DNF = CNF = মূল নিয়ম: True
parity, n = 1..8: [1, 2, 4, 8, 16, 32, 64, 128]

Canonical DNF বড় হয়, তা স্বাভাবিক; প্রশ্ন হলো সরল করলে কি ছোট হয়? Free delivery-তে চারটি পদ সরল হয়ে তিনটি দুই-literal পদে নেমেছিল। Parity-তে তা হয় না, আর এর একটি সুন্দর প্রমাণ আছে। দাবি: n চলকের parity-র যেকোনো DNF-এ অন্তত 2ⁿ⁻¹টি পদ লাগে।

1. ধরুন DNF-এর কোনো পদ P-তে একটি চলক x নেই, আর P কোনো সারি s-এ T. (বিপরীত অনুমান)
2. s থেকে শুধু x-এর মান উল্টে সারি s′ পান। P-তে x নেই, তাই P সারি s′-এও T, ফলে পুরো DNF s′-এ T. (∨-এর সংজ্ঞা)
3. কিন্তু s আর s′-এ T চলকের সংখ্যা ঠিক এক কম-বেশি, তাই একটিতে parity T হলে অন্যটিতে F. DNF আর parity তাই s বা s′-এর অন্তত একটিতে আলাদা, যা অসম্ভব। (P = T বলে s-এ parity T হতেই হবে)
4. অতএব প্রতিটি পদে n চলকের সবকটি আছে, আর প্রতিটি পদ ঠিক একটি সারিতে T. 2ⁿ⁻¹টি সত্য সারি ঢাকতে অন্তত 2ⁿ⁻¹টি পদ লাগে। ∎

হাতে Boolean রাশি সরল করার কাজ (K-map, Quine–McCluskey) circuit-এর দিক থেকে কম্পিউটার আর্কিটেকচার ও ডিজিটাল লজিক কোর্সের পর্ব ১০-এ আছে, আর এর গণিত এই কোর্সের পর্ব ৬৯-এ (Boolean algebra-র গণিত — function, identity আর minimization).

৬ · Functional completeness — NAND একাই যথেষ্ট

উপপাদ্য ৪-এর একটি চমকপ্রদ ফল আছে। DNF-এ শুধু ¬, ∧ আর ∨ লাগে। তাই যেকোনো truth table, অর্থাৎ যেকোনো Boolean function, শুধু এই তিনটি connective দিয়ে লেখা যায়। যে connective-সেটের এই ক্ষমতা আছে, তাকে বলে functionally complete. প্রশ্ন হলো, তিনটির কম দিয়ে কি চলে?

প্রমাণ। {¬, ∧, ∨}-এর কথা উপপাদ্য ৪ থেকে আসে। {¬, ∧}-এর জন্য De Morgan আর double negation থেকে p ∨ q ≡ ¬(¬p ∧ ¬q); তাই DNF-এর প্রতিটি ∨ এভাবে বদলে দিলে শুধু ¬ আর ∧ থাকে। একইভাবে p ∧ q ≡ ¬(¬p ∨ ¬q) থেকে {¬, ∨}. ∎ (একই যুক্তিতে {¬, →}-ও complete, কারণ p ∨ q ≡ ¬p → q.)

এবার আরও এক ধাপ। দুটি নতুন connective: NAND, লেখা হয় p ↑ q, যার অর্থ ¬(p ∧ q); আর NOR, লেখা হয় p ↓ q, যার অর্থ ¬(p ∨ q). ↑ চিহ্নটিকে Sheffer stroke-ও বলে। নিচের stepper দেখায় কীভাবে শুধু NAND দিয়ে ¬, ∧ আর ∨ বানানো যায়।

প্রমাণ। (ক) NAND-এর কথা stepper-এ দেখানো হলো: ¬p ≡ p ↑ p আর p ∧ q ≡ (p ↑ q) ↑ (p ↑ q), আর {¬, ∧} complete (উপপাদ্য ৫)। NOR-এর জন্য একইভাবে ¬p ≡ p ↓ p আর p ∨ q ≡ (p ↓ q) ↓ (p ↓ q), আর {¬, ∨} complete. (খ)-এর জন্য:

1. দাবি: শুধু চলক, ∧ আর ∨ দিয়ে তৈরি যেকোনো রাশি, সব চলক T হলে T. (যা প্রমাণ করতে হবে)
2. রাশিটি একটি চলক হলে কথাটি স্পষ্টতই সত্য। (ভিত্তি)
3. রাশিটি A ∧ B বা A ∨ B হলে, A আর B ছোট রাশি, আর ধরে নেওয়া যায় দাবিটি তাদের জন্য সত্য: সব চলক T হলে A = T, B = T. তখন T ∧ T = T, T ∨ T = T. (∧, ∨-এর সংজ্ঞা)
4. রাশি ছোট থেকে বড় করে এভাবেই গঠিত হয়, তাই দাবিটি সব রাশির জন্য সত্য। এই ধরনের যুক্তির নাম structural induction; পর্ব ১২-এ (Recursive সংজ্ঞা আর structural induction) একে পুরোপুরি নিয়মে বাঁধা হবে।
5. কিন্তু ¬p, p = T হলে F. তাই ¬p কোনো {∧, ∨} রাশির সঙ্গে equivalent নয়, আর {∧, ∨} complete নয়। ∎

নিচের ব্লক এই প্রশ্নগুলোকে brute force দিয়ে দেখে। দুই চলকের প্রতিটি function-এর চার সারির কলামকে একটি 4-bit সংখ্যা হিসেবে রাখা হয় (যেমন p = 1100, q = 1010), তারপর p আর q থেকে শুরু করে প্রদত্ত connective বারবার প্রয়োগ করে নতুন কলাম খোঁজা হয়, যতক্ষণ না আর নতুন কিছু আসে। দুই চলকের মোট function 2⁴ = 16টি।

# দুই চলকের প্রতিটি function = ৪ সারির truth table = একটি 4-bit সংখ্যা
# সারির ক্রম: pq = TT, TF, FT, FF
P, Q, ALL = 0b1100, 0b1010, 0b1111

def closure(start, ops):
    """start থেকে শুধু ops বারবার প্রয়োগ করে যত function পাওয়া যায়"""
    seen = set(start)
    while True:
        new = {op(a, b) for a in seen for b in seen for op in ops} - seen
        if not new:
            return seen
        seen |= new

NOT  = lambda a, b: ALL & ~a          # একটি ইনপুটই লাগে, b উপেক্ষিত
AND  = lambda a, b: a & b
OR   = lambda a, b: a | b
NAND = lambda a, b: ALL & ~(a & b)
NOR  = lambda a, b: ALL & ~(a | b)
XOR  = lambda a, b: a ^ b
IFF  = lambda a, b: ALL & ~(a ^ b)

sets = [("¬, ∧", [NOT, AND]), ("¬, ∨", [NOT, OR]), ("NAND", [NAND]),
        ("NOR", [NOR]), ("∧, ∨", [AND, OR]), ("⊕, ↔", [XOR, IFF])]
for name, ops in sets:
    got = closure({P, Q}, ops)
    print(f"{name:<6} → {len(got):2d}/16", "functionally complete" if len(got) == 16 else "")

print("∧, ∨ দিয়ে পাওয়া:", sorted(format(x, "04b") for x in closure({P, Q}, [AND, OR])))

¬, ∧   → 16/16 functionally complete
¬, ∨   → 16/16 functionally complete
NAND   → 16/16 functionally complete
NOR    → 16/16 functionally complete
∧, ∨   →  4/16 
⊕, ↔   →  8/16 
∧, ∨ দিয়ে পাওয়া: ['1000', '1010', '1100', '1110']

৭ · Satisfiability — SAT, 2ⁿ সারি আর NP-completeness-এর প্রথম দেখা

Tautology-র উল্টো দিকের প্রশ্নটি কম্পিউটার বিজ্ঞানের অন্যতম কেন্দ্রীয় প্রশ্ন: রাশিটি কি অন্তত একবার সত্য হতে পারে?

সংজ্ঞাগুলো একে অপরের সঙ্গে খুব ঘনিষ্ঠ। নিচের তিনটি কথা সরাসরি সংজ্ঞা থেকে আসে, কারণ ¬ প্রতিটি সারির মান উল্টে দেয়:

• A tautology ⇔ ¬A unsatisfiable.
• A ≡ B ⇔ A ↔ B tautology ⇔ ¬(A ↔ B) unsatisfiable.
• A satisfiable ⇔ A contradiction নয় ⇔ ¬A tautology নয়।

অর্থাৎ equivalence যাচাই আর satisfiability আসলে একই প্রশ্নের দুই রূপ: একটির দ্রুত পদ্ধতি পেলে অন্যটিরও পাওয়া যায়। পর্ব ০২-এ যে specification-এর consistency দেখেছেন, সেটিও SAT: বাজারঘরের সব নিয়ম একসঙ্গে মানা যায় কি না, মানে নিয়মগুলোর ∧ satisfiable কি না।

নিচের ব্লকটি clause-কে সংখ্যার তালিকায় লেখে, যেভাবে SAT solver-রা লেখে (DIMACS ধারা): 3 মানে চলক ৩, আর −3 মানে ¬(চলক ৩)। যেমন [−3, 1] হলো ¬x₃ ∨ x₁, অর্থাৎ x₃ → x₁. বাজারঘরের delivery-র পাঁচটি নিয়ম: ঠিক একটি slot বেছে নিতে হবে (প্রথম দুই clause); express হলে সকালের slot; express আর cash on delivery একসঙ্গে নয়; আর অর্ডারটি হয় express, নয়তো cash on delivery.

from itertools import product
import random

def count_models(cnf, n):
    """সব 2**n assignment যাচাই: কয়টি CNF-কে সত্য করে, আর প্রথমটি কোনটি"""
    count, first = 0, None
    for bits in product([False, True], repeat=n):
        if all(any(bits[abs(l) - 1] == (l > 0) for l in cl) for cl in cnf):
            count += 1
            first = first or "".join("1" if b else "0" for b in bits)
    return count, first

# 1 = সকালের slot, 2 = বিকেলের slot, 3 = express, 4 = cash on delivery
spec = [[1, 2], [-1, -2], [-3, 1], [-3, -4], [3, 4]]
print("নিয়ম ৫টি:", count_models(spec, 4))
print("আরও দুটি নিয়ম যোগ করলে:", count_models(spec + [[-1], [-4]], 4))

random.seed(7)
n, m = 12, 50
f = [[random.choice([-1, 1]) * v for v in random.sample(range(1, n + 1), 3)]
     for _ in range(m)]
c, first = count_models(f, n)
print(f"এলোমেলো 3-CNF, n={n}, m={m}: {2**n}টি সারি দেখে {c}টি সমাধান, প্রথম {first}")

for n in (20, 40, 60, 80, 100):
    sec = 2**n / 1e9                    # সেকেন্ডে 10^9 সারি দেখলে
    print(f"n={n:3d}: {2**n:.2e} সারি, {sec:.1e} সেকেন্ড ≈ {sec / 31_536_000:.1e} বছর")

নিয়ম ৫টি: (3, '0101')
আরও দুটি নিয়ম যোগ করলে: (0, None)
এলোমেলো 3-CNF, n=12, m=50: 4096টি সারি দেখে 2টি সমাধান, প্রথম 001011010111
n= 20: 1.05e+06 সারি, 1.0e-03 সেকেন্ড ≈ 3.3e-11 বছর
n= 40: 1.10e+12 সারি, 1.1e+03 সেকেন্ড ≈ 3.5e-05 বছর
n= 60: 1.15e+18 সারি, 1.2e+09 সেকেন্ড ≈ 3.7e+01 বছর
n= 80: 1.21e+24 সারি, 1.2e+15 সেকেন্ড ≈ 3.8e+07 বছর
n=100: 1.27e+30 সারি, 1.3e+21 সেকেন্ড ≈ 4.0e+13 বছর

তাহলে SAT কি আসলে কঠিন, নাকি আমরা চালাক পদ্ধতি এখনো খুঁজে পাইনি? এখানে দুটি কাজের পার্থক্য লক্ষ করুন। কেউ একটি সমাধান হাতে দিলে তা যাচাই করা সহজ: প্রতিটি clause-এ একটি সত্য literal আছে কি না দেখা, রাশির আকারের প্রায় সমান সময়ে। কিন্তু সমাধান খুঁজে বের করার জন্য কোনো দ্রুত পদ্ধতি জানা নেই। যেসব হ্যাঁ/না প্রশ্নের “হ্যাঁ” উত্তরের প্রমাণ polynomial সময়ে (চলকের সংখ্যার কোনো নির্দিষ্ট ঘাতের মধ্যে) যাচাই করা যায়, তাদের শ্রেণিকে বলে NP.

সব SAT সমান কঠিন নয়। প্রতিটি clause-এ বড়জোর দুটি literal থাকলে (2-SAT) polynomial সময়ের, এমনকি linear সময়ের algorithm জানা আছে; ঠিক তিনটি literal-এর 3-SAT-ই NP-complete. P, NP, reduction আর NP-completeness-এর পুরো কাঠামো algorithm-এর দিক থেকে DSA কোর্সের পর্ব ৬৪-এ আছে, আর বাস্তবে এমন সমস্যার মোকাবিলা পর্ব ৬৫-এ। মজার ব্যাপার হলো, তত্ত্বে কঠিন হলেও আধুনিক SAT solver অনেক বাস্তব instance বিপুল আকারেও দ্রুত সমাধান করে; একটি আসল solver চালিয়ে দেখবেন পর্ব ০৭-এ (কাজে যুক্তি — specification, ধাঁধা আর SAT solver), আর software যাচাইয়ে এর ব্যবহার পর্ব ৭৭-এ।

৮ · AI-এর যুগে equivalence যাচাইয়ের অভ্যাস

AI assistant-কে “এই দুটি শর্ত কি একই?” বা “এই রাশিটি সরল করে দাও” জিজ্ঞেস করলে দ্রুত, আত্মবিশ্বাসী উত্তর আসে। সমস্যা হলো, ভুল উত্তরও একই আত্মবিশ্বাসে আসে, আর যুক্তির ভুল চোখে ধরা কঠিন, কারণ প্রতিটি লাইন দেখতে বিশ্বাসযোগ্য। সুখবর হলো, এই পর্বের বিষয়ে যাচাই প্রায় বিনামূল্যে: কয়েক চলকের যেকোনো দাবি অংশ ২-এর ব্লকের মতো দশ লাইনের Python দিয়ে সব সারিতে মিলিয়ে দেখা যায়।

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

• দাবিটি ছোট মানে (সব সারি বা এলোমেলো কিছু সারি) Python-এ চালিয়ে মিলিয়েছি; counterexample খুঁজেছি
• প্রতিটি ধাপের সূত্র তালিকার সঙ্গে মিলিয়েছি, আর এক ধাপে একটিই সূত্র আছে
• প্রমাণ শেষে যা দেখানো হলো, তা-ই চাওয়া হয়েছিল কি না দেখেছি: converse বা উল্টো দিক নয়, আর বৃত্তাকার যুক্তিও নয়
• ব্যবহৃত প্রতিটি উপপাদ্যের শর্ত (কোন connective, কয়টি চলক) জিজ্ঞেস করেছি
• ইতিহাস বা reference-এর দাবি (সাল, নাম, গবেষণাপত্র) একটি বিশ্বস্ত পাঠ্যবই বা মূল উৎসের সঙ্গে মিলিয়েছি