होरे तर्क

होरे तर्क (फ्लोयड-होरे तर्क या होरे नियम के रूप में भी जाना जाता है) कंप्यूटर प्रोग्राम की शुद्धता के बारे में दृढ़ता से तर्क करने के लिए तार्किक नियमों के एक क्रम के साथ औपचारिक प्रणाली है। यह 1969 में ब्रिटिश कंप्यूटर वैज्ञानिक और तर्कशास्त्री टोनी होरे द्वारा प्रस्तावित किया गया था, और बाद में होरे और अन्य शोधकर्ताओं द्वारा परिष्कृत किया गया था।^[1] मूल विचार रॉबर्ट डब्ल्यू फ़्लॉइड के काम से उत्पन्न हुए थे, जिन्होंने फ्लोचार्ट के लिए समान प्रणाली^[2] प्रकाशित की थी।

होरे त्रिगुण

होरे तर्क की केंद्रीय विशेषता होरे त्रिगुण है। त्रिगुण बताता है कि कोड के एक टुकड़े का निष्पादन कैसे गणना की स्थिति को बदलता है। होरे त्रिगुण का रूप है

\{P\}C\{Q\}

जहां $P$ और $Q$ अभिकथन हैं और $C$ कमांड है।^{[note 1]} $P$ को पूर्व अवस्था और $Q$ को पश्च अवस्था नाम दिया गया है- जब पूर्व अवस्था पूर्ण हो जाती है, तो कमांड निष्पादित करने से पश्च अवस्था स्थापित हो जाती है। विधेय तर्क में अभिकथन सूत्र हैं।

होरे तर्क साधारण अनिवार्य प्रोग्रामिंग भाषा के सभी निर्माणों के लिए स्वयंसिद्ध और अनुमान नियम प्रदान करता है। होरे के मूल पेपर में सरल भाषा के नियमों के अलावा, होरे और कई अन्य शोधकर्ताओं द्वारा तब से अन्य भाषा निर्माणों के लिए नियम विकसित किए गए हैं। समवर्ती, प्रक्रियाओं, व्यतिक्रम, और संकेत के लिए नियम हैं।

आंशिक और कुल शुद्धता

मानक होरे तर्क का उपयोग करते हुए, केवल आंशिक शुद्धता ही सिद्ध की जा सकती है। कुल शुद्धता के लिए अतिरिक्त रूप से समाप्ति की आवश्यकता होती है, जिसे अलग से या जबकि नियम के विस्तारित संस्करण के साथ सिद्ध किया जा सकता है।^[3] इस प्रकार होरे त्रिगुण का सहज ज्ञान युक्त पठन है- जब भी $P$ , $C$ के निष्पादन से पहली अवस्था को धारण करता है, तो $Q$ बाद में धारण करेगा, या $C$ समाप्त नहीं होता है। बाद की स्थिति में, कोई "बाद" नहीं है, इसलिए $Q$ कोई भी कथन हो सकता है। वास्तव में, यह व्यक्त करने के लिए कि $C$ समाप्त नहीं होता है, असत्य होने के लिए कोई भी $Q$ चुन सकता है।

यहाँ और इस लेख के अन्य भागों में "समाप्ति" का अर्थ व्यापक अर्थों में है कि गणना अंततः समाप्त हो जाएगी, अर्थात यह अनंत छोरों की अनुपस्थिति का अर्थ है यह कार्यान्वयन सीमा के उल्लंघन (जैसे शून्य से विभाजन) की अनुपस्थिति को प्रोग्राम को समय से पहले रोकना नहीं दर्शाता है। अपने 1969 के पेपर में, होरे ने समाप्ति की एक संकीर्ण धारणा का उपयोग किया, जिसमें कार्यान्वयन सीमा के उल्लंघन की अनुपस्थिति भी सम्मिलित थी, और समाप्ति की व्यापक धारणा के लिए अपनी प्राथमिकता व्यक्त की क्योंकि यह कार्यान्वयन-स्वतंत्र होने का दावा करता है-^[4]

ऊपर उद्धृत सिद्धांतों और नियमों में एक और कमी यह है कि वे इस बात के प्रमाण के लिए कोई आधार नहीं देते हैं कि प्रोग्राम सफलतापूर्वक समाप्त हो गया है। समाप्त करने में विफलता अनंत लूप के कारण हो सकती है या यह कार्यान्वयन-परिभाषित सीमा के उल्लंघन के कारण हो सकता है, उदाहरण के लिए, संख्यात्मक संकार्य की सीमा, स्टोरेज का आकार, या ऑपरेटिंग सिस्टम की समय सीमा। इस प्रकार अंकन “ $P\{Q\}R$ ” की व्याख्या की जानी चाहिए "बशर्ते कि कार्यक्रम सफलतापूर्वक समाप्त हो जाए, इसके परिणामों के गुणों को $R$ द्वारा वर्णित किया गया है।" स्वयंसिद्धों को अनुकूलित करना काफी आसान है ताकि उन्हें गैर-समाप्ति प्रोग्रामों के "परिणामों" की भविष्यवाणी करने के लिए उपयोग नहीं किया जा सके लेकिन स्वयंसिद्धों का वास्तविक उपयोग अब कई कार्यान्वयन-निर्भर विशेषताओं के ज्ञान पर निर्भर करेगा, उदाहरण के लिए, कंप्यूटर का आकार और गति, संख्याओं की सीमा और अतिप्रवाह तकनीक का विकल्प। अनंत लूप से बचने के प्रमाण के अलावा, किसी प्रोग्राम की "सशर्त" शुद्धता को सिद्ध करना और चेतावनी देने के लिए कार्यान्वयन पर भरोसा करना सम्भवतः बेहतर है, यदि इसे कार्यान्वयन सीमा के उल्लंघन के परिणामस्वरूप प्रोग्राम के निष्पादन को त्यागना पड़ा हो।

नियम

रिक्त कथन स्वयंसिद्ध स्कीमा

रिक्त कथन नियम यह दावा करता है कि स्किप कथन प्रोग्राम की स्थिति को नहीं बदलता है, इस प्रकार स्किप से पहले जो भी सही है वह बाद में भी सही रहेगा।^{[note 2]}

{\dfrac {}{\{P\}{\texttt {skip}}\{P\}}}

नियत कार्य स्वयंसिद्ध स्कीमा

नियत कार्य स्वयंसिद्ध कहता है कि, नियत कार्य के बाद, कोई भी विधेय जो पहले नियत कार्य के दाईं ओर के लिए सही था, अब चर के लिए मान्य है। औपचारिक रूप से, मान लीजिए कि $P$ अभिकथन है जिसमें चर $x$ मुक्त है। तब-

{\dfrac {}{\{P[E/x]\}x:=E\{P\}}}

जहां $P[E/x]$ अभिकथन $P$ को दर्शाता है जिसमें $x$ की प्रत्येक मुक्त घटना को अभिव्यक्ति $E$ द्वारा प्रतिस्थापित किया गया है।

नियत कार्य स्वयंसिद्ध योजना का अर्थ है कि $P[E/x]$ का सत्य $P$ के बाद के नियत कार्य सत्य के बराबर है। इस प्रकार $P[E/x]$ नियत कार्य से पहले सत्य थे, नियत कार्य स्वयंसिद्ध द्वारा, फिर $P$ जिसके बाद सत्य होगा। इसके विपरीत, $P[E/x]$ असत्य (अर्थात $\neg P[E/x]$ सत्य) नियत कार्य कथन से पहले थे, $P$ को बाद में असत्य होना चाहिए।

मान्य त्रिगुण के उदाहरणों में सम्मिलित हैं-

$\{x+1=43\}y:=x+1\{y=43\}$
$\{x+1\leq N\}x:=x+1\{x\leq N\}$

सभी पूर्व अवस्था जो अभिव्यक्ति द्वारा संशोधित नहीं की जाती हैं उन्हें पश्च अवस्था पर ले जाया जा सकता है। प्रथम उदाहरण में, $y:=x+1$ निर्दिष्ट करने से यह तथ्य नहीं बदलता है कि $x+1=43$ है, इसलिए दोनों कथन पश्च अवस्था में दिखाई दे सकते हैं। औपचारिक रूप से, यह परिणाम $P$ के साथ स्वयंसिद्ध स्कीमा को लागू करके प्राप्त किया जाता है ( $y=43$ और $x+1=43$ ), जो $P[(x+1)/y]$ को ( $x+1=43$ और $x+1=43$ ) की उपज देता है, जिसे बदले में दिए गए पूर्व अवस्था $x+1=43$ के लिए सरलीकृत किया जा सकता है। नियत कार्य स्वयंसिद्ध योजना यह कहने के बराबर है कि पूर्व अवस्था को खोजने के लिए, पहले पश्च-अवस्था को लें और नियत कार्य के बाएं हाथ की सभी घटनाओं को नियत कार्य के दाईं ओर के साथ बदल दें। सावधान रहें कि सोचने के इस गलत तरीके से पालन करके यह पीछे की ओर करने की कोशिश न करें- $\{P\}x:=E\{P[E/x]\}$ यह नियम निरर्थक उदाहरणों की ओर जाता है जैसे-

\{x=5\}x:=3\{3=5\}

पहली नज़र में लुभाने वाली एक और गलत नियम $\{P\}x:=E\{P\wedge x=E\}$ है, यह निरर्थक उदाहरणों की ओर जाता है जैसे-

\{x=5\}x:=x+1\{x=5\wedge x=x+1\}

जबकि दिए गए पश्च अवस्था $P$ विशिष्ट रूप से पूर्व अवस्था $P[E/x]$ को निर्धारित करता है, इसका विपरीत सत्य नहीं है। उदाहरण के लिए-

$\{0\leq y\cdot y\wedge y\cdot y\leq 9\}x:=y\cdot y\{0\leq x\wedge x\leq 9\}$ ,
$\{0\leq y\cdot y\wedge y\cdot y\leq 9\}x:=y\cdot y\{0\leq x\wedge y\cdot y\leq 9\}$ ,
$\{0\leq y\cdot y\wedge y\cdot y\leq 9\}x:=y\cdot y\{0\leq y\cdot y\wedge x\leq 9\}$ , और
$\{0\leq y\cdot y\wedge y\cdot y\leq 9\}x:=y\cdot y\{0\leq y\cdot y\wedge y\cdot y\leq 9\}$

नियत कार्य स्वयंसिद्ध योजना के मान्य उदाहरण हैं।

होरे द्वारा प्रस्तावित नियत कार्य स्वयंसिद्ध तब लागू नहीं होता है जब एक से अधिक नाम एक ही संग्रहीत मान को संदर्भित कर सकते हैं। उदाहरण के लिए,

\{y=3\}x:=2\{y=3\}

यदि $x$ और $y$ एक ही चर (उपनाम) को संदर्भित करते हैं, तो यह गलत है, हालांकि यह नियत कार्य स्वयंसिद्ध योजना ( $\{P\}$ और $\{P[2/x]\}$ दोनों के साथ $\{y=3\}$ ) का उचित उदाहरण है।

रचना का नियम

Verifying swap-code
without auxiliary variables

The three statements below (line 2, 4, 6) exchange the values of the variables $a$ and $b$ , without needing an auxiliary variable. In the verification proof, the initial value of $a$ and $b$ is denoted by the constant $A$ and $B$ , respectively. The proof is best read backwards, starting from line 7; for example, line 5 is obtained from line 7 by replacing $a$ (target expression in line 6) by $a-b$ (source expression in line 6). Some arithmetical simplifications are used tacitly, viz. $a-(a-b)=b$ (line 5→3), and $a+b-b=a$ (line 3→1).
Nr	Code	Assertions
1:		$\{a=A\wedge b=B\}$
2:	$a:=a+b;$
3:		$\{a-b=A\wedge b=B\}$
4:	$b:=a-b;$
5:		$\{b=A\wedge a-b=B\}$
6:	$a:=a-b$
7:		$\{b=A\wedge a=B\}$

होरे की रचना का नियम क्रमिक रूप से निष्पादित प्रोग्रामों $S$ और $T$ पर लागू होता है, जहां $S$ $T$ से पहले निष्पादित करता है और $S;T$ को लिखा जाता है ( $Q$ को मध्य अवस्था कहा जाता है)-^[5]

{\dfrac {\{P\}S\{Q\}\quad ,\quad \{Q\}T\{R\}}{\{P\}S;T\{R\}}}

उदाहरण के लिए, नियत कार्य स्वयंसिद्ध के निम्नलिखित दो उदाहरणों पर विचार करें-

\{x+1=43\}y:=x+1\{y=43\}

और

\{y=43\}z:=y\{z=43\}

अनुक्रमण नियम द्वारा, एक निष्कर्ष निकाला गया-

\{x+1=43\}y:=x+1;z:=y\{z=43\}

एक अन्य उदाहरण सही बॉक्स में दिखाया गया है।

सशर्त नियम

{\dfrac {\{B\wedge P\}S\{Q\}\quad ,\quad \{\neg B\wedge P\}T\{Q\}}{\{P\}{\texttt {if}}\ B\ {\texttt {then}}\ S\ {\texttt {else}}\ T\ {\texttt {endif}}\{Q\}}}

सशर्त नियम में कहा गया है कि पश्च अवस्था $Q$ सामान्य है और अन्य भाग भी पूरे की पश्च अवस्था है यदि ...यदि अंत कथन।^[6] तत्कालीन और अन्य भाग में, अनपेक्षित और ऋणात्मक स्थिति $B$ को क्रमशः पूर्व अवस्था $P$ में जोड़ा जा सकता है। स्थिति, $B$ , के दुष्प्रभाव नहीं होने चाहिए। अगले भाग में उदाहरण दिया गया है।

यह नियम होरे के मूल प्रकाशन में निहित नहीं था।^[1] हालांकि, कथन के बाद से

{\texttt {if}}\ B\ {\texttt {then}}\ S\ {\texttt {else}}\ T\ {\texttt {endif}}

एक-बार के लूप निर्माण के समान प्रभाव होते है

{\texttt {bool}}\ b:={\texttt {true}};{\texttt {while}}\ B\wedge b\ {\texttt {do}}\ S;b:={\texttt {false}}\ {\texttt {done}};b:={\texttt {true}};{\texttt {while}}\ \neg B\wedge b\ {\texttt {do}}\ T;b:={\texttt {false}}\ {\texttt {done}}

सशर्त नियम अन्य होरे नियमों से व्युत्पन्न किया जा सकता है। इसी तरह, अन्य व्युत्पन्न प्रोग्राम निर्माणों के लिए नियम, जैसे लूप के लिए, लूप तक करें, स्विच करें, ब्रेक करें, जारी रखें को होरे के मूल पेपर से नियमों में परिवर्तन करके कम किया जा सकता है।

परिणाम नियम

{\dfrac {P_{1}\rightarrow P_{2}\quad ,\quad \{P_{2}\}S\{Q_{2}\}\quad ,\quad Q_{2}\rightarrow Q_{1}}{\{P_{1}\}S\{Q_{1}\}}}

यह नियम पूर्व अवस्था $P_{2}$ को मजबूत करने और/या पश्च अवस्था $Q_{2}$ को कमजोर करने की अनुमति देता है। इसका उपयोग किया जाता है उदाहरणार्थ तत्कालीन और अन्य भाग के लिए शाब्दिक रूप से समान पश्च अवस्था प्राप्त करना।

उदाहरण के लिए, का प्रमाण है

\{0\leq x\leq 15\}{\texttt {if}}\ x<15\ {\texttt {then}}\ x:=x+1\ {\texttt {else}}\ x:=0\ {\texttt {endif}}\{0\leq x\leq 15\}

सशर्त नियम को लागू करने की आवश्यकता है, जिसे सिद्ध करने की आवश्यकता है

\{0\leq x\leq 15\wedge x<15\}x:=x+1\{0\leq x\leq 15\}

, या सरलीकृत

\{0\leq x<15\}x:=x+1\{0\leq x\leq 15\}

तत्कालीन भाग के लिए, और

\{0\leq x\leq 15\wedge x\geq 15\}x:=0\{0\leq x\leq 15\}

, या सरलीकृत

\{x=15\}x:=0\{0\leq x\leq 15\}

दूसरे भाग के लिए।

हालाँकि, तत्कालीन भाग के लिए असाइनमेंट नियम को $P$ को $0\leq x\leq 15$ के रूप में चुनने की आवश्यकता है नियम लागू होता है इसलिए उत्पन्न होती हैl

\{0\leq x+1\leq 15\}x:=x+1\{0\leq x\leq 15\}

, जो तार्किक रूप से समतुल्य हैl

\{-1\leq x<15\}x:=x+1\{0\leq x\leq 15\}

.

सशर्त नियम के लिए आवश्यक पूर्व अवस्था $\{-1\leq x<15\}$ को नियत कार्य नियम से $\{0\leq x<15\}$ तक दृढ़ करने के लिए परिणाम नियम की आवश्यकता है।

इसी प्रकार, दूसरे भाग के लिए, नियत कार्य नियम उत्पन्न करता है

\{0\leq 0\leq 15\}x:=0\{0\leq x\leq 15\}

, या समकक्ष

\{{\texttt {true}}\}x:=0\{0\leq x\leq 15\}

,

इसलिए परिणाम नियम को $P_{1}$ और $P_{2}$ क्रमशः $\{x=15\}$ और $\{{\texttt {true}}\}$ के साथ लागू करना होगा, पूर्व अवस्था को फिर से दृढ़ करने के लिए।

अनौपचारिक रूप से, परिणाम नियम का प्रभाव "भूल जाना" है कि $\{x=15\}$ अन्य भाग के प्रवेश पर जाना जाता है, क्योंकि अन्य भाग के लिए उपयोग किए जाने वाले नियत कार्य नियम को उस जानकारी की आवश्यकता नहीं है।

जबकि नियम

{\dfrac {\{P\wedge B\}S\{P\}}{\{P\}{\texttt {while}}\ B\ {\texttt {do}}\ S\ {\texttt {done}}\{\neg B\wedge P\}}}

यहाँ $P$ लूप अचर है, जिसे लूप बॉडी $S$ द्वारा संरक्षित किया जाना है। लूप समाप्त होने के बाद, यह अचर $P$ अभी भी धारण करता है, और इसके अलावा $\neg B$ ने लूप को समाप्त करने का कारण बना दिया होगा। जैसा कि सशर्त नियम में है, $B$ के दुष्प्रभाव नहीं होने चाहिए।

उदाहरण के लिए, का प्रमाण

\{x\leq 10\}{\texttt {while}}\ x<10\ {\texttt {do}}\ x:=x+1\ {\texttt {done}}\{\neg x<10\wedge x\leq 10\}

जबकि नियम द्वारा सिद्ध करने की आवश्यकता है

\{x\leq 10\wedge x<10\}x:=x+1\{x\leq 10\}

, या सरलीकृत

\{x<10\}x:=x+1\{x\leq 10\}

,

जो नियत कार्य नियम द्वारा आसानी से प्राप्त हो जाता है। अंत में, पश्च अवस्था $\{\neg x<10\wedge x\leq 10\}$ को $\{x=10\}$ में सरलीकृत किया जा सकता है।

एक अन्य उदाहरण के लिए, जबकि नियम का उपयोग निम्नलिखित असामान्य प्रोग्राम को औपचारिक रूप से सत्यापित करने के लिए किया जा सकता है ताकि किसी मनमानी संख्या $a$ के सटीक वर्गमूल $x$ की गणना की जा सके, भले ही $x$ एक पूर्णांक चर हो और $a$ वर्ग संख्या न हो-

\{{\texttt {true}}\}{\texttt {while}}\ x\cdot x\neq a\ {\texttt {do}}\ {\texttt {skip}}\ {\texttt {done}}\{x\cdot x=a\wedge {\texttt {true}}\}

$P$ के सत्य होने के साथ, जबकि नियम लागू करने के बाद, यह सिद्ध करना शेष रह जाता है

\{{\texttt {true}}\wedge x\cdot x\neq a\}{\texttt {skip}}\{{\texttt {true}}\}

,

जो स्किप नियम और परिणाम नियम से अनुसरण करता है।

वास्तव में, असामान्य प्रोग्राम आंशिक रूप से सही है- यदि यह समाप्त हो गया, तो यह निश्चित है कि $x$ में (संयोग से) $a$ के वर्गमूल का मान होना चाहिए। अन्य सभी स्थितियों में, यह समाप्त नहीं होगा इसलिए यह पूरी तरह से सही नहीं है।

कुल शुद्धता के लिए जबकि नियम

यदि उपरोक्त सामान्य जबकि नियम को निम्नलिखित द्वारा प्रतिस्थापित किया जाता है, तो होरे गणना का उपयोग कुल शुद्धता, अर्थात समाप्ति के साथ-साथ आंशिक शुद्धता को सिद्ध करने के लिए भी किया जा सकता है। प्रायः प्रोग्राम शुद्धता की विभिन्न धारणाओं को इंगित करने के लिए धनु कोष्ठकों के स्थान पर वर्ग कोष्ठकों का उपयोग किया जाता है।

{\dfrac {<\ {\text{is a well-founded ordering on the set}}\ D\quad ,\quad [P\wedge B\wedge t\in D\wedge t=z]S[P\wedge t\in D\wedge t<z]}{[P\wedge t\in D]{\texttt {while}}\ B\ {\texttt {do}}\ S\ {\texttt {done}}[\neg B\wedge P\wedge t\in D]}}

इस नियम में, लूप अचर को बनाए रखने के अलावा, एक अभिव्यक्ति $t$ के माध्यम से समापन भी सिद्ध होता है, जिसे लूप चर कहा जाता है, जिसका मान प्रत्येक पुनरावृत्ति के दौरान कुछ क्षेत्र क्रम $D$ पर अच्छी तरह से स्थापित संबंध $<$ के संबंध में दृढ़ता से घटता है। चूंकि $<$ अच्छी तरह से स्थापित है, $D$ के सदस्यों की दृढ़ता से घटती श्रृंखला में केवल परिमित लंबाई हो सकती है, इसलिए $t$ सदैव के लिए घटता नहीं रह सकता है। (उदाहरण के लिए, सामान्य क्रम $<$ धनात्मक पूर्णांक $\mathbb {N}$ पर अच्छी तरह से स्थापित है, लेकिन न तो पूर्णांक $\mathbb {Z}$ पर और न ही धनात्मक वास्तविक संख्याओं $\mathbb {R} ^{+}$ पर ये सभी क्रम गणितीय अर्थ में हैं, कंप्यूटिंग अर्थ में नहीं, ये सभी विशेष रूप से अनंत हैं।)

लूप अचर $P$ को देखते हुए, स्थिति $B$ को यह बताना चाहिए कि $t$ , $D$ का न्यूनतम तत्व नहीं है, अन्यथा निकाय $S$ आगे $t$ को कम नहीं कर सकता है, अर्थात नियम का आधार असत्य होगा। (यह कुल शुद्धता के लिए विभिन्न संकेतन में से एक है।)^{[note 3]}

कुल शुद्धता के प्रमाण के लिए पिछले अनुभाग के प्रथम उदाहरण को फिर से प्रारम्भ करना

[x\leq 10]{\texttt {while}}\ x<10\ {\texttt {do}}\ x:=x+1\ {\texttt {done}}[\neg x<10\wedge x\leq 10]

कुल शुद्धता के लिए जबकि नियम लागू किया जा सकता है उदाहरण- $D$ सामान्य क्रम के साथ गैर-ऋणात्मक पूर्णांक है, और अभिव्यक्ति $t$ , $10-x$ है, जिसे बाद में सिद्ध करने की आवश्यकता होती है

[x\leq 10\wedge x<10\wedge 10-x\geq 0\wedge 10-x=z]x:=x+1[x\leq 10\wedge 10-x\geq 0\wedge 10-x<z]

अनौपचारिक रूप से, हमें यह सिद्ध करना होगा कि प्रत्येक लूप चक्र में $10-x$ की दूरी घट जाती है, जबकि यह सदैव गैर-ऋणात्मक रहती है, यह प्रक्रिया केवल सीमित संख्या में चक्रों के लिए ही चल सकती है।

पिछले प्रमाण लक्ष्य को सरल बनाया जा सकता है

[x<10\wedge 10-x=z]x:=x+1[x\leq 10\wedge 10-x<z]

,

जिसे इस प्रकार सिद्ध किया जा सकता है-

[x+1\leq 10\wedge 10-x-1<z]x:=x+1[x\leq 10\wedge 10-x<z]

नियत कार्य नियम द्वारा प्राप्त किया जाता है, और

[x+1\leq 10\wedge 10-x-1<z]

को दृढ़ किया जा सकता है

[x<10\wedge 10-x=z]

परिणाम नियम द्वारा है।

पिछले खंड के दूसरे उदाहरण के लिए, निश्चित रूप से कोई अभिव्यक्ति

t

नहीं पाई जा सकती है जो रिक्त लूप निकाय से कम हो जाती है, इसलिए समाप्ति सिद्ध नहीं की जा सकती हैl

यह भी देखें

↑ Hoare originally wrote " $P\{C\}Q$ " rather than " $\{P\}C\{Q\}$ ".
↑ This article uses a natural deduction style notation for rules. For example, ${\dfrac {\alpha ,\beta }{\phi }}$ informally means "If both $α$ and $β$ hold, then also $φ$ holds"; $α$ and $β$ are called antecedents of the rule, $φ$ is called its succedent. A rule without antecedents is called an axiom, and written as ${\dfrac {}{\quad \phi \quad }}$ .
↑ Hoare's 1969 paper didn't provide a total correctness rule; cf. his discussion on p.579 (top left). For example Reynolds' textbook^[3] gives the following version of a total correctness rule: ${\dfrac {P\wedge B\rightarrow 0\leq t\quad ,\quad [P\wedge B\wedge t=z]S[P\wedge t<z]}{[P]{\texttt {while}}\ B\ {\texttt {do}}\ S\ {\texttt {done}}[P\wedge \neg B]}}$ when $z$ is an integer variable that doesn't occur free in $P$ , $B$ , $S$ , or $t$ , and $t$ is an integer expression (Reynolds' variables renamed to fit with this article's settings).

संदर्भ

↑ ^1.0 ^1.1 Hoare, C. A. R. (October 1969). "An axiomatic basis for computer programming". Communications of the ACM. 12 (10): 576–580. doi:10.1145/363235.363259. S2CID 207726175.
↑ R. W. Floyd. "Assigning meanings to programs." Proceedings of the American Mathematical Society Symposia on Applied Mathematics. Vol. 19, pp. 19–31. 1967.
↑ ^3.0 ^3.1 John C. Reynolds (2009). प्रोग्रामिंग भाषाओं का सिद्धांत. Cambridge University Press.) Here: Sect. 3.4, p. 64.
↑ Hoare (1969), p.578-579
↑ Huth, Michael; Ryan, Mark (2004-08-26). कंप्यूटर विज्ञान में तर्क (second ed.). CUP. p. 276. ISBN 978-0521543101.
↑ Apt, Krzysztof R.; Olderog, Ernst-Rüdiger (December 2019). "होरे के तर्क के पचास साल". Formal Aspects of Computing. 31 (6): 759. doi:10.1007/s00165-019-00501-3. S2CID 102351597.

अग्रिम पठन

Robert D. Tennent. Specifying Software (a textbook that includes an introduction to Hoare logic, written in 2002) ISBN 0-521-00401-2

बाहरी संबंध

KeY-Hoare is a semi-automatic verification system built on top of the KeY theorem prover. It features a Hoare calculus for a simple while language.
j-Algo-modul Hoare calculus — A visualisation of the Hoare calculus in the algorithm visualisation program j-Algo

[3] Hoare originally wrote " $P\{C\}Q$ " rather than " $\{P\}C\{Q\}$ ".

[6] This article uses a natural deduction style notation for rules. For example, ${\dfrac {\alpha ,\beta }{\phi }}$ informally means "If both $α$ and $β$ hold, then also $φ$ holds"; $α$ and $β$ are called antecedents of the rule, $φ$ is called its succedent. A rule without antecedents is called an axiom, and written as ${\dfrac {}{\quad \phi \quad }}$ .

[9] Hoare's 1969 paper didn't provide a total correctness rule; cf. his discussion on p.579 (top left). For example Reynolds' textbook^[3] gives the following version of a total correctness rule: ${\dfrac {P\wedge B\rightarrow 0\leq t\quad ,\quad [P\wedge B\wedge t=z]S[P\wedge t<z]}{[P]{\texttt {while}}\ B\ {\texttt {do}}\ S\ {\texttt {done}}[P\wedge \neg B]}}$ when $z$ is an integer variable that doesn't occur free in $P$ , $B$ , $S$ , or $t$ , and $t$ is an integer expression (Reynolds' variables renamed to fit with this article's settings).

[hoare-1] 1.0 ^1.1 Hoare, C. A. R. (October 1969). "An axiomatic basis for computer programming". Communications of the ACM. 12 (10): 576–580. doi:10.1145/363235.363259. S2CID 207726175.

[2] R. W. Floyd. "Assigning meanings to programs." Proceedings of the American Mathematical Society Symposia on Applied Mathematics. Vol. 19, pp. 19–31. 1967.

[Reynolds.2009-4] 3.0 ^3.1 John C. Reynolds (2009). प्रोग्रामिंग भाषाओं का सिद्धांत. Cambridge University Press.) Here: Sect. 3.4, p. 64.

[5] Hoare (1969), p.578-579

[7] Huth, Michael; Ryan, Mark (2004-08-26). कंप्यूटर विज्ञान में तर्क (second ed.). CUP. p. 276. ISBN 978-0521543101.

[8] Apt, Krzysztof R.; Olderog, Ernst-Rüdiger (December 2019). "होरे के तर्क के पचास साल". Formal Aspects of Computing. 31 (6): 759. doi:10.1007/s00165-019-00501-3. S2CID 102351597.

[1]

[2]

[note 1]

[3]

[4]

[note 2]

[5]

[6]

[note 3]

Anonymous

Search

होरे तर्क

Namespaces

More

Page actions

Contents

होरे त्रिगुण

आंशिक और कुल शुद्धता

नियम

रिक्त कथन स्वयंसिद्ध स्कीमा

नियत कार्य स्वयंसिद्ध स्कीमा

रचना का नियम

सशर्त नियम

परिणाम नियम

जबकि नियम

कुल शुद्धता के लिए जबकि नियम

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

होरे तर्क

होरे त्रिगुण

आंशिक और कुल शुद्धता

नियम

रिक्त कथन स्वयंसिद्ध स्कीमा

नियत कार्य स्वयंसिद्ध स्कीमा

रचना का नियम

सशर्त नियम

परिणाम नियम

जबकि नियम

कुल शुद्धता के लिए जबकि नियम

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories