منطق هور

منطق هور (المعروف أيضًا باسم منطق فلويد–هور أو قواعد هور) هو نظام شكلي يحتوي على مجموعة من القواعد المنطقية للتفكير بشكل دقيق حول صحة برامج الكمبيوتر. تم اقتراحه في عام 1969 بواسطة عالم الكمبيوتر البريطاني والمنطق الرياضي توني هور، ثم تم تحسينه لاحقًا من قبل هور وباحثين آخرين. كانت الأفكار الأصلية قد بدأت بعمل روبرت فلويد، الذي نشر نظامًا مشابهًا للمخططات الانسيابية.

 الثلاثية بحسب هور 
الميزة المركزية في منطق هور هي ثلاثية هور، وهي تصف كيف تُغيّر قطعة من الشيفرة حالة الحوسبة بعد تنفيذها. تكون ثلاثية هور على الشكل:



حيث  و هما عبارتان شرطيّتان و هو أمر برمجي.كتب هور في الأصل "" بدلاً من "". تُسمّى  الشرط القبلي و الشرط البعدي: فعندما يتحقق الشرط القبلي، فإن تنفيذ الأمر  يؤدي إلى تحقق الشرط البعدي. العبارات الشرطية هي صيغ في منطق الرتبة الأولى.

يوفر منطق هور مسلمات وقواعد استدلال لجميع بنيات البرمجة الأمرية البسيطة. بالإضافة إلى القواعد المتعلقة باللغة البسيطة في ورقة هور الأصلية، فقد طُوّرت لاحقًا قواعد لبنيات لغوية أخرى من قِبل هور وغيرِه من الباحثين. وتشمل هذه القواعد ما يتعلق بـالتزامن، والدوال، وأوامر القفز، والمؤشرات.

 الصحة الجزئية والصحة الكلية 

باستخدام منطق هور القياسي، يمكن إثبات الصحة الجزئية فقط. أما الصحة الكلية، فهي تتطلب بالإضافة إلى ذلك إثبات الإنهاء، والذي يمكن إثباته بشكل منفصل أو باستخدام نسخة موسعة من قاعدة التكرار While. بالتالي، التفسير البديهي لثلاثية هور هو: كلما تحقق  من الحالة قبل تنفيذ ، فإن  سيتحقق بعد التنفيذ، أو أن  لن ينتهي. في الحالة الأخيرة، لا توجد "نهاية"، لذا يمكن أن تكون  أي عبارة كانت. في الواقع، يمكن اختيار  لتكون خاطئة للتعبير عن أن  لا ينتهي.

مصطلح "الإنهاء" هنا وفي باقي المقال يُفهم بالمعنى الأوسع: أن تنتهي الحوسبة في نهاية المطاف، أي أنه لا توجد حلقات لا نهائية؛ ولا يُشترط غياب أخطاء التنفيذ (مثل القسمة على صفر) التي قد توقف البرنامج مبكرًا. في ورقته عام 1969، استخدم هور تعريفًا أضيق للإنهاء يتضمن أيضًا غياب انتهاكات حدود التنفيذ، وقد أعرب عن تفضيله للتعريف الأوسع لأنه يجعل العبارات الشرطية مستقلة عن تفاصيل التنفيذ:

 القواعد 

 قاعدة العملية الفارغة 

تؤكد قاعدة العملية الفارغة أن التعليمة  لا تُغيّر حالة البرنامج، لذا فإن أي شرط يتحقق قبل  سيبقى محققًا بعدها.يستخدم هذا المقال أسلوب الاستنتاج الطبيعي لعرض القواعد. على سبيل المثال،  تعني بشكل غير رسمي "إذا تحقق كل من  و, فإن  يتحقق أيضًا"؛ وتسمى  و بالمقدمات، و بالنتيجة. القاعدة التي ليس لها مقدمات تُسمى مسلمة وتُكتب .



 قاعدة الإسناد 

تنص قاعدة الإسناد على أنه بعد تنفيذ الإسناد، فإن أي تعبير كان محققًا لجهة اليمين من الإسناد، سيتحقق للمتغير المُسنَد إليه. لنفترض أن  عبارة شرطية تحتوي على المتغير  كمُتغير حر. إذًا:



حيث  تعني العبارة الشرطية  بعد استبدال كل ظهور حر للمتغير  بالتعبير .

هذا يعني أن تحقق  قبل الإسناد يعادل تحقق  بعده. فلو كانت  صحيحة قبل الإسناد، فإن  ستكون صحيحة بعده، والعكس غير صحيح بالضرورة.

أمثلة على ثلاثيات صحيحة:



العبارات القبلية غير المتأثرة بالإسناد يمكن نقلها إلى العبارة البعدية. مثلًا، في المثال الأول، لا يتغير  بعد تنفيذ .

لكن هذه القاعدة لا تصح عندما يشير أكثر من اسم إلى نفس المكان في الذاكرة (كما في حالة الإشارة المشتركة). مثلًا:

تكون غير صحيحة إذا كان كل من  و يشيران لنفس الموقع.

 قاعدة التركيب 

تنطبق قاعدة التركيب على برنامجين ينفّذان بالتسلسل،  ثم ، ويُكتب ذلك ، حيث تُدعى  بـ"الشرط الوسيط":

مثال:

التسلسل يعطي:

 قاعدة الشرطية 

تنص القاعدة على أنه إذا تحققت  بعد كل من فرعي  و بشرط تحقيق  و أو نفي ، فإن  تتحقق بعد عبارة  بأكملها. ويجب ألا يكون للشرط  أي آثار جانبية. مثال يُقدّم في القسم التالي.

يجب ألّا تُحدِث الشرط  أي تأثيرات جانبية. يُقدَّم مثال في القسم التالي.

لم تكن هذه القاعدة واردة في منشور هور الأصلي.
ومع ذلك، بما أن العبارة

لها نفس تأثير البنية التكرارية لمرة واحدة التالية:

فإنه يمكن اشتقاق قاعدة الشرط من قواعد هور الأخرى.
وبطريقة مشابهة، يمكن تحويل القواعد الخاصة ببنى البرامج الأخرى المشتقة، مثل حلقة ، وحلقة ، وتعليمة ، و، و من خلال تحويل البرنام إلى القواعد الموجودة في ورقة هور الأصلية.

 قاعدة العاقبة 

تُتيح هذه القاعدة تقوية الشرط المسبق  و/أو إضعاف الشرط اللاحق .
تُستخدم هذه القاعدة مثلاً لتحقيق تطابق حرفي بين الشرطين اللاحقين في جزئي  و.

على سبيل المثال، لإثبات ما يلي:

يجب تطبيق قاعدة الشرط، والتي بدورها تتطلب إثبات:
، أو مبسطة

لجزء ، و
، أو مبسطة

لجزء .

ومع ذلك، تتطلب قاعدة الإسناد في جزء  اختيار  كـ ؛ وبالتالي تطبيق القاعدة يُعطي:
، وهو ما يعادل منطقياً
.
وبالتالي، تُستخدم قاعدة العاقبة لتقوية الشرط المسبق  المستنتج من قاعدة الإسناد إلى  المطلوب لقاعدة الشرط.

وبالمثل، لجزء ، تعطي قاعدة الإسناد:
، أو مكافئة
،
لذلك يجب تطبيق قاعدة العاقبة بحيث يكون  و هما  و على التوالي، لتقوية الشرط المسبق مرة أخرى. وبتعبير غير رسمي، فإن تأثير قاعدة العاقبة هو "نسيان" أن  كان معلوماً عند دخول جزء ، لأن قاعدة الإسناد المستخدمة لذلك الجزء لا تحتاج إلى هذه المعلومة.

 قاعدة while 

هنا،  هو ثبات الحلقة، الذي يجب الحفاظ عليه داخل جسم الحلقة .
بعد انتهاء الحلقة، يظل هذا الثبات  قائمًا، ويجب أيضًا أن تكون  قد تسببت في إنهاء الحلقة.
وكما في قاعدة الشرط، يجب ألا يُحدِث  أي تأثيرات جانبية.

على سبيل المثال، لإثبات:

باستخدام قاعدة while، يجب إثبات:
، أو مبسطة
،
وهو ما يُستنتج بسهولة من قاعدة الإسناد.
وأخيراً، يمكن تبسيط الشرط اللاحق  إلى .

كمثال آخر، يمكن استخدام قاعدة while للتحقق رسميًا من البرنامج الغريب التالي لحساب الجذر التربيعي الدقيق  لعدد عشوائي —حتى لو كانت  متغيرًا صحيحًا و عددًا غير مربعي:

بعد تطبيق قاعدة while مع كون  هو ، يتبقى إثبات:
،
وهو ما ينتج عن قاعدة التجاوز (skip) وقاعدة العاقبة.

في الواقع، هذا البرنامج الغريب صحيح جزئيًا فقط: إذا انتهى تنفيذه، فهذا يعني أن  قد احتوى صدفةً على الجذر التربيعي لـ .
أما في الحالات الأخرى، فلن ينتهي؛ لذا فهو ليس صحيحًا كليًا.

 قاعدة while للصحة الكلية 

إذا تم استبدال قاعدة while العادية أعلاه بالقاعدة التالية، يمكن استخدام حساب هور لإثبات الصحة الكلية، أي التوقف بالإضافة إلى الصحة الجزئية. وغالبًا ما تُستخدم الأقواس المربعة بدلاً من المعقوفة للإشارة إلى المفهوم المختلف لصحة البرامج:

في هذه القاعدة، بالإضافة إلى الحفاظ على ثبات الحلقة، يجب أيضًا إثبات إثبات التوقف عبر تعبير  يُعرف باسم متغيّر الحلقة، الذي تتناقص قيمته تناقصًا صارمًا وفق علاقة ترتيب  مؤسَّسة جيدًا على مجموعة  خلال كل تكرار.
وبما أن  مؤسسة جيدًا، فإن أي تسلسل تناقصي صارم لمتغيرات من  يكون نهائيًا؛ فلا يمكن أن يستمر  في التناقص إلى الأبد. (على سبيل المثال، الترتيب الاعتيادي  مؤسَّس جيدًا على الأعداد الصحيحة الموجبة ، لكنه ليس كذلك على  ولا على ؛ وكل هذه المجموعات تُفهم بالمعنى الرياضي لا الحاسوبي، وهي جميعًا لانهائية).

بما أن  هو ثبات الحلقة، يجب أن يُشير الشرط  إلى أن  ليس عنصرًا عنصرًا أدنى في ؛ وإلا فلن يتمكن جسم الحلقة  من إنقاص  أكثر، أي أن مقدم القاعدة سيكون خاطئًا. (هذه إحدى صيغ الصحة الكلية.)

وبالرجوع إلى المثال الأول في القسم السابق، لإثبات الصحة الكلية لـ

يمكن تطبيق قاعدة while للصحة الكلية باختيار  كالأعداد الصحيحة غير السالبة مع الترتيب الاعتيادي، والتعبير  كـ ، مما يتطلب بدوره إثبات:

وبتعبير غير رسمي، يجب إثبات أن المسافة  تتناقص في كل دورة من الحلقة، بينما تظل غير سالبة؛ مما يعني أن هذه العملية لا يمكن أن تستمر إلا لعدد محدود من الدورات.

يمكن تبسيط هدف الإثبات السابق إلى:
،
ويمكن إثبات ذلك على النحو التالي:
 يتم الحصول عليها باستخدام قاعدة الإسناد،
ويمكن تقويتها إلى  باستخدام قاعدة النتيجة.

في المثال الثاني من القسم السابق، من الواضح أنه لا يمكن العثور على أي تعبير  يتم إنقاصه بواسطة جسم الحلقة الفارغ، وبالتالي لا يمكن إثبات الانتهاء.

 انظر أيضًا 

 ملاحظات 

 المراجع 

 البيبليوغرافيا 












 روابط خارجية 
 KeY-Hoare هو نظام تحقق شبه تلقائي مبني على المسستنتج KeY، ويتضمن حساب هور للغة بسيطة تعتمد على حلقة while.
 وحدة حساب هور في j-Algo (j-Algo على غيت هاب، j-Algo على سورس فورج) – تصور مرئي لحساب هور ضمن برنامج تصور الخوارزميات j-Algo.

تصنيف:علم الحاسوب في 1969
تصنيف:تحليل البرنامج الساكن