प्रथम-क्रम तर्क: domain और quantifiers
उद्देश्य और पूर्वज्ञान
Domain और scope के साथ quantified statement पढ़ना, “हर,” “कोई” और “ठीक एक” को सूत्र में लिखना, quantifiers का निषेध करना और उनके क्रम का प्रभाव समझना सीखें। पूर्वज्ञान: कथन तर्क वाले पाठ से proposition, implication, conjunction और negation। यह प्रथम-क्रम तर्क का आधारभूत पाठ है; proof systems, resolution, formal semantics या GATE के सभी logic प्रश्नों का पूरा उपचार नहीं।
हम शास्त्रीय द्विमूल्य तर्क, सामान्य equality और स्पष्ट गैर-रिक्त domain लेते हैं। बड़े universe के भीतर कोई सीमित श्रेणी, जैसे सभी लोगों में विद्यार्थियों की श्रेणी, रिक्त हो सकती है। प्रश्न के बीच चुपचाप domain नहीं बदलेंगे।
1. Predicate के लिए inputs और domain चाहिए
Predicate variables वाला कथन-रूप है। जैसे P(x): “x सम है” में उचित domain से x चुनने पर सत्य मान निकाल सकते हैं। पूर्णांकों पर P(4) सत्य और P(5) असत्य है। खुला expression P(x) अपने आप निश्चित सत्य मान वाला closed sentence नहीं है; x का assignment चाहिए या x को quantifier से बाँधना होगा।
Universal quantifier ∀ का अर्थ “हर के लिए” है। Existential quantifier ∃ का अर्थ “कम-से-कम एक मौजूद है” है। ∀x P(x) कहता है कि domain का हर तत्व P पूरा करता है; ∃x P(x) कहता है कि कम-से-कम एक करता है। Logic में “कुछ” का अर्थ कम-से-कम एक है; सभी भी हो सकते हैं। इसका अर्थ “कुछ, लेकिन सभी नहीं” नहीं है।
Domain महत्वपूर्ण है। ∀x(x²≥x) पूर्णांकों पर सत्य है: x≤0 और x≥1 दोनों में x(x−1)≥0 है। वास्तविक संख्याओं पर यह असत्य है, क्योंकि x=1/2 पर 1/4<1/2 है। संकेत नहीं बदले; स्वीकृत inputs बदल गए। निर्णय से पहले सूत्र के साथ domain लिखें।
2. Scope, free variables और bound variables
Quantifier अपने scope के सूत्र को नियंत्रित करता है। ∀x(P(x)→Q(x)) में दोनों predicates का x bound है। (∀x P(x))→Q(x) में quantifier का scope बंद कोष्ठक पर समाप्त होता है; Q(x) का x free है। ये केवल एक ही वाक्य की दो लिखावटें नहीं हैं। संक्षिप्त प्रचलनों पर निर्भर होने के बजाय पूरे कोष्ठक लगाएँ।
∀x∃y R(x,y) में दोनों variables bound हैं। ∀x R(x,y) में y free है और सूत्र दिए गए y पर निर्भर कर सकता है। Bound variable एक placeholder है: ∀x P(x) और ∀z P(z) का अर्थ समान है, बशर्ते नया नाम किसी पहले से free variable को अनजाने में bind न करे। उदाहरण के लिए ∀x R(x,y) को ∀y R(y,y) करना सुरक्षित नाम-परिवर्तन नहीं है; इससे y की भूमिका बदलती है।
3. किसी श्रेणी तक सीमित कथन लिखें
Domain सभी लोग हों। S(x) का अर्थ “x विद्यार्थी है” और P(x) का अर्थ “x उत्तीर्ण हुआ” हो।
- हर विद्यार्थी उत्तीर्ण हुआ: ∀x(S(x)→P(x))। गैर-विद्यार्थी इस conditional को गलत नहीं करता।
- कोई विद्यार्थी उत्तीर्ण हुआ: ∃x(S(x)∧P(x))। Witness विद्यार्थी भी हो और उत्तीर्ण भी।
- कोई विद्यार्थी उत्तीर्ण नहीं हुआ: ∀x(S(x)→¬P(x)), या ¬∃x(S(x)∧P(x))।
- सभी विद्यार्थी उत्तीर्ण नहीं हुए: ∃x(S(x)∧¬P(x))। अर्थात कम-से-कम एक विद्यार्थी उत्तीर्ण नहीं हुआ; यह नहीं कहता कि हर विद्यार्थी असफल रहा।
“हर विद्यार्थी” के लिए ∀x(S(x)∧P(x)) लिखना गलत रूप से हर व्यक्ति को विद्यार्थी भी घोषित करेगा। “कोई विद्यार्थी” के लिए ∃x(S(x)→P(x)) बहुत कमजोर है: एक गैर-विद्यार्थी से implication सत्य हो सकती है, भले कोई विद्यार्थी उत्तीर्ण न हुआ हो।
यदि विद्यार्थी हैं ही नहीं, तो “हर विद्यार्थी उत्तीर्ण हुआ” vacuously सत्य है: कोई विद्यार्थी counterexample नहीं है। “कोई विद्यार्थी उत्तीर्ण हुआ” असत्य है। यहाँ गैर-रिक्त लोगों के universe के भीतर विद्यार्थियों की श्रेणी रिक्त है; प्रथम-क्रम domain को रिक्त मानने की जरूरत नहीं। Universal claim अपने आप विद्यार्थियों का अस्तित्व सिद्ध नहीं करता।
4. एक-एक quantifier का निषेध करें
Negation “हर” और “कोई” को आपस में बदलकर भीतर जाती है:
¬∀x P(x) ≡ ∃x ¬P(x)।
¬∃x P(x) ≡ ∀x ¬P(x)।
Quantifiers पार करने के बाद propositional negation के नियम लगाएँ। उदाहरण:
¬∀x(S(x)→P(x)) ≡ ∃x ¬(S(x)→P(x)) ≡ ∃x(S(x)∧¬P(x))।
अंतिम conjunction, ¬(a→b)≡a∧¬b से मिलती है। केवल P पर negation लगाकर universal quantifier बनाए रखने का अर्थ “कोई विद्यार्थी उत्तीर्ण नहीं हुआ” होगा। यह अलग दावा है, सामान्य निषेध नहीं। विद्यार्थी हों ही नहीं तो “कोई विद्यार्थी उत्तीर्ण नहीं हुआ” सत्य है, लेकिन “कम-से-कम एक विद्यार्थी उत्तीर्ण नहीं हुआ” असत्य है। कम-से-कम एक विद्यार्थी मौजूद होने पर ही पहले दावे से दूसरे का निष्कर्ष निकलता है।
दो quantifiers के साथ ¬∀x∃y R(x,y) ≡ ∃x∀y ¬R(x,y)। अर्थ: एक ऐसा x है जिसके लिए कोई y काम नहीं करता। निषेध करते समय क्रम न उलटें; हर quantifier को अपनी जगह बदलें और भीतर के predicate का निषेध करें।
5. हल किया उदाहरण: witness, x पर निर्भर हो सकता है
D={1,2,3} लें और R(x,y) का अर्थ x+y=4 हो। Witness सूची बनाएँ:
| x | x+y=4 को सत्य करने वाला y |
|---|---|
| 1 | 3 |
| 2 | 2 |
| 3 | 1 |
इसलिए ∀x∃y R(x,y) सत्य है: हर x के लिए कम-से-कम एक उचित y, D में मिलता है। x चुनने के बाद witness बदल सकता है।
लेकिन ∃y∀x R(x,y) असत्य है। एक ही साझा y को x=1 के लिए 3 और x=2 के लिए 2 होना पड़ेगा, जो असंभव है। Existential quantifier पहले है, इसलिए सभी x जाँचने से पहले उसका witness निश्चित होना चाहिए।
सामान्य implication ∃y∀x R(x,y) → ∀x∃y R(x,y) सही है: सबके लिए काम करने वाला एक witness, हर अलग x के लिए भी काम करेगा। उलटी दिशा आवश्यक नहीं; यही उदाहरण इसे दिखाता है। लगातार universal quantifiers का आपसी क्रम बदल सकते हैं; लगातार existential quantifiers का भी। अलग प्रकार के quantifiers सामान्यतः आपस में नहीं बदल सकते।
6. हल किया उदाहरण: अनंत domain
पूर्णांकों पर ∀x∃y(y>x) सत्य है: हर पूर्णांक x के लिए पूर्णांक y=x+1 चुनें। एक सूत्र हर x के लिए वैध witness देता है; सभी पूर्णांक अलग-अलग लिखना आवश्यक नहीं।
उसी domain पर ∃y∀x(y>x) असत्य है। कोई भी प्रस्तावित y लें और x=y चुनें। तब y>x असत्य है, क्योंकि कोई संख्या स्वयं से बड़ी नहीं है। यह हर संभावित y को गलत सिद्ध करता है, केवल किसी एक खराब चुनाव को नहीं।
सीमित domain {1,2,3} पर ∀x∃y(y>x) भी असत्य है: x=3 के लिए domain में बड़ा तत्व नहीं। इसलिए quantifiers का क्रम और domain दोनों जरूरी हैं।
7. ठीक एक और प्रमाण की व्यावहारिक जाँच
“कम-से-कम एक वस्तु में P है” का सूत्र ∃x P(x) है। “ठीक एक वस्तु में P है” में uniqueness भी चाहिए:
∃x(P(x)∧∀y(P(y)→y=x))।
अर्थ: P वाली एक वस्तु चुनें और P वाली हर वस्तु को उसी के बराबर होना आवश्यक करें। केवल ∃x∃y(P(x)∧P(y)) से दो अलग वस्तुओं का अस्तित्व नहीं मिलता, क्योंकि x और y एक ही वस्तु हो सकते हैं। अलग होना आवश्यक हो तो x≠y जोड़ें।
सीमित domain में universal statement को conjunction और existential statement को disjunction में खोल सकते हैं। D={a,b} पर ∀x P(x) का अर्थ P(a)∧P(b), जबकि ∃x P(x) का अर्थ P(a)∨P(b) है। यह छोटे उदाहरण की उपयोगी जाँच है, अनंत domain की सूची बनाने की विधि नहीं।
Universal statement सिद्ध करने के लिए कोई भी स्वीकृत तत्व लेकर तर्क दें। उसे गलत सिद्ध करने के लिए एक counterexample पर्याप्त है। Existential statement सिद्ध करने के लिए एक वैध witness दें। उसे गलत सिद्ध करने के लिए हर candidate की विफलता दिखाएँ। Nested quantifiers में यही जाँच क्रम से करें और ध्यान रखें कि witness किन पहले variables पर निर्भर हो सकता है।
झटपट संदर्भ और गलतियाँ
- सूत्र जाँचने से पहले domain बताएँ।
- ∃ का अर्थ “कम-से-कम एक” है, “ठीक एक” नहीं।
- सीमित श्रेणी के universal कथन में सामान्यतः implication और existential कथन में conjunction आती है।
- “सभी नहीं” और “एक भी नहीं” अलग हैं।
- बाद का existential witness, पहले universal variable पर निर्भर हो सकता है।
- Scope तय करता है कि variables कहाँ bound हैं; कोष्ठक अर्थ का हिस्सा हैं।
- कुछ उदाहरणों में counterexample न मिलना अनंत domain पर प्रमाण नहीं है।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें। दिए domains और operations महत्वपूर्ण हैं।
C01. Domain सभी लोग हैं। S(x) का अर्थ विद्यार्थी और P(x) का अर्थ उत्तीर्ण है। ∀x(S(x)→P(x)) का निषेध कौन-सा है?
A. ∀x(S(x)→¬P(x)) B. ∃x(S(x)∧P(x)) C. ∃x(S(x)∧¬P(x)) D. ∀x(¬S(x)∧¬P(x))
उत्तर: C
A: यह कहता है कोई विद्यार्थी उत्तीर्ण नहीं हुआ। यह आवश्यक निषेध के समतुल्य नहीं: विद्यार्थी हों ही नहीं तो यह universal कथन सत्य और आवश्यक existential कथन असत्य है।
B: यह किसी विद्यार्थी के उत्तीर्ण होने का दावा है, universal कथन का counterexample नहीं।
C: ∀ को ∃ करें और implication नकारें: एक ऐसा विद्यार्थी है जो उत्तीर्ण नहीं हुआ।
D: यह हर व्यक्ति को गैर-विद्यार्थी और अनुत्तीर्ण बताता है; दिए नियम का निषेध नहीं।
C02. D={1,2,3} और R(x,y): x+y=4 के लिए क्रमशः ∀x∃y R(x,y) और ∃y∀x R(x,y) के सत्य मान क्या हैं?
A. F, T B. T, F C. T, T D. F, F
उत्तर: B
A: मान उलटे हैं: हर x का witness है, लेकिन एक ही y सबके लिए काम नहीं करता।
B: x=1,2,3 के witnesses y=3,2,1 हैं। साझा y को 3 और 2 दोनों होना पड़ेगा, इसलिए केवल पहला कथन सत्य है।
C: दूसरे कथन में सभी x के लिए एक ही y तय है; अलग आवश्यक मानों से यह असंभव है।
D: पहले कथन में y, x के साथ बदल सकता है, इसलिए वह सत्य है।
C03. सूत्र ∀x R(x,y) में कौन-सा variable free है?
A. केवल x B. केवल y C. x और y दोनों D. न x, न y
उत्तर: B
A: Universal quantifier, R(x,y) के x को bind करता है।
B: सूत्र x को bind करता है, लेकिन y के लिए quantifier नहीं, इसलिए y free है।
C: केवल y free है; x universal quantifier के scope में है।
D: x का quantifier अपने आप बाकी variables को bind नहीं करता।
C04. Domain सभी लोग हों तो “कम-से-कम एक विद्यार्थी उत्तीर्ण हुआ” का सही सूत्र कौन-सा है?
A. ∀x(S(x)→P(x)) B. ∃x(S(x)→P(x)) C. ∀x(S(x)∧P(x)) D. ∃x(S(x)∧P(x))
उत्तर: D
A: यह हर विद्यार्थी के उत्तीर्ण होने का दावा है; विद्यार्थी का अस्तित्व नहीं देता।
B: गैर-विद्यार्थी से implication सत्य हो सकती है, बिना किसी उत्तीर्ण विद्यार्थी के।
C: यह हर व्यक्ति को विद्यार्थी और उत्तीर्ण माँगता है, जो पूछे कथन से अधिक है।
D: Existential witness को दोनों शर्तें पूरी करनी हैं: विद्यार्थी और उत्तीर्ण।
C05. पूर्णांकों और वास्तविक संख्याओं पर ∀x(x²≥x) के सत्य मान कैसे हैं?
A. पूर्णांकों पर सत्य; वास्तविक संख्याओं पर असत्य B. पूर्णांकों पर असत्य; वास्तविक संख्याओं पर सत्य C. दोनों पर सत्य D. दोनों पर असत्य
उत्तर: A
A: पूर्णांक में x≤0 या x≥1 से x(x−1)≥0। वास्तविक x=1/2 पर 1/4<1/2।
B: पूर्णांक inequality पूरी करते हैं; counterexample 1/2 वास्तविक है, पूर्णांक नहीं।
C: वास्तविक संख्याओं वाला दावा x=1/2 पर विफल है।
D: पूर्णांकों वाला दावा सत्य है; केवल nonintegers जाँचकर उसे गलत नहीं कर सकते।
C06. कौन-सा सूत्र कहता है कि domain का ठीक एक तत्व P पूरा करता है?
A. ∃x P(x) B. ∀x P(x) C. ∃x(P(x)∧∀y(P(y)→y=x)) D. ∃x∃y(P(x)∧P(y))
उत्तर: C
A: यह अस्तित्व बताता है, लेकिन दो या अधिक satisfying तत्वों को नहीं रोकता।
B: यह हर तत्व के P पूरा करने का दावा है, ठीक एक का नहीं।
C: P वाला x चुनें और P वाले हर y को उसी के बराबर माँगें; अस्तित्व और uniqueness दोनों मिलते हैं।
D: दो witnesses समान हो सकते हैं और सूत्र अन्य satisfying तत्वों को भी नहीं रोकता।
स्रोत और दायरा
यह मौलिक आधारभूत पाठ आधिकारिक GATE 2027 CS syllabus के Section 1 में Discrete Mathematics से जुड़ा है। यह पूरा विषय या पूरा syllabus नहीं। Syllabus प्रासंगिकता बताता है; NPTEL course आगे पढ़ने का मूल संस्थागत स्रोत है। उदाहरण और अभ्यास मौलिक हैं, परीक्षा से नकल किए प्रश्न नहीं।
स्रोत जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन