प्रतिज्ञप्ति व प्रथम-कोटि तर्कशास्त्र

तर्कशास्त्र इस खंड का वह एक प्रकरण है जहाँ अभ्यर्थी उत्तर के विषय में निश्चित हो सकता है, क्योंकि प्रतिज्ञप्ति तर्क का प्रत्येक प्रश्न परिगणना से तय हो जाता है — और फिर भी अंक जाते हैं, क्योंकि घड़ी के नीचे परिगणना धीमी है और लघु-मार्ग अपरिचित। उनमें दो सर्वाधिक काम करते हैं। पहला, निहितार्थ छद्म रूप में वियोजन है: p → q ठीक ¬p ∨ q है, और उसे उस रूप में लिखना तीरों के जाल को ऐसी वस्तु बना देता है जिस पर डी मॉर्गन सीधे लगाया जा सके। दूसरा, केवल प्रतिधनात्मक तुल्य है। p → q से आप ¬q → ¬p निकाल सकते हैं और कुछ नहीं: विलोम q → p तथा प्रतिलोम ¬p → ¬q दोनों मूल से स्वतंत्र हैं, और इनमें किसी को उससे भ्रमित करना इस प्रकरण की सबसे आम एकल त्रुटि है — GATE तीनों को विकल्पों में रखकर इसे जान-बूझकर परखता है। इसके आगे, स्मरण रखें कि असत्य पूर्ववर्ती वाला निहितार्थ क्या करता है: वह रिक्त रूप से सत्य है, इसीलिए "यदि x, 2 से बड़ा अभाज्य है तो x विषम है" x = 4 से असत्य नहीं होता। प्रथम-कोटि भाग परिमाणक तथा ठीक-ठीक रखने योग्य दो नियम जोड़ता है। निषेध परिमाणक पलटता है और भीतर चला जाता है: ¬∀x P(x), ∃x ¬P(x) है, और ¬∃x P(x), ∀x ¬P(x)। तथा असमान परिमाणकों का क्रम महत्व रखता है: वास्तविक संख्याओं पर ∀x ∃y (x < y) सत्य है — प्रत्येक संख्या के ऊपर कुछ है — जबकि ∃y ∀x (x < y) असत्य, क्योंकि वह सब के ऊपर एक संख्या का दावा करता है। उन्हें बदलना पुनर्व्यवस्था नहीं, भिन्न कथन है, और दोनों देने वाला प्रश्न यह परखता है कि आपने प्रतीक नहीं, क्रम पढ़ा।

निहितार्थ, व उसके तीन छद्मरूप

p → q से बने चार कथन, व उनमें कौन उसके तुल्य हैं
नाम व रूपp → q के तुल्य?महत्व
मूल: p → q ≡ ¬p ∨ qहाँ — परिभाषा सेतीर को वियोजन लिखना लगभग प्रत्येक सरलीकरण प्रश्न की पहली चाल है।
प्रतिधनात्मक: ¬q → ¬pहाँ — एकमात्रदोनों भाग निषेधित तथा परस्पर बदले हुए। प्रतिधनात्मक विधि से प्रमाण इसी प्रतिस्थापन पर टिकता है।
विलोम: q → pनहींबदले हुए पर निषेधित नहीं। "सभी वर्ग आयत हैं" से "सभी आयत वर्ग हैं" नहीं मिलता।
प्रतिलोम: ¬p → ¬qनहींनिषेधित पर बदले नहीं। वह विलोम का प्रतिधनात्मक है, इसीलिए दोनों साथ खड़े या साथ गिरते हैं।
⚠️ असत्य पूर्ववर्ती निहितार्थ को सत्य बनाता है
p → q अपनी सत्य-सारणी की ठीक एक पंक्ति में असत्य है: p सत्य व q असत्य। अन्य हर स्थान पर वह सत्य है, उन दोनों पंक्तियों सहित जहाँ p असत्य है — रिक्त स्थिति। अतः "यदि 2 + 2 = 5 तो चंद्रमा पनीर है" सत्य कथन है, और सूत्र के सत्य होने की पंक्तियाँ गिनने वाले प्रश्न को वे पंक्तियाँ भी गिननी होंगी। अंक बचाने वाली आदत यह है कि चारों जाँचने के बजाय एकमात्र असत्यकारी पंक्ति खोजें: निहितार्थ केवल वहाँ विफल होता है जहाँ उसका पूर्ववर्ती सत्य और परिणामी असत्य हो।
  • सत्य-सारणियाँ 2ⁿ के रूप में बढ़ती हैं। तीन चर अर्थात् आठ पंक्तियाँ, चार अर्थात् सोलह। पाँच चर देने वाला प्रश्न सारणी नहीं माँग रहा — वह बीजीय सरलीकरण या एक सुविचारित पंक्ति माँग रहा है।
  • n चरों के भिन्न बूलीय फलनों की संख्या 2(2ⁿ) है। दो चरों हेतु वह 2⁴ = 16 है, इसीलिए सोलह दो-निवेश गेट संभावनाओं को समाप्त कर देते हैं और खोजने हेतु सत्रहवाँ नहीं है। फलनों की गिनती व पंक्तियों की गिनती भिन्न प्रश्न हैं और दोनों आते हैं।
  • पुनरुक्ति प्रत्येक पंक्ति में सत्य, विरोधोक्ति किसी में नहीं, तथा आपातिक कुछ में। निर्वचन-नियम (p ∧ (p → q)) → q, वियोजक न्यायवाक्य ((p ∨ q) ∧ ¬p) → q, तथा परिकल्पित न्यायवाक्य ((p → q) ∧ (q → r)) → (p → r) सभी पुनरुक्तियाँ हैं, और तीनों इस अध्याय हेतु परिगणना से पुष्ट किए गए।

परिमाणक — निषेध व क्रम

दो यांत्रिक नियम GATE के लगभग प्रत्येक प्रथम-कोटि प्रश्न को समेट लेते हैं, और दोनों को सहज बोध के बजाय प्रतीक-दर-प्रतीक लगाना उपयोगी है।

  1. निषेध को भीतर धकेलें, और गुजरते हुए प्रत्येक परिमाणक पलटें। ¬∀x P(x) ≡ ∃x ¬P(x); ¬∃x P(x) ≡ ∀x ¬P(x)। दो बार लगाने पर: ¬∀x ∃y P(x, y) ≡ ∃x ∀y ¬P(x, y)। परिमाणक अपना क्रम रखते हैं और प्रत्येक अपना प्रकार बदलता है — अभ्यर्थी प्रायः यह चरण उलट देते हैं, जिससे ∀x ∃y ¬P बनता है, जो भिन्न दावा है।
  2. असमान परिमाणक क्रम-विनिमेय नहीं हैं। ∀x ∃y तथा ∃y ∀x भिन्न बातें कहते हैं, और दूसरा अधिक प्रबल है: वह ऐसा एक y माँगता है जो प्रत्येक x हेतु चले। वास्तविक संख्याओं पर ∀x ∃y (x < y) सत्य और ∃y ∀x (x < y) असत्य है। समान परिमाणक क्रम-विनिमेय होते हैं: ∀x ∀y वही है जो ∀y ∀x, और दो अस्तित्व-परिमाणकों हेतु भी वैसा ही।
🧠 "सभी" का अनुवाद निहितार्थ से और "कुछ" का संयोजन से करें
"प्रत्येक विद्यार्थी उत्तीर्ण हुआ" ∀x (विद्यार्थी(x) → उत्तीर्ण(x)) है — निहितार्थ, अतः विद्यार्थी-रहित जगत् में वह रिक्त रूप से सत्य है। "कोई विद्यार्थी उत्तीर्ण हुआ" ∃x (विद्यार्थी(x) ∧ उत्तीर्ण(x)) है — संयोजन, जो उसी रिक्त जगत् में असत्य है। संयोजकों को बदल देना मानक अनुवाद-त्रुटि है और वह दो ऐसे कथन बनाती है जो लगभग सदा गलत होते हैं: ∀x (विद्यार्थी(x) ∧ उत्तीर्ण(x)) दावा करता है कि जगत् की प्रत्येक वस्तु विद्यार्थी है, और ∃x (विद्यार्थी(x) → उत्तीर्ण(x)) किसी भी अविद्यार्थी से ही संतुष्ट हो जाता है।

मुख्य बिंदु

  • p → q का अर्थ ¬p ∨ q है। तीर को वियोजन लिखना लगभग प्रत्येक सरलीकरण प्रश्न की पहली चाल है।
  • केवल प्रतिधनात्मक ¬q → ¬p, p → q के तुल्य है। विलोम व प्रतिलोम नहीं, और GATE तीनों विकल्पों में रखता है।
  • निहितार्थ ठीक एक पंक्ति में विफल होता है — पूर्ववर्ती सत्य, परिणामी असत्य। असत्य पूर्ववर्ती उसे रिक्त रूप से सत्य बनाता है।
  • n चर 2ⁿ पंक्तियाँ तथा 2(2ⁿ) भिन्न बूलीय फलन देते हैं। दो चर: 4 पंक्तियाँ, 16 फलन — दो भिन्न प्रश्न।
  • निषेध परिमाणक पलटकर भीतर जाता है: ¬∀x ∃y P ≡ ∃x ∀y ¬P। क्रम बना रहता है; प्रकार बदलते हैं।
  • ∀x ∃y तथा ∃y ∀x भिन्न कथन हैं, दूसरा अधिक प्रबल। वास्तविक संख्याओं पर x < y हेतु पहला सत्य व दूसरा असत्य है।
  • "सभी" का अनुवाद → से, "कुछ" का ∧ से करें। उन्हें बदलने पर दो ऐसे कथन बनते हैं जो लगभग सदा गलत हैं।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. प्रतिज्ञप्ति p → q तार्किक रूप से किसके तुल्य है:

    1. p ∨ ¬q
    2. ¬p ∨ q
    3. p ∧ ¬q
    4. ¬p ∧ q
    उत्तर देखें

    उत्तर: B — ¬p ∨ q

    निहितार्थ केवल तब असत्य है जब p सत्य व q असत्य हो, और ¬p ∨ q भी ठीक उसी पंक्ति में असत्य है — अतः दोनों चारों पंक्तियों पर सहमत हैं। विकल्प C निहितार्थ का निषेध है, जो स्वयं जानने योग्य है: ¬(p → q) ≡ p ∧ ¬q, और विरोधाभास से प्रमाण यही रूप मानकर चलता है। विकल्प A यह बदल देता है कि कौन-सा पक्ष निषेधित है, जिससे वह सूत्र बनता है जो केवल तब असत्य है जब p असत्य व q सत्य हो — विलोम का निषेध। तीर दिखते ही ¬p ∨ q तक पहुँचना ही निहितार्थों के जाल पर डी मॉर्गन को लागू करने योग्य बनाता है।

  2. इनमें कौन "यदि वर्षा होती है तो मैच रद्द हो जाता है" के तार्किक रूप से तुल्य है?

    1. यदि मैच रद्द होता है तो वर्षा होती है
    2. यदि वर्षा नहीं होती तो मैच रद्द नहीं होता
    3. यदि मैच रद्द नहीं होता तो वर्षा नहीं होती
    4. वर्षा होती है और मैच रद्द होता है
    उत्तर देखें

    उत्तर: C — यदि मैच रद्द नहीं होता तो वर्षा नहीं होती

    मूल p → q है, जहाँ p = "वर्षा होती है" व q = "मैच रद्द होता है"। उसका प्रतिधनात्मक ¬q → ¬p विकल्प C है, और केवल प्रतिधनात्मक तुल्य है। विकल्प A विलोम व विकल्प B प्रतिलोम है, और दोनों मूल से स्वतंत्र हैं: मैच किसी अन्य कारण से भी रद्द हो सकता है, जो A को असत्य कर देता है जबकि मूल सत्य रहता है, और उसी स्थिति में B को भी। विकल्प D संयोजन है, जो दावा करता है कि वर्षा वस्तुतः हो रही है — निहितार्थ इस विषय में कुछ दावा नहीं करता कि p सत्य है या नहीं। ध्यान दें A व B परस्पर तुल्य हैं, क्योंकि प्रतिलोम विलोम का प्रतिधनात्मक है, इसीलिए परीक्षक कुछ भी उजागर किए बिना दोनों दे सकता है।

  3. दो चरों के भिन्न बूलीय फलनों की संख्या है:

    1. 4
    2. 8
    3. 16
    4. 256
    उत्तर देखें

    उत्तर: C — 16

    दो चरों का फलन 2² = 4 निवेश-पंक्तियों में प्रत्येक पर अपने निर्गम से नियत होता है, और प्रत्येक निर्गम दो मानों में से एक — अतः 2⁴ = 16 फलन हैं। सामान्य सूत्र 2(2ⁿ) है, और दुहरा घातांक ही इसे इतना तेज़ बढ़ाता है: तीन चर 2⁸ = 256 देते हैं, जो विकल्प D है और इस परिवार के अगले प्रश्न का उत्तर। विकल्प A पंक्तियों की संख्या है और विकल्प B तीन चरों हेतु पंक्तियों की, और उत्तर के साथ दोनों देना परीक्षक की यह जाँच है कि आप जानते हैं कि कौन-सी गिनती पूछी गई। सोलह ही वह कारण है कि खोजने हेतु सत्रहवाँ दो-निवेश लॉजिक गेट नहीं है।

  4. ∀x ∃y P(x, y) का निषेध है:

    1. ∃x ∀y ¬P(x, y)
    2. ∀x ∃y ¬P(x, y)
    3. ∀y ∃x ¬P(x, y)
    4. ∃y ∀x ¬P(x, y)
    उत्तर देखें

    उत्तर: A — ∃x ∀y ¬P(x, y)

    निषेध को एक-एक परिमाणक भीतर धकेलें, गुजरते हुए प्रत्येक को पलटें और क्रम अछूता छोड़ें: ¬∀x (…) बनता है ∃x ¬(…), और फिर ¬∃y P बनता है ∀y ¬P। परिणाम ∃x ∀y ¬P(x, y) है। विकल्प B कुछ नहीं पलटता और सबसे आम गलत उत्तर है — वह विधेय को निषेधित करता है और दोनों परिमाणक यथावत् छोड़ देता है, जो सर्वथा भिन्न बात कहता है। विकल्प C व D परिमाणकों का क्रम भी बदल देते हैं, और असमान परिमाणक क्रम-विनिमेय नहीं हैं, अतः क्रम बदलना कथन को फिर से कहना नहीं, बदल देना है। जाँच हेतु उत्तर को शब्दों में पढ़ें: मूल कहता है प्रत्येक x हेतु कोई y चलता है, और उसका निषेध कहता है किसी x हेतु कोई y नहीं चलता।

  5. वास्तविक संख्याओं के प्रांत पर S₁ = ∀x ∃y (x < y) तथा S₂ = ∃y ∀x (x < y) लें। तब:

    1. दोनों सत्य हैं
    2. S₁ सत्य व S₂ असत्य है
    3. S₁ असत्य व S₂ सत्य है
    4. दोनों असत्य हैं
    उत्तर देखें

    उत्तर: B — S₁ सत्य व S₂ असत्य है

    S₁ कहता है: प्रत्येक वास्तविक x हेतु उससे ऊपर कोई वास्तविक y है। सत्य — y = x + 1 लें, और y को x पर निर्भर होने की अनुमति है। S₂ कहता है: एक ऐसा वास्तविक y है जो प्रत्येक वास्तविक x से ऊपर है। असत्य — कोई वास्तविक संख्या सभी वास्तविकों से बड़ी नहीं, क्योंकि तब y को स्वयं y से बड़ा होना पड़ता। अतः S₁ सत्य, S₂ असत्य। दोनों सूत्रों में वही प्रतीक भिन्न क्रम में हैं, और वह क्रम ही पूरा प्रश्न है: ∀x ∃y में y को x देखने के बाद चुना जा सकता है, जबकि ∃y ∀x में उसे पहले चुनना है और सब हेतु चलना है। जब भी प्रश्न दोनों क्रम दे, तुलना से पहले प्रत्येक का वाक्य में अनुवाद करें — प्रतीक परस्पर विनिमेय दिखते हैं और वाक्य कभी नहीं।

  6. निम्नलिखित में कौन पुनरुक्ति नहीं है?

    1. (p ∧ (p → q)) → q
    2. ((p → q) ∧ (q → r)) → (p → r)
    3. (p → q) → (q → p)
    4. p → (q → p)
    उत्तर देखें

    उत्तर: C — (p → q) → (q → p)

    विकल्प C उस पंक्ति पर विफल होता है जहाँ p असत्य व q सत्य है: तब p → q सत्य है, q → p असत्य, और सत्य पूर्ववर्ती के साथ असत्य परिणामी पूरे सूत्र को असत्य कर देता है। अतः वह पुनरुक्ति नहीं है — वह यह दावा है कि निहितार्थ अपना विलोम दे देता है, और पिछले प्रश्न ठीक इसी त्रुटि के विषय में थे। अन्य तीन मानक पुनरुक्तियाँ हैं और परिगणना से जाँची गईं: A निर्वचन-नियम है, B परिकल्पित न्यायवाक्य, और D इसलिए सत्य है कि जब भी p सत्य हो, q जो भी करे, q → p सत्य होता है। ऐसे प्रश्न पर सबसे तेज़ मार्ग चार सत्य-सारणियाँ बनाना नहीं, प्रत्येक संभावित उत्तर में एक असत्यकारी पंक्ति खोजना है, और पहले p असत्य के साथ q सत्य आज़माना, क्योंकि वही पंक्ति विलोमों को तोड़ती है।

  7. निम्नलिखित में कौन-सी पुनरुक्तियाँ हैं? (एक से अधिक विकल्प सही हो सकते हैं।)

    1. ((p ∨ q) ∧ ¬p) → q
    2. (p → q) ↔ (¬q → ¬p)
    3. (p → q) ↔ (¬p → ¬q)
    4. p ↔ q
    उत्तर देखें

    उत्तर: A — ((p ∨ q) ∧ ¬p) → q; B — (p → q) ↔ (¬q → ¬p)

    A वियोजक न्यायवाक्य है: यदि p ∨ q सत्य हो और p न हो, तो q को होना ही पड़ेगा — प्रत्येक पंक्ति में सत्य। B कहता है कि निहितार्थ व उसका प्रतिधनात्मक तुल्य हैं, जो वही एक तुल्यता है जिस पर यह अध्याय बल देता है, अतः यह द्विशर्त पुनरुक्ति है। C वही दावा प्रतिलोम हेतु करता है, और p असत्य के साथ q सत्य पर विफल होता है, जहाँ p → q सत्य व ¬p → ¬q असत्य है। D आपातिक है, पुनरुक्ति नहीं: p ↔ q केवल उन दो पंक्तियों में सत्य है जहाँ p व q सहमत हों, और कुछ पंक्तियों में सत्य तथा अन्य में असत्य सूत्र ठीक वही है जो पुनरुक्ति नहीं होती। चार में दो सही, और चूँकि MSQ आंशिक अंक नहीं देता, चारों को परखना ही उसे प्राप्त करने का एकमात्र मार्ग है — जिसकी कोई लागत नहीं, क्योंकि गलत MSQ पर दंड नहीं है।

  8. (p ∨ q) ∧ (¬p ∨ r) को संतुष्ट करने वाले p, q व r के सत्य-निर्धारणों की संख्या _____ है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 4

    2³ = 8 निर्धारण हैं; उनमें 4 सूत्र को संतुष्ट करते हैं। आठों की सारणी बनाने के बजाय p पर स्थिति-विभाजन करें। यदि p सत्य है, तो पहला उपवाक्य स्वतः सत्य है और दूसरे को r चाहिए, अतः q मुक्त है: 2 निर्धारण, (p, q, r) = (T, T, T) व (T, F, T)। यदि p असत्य है, तो दूसरा उपवाक्य स्वतः सत्य है और पहले को q चाहिए, अतः r मुक्त है: 2 और, (F, T, T) व (F, T, F)। कुल 4, और स्थिति-विभाजन दो पंक्तियों में वह कर देता है जो सारणी आठ पंक्तियों में। दोनों उपवाक्यों में आने वाले चर पर विभाजन करना सामान्य युक्ति है — वह SAT हलकर्ता की एकक-प्रसार जैसी ही है, और वही इन प्रश्नों को केवल परिमित नहीं, तेज़ बनाती है।