맨위로가기

호어 논리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

호어 논리는 명령 실행이 계산 상태를 어떻게 변경하는지 설명하는 형식 논리 체계이다. 핵심은 호어 세 쌍으로, 전제 조건이 충족된 상태에서 명령을 실행했을 때 사후 조건이 성립함을 나타낸다. 호어 논리는 부분 정확성과 총 정확성을 검증하는 데 사용되며, 공리 및 추론 규칙을 제공하여 프로그램의 정확성을 증명한다. 주요 관련 인물로는 에츠허르 데이크스트라, 니클라우스 비르트, 페르 마르틴 뢰프 등이 있다.

더 읽어볼만한 페이지

  • 1969년 컴퓨팅 - 관계형 모델
    관계형 모델은 에드거 F. 코드가 제안한 2차원 테이블 형태의 데이터 모델로, 튜플과 속성으로 데이터를 구성하며 관계 대수 또는 관계 논리를 통해 데이터 연산을 수행하고 SQL의 기반이 된다.
  • 1969년 컴퓨팅 - 커리-하워드 대응
    커리-하워드 대응은 증명 시스템과 계산 모델 간의 동형성을 나타내며, 증명은 프로그램이고 증명하는 공식은 프로그램의 타입이라는 일반화를 통해 논리 프로그래밍의 기초가 되어 현대 타입 이론 연구에 큰 영향을 미쳤다.
  • 정적 프로그램 분석 - Perl::Critic
    Perl::Critic은 Perl 코드의 품질, 스타일, 오류를 검사하여 더 나은 코드를 작성하도록 돕는 정적 분석 도구이다.
  • 정적 프로그램 분석 - 포인터 분석
    포인터 분석은 프로그램 내 포인터가 가리키는 메모리 위치를 파악하는 정적 분석 기법으로, 프로그램 최적화, 버그 탐지, 보안 취약점 분석 등에 활용되지만, 정확도와 효율성 간의trade-off, 동적 특징 분석의 어려움 등의 과제를 안고 있다.
  • 컴퓨터 과학 내 논리 - 자동화된 추론
    자동화된 추론은 컴퓨터 프로그램을 사용하여 논리적 추론을 수행하는 인공지능 분야로, 수리 논리학의 발전과 초기 연구를 통해 자동 정리 증명 분야의 기틀을 마련했으며, AI 겨울을 겪었지만 소프트웨어 검증 등 다양한 분야에 활용되며 Coq, HOL Light 등의 증명 보조기가 개발되어 난제들의 형식적 증명에 기여했다.
  • 컴퓨터 과학 내 논리 - 혼 절
    혼 절은 하나의 긍정 리터럴만을 포함하는 분리절이며, 논리 프로그래밍, 자동 정리 증명, 데이터베이스 이론 등 여러 분야에 응용된다.
호어 논리
호어 논리
유형형식 검증
분야컴퓨터 과학
개발자토니 호어
개발일1969년
세부 사항
목표프로그램 정확성 증명
핵심 개념호어 삼중조
논리적 기반술어 논리
관련 개념표시적 의미론
공리적 의미론
정적 분석
활용
사용 분야프로그램 검증
소프트웨어 개발
예시
예시 설명{P} C {Q}는 프로그램 C를 실행하기 전에 조건 P가 참이고, C의 실행이 종료되면 조건 Q가 참임을 의미한다.

2. 호어 세 쌍

호어 논리의 핵심 특징은 '''호어 세 쌍'''(Hoare triple영어)이다. 호어 세 쌍은 명령을 실행하는 것이 계산 상태를 어떻게 바꾸는지 설명한다. PQ가 '''표명'''(assertion영어)이고 C가 '''명령'''(command영어)일 때, 호어 세 쌍은 \{P\} C \{Q\}와 같은 형태이다.[20] 이때 P는 '''전제 조건'''(precondition영어), Q는 '''사후 조건'''(postcondition영어)으로, 위의 호어 세 쌍은 전제 조건이 충족된 상태에서 명령을 실행하였을 때 사후 조건이 성립함을 나타낸다. 각 표명은 1차 논리의 논리식이다.

사전 조건 P가 성립할 때, 프로그램 S를 실행하여 정지했을 경우 반드시 사후 조건 Q가 성립한다면, 프로그램 S는 사전 조건 P와 사후 조건 Q에 관해 '''부분적으로 정당'''(partially correct)하다고 말하며[11], P { S } Q라고 기술한다[12]. 호어의 원래 표기는 위와 같지만, 일반적으로 프로그램 S의 부분 정당성은 { P } S { Q }라고 기술되는 경우가 많다.[13][14]

3. 부분 정확성과 총 정확성

호어 논리는 프로그램의 '''부분 정확성'''(partial correctness영어)만을 검증한다. 부분 정확성은 프로그램이 종료되었을 때 그 결과가 올바른지를 나타낸다. 만약 프로그램이 종료되지 않으면, 결과에 대한 어떠한 가정도 할 수 없으므로 호어 세 쌍은 유효하다.[21]

'''총 정확성'''(total correctness영어)을 증명하기 위해서는 프로그램이 '''종료'''(termination영어)하는지 추가로 검증해야 한다. 이는 별도의 방법을 사용하거나 반복문 규칙을 확장하여 증명할 수 있다.[21] 종료는 계산이 언젠가 완료되어 무한 루프가 없음을 의미한다. 그러나 0으로 나누기 등 구현 제한 위반으로 인한 프로그램 중지는 포함하지 않는다.[22]

프로그램 S가 사전 조건 P를 만족하는 상태에서 실행되어 정지했을 때 사후 조건 Q를 만족하면, S는 부분적으로 정당하다.[11] 또한, 프로그램 S가 사전 조건 P를 만족하는 상태에서 실행될 때 반드시 종료된다면, 프로그램 S는 사전 조건 P에 관해 종료된다고 한다.[11]

프로그램 S가 부분적으로 정당하고 종료되면, 프로그램 S는 사전 조건 P와 사후 조건 Q에 관해 정당하다.[11]

4. 추론 규칙

호어 논리는 명령형 프로그래밍의 모든 구성 요소에 대한 공리추론 규칙을 갖추고 있다. 최초의 논문에 있던 규칙 외에도 호어와 다른 연구자들은 병행성, 프로시저, 분기문, 포인터 등 다양한 언어 요소에 대한 규칙을 개발했다.[11]
할당 공리는 다음과 같이 표현된다.


  • { Q[e/x] } x:=e { Q }


여기서 사전 조건 Q[e/x]는 '''치환'''으로, 식 Q에 나타나는 모든 x를 식 e로 치환한 식을 나타낸다. 반면 사후 조건 Q는 대입문 실행 후(치환'''이 아닌''' 대입을 수행한 후) x의 값에 대해 식 Q가 성립함을 나타낸다.[11]
공문(skip문) 공리는 다음과 같다.

  • { P } skip { P }


이는 프로그램의 상태를 변화시키지 않음을 나타낸다. skip 이전에 참이었던 것은 그대로 참이 된다.
복합문 규칙은 다음과 같다.

{ P } S1 { R } , { R } S2 { Q }
{ P } S1 ; S2 { Q }



이는 분해된 프로그램이 중간 조건 R을 거쳐 원래 기능으로 합성되는 것을 나타낸다.[16]
조건문 규칙은 다음과 같다.

{ P ∧ B } S1 { Q } , { P ∧ ¬B } S2 { Q }
{ P } If B Then S1 else S2 End { Q }


축약형 조건문 규칙은 다음과 같다.

{ P ∧ B } S1 { Q } , P ∧ ¬B => Q
{ P } If B Then S1 End { Q }


반복문 규칙은 다음과 같다.

{ P & B } S1 { P }
{ P } While B Do S1 End { P & ¬B }



여기서 ''P''는 루프 불변 조건이다.[17]
결과 규칙은 다음과 같다.

P => P1 , { P1 } S { Q1 } , Q1 => Q
{ P } S { Q }


4. 1. 빈 명령 공리 도식

빈 명령(empty statement영어) 공리 도식은 다음과 같다.[23]

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

skip영어 문은 프로그램의 상태를 변경하지 않으므로, 실행 이전에 참이었던 것은 무엇이든 실행 이후에도 마찬가지로 참이다.[6]

4. 2. 할당 공리 도식

변수에 값을 할당하는 명령에 대한 공리 도식은 다음과 같다.

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

여기서 `P[E/x]`는 변수 `x`를 자유 변수로 갖는 명제 `P`에서 자유롭게 나타나는 `x`를 표현 `E`로 치환하여 얻은 명제를 나타낸다.

쉽게 설명하면, `P[E/x]`의 참, 거짓 여부는 할당 이후의 `P`의 참, 거짓 여부와 같다. 따라서 `P[E/x]`가 할당 이전에 참이라면 할당 이후 `P`는 참이다. 예를 들어, `x + 1 = 43`이 참일 때, `y := x + 1`을 실행하면 `y = 43`은 참이 된다.

반대로, `P[E/x]`가 할당 이전에 거짓이라면 할당 이후 `P`는 거짓이다. 예를 들어, `x + 1 = 43`이 거짓일 때, `y := x + 1`을 실행하면 `y = 43`은 거짓이 된다.
몇 가지 예시:

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

주의할 점:

  • 할당을 통해 바뀌지 않은 조건은 모두 결과로 넘어갈 수 있다. 예를 들어, `y := x + 1` 할당 이후에도 `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]`을 유일하게 결정하는 반면, 역은 성립하지 않는다.
  • 호어가 제안한 할당 공리는 둘 이상의 이름이 동일한 저장된 값을 참조할 수 있는 경우(앨리어싱) 적용되지 않는다. 예를 들어, `x`와 `y`가 동일한 변수를 참조하는 경우, \{ y = 3 \} x := 2 \{ y = 3 \}은 올바르지 않다.

4. 3. 합성 규칙

'''합성 규칙'''(rule of composition영어)은 다음과 같다.[24]

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

프로그램 가 실행된 이후 프로그램 를 실행하는 (즉 , 를 순차적으로 실행하는) 프로그램을 S;T으로 표기한다. 이때 는 '''중간 조건'''(midcondition영어)이라고 부른다.

예를 들어, 할당 공리의 다음 두 가지 예시

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

에서, 합성 규칙을 적용하여

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

와 같은 결론을 얻을 수 있다.

4. 4. 조건문 규칙

조건문 규칙(conditional rule영어)은 조건문의 정확성을 검증하는 데 사용되는 추론 규칙이다. 이 규칙은 조건 B가 참일 때와 거짓일 때 각각의 경우를 분석한다. 조건이 참이면 부분의 문장 S가 실행되고, 거짓이면 부분의 문장 T가 실행된다. 이때, 두 경우 모두에서 만족해야 하는 사후 조건 Q가 전체 조건문 의 사후 조건이 된다.[25]

부분에서는 전제 조건 P에 조건 B를 추가할 수 있고, 부분에서는 PB의 부정 \neg B를 추가할 수 있다. 조건 B는 부작용이 없어야 한다.

조건문 규칙은 호어의 원본 논문에는 포함되어 있지 않다.[18] 그러나 조건문은 일회성 반복문과 동일한 효과를 가지므로, 다른 추론 규칙으로부터 유도할 수 있다. 예를 들어,

:\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}

와 동일하다.

마찬가지로, 반복, 반복, , , 등 다른 프로그램 구성에 대한 규칙도 프로그램 변환을 통해 유도할 수 있다.

4. 5. 결과 규칙

'''결과 규칙'''(consequence rule영어)은 전제 조건을 강화하거나 사후 조건을 약화하는 규칙이다. 결과 규칙을 통해 얻는 새로운 호어 세 쌍은 일반적으로 전제가 되는 호어 세 쌍보다 약하지만, 원하는 것보다 더 강한 호어 세 쌍을 이미 증명하였을 때 구문론적으로 일치하는 호어 세 쌍을 얻기 위해 사용될 수 있다.

예를 들어, 다음을 검증하자.

:\{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 \})


P0 \le x \le 15로 두고 할당 공리 도식을 적용하면 \{0 \leq x+1 \leq 15\} x:=x+1 \{0 \leq x \leq 15\} (단순화: \{-1 \leq x < 15\} x:=x+1 \{0 \leq x \leq 15\})를 얻는다. 이 호어 세 쌍의 전제는 \{0 \leq x < 15\}보다 약하므로, 결과 규칙을 적용하여 \{0 \leq x < 15\} x:=x+1 \{0 \leq x \leq 15\}를 유도한다.

마찬가지로, 할당 공리 도식을 적용하면 \{0 \leq 0 \leq 15\} x:=0 \{0 \leq x \leq 15\} (단순화: \{\texttt{true}\} x:=0 \{0 \leq x \leq 15\})를 얻는다. 이 호어 세 쌍의 전제는 \{x = 15\}보다 약하므로, 결과 규칙을 적용하여 \{x=15\} x:=0 \{0 \leq x \leq 15 \}를 유도한다.

결과 규칙은 너무 강한 전제로부터 얻는 정보 \{x=15\}를 "잊어버리는" 효과를 준다. 왜냐하면 \{x=15\} x:=0 \{0 \leq x \leq 15 \}를 증명하기 위해서는 그만큼 강한 정보가 필요하지 않기 때문이다.

4. 6. 반복문 규칙

반복문 규칙은 주어진 프로그램의 반복문이 올바르게 작동하는지를 검증하는 데 사용되는 추론 규칙이다. 이 규칙은 반복 불변량(loop invariant)이라는 개념을 사용하여 반복문의 정확성을 증명한다. 반복 불변량은 반복문의 내용이 실행되는 동안 항상 참으로 유지되는 조건이다.

반복문 규칙은 다음과 같이 표현된다.

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

여기서,

  • `P`는 반복 불변량이다.
  • `B`는 반복문의 조건이다.
  • `S`는 반복문의 내용이다.


이 규칙은 반복문의 조건 `B`가 참이고 반복 불변량 `P`가 만족되는 상태에서 반복문의 내용 `S`를 실행하면, 실행 후에도 여전히 반복 불변량 `P`가 참으로 유지됨을 의미한다. 따라서 반복문이 종료된 후에는 `B`가 거짓이 되고 `P`는 여전히 참이 된다.

예를 들어, 다음 코드를 보자.

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

이 코드는 `x`가 10보다 작거나 같은 동안, `x`를 1씩 증가시키는 반복문이다. 이 코드는 반복문 규칙에 의해 다음을 증명하여 검증할 수 있다.

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

이는 `x < 10`을 만족하며 단순화하면, \{x < 10\} x := x + 1 \{x \leq 10 \} 와 같고, 할당 공리 도식을 통해 쉽게 증명할 수 있다.

또한, 반복문 규칙을 통해 프로그램의 부분 정확성을 증명할 수 있다. 예를 들어, 다음 코드는 임의의 수 `a`의 제곱근 `x`를 계산하는 프로그램이다.

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

이 프로그램은 반복문 규칙을 적용하여 부분적으로 정확하다는 것을 보일 수 있다. 즉, 만약 프로그램이 종료된다면 `x`는 `a`의 제곱근 값을 가지게 된다. 하지만 프로그램이 항상 종료된다는 보장은 없다.

4. 6. 1. 총 정확성과 반복문 규칙

호어 대수를 사용하여 총 정확성을 증명하기 위해 일반적인 반복문 규칙을 확장할 수 있다. 총 정확성은 부분 정확성과 종료를 모두 포함하는 개념이다. 이를 위해 중괄호 대신 대괄호를 사용하여 표기한다.

확장된 반복문 규칙은 다음과 같다.

:\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]}

이 규칙에서는 반복 불변량 loop invariant|루프 불변식영어를 유지하는 것 외에도, 반복 변량 loop variant|루프 변량영어를 도입한다. 반복 변량은 어떤 집합 위의 정초 순서에 대해 값이 감소하는 표현식이다. ''<''는 정초 관계이므로, 안에서 무한히 감소하는 사슬은 존재하지 않는다. 따라서 ''t''는 무한히 감소할 수 없고, 유한 번의 반복 후에는 반복문이 종료된다는 것을 보장한다.[26]

예를 들어, 자연수 \mathbb{N} 위의 순서 ''<''는 정초 관계이다. 반면, 정수 \mathbb{Z}양의 실수 \mathbb{R}^+ 위의 순서 ''<''는 무한히 감소하는 수열을 만들 수 있으므로 정초 관계가 아니다.

반복 불변량 ''P''가 주어졌을 때, 조건 ''B''는 ''t''가 ''D''의 극소 원소가 아니어야 한다. 그렇지 않으면 반복문의 내용 ''S''가 ''t''를 더 감소시킬 수 없기 때문이다.

이전 절의 첫 번째 예시를 다시 살펴보면,

:[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]로 강화할 수 있다.


반면, 이전 절의 두 번째 예시는 반복문이 비어있어 반복 변량을 찾을 수 없으므로 종료를 증명할 수 없다.

5. 예시

예시 1
\{x+1 = 43\}\!\ y:=x + 1\ \!\{ y = 43 \}\!(대입 공리)
( x + 1 = 43 \Leftrightarrow x = 42 )
\{x=42\}\!\ y:=x + 1\ \!\{y=43 \land x=42\}\!(결과 규칙)



예시 2
\{x + 1 \leq N \}\!\ x := x + 1\ \!\{x \leq N\}\ \!(대입 공리)
( x < N \implies x + 1 \leq N 여기서 xN은 정수형)
\{x < N \}\!\ x := x + 1\ \!\{x \leq N\}\ \!(결과 규칙)


6. 관련 인물

7. 읽을거리

참조

[1] 논문 An axiomatic basis for computer programming 1969-10
[2] 문서 Assigning meanings to programs. https://www.cs.tau.a[...] Proceedings of the American Mathematical Society Symposia on Applied Mathematics 1967
[3] 문서
[4] 서적 Theories of Programming Languages Cambridge University Press
[5] 문서
[6] 문서
[7] 서적 Logic in Computer Science http://www.cs.bham.a[...] CUP 2004-08-26
[8] 논문 Fifty years of Hoare's logic https://ir.cwi.nl/pu[...] 2019-12
[9] 문서
[10] 문서
[11] 문서
[12] 문서
[13] 문서
[14] 문서
[15] 문서
[16] 문서
[17] 문서
[18] 논문 https://dl.acm.org/d[...]
[19] 논문 https://www.cs.tau.a[...]
[20] 문서
[21] 서적
[22] 문서
[23] 문서
[24] 서적 http://www.cs.bham.a[...]
[25] 논문 https://ir.cwi.nl/pu[...]
[26] 문서



본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com