Propositional Logic — সত্য-মিথ্যার বীজগণিত
Propositional Logic
Proposition, connective আর truth table — যে ভাষায় একটা `if` statement, একটা SQL WHERE clause আর CPU-র ভেতরের একটা AND gate সবাই একই জিনিস।
আগে এটা বুঝি
আপনি হাজারবার এটা লিখেছেন:
if (user != NULL && user->is_active && !user->is_banned) {
grant_access();
}কিন্তু কখনো ভেবেছেন — এই লাইনটা আসলে কী? এটা একটা গাণিতিক বাক্য।
&& মানে conjunction, ! মানে negation, আর পুরোটা মিলে একটা
proposition — এমন একটা দাবি যা হয় সত্য, নয় মিথ্যা।
এখন আসল প্রশ্ন: এই শর্তটা কি ঠিক? Attacker কি এমন কোনো অবস্থা বানাতে পারবে
যেখানে grant_access() চলে যাওয়ার কথা না, তবু চলে যায়?
এই প্রশ্নের উত্তর “চালিয়ে দেখি” দিয়ে দেওয়া যায় না। এর উত্তর দিতে হলে আপনাকে সব সম্ভাব্য combination বিবেচনা করতে হবে। তিনটা variable মানে আটটা combination — সেগুলো সাজিয়ে ফেলার নাম truth table।
আর এটাই propositional logic: সত্য-মিথ্যা নিয়ে হিসাব করার নিয়মতান্ত্রিক পদ্ধতি।
মূল ধারণা
Proposition কী
Proposition হলো এমন একটা declarative বাক্য যার একটা নির্দিষ্ট সত্যমান আছে — হয় true, নয় false। দুটোই একসাথে না, কোনোটাই না — এমনও না।
| বাক্য | Proposition? | কেন |
|---|---|---|
| “২ + ২ = ৪” | ✅ হ্যাঁ (T) | নির্দিষ্টভাবে সত্য |
| “২ + ২ = ৫” | ✅ হ্যাঁ (F) | নির্দিষ্টভাবে মিথ্যা |
| “ঢাকা বাংলাদেশের রাজধানী” | ✅ হ্যাঁ (T) | যাচাইযোগ্য |
| “দরজাটা বন্ধ করো” | ❌ না | আদেশ, দাবি নয় |
| “এখন কয়টা বাজে?” | ❌ না | প্রশ্ন |
“x > 5” | ❌ না (এখনো) | x-এর মান না জানলে সত্যমান নেই |
| “এই বাক্যটা মিথ্যা” | ❌ না | স্ববিরোধী (liar paradox) |
শেষ দুটো গুরুত্বপূর্ণ।
x > 5 কে বলে predicate — variable-সহ একটা টেমপ্লেট। x-এ একটা
নির্দিষ্ট মান বসালে সেটা proposition হয়ে যায়। Predicate নিয়ে আমরা
আলাদা লেসনে কাজ করব।
আর liar paradox দেখায় যে সব ভাষার বাক্যকে সত্য/মিথ্যা বলা যায় না — এই ফাটলটাই পরে Gödel-এর incompleteness theorem আর halting problem-এ গিয়ে বিস্ফোরিত হবে (Level 13)।
পাঁচটা connective
ছোট proposition জোড়া লাগিয়ে বড় proposition বানানোর operator-গুলোকে বলে logical connective।
| নাম | চিহ্ন | কোডে | পড়ে | সত্য কখন |
|---|---|---|---|---|
| Negation | ¬p | !p | “p নয়” | p মিথ্যা হলে |
| Conjunction | p ∧ q | p && q | “p এবং q” | দুটোই সত্য হলে |
| Disjunction | p ∨ q | p || q | “p অথবা q” | অন্তত একটা সত্য হলে |
| Implication | p → q | — | “p হলে q” | p সত্য অথচ q মিথ্যা — কেবল এই ক্ষেত্রেই মিথ্যা |
| Biconditional | p ↔ q | p == q | “p যদি এবং কেবল যদি q” | দুটোর মান এক হলে |
এই পাঁচটার truth table:
| p | q | ¬p | p ∧ q | p ∨ q | p → q | p ↔ q |
|---|---|---|---|---|---|---|
| F | F | T | F | F | T | T |
| F | T | T | F | T | T | F |
| T | F | F | F | T | F | F |
| T | T | F | T | T | T | T |
চারটা connective স্বাভাবিক মনে হয়। পঞ্চমটা — implication — প্রায় সবাইকে প্রথমবার ধাক্কা দেয়। সেটা নিয়ে আলাদা করে কথা বলি।
Implication কেন এমন অদ্ভুত
p → q-এর truth table-এর প্রথম দুই সারিতে p মিথ্যা, তবু পুরোটা সত্য।
কেন?
একটা প্রতিশ্রুতি ভাবুন:
“পরীক্ষায় A+ পেলে তোমাকে ফোন কিনে দেব।”
কখন বলবেন আমি মিথ্যা বলেছি?
| A+ পেয়েছে (p) | ফোন দিয়েছি (q) | আমি মিথ্যাবাদী? |
|---|---|---|
| না | না | না — শর্তই তো পূরণ হয়নি |
| না | হ্যাঁ | না — বাড়তি দিয়েছি, প্রতিশ্রুতি ভাঙিনি |
| হ্যাঁ | না | হ্যাঁ — এটাই একমাত্র বিশ্বাসঘাতকতা |
| হ্যাঁ | হ্যাঁ | না — কথা রেখেছি |
ঠিক এটাই p → q-এর table। প্রতিশ্রুতি ভাঙে কেবল যখন শর্ত পূরণ হয়েছে
অথচ প্রতিশ্রুত জিনিস দেওয়া হয়নি।
শর্তই যদি পূরণ না হয়, তাহলে প্রতিশ্রুতির কোনো পরীক্ষাই হলো না — তাই সেটা “ভাঙা হয়নি”, অর্থাৎ সত্য। একে বলে vacuous truth।
ভেতরে কী ঘটছে
Precedence — কে আগে বাঁধে
গণিতে যেমন 2 + 3 × 4 মানে 2 + (3 × 4), logic-এও তেমন precedence আছে:
সবচেয়ে শক্ত ¬ (negation)
∧ (and)
∨ (or)
→ (implies)
সবচেয়ে ঢিলা ↔ (iff)তাই:
¬p ∨ q ∧ r → sআসলে মানে:
((¬p) ∨ (q ∧ r)) → sএবং implication right-associative: p → q → r মানে p → (q → r),
(p → q) → r নয়। এই দুটো আলাদা জিনিস — নিজে truth table বানিয়ে দেখুন।
Truth table কীভাবে বানাবেন
নিয়মটা যান্ত্রিক:
nটা variable থাকলে2^nটা row বানান- Variable column-গুলো এমনভাবে ভরুন যাতে সব combination আসে — সবচেয়ে সহজ উপায়: প্রতিটা row-কে একটা binary সংখ্যা ভাবুন (
0থেকে2^n − 1) - ভেতরের ছোট sub-expression-গুলোর জন্য মধ্যবর্তী column বানান
- শেষে পুরো expression-এর column
উদাহরণ: (p ∧ ¬q) → r
| # | p | q | r | ¬q | p ∧ ¬q | (p ∧ ¬q) → r |
|---|---|---|---|---|---|---|
| 0 | F | F | F | T | F | T |
| 1 | F | F | T | T | F | T |
| 2 | F | T | F | F | F | T |
| 3 | F | T | T | F | F | T |
| 4 | T | F | F | T | T | F |
| 5 | T | F | T | T | T | T |
| 6 | T | T | F | F | F | T |
| 7 | T | T | T | F | F | T |
আটটা row-এর মধ্যে মাত্র একটাতে (row 4) পুরো expression মিথ্যা।
খেয়াল করুন row-এর নম্বরটাই binary-তে p q r-এর মান: row 4 = 100 =
p সত্য, q মিথ্যা, r মিথ্যা। এই সম্পর্কটা Level 1-এ binary শেখার সময়
আবার ফিরে আসবে।
এই logic-টা hardware-এ কোথায়
এখানেই propositional logic শুধু গণিত থাকে না।
- if (a && b)C source — আপনি যা লেখেন
- test / and / jzcompiler এটাকে machine instruction-এ ভাঙে
- ALU-র AND unitCPU-র ভেতরে একটা নির্দিষ্ট circuit
- AND gate arrayপ্রতি bit-এর জন্য একটা gate
- দুইটা transistor সিরিজেCMOS-এ AND = NAND + NOT
- Electron প্রবাহদুই gate-ই খোলা থাকলেই কারেন্ট যায়
আপনি যে ∧ লিখছেন খাতায়, CPU সেটা করছে দুইটা transistor সিরিজে বসিয়ে —
দুটোই “on” হলে তবেই কারেন্ট পার হয়। গণিতটাই hardware, hardware-টাই গণিত।
Level 2-এ আমরা এই gate-গুলো নিজে বানাব। আপাতত নিচে খেলে দেখুন — এটা সেই একই truth table, কিন্তু circuit হিসেবে:
Half Adder
| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
টেবিলের যেকোনো row-তে ক্লিক করলে circuit সেই input-এ চলে যাবে।
Half adder দুইটা bit যোগ করে। খেয়াল করুন — Sum আসলে XOR, Carry আসলে AND। অর্থাৎ “যোগ করা” জিনিসটা propositional logic ছাড়া আর কিছুই না।
উদাহরণ
শুরুর কোডটায় ফিরে যাই
if (user != NULL && user->is_active && !user->is_banned) {
grant_access();
}ধরি:
n= “user pointer NULL নয়”a= “user active”b= “user banned”
শর্তটা হলো: n ∧ a ∧ ¬b
| n | a | b | n ∧ a ∧ ¬b | access? |
|---|---|---|---|---|
| F | F | F | F | না |
| F | F | T | F | না |
| F | T | F | F | না |
| F | T | T | F | না |
| T | F | F | F | না |
| T | F | T | F | না |
| T | T | F | T | হ্যাঁ |
| T | T | T | F | না |
আটটা ক্ষেত্রের মধ্যে ঠিক একটাতে access দেওয়া হচ্ছে — সেটা ঠিক সেই ক্ষেত্র যেটা আমরা চেয়েছিলাম। শর্তটা সঠিক। এটা এখন আর অনুমান নয়, যাচাই করা।
এবার একটা ভুল শর্ত
ধরুন কেউ লিখল:
if (user != NULL && user->is_active || !user->is_banned) {
grant_access(); // ⚠ bug
}&&-এর precedence ||-এর চেয়ে বেশি, তাই এটা আসলে:
(n ∧ a) ∨ ¬b| n | a | b | n ∧ a | ¬b | (n ∧ a) ∨ ¬b |
|---|---|---|---|---|---|
| F | F | F | F | T | T ⚠ |
| F | F | T | F | F | F |
| F | T | F | F | T | T ⚠ |
| F | T | T | F | F | F |
| T | F | F | F | T | T ⚠ |
| T | F | T | F | F | F |
| T | T | F | T | T | T |
| T | T | T | T | F | T ⚠ |
চারটা row-তে access দেওয়া হচ্ছে যেখানে দেওয়ার কথা না। সবচেয়ে ভয়ানকটা
প্রথম row: user NULL, তবু access granted — কারণ NULL user “banned”
নয়। পরের লাইনেই user->something করলে segfault, আর তার আগে হয়তো
কোনো privileged কাজ হয়ে গেছে।
নিজে চালিয়ে দেখুন
Short-circuit evaluation নিজে ধরুন
def loud(name, value):
print(f" → {name} evaluate হলো")
return value
print("Case 1: False and ...")
r = loud("A", False) and loud("B", True)
print("result:", r)
print("\nCase 2: True or ...")
r = loud("A", True) or loud("B", False)
print("result:", r)
print("\nCase 3: True and ...")
r = loud("A", True) and loud("B", False)
print("result:", r)চালানোর আগে নিজে লিখে রাখুন কোন কোন লাইন ছাপা হবে। তারপর চালান।
Output:
Case 1: False and ...
→ A evaluate হলো
result: False
Case 2: True or ...
→ A evaluate হলো
result: True
Case 3: True and ...
→ A evaluate হলো
→ B evaluate হলো
result: FalseCase 1 আর 2-এ B কখনো চলেইনি। কারণ:
F ∧ ?— table দেখুন, প্রথম column F হলে ফল সবসময় F। ডান পাশ দেখার দরকার নেই।T ∨ ?— প্রথমটা T হলে ফল সবসময় T।
এবার এই বহুল ব্যবহৃত pattern-টা দেখুন:
if user is not None and user.is_active:
...user যদি None হয়, user.is_active কখনো চলবে না — তাই
AttributeError হবে না। এই নিরাপত্তাটা পুরোপুরি short-circuit-এর উপর
দাঁড়ানো। ক্রম উল্টে দিলে crash।
C-তে একই জিনিস, কিন্তু bitwise & আর | short-circuit করে না:
// নিরাপদ — short circuits
if (p != NULL && p->x > 0) { ... }
// অনিরাপদ — & সবসময় দুই পাশই evaluate করে → NULL deref
if (p != NULL & p->x > 0) { ... }`&&` আর `||` শুধু logical operator না — এরা control flow-ও। ডান পাশ কখনো চলবে কি না সেটা বাঁ পাশের মানের উপর নির্ভর করে। এটা না জানলে side-effect-যুক্ত কোডে অদৃশ্য bug তৈরি হয়।
SQL-এ logic তিন-মানের
SELECT
NULL = NULL AS "NULL = NULL",
NULL IS NULL AS "NULL IS NULL",
TRUE OR NULL AS "T or NULL",
FALSE OR NULL AS "F or NULL",
TRUE AND NULL AS "T and NULL",
FALSE AND NULL AS "F and NULL";ফলাফল:
NULL = NULL | NULL IS NULL | T or NULL | F or NULL | T and NULL | F and NULL
-------------+--------------+-----------+-----------+------------+------------
[null] | t | t | [null] | [null] | fলক্ষ্য করুন NULL = NULL সত্যও নয়, মিথ্যাও নয় — NULL। কারণ SQL-এ
NULL মানে “মান জানি না”। দুইটা অজানা মান সমান কি না — সেটাও অজানা।
কিন্তু TRUE OR NULL = TRUE, কারণ বাঁ পাশ সত্য হলে ডান পাশ যাই হোক ফল সত্য।
আর FALSE AND NULL = FALSE, একই কারণে।
যেখানে এটা কামড়ায়:
-- ভুল: NULL status-ওয়ালা row কখনো আসবে না
SELECT * FROM orders WHERE status != 'shipped';
-- ঠিক
SELECT * FROM orders WHERE status IS DISTINCT FROM 'shipped';WHERE clause শুধু TRUE row রাখে। NULL row বাদ পড়ে যায় নীরবে —
কোনো error নেই, শুধু কম row। Level 8-এ database-এ এটা বিস্তারিত দেখব।
সব জায়গায় logic দুই-মানের নয়। SQL-এ NULL মানে 'অজানা', আর অজানা নিয়ে হিসাব করতে তিন-মানের logic লাগে। এটা না জানলে WHERE clause নীরবে ভুল ফল দেয়।
নিজে বানান
Truth Table Evaluator — ৩০ লাইনে
- একটা expression string আর variable-এর তালিকা নিন
- itertools.product দিয়ে 2^n টা assignment বানান
- প্রতিটা assignment-এ expression evaluate করুন
- ছেপে দিন, আর tautology/contradiction/contingency বলুন
শুরুতে Python-এর নিজের eval ব্যবহার করছি — parser নিজে লেখাটা
Truth Table Generator প্রজেক্টে করবেন।
from itertools import product
def truth_table(expr, variables):
"""expr: Python boolean expression string, e.g. '(p and not q) or r'"""
header = variables + [expr]
widths = [max(len(h), 5) for h in header]
print(" | ".join(h.ljust(w) for h, w in zip(header, widths)))
print("-+-".join("-" * w for w in widths))
results = []
for combo in product([False, True], repeat=len(variables)):
env = dict(zip(variables, combo))
value = eval(expr, {"__builtins__": {}}, env)
results.append(value)
row = [("T" if v else "F") for v in combo] + [("T" if value else "F")]
print(" | ".join(c.ljust(w) for c, w in zip(row, widths)))
if all(results):
verdict = "TAUTOLOGY — সব ক্ষেত্রেই সত্য"
elif not any(results):
verdict = "CONTRADICTION — কোনো ক্ষেত্রেই সত্য নয়"
else:
verdict = f"CONTINGENCY — {sum(results)}/{len(results)} ক্ষেত্রে সত্য"
print("\n" + verdict)
return results
truth_table("p or not p", ["p"])
truth_table("(p and q) or (not p)", ["p", "q"])
truth_table("(not p) or q", ["p", "q"]) # এটাই p → qনিজে যোগ করুন:
implies(p, q)helper —(not p) or q- দুইটা expression একই কি না বলার function (দুটোর result list মিলিয়ে দেখুন)
xor—p != q- এই তিনটা tautology কি না যাচাই করুন:
(p → q) ↔ (¬q → ¬p)— contrapositive¬(p ∧ q) ↔ (¬p ∨ ¬q)— De Morgan((p → q) ∧ (q → r)) → (p → r)— hypothetical syllogism
বাস্তব সিস্টেমে
এই logic বাস্তবে কোথায় চলছে
Compiler optimization. GCC/LLVM আপনার লেখা শর্তকে logically equivalent
কিন্তু দ্রুততর রূপে বদলে দেয়। if (!(a || b)) কে if (!a && !b) বানানো —
এটা De Morgan’s law, যেটা পরের লেসনে দেখব। Compiler প্রতিদিন লক্ষ লক্ষবার
এই বীজগণিত করে।
Database query planner. PostgreSQL আপনার WHERE clause-কে CNF-এ
রূপান্তর করে, তারপর দেখে কোন অংশটা index দিয়ে সমাধান করা যায়।
WHERE (a = 1 AND b = 2) OR (a = 1 AND c = 3) কে WHERE a = 1 AND (b = 2 OR c = 3)
বানালে a-এর index ব্যবহার করা যায়।
Static analysis আর verification. Clang analyzer, Infer, বা Coverity যখন বলে “this branch is always false”, সেটা propositional reasoning। Formal verification tool (TLA+, Dafny) পুরো proof-টা automated করে।
SAT solver. “এই boolean formula সত্য করা যায় এমন কোনো assignment আছে
কি?” — এই প্রশ্নটাই SAT, প্রথম প্রমাণিত NP-complete সমস্যা (Level 13)।
আর তবু আধুনিক SAT solver লক্ষ variable-এর formula মিনিটে সমাধান করে।
এগুলো ব্যবহার হয় hardware verification-এ (Intel প্রতিটা chip design
verify করে SAT দিয়ে), package dependency resolution-এ (apt, cargo,
npm এর ভেতরে SAT solver আছে), আর program analysis-এ।
Access control. AWS IAM policy, Kubernetes RBAC, firewall rule — সবই মূলত বড় boolean expression। “এই request কি অনুমোদিত?” প্রশ্নের উত্তর একটা truth table evaluation।
Digital circuit. সবচেয়ে সরাসরি প্রয়োগ — Level 2-তে দেখব যে একটা CPU আক্ষরিক অর্থেই কোটি কোটি gate দিয়ে বানানো boolean function।
যে ভুলগুলো সবাই করে
“`p → q` মানে p, q-এর কারণ (cause)।”
না। Implication কার্যকারণ (causation) নিয়ে কিছু বলে না, শুধু সত্যমানের সম্পর্ক নিয়ে বলে।
“যদি ২ + ২ = ৫ হয়, তাহলে চাঁদ পনিরের তৈরি” — এটা সত্য implication, কারণ শর্তটা মিথ্যা। এখানে কোনো কার্যকারণ নেই, তবু logically সত্য।
গণিতে এটা কাজে লাগে: n জোড় হলে n² জোড় — এই দাবি প্রমাণ করতে বিজোড়
n-এর ক্ষেত্রে কিছু বলার দরকার নেই, কারণ সেখানে implication এমনিতেই সত্য।
“`∨` মানে 'হয় এটা নয় ওটা' — দুটো একসাথে নয়।”
প্রাত্যহিক বাংলায় “চা নেবেন নাকি কফি?” মানে সাধারণত একটা। কিন্তু logic-এ
∨ হলো inclusive or — দুটোই সত্য হলেও ফল সত্য।
“হয় এটা নয় ওটা, দুটো নয়” — সেটা XOR (⊕), আলাদা operator:
p ⊕ q ≡ (p ∨ q) ∧ ¬(p ∧ q)।
কোডে || inclusive, আর != (boolean-এ) exclusive।
“Truth table বানানো একটা academic ব্যায়াম, বাস্তবে কেউ করে না।”
হাতে ৩২-row table বানানো বাস্তবে করে না — কিন্তু যন্ত্র করে, অবিরাম।
প্রতিটা compiler optimization pass, প্রতিটা query planner, প্রতিটা static analyzer, প্রতিটা model checker — সবাই এই কাজটাই করছে, শুধু আরো চতুর algorithm দিয়ে (BDD, DPLL, CDCL)।
আপনার হাতে করার উদ্দেশ্য হলো যন্ত্রটা কী করছে সেটা বোঝা — আর যখন সেটা অপ্রত্যাশিত কিছু করে, তখন কেন করছে সেটা ধরতে পারা।
“`&&` আর `&` একই জিনিস, একটা শুধু ছোট লেখা।”
সম্পূর্ণ আলাদা।
&& হলো logical AND — short-circuit করে, ফল boolean।
& হলো bitwise AND — দুই পাশই evaluate করে, প্রতিটা bit আলাদাভাবে AND করে।
5 && 3 // → 1 (দুটোই non-zero, তাই true)
5 & 3 // → 1 (0101 & 0011 = 0001) — কাকতালীয়ভাবে একই!
4 && 1 // → 1
4 & 1 // → 0 (0100 & 0001 = 0000) — এখানে পার্থক্য স্পষ্টLevel 1-এ bitwise operation বিস্তারিত দেখব।
বুঝেছেন কি না দেখুন
1p → q আর q → p কি একই জিনিস? না হলে, p → q-এর সাথে কোনটা সমান?
যুক্তি
p → q আর q → p কি একই জিনিস? না হলে, p → q-এর সাথে কোনটা সমান?না, একই নয়। q → p কে বলে converse, আর সেটা আলাদা:
| p | q | p → q | q → p |
|---|---|---|---|
| F | F | T | T |
| F | T | T | F |
| T | F | F | T |
| T | T | T | T |
মাঝের দুই row-তে মান আলাদা।
p → q-এর সাথে সমান হলো contrapositive: ¬q → ¬p।
| p | q | p → q | ¬q → ¬p |
|---|---|---|---|
| F | F | T | T |
| F | T | T | T |
| T | F | F | F |
| T | T | T | T |
চারটা row-তেই মিলে গেছে — এরা logically equivalent।
কেন এটা গুরুত্বপূর্ণ: “বৃষ্টি হলে রাস্তা ভেজা” সত্য হলে, “রাস্তা শুকনো থাকলে বৃষ্টি হয়নি”-ও সত্য। কিন্তু “রাস্তা ভেজা থাকলে বৃষ্টি হয়েছে” — এটা নয় (কেউ পানি ঢালতে পারে)।
Converse আর implication গুলিয়ে ফেলা মানুষের সবচেয়ে সাধারণ যৌক্তিক ভুল।
2এই দুইটা কি সমান? !(a && b) আর !a && !b — truth table দিয়ে যাচাই করুন।
সমান না হলে, !(a && b)-এর সঠিক রূপ কী?
প্রয়োগ
!(a && b) আর !a && !b — truth table দিয়ে যাচাই করুন।
সমান না হলে, !(a && b)-এর সঠিক রূপ কী?সমান নয়।
| a | b | a ∧ b | ¬(a ∧ b) | ¬a ∧ ¬b | ¬a ∨ ¬b |
|---|---|---|---|---|---|
| F | F | F | T | T | T |
| F | T | F | T | F | T |
| T | F | F | T | F | T |
| T | T | T | F | F | F |
¬(a ∧ b) আর ¬a ∧ ¬b মাঝের দুই row-তে আলাদা।
সঠিক রূপ: ¬(a ∧ b) ≡ ¬a ∨ ¬b — AND ভাঙলে OR হয়।
এটাই De Morgan’s law, পরের লেসনের মূল বিষয়। কোডে:
if (!(is_admin && is_verified)) // ঠিক
if (!is_admin && !is_verified) // ভুল — সম্পূর্ণ ভিন্ন শর্ত
if (!is_admin || !is_verified) // ঠিক, De Morgan প্রয়োগ করেদ্বিতীয় লাইনটা লিখলে verified non-admin এবং unverified admin — দুই দলই ভুলভাবে পার পেয়ে যাবে।
3কেন all([]) সত্য কিন্তু any([]) মিথ্যা? এটার সাথে vacuous truth-এর
সম্পর্ক কী?
যুক্তি
all([]) সত্য কিন্তু any([]) মিথ্যা? এটার সাথে vacuous truth-এর
সম্পর্ক কী?all(L) মানে “L-এর প্রতিটা element সত্য” — অর্থাৎ “এমন কোনো element নেই
যেটা মিথ্যা”। খালি list-এ মিথ্যা element নেই, তাই দাবিটা সত্য।
এটাই vacuous truth।
any(L) মানে “L-এ অন্তত একটা সত্য element আছে”। খালি list-এ কোনো element-ই
নেই, তাই সত্য element-ও নেই। মিথ্যা।
আরেকভাবে দেখুন — identity element হিসেবে:
allহলো পরপর AND:T ∧ x₁ ∧ x₂ ∧ …। AND-এর identity হলো T (কারণT ∧ x = x)। খালি হলে identity-টাই থাকে → T।anyহলো পরপর OR:F ∨ x₁ ∨ x₂ ∨ …। OR-এর identity হলো F। খালি হলে → F।
ঠিক যেমন sum([]) == 0 (যোগের identity) আর math.prod([]) == 1
(গুণের identity)। একই গাণিতিক নীতি।
4একটা login system-এ শর্ত: “account active হতে হবে এবং (password ঠিক
হতে হবে অথবা valid recovery token থাকতে হবে), কিন্তু account locked
থাকলে কোনোভাবেই ঢোকা যাবে না।”
এটাকে propositional formula-য় লিখুন এবং truth table বানিয়ে যাচাই করুন
locked account সত্যিই সব ক্ষেত্রে আটকে যাচ্ছে কি না।
ডিজাইন
Variable: A = active, P = password ঠিক, R = valid recovery token, L = locked।
Formula: A ∧ (P ∨ R) ∧ ¬L
Truth table-এ ১৬টা row। কিন্তু পুরোটা না বানিয়েও যাচাই করা যায় — এটাই logical reasoning-এর শক্তি:
L = T হলে ¬L = F। আর x ∧ F = F সবসময়। তাই পুরো expression F,
A, P, R যাই হোক। আটটা locked row-এর সবগুলোতেই access denied। ✓
বাকি আটটা row (L = F) -এ expression হয়ে যায় A ∧ (P ∨ R):
| A | P | R | P ∨ R | A ∧ (P ∨ R) |
|---|---|---|---|---|
| F | F | F | F | F |
| F | F | T | T | F |
| F | T | F | T | F |
| F | T | T | T | F |
| T | F | F | F | F |
| T | F | T | T | T |
| T | T | F | T | T |
| T | T | T | T | T |
Active account তিনভাবে ঢুকতে পারে — password দিয়ে, token দিয়ে, বা দুটোই। Inactive কখনো না। ঠিক যা চেয়েছিলাম।
Design-এর দিক থেকে গুরুত্বপূর্ণ: ¬L কে আলাদা রেখে ∧ দিয়ে জোড়া
দেওয়ায় এটা একটা kill switch হয়ে গেছে — বাকি logic যত জটিলই হোক,
locked মানে locked। এই pattern-টা security design-এ খুব দরকারি: fail-safe
শর্তগুলো সবচেয়ে বাইরের ∧-এ রাখুন।
5n টা variable-এর জন্য কতগুলো ভিন্ন truth table (অর্থাৎ কতগুলো ভিন্ন
boolean function) সম্ভব? n = 2-এর জন্য সংখ্যাটা বের করুন।
প্রয়োগ
n টা variable-এর জন্য কতগুলো ভিন্ন truth table (অর্থাৎ কতগুলো ভিন্ন
boolean function) সম্ভব? n = 2-এর জন্য সংখ্যাটা বের করুন।n টা variable মানে 2^n টা row। প্রতিটা row-এর output হয় T নয় F —
দুইটা পছন্দ। Row-গুলো স্বাধীন, তাই মোট:
n = 2-এর জন্য: 2^(2²) = 2⁴ = ১৬টা ভিন্ন boolean function।
সেই ১৬টার মধ্যে পরিচিত নামওয়ালা কয়েকটা: AND, OR, XOR, NAND, NOR, XNOR,
implication, converse implication, দুইটা projection (p, q), দুইটা
negation (¬p, ¬q), constant TRUE, constant FALSE, আর দুইটা inhibition।
n = 3-এ সংখ্যাটা 2⁸ = ২৫৬। n = 4-এ 2¹⁶ = ৬৫,৫৩৬। n = 5-এ
৪২৯ কোটির বেশি। এই বিস্ফোরক বৃদ্ধিই কারণ যে truth table দিয়ে সব সমস্যা
সমাধান করা যায় না — আর কেন SAT solver-এর মতো চতুর algorithm লাগে।
একটা চমৎকার সত্য: এই সব function — সবগুলো — শুধু NAND gate দিয়ে বানানো যায়। Level 2-এ সেটা নিজে হাতে করব।
এরপর কী
এই লেসনে আমরা truth table বানাতে শিখলাম। কিন্তু ৫টা variable মানে ৩২ row, ১০টা মানে ১০২৪ — হাতে করা অসম্ভব।
তাই পরের লেসনে আমরা শিখব logical equivalence — truth table না বানিয়ে বীজগণিতের নিয়ম দিয়ে expression সরল করা। De Morgan’s law, distribution, absorption। এগুলো ঠিক সেই নিয়ম যা দিয়ে compiler আপনার শর্ত optimize করে, আর যা দিয়ে Level 2-এ আমরা circuit-এর gate সংখ্যা কমাব।
তারপর আসবে predicate logic — কারণ x > 5 কে proposition বানাতে
“সব x-এর জন্য” বা “কোনো একটা x আছে যার জন্য” বলার ভাষা লাগে। সেই ভাষা
ছাড়া কোনো algorithm-এর correctness লেখাই যায় না।
আরও পড়ুন
- Mathematics for Computer Science, Chapter 1–3 — Lehman, Leighton, Meyer
- Discrete Mathematics and Its Applications, Chapter 1 — Kenneth Rosen · Truth table আর logical equivalence-এর জন্য সবচেয়ে বিস্তারিত reference