Predicate logic আর quantifier — "সব" আর "কোনো একটি" লেখা

১ · "প্রতিটি অর্ডার" — যেখানে propositional logic আটকে যায়

পর্ব ০২-এ আমরা proposition নিয়ে কাজ করেছি: এমন বাক্য, যা হয় সত্য নয়তো মিথ্যা। "অর্ডার B101 ডেলিভার হয়েছে" একটি proposition, একে p বলা যায়। "অর্ডার B102 ডেলিভার হয়েছে" আরেকটি, একে q. কিন্তু বাজারঘরের দিনে কয়েক হাজার অর্ডার আসে। এখন এই নিয়মটি লিখতে চাই:

"ঢাকার প্রতিটি অর্ডার ২৪ ঘণ্টার মধ্যে ডেলিভার হয়।"

Propositional logic-এ এর জন্য প্রতিটি অর্ডারের আলাদা প্রতীক লাগবে, আর তাদের সবাইকে ∧ দিয়ে জুড়তে হবে। কাল নতুন অর্ডার এলে সূত্রটিও বদলাতে হবে। আরও বড় সমস্যা: "প্রতিটি পূর্ণসংখ্যা n-এর জন্য n² ≥ 0" জাতীয় কথায় বস্তু অসীম, সেখানে ∧-এর শিকল কখনো শেষ হয় না। Propositional logic প্রতিটি বাক্যকে একটি আস্ত বাক্স হিসেবে দেখে; বাক্সের ভেতরের "কে" আর "কী গুণ" সে দেখতে পায় না।

উদাহরণ: P(x): "x² ≥ x". P(3) মানে 9 ≥ 3, সত্য। P(1/2) মানে 1/4 ≥ 1/2, মিথ্যা। P(x) নিজে কিছুই দাবি করে না; সে শুধু একটি ছাঁচ। Programming-এর ভাষায় predicate হলো এমন একটি function, যা True বা False ফেরত দেয়, যেমন def D(order): return order.status == "delivered". এই মিলটি আমরা পুরো পর্বে কাজে লাগাব।

Predicate দিয়ে তৈরি এই বড় ব্যবস্থাকে বলে predicate logic বা first-order logic. "First-order" কথাটির মানে: quantifier শুধু বস্তুর (অর্ডার, সংখ্যা, গ্রাহক) ওপর বসে, predicate-এর ওপর নয়। AI-এর ভিত্তি কোর্সের পর্ব ৪৬-এ দেখবেন একই ভাষা দিয়ে AI agent-এর knowledge base লেখা হয়; এখানে আমরা দেখব এর গণিত: সংজ্ঞা, সূত্র আর প্রমাণ।

২ · দুই quantifier — ∀ আর ∃

একটি propositional function থেকে proposition পাওয়ার দুটি উপায় আছে। প্রথমটি আগেই দেখেছি: x-এ একটি নির্দিষ্ট মান বসানো। দ্বিতীয়টি হলো x সম্পর্কে একটি "পরিমাণ" বলা: সবার জন্য, নাকি অন্তত একজনের জন্য। এই পরিমাণ-বাচক চিহ্নকে বলে quantifier.

Domain সসীম হলে, ধরুন D = {a₁, a₂, …, a_n}, তখন দুটি quantifier-কে পুরোনো connective দিয়েই লেখা যায়:

∀x P(x) ≡ P(a₁) ∧ P(a₂) ∧ … ∧ P(a_n)
∃x P(x) ≡ P(a₁) ∨ P(a₂) ∨ … ∨ P(a_n)

এই দুই লাইন থেকেই অনেক কিছু বোঝা যায়। একটি লম্বা ∧ মিথ্যা হতে একটি মিথ্যা অংশই যথেষ্ট; তাই ∀-দাবি ভাঙতে একটি বস্তু লাগে, যাকে বলে counterexample. আর একটি লম্বা ∨ সত্য হতে একটি সত্য অংশই যথেষ্ট; তাই ∃-দাবি প্রমাণে একটি বস্তু দেখানোই যথেষ্ট, যাকে বলে witness. নিচের ছবিতে বাজারঘরের পাঁচটি অর্ডার দিয়ে ব্যাপারটি দেখুন।

Domain বদলালে সত্য-মিথ্যাও বদলায়

∀x (x² ≥ x) বাক্যটি নিন। Domain ℤ (সব পূর্ণসংখ্যা, ঋণাত্মকসহ) হলে এটি সত্য। প্রমাণ: x ≤ 0 হলে x² ≥ 0 ≥ x; আর x ≥ 1 হলে x ≥ 1 দিয়ে দুই দিক গুণ করে x² ≥ x; পূর্ণসংখ্যায় এই দুই ঘরের বাইরে কিছু নেই। ∎ কিন্তু domain ℝ (সব বাস্তব সংখ্যা) হলে x = 1/2 একটি counterexample, কারণ 1/4 < 1/2. একই সূত্র, ভিন্ন domain, ভিন্ন উত্তর। এজন্যই পরীক্ষার প্রশ্নে domain না বলা থাকলে প্রথমে সেটি লিখে নিন।

৩ · Scope, অগ্রাধিকার আর bound বনাম free variable

একটি quantifier বাক্যের কতটুকু অংশে খাটে, সেটি তার scope. Programming-এ একটি loop variable যেমন শুধু loop-এর ভেতরে বাঁচে, তেমনি ∀x-এর x শুধু তার scope-এর ভেতরে অর্থ পায়।

উদাহরণ: ∃x (Ord(x, y) ∧ D(x)). এখানে x bound, কিন্তু y free. তাই এটি এখনো একটি propositional function, y-এর ওপর নির্ভর করে: "গ্রাহক y-এর অন্তত একটি অর্ডার ডেলিভার হয়েছে" ধরনের একটি ছাঁচ। y-এ একজন নির্দিষ্ট গ্রাহক বসালে, অথবা সামনে ∀y বা ∃y বসালে, তবেই এটি proposition হবে।

অগ্রাধিকার: quantifier সবার আগে বাঁধে

বেশিরভাগ discrete math বইয়ের প্রথা হলো: ∀ আর ∃ সব connective-এর চেয়ে বেশি শক্তভাবে বাঁধে। তাই

∀x P(x) ∨ Q(x) মানে (∀x P(x)) ∨ Q(x), ∀x (P(x) ∨ Q(x)) নয়।

প্রথম রূপে শেষের x-টি free, কারণ ∀x-এর scope শুধু P(x) পর্যন্ত। দ্বিতীয় রূপে দুটিই bound. দুটির অর্থও আলাদা, যা অংশ ৬-এ প্রমাণ করব। কিছু বই আর AI সংক্রান্ত লেখায় উল্টো প্রথা চলে, যেখানে quantifier-এর scope যতদূর সম্ভব ডানে যায়। তাই নিরাপদ অভ্যাস একটাই: quantifier-এর পরে সবসময় বন্ধনী দিন।

Bound variable-এর নাম বদলালে অর্থ বদলায় না: ∀x P(x) আর ∀z P(z) একই কথা, ঠিক যেমন for i in range(5) আর for k in range(5) একই loop. শুধু খেয়াল রাখবেন, নতুন নামটি যেন সূত্রের আরেকটি free variable-এর সঙ্গে মিলে না যায়। ∃x Ord(x, y)-তে x-এর নাম y রাখলে ∃y Ord(y, y) হয়, যার অর্থ সম্পূর্ণ আলাদা ("কেউ নিজেই নিজের অর্ডার")। একে বলে variable capture, আর প্রমাণে এটি একটি চেনা ভুল।

৪ · বাংলা বাক্য থেকে সূত্র — "সব"-এর সঙ্গে →, "কিছু"-র সঙ্গে ∧

বাস্তবের বাক্য প্রায় কখনো পুরো domain নিয়ে কথা বলে না। "ঢাকার প্রতিটি অর্ডার" মানে সব অর্ডার নয়, শুধু ঢাকারগুলো। এমন সীমিত কথা লেখার দুটি উপায় আছে। একটি হলো domain-টাই ছোট করা (শুধু ঢাকার অর্ডার)। কিন্তু একই বাক্যে অনেক রকম শর্ত থাকলে সেটি অসুবিধার, তাই সাধারণ উপায় হলো domain বড় রেখে শর্তটি একটি predicate দিয়ে লেখা। একে বলে restricted quantifier:

কেন ∀-এর সঙ্গে → আর ∃-এর সঙ্গে ∧? দুটি ভুল রূপ নিয়ে ভাবলেই বোঝা যায়।

• ∀x (C(x) ∧ P(x)) কেন ভুল: এটি দাবি করে domain-এর প্রতিটি বস্তুই C. সব অর্ডারের domain-এ একটি খুলনার অর্ডার থাকলেই এটি মিথ্যা, যদিও ঢাকার সব অর্ডার সময়মতো গেছে। → ব্যবহার করলে খুলনার অর্ডারের জন্য C(x) মিথ্যা, আর মিথ্যা → যেকোনো কিছু সত্য; অর্থাৎ বাইরের বস্তুগুলো দাবিকে বিরক্ত করে না।
• ∃x (C(x) → P(x)) কেন ভুল: একটিমাত্র খুলনার অর্ডার থাকলেই C(x) মিথ্যা, তাই C(x) → P(x) সত্য, তাই পুরো ∃ সত্য, ঢাকার অর্ডার সম্পর্কে কিছু না জেনেই। এই সূত্র প্রায় সবসময় বিনা কারণে সত্য হয়ে যায়।

নিচের stepper-এ তিনটি বাক্য ধাপে ধাপে অনুবাদ করা হয়েছে। Domain: বাজারঘরের সব অর্ডার। Predicate: D(x) ঢাকার অর্ডার, F(x) ২৪ ঘণ্টায় ডেলিভারি, K(x) কুপন ব্যবহার হয়েছে, Z(x) ডেলিভারি ফ্রি, B(x) বাতিল, R(x) রিভিউ আছে।

Python-এ ∀ মানে all(), ∃ মানে any()

সসীম domain-এ এই সূত্রগুলোর মান সরাসরি হিসাব করা যায়। Python-এর all(...) একটি লম্বা ∧, আর any(...) একটি লম্বা ∨, ঠিক অংশ ২-এর সংজ্ঞার মতো। → এর জন্য Python-এ আলাদা operator নেই, তাই p → q ≡ ¬p ∨ q দিয়ে একটি ছোট function লেখা হয়েছে। নিচের ব্লকে বাজারঘরের ছয়টি কাল্পনিক অর্ডারে তিনটি বাক্য, ∃! আর ফাঁকা domain যাচাই করা হয়েছে। ব্লকটি আপনার ব্রাউজারেই চলে (Pyodide, অর্থাৎ WebAssembly-তে compile করা আসল CPython); প্রথমবার চালাতে কয়েক সেকেন্ড লাগতে পারে।

# বাজারঘরের ৬টি কাল্পনিক অর্ডার = domain D
keys = ("id", "district", "hours", "coupon", "free", "cancelled", "review")
rows = [
    ("B101", "Dhaka",    20, 1, 1, 0, 1),
    ("B102", "Dhaka",    22, 0, 0, 0, 0),
    ("B103", "Khulna",   40, 1, 0, 0, 1),
    ("B104", "Sylhet",   30, 0, 0, 1, 0),
    ("B105", "Dhaka",    26, 0, 0, 0, 1),
    ("B106", "Rajshahi", 48, 1, 1, 0, 0),
]
orders = [dict(zip(keys, r)) for r in rows]
def implies(p, q):
    return (not p) or q

# S1: ∀x (Dhaka(x) → F24(x))
s1 = all(implies(o["district"] == "Dhaka", o["hours"] <= 24) for o in orders)
bad = [o["id"] for o in orders
       if not implies(o["district"] == "Dhaka", o["hours"] <= 24)]
print("S1 forall Dhaka->24h:", s1, "| counterexamples:", bad)

# S2: ∃x (coupon(x) ∧ free(x))
wit = [o["id"] for o in orders if o["coupon"] and o["free"]]
print("S2 exists coupon&free:", any(o["coupon"] and o["free"] for o in orders),
      "| witnesses:", wit)

# S3: ∀x (cancelled(x) → ¬review(x))
print("S3 forall cancelled->no review:",
      all(implies(o["cancelled"], not o["review"]) for o in orders))

# ∃!x: ঠিক একটি
for d in ["Rajshahi", "Dhaka"]:
    k = sum(o["district"] == d for o in orders)
    print(f"exists-unique {d}: {k == 1} (count {k})")

print("empty domain: all ->", all([]), "| any ->", any([]))

S1 forall Dhaka->24h: False | counterexamples: ['B105']
S2 exists coupon&free: True | witnesses: ['B101', 'B106']
S3 forall cancelled->no review: True
exists-unique Rajshahi: True (count 1)
exists-unique Dhaka: False (count 3)
empty domain: all -> True | any -> False

৫ · Negation — ¬ ভেতরে ঢুকলে quantifier উল্টে যায়

বাজারঘরের ম্যানেজার দাবি করলেন: "প্রতিটি ডেলিভারিম্যান আজ সময়মতো এসেছেন।" দাবিটি মিথ্যা প্রমাণ করতে কী লাগবে? সবাই দেরিতে এসেছেন, এমন দেখানোর দরকার নেই; অন্তত একজন দেরিতে এসেছেন দেখালেই যথেষ্ট। এটাই quantifier-এর De Morgan সূত্রের মূল কথা।

প্রমাণ (প্রথম সূত্র): দুটি বাক্য equivalent মানে, যেকোনো domain আর P-এর যেকোনো অর্থে দুটির মান সমান। দুই দিক আলাদা করে দেখাই।

1. ধরি ¬∀x P(x) সত্য। তাহলে ∀x P(x) মিথ্যা। (¬-এর সংজ্ঞা)
2. ∀x P(x) মিথ্যা মানে "প্রতিটি a-র জন্য P(a)" কথাটি খাটে না, অর্থাৎ domain-এ অন্তত একটি a আছে যার জন্য P(a) মিথ্যা। (∀-এর সংজ্ঞা)
3. সেই a-র জন্য ¬P(a) সত্য, তাই ∃x ¬P(x) সত্য; a হলো witness. (∃-এর সংজ্ঞা)
4. উল্টো দিক: ধরি ∃x ¬P(x) সত্য, witness b. তাহলে P(b) মিথ্যা, তাই "প্রতিটি a-র জন্য P(a)" খাটে না, অর্থাৎ ∀x P(x) মিথ্যা, অর্থাৎ ¬∀x P(x) সত্য। (∀ আর ¬-এর সংজ্ঞা)
5. দুই দিকেই একটি সত্য হলে অন্যটি সত্য; তাই একটি মিথ্যা হলে অন্যটিও মিথ্যা, এবং দুটির মান সবসময় সমান। ∎

দ্বিতীয় সূত্র প্রথমটি থেকেই আসে। প্রথম সূত্রে P-এর জায়গায় ¬P বসালে: ¬∀x ¬P(x) ≡ ∃x ¬¬P(x) ≡ ∃x P(x). দুই দিকে ¬ নিলে ∀x ¬P(x) ≡ ¬∃x P(x). ∎ সসীম domain-এ এটি আসলে পর্ব ০৩-এর সাধারণ De Morgan: ¬(P(a₁) ∧ … ∧ P(a_n)) ≡ ¬P(a₁) ∨ … ∨ ¬P(a_n). তাই একে বলা হয় quantifier-এর De Morgan সূত্র.

Restricted রূপে এই সূত্র আর অংশ ৪-এর নিয়ম মিলিয়ে দুটি দরকারি ফল পাওয়া যায়, পরীক্ষায় এগুলো বারবার আসে:

¬∀x (C(x) → P(x)) ≡ ∃x (C(x) ∧ ¬P(x))
¬∃x (C(x) ∧ P(x)) ≡ ∀x (C(x) → ¬P(x))

প্রথমটির প্রমাণ: ¬∀x (C → P) ≡ ∃x ¬(C → P) (De Morgan) ≡ ∃x ¬(¬C ∨ P) (p → q ≡ ¬p ∨ q) ≡ ∃x (C ∧ ¬P) (De Morgan আর double negation). ∎ দ্বিতীয়টি একইভাবে। অংশ ৪-এর বাক্য ৩-এর দুটি রূপ এভাবেই মেলে।

এবার নিয়মগুলো একসঙ্গে লাগিয়ে একটি দুই-quantifier বাক্যকে negate করি। প্রতিটি ধাপে ¬ এক ঘর ভেতরে যায়, আর যে quantifier পার হয় সেটি উল্টে যায়। Predicate: Ord(c, o) মানে গ্রাহক c অর্ডার o দিয়েছেন, Del(o) মানে o ডেলিভার হয়েছে।

৬ · কোন equivalence খাটে — ∀ ভাগ হয় ∧-এ, ∨-এ নয়

সাধারণ বীজগণিতে 2(a + b) = 2a + 2b; গুণ যোগের ওপর ভাগ হয়ে যায় (distributes). Quantifier-এরও এমন নিয়ম আছে, কিন্তু অর্ধেক জোড়ায় খাটে, অর্ধেকে খাটে না। ভুল জোড়াটি মনে রাখা পরীক্ষার জন্য খুব জরুরি।

(ক)-এর প্রমাণ:

1. ধরি বাঁ দিক সত্য: প্রতিটি a-র জন্য P(a) ∧ Q(a). তাহলে প্রতিটি a-র জন্য P(a) (∧ থেকে আলাদা করা), তাই ∀x P(x); একইভাবে ∀x Q(x). তাই ডান দিক সত্য।
2. ধরি ডান দিক সত্য। যেকোনো a নিন। ∀x P(x) থেকে P(a), ∀x Q(x) থেকে Q(a), তাই P(a) ∧ Q(a). a যেকোনো ছিল, তাই ∀x (P(x) ∧ Q(x)).
3. দুই দিকেই একটি থেকে অন্যটি আসে, তাই দুটি equivalent. ∎

(খ)-এর প্রমাণ (ক) থেকে De Morgan দিয়ে আসে: ∃x (P ∨ Q) ≡ ¬∀x ¬(P ∨ Q) ≡ ¬∀x (¬P ∧ ¬Q) ≡ ¬(∀x ¬P ∧ ∀x ¬Q) ≡ ¬∀x ¬P ∨ ¬∀x ¬Q ≡ ∃x P ∨ ∃x Q. ∎ এখানে তৃতীয় ধাপে (ক) ব্যবহার হয়েছে, P আর Q-এর জায়গায় ¬P আর ¬Q দিয়ে।

(গ)-এর counterexample: Domain {1, 2}, P(x): "x বিজোড়", Q(x): "x জোড়"। প্রতিটি সংখ্যা জোড় অথবা বিজোড়, তাই ∀x (P(x) ∨ Q(x)) সত্য। কিন্তু সব সংখ্যা বিজোড় নয় (২ আছে), সব জোড়ও নয় (১ আছে); তাই ∀x P(x) ∨ ∀x Q(x) মিথ্যা। বাজারঘরের ভাষায়: "প্রতিটি অর্ডার bKash বা ক্যাশে পরিশোধ হয়েছে" আর "সব অর্ডার bKash-এ, অথবা সব অর্ডার ক্যাশে" মোটেই এক কথা নয়। (ঘ)-এর counterexample একই domain-এ: ∃x P(x) আর ∃x Q(x) দুটিই সত্য, কিন্তু একই সঙ্গে জোড় ও বিজোড় কোনো সংখ্যা নেই।

প্রমাণ হয়ে গেছে, তবু সংখ্যা দিয়ে মিলিয়ে দেখা ভালো অভ্যাস। নিচের ব্লক domain-এর আকার n = 1 থেকে 4 পর্যন্ত P আর Q-এর প্রতিটি সম্ভাব্য অর্থ (n উপাদানের domain-এ একটি predicate মানে 2ⁿ রকম True/False তালিকা) চেষ্টা করে, আর প্রতিটি দাবি কতবার ভাঙে গোনে। এটি পর্ব ০২-এর truth table-এর বড় ভাই: সারি হলো (P, Q) জোড়া।

from itertools import product

def A(P): return all(P)      # ∀x P(x); P = প্রতিটি x-এর True/False
def E(P): return any(P)      # ∃x P(x)
def AND(P, Q): return [p and q for p, q in zip(P, Q)]
def OR(P, Q): return [p or q for p, q in zip(P, Q)]
def NOT(P): return [not p for p in P]

laws = {
    "not forall P == exists not P": lambda P, Q: (not A(P)) == E(NOT(P)),
    "not exists P == forall not P": lambda P, Q: (not E(P)) == A(NOT(P)),
    "forall(P and Q) == A P and A Q": lambda P, Q: A(AND(P, Q)) == (A(P) and A(Q)),
    "exists(P or Q) == E P or E Q": lambda P, Q: E(OR(P, Q)) == (E(P) or E(Q)),
    "forall(P or Q) == A P or A Q": lambda P, Q: A(OR(P, Q)) == (A(P) or A(Q)),
    "exists(P and Q) == E P and E Q": lambda P, Q: E(AND(P, Q)) == (E(P) and E(Q)),
}
sizes = range(1, 5)                          # domain-এর আকার n = 1..4
print("pairs (P, Q) checked for n = 1..4:", [4 ** n for n in sizes])
for name, law in laws.items():
    fails = []
    for n in sizes:
        preds = list(product([False, True], repeat=n))
        fails.append(sum(not law(P, Q) for P in preds for Q in preds))
    print(f"{name:31} failures {fails}")

# সবচেয়ে ছোট counterexample: domain {x1, x2}
P, Q = [True, False], [False, True]
print("forall(P or Q) =", A(OR(P, Q)), "| A P or A Q =", A(P) or A(Q))

pairs (P, Q) checked for n = 1..4: [4, 16, 64, 256]
not forall P == exists not P    failures [0, 0, 0, 0]
not exists P == forall not P    failures [0, 0, 0, 0]
forall(P and Q) == A P and A Q  failures [0, 0, 0, 0]
exists(P or Q) == E P or E Q    failures [0, 0, 0, 0]
forall(P or Q) == A P or A Q    failures [0, 2, 12, 50]
exists(P and Q) == E P and E Q  failures [0, 2, 12, 50]
forall(P or Q) = True | A P or A Q = False

যে অংশে x নেই, তাকে বাইরে আনা যায়

q যদি এমন একটি বাক্য হয় যার ভেতরে x free নয় (যেমন "আজ হরতাল"), তাহলে ∀x (P(x) ∨ q) ≡ ∀x P(x) ∨ q, আর ∃x (P(x) ∧ q) ≡ ∃x P(x) ∧ q. যুক্তি: q-এর মান x-এর ওপর নির্ভর করে না। প্রথমটিতে q সত্য হলে দুই দিকই সত্য, আর q মিথ্যা হলে দুই দিকই ∀x P(x)-এর সমান। দ্বিতীয়টিতে q সত্য হলে দুই দিকই ∃x P(x), q মিথ্যা হলে দুই দিকই মিথ্যা। এর জোড়া দুটি, ∀x (P(x) ∧ q) ≡ ∀x P(x) ∧ q আর ∃x (P(x) ∨ q) ≡ ∃x P(x) ∨ q, একই যুক্তিতে খাটে, তবে একটি শর্তে: domain অশূন্য হতে হবে। শর্তটি কাকতালীয় নয়; পরের অংশ সেটি নিয়েই।

৭ · ফাঁকা domain আর vacuous truth

বাজারঘরের নতুন শাখা খুলেছে কক্সবাজারে, আজ সেখানে একটিও অর্ডার আসেনি। "কক্সবাজারের প্রতিটি অর্ডার সময়মতো ডেলিভার হয়েছে" — সত্য না মিথ্যা? সংজ্ঞা অনুযায়ী ∀ মিথ্যা হতে একটি counterexample লাগে, আর ফাঁকা সেটে কোনো counterexample নেই। তাই বাক্যটি সত্য। এমন "ফাঁকা কারণে সত্য"-কে বলে vacuous truth. পর্ব ০২-এ দেখেছেন মিথ্যা → যেকোনো কিছু সত্য; এটি তারই quantifier-রূপ।

এর একটি সুন্দর ব্যাখ্যা আছে। ∧-এর "নিরপেক্ষ" মান সত্য (p ∧ সত্য ≡ p), ঠিক যেমন গুণের নিরপেক্ষ মান ১; আর ∨-এর নিরপেক্ষ মান মিথ্যা, যেমন যোগের ০. শূন্যটি সংখ্যার গুণফল ১ ধরা হয়, শূন্যটি সংখ্যার যোগফল ০; একই যুক্তিতে শূন্যটি বাক্যের ∧ সত্য, শূন্যটি বাক্যের ∨ মিথ্যা। Python-এর all আর any ঠিক এই নিয়ম মানে।

এর ফলে একটি অদ্ভুত ব্যাপার ঘটে। স্বাভাবিকভাবে মনে হয় ∀x P(x) → ∃x P(x) সবসময় সত্য: সবার জন্য সত্য হলে অন্তত একজনের জন্য তো সত্যই। Domain অশূন্য হলে কথাটি ঠিক: একটি বস্তু a নিন, ∀ থেকে P(a), তাই ∃. কিন্তু ফাঁকা domain-এ বাঁ দিক সত্য আর ডান দিক মিথ্যা, তাই → মিথ্যা। একইভাবে ∃x (P(x) ∨ q) ≡ ∃x P(x) ∨ q ফাঁকা domain-এ ভাঙে (বাঁ দিক মিথ্যা, ডান দিক q).

৮ · Counterexample খোঁজা — একটি যথেষ্ট, হাজারটি মিলও প্রমাণ নয়

অংশ ২-এর লম্বা ∧ থেকে একটি অসম ব্যাপার বেরিয়ে আসে, যা গণিত আর software testing দুই জায়গাতেই মূল নীতি:

সসীম ছোট domain-এ সব বস্তু একে একে দেখলেই ∀-দাবির প্রমাণ হয়ে যায় (একে বলে exhaustive check). কিন্তু domain অসীম হলে কয়েক হাজার উদাহরণে মিলে যাওয়াও প্রমাণ নয়। গণিতের ইতিহাসের একটি বিখ্যাত উদাহরণ দেখুন। ১৬৪০ সালের দিকে Pierre de Fermat চিঠিতে লেখেন যে F(n) = 2²ⁿ + 1 আকারের সব সংখ্যা মৌলিক বলে তাঁর ধারণা। n = 0 থেকে 4 পর্যন্ত সত্যিই তাই: 3, 5, 17, 257, 65537. প্রায় এক শতাব্দী পরে, সাধারণত বলা হয় ১৭৩২ সালে, Leonhard Euler দেখান F(5) মৌলিক নয়। নিচের ব্লক সাধারণ trial division দিয়ে সেই counterexample নিজেই খুঁজে বের করে।

import math

def smallest_factor(m):
    """m-এর ১-এর চেয়ে বড় সবচেয়ে ছোট ভাজক (trial division)"""
    if m % 2 == 0:
        return 2
    d = 3
    while d * d <= m:
        if m % d == 0:
            return d
        d += 2
    return m                    # কোনো ভাজক নেই: m মৌলিক

# দাবি: ∀n ∈ {0, 1, 2, ...}, F(n) = 2^(2^n) + 1 মৌলিক
for n in range(6):
    F = 2 ** (2 ** n) + 1
    p = smallest_factor(F)
    if p == F:
        print(f"n = {n}: F = {F} is prime")
    else:
        print(f"n = {n}: F = {F} = {p} x {F // p}  <-- counterexample")
        break

# প্রমাণ নয়, যাচাই: দুই ভাজক মৌলিক কি না
print("641 prime?", smallest_factor(641) == 641,
      "| 6700417 prime?", smallest_factor(6700417) == 6700417)
print("checked divisors up to", math.isqrt(6700417), "for the second factor")

n = 0: F = 3 is prime
n = 1: F = 5 is prime
n = 2: F = 17 is prime
n = 3: F = 257 is prime
n = 4: F = 65537 is prime
n = 5: F = 4294967297 = 641 x 6700417  <-- counterexample
641 prime? True | 6700417 prime? True
checked divisors up to 2588 for the second factor

এর উল্টো দিকটিও মনে রাখুন। n = 0 থেকে 4-এর পাঁচটি উদাহরণ ∃n (F(n) মৌলিক)-এর জন্য যথেষ্টর চেয়েও বেশি; একটি witness, যেমন n = 0, দিলেই হতো। কিন্তু ∀-দাবির জন্য এগুলো কিছুই প্রমাণ করে না। আজও জানা নেই n ≥ 5-এ কোনো F(n) মৌলিক কি না; এটি একটি খোলা প্রশ্ন বলে জানা যায়। Proof-এর পদ্ধতি নিয়ে বিস্তারিত পর্ব ০৮ আর পর্ব ০৯-এ।

৯ · দুই quantifier একসঙ্গে — পরের পর্বের এক ঝলক

অংশ ৫-এর বাক্যে দুটি quantifier ছিল। এমন বাক্যে quantifier-এর ক্রম অর্থ বদলে দেয়, এবং এটি পর্ব ০৫-এর পুরো বিষয়। এখানে শুধু একটি ছোট টেবিলে পার্থক্যটি দেখি। ডেলিভারিম্যান জানতে চান, তিন গ্রাহক কোন সময়ে বাসায় থাকেন। Free(x, y) মানে গ্রাহক x সময় y-তে বাসায় আছেন (১ = আছেন)।

• ∀x ∃y Free(x, y): প্রতিটি গ্রাহকের নিজের কোনো একটি সুবিধাজনক সময় আছে। y গ্রাহক অনুযায়ী আলাদা হতে পারে।
• ∃y ∀x Free(x, y): এমন একটি সময় আছে, যখন সবাই বাসায় থাকেন। একটি y সবার জন্য খাটতে হবে।

সাধারণভাবে ∃y∀x P(x, y) → ∀x∃y P(x, y) সবসময় সত্য (একটি সময় সবার জন্য খাটলে প্রত্যেকের জন্য সেটিই witness), কিন্তু উল্টোটি নয়, ওপরের টেবিলই তার counterexample. কেন, কোথায় কাজে লাগে, আর nested loop ও SQL-এর সঙ্গে এর সম্পর্ক কী, সবই পর্ব ০৫ (Nested quantifier — ক্রম বদলালে অর্থ বদলায়)-এ।

১০ · AI-এর যুগে — quantifier-এ AI কোথায় ভুল করে

AI সহকারীকে "এই বাক্যটি predicate logic-এ লেখো" বললে সাধারণত চকচকে, আত্মবিশ্বাসী উত্তর আসে। প্রায়ই উত্তরটি ঠিক। কিন্তু quantifier-এর ক্ষেত্রে কয়েকটি ভুল এত নিয়মিত দেখা যায় যে সেগুলো চিনে রাখা দরকার। গণিতে AI-এর সাধারণ দুর্বলতাও এখানে খাটে: আত্মবিশ্বাসী কিন্তু ভুল প্রমাণ (যা প্রমাণ করার কথা সেটিই ধরে নেওয়া, converse প্রমাণ করে দেওয়া), উপপাদ্যের শর্ত বাদ দেওয়া (যেমন "domain অশূন্য"), আর বানানো reference.

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

• Domain স্পষ্ট লেখা আছে, আর প্রতিটি predicate-এর অর্থ এক বাক্যে বলা আছে
• ∀-এর সঙ্গে শর্ত → দিয়ে, ∃-এর সঙ্গে শর্ত ∧ দিয়ে বসেছে; ব্যতিক্রম থাকলে কারণ বুঝেছি
• Negation-এ ¬ প্রতিটি quantifier পার হওয়ার সময় quantifier উল্টেছে, ক্রম বদলায়নি
• ছোট একটি domain বানিয়ে Python-এর all/any দিয়ে মূল বাক্য আর উত্তর দুটির মান মিলিয়েছি
• কোনো equivalence দাবি করলে দুই-তিন বস্তুর domain-এ সব সম্ভাবনা চালিয়ে counterexample খুঁজেছি
• প্রমাণের প্রতিটি ধাপের যুক্তি আছে, আর উপপাদ্যের শর্ত (অশূন্য domain, x free নয়) বাদ পড়েনি
• সন্দেহ থাকলে একটি বিশ্বস্ত পাঠ্যবইয়ের সংজ্ঞার সঙ্গে মিলিয়েছি; AI-এর দেওয়া reference নিজে খুঁজে দেখেছি

SELECT c.id FROM customers c
WHERE NOT EXISTS (SELECT 1 FROM categories k
  WHERE NOT EXISTS (SELECT 1 FROM orders o
    WHERE o.customer_id = c.id AND o.category_id = k.id));