कथन तर्क और सत्यता सारणियाँ
उद्देश्य और दायरा
इस पाठ में आप शर्तों को सूत्रों में लिखना, पूरी truth table बनाना, implication और converse में अंतर करना, समतुल्यता जाँचना और तर्क के counterexamples खोजना सीखेंगे। पूर्वज्ञान: सामान्य गणितीय संकेत। यहाँ केवल शास्त्रीय द्विमूल्य propositional logic की नींव है। Predicate logic, quantifiers, normal-form algorithms और proof systems अलग पाठों के विषय हैं; यह संपूर्ण Discrete Mathematics नहीं है।
1. कथन से शुरुआत करें
Proposition ऐसा घोषणात्मक वाक्य है जिसका दी गई स्थिति में निश्चित सत्य मान हो: सत्य (T) या असत्य (F)। “7 अभाज्य है” सत्य proposition है। “8 अभाज्य है” भी proposition है, लेकिन असत्य है। “फ़ाइल खोलो” आदेश है, proposition नहीं। “x सम है” तब तक open predicate है जब तक x का मान न दिया जाए या उसे quantify न किया जाए।
मानें p का अर्थ “टोकन वैध है” और q का अर्थ “प्रवेश मिला है”। इन्हें अमूर्त सत्य मान मानकर काम करते हैं। Logical implication अपने आप कारण, निष्पादन क्रम या प्रोग्राम नहीं बताती। वास्तविक प्रणाली में इन चरों के अलावा अन्य शर्तें भी हो सकती हैं।
Negation ¬p सत्य मान उलटता है। Conjunction p ∧ q में दोनों कथन सत्य होने चाहिए। Disjunction p ∨ q समावेशी है: एक या दोनों सत्य हो सकते हैं। Exclusive OR p ⊕ q में ठीक एक कथन सत्य होता है। कोष्ठक महत्वपूर्ण हैं: ¬(p ∧ q) और (¬p) ∧ q अलग हैं। Precedence के अलग प्रचलनों से बचने के लिए मिले-जुले सूत्रों में कोष्ठक लगाएँ।
2. पूरी सारणी बनाएँ
n अलग variables के 2^n assignments होते हैं; अलग चरों को गिनें, उनके दोहराव को नहीं। दो चरों के लिए क्रम से TT, TF, FT, FF लिखें।
| p | q | ¬p | p ∧ q | p ∨ q | p ⊕ q | p → q | p ↔ q |
|---|---|---|---|---|---|---|---|
| T | T | F | T | T | F | T | T |
| T | F | F | F | T | T | F | F |
| F | T | T | F | T | T | T | F |
| F | F | T | F | F | F | T | T |
p → q का अर्थ “यदि p, तो q” है। यह केवल तब असत्य है जब p सत्य और q असत्य हो; इसका समतुल्य ¬p ∨ q है। Antecedent असत्य होने पर material implication सत्य है, लेकिन इससे q के सत्य होने का प्रमाण नहीं मिलता। Biconditional p ↔ q में दोनों सत्य मान समान होने चाहिए; यह (p → q) ∧ (q → p) के बराबर है।
उपयोगी उदाहरण: “अगर आप फ़ॉर्म जमा करेंगे, तो मैं रसीद भेजूँगा।” फ़ॉर्म जमा होने पर रसीद न भेजना वादा तोड़ता है। फ़ॉर्म जमा ही न हो तो यह सशर्त वादा नहीं टूटा, चाहे रसीद आए या न आए। प्रश्न में औपचारिक सत्य परिभाषा लागू करें, उदाहरण के रोज़मर्रा के कारण-संबंध को नहीं।
3. दिशा और निषेध
p → q का converse q → p, inverse ¬p → ¬q और contrapositive ¬q → ¬p है। केवल contrapositive हमेशा मूल के समतुल्य है। p = F, q = T पर मूल T और converse F है; समतुल्यता गलत सिद्ध करने के लिए एक counterexample पर्याप्त है। मूल और contrapositive दोनों ¬p ∨ q में बदलते हैं।
Implication का निषेध अलग क्रिया है: ¬(p → q) ≡ p ∧ ¬q। यह ठीक वादा टूटने की स्थिति है। “p only if q” को p → q लिखें: q, p के लिए आवश्यक है। “p if q” को q → p लिखें: q, p के लिए पर्याप्त है। “If and only if” में दोनों दिशाएँ चाहिए।
4. हल किया उदाहरण: सरलीकरण और जाँच
F = (p → q) ∧ p लें। Implication हटाने और distributive law लगाने पर
F ≡ (¬p ∨ q) ∧ p ≡ (¬p ∧ p) ∨ (q ∧ p) ≡ p ∧ q।
विरोधाभासी पद ¬p ∧ p असत्य है; असत्य के साथ OR करने पर दूसरा पद बचता है। अलग से जाँचें:
| p | q | p → q | (p → q) ∧ p | p ∧ q |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | F |
| F | T | T | F | F |
| F | F | T | F | F |
अंतिम स्तंभ हर assignment पर समान हैं। केवल एक पंक्ति में समानता से समतुल्यता सिद्ध नहीं होती।
5. सूत्रों का वर्गीकरण
Tautology हर assignment पर सत्य है, जैसे p ∨ ¬p। Contradiction हर assignment पर असत्य है, जैसे p ∧ ¬p। Contingency कुछ पर सत्य और कुछ पर असत्य है, जैसे p → q। Satisfiable का अर्थ कम-से-कम एक assignment पर सत्य होना है; इसलिए tautology और contingency दोनों satisfiable हैं। यहाँ valid formula का अर्थ tautology है, केवल satisfiable होना नहीं।
F और G की समतुल्यता truth table से सिद्ध करने के लिए सभी assignments जाँचें। असमतुल्यता के लिए एक अलग परिणाम वाली पंक्ति पर्याप्त है। दूसरे शब्दों में F ↔ G tautology होना चाहिए। कुछ अनुकूल उदाहरण पूरे प्रमाण का विकल्प नहीं हैं।
6. हल किया उदाहरण: तर्क की वैधता
Premises p → q और q → r से conclusion p → r निकलता है। मानें दोनों premises सत्य हैं। p असत्य हो तो conclusion स्वतः सत्य है। p सत्य हो तो पहली premise से q सत्य और दूसरी से r सत्य होना चाहिए; तब भी conclusion सत्य है। कोई assignment सभी premises को सत्य और conclusion को असत्य नहीं बनाता।
इसके विपरीत, p → q और q से p नहीं निकलता। p = F, q = T चुनें। दोनों premises सत्य हैं, लेकिन p असत्य है। इसे affirming the consequent कहते हैं। Validity यह जाँचती है कि सत्य premises से असत्य conclusion तो नहीं निकलता; इससे वास्तविक दुनिया में premises के सच होने की पुष्टि नहीं होती।
झटपट संदर्भ और सामान्य गलतियाँ
- n अलग variables से 2^n पंक्तियाँ बनती हैं।
- p → q ≡ ¬p ∨ q ≡ ¬q → ¬p।
- ¬(p → q) ≡ p ∧ ¬q।
- De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q।
- ↔ में सत्य मान समान; ⊕ में अलग होते हैं।
- Invalid argument: सभी premises T और conclusion F वाली कम-से-कम एक पंक्ति।
Inclusive OR को “ठीक एक” न पढ़ें। Consequent से antecedent न निकालें और निषेध की जगह inverse न लिखें। विधि अपनाएँ: अलग variables पहचानें, कोष्ठक लगाएँ, सभी assignments लिखें, भीतर के पद पहले निकालें, फिर माँगी गई जाँच करें। किसी premise का असत्य होना conclusion के वास्तविक सत्य मान के बारे में अपने आप कुछ नहीं बताता।
7. तर्क की वैधता जाँचने की विधि
Premises P₁,…,Pₖ और conclusion C के लिए (P₁ ∧ … ∧ Pₖ) → C जाँचें। तर्क तभी valid है जब यह conditional tautology हो। दूसरा तरीका: P₁ ∧ … ∧ Pₖ ∧ ¬C को सत्य करने वाला assignment खोजें। ऐसा एक assignment counterexample है; ऐसा कोई assignment न हो तो तर्क valid है। यह सत्य को सुरक्षित रखने की जाँच है, premises के वास्तविक होने का दावा नहीं।
p→q और ¬q से ¬p निकालना valid है; इसे modus tollens कहते हैं। निष्कर्ष असत्य करने के लिए p=T चाहिए। ¬q सत्य हो तो q=F होगा, लेकिन तब p→q असत्य है। इसलिए दोनों premises सत्य रखते हुए निष्कर्ष असत्य नहीं कर सकते। इसके विपरीत, p→q और ¬p से ¬q नहीं निकलता: p=F, q=T लें। Antecedent को नकारने की इस गलत विधि को modus tollens से न मिलाएँ।
Premises p और ¬p हों तो कोई row दोनों को सत्य नहीं करती। शास्त्रीय तर्क में ऐसे असंगत premises से किसी भी conclusion वाला argument vacuously valid होता है। इसलिए “valid” का अर्थ “premises एक साथ संभव हैं” या “यह वास्तविक दुनिया की उपयोगी व्याख्या है” नहीं है।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।
C01. p=F और q=T पर क्रमशः p→q और q→p के सत्य मान क्या हैं?
A. T, T B. T, F C. F, T D. F, F
उत्तर: B
A: Converse में antecedent सत्य और consequent असत्य है, इसलिए वह असत्य है।
B: p असत्य होने से पहला implication सत्य है; q सत्य और p असत्य होने से converse असत्य है।
C: दोनों मान उलटे हैं; असत्य antecedent से implication असत्य नहीं होता।
D: केवल q→p असत्य है; p→q का antecedent असत्य है।
C02. कौन-सा सूत्र ¬(p→q) के समतुल्य है?
A. ¬p∨q B. ¬p∧q C. p∧¬q D. ¬q→¬p
उत्तर: C
A: यह स्वयं p→q है, उसका निषेध नहीं।
B: यह p असत्य और q सत्य का मामला है, जहाँ implication सत्य है।
C: De Morgan से ¬(¬p∨q)≡p∧¬q; यही implication की अकेली असत्य row है।
D: Contrapositive मूल implication के समतुल्य है, उसके निषेध के नहीं।
C03. (p∨q)∧(p→r) की पूरी truth table में कितनी rows चाहिए?
A. 4 B. 6 C. 16 D. 8
उत्तर: D
A: चार rows दो अलग variables के लिए हैं; यहाँ तीन हैं।
B: Rows सभी combinations गिनती हैं, variables की संख्या का दुगुना नहीं।
C: दोबारा आया p चौथा स्वतंत्र variable नहीं है।
D: अलग variables p,q,r हैं; 2^3=8 assignments चाहिए।
C04. (p→q)∨(q→p) किस प्रकार का सूत्र है?
A. Tautology B. Contradiction C. Contingency D. Unsatisfiable, लेकिन contradiction नहीं
उत्तर: A
A: विस्तार ¬p∨q∨¬q∨p में q∨¬q है, इसलिए हर assignment पर सत्य है।
B: यह कभी असत्य नहीं, इसलिए contradiction नहीं है।
C: Contingency में सत्य और असत्य दोनों rows चाहिए; यहाँ कोई असत्य row नहीं।
D: इस तर्क में unsatisfiable सूत्र contradiction होता है; यहाँ हर row सत्य है।
C05. कौन-सा assignment इस तर्क को गलत सिद्ध करता है: p→q और q, इसलिए p?
A. p=T, q=T B. p=T, q=F C. p=F, q=F D. p=F, q=T
उत्तर: D
A: निष्कर्ष सत्य है, इसलिए इससे validity गलत सिद्ध नहीं होती।
B: q और implication दोनों premises असत्य हैं; counterexample में सभी premises सत्य चाहिए।
C: q असत्य है; invalidity दिखाने के लिए हर premise सत्य होना चाहिए।
D: p→q और q दोनों सत्य हैं, पर निष्कर्ष p असत्य है; यही आवश्यक counterexample है।
C06. p का अर्थ “request स्वीकार होती है” और q का अर्थ “उसका token वैध है” लें। “Request तभी स्वीकार होती है जब उसका token वैध हो” का सूत्र क्या है?
A. q→p B. p→q C. p↔q D. p∧q
उत्तर: B
A: यह token वैध होने को acceptance के लिए पर्याप्त बताता है; ऐसा नहीं कहा गया।
B: Acceptance के लिए validity आवश्यक है, इसलिए p→q।
C: “Only if” से उलटी दिशा नहीं मिलती; biconditional अतिरिक्त शर्त जोड़ता है।
D: Conditional नियम दोनों घटनाओं के वास्तव में होने का दावा नहीं करता।
स्रोत और दायरा
यह आधारभूत पाठ आधिकारिक GATE 2027 CS पाठ्यक्रम के Section 1 में Discrete Mathematics से जुड़ा है। यह पूरे विषय या पूरे पाठ्यक्रम की समाप्ति नहीं है। स्रोत विषय की प्रासंगिकता बताता है; उदाहरण और अभ्यास प्रश्न मौलिक हैं।
Official GATE 2027 CS syllabus (verified 2026-10-14).
प्रगति सहेजने के लिए साइन इन करें। साइन इन