1. प्रमाण क्या है
तर्क यह दावा है कि कोई निष्कर्ष कुछ आधारवाक्यों से निकलता है। प्रमाण वह है जो इस दावे का निपटारा करता है: एक सीमित, जाँचने योग्य वस्तु जिसे कोई भी पंक्ति-दर-पंक्ति पढ़कर स्वीकार कर सके, आपकी बात पर भरोसा किए बिना। प्रमाण का सार यह नहीं कि वह आश्वस्त करता है - अच्छा भाषण भी करता है - बल्कि यह कि उसका हर कदम और किसी तरह हो ही नहीं सकता था।
यह माँग सुनने में जितनी लगती है उससे कहीं कड़ी है। «बारिश हो रही है, इसलिए ज़मीन गीली है» कहना उचित है, पर यह इस पर टिका है कि आप बारिश और ज़मीन के बारे में क्या जानते हैं। औपचारिक तर्कशास्त्र यह सब हटा देता है और एक संकरा प्रश्न पूछता है: केवल वाक्यों के रूप को देखते हुए, क्या ऐसा कोई रास्ता है जिसमें आधारवाक्य सत्य हों और निष्कर्ष असत्य? यदि कोई रास्ता नहीं, तो तर्क वैध है, और प्रमाण इसी का लेखा है कि कोई रास्ता क्यों नहीं।
यह मार्गदर्शिका वह लेखा तैयार करने के एक तरीके के बारे में है - सिमैंटिक टैब्लो की विधि, जिसे सत्य-वृक्ष भी कहते हैं। जब भी आप कैलकुलेटर में कोई तर्क लिखते हैं, यह साइट यही विधि चलाती है; और एक बार इसे साध लेने पर आप केवल एक कलम से कागज़ पर तर्क जाँच सकते हैं।
2. वैध, और आप यह कैसे जानेंगे
तर्क को निष्पत्ति-चिह्न के साथ लिखिए: बाएँ आधारवाक्य, दाएँ निष्कर्ष। दावा p → q, ¬q ⊨ ¬p कहता है कि एक शर्तवाक्य और उसके उत्तरांग के निषेध से पूर्वांग का निषेध निकलता है। निष्पत्ति-चिह्न कोई और संयोजक नहीं है। वह अपने दोनों ओर की सूत्र-रचनाओं के बारे में एक दावा है, और वह या तो सही है या ग़लत।
वैधता की परिभाषा सीधे उसकी जाँच का तरीका बताती है: चरों को सत्य और असत्य देने की हर संभावना देख जाइए और पता कीजिए कि क्या कोई ऐसी है जो सभी आधारवाक्यों को सत्य और निष्कर्ष को असत्य बनाती हो। सत्य-सारणी यही करती है, और दो-तीन चरों तक यह बिलकुल ठीक है। दिक्कत यह है कि सारणी 2ⁿ की दर से बढ़ती है। दस चरों को हज़ार पंक्तियाँ चाहिए, बीस को दस लाख, और सारणी यह नहीं बताती कि कौन-सी पंक्तियाँ मायने रखती थीं।
टैब्लो उसी प्रश्न पर दूसरे सिरे से हमला करता है। हर संभावना गिनाकर उनमें से एक बुरी खोजने के बजाय, वह मान लेता है कि एक बुरी संभावना है और उसे गढ़ने की कोशिश करता है। यदि यह कोशिश हर संभव राह पर विरोधाभास में ढह जाए, तो ऐसा कोई निर्धारण है ही नहीं और तर्क वैध है। यदि कोशिश सफल हो जाए, तो जो गढ़ा गया वही प्रतिउदाहरण है, जिसे आप सीधे पढ़ सकते हैं।
3. टैब्लो विधि
टैब्लो चिह्नित सूत्रों का एक वृक्ष है। हर पंक्ति एक सूत्र है जिसके आगे T या F लगा है, और यह चिह्न बताता है कि शाखा उस सूत्र के बारे में क्या मान रही है - उसका सत्य-मान क्या है यह नहीं, बल्कि तर्क के विफल होने के लिए वह क्या होना चाहिए। पूरी विधि चार चरणों की है:
- हर आधारवाक्य को T के साथ लिखिए। आप मान रहे हैं कि तर्क के सभी आधारवाक्य टिकते हैं।
- निष्कर्ष को F के साथ लिखिए। आप मान रहे हैं कि फिर भी वह विफल होता है - यही वह मान्यता है जिसका आप खंडन करना चाहते हैं।
- कोई भी ऐसी पंक्ति लीजिए जो अभी परमाणु नहीं है, और उसके मुख्य संयोजक तथा चिह्न का नियम लगाइए, और नियम जो देता है उसे उस पंक्ति से गुज़रने वाली हर शाखा के अंत में जोड़िए।
- जैसे ही किसी शाखा पर एक ही सूत्र A के लिए T A और F A दोनों आ जाएँ, उसे बंद कर दीजिए। जब हर शाखा बंद हो जाए, या विघटित करने को कोई पंक्ति न बचे, तब रुक जाइए।
इस चक्र में न चतुराई चाहिए न रणनीति का चुनाव। हर पंक्ति का ठीक एक नियम होता है, और उन्हें किसी भी क्रम में लगाने पर वही निर्णय निकलता है - इसीलिए यह काम मशीन कर सकती है, और इसीलिए जब वह करे तो परिणाम पर भरोसा किया जा सकता है।
4. नियम
हर संयोजक के लिए हर चिह्न के अंतर्गत एक नियम है - कुल दस। ये दो किस्मों में बँटते हैं, और इन किस्मों का अंतर ही वह पूरा कारण है जिससे टैब्लो सूची नहीं बल्कि वृक्ष है। α नियम कहता है कि कई बातें एक साथ टिकनी चाहिए, इसलिए वह अपने परिणाम शाखा के साथ नीचे की ओर चढ़ाता जाता है। β नियम कहता है कि दो में से एक बात टिकनी चाहिए, इसलिए वह शाखा को दो में चीर देता है और हर स्थिति को अपनी राह जाने देता है।
| पंक्ति | देता है | रूप |
|---|---|---|
T ¬A | F A | चढ़ाता है |
F ¬A | T A | चढ़ाता है |
T (A∧B) | T A, T B | चढ़ाता है |
F (A∧B) | F AF B | शाखित |
T (A∨B) | T AT B | शाखित |
F (A∨B) | F A, F B | चढ़ाता है |
T (A→B) | F AT B | शाखित |
F (A→B) | T A, F B | चढ़ाता है |
T (A↔B) | T A, T BF A, F B | शाखित |
F (A↔B) | T A, F BF A, T B | शाखित |
हर नियम अपने संयोजक की सत्य-शर्त को उलटकर पढ़ने भर से बनता है। संयोजन तभी सत्य है जब दोनों पक्ष सत्य हों, इसलिए T (A ∧ B) पर T A और T B चढ़ते हैं। संयोजन तब असत्य है जब कम से कम एक पक्ष असत्य हो, पर सूत्र यह नहीं बताता कि कौन-सा, इसलिए F (A ∧ B) को दोनों आज़माने पड़ते हैं: वह शाखित होता है। वियोजन में यही असमानता उलटी दिशा में चलती है, और शर्तवाक्य का असत्य होना यह कहता है कि पूर्वांग टिका और उत्तरांग गिरा - वही एकमात्र स्थिति जिसमें निहितार्थ टूटता है।
ध्यान दीजिए कि नियम क्या कभी नहीं करते: वे कभी कोई सूत्र गढ़ते नहीं। नियम जो कुछ देता है वह उसी पंक्ति का एक टुकड़ा होता है जिससे वह आया। यही गुण - उपसूत्र-गुण - विधि को सीमित बनाता है, और नीचे हम इस पर लौटेंगे।
5. शाखा बंद करना
शाखा तर्क का एक अकेला सिलसिला है: जड़ से पत्ते तक पढ़िए और आपके पास मान्यताओं का एक पूरा समुच्चय होगा। शाखा तब बंद होती है जब ये मान्यताएँ आपस में सीधे टकराती हैं, यानी जब वह एक ही सूत्र के लिए T A और F A दोनों ढोती है। A कितना भी जटिल हो या दोनों पंक्तियाँ कितनी भी दूर हों, इससे फ़र्क नहीं पड़ता - यदि किसी शाखा को चाहिए कि कोई सूत्र सत्य भी हो और असत्य भी, तो उसे कुछ भी संतुष्ट नहीं करता।
बंद शाखा पर × लगाइए, उन दो पंक्तियों के नाम लिखिए जिन्होंने उसे बंद किया, और उस पर काम करना छोड़ दीजिए। जो मान्यता पहले से ही असंभव थी, उससे और कुछ सीखने को नहीं है।
जब हर शाखा बंद हो जाती है, टैब्लो बंद है, और वही प्रमाण है। वह दिखाता है कि जिस अनुमान से आपने शुरू किया - सभी आधारवाक्य सत्य, निष्कर्ष असत्य - वह हर संभव राह पर विरोधाभास तक ले जाता है। चूँकि कोई राह बची नहीं, ऐसा कोई निर्धारण है नहीं, और तर्क वैध है। यह विरोधाभास द्वारा प्रमाण है, ऐसे बिछाया गया कि कोई स्थिति छूट न सके।
6. एक प्रमाण, पंक्ति-दर-पंक्ति
मोडस टॉलेंस लीजिए: p → q, ¬q ⊨ ¬p. पंक्ति 1 और 2 आधारवाक्य हैं, सत्य मान लिए गए। पंक्ति 3 निष्कर्ष है, असत्य मान लिया गया - और चूँकि निष्कर्ष ¬p है, उसे असत्य मानना p को सत्य मानना है, जिसे पंक्ति 5 दर्ज करती है। पंक्ति 4 पंक्ति 2 पर निषेध नियम लगाने से आती है: यदि ¬q सत्य है तो q असत्य है। पंक्ति 1 का शर्तवाक्य ही एकमात्र बची पंक्ति है जिसमें संयोजक है, और वह β नियम है, इसलिए वृक्ष दो में फूटता है:
- 1सत्य: p→qआधार वाक्य
- 2सत्य: ¬qआधार वाक्य
- 3असत्य: ¬pनिषिद्ध निष्कर्ष
- 4असत्य: qपंक्ति 2 से
- 5सत्य: pपंक्ति 3 से
- 6असत्य: pपंक्ति 1 से
शाखा बंद: पंक्ति 6 पंक्ति 5 का खंडन करती है।
- 7सत्य: qपंक्ति 1 से
शाखा बंद: पंक्ति 7 पंक्ति 4 का खंडन करती है।
बंद शाखा
बाईं शाखा मानती है कि शर्तवाक्य इसलिए टिका क्योंकि उसका पूर्वांग गिरा - पर पंक्ति 5 में p पहले ही सत्य है, इसलिए शाखा स्वयं से टकराकर बंद हो जाती है। दाईं शाखा मानती है कि वह इसलिए टिका क्योंकि उसका उत्तरांग सत्य था - पर पंक्ति 4 में q पहले ही असत्य है, इसलिए वह भी बंद हो जाती है।
दोनों शाखाएँ बंद हुईं, इसलिए ¬p को असत्य रखते हुए p → q और ¬q को सत्य करने का कोई रास्ता नहीं। तर्क वैध है, और वृक्ष ही उसका कारण है। ध्यान दीजिए कि प्रमाण में न बारिश आई, न ज़मीन, न यह कि p और q किसके लिए खड़े हैं। उसे इनकी ज़रूरत ही नहीं पड़ी।
7. जब कोई शाखा खुली रह जाती है
हर तर्क वैध नहीं होता, और यहीं यह विधि अपना मोल चुकाती है। यदि आप किसी शाखा पर तब तक काम करें जब तक उस पर कुछ और विघटित करने को न बचे - केवल परमाणु और निषिद्ध परमाणु शेष रहें - और फिर भी वह बंद न हुई हो, तो वह शाखा संतृप्त और खुली है। वह इसलिए खुली नहीं रही कि आपने जल्दी रोक दिया। आज़माने को कुछ बचा ही नहीं।
खुली शाखा «अवैध» के निर्णय से कहीं अधिक है। उसके परमाणुओं के चिह्न पढ़िए और आपके पास एक निर्धारण है: T लगा हर परमाणु सत्य, F लगा हर परमाणु असत्य। यह निर्धारण हर आधारवाक्य को सत्य और निष्कर्ष को असत्य बनाता है, और प्रतिउदाहरण ठीक यही होता है। तर्कशास्त्री इसे प्रतिमॉडल कहते हैं, और यह «क्यों नहीं?» का ठोस उत्तर है, इनकार नहीं।
उत्तरांग की पुष्टि, p → q, q ⊨ p, पाठ्यपुस्तक वाली स्थिति है। उसका टैब्लो p असत्य और q सत्य पर एक शाखा खुली छोड़ देता है - एक ऐसी स्थिति जिसमें शर्तवाक्य टिकता है और उसका उत्तरांग भी टिकता है, फिर भी पूर्वांग नहीं टिकता। यह अकेला निर्धारण ही तर्क का खंडन कर देता है।
8. यह हमेशा समाप्त क्यों होती है
हर नियम किसी सूत्र की जगह उसी के उपसूत्र रख देता है, और हर उपसूत्र उस सूत्र से निश्चित रूप से छोटा होता है जिससे वह आया। इसलिए कोई शाखा सदा नहीं बढ़ सकती: हर कदम मूल तर्क के टुकड़ों की एक सीमित सीढ़ी उतरता है, और सीढ़ी का तल है। अंततः शाखा की हर पंक्ति एक परमाणु या उसका निषेध बन जाती है, और आगे करने को कुछ नहीं रहता।
यह सचमुच की गारंटी है, आशा नहीं। इसका अर्थ है कि यह विधि प्रतिज्ञप्ति-तर्कशास्त्र के लिए एक निर्णय-प्रक्रिया है: किसी भी तर्क पर चलाइए, वह रुकेगी - या तो बंद वृक्ष के साथ या खुली शाखा के साथ, कंधे उचकाकर कभी नहीं। इस साइट का प्रमाणक इसके ऊपर नोड की एक सीमा भी लगाता है, पर केवल इस बचाव के लिए कि कोई विकृत सूत्र ब्राउज़र टैब को न चूस ले - गणित को ऐसी किसी सीमा की ज़रूरत नहीं।
9. अन्य प्रमाण-प्रणालियाँ
टैब्लो कई प्रमाण-प्रणालियों में से एक है, और यह खंडन के आकार वाली है: यह विफलता को बाहर करके काम करती है। प्राकृतिक निगमन उलटी दिशा में चलता है और मोडस पोनेंस तथा सशर्त प्रमाण जैसे नियमों से आधारवाक्यों से आगे बढ़ते हुए निष्कर्ष खड़ा करता है, और वह उस ढंग से कहीं अधिक मिलता-जुलता पढ़ा जाता है जिस ढंग से गणितज्ञ गद्य में तर्क करता है। प्राकृतिक निगमन का प्रमाण आमतौर पर छोटा होता है; उसे ढूँढ़ने में आमतौर पर अधिक सूझ लगती है।
अनुक्रम-कलन स्वयं निष्पत्ति-चिह्न को औपचारिक बनाता है और निष्पत्ति के दावों को वस्तुओं की तरह बरतता है, जिससे वह प्रमाणों के बारे में कुछ सिद्ध करने का पसंदीदा औज़ार बन जाता है। रिज़ॉल्यूशन सब कुछ खंडों और एक ही नियम पर उतार लाता है, जो पढ़ने में फीका है और चलाने में बेहद तेज़ - अधिकांश स्वचालित प्रमाणक और SAT-सॉल्वर इसी पर बने हैं।
कौन-से प्रतिज्ञप्ति-तर्क वैध हैं, इस पर ये सब सहमत हैं; ये इसमें भिन्न हैं कि प्रमाण दिखता कैसा है और क्या ढूँढ़ना आसान है। सीखने के लिए सबसे मित्रवत टैब्लो हैं, क्योंकि यहाँ विफल प्रमाण मृत गली नहीं है - वह आपके हाथ में प्रतिउदाहरण थमा देता है।
10. अभ्यास
इस विधि को सीखने का सबसे तेज़ तरीका है इसे चलाना। कैलकुलेटर में ⊨, ⊢ या |= के साथ कोई तर्क लिखिए और टैब्लो सत्य-सारणी के बगल में खिंच जाएगा, ताकि आप वृक्ष को पंक्तियों से मिला सकें। फिर देखने से पहले कुछ प्रमाण कागज़ पर हल कीजिए।