Propositional Logic-এর ব্যবহার: Translation, Specification, Puzzle আর Circuit
· 6 min read · #discrete-math #logic #logic-circuit
On this page
গত দুই পর্বে connective আর truth table শিখেছি। এবার প্রশ্ন: এগুলো দিয়ে করব কী? এই পর্বে পাঁচটা বাস্তব ব্যবহার দেখব। (Section 1.2)
১. বাক্য থেকে logic
সাধারণ ভাষা অনেক সময় অস্পষ্ট। Logic-এ লিখলে মানে একদম নির্দিষ্ট হয়ে যায়। ধাপ তিনটা:
- Identify: বাক্যের ছোট ছোট atomic proposition খুঁজে বের করা
- Represent: প্রতিটাকে একটা variable দেওয়া
- Determine: ঠিক connective বসানো
উদাহরণ: "যদি আমি নানুবাড়ি অথবা গ্রামে যাই, তাহলে আমি shopping-এ যাব না।"
- p: আমি নানুবাড়ি যাই
- q: আমি গ্রামে যাই
- r: আমি shopping-এ যাব
"যদি p অথবা q, তাহলে r না", মানে (p ∨ q) → ¬r।
আরেকটা, একটু কঠিন: "Campus থেকে internet use করতে পারবে only if তুমি CSE-র student অথবা তুমি first year-এর না।"
- a: তুমি campus থেকে internet use করতে পারবে
- c: তুমি CSE-র student
- f: তুমি first year-এর student
"only if" মানে implication (গত পর্ব মনে আছে?), তাই: a → (c ∨ ¬f)
২. System specification
Software engineer-রা client-এর requirement সাধারণ ভাষায় পান, তারপর সেটাকে নির্দিষ্ট করতে logic-এ লেখেন।
"File system full থাকলে automated reply পাঠানো যাবে না।"
p = automated reply পাঠানো যায়, q = file system full। তাহলে: q → ¬p
Requirement গুলো consistent তো?
অনেকগুলো requirement একসাথে থাকলে দেখতে হয় এরা পরস্পরবিরোধী কিনা। কিছু proposition-এর list consistent, যদি variable গুলোকে এমনভাবে truth value দেওয়া যায় যাতে সবগুলো একসাথে true হয়।
উদাহরণ, একটা system-এর তিনটা requirement:
- Diagnostic message buffer-এ store হবে, অথবা retransmit হবে।
- Diagnostic message buffer-এ store হবে না।
- যদি message buffer-এ store হয়, তাহলে retransmit হবে।
p = message buffer-এ store হয়, q = message retransmit হয়। তাহলে requirement গুলো: p ∨ q, ¬p আর p → q।
| p | q | p ∨ q | ¬p | p → q |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | T | F | F |
| F | T | T | T | T |
| F | F | F | T | T |
তৃতীয় row-তে (p = F, q = T) তিনটাই true। তাই requirement গুলো consistent: message buffer-এ রাখা হবে না, retransmit করা হবে।
এবার চতুর্থ একটা requirement যোগ করি: "Diagnostic message retransmit হবে না।" মানে ¬q।
| p | q | p ∨ q | ¬p | p → q | ¬q |
|---|---|---|---|---|---|
| T | T | T | F | T | F |
| T | F | T | F | F | T |
| F | T | T | T | T | F |
| F | F | F | T | T | T |
এখন কোনো row-তেই চারটা একসাথে true না। যে একমাত্র row-তে প্রথম তিনটা true ছিল, সেখানে ¬q false হয়ে গেছে। তাই এই specification inconsistent, এমন system বানানোই সম্ভব না।
৩. Boolean search
Search engine বা library database-এ খোঁজার সময় আমরা আসলে connective use করি। তাই এগুলোকে বলে Boolean search:
- AND: দুটো শব্দই থাকতে হবে
- OR: যেকোনো একটা থাকলেই চলবে
- NOT: এই শব্দ থাকা চলবে না
যেমন (kacchi OR biryani) AND dhaka NOT tehari মানে ঢাকার kacchi বা biryani নিয়ে page, কিন্তু যেখানে tehari-র কথা আছে সেগুলো বাদ।
Google-এ AND লিখতে হয় না, space দিলেই AND ধরে। OR সরাসরি লেখা যায়, আর NOT-এর জন্য শব্দের আগে - দিতে হয়: dhaka biryani -tehari।
৪. Logic puzzle: knights আর knaves
Raymond Smullyan-এর বিখ্যাত puzzle: একটা দ্বীপে দুই ধরনের মানুষ থাকে। Knight সবসময় সত্য বলে, knave সবসময় মিথ্যা বলে।
দ্বীপে আপনার দেখা হলো A আর B-এর সাথে:
- A বলল: "B একজন knight।"
- B বলল: "আমরা দুজন বিপরীত ধরনের।"
কে কী?
p = A knight, q = B knight। তাহলে ¬p = A knave, ¬q = B knave।
ধরি A knight (p true): knight সত্য বলে, তাই B-ও knight (q true)। কিন্তু তাহলে B-র কথা "আমরা বিপরীত" মিথ্যা হয়ে যায়, অথচ knight মিথ্যা বলতে পারে না। বিরোধ। তাই A knight না।
তাহলে A knave (¬p true): A মিথ্যা বলছে, তাই B knight না, B-ও knave (¬q)। এবার B-র কথা যাচাই করি: দুজনেই knave, তাই "আমরা বিপরীত" কথাটা মিথ্যা, আর knave মিথ্যাই বলে। সব মিলে গেল।
উত্তর: A আর B দুজনেই knave।
চারটা সম্ভাবনা একসাথে table-এ দেখা যায়। প্রতিটা row-তে লেখা আছে দুজনের কথা আসলে true নাকি false। Knight-এর কথা true হতে হবে, knave-এর কথা false:
| A | B | A-র কথা | B-র কথা | সম্ভব? |
|---|---|---|---|---|
| Knight | Knight | T | F | না |
| Knight | Knave | F | T | না |
| Knave | Knight | T | T | না |
| Knave | Knave | F | F | হ্যাঁ |
নিজে চেষ্টা করুন: কাদা মাখা দুই শিশু
একজন বাবা তাঁর ছেলে আর মেয়েকে backyard-এ খেলতে বললেন, কিন্তু গায়ে কাদা লাগানো যাবে না। খেলতে গিয়ে দুজনের কপালেই কাদা লেগে গেল। প্রত্যেকে অন্যজনের কপাল দেখতে পায়, নিজেরটা না।
বাবা বললেন: "তোমাদের অন্তত একজনের কপালে কাদা আছে।" তারপর জিজ্ঞেস করলেন: "তুমি কি জানো তোমার কপালে কাদা আছে কিনা?" দুজন একসাথে, সৎভাবে উত্তর দেবে। বাবা প্রশ্নটা দুইবার করলেন। প্রতিবার ওরা কী বলবে?
Answer
প্রথমবার দুজনেই বলবে "না"। প্রত্যেকে অন্যজনের কপালে কাদা দেখছে, তাই বাবার কথা ("অন্তত একজনের") অন্যজনকে দেখেই সত্য হয়ে যায়। নিজের কপাল নিয়ে কিছু জানা যায় না।
দ্বিতীয়বার দুজনেই বলবে "হ্যাঁ"। মেয়েটা ভাবে: "আমার কপাল যদি পরিষ্কার হতো, তাহলে ভাই প্রথমবারেই বুঝে যেত যে কাদা ওর কপালেই, আর 'হ্যাঁ' বলত। কিন্তু ও 'না' বলেছে। তাই আমার কপালেও কাদা আছে।" ছেলেটাও একই যুক্তি দেয়।
৫. Logic circuit
Computer-এর circuit-এ প্রতিটা signal হয় 1 (true) নয়তো 0 (false)। জটিল circuit বানানো হয় তিনটা মৌলিক gate দিয়ে:
- NOT gate (inverter): একটা input নেয়, উল্টে দেয়:
¬p - AND gate: দুটো input-এর conjunction:
p ∧ q - OR gate: দুটো input-এর disjunction:
p ∨ q
এগুলো জোড়া দিয়ে যেকোনো expression-এর circuit বানানো যায়। নিচের circuit-টা (p ∧ ¬q) ∨ ¬r হিসাব করে:
ধাপে ধাপে: q-কে NOT gate দিয়ে ¬q বানানো হলো, তারপর p-এর সাথে AND করে p ∧ ¬q। অন্যদিকে r থেকে NOT দিয়ে ¬r। শেষে দুটোকে OR করে output।
p = 1, q = 0, r = 1 হলে: ¬q = 1, p ∧ ¬q = 1, ¬r = 0, আর output = 1 ∨ 0 = 1।
Gate আর circuit নিয়ে বিস্তারিত আছে বইয়ের Chapter 12-এ।
Practice
প্রশ্ন ১. "তুমি roller coaster-এ চড়তে পারবে না, যদি তোমার উচ্চতা 4 feet-এর কম হয়, যদি না তোমার বয়স 16-র বেশি হয়।" q = তুমি roller coaster-এ চড়তে পারবে, r = উচ্চতা 4 feet-এর কম, s = বয়স 16-র বেশি। Logic-এ লিখুন।
Answer
(r ∧ ¬s) → ¬q। মানে: উচ্চতা 4 feet-এর কম এবং বয়স 16-র বেশি না হলে, চড়তে পারবে না।
প্রশ্ন ২. এই তিনটা requirement কি consistent? p → q, q → r, p ∧ ¬r
Answer
না। p ∧ ¬r true হতে হলে p = T আর r = F লাগবে। তখন p → q এর জন্য q = T হতে হবে, আর q → r এর জন্য r = T হতে হবে। কিন্তু r = F আগেই ধরে নিয়েছি। তাই কোনো assignment-এ তিনটা একসাথে true হয় না, specification inconsistent।
প্রশ্ন ৩. উপরের circuit-এ p = 0, q = 1, r = 0 হলে output কত?
Answer
¬q = 0, তাই p ∧ ¬q = 0। ¬r = 1। Output = 0 ∨ 1 = 1।
শেষ কথা
- বাক্যকে logic-এ নিতে: proposition খুঁজুন, variable দিন, connective বসান।
- Requirement consistent মানে এমন একটা assignment আছে, যাতে সব একসাথে true।
- Search engine-এর AND, OR, NOT আসলে
∧,∨,¬। - Puzzle-এ প্রতিটা সম্ভাবনা ধরে বিরোধ খুঁজলেই উত্তর মেলে।
- NOT, AND, OR gate দিয়ে যেকোনো logic expression-এর circuit বানানো যায়।
পরের পর্বে: tautology, contradiction আর logical equivalence, যেখানে De Morgan-এর law দিয়ে code-এর condition ছোট করাও শিখব।