Tautology, Contradiction আর Logical Equivalence
· 6 min read · #discrete-math #logic #de-morgan
On this page
একই কথা নানাভাবে বলা যায়। "বৃষ্টি হলে আমি যাব না" আর "আমি গেলে বুঝবে বৃষ্টি হয়নি" আসলে একই কথা। Logic-এ এই "একই কথা" ব্যাপারটাকে বলে logical equivalence। এই পর্বে সেটা আর তার সাথে জড়িত কয়েকটা সংজ্ঞা দেখব। (Section 1.3)
Tautology, contradiction, contingency
Compound proposition-কে তিন ভাগে ভাগ করা যায়:
- Tautology: variable-এর value যা-ই হোক, সবসময় true। যেমন
p ∨ ¬p("হয় বৃষ্টি হচ্ছে, নয়তো হচ্ছে না")। - Contradiction: সবসময় false। যেমন
p ∧ ¬p("বৃষ্টি হচ্ছে, আবার হচ্ছেও না")। - Contingency: কখনো true, কখনো false। যেমন শুধু
p, বাp → q।
| p | ¬p | p ∨ ¬p | p ∧ ¬p |
|---|---|---|---|
| T | F | T | F |
| F | T | T | F |
p ∨ ¬p কলামের পুরোটা T, আর p ∧ ¬p কলামের পুরোটা F।
Code-এ tautology বা contradiction মানে সাধারণত একটা bug, অথবা অপ্রয়োজনীয় check:
if (isOpen || !isOpen) {
// সবসময় চলবে, condition টা অর্থহীন
}
if (isOpen && !isOpen) {
// কখনো চলবে না, dead code
}Logical equivalence
দুটো compound proposition p আর q logically equivalent, যদি p ↔ q একটা tautology হয়। মানে, সব input-এ দুটোর truth value একই। লিখি p ≡ q (কোথাও p ⇔ q)।
উদাহরণ: ¬a ∨ b আর a → b কি equivalent? Truth table বানাই:
| a | b | ¬a | ¬a ∨ b | a → b |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
শেষ দুই কলাম হুবহু এক, তাই a → b ≡ ¬a ∨ b। গত পর্বে code-এ implication লিখেছিলাম !p || q দিয়ে, এই হলো তার প্রমাণ।
De Morgan's laws
Augustus De Morgan-এর নামে দুটো law, logic-এ এদের ব্যবহার সবচেয়ে বেশি:
¬(p ∧ q) ≡ ¬p ∨ ¬q¬(p ∨ q) ≡ ¬p ∧ ¬q
মনে রাখার উপায়: negation bracket-এর ভেতরে ঢুকলে ∧ হয়ে যায় ∨, আর ∨ হয়ে যায় ∧।
দ্বিতীয় law-এর truth table:
| p | q | p ∨ q | ¬(p ∨ q) | ¬p | ¬q | ¬p ∧ ¬q |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
ছবিতে দেখলে আরও পরিষ্কার। প্রতিটা বৃত্ত মানে সেই proposition true, আর shaded অংশ মানে যেখানে expression true:
সাধারণ কথায়: "চা অথবা কফি, কোনোটাই খাই না" মানে "চা খাই না, এবং কফিও খাই না"।
Code-এ De Morgan
Condition-এর শুরুতে ! আর লম্বা bracket থাকলে পড়তে কষ্ট হয়। De Morgan দিয়ে সহজ করা যায়:
// আগে
if (!(user.isAdmin || user.isOwner)) {
showError("Permission নেই");
}
// পরে: একই logic, পড়তে সহজ
if (!user.isAdmin && !user.isOwner) {
showError("Permission নেই");
}উল্টোটাও কাজে লাগে: !a || !b দেখলে বুঝবেন এটা আসলে !(a && b), মানে "a আর b দুটো একসাথে true না"।
গুরুত্বপূর্ণ equivalence গুলো
এগুলো algebra-র সূত্রের মতো, পরের পর্বে এগুলো দিয়েই truth table ছাড়া proof লিখব। এখানে T মানে এমন proposition যা সবসময় true, আর F মানে সবসময় false।
- Identity:
p ∧ T ≡ p,p ∨ F ≡ p - Domination:
p ∨ T ≡ T,p ∧ F ≡ F - Idempotent:
p ∨ p ≡ p,p ∧ p ≡ p - Double negation:
¬(¬p) ≡ p - Commutative:
p ∨ q ≡ q ∨ p,p ∧ q ≡ q ∧ p - Associative:
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r),(p ∧ q) ∧ r ≡ p ∧ (q ∧ r) - Distributive:
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r),p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) - De Morgan:
¬(p ∧ q) ≡ ¬p ∨ ¬q,¬(p ∨ q) ≡ ¬p ∧ ¬q - Absorption:
p ∨ (p ∧ q) ≡ p,p ∧ (p ∨ q) ≡ p - Negation:
p ∨ ¬p ≡ T,p ∧ ¬p ≡ F
Code-এ কয়েকটা দেখতে এমন (সব variable boolean ধরে):
isAdmin || (isAdmin && isActive); // absorption: শুধু isAdmin
!!isVisible; // double negation: isVisible
flag && true; // identity: flagConditional আর biconditional-এর equivalence
Implication নিয়ে কাজ করতে এগুলো লাগে:
p → q ≡ ¬p ∨ qp → q ≡ ¬q → ¬p(contrapositive)p ∨ q ≡ ¬p → qp ∧ q ≡ ¬(p → ¬q)¬(p → q) ≡ p ∧ ¬q(p → q) ∧ (p → r) ≡ p → (q ∧ r)(p → r) ∧ (q → r) ≡ (p ∨ q) → r(p → q) ∨ (p → r) ≡ p → (q ∨ r)(p → r) ∨ (q → r) ≡ (p ∧ q) → rp ↔ q ≡ (p → q) ∧ (q → p)p ↔ q ≡ ¬p ↔ ¬qp ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)¬(p ↔ q) ≡ p ↔ ¬q
¬(p → q) ≡ p ∧ ¬q টা বিশেষভাবে মনে রাখুন। "A+ পেলে সাইকেল পাবে" কথাটা মিথ্যা হওয়া মানে "A+ পেয়েছ, কিন্তু সাইকেল পাওনি"।
Practice
প্রশ্ন ১. (p ∧ q) → p কি tautology, contradiction, নাকি contingency?
Answer
Tautology। p ∧ q true হলে p অবশ্যই true, তাই implication কখনো "true → false" হয় না। Truth table-এর চারটা row-তেই T আসে।
প্রশ্ন ২. De Morgan দিয়ে negation ভেতরে নিন: ¬(isWeekend ∨ isHoliday)
Answer
¬isWeekend ∧ ¬isHoliday। Code-এ: !isWeekend && !isHoliday, মানে "আজ weekend না, এবং ছুটির দিনও না"।
প্রশ্ন ৩. "যদি bug থাকে, তাহলে test fail করবে" কথাটার negation লিখুন।
Answer
¬(p → q) ≡ p ∧ ¬q, তাই negation হলো: "bug আছে, কিন্তু test fail করেনি।"
"bug না থাকলে test fail করবে না" লিখলে ভুল হবে, ওটা negation না, inverse।
শেষ কথা
- Tautology সবসময় true, contradiction সবসময় false, contingency দুটোই হতে পারে।
p ≡ qমানে সব input-এ দুটোর value একই, অর্থাৎp ↔ qএকটা tautology।- De Morgan: negation ভেতরে ঢুকলে
∧আর∨জায়গা বদলায়। - Equivalence law গুলো দিয়ে expression ছোট করা যায়, code-এর condition-ও।
পরের পর্বে: truth table ছাড়াই এই law গুলো দিয়ে equivalence প্রমাণ, আর satisfiability।