Quantifier-এর Negation আর Translation: বাক্য থেকে Predicate Logic

গত পর্বে ∀ আর ∃ শিখেছি। এবার এগুলো দিয়ে সত্যিকারের বাক্য লেখা, negation করা আর software-এর নিয়ম লেখা দেখব। এখানে একটা ছোট নিয়ম না জানলে প্রায় সবাই একই ভুল করে, সেটাও দেখব। (Section 1.4)

Restricted domain#

অনেক সময় quantifier-এর পাশেই একটা শর্ত লিখে domain ছোট করে দেওয়া হয়। Domain = সব real number ধরে:

• ∀x < 0 (x² > 0): "প্রতিটা ঋণাত্মক real number-এর square ধনাত্মক।" এর মানে ∀x (x < 0 → x² > 0)
• ∀y ≠ 0 (y³ ≠ 0): "প্রতিটা nonzero real number-এর cube nonzero।" মানে ∀y (y ≠ 0 → y³ ≠ 0)
• ∃z > 0 (z² = 2): "2-এর একটা ধনাত্মক square root আছে।" মানে ∃z (z > 0 ∧ z² = 2)

প্যাটার্নটা খেয়াল করুন: ∀-এর শর্ত বসে → দিয়ে, আর ∃-এর শর্ত বসে ∧ দিয়ে। এই নিয়মটা নিচে আবার লাগবে।

Precedence আর binding#

Precedence: ∀ আর ∃ এর precedence সব logical operator-এর চেয়ে বেশি। তাই ∀x P(x) ∨ Q(x) মানে (∀x P(x)) ∨ Q(x), ∀x (P(x) ∨ Q(x)) না। দ্বিতীয়টা বোঝাতে চাইলে bracket দিতেই হবে।

Bound আর free variable: quantifier যে variable-এর উপর বসে, সেটা bound। Quantifier-ও নেই, value-ও বসানো হয়নি, এমন variable free।

∃x (x + y = 1) এ x bound (∃x দিয়ে), কিন্তু y free। একটাও free variable থাকলে পুরো expression proposition হয় না।

Code-এ এটা অনেকটা scope-এর মতো:

const found = [1, 2, 3].some((x) => x + y === 1);
// x bound: callback-এর parameter
// y free: বাইরে কোথাও define না থাকলে ReferenceError

Quantifier-এর equivalence#

Quantifier-যুক্ত দুটো statement logically equivalent, যদি যেকোনো predicate আর যেকোনো domain-এ এদের truth value একই হয়।

উদাহরণ: ∀x (P(x) ∧ Q(x)) ≡ ∀x P(x) ∧ ∀x Q(x)

"সবাই ভদ্র এবং পরিশ্রমী" আর "সবাই ভদ্র, এবং সবাই পরিশ্রমী" একই কথা।

Quantifier-এর negation: De Morgan আবার#

"ক্লাসের সব student Java course করেছে": ∀x J(x), domain = ক্লাসের student।

এর negation কী? "সব student Java করেছে, কথাটা সত্যি না।" মানে অন্তত একজন student আছে, যে Java করেনি: ∃x ¬J(x)।

এভাবেই আসে quantifier-এর De Morgan law:

• ¬∀x P(x) ≡ ∃x ¬P(x)
• ¬∃x P(x) ≡ ∀x ¬P(x)

নিয়ম: negation quantifier পার হলে ∀ হয়ে যায় ∃, আর ∃ হয়ে যায় ∀। পর্ব ৪-এর De Morgan-এর মতোই, আর সেটা কাকতালীয় না। Finite domain-এ ∀ মানে বড় একটা ∧, আর ∃ মানে বড় একটা ∨, তাই এটা আসলে সেই একই law।

Code-এ:

// "সব user verified, কথাটা সত্যি না"
!users.every((u) => u.verified);
 
// একই কথা: "অন্তত একজন user unverified"
users.some((u) => !u.verified);

বাক্য থেকে predicate logic#

প্রথম কাজ: domain ঠিক করা। Domain বদলালে লেখাও বদলায়।

"এই ক্লাসের প্রতিটা student Java course করেছে।"#

• Domain = এই ক্লাসের student হলে: ∀x J(x)
• Domain = সব মানুষ হলে, S(x) = "x এই ক্লাসের student" যোগ করে: ∀x (S(x) → J(x))

∀x (S(x) ∧ J(x)) লিখলে ভুল। এর মানে দাঁড়ায় "পৃথিবীর সব মানুষ এই ক্লাসের student, এবং সবাই Java করেছে", যেটা একদম অন্য কথা।

"এই ক্লাসের কোনো একজন student Java course করেছে।"#

• Domain = এই ক্লাসের student হলে: ∃x J(x)
• Domain = সব মানুষ হলে: ∃x (S(x) ∧ J(x))

∃x (S(x) → J(x)) লিখলে ভুল। ক্লাসের বাইরের যেকোনো মানুষের জন্য S(x) false, তাই S(x) → J(x) true হয়ে যায় (vacuously)। মানে ক্লাসের কেউ Java না করলেও এটা true।

তাই মনে রাখার নিয়ম, restricted domain-এর মতোই:

• "সব ..." হলে ∀x (শর্ত → দাবি)
• "কোনো একজন ..." হলে ∃x (শর্ত ∧ দাবি)

Code-এ দেখলে ব্যাপারটা আরও পরিষ্কার। পর্ব ৪-এ দেখেছি p → q ≡ ¬p ∨ q:

// ∀x (S(x) → J(x)): ক্লাসের বাইরের সবাই বাদ, ভেতরের সবাই Java করেছে
people.every((p) => !p.inClass || p.tookJava);
 
// ∃x (S(x) ∧ J(x)): এমন একজন, যে ক্লাসে আছে আর Java করেছে
people.some((p) => p.inClass && p.tookJava);

আরও দুটো উদাহরণ (domain = সব মানুষ, S(x) = "x এই ক্লাসের student"):

• "এই ক্লাসের কেউ একজন কক্সবাজার গেছে।" C(x) = "x কক্সবাজার গেছে" ধরলে: ∃x (S(x) ∧ C(x))
• "এই ক্লাসের প্রত্যেকে কক্সবাজার অথবা সিলেট গেছে।" Y(x) = "x সিলেট গেছে" ধরলে: ∀x (S(x) → (C(x) ∨ Y(x)))

System specification#

Software-এর নিয়ম লিখতেও quantifier লাগে।

"1 MB-এর বড় প্রতিটা mail message compress করা হবে।"

L(m, y) = "message m, y MB-এর বড়", C(m) = "message m compress হবে" ধরলে: ∀m (L(m, 1) → C(m))

"কোনো user active থাকলে, অন্তত একটা network link available থাকবে।"

A(u) = "user u active", S(n, x) = "network link n-এর অবস্থা x" ধরলে: ∃u A(u) → ∃n S(n, available)

Lewis Carroll-এর যুক্তি#

Alice in Wonderland-এর লেখক Lewis Carroll একজন গণিতবিদও ছিলেন। তাঁর logic-এর বই থেকে একটা যুক্তি:

1. সব সিংহ হিংস্র।
2. কিছু সিংহ কফি খায় না।
3. কিছু হিংস্র প্রাণী কফি খায় না।

প্রথম দুটো premise, তৃতীয়টা conclusion। Domain = সব প্রাণী, P(x) = "x সিংহ", Q(x) = "x হিংস্র", R(x) = "x কফি খায়":

1. ∀x (P(x) → Q(x))
2. ∃x (P(x) ∧ ¬R(x))
3. ∃x (Q(x) ∧ ¬R(x))

দ্বিতীয় আর তৃতীয়টা ∃x (P(x) → ¬R(x)) এর মতো লিখলে ভুল হতো, ঠিক উপরের Java উদাহরণের কারণে: সিংহ না এমন একটা প্রাণী থাকলেই সেটা true হয়ে যেত।

যুক্তিটা valid: কফি না খাওয়া সেই সিংহটা হিংস্র, তাই অন্তত একটা হিংস্র প্রাণী কফি খায় না। Premise থেকে এভাবে conclusion টানার নিয়মকে বলে rules of inference (Section 1.6)।

Practice#

প্রশ্ন ১. Negation লিখুন, আর বাংলায় বলুন: "ক্লাসের সবাই assignment জমা দিয়েছে।" (domain = ক্লাসের student, A(x) = "x assignment জমা দিয়েছে")

প্রশ্ন ২. Domain = সব মানুষ, S(x) = "x CSE student", P(x) = "x Python জানে"। Logic-এ লিখুন: (ক) "প্রত্যেক CSE student Python জানে।" (খ) "কোনো একজন CSE student Python জানে।" (গ) "কোনো CSE student-ই Python জানে না।"

প্রশ্ন ৩. !orders.some((o) => o.status === "failed") কে quantifier দিয়ে লিখুন, তারপর De Morgan দিয়ে every() তে বদলান।

orders.every((o) => o.status !== "failed");

শেষ কথা#

• Restricted domain আর translation-এ: ∀-এর সাথে →, ∃-এর সাথে ∧।
• Quantifier সব operator-এর আগে বসে। Quantifier বা value ছাড়া variable free, তখন expression proposition না।
• ¬∀x P(x) ≡ ∃x ¬P(x) আর ¬∃x P(x) ≡ ∀x ¬P(x)।
• "সবাই করেনি" আর "কেউই করেনি" আলাদা কথা।
• লেখার আগে domain ঠিক করুন।

বইয়ে এরপর আছে nested quantifier (Section 1.5), যেখানে একসাথে একাধিক quantifier আসে, যেমন "প্রত্যেকের অন্তত একজন বন্ধু আছে", আর rules of inference (Section 1.6)।