Logical Equivalence — expression সরল করার বীজগণিত

আগে এটা বুঝি

গত লেসনে আমরা truth table বানাতে শিখেছি। কিন্তু একটা সমস্যা আছে।

৩টা variable → ৮ row। ৫টা → ৩২। ১০টা → ১০২৪। ২০টা → ১০ লক্ষের বেশি।

বাস্তব কোডে ২০টা boolean condition কিছুই অস্বাভাবিক না। তাই “সব row পরীক্ষা করি” পদ্ধতি খুব দ্রুত ভেঙে পড়ে।

দরকার অন্য একটা হাতিয়ার: বীজগণিত।

2(x + 3) কে 2x + 6 বানাতে আপনি সব x-এর মান বসিয়ে দেখেন না — একটা নিয়ম প্রয়োগ করেন। Logic-এও ঠিক তেমন নিয়ম আছে। সেগুলো জানলে আপনি একটা জটিল condition-কে ধাপে ধাপে সরল করতে পারবেন, আর নিশ্চিত থাকতে পারবেন অর্থ বদলায়নি।

এই নিয়মগুলোই compiler প্রয়োগ করে আপনার কোড দ্রুত করতে, database প্রয়োগ করে query দ্রুত করতে, আর Level 2-এ আপনি প্রয়োগ করবেন circuit-এ gate সংখ্যা কমাতে।

মূল ধারণা

Equivalent মানে কী

দুইটা compound proposition P আর Q কে logically equivalent বলা হয় যদি প্রতিটা possible assignment-এ তাদের truth value এক হয়।

লেখা হয়: P ≡ Q

গুরুত্বপূর্ণ পার্থক্য:

P ≡ Q — একটা দাবি যে দুটো সবসময় একই মান দেয় (metalanguage)
P ↔ Q — একটা proposition, যার নিজেরই truth value আছে

সম্পর্ক: P ≡ Q সত্য যদি এবং কেবল যদি P ↔ Q একটা tautology হয়।

তিনটা শ্রেণি মনে রাখুন:

শ্রেণি	মানে	উদাহরণ
Tautology	সব assignment-এ সত্য	`p ∨ ¬p`
Contradiction	সব assignment-এ মিথ্যা	`p ∧ ¬p`
Contingency	কিছুতে সত্য, কিছুতে মিথ্যা	`p ∧ q`

মৌলিক নিয়মগুলো

এগুলো মুখস্থ করার জিনিস না — ব্যবহার করতে করতে হাতে আসে। তবে টেবিলটা হাতের কাছে রাখুন।

Identity ও domination

p ∧ T ≡ p              p ∨ F ≡ p            (identity)
p ∧ F ≡ F              p ∨ T ≡ T            (domination)

p ∨ T ≡ T -টা কোডে খুব কাজে লাগে: if (x || true) মানে if (true)। Compiler এটা ধরে ফেলে আর পুরো branch সরিয়ে দেয়।

Idempotence ও negation

p ∧ p ≡ p              p ∨ p ≡ p            (idempotent)
p ∧ ¬p ≡ F             p ∨ ¬p ≡ T           (negation / excluded middle)
¬(¬p) ≡ p                                    (double negation)

Commutative, associative, distributive

p ∧ q ≡ q ∧ p                    p ∨ q ≡ q ∨ p
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)        (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)     ← এটা পরিচিত, ঠিক গুণের মতো
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)     ← এটা অপরিচিত! সংখ্যায় এমন হয় না

দ্বিতীয় distribution-টা লক্ষ্য করুন। সংখ্যায় 2 + (3 × 4) ≠ (2+3) × (2+4)। কিন্তু logic-এ OR আর AND-এর মধ্যে সম্পূর্ণ প্রতিসাম্য আছে — দুই দিকেই distribution কাজ করে। একে বলে duality।

De Morgan’s laws — সবচেয়ে গুরুত্বপূর্ণ

¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

মনে রাখার সূত্র: negation ভেতরে ঢুকলে operator উল্টে যায়।

বাংলায় ভাবলে স্পষ্ট হয়:

“চা এবং কফি — দুটোই আছে” — এটা মিথ্যা হওয়ার মানে কী? মানে চা নেই অথবা কফি নেই (অথবা দুটোই নেই)।

“চা অথবা কফি — অন্তত একটা আছে” — এটা মিথ্যা হওয়ার মানে? মানে চা-ও নেই এবং কফিও নেই।

Absorption ও অন্যান্য

p ∨ (p ∧ q) ≡ p                  p ∧ (p ∨ q) ≡ p      (absorption)
p → q ≡ ¬p ∨ q                                        (implication ভাঙা)
p → q ≡ ¬q → ¬p                                       (contrapositive)
p ↔ q ≡ (p → q) ∧ (q → p)
p ⊕ q ≡ (p ∨ q) ∧ ¬(p ∧ q)                            (XOR)

p → q ≡ ¬p ∨ q — এই একটা নিয়ম সবচেয়ে বেশি কাজে লাগে, কারণ এটা implication-কে সরিয়ে দেয়। Implication থাকলে বীজগণিত করা কঠিন; ¬ আর ∨-এ নামিয়ে আনলে সহজ।

ভেতরে কী ঘটছে

দুইভাবে প্রমাণ

একই দাবি — ¬(p ∨ q) ≡ ¬p ∧ ¬q — দুইভাবে প্রমাণ করি।

পদ্ধতি ১: Truth table (যান্ত্রিক, নিশ্চিত)

p	q	p ∨ q	¬(p ∨ q)	¬p	¬q	¬p ∧ ¬q
F	F	F	T	T	T	T
F	T	T	F	T	F	F
T	F	T	F	F	T	F
T	T	T	F	F	F	F

মোটা কলাম দুটো হুবহু মিলেছে। ∎

সুবিধা: ভুল হওয়ার সুযোগ নেই। অসুবিধা: n বড় হলে অসম্ভব।

পদ্ধতি ২: বীজগণিত (দ্রুত, কিন্তু নিয়ম জানতে হয়)

জটিল একটা উদাহরণ নিই — সরল করুন:

¬(p → q) ∨ (p ∧ ¬q)

ধাপে ধাপে, প্রতিটা ধাপে কোন নিয়ম ব্যবহার করলাম সেটা লিখে:

¬(p → q) ∨ (p ∧ ¬q)
≡ ¬(¬p ∨ q) ∨ (p ∧ ¬q)        [implication ভাঙা]
≡ (¬¬p ∧ ¬q) ∨ (p ∧ ¬q)       [De Morgan]
≡ (p ∧ ¬q) ∨ (p ∧ ¬q)         [double negation]
≡ p ∧ ¬q                       [idempotent]

চার ধাপে একটা এলোমেলো expression পরিষ্কার হয়ে গেল। Truth table বানালেও একই ফল পেতাম, কিন্তু কেন সমান সেটা বুঝতাম না।

দুইটা normal form

যেকোনো boolean expression-কে দুইটা প্রামাণ্য রূপে আনা যায়। এগুলো গুরুত্বপূর্ণ কারণ algorithm-রা প্রামাণ্য রূপ পছন্দ করে।

DNF — Disjunctive Normal Form

OR of ANDs — “sum of products”।

(p ∧ ¬q ∧ r) ∨ (¬p ∧ q) ∨ (q ∧ ¬r)

গঠন: প্রতিটা bracket একটা term (literal-দের AND), আর term-গুলো OR দিয়ে জোড়া।

Truth table থেকে DNF বানানো সহজ: যেসব row-তে ফল T, প্রতিটার জন্য একটা term লিখুন।

p → q-এর table নিন:

p	q	p → q
F	F	T	→ term: `¬p ∧ ¬q`
F	T	T	→ term: `¬p ∧ q`
T	F	F
T	T	T	→ term: `p ∧ q`

DNF: (¬p ∧ ¬q) ∨ (¬p ∧ q) ∨ (p ∧ q)

যাচাই করুন এটা সরল হয়ে ¬p ∨ q হয়:

(¬p ∧ ¬q) ∨ (¬p ∧ q) ∨ (p ∧ q)
≡ (¬p ∧ (¬q ∨ q)) ∨ (p ∧ q)      [প্রথম দুটোয় ¬p common]
≡ (¬p ∧ T) ∨ (p ∧ q)             [excluded middle]
≡ ¬p ∨ (p ∧ q)                   [identity]
≡ (¬p ∨ p) ∧ (¬p ∨ q)            [distribution]
≡ T ∧ (¬p ∨ q)                   [excluded middle]
≡ ¬p ∨ q                          [identity] ✓

CNF — Conjunctive Normal Form

AND of ORs — “product of sums”।

(p ∨ ¬q) ∧ (¬p ∨ q ∨ r) ∧ (¬r)

প্রতিটা bracket-কে বলে clause।

CNF সবচেয়ে গুরুত্বপূর্ণ কারণ সব আধুনিক SAT solver শুধু CNF নেয়। আর SAT solver ব্যবহার হয় hardware verification, program analysis, scheduling, dependency resolution — সর্বত্র।

Truth table থেকে CNF: যেসব row-তে ফল F, প্রতিটার জন্য একটা clause লিখুন — কিন্তু উল্টো করে (T হলে ¬x, F হলে x)।

p → q-এ শুধু একটা F row (p=T, q=F), তাই একটা clause: ¬p ∨ q। ✓

Functional completeness

একটা চমকপ্রদ সত্য: শুধু NAND দিয়ে সব boolean function বানানো যায়।

দেখা যাক:

¬p        ≡ p NAND p
p ∧ q     ≡ ¬(p NAND q)  ≡ (p NAND q) NAND (p NAND q)
p ∨ q     ≡ ¬p NAND ¬q   ≡ (p NAND p) NAND (q NAND q)

তিনটাই পেয়ে গেলাম। আর ¬, ∧, ∨ দিয়ে যেহেতু যেকোনো truth table DNF আকারে লেখা যায়, তাই NAND দিয়েই সব হয়।

নিচে এটা circuit হিসেবে দেখুন — শুধু NAND gate, আর তা থেকে NOT, AND, OR:

SIMULATOR

NAND দিয়ে সবকিছু

InputsOutputs¬A1A·B0A+B0

A	B	¬A	A·B	A+B
0	0	1	0	0
0	1	1	0	1
1	0	0	0	1
1	1	0	1	1

শুধু NAND gate দিয়ে NOT, AND, OR বানানো — এজন্যই NAND-কে universal gate বলে।
টেবিলের যেকোনো row-তে ক্লিক করলে circuit সেই input-এ চলে যাবে।

Input toggle করে দেখুন তিনটা output সত্যিই ¬A, A ∧ B, আর A ∨ B হিসেবে আচরণ করছে।

এটা কেন গুরুত্বপূর্ণ: চিপ বানানোর সময় এর মানে হলো আপনার একটাই gate type-এর কারখানা দরকার। বাস্তব CMOS-এ NAND সবচেয়ে সস্তা (মাত্র ৪টা transistor, AND-এ লাগে ৬টা)। তাই বহু digital circuit ভেতরে ভেতরে প্রায় পুরোটাই NAND।

NOR-ও একইভাবে universal। Apollo Guidance Computer — যেটা মানুষকে চাঁদে নিয়ে গিয়েছিল — পুরোটাই বানানো হয়েছিল ৫,৬০০টা NOR gate দিয়ে। আর কিছু না।

উদাহরণ

বাস্তব একটা condition সরল করা

এই কোডটা কল্পিত নয় — এই ধরনের জিনিস legacy codebase-এ ভরা:

if (not (user.is_guest or user.is_banned)) and \
   (user.is_admin or (user.is_verified and not user.is_guest)):
    allow()

Variable: g = guest, b = banned, a = admin, v = verified।

¬(g ∨ b) ∧ (a ∨ (v ∧ ¬g))

ধাপে ধাপে:

¬(g ∨ b) ∧ (a ∨ (v ∧ ¬g))
≡ (¬g ∧ ¬b) ∧ (a ∨ (v ∧ ¬g))          [De Morgan]
≡ ¬g ∧ ¬b ∧ (a ∨ (v ∧ ¬g))            [associative — bracket তোলা]

এখন লক্ষ্য করুন ¬g বাইরে ইতিমধ্যে আছে। তাই ভেতরের ¬g অপ্রয়োজনীয় — বাইরেরটা সত্য না হলে পুরোটাই মিথ্যা, আর সত্য হলে ভেতরেরটা T:

≡ ¬g ∧ ¬b ∧ (a ∨ (v ∧ T))
≡ ¬g ∧ ¬b ∧ (a ∨ v)                   [identity]

চূড়ান্ত রূপ:

if not user.is_guest and not user.is_banned and (user.is_admin or user.is_verified):
    allow()

যা অর্জন হলো:

৫টা operator থেকে ৪টা
একটা duplicate check মুছে গেল (¬g দুইবার ছিল)
সবচেয়ে বড় লাভ: এখন শর্তটা পড়লেই বোঝা যায় — “guest নয়, banned নয়, আর admin বা verified”

শেষ পয়েন্টটা আসলে সবচেয়ে গুরুত্বপূর্ণ। Compiler এমনিতেই optimize করত। কিন্তু পরের ডেভেলপার — বা ছয় মাস পরের আপনি — সরল রূপটা পড়ে ভুল কম করবেন।

নিজে চালিয়ে দেখুন

EXPERIMENT

Compiler নিজে De Morgan প্রয়োগ করছে — দেখুন

Linux / macOS, gcc বা clang· ১৫ মিনিট

একটা ফাইল বানান, demorgan.c:

#include <stdbool.h>

bool version_a(bool p, bool q) {
    return !(p || q);
}

bool version_b(bool p, bool q) {
    return !p && !q;
}

Optimization ছাড়া compile করে assembly দেখুন:

gcc -O0 -S -masm=intel -o demorgan_O0.s demorgan.c

এবার optimization চালু করে:

gcc -O2 -S -masm=intel -o demorgan_O2.s demorgan.c
grep -A 8 "version_a:" demorgan_O2.s
grep -A 8 "version_b:" demorgan_O2.s

-O2-তে দুইটা function-এর assembly প্রায় নিশ্চিতভাবে অভিন্ন হবে — সাধারণত এরকম কিছু:

version_a:
        or      edi, esi
        xor     eax, eax
        test    dil, dil
        sete    al
        ret

Compiler বুঝে ফেলেছে !(p || q) আর !p && !q একই function। এটা De Morgan, যান্ত্রিকভাবে প্রয়োগ করা।

আরেকটা চেষ্টা করুন — এই function-টা কী হয়?

bool always_true(bool p) {
    return p || !p;
}

-O2-তে দেখবেন পুরো function-টা হয়ে গেছে:

always_true:
        mov     eax, 1
        ret

p ∨ ¬p ≡ T — compiler tautology চিনে ফেলেছে আর প্যারামিটার পড়ার প্রয়োজনই বাদ দিয়েছে।

এটা কী প্রমাণ করে

আপনি যে বীজগণিত হাতে করছেন, compiler সেটাই যান্ত্রিকভাবে করে — এবং assembly output-এ তার প্রমাণ দেখা যায়। এটাই Level 3 ও Level 5-এর সেতু।

EXPERIMENT

PostgreSQL query planner-এর বীজগণিত

PostgreSQL· ১৫ মিনিট

CREATE TABLE users (
  id       serial PRIMARY KEY,
  status   text,
  age      int,
  country  text
);

INSERT INTO users (status, age, country)
SELECT
  (ARRAY['active','banned','pending'])[1 + (i % 3)],
  18 + (i % 60),
  (ARRAY['BD','IN','US'])[1 + (i % 3)]
FROM generate_series(1, 200000) i;

CREATE INDEX idx_status ON users(status);
ANALYZE users;

এবার একই logical প্রশ্ন দুইভাবে লিখে plan তুলনা করুন:

EXPLAIN (ANALYZE, COSTS OFF)
SELECT count(*) FROM users
WHERE (status = 'active' AND age > 30)
   OR (status = 'active' AND country = 'BD');

EXPLAIN (ANALYZE, COSTS OFF)
SELECT count(*) FROM users
WHERE status = 'active' AND (age > 30 OR country = 'BD');

দুইটা query logically equivalent — distribution law:

(s ∧ a) ∨ (s ∧ c) ≡ s ∧ (a ∨ c)

দ্বিতীয় রূপে status = 'active' বাইরে বেরিয়ে এসেছে, তাই planner সরাসরি idx_status ব্যবহার করতে পারে। প্রথম রূপে সেটা করতে হলে planner-কে আগে factoring করতে হয়।

আধুনিক PostgreSQL সাধারণত দুটোর জন্যই একই plan বের করে — কিন্তু EXPLAIN চালিয়ে নিজে দেখুন। জটিল query-তে পার্থক্য থেকে যায়।

এটা কী প্রমাণ করে

Database-ও একই নিয়ম প্রয়োগ করে — কিন্তু performance-এর জন্য, কারণ কোন রূপে লিখলে index ব্যবহার করা যায় সেটা logical form-এর উপর নির্ভর করে।

নিজে বানান

BUILD IT

Equivalence Checker ও DNF Generator

Python · ●●●○○

গত লেসনের truth_table function-টা reuse করুন
দুইটা expression-এর result list তুলনা করে equivalence বলুন
যেসব row-তে T, সেগুলো থেকে DNF term বানান
যেসব row-তে F, সেগুলো থেকে CNF clause বানান
পরিচিত সব law নিজে যাচাই করুন

from itertools import product

def evaluate_all(expr, variables):
    """প্রতিটা assignment-এ expr-এর মান — list of (assignment, value)."""
    out = []
    for combo in product([False, True], repeat=len(variables)):
        env = dict(zip(variables, combo))
        out.append((env, eval(expr, {"__builtins__": {}}, env)))
    return out


def equivalent(e1, e2, variables):
    r1 = [v for _, v in evaluate_all(e1, variables)]
    r2 = [v for _, v in evaluate_all(e2, variables)]
    return r1 == r2


def to_dnf(expr, variables):
    """সত্য row-গুলো থেকে sum-of-products।"""
    terms = []
    for env, value in evaluate_all(expr, variables):
        if value:
            lits = [v if env[v] else f"¬{v}" for v in variables]
            terms.append("(" + " ∧ ".join(lits) + ")")
    if not terms:
        return "F   [contradiction]"
    return " ∨ ".join(terms)


def to_cnf(expr, variables):
    """মিথ্যা row-গুলো থেকে product-of-sums — literal উল্টে যায়।"""
    clauses = []
    for env, value in evaluate_all(expr, variables):
        if not value:
            lits = [f"¬{v}" if env[v] else v for v in variables]
            clauses.append("(" + " ∨ ".join(lits) + ")")
    if not clauses:
        return "T   [tautology]"
    return " ∧ ".join(clauses)


# ── পরিচিত law যাচাই ────────────────────────────────────────────
LAWS = [
    ("De Morgan (AND)",  "not (p and q)",        "(not p) or (not q)",   ["p","q"]),
    ("De Morgan (OR)",   "not (p or q)",         "(not p) and (not q)",  ["p","q"]),
    ("Implication",      "(not p) or q",         "(not q) or (not (not p))", ["p","q"]),
    ("Contrapositive",   "(not p) or q",         "(not (not q)) or (not p)", ["p","q"]),
    ("Distribution",     "p or (q and r)",       "(p or q) and (p or r)", ["p","q","r"]),
    ("Absorption",       "p or (p and q)",       "p",                     ["p","q"]),
    ("Double negation",  "not (not p)",          "p",                     ["p"]),
    ("XOR expansion",    "p != q",               "(p or q) and not (p and q)", ["p","q"]),
    ("এটা ভুল হওয়া উচিত","not (p and q)",        "(not p) and (not q)",   ["p","q"]),
]

for name, a, b, vs in LAWS:
    mark = "✓" if equivalent(a, b, vs) else "✗"
    print(f"{mark}  {name}")

print("\np → q -এর DNF:", to_dnf("(not p) or q", ["p","q"]))
print("p → q -এর CNF:", to_cnf("(not p) or q", ["p","q"]))
print("\nXOR -এর DNF:  ", to_dnf("p != q", ["p","q"]))
print("XOR -এর CNF:  ", to_cnf("p != q", ["p","q"]))

শেষ law-টা ইচ্ছে করে ভুল রেখেছি — ✗ না দেখালে আপনার code-এ bug আছে।

নিজে বাড়ান:

তিনটা variable-এর সব 2^8 = 256 টা boolean function-এর DNF ছাপুন
এমন একটা expression খুঁজুন যার DNF ছোট কিন্তু CNF বড় (বা উল্টো)
simplify() লিখুন যা DNF থেকে redundant term বাদ দেয় (এটাই Quine–McCluskey algorithm-এর প্রথম ধাপ, যা Level 2-এ K-map হিসেবে ফিরবে)
NAND-only রূপে রূপান্তর করুন এবং gate সংখ্যা গুনুন

বাস্তব সিস্টেমে

এই নিয়মগুলো কোথায় কোথায় চলছে

LLVM-এর InstCombine pass. LLVM-এ আক্ষরিকভাবে হাজারো pattern-rewrite নিয়ম আছে যেগুলো এই লেসনের বীজগণিত। InstCombineAndOrXor.cpp ফাইলটা প্রায় পুরোটাই De Morgan, absorption, আর distribution-এর প্রয়োগ।

SAT solver ও package manager. আপনি যখন npm install বা cargo build চালান, dependency version constraint-গুলো একটা বিশাল CNF formula-য় রূপান্তরিত হয়, তারপর SAT solver সমাধান করে। “কোন version combination সব constraint মানে?” — এটা আক্ষরিকভাবে SAT।

Hardware verification. Intel, AMD, ARM প্রতিটা chip design-এর correctness প্রমাণ করে formal method দিয়ে। প্রশ্নটা হয়: “এই circuit আর এই specification কি logically equivalent?” — উত্তর দেয় equivalence checker, যার ভেতরে BDD আর SAT।

১৯৯৪-এর Pentium FDIV bug — একটা division table-এ ৫টা ভুল entry — Intel-এর $৪৭৫ মিলিয়ন খরচ করিয়েছিল। এরপর থেকে formal verification industry standard।

Firewall ও access policy analysis. “এই ৫০০টা firewall rule-এ কি এমন কোনো ফাঁক আছে যেখান দিয়ে বাইরের traffic ঢুকতে পারে?” — এটা একটা satisfiability প্রশ্ন। AWS-এর Zelkova tool ঠিক এটাই করে IAM policy-র জন্য।

Compiler-এর dead code elimination. একটা branch-এর condition যদি contradiction হয়, পুরো branch-টা কখনো চলবে না — compiler সেটা মুছে দেয়। এটা ধরার জন্য লাগে ঠিক এই বীজগণিত।

যে ভুলগুলো সবাই করে

“De Morgan মানে শুধু 'সব উল্টে দাও'।”

প্রায়, কিন্তু ঠিক না — আর এই ‘প্রায়’-টাই bug তৈরি করে।

De Morgan তখনই প্রয়োগ হয় যখন negation একটা পুরো bracket-এর উপর বসে। আর প্রয়োগ করলে তিনটা জিনিস একসাথে বদলায়:

বাইরের ¬ মুছে যায়
ভেতরের প্রতিটা term-এ ¬ বসে
Operator উল্টে যায় ← এটাই সবাই ভুলে যায়

¬(p ∧ q ∧ r) ≡ ¬p ∨ ¬q ∨ ¬r        ✓ AND → OR
¬(p ∧ q ∧ r) ≡ ¬p ∧ ¬q ∧ ¬r        ✗ operator বদলায়নি

আর nested হলে ভেতর থেকে বাইরে ধাপে ধাপে করুন:

¬(p ∨ (q ∧ ¬r))
≡ ¬p ∧ ¬(q ∧ ¬r)      [বাইরের OR → AND]
≡ ¬p ∧ (¬q ∨ ¬¬r)     [ভেতরের AND → OR]
≡ ¬p ∧ (¬q ∨ r)       [double negation]

“Expression সরল করলে সবসময় কোড দ্রুত হয়।”

প্রায়ই না। আধুনিক compiler এমনিতেই এই optimization করে — আপনি হাতে করলে extra গতি সাধারণত শূন্য।

সরলীকরণের আসল লাভ পাঠযোগ্যতা আর correctness। একটা ৭-operator nested negation পড়ে কেউ নিশ্চিত হতে পারে না; ৩-operator flat শর্ত পড়ে পারে।

তবে ব্যতিক্রম আছে: evaluation-এর খরচ যদি অসম হয়। যদি একটা check সস্তা (boolean flag) আর আরেকটা দামি (database query), তাহলে ক্রমটা গুরুত্বপূর্ণ — সস্তাটা আগে রাখলে short-circuit বেশি কাজ বাঁচায়। আর এই ক্রম compiler বদলাতে পারে না, কারণ side effect থাকতে পারে।

“CNF আর DNF শুধু academic form।”

DNF-টা মোটামুটি academic, সত্যি। কিন্তু CNF শিল্পক্ষেত্রে অপরিহার্য — কারণ প্রতিটা SAT solver-এর input format (DIMACS) হলো CNF।

আর SAT solver যেখানে যেখানে চলছে: chip verification, program analysis, AI planning, cryptanalysis, scheduling, bioinformatics, আর আপনার package manager। মিলিয়ন-variable formula আজকাল সেকেন্ডে সমাধান হয়, যদিও তাত্ত্বিকভাবে সমস্যাটা NP-complete।

তাত্ত্বিকভাবে কঠিন কিন্তু বাস্তবে সমাধানযোগ্য — এই ফাঁকটা Level 13-এর সবচেয়ে আকর্ষণীয় গল্পগুলোর একটা।

বুঝেছেন কি না দেখুন

সরল করুন: ¬(¬p ∨ q) ∨ (p ∧ ¬q) — প্রতিটা ধাপে কোন নিয়ম ব্যবহার করলেন লিখুন।

প্রয়োগ

¬(¬p ∨ q) ∨ (p ∧ ¬q)
≡ (¬¬p ∧ ¬q) ∨ (p ∧ ¬q)      [De Morgan — OR ভাঙলে AND]
≡ (p ∧ ¬q) ∨ (p ∧ ¬q)        [double negation]
≡ p ∧ ¬q                      [idempotent: x ∨ x ≡ x]

যাচাই — p ∧ ¬q সত্য কেবল p=T, q=F-এ। মূল expression-এ: ¬(¬T ∨ F) ∨ (T ∧ ¬F) = ¬(F ∨ F) ∨ (T ∧ T) = T ∨ T = T ✓

আর p=T, q=T-এ: ¬(F ∨ T) ∨ (T ∧ F) = ¬T ∨ F = F ∨ F = F ✓

p ⊕ q (XOR) কে শুধু ¬, ∧, ∨ দিয়ে দুইভাবে লিখুন — একবার DNF আকারে, একবার অন্যভাবে। দুটোর মধ্যে কোনটা কম operator ব্যবহার করে?

যুক্তি

XOR-এর truth table: সত্য যখন p ≠ q, অর্থাৎ row (F,T) আর (T,F)।

DNF রূপ (সত্য row থেকে):

(¬p ∧ q) ∨ (p ∧ ¬q)

Operator গুনি: ২টা ¬, ২টা ∧, ১টা ∨ = ৫টা

বিকল্প রূপ (“অন্তত একটা সত্য, কিন্তু দুটো নয়”):

(p ∨ q) ∧ ¬(p ∧ q)

Operator: ১টা ∨, ২টা ∧, ১টা ¬ = ৪টা

দ্বিতীয়টা কম — একটা operator বাঁচল।

CNF রূপ (মিথ্যা row থেকে, literal উল্টে):

(p ∨ q) ∧ (¬p ∨ ¬q)

এটাও ৪টা, আর এটাই সবচেয়ে প্রতিসম রূপ। খেয়াল করুন এটা বিকল্প রূপটারই De Morgan প্রয়োগ করা চেহারা।

Hardware-এর দৃষ্টিতে: XOR এত ঘন ঘন লাগে (প্রতিটা adder-এ, প্রতিটা parity check-এ, প্রতিটা cryptographic round-এ) যে chip designer একে আলাদা primitive gate হিসেবেই বানান — ভাঙেন না। Level 2-এ দেখব XOR CMOS-এ কীভাবে বানানো হয়।

একটা ক্যাশে invalidation শর্ত: “entry বাদ দাও যদি সেটা expired হয়, অথবা (manually invalidated হয় এবং pinned না হয়)। তবে entry যদি pinned হয়, কোনোভাবেই বাদ দেওয়া যাবে না।”

শেষ বাক্যটা কি প্রথম দুটোর সাথে সঙ্গতিপূর্ণ? Formula লিখে বিশ্লেষণ করুন।

ডিজাইন

প্রথম দুই বাক্য থেকে: e ∨ (m ∧ ¬p) — যেখানে e=expired, m=manually invalidated, p=pinned।

তৃতীয় বাক্য দাবি করে: p → ¬evict, অর্থাৎ p সত্য হলে formula মিথ্যা হতে হবে।

p = T বসাই:

e ∨ (m ∧ ¬T) ≡ e ∨ (m ∧ F) ≡ e ∨ F ≡ e

তাহলে pinned entry-ও evict হবে যদি e (expired) সত্য হয়। অসঙ্গতি।

Specification-টা স্ববিরোধী — বা অন্তত অস্পষ্ট। দুটো পড়া সম্ভব:

পড়া ১ — pinned সর্বোচ্চ অগ্রাধিকার:

¬p ∧ (e ∨ m)

Pinned হলে কখনো evict নয়, এমনকি expired হলেও।

পড়া ২ — expiry pin-এর উপরে:

e ∨ (m ∧ ¬p)

মূল formula-টাই, আর তৃতীয় বাক্যটা শুধু manual invalidation-এর ক্ষেত্রে প্রযোজ্য।

শিক্ষণীয়: এই ধরনের অস্পষ্টতা প্রাকৃতিক ভাষার specification-এ সর্বত্র। Formula-য় লেখামাত্র অসঙ্গতিটা দৃশ্যমান হয়ে গেল — এটাই formal specification-এর মূল মূল্য।

বাস্তবে Redis, Memcached-এর মতো সিস্টেমে সাধারণত পড়া ২ বেছে নেওয়া হয়: expired data মেয়াদোত্তীর্ণ, pin করা থাকলেও সেটা আর বৈধ নয়। কিন্তু সিদ্ধান্তটা স্পষ্ট করে লিখে রাখতে হয়।

প্রমাণ করুন p → (q → r) আর (p ∧ q) → r logically equivalent। তারপর ব্যাখ্যা করুন এটা কেন functional programming-এর currying-এর সাথে সম্পর্কিত।

যুক্তি

বীজগণিত দিয়ে প্রমাণ:

p → (q → r)
≡ ¬p ∨ (q → r)        [implication ভাঙা]
≡ ¬p ∨ (¬q ∨ r)       [আবার]
≡ (¬p ∨ ¬q) ∨ r       [associative]
≡ ¬(p ∧ q) ∨ r        [De Morgan, উল্টো দিকে]
≡ (p ∧ q) → r         [implication জোড়া] ∎

Currying-এর সাথে সম্পর্ক:

Curry–Howard correspondence অনুযায়ী proposition = type, proof = program। এই দৃষ্টিতে:

Logic	Type theory
`p → q`	`p -> q` (function type)
`p ∧ q`	`(p, q)` (tuple/product type)
`p ∨ q`	`Either p q` (sum type)

তাহলে আমাদের equivalence-টা হয়ে যায়:

p -> (q -> r)     ≅     (p, q) -> r

এটাই currying! একটা দুই-argument function আর একটা function যা একটা function ফেরত দেয় — এরা isomorphic।

curry   :: ((a, b) -> c) -> (a -> b -> c)
uncurry :: (a -> b -> c) -> ((a, b) -> c)

অর্থাৎ Haskell-এর curry/uncurry জোড়াটা আক্ষরিকভাবে এই logical equivalence-এর computational রূপ।

Level 5 (Programming Languages) আর Level 13 (Type theory)-তে আমরা এই সংযোগটা পুরোপুরি খুলব। আপাতত শুধু এটুকু মনে রাখুন: logic আর programming আলাদা দুইটা জিনিস নয় — একই জিনিসের দুইটা ভাষা।

এই দুইটা কি equivalent? (p → q) ∨ (q → p) আর T। উত্তর দেওয়ার আগে অনুমান করুন, তারপর যাচাই করুন।

প্রয়োগ

হ্যাঁ, এটা একটা tautology — সবসময় সত্য। অনেকের কাছে এটা প্রথমে অস্বস্তিকর লাগে।

(p → q) ∨ (q → p)
≡ (¬p ∨ q) ∨ (¬q ∨ p)      [implication ভাঙা]
≡ (¬p ∨ p) ∨ (q ∨ ¬q)      [commutative + associative দিয়ে সাজানো]
≡ T ∨ T                     [excluded middle, দুইবার]
≡ T                          ∎

কেন এটা অস্বস্তিকর লাগে: স্বাভাবিক ভাষায় এর মানে দাঁড়ায় — “যেকোনো দুইটা বাক্য নিন; হয় প্রথমটা দ্বিতীয়টাকে বোঝায়, নয় দ্বিতীয়টা প্রথমটাকে।” শুনতে অর্থহীন।

কিন্তু মনে রাখুন: material implication কার্যকারণ নিয়ে কিছু বলে না। p মিথ্যা হলেই p → q সত্য, q যাই হোক। তাই:

p মিথ্যা হলে → বাঁ পাশ সত্য → পুরোটা সত্য
p সত্য হলে → q → p-এর ডান পাশ সত্য → ডান পাশ সত্য → পুরোটা সত্য

কোনো তৃতীয় সম্ভাবনা নেই।

এই অস্বস্তিই কারণ যে দার্শনিক ও গণিতবিদরা relevance logic আর modal logic তৈরি করেছেন, যেখানে implication-এর জন্য বাঁ-ডান পাশের মধ্যে প্রকৃত সম্পর্ক থাকা লাগে। Computer science-এ আমরা প্রায় সবসময় material implication-ই ব্যবহার করি, কারণ এটা যান্ত্রিকভাবে হিসাবযোগ্য।

এরপর কী

এখন পর্যন্ত আমরা যা করেছি সবই propositional — প্রতিটা proposition একটা অবিভাজ্য একক, শুধু T বা F।

কিন্তু এই ভাষায় এই বাক্যটা লেখাই যায় না:

“array-এর প্রতিটা element ধনাত্মক”

কারণ “প্রতিটা” বলতে গেলে element-গুলোর ভেতরে তাকাতে হয়, আর propositional logic-এ কোনো কিছুর ভেতরে তাকানোর ব্যবস্থা নেই।

পরের লেসনে আসছে predicate logic ও quantifier — ∀ (সব) আর ∃ (অন্তত একটা)। এই দুইটা প্রতীক ছাড়া কোনো algorithm-এর correctness লেখাই সম্ভব না, কোনো database query-র semantics সংজ্ঞায়িত করা সম্ভব না, আর কোনো loop invariant প্রকাশ করা সম্ভব না।

Logical Equivalence — expression সরল করার বীজগণিত

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

Equivalent মানে কী

মৌলিক নিয়মগুলো

Identity ও domination

Idempotence ও negation

Commutative, associative, distributive

De Morgan’s laws — সবচেয়ে গুরুত্বপূর্ণ

Absorption ও অন্যান্য

ভেতরে কী ঘটছে

দুইভাবে প্রমাণ

পদ্ধতি ১: Truth table (যান্ত্রিক, নিশ্চিত)

পদ্ধতি ২: বীজগণিত (দ্রুত, কিন্তু নিয়ম জানতে হয়)

দুইটা normal form

DNF — Disjunctive Normal Form

CNF — Conjunctive Normal Form

Functional completeness

NAND দিয়ে সবকিছু

উদাহরণ

বাস্তব একটা condition সরল করা

নিজে চালিয়ে দেখুন

Compiler নিজে De Morgan প্রয়োগ করছে — দেখুন

PostgreSQL query planner-এর বীজগণিত

নিজে বানান

Equivalence Checker ও DNF Generator

বাস্তব সিস্টেমে

এই নিয়মগুলো কোথায় কোথায় চলছে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

Equivalent মানে কী

মৌলিক নিয়মগুলো

Identity ও domination

Idempotence ও negation

Commutative, associative, distributive

De Morgan’s laws — সবচেয়ে গুরুত্বপূর্ণ

Absorption ও অন্যান্য

⚙ভেতরে কী ঘটছেUnder the hood

দুইভাবে প্রমাণ

পদ্ধতি ১: Truth table (যান্ত্রিক, নিশ্চিত)

পদ্ধতি ২: বীজগণিত (দ্রুত, কিন্তু নিয়ম জানতে হয়)

দুইটা normal form

DNF — Disjunctive Normal Form

CNF — Conjunctive Normal Form

Functional completeness

NAND দিয়ে সবকিছু

▶উদাহরণExample

বাস্তব একটা condition সরল করা

⌘নিজে চালিয়ে দেখুনExperiment

Compiler নিজে De Morgan প্রয়োগ করছে — দেখুন

PostgreSQL query planner-এর বীজগণিত

⚒নিজে বানানBuild it yourself

Equivalence Checker ও DNF Generator

◉বাস্তব সিস্টেমেReal-world usage

এই নিয়মগুলো কোথায় কোথায় চলছে

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী