Algebra of Proposition: Laws, Identities, and Simplifications | प्रपोजिशन का बीजगणित: नियम, पहचाने और सरलीकरण


प्रपोजिशन का बीजगणित: नियम, पहचानें और सरलीकरण

प्रपोजिशनल बीजगणित (Algebra of Propositions) या प्रपोजिशनल लॉजिक का गणितीय पक्ष वह सेट नियम, पहचानें और तरीक़े प्रदान करता है जिनसे जटिल तार्किक अभिव्यक्तियों को सरल किया जा सकता है। यह डिजिटल सर्किट डिज़ाइन, सत्यापन, क्वेरी ऑप्टिमाइज़ेशन और आर्टिफिशियल इंटेलिजेंस में सीधे लागू होता है। इस लेख में हम बारीकी से उन सभी मूलभूत नियमों, पहचान (identities), सामान्य रूप (canonical forms) और व्यावहारिक सरलीकरण उदाहरणों का उल्लेख करेंगे — और साथ में सत्यतालिकाओं (truth tables) व कदम-दर-कदम सरलीकरण दिखाएँगे ताकि आप किसी भी प्रपोजिशनल अभिव्यक्ति को बेहतर तरीके से समझ और बदल सकें।

1. परिचय और मूल बातें

एक प्रपोजिशन (proposition) वह वाक्य है जिसका सत्यमान (True/False) निश्चित रूप से जाना जा सके। प्रपोजिशनल बीजगणित में हम निम्नलिखित मूल ऑपरेशनों का प्रयोग करते हैं:

  • निगेशन (Negation) — ¬P: P का विरोध।
  • संयोजन/और (Conjunction) — P ∧ Q: तभी सत्य जब दोनों P और Q सत्य हों।
  • विलयन/या (Disjunction) — P ∨ Q: तभी सत्य जब कम से कम एक सत्य हो।
  • प्रभुता/निष्कर्ष (Implication) — P → Q: तभी असत्य जब P सत्य और Q असत्य हो।
  • द्वि-परस्पर (Biconditional) — P ↔ Q: तभी सत्य जब P और Q दोनों का सत्यमान समान हो।

2. प्रमुख लॉज़ (Logical Laws) और पहचानें (Identities)

निम्न नियम और पहचानें बार-बार प्रयुक्त होती हैं — इन्हें याद रखना और व्यावहारिक उदाहरणों में लागू करना उपयोगी है:

  • Idempotent: P ∨ P = P ; P ∧ 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)
  • Identity: P ∨ F = P ; P ∧ T = P
  • Domination: P ∨ T = T ; P ∧ F = F
  • Double Negation: ¬(¬P) = P
  • De Morgan’s Laws: ¬(P ∧ Q) = ¬P ∨ ¬Q ; ¬(P ∨ Q) = ¬P ∧ ¬Q
  • Implication equivalence: (P → Q) ≡ (¬P ∨ Q)
  • Biconditional breakdown: (P ↔ Q) ≡ (P → Q) ∧ (Q → P) ≡ (P ∧ Q) ∨ (¬P ∧ ¬Q)

3. सत्य तालिकाओं से सत्यापन (Verification by Truth Tables)

किसी भी पहचान या रूपांतरण की सत्यता दिखाने का सबसे सीधा तरीका है सत्य तालिका (truth table) बनाना। उदाहरण के लिए De Morgan के पहले नियम के लिए:

PQP ∧ Q¬(P ∧ Q)¬P ∨ ¬Q
TTTFF
TFFTT
FTFTT
FFFTT

ऊपर की तालिका दिखाती है कि ¬(P ∧ Q) और ¬P ∨ ¬Q हर पंक्ति पर समान हैं — अतः वे तुल्य हैं (equivalent)।

4. सामान्य रूप: CNF और DNF (Canonical Forms)

लॉजिक इंजीनियरिंग और SAT-solvers में अभिव्यक्तियों को सामान्य रूपों में बदलना आवश्यक होता है:

  • Disjunctive Normal Form (DNF): OR का संयोजन जहाँ प्रत्येक घटक एक AND-clause है — उदाहरण: (P ∧ Q) ∨ (¬P ∧ R)
  • Conjunctive Normal Form (CNF): AND का संयोजन जहाँ प्रत्येक घटक एक OR-clause है — उदाहरण: (P ∨ ¬Q) ∧ (¬P ∨ R)

किसी भी प्रपोजिशनल सूत्र को क्रमशः CNF या DNF में बदला जा सकता है — अक्सर मध्यवर्ती कदमों में De Morgan और distributive नियम उपयोगी होते हैं।

5. स्टेप-बाय-स्टेप सरलीकरण उदाहरण (Step-by-step Simplifications)

उदाहरण 1:

S = (P ∧ Q) ∨ (P ∧ ¬Q)

चरण 1: बाहर P को factor करें (Distributive का उल्टा): S = P ∧ (Q ∨ ¬Q)

चरण 2: Q ∨ ¬Q = T (tautology), अतः S = P ∧ T = P

निष्कर्ष: मूल अभिव्यक्ति P के बराबर है।

उदाहरण 2 (Implication से सरलीकरण):

S = (P → Q) ∧ P

चरण 1: P → Q को (¬P ∨ Q) से बदलें → S = (¬P ∨ Q) ∧ P

चरण 2: वितरण करें: S = (¬P ∧ P) ∨ (Q ∧ P)

परन्तु ¬P ∧ P = F, अतः S = P ∧ Q

6. निष्कर्ष निकालने के नियम (Inference Rules) — व्यावहारिक उपयोग

  • Modus Ponens: P → Q, P ⊢ Q
  • Modus Tollens: P → Q, ¬Q ⊢ ¬P
  • Hypothetical Syllogism: P → Q, Q → R ⊢ P → R
  • Disjunction Introduction: P ⊢ P ∨ Q
  • Conjunction Introduction: P, Q ⊢ P ∧ Q

ये नियम प्रूफ़ और तर्कशक्ति (automated theorem proving) के लिए आधार हैं।

7. डिजिटल सर्किट व अनुप्रयोग (Digital Circuits and Applications)

Boolean अभिव्यक्तियों को Gate-level पर map करके सर्किट डिज़ाइन किया जाता है। उदाहरण —

  • F = A ∧ B ∨ ¬A ∧ C को AND और OR व NOT गेट्स से बनाया जा सकता है।
  • सरलीकरण से गेट-काउंट घटता है — लागत और लेटेंसी घटती है।

8. समस्याएँ और टिप्स (Common Pitfalls & Tips)

  • निगेशन को सही ढंग से प्रसारित करें (De Morgan का सही प्रयोग करें)।
  • Implication को हमेशा ¬P ∨ Q में बदलकर काम करें — इससे तालिकाओं और सरलीकरण में आसानी होती है।
  • CNF में बदलते समय distributive explosion से बचने के लिए चरणबद्ध रूपांतरण करें।

9. उपयोगी अभ्यास (Exercises)

  1. सरलीकृत रूप खोजें: (P ∨ Q) ∧ (P ∨ ¬Q)
  2. CNF में बदलें: ¬(P ∧ (Q ∨ R))
  3. सत्य तालिका बनाकर दिखाएँ: (P → Q) ≡ (¬P ∨ Q)

10. सारांश (Summary)

प्रपोजिशन का बीजगणित उन सभी नियमों और तरीकों का समूह है जो जटिल तार्किक अभिव्यक्तियों को व्यवस्थित, प्रमाणित और सरल बनाते हैं। De Morgan, distributive, associative, commutative तथा अन्य पहचानें न केवल सैद्धान्तिक रूप से महत्वपूर्ण हैं बल्कि व्यावहारिक सर्किट डिज़ाइन, क्वेरी ऑप्टिमाइज़ेशन और तर्कप्रमाण में भी अनिवार्य हैं।

अगला कदम: इन्हीं नियमों का प्रयोग कर आप दूसरे विषयों — जैसे Predicate Logic और SAT/SMT solving — में अधिक प्रभावी बन सकते हैं।

Related Post