Skip to content
All posts
Discrete Math

Predicate আর Quantifier: ∀ আর ∃ দিয়ে “সবাই” আর “অন্তত একজন”

· 6 min read · #discrete-math #logic #quantifier

On this page

এখন পর্যন্ত আমরা p, q এর মতো একটা অক্ষর দিয়ে পুরো একটা বাক্য ধরেছি। কিন্তু এই দুটো কথা দেখুন:

  • সব মানুষ মরণশীল।
  • সক্রেটিস একজন মানুষ।

এখান থেকে পরিষ্কার বোঝা যায় "সক্রেটিস মরণশীল"। অথচ propositional logic দিয়ে এটা দেখানো যায় না। p = "সব মানুষ মরণশীল" আর q = "সক্রেটিস একজন মানুষ" ধরলে, দুটো বাক্যের ভেতরের "মানুষ" শব্দের মিলটাই হারিয়ে যায়।

আমাদের দরকার এমন একটা ভাষা, যেটা object, তাদের property আর তাদের মধ্যকার relation নিয়ে কথা বলতে পারে। সেটাই predicate logic। (Section 1.4)

Predicate আর propositional function

"x, 3-এর চেয়ে বড়" বাক্যটায় দুটো অংশ:

  • x হলো variable (যাকে নিয়ে কথা হচ্ছে)
  • "3-এর চেয়ে বড়" হলো predicate, মানে x সম্পর্কে যে property বলা হচ্ছে

Predicate-কে P ধরলে বাক্যটা লিখি P(x)। একে বলে propositional function।

P(x) নিজে proposition না, কারণ x-এর value না জানলে true/false বলা যায় না। (পর্ব ১-এর x + 1 = 2 মনে আছে?) কিন্তু x-এর জায়গায় একটা value বসালেই এটা proposition হয়ে যায়:

  • P(4) = "4, 3-এর চেয়ে বড়": true
  • P(2) = "2, 3-এর চেয়ে বড়": false

Programming-এ এটা আসলে একটা function, যেটা boolean ফেরত দেয়। JavaScript-এ filter-এর callback-কে এজন্যই predicate বলা হয়:

predicate.js
const P = (x) => x > 3;
 
P(4); // true
P(2); // false
 
[1, 5, 2, 8].filter(P); // [5, 8]

x কোন কোন value নিতে পারবে, সেই set-কে বলে domain (বা universe of discourse), সংক্ষেপে U।

একাধিক variable

Predicate-এ একাধিক variable থাকতে পারে। ধরি R(x, y, z) মানে x + y = z, আর domain হলো integer:

  • R(3, 4, 7): 3 + 4 = 7, তাই true
  • R(2, -1, 5): 2 + (-1) = 1, 5 না, তাই false
  • R(x, 3, z): x আর z এখনো খালি, তাই proposition না

Connective এখানেও চলে

Propositional logic-এর সব connective predicate-এর সাথেও চলে। P(x) মানে x > 0 হলে:

  • P(3) ∨ P(-1) = T ∨ F = T
  • P(3) ∧ P(-1) = T ∧ F = F
  • P(3) → P(-1) = T → F = F
  • P(3) → ¬P(-1) = T → T = T

তবে P(3) ∧ P(y) বা P(x) → P(y) এর মতো expression-এ খালি variable থাকায় এগুলো proposition না।

Precondition আর postcondition

Program ঠিকমতো কাজ করছে কিনা, সেটা প্রমাণ করতেও predicate লাগে।

  • Precondition: valid input কেমন হবে, তার শর্ত
  • Postcondition: program চলার পর output কোন শর্ত মানবে

উদাহরণ: দুটো variable-এর value অদলবদল (swap) করার program:

swap.js
let temp = x;
x = y;
y = temp;
  • Precondition P(x, y): "x = a এবং y = b"
  • Postcondition Q(x, y): "x = b এবং y = a"

শুরুতে precondition সত্য ধরে ধাপে ধাপে যাচাই করি:

  1. temp = x এর পর: x = a, temp = a, y = b
  2. x = y এর পর: x = b, temp = a, y = b
  3. y = temp এর পর: x = b, temp = a, y = a

শেষে "x = b এবং y = a", মানে postcondition সত্য। তাই যেকোনো valid input-এ program ঠিক কাজ করে।

Quantifier

Variable-এ value না বসিয়েও propositional function-কে proposition বানানো যায়: বলে দিতে হয় predicate টা কতগুলো value-এর জন্য সত্য। এই "কতগুলো" বোঝানোর চিহ্নকে বলে quantifier। প্রধান দুটো:

  • Universal quantifier ∀: "সবার জন্য" (for all)
  • Existential quantifier ∃: "অন্তত একটার জন্য" (there exists)

মনে রাখার সহজ উপায়: ∀ হলো উল্টানো A (All), আর ∃ হলো উল্টো দিকে ফেরানো E (Exists)।

Universal quantifier (∀)

∀x P(x) পড়ি "সব x-এর জন্য P(x)"। এটা true, যদি domain-এর প্রতিটা x-এর জন্য P(x) true হয়। একটাও false হলে পুরোটা false।

  • P(x): x > 0, U = সব integer: ∀x P(x) false (যেমন x = -5)
  • P(x): x > 0, U = positive integer: ∀x P(x) true
  • P(x): "x জোড়", U = সব integer: ∀x P(x) false (যেমন x = 3)

খেয়াল করুন, প্রথম দুটোতে predicate একই, কিন্তু domain বদলানোয় উত্তর বদলে গেছে। তাই quantifier-এর সাথে domain বলে দেওয়া জরুরি।

∀x P(x) false দেখাতে একটা উদাহরণই যথেষ্ট, যেখানে P(x) false। এমন উদাহরণকে বলে counterexample।

Existential quantifier (∃)

∃x P(x) পড়ি "এমন একটা x আছে, যার জন্য P(x)"। এটা true, যদি domain-এ অন্তত একটা x-এর জন্য P(x) true হয়।

  • P(x): x > 0, U = সব integer: ∃x P(x) true (যেমন x = 1)
  • P(x): "x ঋণাত্মক", U = positive integer: ∃x P(x) false
  • P(x): "x জোড়", U = সব integer: ∃x P(x) true

Uniqueness quantifier (∃!)

∃!x P(x) মানে "ঠিক একটা x আছে, যার জন্য P(x) true"। একটার বেশিও না, কমও না।

  • P(x): x + 1 = 0, U = integer: ∃!x P(x) true (শুধু x = -1)
  • P(x): x > 0, U = integer: ∃!x P(x) false (1, 2, 3... অনেকগুলো)

Quantifier মানে আসলে একটা loop

Domain finite হলে quantifier-কে loop হিসেবে ভাবা যায়। JavaScript-এ এর জন্য তৈরি method-ই আছে:

  • ∀x P(x) হলো every(): সব element ঘুরে দেখে। একটা false পেলেই থামে, উত্তর false।
  • ∃x P(x) হলো some(): একটা true পেলেই থামে, উত্তর true। শেষ পর্যন্ত না পেলে false।
quantifier.js
const U = [1, 2, 3, 4, 5];
const P = (x) => x < 4;
 
U.every(P); // false, 4-এ এসে থামে
U.some(P); // true, 1-এই থামে

U = 1 থেকে 5 আর P(x) = x ছোট 4-এর চেয়ে: every() চতুর্থ element-এ থেমে false দেয়, some() প্রথমটাতেই থেমে true দেয়

Domain যদি শুধু 1, 2 আর 3 হয়, তাহলে quantifier আসলে বড় একটা ∧ বা ∨:

  • ∀x P(x) ≡ P(1) ∧ P(2) ∧ P(3)
  • ∃x P(x) ≡ P(1) ∨ P(2) ∨ P(3)

Domain infinite হলেও এভাবে ভাবা যায়, শুধু loop সবসময় শেষ হবে না।

Practice

প্রশ্ন ১. Q(x, y, z) মানে x - y = z, domain integer। নিচেরগুলোর truth value কী? Q(2, -1, 3), Q(3, 4, 7), Q(x, 3, z)

Answer

Q(2, -1, 3): 2 - (-1) = 3, তাই true। Q(3, 4, 7): 3 - 4 = -1, তাই false। Q(x, 3, z): x আর z খালি, তাই proposition না।

প্রশ্ন ২. Domain = সব real number। নিচেরগুলোর truth value কী? (ক) ∀x (x² ≥ 0) (খ) ∃x (x² = -1) (গ) ∃!x (x² = 4)

Answer

(ক) true, যেকোনো real number-এর square শূন্য বা তার বেশি। (খ) false, কোনো real number-এর square ঋণাত্মক না। (গ) false, কারণ x = 2 আর x = -2 দুটোই কাজ করে, "ঠিক একটা" না।

প্রশ্ন ৩. const nums = [2, 4, 7, 10]; হলে nums.every((n) => n % 2 === 0) আর nums.some((n) => n > 9) কী দেবে? Quantifier দিয়ে লিখুন।

Answer

প্রথমটা "সব n জোড়", মানে ∀। 7-এ এসে false পায়, তাই false। দ্বিতীয়টা "এমন n আছে যা 9-এর বড়", মানে ∃। 10 পেয়ে true।

শেষ কথা

  • Predicate হলো variable সম্পর্কে একটা property। P(x) নিজে proposition না, value বসালে বা quantifier দিলে হয়।
  • ∀x P(x) true যখন domain-এর সবার জন্য true। একটা counterexample-ই এটাকে false করে দেয়।
  • ∃x P(x) true যখন অন্তত একজনের জন্য true। ∃! মানে ঠিক একজন।
  • একই predicate, ভিন্ন domain, ভিন্ন উত্তর। তাই domain সবসময় বলে দিন।
  • Code-এ every() হলো ∀, আর some() হলো ∃।

পরের পর্বে দেখব quantifier-এর negation (De Morgan আবার!), আর সাধারণ বাক্যকে predicate logic-এ লেখার নিয়ম, যেখানে সবচেয়ে বেশি ভুল হয়।

More in Discrete Math