호어 논리
"오늘의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영어)이다. 호어 세 쌍은 명령을 실행하는 것이 계산 상태를 어떻게 바꾸는지 설명한다. 와 가 '''표명'''(assertion영어)이고 가 '''명령'''(command영어)일 때, 호어 세 쌍은 와 같은 형태이다.[20] 이때 는 '''전제 조건'''(precondition영어), 는 '''사후 조건'''(postcondition영어)으로, 위의 호어 세 쌍은 전제 조건이 충족된 상태에서 명령을 실행하였을 때 사후 조건이 성립함을 나타낸다. 각 표명은 1차 논리의 논리식이다.
호어 논리는 프로그램의 '''부분 정확성'''(partial correctness영어)만을 검증한다. 부분 정확성은 프로그램이 종료되었을 때 그 결과가 올바른지를 나타낸다. 만약 프로그램이 종료되지 않으면, 결과에 대한 어떠한 가정도 할 수 없으므로 호어 세 쌍은 유효하다.[21]
호어 논리는 명령형 프로그래밍의 모든 구성 요소에 대한 공리와 추론 규칙을 갖추고 있다. 최초의 논문에 있던 규칙 외에도 호어와 다른 연구자들은 병행성, 프로시저, 분기문, 포인터 등 다양한 언어 요소에 대한 규칙을 개발했다.[11]
사전 조건 P가 성립할 때, 프로그램 S를 실행하여 정지했을 경우 반드시 사후 조건 Q가 성립한다면, 프로그램 S는 사전 조건 P와 사후 조건 Q에 관해 '''부분적으로 정당'''(partially correct)하다고 말하며[11], P { S } Q라고 기술한다[12]. 호어의 원래 표기는 위와 같지만, 일반적으로 프로그램 S의 부분 정당성은 { P } S { Q }라고 기술되는 경우가 많다.[13][14]
3. 부분 정확성과 총 정확성
'''총 정확성'''(total correctness영어)을 증명하기 위해서는 프로그램이 '''종료'''(termination영어)하는지 추가로 검증해야 한다. 이는 별도의 방법을 사용하거나 반복문 규칙을 확장하여 증명할 수 있다.[21] 종료는 계산이 언젠가 완료되어 무한 루프가 없음을 의미한다. 그러나 0으로 나누기 등 구현 제한 위반으로 인한 프로그램 중지는 포함하지 않는다.[22]
프로그램 S가 사전 조건 P를 만족하는 상태에서 실행되어 정지했을 때 사후 조건 Q를 만족하면, S는 부분적으로 정당하다.[11] 또한, 프로그램 S가 사전 조건 P를 만족하는 상태에서 실행될 때 반드시 종료된다면, 프로그램 S는 사전 조건 P에 관해 종료된다고 한다.[11]
프로그램 S가 부분적으로 정당하고 종료되면, 프로그램 S는 사전 조건 P와 사후 조건 Q에 관해 정당하다.[11]
4. 추론 규칙
할당 공리는 다음과 같이 표현된다.x:=e
{ Q }
여기서 사전 조건 Q[e/x]는 '''치환'''으로, 식 Q에 나타나는 모든 x를 식 e로 치환한 식을 나타낸다. 반면 사후 조건 Q는 대입문 실행 후(치환'''이 아닌''' 대입을 수행한 후) x의 값에 대해 식 Q가 성립함을 나타낸다.[11]
공문(skip
문) 공리는 다음과 같다.
이는 프로그램의 상태를 변화시키지 않음을 나타낸다. 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]:
skip영어 문은 프로그램의 상태를 변경하지 않으므로, 실행 이전에 참이었던 것은 무엇이든 실행 이후에도 마찬가지로 참이다.[6]
4. 2. 할당 공리 도식
변수에 값을 할당하는 명령에 대한 공리 도식은 다음과 같다.:
여기서 `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`은 거짓이 된다.
몇 가지 예시:
주의할 점:
- 할당을 통해 바뀌지 않은 조건은 모두 결과로 넘어갈 수 있다. 예를 들어, `y := x + 1` 할당 이후에도 `x + 1 = 43`이라는 사실은 변하지 않으므로, `x + 1 = 43`은 결과 조건에 나타날 수 있다.
- 할당 공리 도식을 통해 전제 조건을 찾기 위해서는, 먼저 결과 조건을 선택한 후 할당의 좌변에 있는 모든 변수를 할당의 우변에 있는 표현으로 치환해야 한다.
- 는 올바르지 않은 규칙이다. 가 이 규칙의 반례이다.
- 또한 올바르지 않다. 가 이 규칙의 반례이다.
- 주어진 사후 조건 `P`가 전제 조건 `P[E/x]`을 유일하게 결정하는 반면, 역은 성립하지 않는다.
- 호어가 제안한 할당 공리는 둘 이상의 이름이 동일한 저장된 값을 참조할 수 있는 경우(앨리어싱) 적용되지 않는다. 예를 들어, `x`와 `y`가 동일한 변수를 참조하는 경우, 은 올바르지 않다.
4. 3. 합성 규칙
'''합성 규칙'''(rule of composition영어)은 다음과 같다.[24]:
프로그램 가 실행된 이후 프로그램 를 실행하는 (즉 , 를 순차적으로 실행하는) 프로그램을 으로 표기한다. 이때 는 '''중간 조건'''(midcondition영어)이라고 부른다.
예를 들어, 할당 공리의 다음 두 가지 예시
: ,
에서, 합성 규칙을 적용하여
:
와 같은 결론을 얻을 수 있다.
4. 4. 조건문 규칙
조건문 규칙(conditional rule영어)은 조건문의 정확성을 검증하는 데 사용되는 추론 규칙이다. 이 규칙은 조건 가 참일 때와 거짓일 때 각각의 경우를 분석한다. 조건이 참이면 부분의 문장 가 실행되고, 거짓이면 부분의 문장 가 실행된다. 이때, 두 경우 모두에서 만족해야 하는 사후 조건 가 전체 조건문 의 사후 조건이 된다.[25]부분에서는 전제 조건 에 조건 를 추가할 수 있고, 부분에서는 에 의 부정 를 추가할 수 있다. 조건 는 부작용이 없어야 한다.
조건문 규칙은 호어의 원본 논문에는 포함되어 있지 않다.[18] 그러나 조건문은 일회성 반복문과 동일한 효과를 가지므로, 다른 추론 규칙으로부터 유도할 수 있다. 예를 들어,
:
는
:
와 동일하다.
마찬가지로, 반복, 반복, , , 등 다른 프로그램 구성에 대한 규칙도 프로그램 변환을 통해 유도할 수 있다.
4. 5. 결과 규칙
'''결과 규칙'''(consequence rule영어)은 전제 조건을 강화하거나 사후 조건을 약화하는 규칙이다. 결과 규칙을 통해 얻는 새로운 호어 세 쌍은 일반적으로 전제가 되는 호어 세 쌍보다 약하지만, 원하는 것보다 더 강한 호어 세 쌍을 이미 증명하였을 때 구문론적으로 일치하는 호어 세 쌍을 얻기 위해 사용될 수 있다.예를 들어, 다음을 검증하자.
:
조건문 규칙을 적용하면, 다음을 증명하면 충분하다.
- (단순화: )
- (단순화: )
를 로 두고 할당 공리 도식을 적용하면 (단순화: )를 얻는다. 이 호어 세 쌍의 전제는 보다 약하므로, 결과 규칙을 적용하여 를 유도한다.
마찬가지로, 할당 공리 도식을 적용하면 (단순화: )를 얻는다. 이 호어 세 쌍의 전제는 보다 약하므로, 결과 규칙을 적용하여 를 유도한다.
결과 규칙은 너무 강한 전제로부터 얻는 정보 를 "잊어버리는" 효과를 준다. 왜냐하면 를 증명하기 위해서는 그만큼 강한 정보가 필요하지 않기 때문이다.
4. 6. 반복문 규칙
반복문 규칙은 주어진 프로그램의 반복문이 올바르게 작동하는지를 검증하는 데 사용되는 추론 규칙이다. 이 규칙은 반복 불변량(loop invariant)이라는 개념을 사용하여 반복문의 정확성을 증명한다. 반복 불변량은 반복문의 내용이 실행되는 동안 항상 참으로 유지되는 조건이다.반복문 규칙은 다음과 같이 표현된다.
:
여기서,
- `P`는 반복 불변량이다.
- `B`는 반복문의 조건이다.
- `S`는 반복문의 내용이다.
이 규칙은 반복문의 조건 `B`가 참이고 반복 불변량 `P`가 만족되는 상태에서 반복문의 내용 `S`를 실행하면, 실행 후에도 여전히 반복 불변량 `P`가 참으로 유지됨을 의미한다. 따라서 반복문이 종료된 후에는 `B`가 거짓이 되고 `P`는 여전히 참이 된다.
예를 들어, 다음 코드를 보자.
:
이 코드는 `x`가 10보다 작거나 같은 동안, `x`를 1씩 증가시키는 반복문이다. 이 코드는 반복문 규칙에 의해 다음을 증명하여 검증할 수 있다.
:
이는 `x < 10`을 만족하며 단순화하면, 와 같고, 할당 공리 도식을 통해 쉽게 증명할 수 있다.
또한, 반복문 규칙을 통해 프로그램의 부분 정확성을 증명할 수 있다. 예를 들어, 다음 코드는 임의의 수 `a`의 제곱근 `x`를 계산하는 프로그램이다.
:
이 프로그램은 반복문 규칙을 적용하여 부분적으로 정확하다는 것을 보일 수 있다. 즉, 만약 프로그램이 종료된다면 `x`는 `a`의 제곱근 값을 가지게 된다. 하지만 프로그램이 항상 종료된다는 보장은 없다.
4. 6. 1. 총 정확성과 반복문 규칙
호어 대수를 사용하여 총 정확성을 증명하기 위해 일반적인 반복문 규칙을 확장할 수 있다. 총 정확성은 부분 정확성과 종료를 모두 포함하는 개념이다. 이를 위해 중괄호 대신 대괄호를 사용하여 표기한다.확장된 반복문 규칙은 다음과 같다.
:
이 규칙에서는 반복 불변량 loop invariant|루프 불변식영어를 유지하는 것 외에도, 반복 변량 loop variant|루프 변량영어를 도입한다. 반복 변량은 어떤 집합 위의 정초 순서에 대해 값이 감소하는 표현식이다. ''<''는 정초 관계이므로, 안에서 무한히 감소하는 사슬은 존재하지 않는다. 따라서 ''t''는 무한히 감소할 수 없고, 유한 번의 반복 후에는 반복문이 종료된다는 것을 보장한다.[26]
예를 들어, 자연수 위의 순서 ''<''는 정초 관계이다. 반면, 정수 나 양의 실수 위의 순서 ''<''는 무한히 감소하는 수열을 만들 수 있으므로 정초 관계가 아니다.
반복 불변량 ''P''가 주어졌을 때, 조건 ''B''는 ''t''가 ''D''의 극소 원소가 아니어야 한다. 그렇지 않으면 반복문의 내용 ''S''가 ''t''를 더 감소시킬 수 없기 때문이다.
이전 절의 첫 번째 예시를 다시 살펴보면,
:
확장된 반복문 규칙을 사용하여 총 정확성을 증명할 수 있다. ''D''를 자연수 집합, ''t''를 로 놓으면, 다음을 증명해야 한다.
:
이는 매 반복마다 '종료까지 남은 거리' 가 음수가 아닌 상태를 유지하며 줄어든다는 것을 의미한다. 자연수의 감소 수열은 유한하므로, 반복문은 유한 번의 반복 후에 종료된다.
위 식은 다음과 같이 단순화할 수 있다.
:
이는 할당 규칙과 결과 규칙을 통해 증명할 수 있다.
- 할당 규칙에 의해 를 얻는다.
- 결과 규칙에 의해 를 로 강화할 수 있다.
반면, 이전 절의 두 번째 예시는 반복문이 비어있어 반복 변량을 찾을 수 없으므로 종료를 증명할 수 없다.
5. 예시
(대입 공리) | |||
(결과 규칙) |
(대입 공리) | |||
( 여기서 x와 N은 정수형) | |||
(결과 규칙) |
6. 관련 인물
- 에츠허르 데이크스트라
- 니클라우스 비르트
- 페르 마르틴뢰프
7. 읽을거리
- http://www.cs.queensu.ca/home/specsoft/ Specifying Software (호어 논리에 대한 소개가 포함된 교과서, 2002년)
참조
[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