Nested quantifier — ক্রম বদলালে অর্থ বদলায়

১ · এক বাক্য, দুই অর্থ — quantifier-এর ক্রম কেন গুরুত্বপূর্ণ

বাজারঘরের ঢাকা অফিসে দুজন ম্যানেজার কথা বলছেন। প্রথমজন বললেন, “প্রতিটি এলাকায় কোনো না কোনো রাইডার যান।” দ্বিতীয়জন বললেন, “একজন রাইডার আছেন যিনি প্রতিটি এলাকায় যান।” দুটি বাক্যে শব্দ প্রায় একই: “প্রতিটি”, “কোনো একজন”, “এলাকা”, “রাইডার”। কিন্তু অর্থ একেবারে আলাদা। প্রথম বাক্য সত্য হতে মিরপুরে রাজু আর উত্তরায় শিলা গেলেই চলে। দ্বিতীয়টি সত্য হতে একজন মানুষকেই সব এলাকা সামলাতে হবে। সেই রাইডার অসুস্থ হলে পুরো শহরের ডেলিভারি বন্ধ, তাই দ্বিতীয় বাক্যটি ব্যবসার জন্য একটি ঝুঁকির কথাও বলে।

পর্ব ০৪-এ (Predicate logic আর quantifier) আপনি একটি চলকের predicate আর দুটি quantifier দেখেছেন: ∀ (“প্রতিটির জন্য”) আর ∃ (“অন্তত একটির জন্য”)। এই পর্বে দুই বা তার বেশি চলক আসবে, আর একটি quantifier আরেকটির ভেতরে বসবে। একে বলে nested quantifier. ধরুন:

• X = বাজারঘরের এলাকার সেট, Y = রাইডারের সেট;
• S(x, y) = “রাইডার y এলাকা x-এ ডেলিভারি দেন”।

তাহলে প্রথম ম্যানেজারের কথা ∀x∃y S(x, y), আর দ্বিতীয়জনের কথা ∃y∀x S(x, y). দুটিতে একই তিনটি জিনিস আছে, শুধু quantifier-এর ক্রম উল্টো। এই পর্বের পুরো গল্প এই এক ছোট পরিবর্তনকে ঘিরে।

এই “খেলা” শুধু উপমা নয়। যুক্তিবিদ্যায় এটিকে game semantics বলা হয়, আর পরে দেখবেন জটিলতা তত্ত্বেও (complexity theory) এই খেলার ধারণা সরাসরি কাজে লাগে। এখন একটি কথা মনে রাখুন: ∃ যত ডানে থাকে, তার witness তত বেশি তথ্য দেখে বাছা যায়, তাই বাক্যটি তত সহজে সত্য হয়।

২ · দুই চলকের বাক্যগুলো আর তাদের সম্পর্ক

প্রথমে একটি ছোট টেবিলে দুটি বাক্যের মান হাতে বের করি। বাজারঘরের চারটি এলাকা আর চারজন রাইডার; ✓ মানে S(x, y) সত্য, · মানে মিথ্যা। Domain সসীম হলে ∀ আসলে একটি বড় ∧ (এবং), আর ∃ একটি বড় ∨ (অথবা)। তাই ∀x∃y S(x, y) মানে “প্রতিটি সারিতে অন্তত একটি ✓”, আর ∃y∀x S(x, y) মানে “অন্তত একটি কলাম পুরোটা ✓”।

দুই চলক আর দুই quantifier মিলিয়ে বাক্য হয় আটটি (চলকের দুটি ক্রম × প্রতিটি জায়গায় ∀ বা ∃)। কিন্তু এর মধ্যে কয়েকটি জোড়া সমতুল্য, তাই আলাদা বাক্য থাকে ছয়টি। নিচের উপপাদ্য বলে কোনটি কোনটিকে নিশ্চিত করে।

(ক) আর (খ) সহজ: ∀∀ মানে “সব জোড়ায় সত্য”, জোড়াগুলো কোন ক্রমে দেখছেন তাতে কিছু যায় আসে না; ∃∃ মানে “অন্তত একটি জোড়ায় সত্য”, সেটিও ক্রমের ওপর নির্ভর করে না। আসল কথা (গ) আর (ঘ)।

(গ)-এর প্রমাণ। এখানে পর্ব ০৬-এর (অনুমানের নিয়ম) চারটি নিয়ম আগে থেকেই সাধারণ ভাষায় ব্যবহার করছি; সেখানে এদের আনুষ্ঠানিক নাম দেখবেন।

1. ধরি ∃y∀x P(x, y) সত্য। (অনুমান)
2. তাহলে Y-তে একটি নির্দিষ্ট উপাদান b আছে, যার জন্য ∀x P(x, b) সত্য। (∃-এর সংজ্ঞা; b-কে একটি নাম দিলাম)
3. X থেকে ইচ্ছামতো একটি উপাদান c নিন। ধাপ ২ থেকে P(c, b) সত্য। (∀-এর সংজ্ঞা: সব x-এ সত্য, তাই c-তেও)
4. অতএব y = b নিলে P(c, y) সত্য হয়, অর্থাৎ ∃y P(c, y) সত্য। (b হলো witness)
5. c-কে কোনো বিশেষ শর্ত ছাড়া ইচ্ছামতো নেওয়া হয়েছিল, তাই প্রতিটি x-এর জন্য ∃y P(x, y) সত্য, অর্থাৎ ∀x∃y P(x, y). ∎

(ঘ)-এর প্রমাণ (একটি counterexample). Domain X = Y = ℤ (সব পূর্ণসংখ্যা), P(x, y): x + y = 0. ∀x∃y সত্য: যেকোনো x-এর জন্য y = −x নিলে চলে। কিন্তু ∃y∀x মিথ্যা: যেকোনো b নিন, তাহলে x = 1 − b-তে x + b = 1 ≠ 0, অর্থাৎ কোনো একটি b সব x-এর জন্য কাজ করে না। একটি উদাহরণে implication ভাঙল, তাই সেটি সাধারণভাবে সত্য নয়। ∎

ছয়টি আলাদা বাক্যের পুরো সম্পর্ক নিচের চিত্রে। তীর মানে “ওপরেরটি সত্য হলে নিচেরটিও অবশ্যই সত্য”। কোনো তীর উল্টো দিকে খাটে না, আর বাঁ আর ডানের শিকলের মধ্যে কোনো সরাসরি তীর নেই।

চিত্রটি বিশ্বাস না করে যাচাই করুন। ৩টি x আর ৩টি y থাকলে P-এর মোট সম্ভাব্য রূপ (relation) 2⁹ = 512টি, কারণ নয়টি ঘরের প্রতিটি ✓ বা · হতে পারে। নিচের brute force ব্লক সবগুলো তৈরি করে, ছয়টি বাক্যের মান হিসাব করে, আর প্রতিটি জোড়া (A, B)-র জন্য গোনে কতগুলো relation-এ A সত্য কিন্তু B মিথ্যা। শূন্য মানে সেই ৫১২টির কোনোটিতেই A → B ভাঙেনি। (এই কোর্সের Python ব্লকগুলো আপনার ব্রাউজারেই চলে; প্রথমবার চালাতে Python লোড হতে কয়েক সেকেন্ড লাগে।)

from itertools import product

n = 3
R = range(n)
stmts = {   # ছয়টি আলাদা বাক্য; P[x][y] = 1 মানে P(x, y) সত্য
    "∀x∀y": lambda P: all(P[x][y] for x in R for y in R),
    "∃x∀y": lambda P: any(all(P[x][y] for y in R) for x in R),
    "∃y∀x": lambda P: any(all(P[x][y] for x in R) for y in R),
    "∀x∃y": lambda P: all(any(P[x][y] for y in R) for x in R),
    "∀y∃x": lambda P: all(any(P[x][y] for x in R) for y in R),
    "∃x∃y": lambda P: any(P[x][y] for x in R for y in R),
}
rels = [[bits[i * n:(i + 1) * n] for i in R]
        for bits in product((0, 1), repeat=n * n)]
print("3×3 relation মোট:", len(rels))
truth = {s: [f(P) for P in rels] for s, f in stmts.items()}
for s in stmts:
    print(f"{s} সত্য {sum(truth[s]):3d}টিতে")
print("সূত্র: ∀x∃y =", (2**n - 1)**n, " ∃y∀x =", 2**(n * n) - (2**n - 1)**n)

names = list(stmts)
print("\nসারি A, কলাম B: A সত্য কিন্তু B মিথ্যা — এমন relation কয়টি")
print("      " + " ".join(f"{b:>5}" for b in names))
for a in names:
    row = [sum(ta and not tb for ta, tb in zip(truth[a], truth[b]))
           for b in names]
    print(f"{a}  " + " ".join(f"{c:5d}" for c in row))

3×3 relation মোট: 512
∀x∀y সত্য   1টিতে
∃x∀y সত্য 169টিতে
∃y∀x সত্য 169টিতে
∀x∃y সত্য 343টিতে
∀y∃x সত্য 343টিতে
∃x∃y সত্য 511টিতে
সূত্র: ∀x∃y = 343  ∃y∀x = 169

সারি A, কলাম B: A সত্য কিন্তু B মিথ্যা — এমন relation কয়টি
       ∀x∀y  ∃x∀y  ∃y∀x  ∀x∃y  ∀y∃x  ∃x∃y
∀x∀y      0     0     0     0     0     0
∃x∀y    168     0    78    42     0     0
∃y∀x    168    78     0     0    42     0
∀x∃y    342   216   174     0    78     0
∀y∃x    342   174   216    78     0     0
∃x∃y    510   342   342   168   168     0

৩ · অনুবাদ — বাংলা বাক্য থেকে nested quantifier, আর ফিরতি পথে

বাস্তবের নিয়ম, যেমন বাজারঘরের ডেলিভারি নীতি, সাধারণত লম্বা বাংলা বাক্যে লেখা থাকে। সেটিকে সূত্রে আনতে পারলে তিনটি লাভ: অস্পষ্টতা ধরা পড়ে, negation বের করা যায়, আর কোডে বা database-এ যাচাই করা যায়। কাজটি করার একটি নির্ভরযোগ্য কৌশল আছে: বাইরে থেকে ভেতরে, এক একটি quantifier করে।

গণিতের কয়েকটি পরিচিত বাক্যে একই কৌশল খাটান। প্রতিটির ক্ষেত্রে domain বদলালে কী হয়, সেটিও খেয়াল করুন:

ফিরতি পথটিও অনুশীলন করুন: সূত্র পড়ে স্বাভাবিক বাংলায় বলা। ∀x∀y ((x > 0 ∧ y > 0) → xy > 0)-কে “x-এর জন্য, y-এর জন্য …” না বলে বলুন “দুটি ধনাত্মক সংখ্যার গুণফল ধনাত্মক”। আক্ষরিক অনুবাদ প্রথম ধাপ; স্বাভাবিক বাক্যে আনা দ্বিতীয় ধাপ, আর সেটিই প্রমাণ করে আপনি অর্থ বুঝেছেন। চলকের নামও খেয়াল করুন: ∀x∃y P(x, y)-তে x আর y দুটিই bound variable, তাই এদের নাম বদলে ∀a∃b P(a, b) লিখলে অর্থ একই থাকে। কিন্তু ∃y P(x, y)-তে x একটি free variable, তাই x-এর মান না জানা পর্যন্ত বাক্যটি সত্য বা মিথ্যা কোনোটিই নয়।

৪ · Nested quantifier-এর negation

পর্ব ০৪-এ quantifier-এর De Morgan নিয়ম দেখেছেন: ¬∀x Q(x) ≡ ∃x ¬Q(x) আর ¬∃x Q(x) ≡ ∀x ¬Q(x). Nested বাক্যে এই নিয়মটিই বারবার লাগাতে হয়, প্রতিবার একটি quantifier পেরিয়ে।

প্রমাণ (প্রথম সমতুল্যতা)।

1. Q(x) দিয়ে ∃y P(x, y) বোঝাই। তাহলে ¬∀x∃y P(x, y) হলো ¬∀x Q(x). (শুধু নাম দেওয়া)
2. ¬∀x Q(x) ≡ ∃x ¬Q(x). (quantifier-এর De Morgan, পর্ব ০৪)
3. প্রতিটি x-এর জন্য ¬Q(x) = ¬∃y P(x, y) ≡ ∀y ¬P(x, y). (আবার De Morgan, এবার y-এর ওপর)
4. দুটি সমতুল্য সূত্র প্রতিটি x-এ একই মান দেয়, তাই ∃x-এর ভেতরে একটির জায়গায় আরেকটি বসানো যায়: ∃x ¬Q(x) ≡ ∃x∀y ¬P(x, y). ∎

দ্বিতীয়টির প্রমাণ একইভাবে, শুধু ∃ আর ∀ উল্টো। আর সাধারণ ক্ষেত্রে quantifier-এর সংখ্যা ধরে induction করা যায় (পর্ব ১০-এ induction শিখবেন)।

প্রথম স্টেপারের টেবিলে মিলিয়ে দেখুন। ∃y∀x S(x, y) মিথ্যা ছিল, তাই তার negation ∀y∃x ¬S(x, y) সত্য, আর সেটির witness ছিল function g: প্রতিটি রাইডারের একটি বাদ পড়া এলাকা। উপপাদ্য শুধু চিহ্নের খেলা নয়; negation-এর প্রতিটি quantifier বলে দেয় প্রমাণে কী হাজির করতে হবে।

বাজারঘরের অনুবাদ করা নিয়মটির negation:

¬∀d (J(d) → ∃w (G(w, d) ∧ ∀t (T(t, d) → R(w, t))))
≡ ∃d (J(d) ∧ ∀w (G(w, d) → ∃t (T(t, d) ∧ ¬R(w, t))))

বাংলায়: “এমন একটি জেলা আছে, যার প্রতিটি গুদামের জন্য সেই জেলার অন্তত একটি থানা আছে যেখানে ওই গুদাম পৌঁছায় না।” খেয়াল করুন, restricted quantifier-এর রূপও বদলায়: ∀d (J(d) → …)-এর negation ∃d (J(d) ∧ ¬…), কারণ ¬(p → q) ≡ p ∧ ¬q; আর ∃w (G ∧ …)-এর negation ∀w (G → ¬…)। নিয়ম দাঁড়ায়: ∀-এর সঙ্গী →, ∃-এর সঙ্গী ∧; negation-এ quantifier উল্টালে সঙ্গীও বদলায়। নিয়ম ভঙ্গের একটি প্রমাণ দিতে তাই দরকার একটি জেলা আর একটি function: প্রতিটি গুদামকে একটি না-পৌঁছানো থানা।

এবার সবচেয়ে বিখ্যাত nested বাক্যটি, যা বহু শিক্ষার্থীকে প্রথমবার হোঁচট খাওয়ায়। নিচের stepper-টি একটু উন্নত স্তরের; Calculus-এর limit না দেখে থাকলে শুধু quantifier-এর নড়াচড়া খেয়াল করুন, বাকিটা পরের অংশে ব্যাখ্যা আছে।

৫ · গণিতে quantifier — witness function, limit আর continuity

∀x∃y P(x, y) সত্য হলে প্রতিটি x-এর জন্য অন্তত একটি কাজের y আছে। প্রতিটি x-এর জন্য এমন একটি y বেছে রাখলে একটি function পাই: f(x) = বাছাই করা y. তখন ∀x P(x, f(x)) সত্য। এই function-কে বলে witness function, যুক্তিবিদ্যায় Skolem function (নরওয়েজীয় গণিতবিদ Thoralf Skolem-এর নামে, যিনি ১৯২০-এর দশকে এটি ব্যবহার করেন)। এটিই nested quantifier-এর সবচেয়ে কাজের দৃষ্টিভঙ্গি:

অর্থাৎ ∃y∀x মানে witness function-টি ধ্রুবক হতে পারে। এই দৃষ্টিতে উপপাদ্য ৫.১-এর (গ) প্রায় স্পষ্ট: ধ্রুবক function-ও তো একটি function. সসীম domain-এ “প্রতিটি x-এর জন্য একটি বাছাই” সোজা কাজ; অসীম domain-এ সাধারণভাবে এমন বাছাইয়ের অস্তিত্বের জন্য গণিতের একটি স্বতঃসিদ্ধ, axiom of choice, ব্যবহার করা হয়। আমাদের উদাহরণগুলোতে বাছাইয়ের নিয়ম স্পষ্ট লেখা যায়, তাই সে প্রশ্ন ওঠে না।

নিচের ব্লক প্রথম stepper-এর টেবিল থেকে f আর g দুটি function বানায়, তারপর একটি সংখ্যার উদাহরণ দেখায়: ∀n∃p (p > n ∧ p মৌলিক)। এটি Euclid-এর সেই প্রাচীন উপপাদ্য, “মৌলিক সংখ্যা অসীম”, quantifier-এর ভাষায়; এর প্রমাণ পর্ব ২০-এ (বিভাজ্যতা আর মৌলিক সংখ্যা) আসবে। এখানে witness function হলো “n-এর পরের মৌলিক সংখ্যা”।

areas = ["মিরপুর", "উত্তরা", "ধানমন্ডি", "মতিঝিল"]
riders = ["রাজু", "শিলা", "তানভীর", "মিতু"]
P = [[1, 0, 1, 0],      # P[x][y] = 1: রাইডার y এলাকা x-এ যান
     [0, 1, 0, 0],
     [0, 0, 1, 1],
     [1, 0, 0, 1]]

# ∀x∃y P(x, y)-এর witness function: প্রতিটি x-এর জন্য প্রথম যে y কাজ করে
f = {}
for i, x in enumerate(areas):
    ys = [riders[j] for j in range(4) if P[i][j]]
    f[x] = ys[0] if ys else None
print("f =", f)
print("∀x∃y সত্য?", all(v is not None for v in f.values()))

# ∃y∀x মিথ্যা, অর্থাৎ ∀y∃x ¬P: প্রতিটি রাইডারের একটি 'বাদ পড়া' এলাকা g(y)
g = {riders[j]: next(areas[i] for i in range(4) if not P[i][j])
     for j in range(4)}
print("g =", g)

# সংখ্যার উদাহরণ: ∀n∃p (p > n এবং p মৌলিক); witness = পরের মৌলিক সংখ্যা
def is_prime(m):
    return m > 1 and all(m % d for d in range(2, int(m ** 0.5) + 1))

def next_prime(n):
    p = n + 1
    while not is_prime(p):
        p += 1
    return p

print([(n, next_prime(n)) for n in (1, 10, 24, 89, 113, 1000)])
# ∃p∀n (p > n)-এর জন্য যেকোনো p-এর বিপক্ষে n = p-ই counterexample
print([(p, p > p) for p in (2, 97, 7919)])

f = {'মিরপুর': 'রাজু', 'উত্তরা': 'শিলা', 'ধানমন্ডি': 'তানভীর', 'মতিঝিল': 'রাজু'}
∀x∃y সত্য? True
g = {'রাজু': 'উত্তরা', 'শিলা': 'মিরপুর', 'তানভীর': 'উত্তরা', 'মিতু': 'মিরপুর'}
[(1, 2), (10, 11), (24, 29), (89, 97), (113, 127), (1000, 1009)]
[(2, False), (97, False), (7919, False)]

Limit আর continuity: quantifier-এর ক্রমের সবচেয়ে বিখ্যাত উদাহরণ (উন্নত)

এই অংশটি Calculus বা real analysis-এর বিষয়; এখানে শুধু quantifier-এর গঠনটুকু দেখছি, পুরো তত্ত্ব নয়। বাস্তব ফাংশন f-এর ক্ষেত্রে “x যখন a-এর দিকে যায়, f(x)-এর limit L” কথাটির নিখুঁত সংজ্ঞা:

∀ε > 0 ∃δ > 0 ∀x (0 < |x − a| < δ → |f(x) − L| < ε)

এখানে ε (এপসাইলন) হলো “L থেকে কতটা দূরে থাকা চলবে”, আর δ (ডেল্টা) হলো “a-এর কতটা কাছে আসতে হবে”; |x − a| মানে x আর a-এর দূরত্ব। খেলার ভাষায়: প্রতিপক্ষ একটি সহনশীলতা ε দেন, আপনি সেটি দেখে δ বাছেন, তারপর প্রতিপক্ষ δ-এর ভেতরের যেকোনো x বাছেন। f(x) ε-এর ভেতরে থাকলে আপনি জেতেন। δ বাছার সময় আপনি ε জানেন, কিন্তু x জানেন না।

a বিন্দুতে continuity হলো একই গঠন, L-এর জায়গায় f(a). এখন f পুরো ℝ-এ continuous মানে প্রতিটি a-তে continuous: ∀a ∀ε ∃δ ∀x. এখানে δ নির্ভর করতে পারে ε আর a দুটোর ওপরই। কিন্তু যদি দাবি করি একটিই δ সব a-তে খাটে, তাহলে ∃δ-কে ∀a-র বাঁয়ে সরাতে হয়: ∀ε ∃δ ∀a ∀x. এটির নাম uniform continuity. দুটি সংজ্ঞায় শব্দ এক, শুধু ∃δ আর ∀a-র ক্রম আলাদা, আর উপপাদ্য ৫.১-এর (গ) অনুযায়ী uniform continuity থেকে সাধারণ continuity আসে, কিন্তু উল্টোটা নয়।

উদাহরণ: f(x) = x², a = 3-এ continuous. ε > 0 দেওয়া আছে। δ = min(1, ε/7) নিন। তাহলে |x − 3| < δ হলে:

1. |x − 3| < 1, তাই 2 < x < 4, আর 5 < x + 3 < 7, অর্থাৎ |x + 3| < 7. (δ ≤ 1)
2. |x² − 9| = |x − 3| · |x + 3|। (বীজগণিত: x² − 9 = (x − 3)(x + 3))
3. |x − 3| · |x + 3| < δ · 7 ≤ (ε/7) · 7 = ε। (ধাপ ১ আর δ ≤ ε/7) ∎

এখানে δ = min(1, ε/7) হলো ∀ε∃δ-এর witness function: ε থেকে δ বানানোর নিয়ম। কিন্তু ৭ সংখ্যাটি এসেছে a = 3 থেকে (|x + 3| < 7). a বড় হলে δ-কে আরও ছোট হতে হয়।

উদাহরণ: x² ℝ-এ uniformly continuous নয়। Uniform continuity-র negation (উপপাদ্য ৫.২ খাটিয়ে): ∃ε > 0 ∀δ > 0 ∃x∃y (|x − y| < δ ∧ |x² − y²| ≥ ε)। ε = 1 নিন। যেকোনো δ > 0-এর জন্য x = 1/δ আর y = x + δ/2 নিন। তাহলে |x − y| = δ/2 < δ, আর y² − x² = (y − x)(y + x) = (δ/2)(2/δ + δ/2) = 1 + δ²/4 ≥ 1. ∎ নিচের ব্লক দুটি দাবিই সঠিক ভগ্নাংশে (Fraction, কোনো rounding ছাড়া) যাচাই করে।

from fractions import Fraction as F

def f(x):
    return x * x

a, L = F(3), F(9)

def delta(eps):                 # প্রমাণ থেকে পাওয়া witness: δ = min(1, ε/7)
    return min(F(1), eps / 7)

print("x = 3-এ continuity: প্রতিটি ε-এর জন্য δ(ε)")
for eps in (F(1), F(1, 10), F(1, 1000)):
    d = delta(eps)
    xs = [a + d * k / 1000 for k in range(-999, 1000) if k != 0]
    worst = max(abs(f(x) - L) for x in xs)
    print(f"  ε={str(eps):6} δ={str(d):6} সবচেয়ে বড় |x²-9| = "
          f"{float(worst):.6f}  < ε? {worst < eps}")

print("ε = 1 ধরে uniform continuity যাচাই: কোনো একটি δ কি সব x-এ চলে?")
for d in (F(1, 2), F(1, 10), F(1, 100)):
    x = 1 / d                   # δ যত ছোট, x তত দূরে নিতে হয়
    y = x + d / 2               # |y - x| = δ/2 < δ
    print(f"  δ={str(d):5} x={str(x):4} |y-x|={str(y - x):6} "
          f"|y²-x²| = {y * y - x * x} ≥ 1? {y * y - x * x >= 1}")

x = 3-এ continuity: প্রতিটি ε-এর জন্য δ(ε)
  ε=1      δ=1/7    সবচেয়ে বড় |x²-9| = 0.876653  < ε? True
  ε=1/10   δ=1/70   সবচেয়ে বড় |x²-9| = 0.085832  < ε? True
  ε=1/1000 δ=1/7000 সবচেয়ে বড় |x²-9| = 0.000856  < ε? True
ε = 1 ধরে uniform continuity যাচাই: কোনো একটি δ কি সব x-এ চলে?
  δ=1/2   x=2    |y-x|=1/4    |y²-x²| = 17/16 ≥ 1? True
  δ=1/10  x=10   |y-x|=1/20   |y²-x²| = 401/400 ≥ 1? True
  δ=1/100 x=100  |y-x|=1/200  |y²-x²| = 40001/40000 ≥ 1? True

৬ · Programming-এ quantifier — nested loop, all/any আর SQL

সসীম domain-এ quantifier আসলে loop. ∀x Q(x) মানে সব x একে একে দেখা, আর একটিতেও Q মিথ্যা হলে সেখানেই থেমে False ফেরত দেওয়া; ∃x Q(x) মানে একটিতে Q সত্য হলেই থেমে True ফেরত দেওয়া। তাই ∀x∃y P(x, y) হয় দুই স্তরের loop: বাইরে x, ভেতরে y. Quantifier-এর ক্রম আর loop-এর ক্রম এক। নিচের trace-এ একটি ৩×৩ relation-এ ∀x∃y যাচাই হচ্ছে, যার শেষ সারিতে কোনো ✓ নেই।

1def forall_exists(P):2    for x in range(3):      # ∀x3        found = False4        for y in range(3):  # ∃y5            if P[x][y]:6                found = True7                break8        if not found:9            return False10    return True

Python-এ একই কাজ এক লাইনে: all(any(P[x][y] for y in Y) for x in X). all() হলো ∀, any() হলো ∃, আর লেখার ক্রমই quantifier-এর ক্রম। দুটিই short-circuit করে: all() প্রথম False পেলে থামে, any() প্রথম True পেলে, ঠিক উপরের break আর return-এর মতো। (loop আর comprehension-এর Python দিক Python প্রোগ্রামিং কোর্সের পর্ব ১২ আর পর্ব ১৮-এ আছে।) ∃y∀x লিখতে হলে loop-এর ক্রম বদলাতে হয়: any(all(P[x][y] for x in X) for y in Y). দুই ক্ষেত্রেই সবচেয়ে খারাপ অবস্থায় |X| · |Y|টি ঘর দেখতে হয়; প্রতিটি অতিরিক্ত quantifier আরেকটি গুণক যোগ করে, তাই তিন স্তরের quantifier-এ n চলকের domain-এ n³ পর্যন্ত কাজ।

বাস্তবের ডেটায় দুটি বাক্য কত ঘন ঘন সত্য হয়? ধরুন প্রতিটি (এলাকা, রাইডার) জোড়ায় ডেলিভারি ব্যবস্থা থাকার সম্ভাবনা p = 0.6, স্বাধীনভাবে। একটি সারিতে কোনো ✓ না থাকার সম্ভাবনা (1 − p)ⁿ, তাই ∀x∃y-এর সম্ভাবনা (1 − (1 − p)ⁿ)ⁿ. একটি কলাম পুরো ✓ হওয়ার সম্ভাবনা pⁿ, তাই ∃y∀x-এর সম্ভাবনা 1 − (1 − pⁿ)ⁿ. নিচের ব্লক seed-সহ এলোমেলো relation বানিয়ে সূত্রের সঙ্গে মেলায়।

import random

random.seed(2026)
p = 0.6            # প্রতিটি (এলাকা, রাইডার) জোড়ায় P সত্য হওয়ার সম্ভাবনা
trials = 3000

def one(n):
    P = [[random.random() < p for _ in range(n)] for _ in range(n)]
    ae = all(any(row) for row in P)                       # ∀x∃y
    ea = any(all(P[x][y] for x in range(n)) for y in range(n))  # ∃y∀x
    return ae, ea

print(" n  ∀x∃y(sim) সূত্র    ∃y∀x(sim) সূত্র   ∃y∀x সত্য কিন্তু ∀x∃y মিথ্যা")
for n in (2, 4, 6, 8, 12):
    ae = ea = bad = 0
    for _ in range(trials):
        a, e = one(n)
        ae += a; ea += e; bad += e and not a
    f_ae = (1 - (1 - p) ** n) ** n
    f_ea = 1 - (1 - p ** n) ** n
    print(f"{n:2d}   {ae / trials:.3f}   {f_ae:.3f}    "
          f"{ea / trials:.3f}   {f_ea:.3f}    {bad}")

 n  ∀x∃y(sim) সূত্র    ∃y∀x(sim) সূত্র   ∃y∀x সত্য কিন্তু ∀x∃y মিথ্যা
 2   0.715   0.706    0.604   0.590    0
 4   0.898   0.901    0.427   0.426    0
 6   0.976   0.976    0.263   0.249    0
 8   0.991   0.995    0.121   0.127    0
12   0.999   1.000    0.024   0.026    0

SQL-এ “সবার জন্য”: দুটি NOT EXISTS

SQL-এ EXISTS আছে (এটি ∃), কিন্তু FOR ALL বলে কোনো শব্দ নেই। তাই ∀ লিখতে উপপাদ্য ৫.২-এর কৌশল লাগে: ∀x Q(x) ≡ ¬∃x ¬Q(x). “যে রাইডার সব এলাকায় যান” মানে ∃y∀x S(x, y)-এর witness খোঁজা, অর্থাৎ এমন y যার জন্য ¬∃x ¬S(x, y): “এমন কোনো এলাকা নেই যেখানে তিনি যান না।” এই ধরনের প্রশ্নকে database-এর ভাষায় relational division বলে (DBMS ও SQL কোর্সের পর্ব ৩৩), আর EXISTS-এর বিস্তারিত সেই কোর্সের পর্ব ২১-এ।

-- ∀x∃y: কোনো এলাকা কি রাইডারহীন? (ফাঁকা ফল = প্রতিটি এলাকায় কেউ যান)
SELECT a.name FROM area a
WHERE NOT EXISTS (SELECT 1 FROM serves s WHERE s.area = a.name);

-- ∃y∀x: কোন রাইডারের জন্য "যেখানে তিনি যান না এমন এলাকা" নেই?
SELECT r.name FROM rider r
WHERE NOT EXISTS (
  SELECT 1 FROM area a
  WHERE NOT EXISTS (
    SELECT 1 FROM serves s
    WHERE s.rider = r.name AND s.area = a.name));

সত্যিকারের run: Python 3.14.4-এর ভেতরের SQLite 3.50.4-এ, প্রথম stepper-এর টেবিলটিই serves টেবিলে বসিয়ে (প্রশ্ন দুটিকে Q1, Q2 নামে), পরে মিতুর জন্য মিরপুর আর উত্তরা যোগ করে:

$ python sql_demo.py
sqlite 3.50.4
Q1 rows: []
Q2 rows: []
after adding Mitu->Mirpur, Mitu->Uttara
Q2 rows: [('Mitu',)]

Q1 ফাঁকা, অর্থাৎ রাইডারহীন কোনো এলাকা নেই: ∀x∃y সত্য। Q2-ও ফাঁকা: ∃y∀x মিথ্যা, stepper-এর সঙ্গে মিলে গেল। মিতুর দুটি নতুন এলাকা যোগ করার পর মিতুর কলাম পুরো ✓ হলো, আর Q2 তাঁকেই witness হিসেবে ফেরত দিল। দুই স্তরের NOT EXISTS পড়ার সহজ উপায়: “এমন কোনো এলাকা নেই, যেখানে এমন কোনো ডেলিভারি নেই” = ¬∃x ¬∃ = ∀x∃।

৭ · সাধারণ ভুল, গভীরতর দিক আর পরীক্ষার প্রস্তুতি

Nested quantifier-এ ভুলগুলো বারবার একই ছাঁচে আসে। নিচের তালিকাটি নিজের লেখা মেলানোর জন্য রেখে দিন।

আরেকটি সূক্ষ্ম ভুল খালি domain নিয়ে। পর্ব ০৪-এ দেখেছেন, খালি domain-এ ∀x Q(x) আপনাআপনি সত্য (vacuous truth) আর ∃x Q(x) মিথ্যা। তাই ছবি ৫.১-এর ∀x∀y → ∃x∀y তীরটি খালি X-এ ভাঙে: ∀x∀y সত্য, কিন্তু ∃x∀y মিথ্যা। কোডেও একই ঘটনা: খালি list-এ all([]) হলো True আর any([]) হলো False. বাজারঘরে নতুন খোলা একটি শহরে এখনো কোনো এলাকা না থাকলে “প্রতিটি এলাকায় রাইডার আছে” পরীক্ষা পাস করবে; আপনার রিপোর্ট যেন সেটিকে “সব ঠিক আছে” না বলে।

৮ · AI-এর যুগে nested quantifier — AI-কে কীভাবে যাচাই করবেন

AI সহকারীকে “এই বাক্যটি predicate logic-এ লিখে দাও” বা “এর negation কী” জিজ্ঞেস করলে সাধারণত দ্রুত, আত্মবিশ্বাসী আর পরিপাটি উত্তর আসে। কিন্তু nested quantifier ঠিক সেই জায়গা, যেখানে একটি চিহ্ন এদিক-ওদিক হলে পুরো অর্থ বদলে যায়, অথচ লেখা দেখতে প্রায় একই থাকে। সাধারণত যে ধরনের ভুল দেখা যায়, সেগুলোও বলা হয় একই আত্মবিশ্বাস নিয়ে:

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

• সূত্রটি আবার স্বাভাবিক বাংলায় পড়েছি, আর সেটি মূল বাক্যের অর্থই দেয়
• প্রতিটি ∃ কোন কোন চলকের ওপর নির্ভর করতে পারে (তার বাঁয়ের ∀-গুলো), তা চিহ্নিত করেছি
• ছোট domain-এ brute force চালিয়ে দাবিটি যাচাই করেছি, আর negation-এর মান প্রতিবার উল্টো এসেছে
• প্রমাণের প্রতিটি ধাপের কারণ দেখেছি; বৃত্তাকার যুক্তি, উল্টো দিকের প্রমাণ বা বাদ পড়া শর্ত খুঁজেছি
• ব্যবহৃত প্রতিটি উপপাদ্যের শর্ত জেনেছি, আর রেফারেন্স থাকলে নিজে খুঁজে মিলিয়েছি
• সন্দেহ থাকলে একটি বিশ্বস্ত পাঠ্যবইয়ের সংজ্ঞার সঙ্গে মিলিয়েছি