Equivalence Proof আর Satisfiability: Truth Table ছাড়া প্রমাণ
· 6 min read · #discrete-math #logic #satisfiability
On this page
Truth table দিয়ে সব equivalence প্রমাণ করা যায়, কিন্তু একটা সমস্যা আছে। n টা variable থাকলে row হয় 2ⁿ টা। 3 variable-এ 8 row ঠিক আছে, কিন্তু 10 variable-এ 1024, আর 30 variable-এ একশো কোটির বেশি (2³⁰ = 1,073,741,824)।
সমাধান হলো গত পর্বের equivalence law গুলো দিয়ে ধাপে ধাপে proof লেখা, ঠিক যেভাবে algebra-য় সূত্র দিয়ে expression সরল করি। এই পর্বে সেটা শিখব, তারপর দেখব satisfiability। (Section 1.3)
Equivalence proof কীভাবে লিখতে হয়
নিয়ম সহজ: বাম পাশের expression থেকে শুরু করে প্রতিটা ধাপে একটা law প্রয়োগ করব, যতক্ষণ না ডান পাশের expression পাই। প্রতিটা ধাপের পাশে লিখে রাখব কোন law use করলাম।
উদাহরণ ১
প্রমাণ করুন: ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q
¬(p ∨ (¬p ∧ q))
≡ ¬p ∧ ¬(¬p ∧ q) De Morgan (দ্বিতীয়)
≡ ¬p ∧ (¬(¬p) ∨ ¬q) De Morgan (প্রথম)
≡ ¬p ∧ (p ∨ ¬q) Double negation
≡ (¬p ∧ p) ∨ (¬p ∧ ¬q) Distributive
≡ F ∨ (¬p ∧ ¬q) Negation (¬p ∧ p ≡ F)
≡ (¬p ∧ ¬q) ∨ F Commutative
≡ ¬p ∧ ¬q Identityপ্রতিটা লাইন আগের লাইনের সমান, তাই প্রথম আর শেষ লাইনও সমান। প্রমাণ শেষ।
উদাহরণ ২: tautology প্রমাণ
প্রমাণ করুন, (p ∧ q) → (p ∨ q) একটা tautology। মানে দেখাতে হবে এটা ≡ T।
(p ∧ q) → (p ∨ q)
≡ ¬(p ∧ q) ∨ (p ∨ q) p → q ≡ ¬p ∨ q
≡ (¬p ∨ ¬q) ∨ (p ∨ q) De Morgan (প্রথম)
≡ (¬p ∨ p) ∨ (¬q ∨ q) Associative + Commutative
≡ T ∨ T Negation
≡ T Dominationসহজ ভাষায়: "p আর q দুটোই true হলে, অন্তত একটা true" কথাটা সবসময় সত্য।
Satisfiability
একটা compound proposition satisfiable, যদি variable গুলোকে অন্তত একটা truth value assignment দেওয়া যায়, যাতে পুরো expression true হয়। কোনো assignment-এই true না হলে সেটা unsatisfiable।
তুলনা করুন: tautology মানে সব assignment-এ true, satisfiable মানে অন্তত একটা assignment-এ true। প্রতিটা tautology satisfiable, কিন্তু উল্টোটা সত্য না।
একটা সুন্দর সম্পর্ক: কোনো proposition unsatisfiable হয় if and only if তার negation একটা tautology। সবসময় false মানে, উল্টে দিলে সবসময় true।
পর্ব ৩-এর requirement consistency check-ও আসলে এটাই: requirement গুলো consistent মানে, সবগুলোর conjunction satisfiable।
তিনটা উদাহরণ
(ক) (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p)
Satisfiable। p, q, r তিনটাকেই T দিলে প্রতিটা bracket true হয়। আসলে প্রতিটা bracket একটা implication: q → p, r → q আর p → r। এরা চক্রাকারে একটা আরেকটাকে টানে, তাই expression true হয় ঠিক তখনই, যখন তিনটার value একই (সব T, অথবা সব F)।
(খ) (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r)
Satisfiable। p = T, q = F দিলেই হয়, r যা-ই হোক। প্রথম bracket চায় অন্তত একটা true, দ্বিতীয়টা চায় অন্তত একটা false। মানে তিনটার value সব এক হওয়া চলবে না।
(গ) (ক) আর (খ) একসাথে: (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) ∧ (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r)
Unsatisfiable। (ক) অংশ চায় তিনটার value সব এক, (খ) অংশ চায় সব এক হওয়া চলবে না। দুটো একসাথে অসম্ভব।
হাতে যাচাই করার পুরো পথটা একটা binary tree: প্রতিটা variable-এর জন্য T বা F বেছে নেওয়া। (ক)-এর ক্ষেত্রে 8 টা leaf-এর মধ্যে মাত্র দুটোতে expression true:
Satisfiability কেন এত গুরুত্বপূর্ণ
Sudoku: প্রতিটা ঘরে কোন সংখ্যা বসবে, সেটাকে variable ধরা যায়। যেমন p(i, j, n) মানে "i-তম row, j-তম column-এর ঘরে n বসেছে"। 9×9 Sudoku-তে এমন variable 9 × 9 × 9 = 729 টা। "প্রতিটা row-তে প্রতিটা সংখ্যা একবার" এর মতো নিয়মগুলো মিলে বিশাল একটা compound proposition হয়, আর তার satisfying assignment-ই puzzle-এর সমাধান।
এমন নিয়ম লিখতে অনেকগুলো disjunction ছোট করে লেখা হয়: p₁ ∨ p₂ ∨ … ∨ pₙ কে লেখা হয় ⋁ pⱼ (j = 1 থেকে n)। যেমন "এই ঘরে 1 থেকে 9-এর কোনো একটা বসবে" হলো n = 1 থেকে 9 পর্যন্ত সব p(i, j, n) এর disjunction।
SAT solver: Satisfiability যাচাই করার বিশেষ program-কে বলে SAT solver। সব ক্ষেত্রে দ্রুত কাজ করে এমন কোনো পদ্ধতি এখনো কেউ জানে না। SAT ছিল প্রথম প্রমাণিত NP-complete problem, আর বিখ্যাত P vs NP প্রশ্ন এর সাথেই জড়িত। তবু আধুনিক solver গুলো বাস্তবের লাখো variable-এর problem-ও প্রায়ই দ্রুত সমাধান করে ফেলে।
এগুলো use হয় chip design যাচাইয়ে, scheduling-এ, আর Linux-এর কিছু package manager-এ (যেমন dnf আর zypper), কোন কোন version-এর package একসাথে install করা যাবে সেটা বের করতে।
Practice
প্রশ্ন ১. Law দিয়ে প্রমাণ করুন: ¬(p → q) ≡ p ∧ ¬q
Answer
¬(p → q)
≡ ¬(¬p ∨ q) p → q ≡ ¬p ∨ q
≡ ¬(¬p) ∧ ¬q De Morgan (দ্বিতীয়)
≡ p ∧ ¬q Double negationপ্রশ্ন ২. (p ∧ (p → q)) → q কি tautology? Law দিয়ে দেখান।
Answer
(p ∧ (p → q)) → q
≡ ¬(p ∧ (p → q)) ∨ q p → q ≡ ¬p ∨ q
≡ ¬(p ∧ (¬p ∨ q)) ∨ q p → q ≡ ¬p ∨ q
≡ ¬((p ∧ ¬p) ∨ (p ∧ q)) ∨ q Distributive
≡ ¬(F ∨ (p ∧ q)) ∨ q Negation
≡ ¬(p ∧ q) ∨ q Commutative + Identity
≡ (¬p ∨ ¬q) ∨ q De Morgan (প্রথম)
≡ ¬p ∨ (¬q ∨ q) Associative
≡ ¬p ∨ T Negation
≡ T Dominationহ্যাঁ, এটা tautology। "p true, আর p হলে q হয়, তাহলে q true": এই যুক্তির নাম modus ponens, পরের অধ্যায়ের rules of inference-এর প্রথম rule।
প্রশ্ন ৩. (p ∨ q) ∧ ¬p ∧ ¬q কি satisfiable?
Answer
না, unsatisfiable। ¬p ∧ ¬q true হতে হলে p = F আর q = F লাগবে, কিন্তু তখন p ∨ q false।
De Morgan দিয়েও দেখা যায়: ¬p ∧ ¬q ≡ ¬(p ∨ q), তাই পুরো expression আসলে x ∧ ¬x আকারের, একটা contradiction।
শেষ কথা
- Variable বেশি হলে truth table অচল, তখন law দিয়ে ধাপে ধাপে proof।
- প্রতিটা ধাপে একটা law, আর পাশে তার নাম।
- Satisfiable মানে অন্তত একটা assignment-এ true, tautology মানে সবগুলোতে।
- কোনো proposition unsatisfiable, যদি আর কেবল যদি তার negation tautology হয়।
- SAT solver দিয়ে Sudoku থেকে package dependency পর্যন্ত সমাধান হয়।
এখানেই propositional logic শেষ। পরের পর্ব থেকে শুরু হবে predicate logic: x + 1 = 2 এর মতো variable-ওয়ালা statement, আর "সবার জন্য" ও "অন্তত একজনের জন্য" বোঝাতে quantifier ∀ আর ∃। (Section 1.4)