Proposition আর Logical Connective: Discrete Math-এর প্রথম ধাপ
· 5 min read · #discrete-math #logic #proposition
On this page
Programming করতে গিয়ে আমরা প্রতিদিন if, &&, || আর ! লিখি। এগুলোর পেছনের গণিতটাই হলো propositional logic, আর Discrete Mathematics-এর যাত্রা শুরু হয় এখান থেকেই।
এই series-এ Discrete Math-এর chapter গুলো সহজ ভাষায়, উদাহরণসহ লিখব। প্রথম পর্বে দেখব proposition কী, আর কয়েকটা proposition জোড়া লাগানোর জন্য কোন কোন logical connective আছে। (Section 1.1)
Discrete Math কেন?
"Discrete" মানে আলাদা আলাদা, গোনা যায় এমন। Calculus যেখানে continuous জিনিস নিয়ে কাজ করে, Discrete Math সেখানে কাজ করে integer, set, graph আর true/false এর মতো আলাদা আলাদা value নিয়ে।
Computer নিজেই discrete, ভেতরে সবকিছু শেষ পর্যন্ত 0 আর 1। তাই algorithm, database query, circuit, এমনকি একটা সাধারণ if condition ঠিকমতো বুঝতেও এই গণিত কাজে লাগে।
Proposition কী?
Proposition হলো এমন একটা declarative sentence (বিবৃতি), যেটা হয় true, নয়তো false। দুটো একসাথে না, আর মাঝামাঝি কিছুও না।
কয়েকটা proposition:
- ঢাকা বাংলাদেশের রাজধানী। (true)
- টরন্টো কানাডার রাজধানী। (false, রাজধানী Ottawa)
1 + 0 = 1(true)0 + 0 = 2(false)
False হলেও এগুলো proposition, কারণ প্রতিটার একটা নির্দিষ্ট truth value আছে।
এবার কয়েকটা sentence, যেগুলো proposition না:
- বসো! (আদেশ, true বা false বলা যায় না)
- এখন কয়টা বাজে? (প্রশ্ন)
x + 1 = 2(x-এর value না জানলে true বা false বলা যায় না)x + y = z
Propositional variable আর compound proposition
Proposition গুলোকে ছোট করে লিখতে আমরা অক্ষর use করি: p, q, r, s... এদের বলে propositional variable। Programming-এর boolean variable-এর মতোই:
const p = true; // "আজ বৃষ্টি হচ্ছে"
const q = false; // "আমি বাসায় আছি"Truth value দুটো: true কে লিখি T, false কে F। Code আর circuit-এ এরাই 1 আর 0।
একাধিক proposition-কে logical connective দিয়ে জোড়া দিলে পাই compound proposition। প্রধান connective পাঁচটা:
- Negation
¬(NOT) - Conjunction
∧(AND) - Disjunction
∨(OR) - Implication
→(IF... THEN) - Biconditional
↔(IF AND ONLY IF)
এই পর্বে প্রথম তিনটা, সাথে exclusive or ⊕। Implication আর biconditional পরের পর্বে।
একটা connective কেমন আচরণ করে, সেটা পুরোপুরি বোঝা যায় তার truth table দেখে: সম্ভাব্য প্রতিটা input-এর জন্য output কী।
Negation (¬): উল্টে দেওয়া
p যদি একটা proposition হয়, তাহলে ¬p (পড়ি "not p") হলো তার উল্টো। p true হলে ¬p false, আর p false হলে ¬p true।
| p | ¬p |
|---|---|
| T | F |
| F | T |
উদাহরণ: p = "পৃথিবী গোল।" তাহলে ¬p = "পৃথিবী গোল না।"
Code-এ এটাই ! operator:
const isLoggedIn = true;
console.log(!isLoggedIn); // falseConjunction (∧): দুটোই true হতে হবে
p ∧ q (পড়ি "p and q") true হয় শুধু তখন, যখন p আর q দুটোই true।
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
p = "আমি বাসায় আছি", q = "বৃষ্টি হচ্ছে" হলে p ∧ q = "আমি বাসায় আছি এবং বৃষ্টি হচ্ছে।" দুটোর একটা মিথ্যা হলেই পুরো কথাটা মিথ্যা।
Code-এ &&:
const canCheckout = cartHasItems && isLoggedIn;Cart-এ item আছে এবং user logged in, দুটোই না হলে checkout হবে না।
Disjunction (∨): অন্তত একটা true
p ∨ q (পড়ি "p or q") true হয় যখন p আর q-এর অন্তত একটা true। False হয় শুধু তখন, যখন দুটোই false।
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Code-এ ||:
const canEdit = isAdmin || isOwner;Admin হলেও চলবে, owner হলেও চলবে, দুটো হলে তো কথাই নেই।
Inclusive or বনাম exclusive or (⊕)
সাধারণ কথায় "অথবা" শব্দের দুটো মানে হয়:
- Inclusive or: "যারা CSE101 অথবা MAT101 করেছে, তারা এই course নিতে পারবে।" দুটোই করা থাকলেও সমস্যা নেই। এটাই
∨। - Exclusive or: "Set menu-র সাথে soup অথবা salad পাবেন।" এখানে দুটো একসাথে পাওয়া যাবে না, ঠিক একটা। একে বলে exclusive or (XOR), লিখি
p ⊕ q।
p ⊕ q true হয় যখন ঠিক একটা true। দুটোই true হলে false।
| p | q | p ⊕ q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
∨-এর সাথে পার্থক্য শুধু প্রথম row-তে। JavaScript-এ দুটো boolean-এর XOR লেখা যায় !== দিয়ে, আর number-এর bit-এর জন্য আছে ^ operator:
const p = true;
const q = true;
console.log(p || q); // true (inclusive or)
console.log(p !== q); // false (exclusive or)
console.log(1 ^ 1); // 0 (bitwise XOR)চারটা connective এক ছবিতে
Venn diagram-এ প্রতিটা বৃত্ত মানে "সেই proposition true", আর shaded অংশ মানে যেখানে পুরো expression true:
Practice
প্রশ্ন ১. নিচের কোনগুলো proposition? Proposition হলে তার truth value কী?
- (ক) পদ্মা বাংলাদেশের একটা নদী।
- (খ) দরজাটা বন্ধ করো।
- (গ)
2 + 3 = 6 - (ঘ)
x > 5
Answer
(ক) proposition, true। (খ) proposition না, এটা আদেশ। (গ) proposition, false। (ঘ) proposition না, কারণ x-এর value জানা নেই।
প্রশ্ন ২. p = "আমি পরীক্ষায় পাস করেছি", q = "আমি খুশি"। বাংলায় লিখুন: p ∧ ¬q আর ¬p ∨ q।
Answer
p ∧ ¬q: "আমি পরীক্ষায় পাস করেছি, কিন্তু আমি খুশি না।" (Logic-এ "কিন্তু" মানেও and।)
¬p ∨ q: "আমি পরীক্ষায় পাস করিনি, অথবা আমি খুশি।"
প্রশ্ন ৩. p = T আর q = F হলে p ∨ q, p ∧ q, p ⊕ q আর ¬p ∨ q এর value কী?
Answer
p ∨ q = T, p ∧ q = F, p ⊕ q = T, আর ¬p ∨ q = F ∨ F = F।
শেষ কথা
- Proposition হলো এমন বিবৃতি, যা হয় true নয়তো false।
¬উল্টে দেয়,∧চায় দুটোই true,∨চায় অন্তত একটা true।⊕(XOR) চায় ঠিক একটা true।- Code-এর
!,&&,||আর boolean-এর!==আসলে এই connective গুলোই।
পরের পর্বে দেখব সবচেয়ে মজার, আবার সবচেয়ে বেশি confusing connective: implication p → q।