First-order logic — বস্তু, সম্পর্ক আর quantifier

আগের পর্বে (পর্ব ৪৫) দেখেছেন, propositional logic-এ প্রতিটি পূর্ণ বাক্য একটি প্রতীক (P, Q), সেগুলো ¬ (না), ∧ (এবং), ∨ (অথবা), → (যদি…তবে) আর ↔ (যদি এবং কেবল যদি) দিয়ে জোড়া হয়, truth table দিয়ে অর্থ যাচাই হয়, আর entailment প্রমাণ করা যায় CNF ও resolution দিয়ে। এই পর্বে সেই ভিত্তির ওপর একটি বড় ধাপ: বাক্যের ভেতরে ঢুকে কার সম্পর্কে, কী সম্পর্ক, তা লেখা। পুরো পর্বের উদাহরণ বাজারঘর (এই কোর্সের কাল্পনিক অনলাইন দোকান); গ্রাহক, পণ্য, দাম আর অর্ডার সব বানানো।

১ · Propositional logic কেন যথেষ্ট নয়

বাজারঘরে চারজন গ্রাহক (রহিম, করিম, মিতু, সুমি) আর পাঁচটি পণ্য (মিনিকেট চাল, চিনিগুঁড়া চাল, মসুর ডাল, সয়াবিন তেল, একটি সাবান)। “কে কী অর্ডার করেছেন” propositional logic-এ লিখতে হলে প্রতিটি জোড়ার জন্য একটি আলাদা প্রতীক লাগে: O_Rahim_Miniket, O_Rahim_Chinigura, … মোট ৪ × ৫ = ২০টি। এখন দোকানের ম্যানেজার একটি নিয়ম যাচাই করতে চান: “যে গ্রাহক চাল অর্ডার করেছেন, তিনি ডালও অর্ডার করেছেন।” Propositional logic-এ এটি একটি বাক্যে লেখা যায় না; প্রত্যেক গ্রাহকের জন্য আলাদা:

(O_Rahim_Miniket ∨ O_Rahim_Chinigura) → O_Rahim_Mosur
(O_Karim_Miniket ∨ O_Karim_Chinigura) → O_Karim_Mosur
(O_Mitu_Miniket  ∨ O_Mitu_Chinigura)  → O_Mitu_Mosur
(O_Sumi_Miniket  ∨ O_Sumi_Chinigura)  → O_Sumi_Mosur

সমস্যা তিনটি। এক, আকার: ১,০০০ গ্রাহক আর ৫,০০০ পণ্য হলে শুধু অর্ডারের প্রতীকই ৫০ লাখ, আর নিয়মটি ১,০০০ বার লিখতে হয়। দুই, নতুন গ্রাহক এলে নতুন প্রতীক আর নতুন বাক্য, আর পুরোনো নিয়ম নিজে থেকে তাঁর ওপর খাটে না। তিন, প্রতীকের নামের ভেতরের “Rahim” বা “Miniket” logic-এর চোখে অর্থহীন অক্ষর; O_Rahim_Miniket আর O_Rahim_Mosur যে একই মানুষের কথা বলছে, তা logic জানে না। নতুন চালের ব্র্যান্ড এলে “চাল” শব্দটিও প্রতিটি বাক্যে হাতে যোগ করতে হয়।

FOL-এ সেই নিয়মটি একটিমাত্র বাক্য, যা যেকোনো সংখ্যক গ্রাহক আর পণ্যের জন্য খাটে:

∀x ( Customer(x) ∧ ∃y (Rice(y) ∧ Ordered(x, y)) → ∃z (Lentil(z) ∧ Ordered(x, z)) )

পড়ুন এভাবে: “প্রত্যেক বস্তু x-এর জন্য: x যদি গ্রাহক হন আর এমন কোনো y থাকে যা চাল এবং x তা অর্ডার করেছেন, তবে এমন কোনো z আছে যা ডাল এবং x তা অর্ডার করেছেন।” এখানের প্রতিটি চিহ্ন এই পর্বে ধাপে ধাপে আসবে। অংশ ৫-এ এই অনুবাদটিই একটি stepper-এ টুকরো টুকরো করে বানানো হবে, আর দেখা যাবে বাজারঘরের জগতে বাক্যটি মিথ্যা: সুমি চাল নিয়েছেন, ডাল নেননি।

২ · FOL-এর জগৎ — বস্তু, সম্পর্ক আর function

প্রতিটি logic জগৎ সম্পর্কে একটি অনুমান করে নেয়: জগতে কী কী আছে। একে বলে ontological commitment. Russell ও Norvig-এর বই “Artificial Intelligence: A Modern Approach” এই তুলনাটি একটি সারণিতে দেখায়; নিচের সারণি তার সরল রূপ।

FOL-এর শব্দভান্ডারে তিন ধরনের প্রতীক, আর প্রতিটির একটি নির্দিষ্ট কাজ:

এগুলো দিয়ে বানানো হয় বড় অংশ। একটি term মানে যেকোনো বস্তুর নাম: একটি constant (Rahim), একটি variable (x), অথবা function-এর ভেতরে term (rider(Rahim), price(rider(x))-এর মতো গভীরেও)। একটি atomic sentence মানে term-এর ওপর একটি predicate: Ordered(Rahim, Miniket), অথবা দুটি term-এর সমতা: rider(Rahim) = Jamal. Atomic sentence-কে পর্ব ৪৫-এর মতোই logical connective (¬ ∧ ∨ → ↔) দিয়ে জোড়া যায়, আর তার ওপর বসে quantifier (অংশ ৩)।

বাজারঘরের ছোট জগৎ

পুরো পর্ব জুড়ে এই জগৎটি ব্যবহার হবে। এতে ৯টি বস্তু: ৪ জন গ্রাহক আর ৫টি পণ্য। দাম টাকায়, বানানো: মিনিকেট ৭৮, চিনিগুঁড়া ১৩৫, মসুর ১১০, সয়াবিন তেল ১৮৫, সাবান ৪৫. রাইডার দুজন: রহিম আর করিমের rider জামাল, মিতু আর সুমির কামাল।

ছবিটি logic-এর আরেকটি মূল ধারণা দেখায়। প্রতীক নিজে কিছু বোঝায় না; Ordered লিখলেই কম্পিউটার জানে না এটি “অর্ডার করা”। একটি interpretation প্রতিটি প্রতীককে জগতের কিছুর সঙ্গে মেলায়: Rahim মানে বাঁ দিকের প্রথম বৃত্ত, Ordered মানে আটটি রেখার সেট, rider মানে গ্রাহক থেকে রাইডারের ম্যাপ। বস্তুর সেট (এখানে ৯টি) হলো domain of discourse, আর domain ও interpretation মিলে একটি model. অংশ ৬-এ এটি আরও গুছিয়ে আসবে।

৩ · Quantifier — ∀ আর ∃, তাদের scope আর দুটি পরিচিত ভুল

Variable একা কিছু বলে না; Rice(x) সত্য না মিথ্যা, তা x কে, তার ওপর নির্ভর করে। Quantifier বলে দেয় x-কে কীভাবে পড়তে হবে:

• ∀x P(x) (“for all”, universal quantifier): domain-এর প্রতিটি বস্তু x-এর জন্য P(x) সত্য। একটি বস্তুতেও মিথ্যা হলে পুরো বাক্য মিথ্যা। বড় ∧-এর মতো: P(বস্তু১) ∧ P(বস্তু২) ∧ …
• ∃x P(x) (“there exists”, existential quantifier): domain-এ অন্তত একটি বস্তু আছে যার জন্য P সত্য। বড় ∨-এর মতো: P(বস্তু১) ∨ P(বস্তু২) ∨ …

Quantifier যে অংশের ওপর খাটে, সেটি তার scope, সাধারণত বন্ধনী দিয়ে দেখানো। Scope-এর ভেতরে থাকা x হলো bound variable; কোনো quantifier-এর আওতায় নেই এমন variable free variable. যেমন ∀x Ordered(x, y)-এ y free, তাই এটি পূর্ণ বাক্য নয়: y কে, না জানলে সত্য-মিথ্যা বলা যায় না। দুটি quantifier একে অপরের সঙ্গে বাঁধা: ¬∀x P(x) ≡ ∃x ¬P(x) (“সবাই নয়” মানে “অন্তত একজন নয়”) আর ¬∃x P(x) ≡ ∀x ¬P(x) (“কেউ না” মানে “প্রত্যেকেই না”)। এখানে ≡ মানে দুই দিকের অর্থ সব model-এ এক।

∀-এর সঙ্গে →, ∃-এর সঙ্গে ∧

বাস্তবের প্রায় সব “সব X হলো Y” বাক্যে ∀ বসে → এর সঙ্গে, আর “কোনো X আছে যা Y” বাক্যে ∃ বসে ∧ এর সঙ্গে। কারণটা domain-এ লুকিয়ে। domain-এ শুধু চাল নেই, গ্রাহকও আছেন। “সব চালের দাম ৬০ টাকার বেশি” বলতে চাইছি শুধু চালের কথা; রহিমের দাম নিয়ে কিছু বলছি না।

দ্বিতীয় ভুলটি সূক্ষ্ম। পর্ব ৪৫-এর truth table মনে করুন: A → B মিথ্যা শুধু তখন, যখন A সত্য আর B মিথ্যা। A মিথ্যা হলেই A → B সত্য (একে vacuous truth বলে)। ∃ খোঁজে একটিমাত্র সত্য উদাহরণ; সাবান চাল নয়, তাই Rice(Soap1) → … সত্য, আর ∃ খুশি। নিচের কোড বাজারঘরের জগতে চারটি রূপই যাচাই করে। ∀ মানে domain-এর সব বস্তুর ওপর loop আর all, ∃ মানে loop আর any. A → B লেখা হয়েছে not A or B হিসেবে। এই ব্লকে শুধু Python-এর মৌলিক অংশ; প্রথমবার চালালে ব্রাউজারে Python নামতে কয়েক সেকেন্ড লাগতে পারে।

customers = {"rahim", "karim", "mitu", "sumi"}
category = {"miniket": "rice", "chinigura": "rice", "mosur": "lentil",
            "soyoil": "oil", "soap1": "toiletry"}
price = {"miniket": 78, "chinigura": 135, "mosur": 110,   # taka, made up
         "soyoil": 185, "soap1": 45}
ordered = {("rahim", "miniket"), ("rahim", "mosur"), ("karim", "chinigura"),
           ("karim", "mosur"), ("karim", "soap1"), ("mitu", "soyoil"),
           ("sumi", "miniket"), ("sumi", "soyoil")}
D = sorted(customers | set(category))      # domain: every object in this world

Customer = lambda x: x in customers
Rice = lambda x: category.get(x) == "rice"
Lentil = lambda x: category.get(x) == "lentil"
Ordered = lambda x, y: (x, y) in ordered
forall = lambda f: all(f(x) for x in D)    # ∀ = loop, every object must pass
exists = lambda f: any(f(x) for x in D)    # ∃ = loop, one object is enough

print("domain size:", len(D))
# "Every rice costs more than 60 taka"    (A → B is written as: not A or B)
print("good ∀x (Rice(x) → price(x) > 60):", forall(lambda x: not Rice(x) or price[x] > 60))
print("bad  ∀x (Rice(x) ∧ price(x) > 60):", forall(lambda x: Rice(x) and price[x] > 60))
# "Mitu ordered some rice"
print("good ∃x (Rice(x) ∧ Ordered(mitu, x)):", exists(lambda x: Rice(x) and Ordered("mitu", x)))
print("bad  ∃x (Rice(x) → Ordered(mitu, x)):", exists(lambda x: not Rice(x) or Ordered("mitu", x)))
# "Every customer who ordered rice also ordered lentil"
rice_then_lentil = lambda x: (not (Customer(x) and exists(lambda y: Rice(y) and Ordered(x, y)))
                              or exists(lambda z: Lentil(z) and Ordered(x, z)))
print("∀x (Customer(x) ∧ ∃y(Rice(y) ∧ Ordered(x,y)) → ∃z(Lentil(z) ∧ Ordered(x,z))):",
      forall(rice_then_lentil))
print("counterexample:", [x for x in D if not rice_then_lentil(x)])

domain size: 9
good ∀x (Rice(x) → price(x) > 60): True
bad  ∀x (Rice(x) ∧ price(x) > 60): False
good ∃x (Rice(x) ∧ Ordered(mitu, x)): False
bad  ∃x (Rice(x) → Ordered(mitu, x)): True
∀x (Customer(x) ∧ ∃y(Rice(y) ∧ Ordered(x,y)) → ∃z(Lentil(z) ∧ Ordered(x,z))): False
counterexample: ['sumi']

৪ · Nested quantifier আর সমতা — ক্রম বদলালে অর্থ বদলায়

একাধিক quantifier একসঙ্গে বসলে তাকে nested quantifier বলে। একই ধরনের দুটি পাশাপাশি থাকলে ক্রম বদলানো যায়: ∀x∀y মানে ∀y∀x, ∃x∃y মানে ∃y∃x. কিন্তু ∀ আর ∃ মিশলে ক্রমই অর্থ ঠিক করে:

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

বাংলা বা ইংরেজি বাক্যে এই পার্থক্য প্রায়ই লুকিয়ে থাকে। “প্রত্যেক গ্রাহক একটি পণ্য অর্ডার করেছেন” দুইভাবেই পড়া যায়; এটি quantifier scope-এর অস্পষ্টতা, যা ভাষাবিজ্ঞানেও পরিচিত সমস্যা। FOL-এ লিখতে গেলেই আপনাকে বেছে নিতে হয়, আর এটাই FOL-এর একটি বড় উপকার: অস্পষ্টতা ধরা পড়ে। নিচের stepper বাজারঘরের অর্ডারের সারণিতে দুটি ক্রম loop দিয়ে যাচাই করে। গ্রাহক আর পণ্য বর্ণানুক্রমে: karim, mitu, rahim, sumi; chinigura, miniket, mosur, soap1, soyoil. “look-up” মানে একবার সারণিতে দেখা, Ordered(x, y) আছে কি না।

1for x in customers:        # ∀x2    find y: Ordered(x, y)   # ∃y3result: True if all found4for y in products:         # ∃y5    all x: Ordered(x, y)?   # ∀x6result: True if one y works

সমতা (=) দিয়ে গোনা আর সীমা টানা

FOL-এ একটি বিশেষ predicate আছে: সমতা, t1 = t2, মানে দুটি term একই বস্তুকে বোঝায়। এটি দিয়েই “অন্তত দুটি”, “ঠিক একটি” আর “শুধু” লেখা যায়:

• অন্তত দুটি আলাদা চাল: ∃x ∃y (Rice(x) ∧ Rice(y) ∧ ¬(x = y)). ¬(x = y) না লিখলে x আর y একই মিনিকেট হতে পারত, তখন “অন্তত একটি” হয়ে যেত।
• শুধু করিম সাবান কিনেছেন: Ordered(Karim, Soap1) ∧ ∀x (Ordered(x, Soap1) → x = Karim). প্রথম অংশ বলে করিম কিনেছেন; দ্বিতীয় অংশ বলে আর যে-ই কিনুক, সে করিমই।
• ঠিক একজন গ্রাহক সাবান কিনেছেন: ∃x (Customer(x) ∧ Ordered(x, Soap1) ∧ ∀y (Customer(y) ∧ Ordered(y, Soap1) → y = x)).

একটি সূক্ষ্ম কথা: FOL নিজে ধরে নেয় না যে আলাদা নামের constant আলাদা বস্তু। Miniket আর Chinigura একই বস্তুর দুই নাম হতে পারে, যদি না আপনি ¬(Miniket = Chinigura) লিখে দেন। Database আর Prolog এর উল্টোটা ধরে নেয়; একে বলে unique names assumption. নিচের কোড অংশ ৪-এর দুটি ক্রম আর সমতার তিনটি বাক্য একই জগতে যাচাই করে।

customers = ["karim", "mitu", "rahim", "sumi"]
products = ["chinigura", "miniket", "mosur", "soap1", "soyoil"]
rice = {"miniket", "chinigura"}
ordered = {("rahim", "miniket"), ("rahim", "mosur"), ("karim", "chinigura"),
           ("karim", "mosur"), ("karim", "soap1"), ("mitu", "soyoil"),
           ("sumi", "miniket"), ("sumi", "soyoil")}
checks = 0
def O(x, y):                       # Ordered(x, y), counting each look-up
    global checks
    checks += 1
    return (x, y) in ordered

# ∀x ∃y Ordered(x, y): every customer ordered at least one product
checks = 0
a = all(any(O(x, y) for y in products) for x in customers)
print("∀x∃y Ordered(x,y):", a, "| look-ups:", checks)
for x in customers:
    print("  ", x, "->", [y for y in products if (x, y) in ordered][0])
# ∃y ∀x Ordered(x, y): one product that every customer ordered
checks = 0
b = any(all(O(x, y) for x in customers) for y in products)
print("∃y∀x Ordered(x,y):", b, "| look-ups:", checks)

# equality: "at least two different rice products"
print("∃x∃y (Rice(x) ∧ Rice(y) ∧ x ≠ y):",
      any(x != y for x in rice for y in rice))
# "only karim ordered soap1":  ∀x (Ordered(x, soap1) → x = karim)
print("∀x (Ordered(x, soap1) → x = karim):",
      all(x == "karim" for x in customers if (x, "soap1") in ordered))
# "no customer ordered both rice and oil": ¬∃x (... ∧ ...)
both = [x for x in customers if any((x, r) in ordered for r in rice)
        and (x, "soyoil") in ordered]
print("¬∃x (OrderedRice(x) ∧ Ordered(x, soyoil)):", not both, both)

∀x∃y Ordered(x,y): True | look-ups: 10
   karim -> chinigura
   mitu -> soyoil
   rahim -> miniket
   sumi -> miniket
∃y∀x Ordered(x,y): False | look-ups: 8
∃x∃y (Rice(x) ∧ Rice(y) ∧ x ≠ y): True
∀x (Ordered(x, soap1) → x = karim): True
¬∃x (OrderedRice(x) ∧ Ordered(x, soyoil)): False ['sumi']

৫ · বাংলা বাক্য থেকে FOL, আর FOL থেকে বাংলা

অনুবাদের একটি কাজের নিয়ম: (১) কাদের নিয়ে কথা, ঠিক করুন: “সব”, “প্রত্যেক”, “যে … সে” মানে ∀; “কেউ”, “কিছু”, “একটি আছে” মানে ∃; (২) ∀-এর ভেতরে শর্ত → ফল, ∃-এর ভেতরে গুণ ∧ গুণ; (৩) “না”, “কেউ না” এলে ¬ কোথায় বসছে, দেখুন; (৪) শেষে প্রতিটি variable bound কি না, মিলিয়ে নিন। নিচের stepper অংশ ১-এর নিয়মটি এই ধাপে বানায়।

1who?   every customer -> ∀x2if:    x ordered some rice3then:  x ordered some lentil4join:  ∀x (if → then)5check: all variables bound6test in the shop world

বারোটি বাক্য, বাজারঘরের জগতে যাচাইসহ

শেষ কলামের সত্যমান অংশ ২-এর জগৎ থেকে একটি ছোট Python script দিয়ে হিসাব করা (অংশ ৩-৪-এর মতো loop). Grocery মানে চাল, ডাল বা তেল; Product আর Customer নিজেদের সেট।

তিনটি কঠিন রূপ আলাদা করে দেখুন। “কেউ না” / “কোনো … নয়” (৪, ৫): ¬∃ দিয়ে শুরু করা সবচেয়ে নিরাপদ, তারপর চাইলে ¬∃x P ≡ ∀x ¬P দিয়ে বদলানো। ভুল প্রায়ই হয় ¬ ভুল জায়গায় বসিয়ে: ∃x (Rice(x) ∧ ¬(price(x) < 60)) মানে “অন্তত একটি চাল ৬০-এর কম নয়”, অনেক দুর্বল কথা। “শুধু” (৮): দুটি অংশ লাগে, কেউ একজন করেছেন আর অন্য কেউ করেননি; দ্বিতীয় অংশটি → আর = দিয়ে। “অন্তত দুটি” আর “ঠিক একটি” (৯, ১০): সমতা ছাড়া গোনা যায় না। “অন্তত তিনটি” লিখতে তিনটি variable আর তিনটি জোড়া ≠ লাগে; সংখ্যা বড় হলে বাক্যও বড় হয়, কারণ FOL-এ সরাসরি “গোনা”র চিহ্ন নেই।

FOL থেকে বাংলায় পড়া উল্টো দিক থেকে একই নিয়ম। ∀x (Product(x) → ∃y (Customer(y) ∧ Ordered(y, x))) পড়ুন: “প্রত্যেক পণ্যের জন্য অন্তত একজন গ্রাহক আছেন যিনি সেটি অর্ডার করেছেন”, মানে “কোনো পণ্য অবিক্রীত নেই”। এই জগতে সত্য: প্রতিটি পণ্যের পাশে অন্তত একটি রেখা আছে (ছবিটি দেখুন)। আবার ∀x ∀y (Ordered(x, Soap1) ∧ Ordered(y, Soap1) → x = y) মানে “বড়জোর একজন সাবান কিনেছেন”; “ঠিক একজন” নয়, কারণ কেউ না কিনলেও এটি সত্য।

৬ · Model, interpretation আর entailment — সহজ ভাষায়

অংশ ২-এর ছবিটি একটি model. আরও গুছিয়ে বললে, FOL-এর একটি model দুটি জিনিস: একটি অশূন্য domain (বস্তুর সেট), আর একটি interpretation, যা বলে দেয় প্রতিটি constant কোন বস্তু, প্রতিটি predicate কোন কোন বস্তু-তালিকার জন্য সত্য, আর প্রতিটি function কোন বস্তুকে কোন বস্তুতে নেয়। এরপর যেকোনো বাক্যের সত্য-মিথ্যা যান্ত্রিকভাবে ঠিক হয়: atomic sentence সারণি দেখে, connective পর্ব ৪৫-এর truth table দিয়ে, ∀ আর ∃ domain-এর ওপর loop দিয়ে। অংশ ৩ আর ৪-এর কোড ঠিক এটাই করেছে।

কিন্তু একটি জ্ঞানভান্ডার, মানে knowledge base (KB), সাধারণত একটি নির্দিষ্ট জগৎকে পুরো বর্ণনা করে না; কিছু নিয়ম আর তথ্য দেয় মাত্র। পর্ব ৪৫-এর মতোই, KB ⊨ α (পড়ুন “KB entails α”; ⊨ চিহ্নের মানে entailment) মানে: যে যে model-এ KB-র সব বাক্য সত্য, তার প্রতিটিতে α-ও সত্য। একটি model-এ সত্য হওয়া এক জিনিস, KB থেকে অবশ্যম্ভাবী হওয়া আরেক জিনিস। বাক্য ১২ বাজারঘরের এই জগতে মিথ্যা, কিন্তু একটি KB, যাতে শুধু লেখা “মিনিকেট চাল” আর “সুমি মিনিকেট কিনেছেন”, তা থেকে ১২-এর অস্বীকারও entail হয় না, কারণ এমন model-ও আছে যেখানে সুমি ডালও কিনেছেন।

Database-এর সঙ্গে মিলটি এখানে স্পষ্ট: টেবিলের একটি সেট আসলে একটি সীমিত model, প্রতিটি টেবিল একটি predicate-এর সত্য সারি, আর SQL query সেই model-এ একটি সূত্র যাচাই (অংশ ৯).

৭ · FOL-এ inference — instantiation, unification আর generalised modus ponens

ধরুন KB-তে আছে: ∀x (Rice(x) → Grocery(x)) আর Rice(Miniket). মানুষ সঙ্গে সঙ্গে বলেন “তাহলে মিনিকেট মুদি পণ্য”। এই লাফটি যন্ত্রকে শেখানোর তিনটি ধাপ আছে।

দুটি instantiation নিয়ম

• Universal instantiation (UI): ∀x α থেকে x-এর জায়গায় যেকোনো ground term (variable ছাড়া term) বসিয়ে নতুন বাক্য পাওয়া যায়। ∀x (Rice(x) → Grocery(x)) থেকে Rice(Miniket) → Grocery(Miniket), আবার Rice(Rahim) → Grocery(Rahim), এমনকি Rice(rider(Sumi)) → Grocery(rider(Sumi)). সব সত্য, কারণ “সবার জন্য” সত্য কথা প্রত্যেকের জন্য সত্য।
• Existential instantiation (EI): ∃x α থেকে x-এর জায়গায় একটি নতুন constant বসানো, যা KB-তে আর কোথাও নেই। ∃x (Customer(x) ∧ Ordered(x, Soap1)) থেকে Customer(C1) ∧ Ordered(C1, Soap1). C1-কে বলে Skolem constant: “যে-ই হোন, তাঁকে আপাতত C1 ডাকি”। পুরোনো নাম (যেমন Karim) বসানো চলবে না, কারণ KB জানে না সেই মানুষটি করিমই। EI একবারই প্রয়োগ হয়, আর ∀-এর ভেতরে থাকা ∃-এর জন্য constant নয়, function লাগে (∀x∃y Ordered(x, y) থেকে ∀x Ordered(x, F(x))), কারণ y প্রতিটি x-এর জন্য আলাদা হতে পারে।

Propositionalisation আর তার বিস্ফোরণ

একটি সরল কৌশল: সব ∀ বাক্যে সম্ভাব্য সব ground term বসিয়ে দিন, তাহলে variable আর থাকে না, আর পুরো KB পর্ব ৪৫-এর propositional KB হয়ে যায়; সেখানে resolution বা SAT solver চালানো যায়। একে বলে propositionalisation. সমস্যা আকারে, এক ধরনের combinatorial explosion. অংশ ৮-এর Prolog KB-তে ১৫টি constant আছে (৪ গ্রাহক, ৫ পণ্য, ৬টি category). তিনটি variable-এর একটি নিয়ম, যেমন bought_from(U, C) :- ordered(U, P), in_cat(P, C), থেকে 15³ = ৩,৩৭৫টি ground বাক্য আসে, যার প্রায় সবই অর্থহীন (“সাবান মিনিকেট থেকে চাল কিনেছে”)। আর একটি function প্রতীক থাকলেই ground term অসীম: Rahim, rider(Rahim), rider(rider(Rahim)), … তখন সব বসানো অসম্ভব।

Unification — সব বসানোর বদলে ঠিকটি খোঁজা

বুদ্ধিমান পথ: সব ground term না বসিয়ে শুধু সেই substitution খোঁজা, যা দুটি বাক্যকে হুবহু এক করে। Substitution θ মানে variable থেকে term-এর একটি তালিকা, যেমন {x/Miniket} (“x-এর জায়গায় Miniket”). Unification হলো দুটি atomic sentence p আর q-এর জন্য এমন θ খোঁজা যাতে pθ = qθ. যেমন Ordered(Rahim, x) আর Ordered(y, Miniket) মেলে θ = {x/Miniket, y/Rahim} দিয়ে। Ordered(Rahim, x) আর Ordered(Karim, y) মেলে না, কারণ Rahim আর Karim দুটি আলাদা constant, কোনো substitution তাদের এক করতে পারে না।

প্রায়ই একাধিক unifier থাকে। Ordered(x, y) আর Ordered(z, Miniket) মেলে {x/z, y/Miniket} দিয়ে, আবার {x/Rahim, z/Rahim, y/Miniket} দিয়েও। দ্বিতীয়টি অকারণে x-কে রহিম বানিয়ে ফেলেছে। প্রথমটি most general unifier (MGU): সবচেয়ে কম প্রতিশ্রুতি দেয়, আর অন্য যেকোনো unifier তার ওপর আরও substitution চাপিয়ে পাওয়া যায়। প্রতীকের নাম বাদ দিলে MGU একটিই। নিচের stepper একটি একটু জটিল জোড়া ধাপে ধাপে মেলায়; এখানে P আর f যেকোনো predicate আর function-এর নাম, আর Prolog-এর মতো বড় হাতের অক্ষর variable.

1same functor and arity?2for each argument pair:3    apply θ, then compare4    var? occurs check, bind5return θ  (the MGU)6occurs -> FAIL

এবার একই অ্যালগরিদম Python-এ। Term হলো একটি string (বড় হাতের অক্ষরে শুরু হলে variable, নইলে constant) অথবা একটি tuple, যার প্রথম উপাদান functor বা predicate-এর নাম। unify substitution-কে একটি dict হিসেবে নিয়ে নতুন dict ফেরত দেয়, ব্যর্থ হলে None. শেষ জোড়াটি সরাসরি occurs check পরীক্ষা করে।

def is_var(t): return isinstance(t, str) and t[:1].isupper()   # X, Y, Z...
def walk(t, s):                    # follow variable bindings in s
    while is_var(t) and t in s:
        t = s[t]
    return t
def occurs(v, t, s):               # does variable v appear inside term t?
    t = walk(t, s)
    return t == v or (isinstance(t, tuple) and any(occurs(v, a, s) for a in t[1:]))
def unify(a, b, s):
    if s is None: return None
    a, b = walk(a, s), walk(b, s)
    if a == b: return s
    if is_var(a): return None if occurs(a, b, s) else {**s, a: b}
    if is_var(b): return unify(b, a, s)
    if isinstance(a, tuple) and isinstance(b, tuple) and a[0] == b[0] and len(a) == len(b):
        for x, y in zip(a[1:], b[1:]):
            s = unify(x, y, s)
        return s
    return None                    # different constants or functors
def full(t, s):                    # apply the substitution all the way down
    t = walk(t, s)
    return (t[0], *[full(a, s) for a in t[1:]]) if isinstance(t, tuple) else t
def show(t): return t if not isinstance(t, tuple) else f"{t[0]}({', '.join(map(show, t[1:]))})"
pairs = [(("Ordered", "rahim", "X"), ("Ordered", "Y", "miniket")),
         (("Delivers", ("rider", "Y"), "Y"), ("Delivers", "X", "rahim")),
         (("Ordered", "X", "Y"), ("Ordered", "Z", "miniket")),
         (("Ordered", "rahim", "X"), ("Ordered", "karim", "Y")),
         (("Ordered", "X", "X"), ("Ordered", "rahim", "miniket")),
         ("X", ("rider", "X"))]
for a, b in pairs:
    s = unify(a, b, {})
    out = "FAIL" if s is None else "{" + ", ".join(f"{v}/{show(full(v, s))}" for v in sorted(s)) + "}"
    print(f"{show(a):22} ≐ {show(b):22} -> {out}")

Ordered(rahim, X)      ≐ Ordered(Y, miniket)    -> {X/miniket, Y/rahim}
Delivers(rider(Y), Y)  ≐ Delivers(X, rahim)     -> {X/rider(rahim), Y/rahim}
Ordered(X, Y)          ≐ Ordered(Z, miniket)    -> {X/Z, Y/miniket}
Ordered(rahim, X)      ≐ Ordered(karim, Y)      -> FAIL
Ordered(X, X)          ≐ Ordered(rahim, miniket) -> FAIL
X                      ≐ rider(X)               -> FAIL

Generalised modus ponens

পর্ব ৪৫-এর modus ponens: P আর P → Q থেকে Q. FOL-এ তার সঙ্গে unification জুড়ে দিলে পাওয়া যায় generalised modus ponens (GMP): যদি KB-তে থাকে p₁′, …, p_n′ আর (p₁ ∧ … ∧ p_n → q), আর একটি θ থাকে যাতে প্রতিটি p_i′θ = p_iθ, তবে qθ সিদ্ধান্ত। উদাহরণ:

নিয়ম:  Ordered(x, y) ∧ Rice(y) → BoughtRice(x)
তথ্য:   Ordered(Sumi, Miniket)    Rice(Miniket)
θ = {x/Sumi, y/Miniket}
সিদ্ধান্ত: BoughtRice(Sumi)

একটি ধাপে UI, unification আর modus ponens একসঙ্গে, অথচ অপ্রয়োজনীয় কোনো ground বাক্য বানানো হয়নি। GMP Horn clause-এর (বড়জোর একটি ধনাত্মক literal; সাধারণত “শর্ত ∧ শর্ত → একটি ফল”) KB-তে sound আর complete: যা entail হয়, তা খুঁজে পাবে। GMP দুই দিকে চালানো যায়: তথ্য থেকে সামনে নতুন তথ্য বানানো (forward chaining) বা প্রশ্ন থেকে পেছনে শর্তে যাওয়া (backward chaining); দুটির বিস্তারিত তুলনা, conflict resolution আর expert system পর্ব ৪৭-এ। পূর্ণ FOL-এর জন্য (Horn নয় এমন বাক্যসহ) প্রমাণের complete পদ্ধতি হলো resolution-এর FOL রূপ, যা J. A. Robinson ১৯৬৫ সালে unification-সহ প্রকাশ করেন।

৮ · Prolog — FOL-এর একটি অংশ, সত্যিকারের যন্ত্র হিসেবে

Prolog (“programming in logic”) প্রোগ্রাম লেখে Horn clause দিয়ে, আর প্রশ্নের উত্তর খোঁজে backward chaining আর unification দিয়ে: লক্ষ্যটি কোন নিয়মের মাথার সঙ্গে মেলে, তা দেখা হয়; মিললে সেই নিয়মের শরীরের শর্তগুলো নতুন লক্ষ্য; বাঁ থেকে ডানে, গভীরে আগে (depth-first), ব্যর্থ হলে পিছিয়ে পরের নিয়ম। প্রথমে এর ছোট একটি রূপ নিজে লিখে দেখা যাক। নিচের কোডে category-র ধাপক্রম (চাল ⊂ মুদি ⊂ খাদ্য) parent/ancestor নিয়মের মতো দুটি নিয়মে লেখা: above মানে “সরাসরি বা কয়েক ধাপ ওপরে”।

FACTS = """is_a miniket rice | is_a chinigura rice | is_a mosur lentil
| is_a soyoil oil | sub rice grocery | sub lentil grocery | sub oil grocery
| sub grocery food | ordered sumi miniket | ordered mitu soyoil"""
KB = [(tuple(f.split()), []) for f in FACTS.replace("\n", " ").split("|")]
KB += [(("above", "S", "C"), [("sub", "S", "C")]),
       (("above", "S", "C"), [("sub", "S", "M"), ("above", "M", "C")]),
       (("in_cat", "P", "C"), [("is_a", "P", "C")]),
       (("in_cat", "P", "C"), [("is_a", "P", "S"), ("above", "S", "C")]),
       (("bought", "U", "C"), [("ordered", "U", "P"), ("in_cat", "P", "C")])]
var = lambda t: t[:1].isupper()
def walk(t, s):
    while var(t) and t in s: t = s[t]
    return t
def unify(a, b, s):                  # atoms are flat tuples of names here
    if len(a) != len(b): return None
    for x, y in zip(a, b):
        x, y = walk(x, s), walk(y, s)
        if x == y: continue
        if var(x): s = {**s, x: y}
        elif var(y): s = {**s, y: x}
        else: return None
    return s
tries = [0]                          # [rule tries so far]
def solve(goals, s):                 # backward chaining, depth-first, left to right
    if not goals: yield s; return
    for head, body in KB:
        ren = lambda atom: tuple(f"{t}_{n}" if var(t) else t for t in atom)
        tries[0] += 1; n = tries[0]  # rename rule variables: S -> S_7
        s2 = unify(goals[0], ren(head), s)
        if s2 is not None:
            yield from solve([ren(b) for b in body] + goals[1:], s2)
for q in [("above", "rice", "C"), ("in_cat", "P", "food"), ("bought", "U", "grocery")]:
    tries[0] = 0
    ans = [walk(q[2] if var(q[2]) else q[1], s) for s in solve([q], {})]
    print(" ".join(q), "->", ans, "| rule tries:", tries[0])

above rice C -> ['grocery', 'food'] | rule tries: 135
in_cat P food -> ['miniket', 'chinigura', 'mosur', 'soyoil'] | rule tries: 585
bought U grocery -> ['sumi', 'mitu'] | rule tries: 390

SWI-Prolog-এ সত্যিকারের run

এবার একই জ্ঞান আসল Prolog-এ। লেখার সময়ে SWI-Prolog-এর সর্বশেষ stable সংস্করণ 10.0.2 (swi-prolog.org-এর download পাতা অনুযায়ী)। Windows-এ অফিসিয়াল installer নামিয়ে তার SHA-256 checksum পাতার সঙ্গে মিলিয়ে, install না করে 7-Zip দিয়ে একটি আলাদা ফোল্ডারে খুলে swipl চালানো হয়েছে; Linux আর macOS-এ সাধারণত package manager দিয়ে বসানো হয়। জ্ঞানভান্ডারের ফাইল (সব নাম আর তথ্য বানানো):

% facts: product -> its own category
is_a(miniket, rice).      is_a(chinigura, rice).
is_a(mosur, lentil).      is_a(soyoil, oil).
is_a(soap1, toiletry).
% facts: category -> parent category
sub(rice, grocery).  sub(lentil, grocery).  sub(oil, grocery).
sub(grocery, food).
% facts: who ordered what
ordered(rahim, miniket).   ordered(rahim, mosur).
ordered(karim, chinigura). ordered(karim, mosur).  ordered(karim, soap1).
ordered(mitu, soyoil).
ordered(sumi, miniket).    ordered(sumi, soyoil).
% rules (Horn clauses)
above(S, C) :- sub(S, C).
above(S, C) :- sub(S, M), above(M, C).
in_cat(P, C) :- is_a(P, C).
in_cat(P, C) :- is_a(P, S), above(S, C).
bought_from(Cust, Cat) :- ordered(Cust, P), in_cat(P, Cat).
% "ordered rice but no lentil" (\+ = negation as failure)
rice_no_lentil(C) :- bought_from(C, rice), \+ bought_from(C, lentil).

Prolog-এ :- মানে ← (“যদি”), কমা মানে ∧, আর প্রতিটি variable নিয়মের মাথায় নীরবে ∀. প্রশ্নগুলো একটি ফাইলে রেখে একটি ছোট driver (ask.pl, প্রতিটি প্রশ্ন পড়ে সব উত্তর ছাপায়) দিয়ে চালানো হয়েছে। সত্যিকারের run (SWI-Prolog 10.0.2, Windows 64-bit):

~/bazarghar-fol$ swipl ask.pl
SWI-Prolog 10.0.2
?- in_cat(mosur,food).
   true.
?- findall(P,in_cat(P,grocery),Ps).
   Ps = [miniket,chinigura,mosur,soyoil]
?- above(rice,C).
   C = grocery
   C = food
?- setof(C,bought_from(C,rice),Cs).
   Cs = [karim,rahim,sumi]
?- rice_no_lentil(Who).
   Who = sumi
?- bought_from(Who,toiletry).
   Who = karim
?- forall(bought_from(C,rice),bought_from(C,lentil)).
   false.
?- bought_from(mitu,rice).
   false.
?- f(X,b)=f(a,Y).
   X = a   Y = b
?- unify_with_occurs_check(X,f(X)).
   false.
?- X=f(X),cyclic_term(X).
   X = @(S_1,[S_1=f(S_1)])

৯ · FOL-এর সীমা, আর আজ FOL-এর ধারণা কোথায় বেঁচে আছে

Semi-decidable: “হ্যাঁ” মিলবে, “না” নাও মিলতে পারে

FOL-এর জন্য complete প্রমাণ-পদ্ধতি আছে: যা entail হয়, তার প্রমাণ একসময় পাওয়া যায় (Gödel-এর completeness theorem, ১৯২৯–৩০)। কিন্তু Church আর Turing ১৯৩৬ সালের দিকে আলাদাভাবে দেখান, এমন কোনো সাধারণ অ্যালগরিদম নেই যা প্রতিটি FOL বাক্যের জন্য শেষ পর্যন্ত “entail হয়” বা “হয় না” বলে থামবে। তাই FOL-এ entailment semi-decidable: উত্তর “হ্যাঁ” হলে খোঁজা থামে, “না” হলে চিরকাল চলতে পারে। বাস্তবের theorem prover তাই সময়-সীমা দিয়ে চালানো হয়, আর “সময় শেষ” মানে “মিথ্যা” নয়। একই কারণে অনেক ব্যবস্থা FOL-এর এমন সীমিত অংশ বেছে নেয়, যেখানে উত্তর সবসময় থামে: function ছাড়া Horn clause (Datalog), বা নিচের description logic.

Description logic আর knowledge graph — পর্ব ৪৮-এর দিকে

Description logic হলো FOL-এর সাবধানে কাটা অংশ: শুধু এক-argument-এর predicate (concept, যেমন Rice) আর দুই-argument-এর predicate (role, যেমন ordered), আর সীমিত ধরনের quantifier. বিনিময়ে বেশিরভাগ প্রশ্নের উত্তর নিশ্চিতভাবে থামে। ওয়েবের ontology ভাষা OWL এর ওপর দাঁড়িয়ে। আর knowledge graph আসলে দুই-argument-এর atomic sentence-এর বিশাল একটি সংগ্রহ: (miniket, is_a, rice) ধরনের triple. এগুলো, RDF আর SPARQL দিয়ে প্রশ্ন, পর্ব ৪৮-এর বিষয় (Knowledge graph — বস্তু, সম্পর্ক আর প্রশ্ন)।

যেখানে FOL-এর ধারণা রোজ কাজ করে

১০ · AI-এর যুগে — AI সহকারী দিয়ে বাক্যকে logic-এ লেখা

“এই নিয়মটা first-order logic-এ লিখে দাও” বা “এর Prolog কোড দাও” বললে AI সহকারী দ্রুত উত্তর দেয়, আর বেশিরভাগ সময় দেখতে ঠিক। কিন্তু logic-এ একটি চিহ্নের ভুলে পুরো অর্থ উল্টে যায়, আর ভুলটি চোখে পড়ে না। Large language model-এর উত্তর পরিসংখ্যানভিত্তিক অনুমান (পর্ব ৭০-এ বিস্তারিত); সে বাক্যটি “বোঝে” বলে ধরে নেওয়ার কারণ নেই। ভালো ভাগাভাগি: AI খসড়া লিখুক, আর আপনি একটি ছোট সীমিত জগতে (অংশ ৩-এর মতো) বা Prolog-এ চালিয়ে যাচাই করুন। এ ধরনের কাজে AI সহকারীরা প্রায়ই যা করে:

• ∀-এর সঙ্গে ∧, ∃-এর সঙ্গে →: অংশ ৩-এর দুটি ভুল; মানুষের মতোই, আর আত্মবিশ্বাসের সঙ্গে।
• Quantifier-এর ক্রম বেছে নেওয়া চুপচাপ: “প্রত্যেক গ্রাহক একটি পণ্য কিনেছেন”-কে ∃y∀x লেখা, অস্পষ্টতার কথা না বলে।
• “শুধু” আর “ঠিক একটি”-র অর্ধেক লেখা: সমতার অংশ বাদ দেওয়া, যাতে “অন্তত একটি” হয়ে যায়।
• Prolog-এর \+-কে খাঁটি ¬ বলা: negation as failure আর closed world-এর কথা না বলা; বা occurs check নেই, তা না জানানো।
• বানানো built-in বা পুরোনো আচরণ: অস্তিত্বহীন predicate বা অন্য Prolog সংস্করণের আচরণ SWI-Prolog-এর বলে চালানো।
• যাচাই ছাড়া “প্রমাণিত” বলা: একটি উদাহরণে সত্য দেখে entailment দাবি করা; অংশ ৬-এর পার্থক্য গুলিয়ে ফেলা।

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

• প্রতিটি ∀-এর ভেতরে →, প্রতিটি ∃-এর ভেতরে ∧ আছে কি না দেখেছি; ব্যতিক্রম থাকলে কারণ বুঝেছি
• Quantifier-এর ক্রম আর ¬-এর জায়গা মূল বাক্যের সঙ্গে মিলিয়েছি; অস্পষ্ট বাক্যে নিজে একটি অর্থ বেছে লিখে রেখেছি
• একটি ছোট বানানো জগতে বাক্যটি loop দিয়ে চালিয়ে দেখেছি, এমন জগৎও বানিয়েছি যেখানে বাক্যটি মিথ্যা হওয়ার কথা
• Prolog কোড আসল SWI-Prolog-এ চালিয়েছি; সংস্করণ swipl --version দিয়ে দেখেছি, অচেনা built-in অফিসিয়াল manual-এ খুঁজেছি
• \+, cut আর occurs check-এর মতো অ-খাঁটি অংশ কোথায়, তা চিহ্নিত করেছি
• আসল গ্রাহক বা কর্মীর ব্যক্তিগত তথ্য AI-তে পেস্ট করিনি; উদাহরণে বানানো নাম ব্যবহার করেছি