안정적 모델 의미론

안정적 모델, 즉 답안 세트의 개념은 부정을 실패로 하는 논리 프로그램에 대한 선언적 의미론을 정의하는 데 사용된다. 이것은 프로그램 완료 및 충분한 근거가 있는 의미론과 함께 논리 프로그래밍에서 부정의 의미에 대한 몇 가지 표준 접근법 중 하나이다. 안정적인 모델 의미론은 응답 세트 프로그래밍의 기본이다.

동기

논리 프로그래밍에서 부정의 선언적 의미론에 대한 연구는 SLDNF 결의안의 행동 즉 규칙의 본문에 부정의 존재에 있어서 Prolog가 사용하는 SLD 분해능의 일반화가 고전적 명제 논리학에서 익숙한 진실 표와 완전히 일치하지 않는다는 사실에 의해 동기 부여되었다. 예를 들어 프로그램을 고려하십시오.

$p\displaystyle p\ }$

$왼쪽 화살표 p,\ q}$

${\displaystyle s\왼쪽 화살표 p,\\designname {not}q.}$

이 프로그램을 고려할 때, p는 p를 사실로 포함하기 때문에 성공할 것이다; q는 어떤 규칙의 머리에서 발생하지 않기 때문에 실패할 것이다. 머리에 r이 있는 유일한 규칙은 몸 속에 하위 골 q를 포함하고 있기 때문에 쿼리 r도 실패할 것이다. 우리가 보았듯이, 하위 골은 실패한다. 마지막으로 쿼리는 성공하는데, 이는 sub${\displaystyle q}$ ${\displaystyle \operatorname {not}q}$이(가) 아닌 각 하위 goals p가 성공하기$$ 때문이다. (후자는 해당 포지티브 목표 q가 실패하기 때문에 성공한다.) 요약하자면, 주어진 프로그램에 대한 SLDNF 결의의 동작은 다음과 같은 진실 할당으로 나타낼 수 있다.

p	q	r	s
T	F	F	T.

반면 콤마를 접속사 ${\displaystyle \land},$ 부정이 ${\displaystyle \$$operatorname {not}$이$($가) 아닌 기호인 {\displaystyle \$neg }$과$($와)로 식별하고 $F{\displaystyle }$ ${\displaystyle \leftarrow }$ ${\displaystyle G}$ ${\displaystysty F\leftarrow$ G$}$을 incollor G}으로$$ 처리하기로 동의하면 해당 프로그램의 규칙을 제안 공식으로 볼 수 있다.tion $G{\displaystyle }$→ ${\displaystyle F}$ ${\displaystyle G\오른쪽$ 화살표 $F}$이(가) 거꾸로 쓰여$$ 있다. 예를 들어, 주어진 프로그램의 마지막 규칙은, 이 관점에서, 명제 공식에 대한 대체 표기법이다.

$\displaystyle p\land \neg q\오른쪽 화살표 s.}$

위와 같은 진리 할당에 대한 프로그램 규칙의 진리 값을 계산하면 각 규칙이 T 값을 얻는 것을 알 수 있을 것이다. 다시 말해, 그 과제는 프로그램의 모델이다. 하지만 이 프로그램은 예를 들어 다른 모델도 가지고 있다.

p	q	r	s
T	T	T	F.

따라서 해당 프로그램의 모델 중 하나는 SLDNF 분해능의 동작을 올바르게 나타낸다는 점에서 특별하다. 그 모델을 특별하게 만드는 수학적 특성은 무엇인가? 이 질문에 대한 답은 안정적인 모델의 정의에 의해 제공된다.

비원론적 논리와의 관계

논리 프로그램에서의 부정의 의미는 비단조적 추론의 두 이론 즉, 자동적 논리와 디폴트 논리와 밀접한 관련이 있다. 이러한 관계의 발견은 안정된 모델 의미론의 발명을 향한 핵심 단계였다.

자동역학 논리의 구문은 무엇이 진실이고 무엇이 믿어지는지를 구별할 수 있는 모달 연산자를 사용한다. 마이클 겔폰드[1987]는 규칙의 본문에 있는$$ ${\displaystyle }$ ${\displaystyle p}$ ${\displaystyle \operatorname {not}p}$을(를) "${\displaystyle }$ ${\displaystyle p}$으로 읽지 않고 부정과 함께 규칙을 자동 인식 논리의 상응하는 공식으로 이해할 것을 제안했다. 안정적 모델 의미론들은 그 기본 형태에서, 자기 계발적 논리에 대한 명시적인 언급을 회피하는 이 사상의 개혁으로 볼 수 있다.

디폴트는 기본 논리에서는 추론 규칙과 유사하지만, 그 전제 및 결론 이외에 정당화라고 하는 공식의 목록을 포함한다. 채무불이행의 정당성이 현재 믿고 있는 것과 일관된다는 가정 하에 채무불이행의 결론을 도출하는 데 사용할 수 있다. 니콜 비도이트와 크리스틴 프로이데보[1987]는 규칙의 체내에서 부정된 원자를 정당화로서 취급할 것을 제안했다. 예를 들어, 규칙은

${\displaystyle s\왼쪽 화살표 p,\\designname {not}q}$

$\neg {\displaystyle \mathrm{}}$ ${\displaystyle q}$ ${\displaystyle \neg q}$이(가) 일관된다고$$ 가정할$$ 때 $p{\displaystyle }$ ${\displaystyle p}$에서 $s{\displaystyle }$ ${\displaystyle s}$을(를) 도출할 수 있는 기본값으로 이해할 수 있다. 안정적 모델 의미론에서는 같은 생각을 사용하지만, 명시적으로 디폴트 로직을 언급하지는 않는다.

안정적 모델

[Gelfond and Lifschitz, 1988년]에서 재현한 아래의 안정적 모델의 정의는 두 가지 규약을 사용한다. 첫째, 진리 배정은 T 값을 얻는 원자의 집합으로 식별된다. 예를 들어, 진실과제는

p	q	r	s
T	F	F	T.

세트${\displaystyle }${${\displaystyle p}$, ${\displaystyle s}$ ${\displaystyle \}}$ ${\displaystyle \{p,s\}$과(와) 동일하다$.$ 이 규약은 세트포함 관계를 사용하여 서로 진실 할당을 비교할 수 있도록 한다. 모든 진실 과제들 중 가장 작은 것 $\varnothing {\displaystyle \mathrm{}}$ ${\displaystyle \emptyet }$은 모든 원자를 거짓으로 만드는 것이다; 가장 큰 진실 과제는 모든 원자를 진실되게 만든다.

둘째, 변수를 포함하는 논리 프로그램은 그 규칙의 모든 기본 인스턴스 집합, 즉 모든 가능한 방법으로 프로그램 규칙의 변수에 변수가 없는 용어를 대체한 결과에 대한 속기로 간주된다. 예를 들어, 짝수 숫자의 논리 프로그래밍 정의

${\displaystyle \venname {even}\ }$

${\displaystyle \operatorname {even}(s(X))\좌측 화살표 \operatorname {not} \operatorname {even}(X)}$

이 프로그램에서 X를 접지 조건으로 교체한 결과로 이해됨

${\displaystyle 0,\s(0),\s(0),\displaystyle .}$

모든 방면에서 그 결과는 무한궤도프로그램이다.

${\displaystyle \venname {even}\ }$

${\displaystyle \venname {ven}(s(0))\좌측 화살표 \venname {not} \venname {ven}(0)}$

${\displaystyle \venname {even}(s(0))\좌측 화살표 \venname {not} \venname {s(0)}$

$\displaystyle \reason }$

정의

P를 양식의 규칙 집합으로 하자.

${\displaystyle A_{n1},\dots,B_{m},\operatorname {not}C_{1},\dots,\operatorname {n}$

여기서 $A{\displaystyle }$, ${\displaystyle {B\mathrm{}}_{}}$ ${\displaystyle 1_{}}$,${\displaystyle }$…${\displaystyle }$, B ${\displaystyle {}_{}}$, C ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$는 접지 원자다. 만약 P에 부정(${\displaystyle }$${\displaystyle }$= 0$${\$displaystyle$n=$0})$이 포함되어 있지 않다면, 정의에 따르면 P의 안정적인 유일한 모델은 세트포함 대비 최소인 모델이다.^[1] (부정이 없는 프로그램은 정확히 하나의 최소 모델을 가지고 있다.) 이 정의를 부정과 함께 프로그램의 경우로 확대하기 위해서는 다음과 같이 정의되는 환원제의 보조 개념이 필요하다.

지면 원자의 임의의 집합 I에 대해 I에 상대적인 P의 환원제는 원자 $C{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ C_{$i}$중 적어도 하나 이상의 원자가 몸 속에 있는$$ 것과 같은 모든 규칙을 먼저 떨어뜨림으로써 P로부터 얻은 부정 없는 규칙 집합이다.

${\displaystyle B_{1},\dots,B_{m},\operatorname {not}C_{1},\dots,\operatorname {not}C_{n}}}$

I에 속하며${\displaystyle ,}$ 그 다음 then ${\displaystyle {}_{}}$ 1 ,${\displaystyle }$…${\displaystyle 이}$ ${\displaystyle \mathrm{아닌}}$ 부품을${\displaystyle n_{}}$ C$$n {\$displaystyle \operatorname$ {$not}{1$},\$dots,\operatorname$ {$not}$C_${n$}}}에서$$ 제외한다.

우리는 내가 I에 비해 P의 환원제의 안정적 모델이라면 P의 안정적 모델이라고 말한다.(환원제가 부정성을 포함하고 있지 않기 때문에, 그 안정적 모델은 이미 정의되어 있다.) "안정적 모델"이라는 용어가 시사하듯이 P의 모든 안정적 모델은 P의 모델이다.

예

이러한 정의를 설명하려면 {p${\displaystyle }$, ${\displaystyle s\}}$ ${\displaystyle \{$p,$s\}이($가) 프로그램의 안정적인 모델인지 확인하십시오$$.

$p\displaystyle p\ }$

$왼쪽 화살표 p,\ q}$

${\displaystyle s\왼쪽 화살표 p,\\designname {not}q.}$

$\{{\displaystyle p}$, ${\displaystyle s}$ ${\displaystyle \}}$ ${\displaystyle \{p,s\}$에 상대적인 이 프로그램의 환원은 다음과 같다$$.

$p\displaystyle p\ }$

$왼쪽 화살표 p,\ q}$

$왼쪽 화살표 페이지$

(Indeed, since ${\displaystyle q\not \in \{p,s\}}$, the reduct is obtained from the program by dropping the part ${\displaystyle \operatorname {not} q.\ }$) The stable model of the reduct is ${\displaystyle \{p,s\}}$. (Indeed, this set of atoms satisfies every rule of the reduct, and it has no p같은 재산으로 자급자족하다.) 따라서 환원제의 안정적인 모델을 계산한 후, 우리는 우리가 시작했던$$ 같은 세트${\displaystyle }${${\displaystyle p}$ , ${\displaystyle s\}}$ ${\displaystyle \{p,s\}$에 도착했다. 결과적으로, 그 세트는 안정적인 모델이다.

원자 $p{\displaystyle }$ ,${\displaystyle \text{q}}$, ${\displaystyle \text{r}}$, s ${\displaystyle p,\ q,$ r$,\ s}$로 구성된 다른 15세트를 동일한 방법으로 점검하면 이 프로그램에 다른 안정적인 모델이 없음을 알 수 있다$$. 예를 들어$,{\displaystyle }$ {${\displaystyle p}$, ${\displaystyle q}$, ${\displaystyle r}$ ${\displaystyle \}}$ ${\displaystyle \{p,q,r\}}$에 상대적인 프로그램의 축소율은 다음과$$ 같다.

$p\displaystyle p\ }$

$왼쪽 화살표 p,\ q.}$

환원제의 안정적인 모델은 {${\displaystyle p}{\displaystyle \}}$ ${\displaystyle \{p\}$인데$,$ 우리가 시작한 세트$$ $\{{\displaystyle p}$ ,${\displaystyle q}$, ${\displaystyle r}$ ${\displaystyle \}}$ ${\displaystyle \{p,q,r\}$와는 다르다.

고유한 안정적 모델이 없는 프로그램

부정 프로그램이 있으면 안정적인 모델이 많거나 안정적인 모델이 없을 수 있다. 예를 들어, 그 프로그램은

${\displaystyle p\왼쪽 화살표 \vmname {not}q}$

$\displaystyle q\왼쪽 화살표 \designname {not}p}$

두 가지 안정적인 모델${\displaystyle }${${\displaystyle p\}}$ ${\displaystyle \{p$${\displaystyle }${${\displaystyle q\}}$ ${\displaystyle \{q$ 단일 규칙 프로그램

$\displaystyle p\leftarrow \chostname {not}p}$

안정적인 모델이 없다.

만일 우리가 안정적 모델 의미론을 부정의 존재에서 프롤로그의 행동에 대한 설명으로 생각한다면, 독특한 안정적 모델이 없는 프로그램들은 만족스럽지 못한 것으로 판단될 수 있다: 그들은 프롤로그 스타일 질의 응답에 대한 모호하지 않은 규격을 제공하지 않는다. 예를 들어, 위의 두 프로그램은 Prolog 프로그램, 즉 SLDNF 해결 프로그램이 종료되지 않기 때문에 합리적이지 않다.

그러나 응답 세트 프로그래밍에서 안정적인 모델을 사용하는 것은 그러한 프로그램에 대한 다른 관점을 제공한다. 그 프로그래밍 패러다임에서 주어진 검색 문제는 로직 프로그램으로 표현되어 프로그램의 안정적인 모델이 해법에 대응한다. 그러면 안정적인 모델이 많은 프로그램은 많은 해결책의 문제에 대응하고, 안정적인 모델이 없는 프로그램은 해결할 수 없는 문제에 대응한다. 예를 들어, 8명의 퀸즈 퍼즐은 92개의 해답을 가지고 있다; 답 세트 프로그래밍을 사용하여 해결하기 위해, 우리는 92개의 안정적인 모델을 가진 논리 프로그램으로 그것을 암호화한다. 이런 관점에서 볼 때, 대수에 정확히 하나의 루트가 있는 다항식처럼, 답안 세트 프로그래밍에 있어서, 정확히 하나의 안정적인 모델을 가진 논리 프로그램은 오히려 특별하다.

안정적 모형 의미론적 특성

이 절에서, 위와 같은 안정적 모델의 정의에서와 같이, 논리 프로그램에 의한 우리는 형식의 규칙들을 의미한다.

${\displaystyle A_{n1},\dots,B_{m},\operatorname {not}C_{1},\dots,\operatorname {n}$

여기서 $A{\displaystyle }$, ${\displaystyle {B\mathrm{}}_{}}$ ${\displaystyle 1_{}}$,${\displaystyle }$…${\displaystyle }$, B ${\displaystyle {}_{}}$, C ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$는 접지 원자다.

헤드 원자

원자 A가 논리 프로그램 P의 안정된 모델에 속한다면, A는 P의 규칙 중 하나의 머리일 것이다.

미니멀리티

로직 프로그램 P의 안정적 모델은 설정된 포함에 비해 P의 모델 중에서 최소이다.

안티케인 속성

만약 나와 J가 같은 논리 프로그램의 안정된 모델이라면 나는 J의 적절한 부분집합이 아니다. 즉, 프로그램의 안정된 모델 집합은 반체이다.

NP-완전성

유한한 지상 논리 프로그램이 안정적인 모델을 가지고 있는지 여부를 시험하는 것은 NP-완전이다.

실패로 부정하는 다른 이론과의 관계

프로그램완료

유한한 지상 프로그램의 어떤 안정된 모델도 프로그램 자체의 모델일 뿐만 아니라, 그 완성의 모델이기도 하다[마렉과 수브라만, 1989년]. 그러나 그 반대는 사실이 아니다. 예를 들어, 단일 규칙 프로그램의 완료

$왼쪽 화살표 p}$

tautology $p{\displaystyle }$ p${\displaystyle }$파운드 ${\displaystyle p}$ ${\displaystyle p\왼쪽$ 화살표 $p}$ 입니다$.$ 이 tautology의 모델$$ $【\displaystyle \emptyset }$은(는) ${\displaystyle p}$ $【\displaystyle p\leftarrow p}$의 안정적인 모델이지만$,$ 다른 모델${\displaystyle }${$}{$은(는)이 아니다$$. 프랑수아 페이즈[1994년]는 그러한 백범주를 없애고 프로그램 완성의 모든 모델의 안정성을 보장하는 논리 프로그램에서 통사적 조건을 찾았다. 그의 컨디션을 만족시키는 프로그램을 빡빡한 프로그램이라고 부른다.

팡전 린과 유팅 자오[2004]는 비긴축 프로그램의 완성을 더욱 강하게 만들어 안정적이지 못한 모든 모델이 제거되도록 하는 방법을 보여주었다. 이들이 완성도에 추가하는 추가 공식을 루프 공식이라고 한다.

근거가 충분한 의미론

논리 프로그램의 근거가 충분한 모델은 모든 접지 원자를 진실, 거짓, 그리고 알 수 없는 세 가지 세트로 분할한다. 만약 원자가 충분한 $근거$가$$있는 P {\$displaystyle$ P$}$ 모델에 참이라면, 그것은$$ $P{\displaystyle }$ ${\displaystyle P}$의 모든 안정된 모델에 속한다$.$ 그 반대는 대체로 타당하지 않다. 예를 들어, 그 프로그램은

${\displaystyle p\왼쪽 화살표 \vmname {not}q}$

$\displaystyle q\왼쪽 화살표 \designname {not}p}$

$왼쪽 화살표 p}$

$왼쪽 화살표 q}$

안정적인 모델 2개가 있는데$,{\displaystyle }$ {${\displaystyle p}$,${\displaystyle }$r ${\displaystyle \}}$ ${\displaystyle \{p,r\},$${\displaystyle }${${\displaystyle q,}$r\} ${\$$displaystyle$ $\}$ {\$displaystyle \{$$q,r$이(가$)$ 둘 다 소속이기는$$ 하지만 근거가 있는 모델에서 그 값은 알 수 없다.

더욱이, 만약 원자가 프로그램의 근거가 충분한 모델에서 거짓이라면, 그것은 그것의 안정된 모델에 속하지 않는다. 따라서 논리 프로그램의 근거가 충분한 모델은 안정된 모델의 교차점에 하한을 제공하고 결합에 상한을 제공한다.

강한 부정

불완전한 정보 표시

지식표현의 관점에서 보면 일련의 지상 원자는 지식의 완전한 상태에 대한 설명으로 생각할 수 있는데, 집합에 속하는 원자는 참이라고 알려져 있고 집합에 속하지 않는 원자는 거짓이라고 알려져 있다. 지식의 불완전한 상태는 일관적이지만 불완전한 리터럴 $집합$을 사용하여 설명할 수 있다. $원자{\displaystyle }$ p ${\displaystyle$ p$}$이(가) 세트에 속하지 않고$$ 부정도 세트에 속하지 않으면 $p{\displaystyle }$ ${\displaystyp p}$이(가) 참인지 거짓인지 알 수 없다.

논리 프로그래밍의 맥락에서, 이 아이디어는 두 종류의 부정, 즉 위에서 논의한 실패로서의 부정과 강한 부정의 구별을 필요로 하게 되는데$,{\displaystyle }$ 여기서 ~ ${\디스플레이$ 스타일 $\sim }$에 의해 가리켜진다$.$^[2] 두 종류의 부정의 차이를 보여주는 다음의 예는 존 매카시에 속한다. 스쿨버스는 접근하는 열차가 없다는 조건으로 철로를 건널 수 있다. 만약 우리가 기차가 접근하고 있는지 반드시 알지 못한다면, 부정을 실패로 사용하는 규칙

${\displaystyle {\hbox{Cross}\왼쪽 화살표 {\hbox{train}}}$

이 아이디어의 적절한 표현은 아니다: 그것은 다가오는 열차에 대한 정보가 없을 때 건너가도 괜찮다고 말한다. 신체에 강한 부정을 사용하는 약한 규칙은 다음과 같은 것이 바람직하다.

${\displaystyle {\hbox{Cross}\왼쪽 화살표 \,\sim {\hbox{Train}}.}$

기차가 접근하지 않는 것을 알면 건너도 괜찮다고 쓰여 있어.

일관성 있는 안정적인 모델

안정된 모델 이론에 강한 부정성을 포함시키기 위해, Gelfond와 Lifschitz[1991]는 규칙으로$$ $A{\displaystyle }$ ${\displaystyle$ A$\},$ ${\displaystyle B_{}}$ i ${\$ $C{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ 등의 표현들을 각각 허용했다.

${\displaystyle A_{n1},\dots,B_{m},\operatorname {not}C_{1},\dots,\operatorname {n}$

강한 부정 기호가 붙은 원자 또는 원자 둘 중 하나이다. 이 일반화는 안정적인 모델 대신, 강력한 부정으로 접두사 앞에 있는 원자와 원자를 모두 포함할 수 있는 해답 세트를 사용한다.

대안적 접근법[Ferraris and Lifschitz, 2005]은 강한 부정을 원자의 일부로 취급하며, 안정적 모델의 정의에 변화가 필요하지 않다. 이 강한 부정의 이론에서, 우리는 양과 음의 두 종류의 원자를 구별하고, 각각의 음의 원자는 형식의 표현이라고 가정한다$.{\displaystyle }$ - A ${\$$displaystyle$$\sim A$ $여기$서 A ${\$ A$\}$는 양의 원자다. 원자 집합은 원자 ${\displaystyle A}$,${\displaystyle }$~$A$의 "완성적인" 쌍을 포함하지 않는 경우에 일관성이라고 불린다$.$ 프로그램의 일관성 있는 안정적 모델은 [헬폰드와 $리프시츠, 1991년]$이라는 의미에서 일관된 대답 집합과 동일하다.

예를 들어, 그 프로그램은

${\displaystyle p\왼쪽 화살표 \vmname {not}q}$

$\displaystyle q\왼쪽 화살표 \designname {not}p}$

${. displaystyle r\ })$

${\displaystyle \sim r\leftarrow \vmsname {not}p}$

두 가지 안정적인 모델이 있는데$,{\displaystyle }$ {${\displaystyle p,}$ r ${\displaystyle \}}$ ${\$과${\displaystyle (}$와$)$ {${\displaystyle q,}$r,\$sim$r\}, {q${\displaystyle ,r}$,}, ${\displaystyle r}$,${\displaystyle }$~${\displaystyle }$} ${\displaystyle \{q,r,\$sim r$\}$ 입니다$.$ 첫 번째 모델은 일관성이 있으며, 두 번째 모델은 원자 r ${\displaystyle$\ r$}$과 원자${\displaystyle r}$ ${\displaystyle \\sim$ r$}$을 모두 $포함$하기 때문에 그렇지 않다$.$

폐쇄 세계 가정

[겔폰드와 $리프시츠,$ 1991년$]$에 따르면 술어 $p$에 대한 폐쇄적인 세계 $가정$은 규칙으로 표현될 수 있다$$$.$

${\displaystyle \sim p(X_{1},\dots,X_{n})\좌측 화살표 \operatorname {not}p(X_{1},\dots,X_{n}}}}}$

(관계 $p{\displaystyle }$ ${\$은(는$$) 튜플 X ${\displaystyle {1\mathrm{}}_{}}$, ${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$에 대해 고정되지 않는다$$. 예를 들어, 프로그램의 안정적 모델

$p(a,b)\ }$

$p(c,d)\ }$

${\displaystyle \sim p(X,Y)\왼쪽 화살표 \operatorname {not}p(X,Y)}$

2개의 양원자로 이루어져 있다.

$p(a,b),\p(c,d)\ }$

14개의 음의 원자

$\displaystyle \sim p(a,a),\\sim p(a,c),\\\simp }$

즉, $p{\displaystyle ,}$ ${\displaystyle \text{a},}$ ${\displaystyle \text{b},}$ ${\displaystyle \text{c},}$ ${\displaystyle \text{d}}$ ${\displaystyle p, a, b, b,$ c, $d}$로부터 형성된 다른 모든 양의 지면 원자의 강한 부정$.$

강한 부정이 있는 논리 프로그램은 그것의 술어 중 일부에 대한 폐쇄적인 세계 가정 규칙을 포함할 수 있고 다른 술어는 개방 세계 가정 영역에 둘 수 있다.

제약 조건이 있는 프로그램

안정적인 모델 의미론은 위에서 논의한 "전통적인" 규칙 모음 이외의 많은 종류의 논리 프로그램으로 일반화되었다. 즉, 형식의 규칙.

${\displaystyle A_{n1},\dots,B_{m},\operatorname {not}C_{1},\dots,\operatorname {n}$

여기서 $A{\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, B ${\displaystyle m_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle C_{}}$ n ${\$는 원자다$$. 프로그램에서 제약 조건을 포함할 수 있는 간단한 확장 기능(빈 헤드가 있는 규칙:

${\displaystyle \leftarrow B_{1},\dots,B_{m},\operatorname {not}C_{1},\dots,\operatorname {n}.}$

쉼표를$$negination$({\displaystyle \mathrm{}}$부정$)$이 ${\displaystyle \mathrm{아닌}}$ {\displaystyle \$playstyle \land},$ $부정$이 {\$displaystyle \$$neg$}인 ${\$$displaystyle$\neg $}$과$($와$)$로 $식별$하고 F${\displaystyle g}$ G$${\$displaystystyleftime G}$을(제안)로$$ 처리하기로 동의하면 전통적인 규칙을 제안 공식의 대체 표기법으로 볼 수 있다는 점을 상기하십시오. 함축성 $G{\displaystyle }$→ ${\displaystyle F}$ ${\displaystyle G\rightarrow F}$는 거꾸로$$ 쓰여 있다. 이 관례를 구속조건으로 확장하기 위해, 우리는 그 본체에 해당하는 공식의 부정으로 제약조건을 식별한다.

$\displaystyle \neg (B_{1}\land \cdots \land B_{m}\land \cdots \land \land \neg C_{n}).}$

우리는 이제 안정적 모델의 정의를 제약이 있는 프로그램으로 확장할 수 있다. 전통적인 프로그램의 경우처럼 부정(negation)이 포함되지 않은 프로그램부터 시작한다. 그러한 프로그램은 일관성이 없을 수 있다. 그러면 우리는 그것이 안정적인 모델을 가지고 있지 않다고 말한다. 이러한 프로그램 $P{\displaystyle }$ ${\displaystyle P}$이(가) 일관성이 있다면$$ $P{\displaystyle }$ ${\displaystyle P}$은(는) 고유한 최소 모델을 가지며$$, 이 모델은 $P{\displaystyle }$ ${\displaystyle P}$의 유일한 안정적인 모델로 간주된다$.$

다음으로, 제약조건이 있는 임의 프로그램의 안정적 모델은 전통적인 프로그램의 경우와 같은 방식으로 형성된 환원제를 사용하여 정의된다(위의 안정적 모델의 정의 참조). 원자의 $집합$ $I{\displaystyle }$ ${\displaystyle$ I$}$은(는) $I{\displaystyle }$ ${\displaystyle I}$에 $상대적$인 P ${\displaystyle P}$의 환원제가 안정적인 모델을 가지며$$, 그 안정 모델은 $I{\displaystyle }$ ${\displaystyle I}$과(는) 같을 경우 제약이 있는$$ 프로그램 $P{\displaystyle }$ ${\displaystyle P}$의 안정적인 모델이다$.$

전통적 프로그램에 대해 위에 기술된 안정적 모델 의미론의 특성도 제약조건이 존재한다.

로직 프로그램 $P{\displaystyle }$ ${\displaystyle P}$에 제약을 추가하는 것은 매우 간단한 방법으로$$ $P{\displaystyle }$ ${\displaystyle P}$의 안정적 모델 수집에 영향을$$ 미치기 때문에 제약조건은 응답 세트 프로그래밍에서 중요한 역할을 한다. 즉, $제약조건$과 제약조건 $C{\displaystyle }$ ${\displaystyle C}$이(가) 있는$$$$모든 $프로그램$ P {\$displaystyle$P${\displaystyle \}}$에 대해$,$ P${\displaystyle \{}$ {$}{\displaystyle$$P$\$cup \C\}$의 $안정모델$은 C ${\displaysty C$}을 만족시키는 $P$ ${\displaystyp}$의 안정모델로 특징 지을 수 있다$$$.$

불연속 프로그램

분리 규칙에서 머리는 여러 원자의 분리일 수 있다.

${\displaystyle A_{1};\dots ;A_{k}\왼쪽 화살표 B_{1},\dots ,B_{m},\operatorname {not} C_{1},\dots ,\operatorname {n}$

( 세미콜론은 분리 $\vee {\displaystyle }$ ${\displaystyle \lor }$의 대체 표기법으로 간주된다.)$$ 전통적인 규칙은 ${\displaystyle \mathrm{k}}$= 1 ${\displaystyle k=1}$에 해당하고$,$ ${\displaystyle \mathrm{제약조건}}$은 $k{\displaystyle }$= 0 {\$displaystyle$ k$=0$ 안정적 모델 의미론을 분리 프로그램으로 확장하기 위해, 우리는 먼저 부정(${\displaystyle }$ 규칙에서$$ n${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle n=0})$이 없을 때 프로그램의 안정적 모델이 된다는 것을 정의한다. 미니멀한 모델 분리 프로그램에 대한 환원제의 정의는 이전과 동일하게 유지된다. 원자의 집합$$ $I{\displaystyle }$ ${\displaystyle$ $I}$이(가$)$ $I{\displaystyle }$ ${\displaystyle I$에 상대적인 $P{\displaystyle }$ ${\displaystyle P}$의 환원제의 안정적인 모델인$$ 경우$$, 원자의 집합 I {\displaystyle $I$$}$은(는) $P{\displaystyle }$ ${\displaystystystyle$ P$}$의 안정적인 모델이다.

예를 들어$,{\displaystyle }$ 세트 {${\displaystyle p}$, r ${\displaystyle \}}$ ${\displaystyle \{p,r\}$은(는) 이격 프로그램의 안정적인 모델이다$$.

$(\displaystaystyle p;q\ }$

${\displaystyle r\leftarrow \vmsname {not}q}$

왜냐하면 그것은 환원제의 두 가지 최소 모델 중 하나이기 때문이다.

$(\displaystaystyle p;q\ }$

$R.\ }$

위의 프로그램에는 안정적인 모델이 하나 더 있으며$,{\displaystyle }$ {${\displaystyle q}$ ${\displaystyle \}}$ ${\displaystyle \{q$

$전통적$인 프로그램의 경우처럼, $P{\displaystyle }$$[\displaystyle$ $P$$}$의 규칙 중 하나의 머리에서 발생한다는 점에서$,$ 이항 프로그램 P[\displaystyle P}의 어떤 안정된 모델의 각 요소는 $P{\displaystyle }$ ${\displaystyle$ $P$$}$의 헤드 원자$.$ 전통적인 경우처럼, 이항 프로그램의 안정적 모델은 최소한이다.안티케인을 형성하다 유한 이분법 프로그램에 안정적인 모델이 있는지 여부를 시험하는 것은 $is{\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {2\mathrm{}}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\$ -완료$$ [Eiter and Gottlob, 1993]이다.

명제 공식 집합의 안정적인 모델

규칙들, 그리고 심지어 이분법적인 규칙들은 자의적인 명제 공식과 비교하여 다소 특별한 통사적 형태를 가지고 있다. 각 이분법칙은 본질적으로 그 선행(규칙의 본체)이 문자의 결합이고, 그 결과(머리)는 원자의 분리라는 암시가 있다. David Pearce [1997]와 Paolo Peraris[2005]는 안정적인 모델의 정의를 임의의 제안 공식으로 확장하는 방법을 보여주었다. 이 일반화는 세트 프로그래밍에 응답하는 응용 프로그램이 있다.

피어스의 제형은 안정된 모델의 원래 정의와는 매우 다르게 보인다. 환원제 대신 평형논리학, 즉 크립케 모델에 기초한 비단조논리의 체계를 가리킨다. 반면에 페라리스의 제형은 위에서 설명한 것과 다르게 환원제를 구성하는 과정은 다르지만 환원제를 기반으로 한다. 명제 공식 집합에 대한 안정적인 모델을 정의하는 두 가지 접근방식은 서로 동등하다.

안정 모형의 일반적 정의

[Ferraris, 2005]에 따르면 $원자$의 집합$$ I ${\displaystyle I}$에 상대적인 명제 공식 $F{\displaystyle }$ ${\displaystyle F}$의 환원은 $I{\displaystyle }$ ${\displaystyle$ $I$$}$이(가) 충족하지 않는 각 최대 보조 공식을 논리적 상수${\displaystyle \mathrm{}}$⊥ ${\displaystyle \b$)로$$ 대체함으로써$$ F${\$에서 얻은 공식이다.$ot }($거짓말). $I{\displaystyle }$ ${\displaystyle I}$에 상대적인 명제 공식의$$ 집합 $P{\displaystyle }$ ${\displaystyle P}$의 환원제는 $I{\displaystyle }${\$displaystyle$I}에$$ $상대적$인 P ${\displaystyle P$}의 모든 공식의 환원제로 구성된다$.$ 이항 프로그램의 경우처럼 원자의$$ $집합{\displaystyle }$ I ${\displaystyle I}$은 $P$의 안정적인 모델이라고 한다.${\displaystyle }$$I{\displaystyle }$ ${\displaystyle I}$이(가) I ${\displaystyle I$에 상대적인 $P{\displaystyle }$ ${\displaystyle P}$의 환원 모델 중에서 최소인 경우$$(설정 포함에 관련) ${\displaystyle P}$

예를 들어, 집합의 축소

$\displaystyle \{p,\p\land q\rightarrow r,\p\land \neg q\rightarrow s\}}$

$\{{\displaystyle p}$, ${\displaystyle s}$ ${\displaystyle \}}$에$$대해 {\$displaystyle \{p,$s\}은$$(는)

$\displaystyle \{p,\\bot \rightarrow \bot,\p\land \neg \bot \rightarrow s\}}$

$\{{\displaystyle p}$, ${\displaystyle s}$ ${\displaystyle \}}$ ${\displaystyle \{p,s\}}$은(는) 환원제의 모델이고, 해당 세트의 적절한 하위 집합은 환원제의 모델이 아니기 때문에$,{\displaystyle }$ {${\displaystyle p}$, s${\displaystyle \}}$ ${\displaystyle \{p,s\}$은 주어진 공식 집합의 안정적인 모델이다$$.

${\displaystyle \mathrm{우리}}$는${\displaystyle }$또한${\displaystyle }${${\displaystyle p}$ , s$}$ {\$displaystyle \{p,$s\}}이(가) 원래 정의의 의미에서 로직 프로그래밍 표기법으로 쓰여진 동일한 공식의 안정적인 모델이라는$$ 것을 보았다. 이것은 일반적인 사실의 한 예다: 전통적인 규칙에 따른 일련의 (공식)에 적용했을 때, 페라리스에 따른 안정적인 모델의 정의는 원래 정의와 동등하다. 제약이 있는 프로그램과 분리형 프로그램도 더 일반적으로 마찬가지다.

일반안정모형 의미론적 특성

프로그램 $P{\displaystyle }${\$displaystyle P}$의 어떤 안정된 모델의 모든 원소가 $P{\displaystyle }$ ${\displaystyle P}$의 헤드 원자라고 주장하는 정리는 다음과 같이 헤드 원자를 정의하면 명제 공식의 집합으로 확장될$$ 수 있다. 원자 $A{\displaystyle }$ ${\displaystyle A}$은(는) $P{\displaystyle }$ ${\displaystyle P}$의 공식에서$$ 적어도 하나 $이상$의 A ${\displaystyle A}$이(가) 부정의 범위에 있지 않거나$$ 함축의 선행 상태에 있지 않은 경우 명제 $공식$의 P ${\displaystystyle P}$ 집합의 헤드 원자이다. (여기서 우리는 등가성이 원시 결합체가 아닌 약자로 취급된다고 가정한다.)

전통적인 프로그램의 안정적 모델의 최소성과 반차인 성질은 일반적인 경우에 해당하지 않는다. 예를 들어, (싱글톤 세트는 공식을 구성함)

$\displaystyle p\lor \neg p}$

두 가지 안정적인 모델이 있는데, $∅{\displaystyle \emptyset }$과(와)${\displaystyle }${${\displaystyle p\}}$ ${\displaystyle \{p\}$이다$.$ 후자는 미미하지 않으며, 전자의 적절한 상위 집합이다.

유한한 명제 공식 집합이 안정적인 모델을 가지고 있는지 여부를 시험하는 것은 programs ${\displaystyle {2\mathrm{}}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\$완전이다.

참고 항목

• 응답 세트 프로그래밍
• 논리 프로그래밍
• 실패로 부정을 나타냄

메모들

참조

• N. Bidoit와 C. 프로이데보 [1987] 미니멀리즘은 기본 논리와 할례를 약화시킨다. 인: LICS-87의 절차, 89-97페이지.
• T. Eiter 및 G. Gottlob [1993] 이항 논리 프로그래밍 및 비단조 로직 적용에 대한 복잡성 결과. 인: ILPS-93의 절차, 266-278페이지.
• M. 밴 엠든과 R. 코왈스키 [1976] 프로그래밍 언어로서의 술어 논리의 의미론. ACM 저널, 23권 733-742페이지.
• F. 페이징 [1994] 클라크의 완성도와 안정적인 모델의 존재에 대한 일관성. 컴퓨터 과학 논리학 저널, 제1권, 51-60페이지.
• P. 페라리 [2005] 명제 이론에 대한 답변 집합. 인: LPNMR-05의 절차 119-131페이지.
• P. 페라리스와 V. Lifschitz [2005] 답변 집합 프로그래밍의 수학 기반. 인: 우리는 그들에게 보여줄 것이다! 킹스 칼리지 출판사 도브 가베이의 명예에 관한 에세이는 615-664페이지에 이른다.
• M. Gelfond [1987] 성층화된 자기계파적 이론에 대하여. 인: AAAI-87의 절차, 207-211페이지.
• M. Gelfond와 V. Lifschitz [1988] 로직 프로그래밍을 위한 안정적인 모델 의미론. In: ICLP(International Conference of Logic Programming) 1070–1080페이지.
• M. Gelfond와 V. Lifschitz [1991] 논리 프로그램과 이격 데이터베이스의 고전적 부정. New Generation Computing, Vol. 9페이지 365–385.
• S. 행크스와 D. McDermott [1987] 비모노토닉 논리 및 시간 투영. 인공지능, 제33권 379-412쪽
• F. 린과 Y. 자오[2004] ASAT: SAT 해결사별 논리 프로그램 응답 세트 계산. 인공지능, 157권 115-137쪽
• V. 마렉과 V.S. 수브라만어 [1989] 로직 프로그램 의미론과 비단조적 추론의 관계. In: ICLP-89의 절차, 600–617페이지.
• D. Pearce [1997] 안정적 모델과 답변 세트의 새로운 논리적 특성화. In: 로직 프로그래밍의 비-모노토닉 확장(인공지능 1216의 선택 노트), 57-70페이지.
• R. 반복 [1980] 기본 추론에 대한 논리. 인공지능, 13권 81~132쪽