ホーア論理

ホーア論理（ホーアろんり、）とは、公理的意味論の立場でプログラムの正当性について厳密に推論するために第一階述語論理を拡張した形式論理の言語を言う。

プログラムの正しさを証明するためのロバート・フロイドによる流れ図に関する方法を基に、計算機科学者のアントニー・ホーアによって提案された。

概要 
ホーア論理には、単純な命令型言語の全構成要素についての公理と推論規則が備わっている。当初の論文にあったそれら規則に加えて、ホーアや他の研究者は様々な言語要素に関する規則を開発した。並行性に関する規則、プロシージャに関する規則、分岐に関する規則、ポインタに関する規則などがある。

定義

部分的正当性（partial correctness） 
事前条件（precondition） P が成り立つときに、プログラム S を実行して、それが停止した場合においては必ず事後条件（postcondition） Q が成り立つならば、プログラム S は、事前条件 P と事後条件 Q とに関して部分的に正当（partially correct）であると言い、
P { S } Q
と記述する。ホーアによる元々の記法は上記のものであるが、一般的にはプログラム S の部分正当性は、
{ P } S { Q }
と記述されることが多い。

正当性（correctness） 
事前条件 P が成り立つときに、プログラム S を実行すると、その実行が必ず終了するならば、プログラム S は、事前条件 P に関して停止する（terminate）と言う。

プログラム S が部分的に正当かつ停止するものであるとき、すなわち、プログラム S が事前条件 P に関して停止し、停止後には必ず事後条件 Q が成り立つならば、プログラム S は、事前条件 P と事後条件 Q とに関して正当（correct）であるという。

部分的正当性の証明体系

(A1) 代入文の公理 
 { Q[e/x] } x:＝e { Q }
ここで、事前条件の Q[e/x] は置換であり、式 Q の中に出現するすべての x を式 e で置き換えた式を表す。一方で事後条件の Q は代入文実行後（置換ではなく代入を行ったあとの）x の値について式 Q が成り立つことを表す。

したがって、この公理は、
 { Q[e/x] }：式 Q 中の全ての x を e に置換するとき式 Q が成り立つのであれば、
 x:=e：（置換で成り立つならば、ほぼ同じような代入操作でも変わらないはずのため）式 Q 中の x の値を代入 x:=e で変更することで、
 { Q }：（置換の場合は成り立っているのであるから x の値が e に変更されたのであれば当然に）代入文実行後の式 Q は成り立つ、
というように読む。

(A2) 空文の公理 
空文（skip文）は、プログラムの状態を変化させないが、これを表すのが空文の公理である。skip以前に真であったことはそのまま真となる。
 { P } skip { P }

(R1) 複合文の規則 
一般に順序的プログラムは機能ごとに分解することができるが、その逆として分解した手続きは複合文として合成することができる。以下の複合文の規則は分解したプログラムが中間条件 R を介することで元の機能に合成されることを表している。

(R2) if文の規則

(R3) while文の規則 

ここで、P はループ不変条件である。

(R4) 帰結の規則

例 

{|style="text-align:left"
| style="background:silver;" colspan="4"|例 1
|-
|
|
|
|（代入の公理）
|-
|
|
|
|
|-
|
|
|
|（結果規則）
|-
| style="background:silver;" colspan="4"|例 2
|-
|
|
|
|（代入の公理）
|-
|
|
|
|（ ここで x と N は整数型）
|-
|
|
|
|（結果規則）
|}

脚注

参考文献 
 Robert D. Tennent: "Specifying Software" (ホーア論理を紹介している最近の教科書) ISBN 0-521-00401-2

関連項目 
 構造化プログラミング - 公理的意味論 - プログラム検証
 第一階述語論理 - 自然演繹
 Pascal

 Communicating Sequential Processes
 契約による設計
 述語変換意味論
 静的コード解析
 カリー・ハワード同型対応 - マーティン＝レーフの型理論（表明の代わりに型を利用したもの）

関連人物 
 エドガー・ダイクストラ
 ニクラウス・ヴィルト
 ペール・マルティン＝レーフ

外部リンク 
 KeY-Hoare - KeY という定理証明機上に構築された半自動検証システムで、ホーア論理を散りいれている。
 j-Algo-modul Hoare calculus — アルゴリズム視覚化プログラム j-Algo におけるホーア論理視覚化モジュール

プログラム論理
計算機科学における論理
形式手法
ソフトウェア工学
エポニム