불리언 및 반영 제약

불리언 및 반영 제약

FD 불리언 및 반영(reified) 제약을 설명해요.

출처: GNU Prolog Manual - Boolean and reified constraints

본문

불리언 FD 표현식

불리언 FD 표현식은 정수(0은 거짓, 1은 참), 변수(Prolog 또는 FD 변수), 부분 AC 산술 제약(9.6.2절), 전체 AC 산술 제약(9.6.3절) 및 불리언 함수를 나타내는 functor(또는 연산자)로 만들어진 Prolog 항이에요. 불리언 표현식의 하위 표현식이 산술 제약 c이면 반영(reified)돼요. 즉 솔버가 c가 참(내포됨, entailed)임을 감지하는 즉시 하위 표현식은 값 1을 가져요. 비슷하게 솔버가 c가 거짓(배제됨, disentailed)임을 감지하면 하위 표현식은 0으로 평가돼요. 내포도 배제도 감지할 수 없는 동안 하위 표현식은 도메인 0..1로 평가돼요.

다음 표는 FD 불리언 표현식의 구성 요소를 자세히 설명해요:

FD 표현식 결과
Prolog 변수 도메인 0..1
FD 변수 X X의 도메인, X는 0..1에 있도록 제약됨
0 (정수) 0 (거짓)
1 (정수) 1 (참)
#\ E not E
E1 #<=> E2 E1이 E2와 동치
E1 #\<=> E2 E1이 E2와 동치가 아님(즉 E1이 E2와 다름)
E1 ## E2 E1이 E2와 배타적 OR(즉 E1이 E2와 동치가 아님)
E1 #==> E2 E1이 E2를 함의
E1 #\==> E2 E1이 E2를 함의하지 않음
E1 #/\ E2 E1 AND E2
E1 #\/\ E2 E1 NAND E2
E1 #\/ E2 E1 OR E2
E1 #\\/ E2 E1 NOR E2

#<=>, #\<=>, ##, #==>, #\==>, #/\, #\/\, #\/, #\\/는 미리 정의된 중위 연산자예요. #\는 미리 정의된 접두 연산자예요(8.14.10절).

Errors

  • 하위 표현식 E가 변수도 정수(0 또는 1)도 FD 불리언 functor도 반영 제약도 아님 — type_error(fd_bool_evaluable, E)
  • 표현식이 너무 복잡 — resource_error(too_big_fd_constraint)
  • 하위 표현식이 유효하지 않은 반영 제약 — 산술 제약 오류(9.6.1절)

fd_reified_in/4

Templates

fd_reified_in(?fd_variable, +integer, +integer, ?fd_variable)

Description fd_reified_in(X, Lower, Upper, B)는 제약 X ∈ [Lower..Upper]의 진릿값을 불리언 변수 B에 포착해요.

Errors

  • X가 변수도 FD 변수도 정수도 아님 — type_error(fd_variable, X)
  • B가 변수도 FD 변수도 정수도 아님 — type_error(fd_variable, B)
  • Lower가 변수 — instantiation_error
  • Lower가 변수도 정수도 아님 — type_error(integer, Lower)
  • Upper가 변수 — instantiation_error
  • Upper가 변수도 정수도 아님 — type_error(integer, Upper)

Portability: GNU Prolog 술어.

(#)/1 - 제약 NOT, (#<=>)/2 - 제약 동치, (#<=>)/2 - 제약 다름, (##)/2 - 제약 XOR, (#==>)/2 - 제약 함의, (#==>)/2 - 제약 비함의, (#/)/2 - 제약 AND, (#/)/2 - 제약 NAND, (#/)/2 - 제약 OR, (#\/)/2 - 제약 NOR

Templates

#\(?fd_bool_evaluable)
#<=>(?fd_bool_evaluable, ?fd_bool_evaluable)
#\<=>(?fd_bool_evaluable, ?fd_bool_evaluable)
##(?fd_bool_evaluable, ?fd_bool_evaluable)
#==>(?fd_bool_evaluable, ?fd_bool_evaluable)
#\==>(?fd_bool_evaluable, ?fd_bool_evaluable)
#/\(?fd_bool_evaluable, ?fd_bool_evaluable)
#\/\(?fd_bool_evaluable, ?fd_bool_evaluable)
#\/(?fd_bool_evaluable, ?fd_bool_evaluable)
#\\/(?fd_bool_evaluable, ?fd_bool_evaluable)

Description

  • #\ FdBoolExpr1 — FdBoolExpr1을 거짓으로 제약.
  • FdBoolExpr1 #<=> FdBoolExpr2 — FdBoolExpr1을 FdBoolExpr2와 동치로 제약.
  • FdBoolExpr1 #\<=> FdBoolExpr2 — FdBoolExpr1을 not FdBoolExpr2와 동치로 제약.
  • FdBoolExpr1 ## FdBoolExpr2 — FdBoolExpr1 XOR FdBoolExpr2를 참으로 제약.
  • FdBoolExpr1 #==> FdBoolExpr2 — FdBoolExpr1이 FdBoolExpr2를 함의하도록 제약.
  • FdBoolExpr1 #\==> FdBoolExpr2 — FdBoolExpr1이 FdBoolExpr2를 함의하지 않도록 제약.
  • FdBoolExpr1 #/\ FdBoolExpr2 — FdBoolExpr1 AND FdBoolExpr2를 참으로 제약.
  • FdBoolExpr1 #\/\ FdBoolExpr2 — FdBoolExpr1 AND FdBoolExpr2를 거짓으로 제약.
  • FdBoolExpr1 #\/ FdBoolExpr2 — FdBoolExpr1 OR FdBoolExpr2를 참으로 제약.
  • FdBoolExpr1 #\\/ FdBoolExpr2 — FdBoolExpr1 OR FdBoolExpr2를 거짓으로 제약.

FdBoolExpr1과 FdBoolExpr2는 불리언 FD 표현식이에요(9.7.1절). 참고로 #\<=>(동치가 아님)와 ##(배타적 OR)은 동의어예요.

이 술어들은 관련 변수의 도메인을 줄이기 위해 부분 호 일관성 알고리즘을 사용해 FD 솔버가 관리하는 불리언 제약을 게시해요. 반영 제약의 (배)내포는 경계(부분 AC 산술 제약의 경우) 또는 전체 도메인(전체 AC 산술 제약의 경우)을 사용해 감지돼요.

#<=>, #\<=>, ##, #==>, #\==>, #/\, #\/\, #\/, #\\/는 미리 정의된 중위 연산자예요. #\는 미리 정의된 접두 연산자예요(8.14.10절).

Errors: 불리언 FD 표현식의 구문에 대한 가능한 오류를 참조해요(9.7.1절).

Portability: GNU Prolog 술어.

fd_cardinality/2, fd_cardinality/3, fd_at_least_one/1, fd_at_most_one/1, fd_only_one/1

Templates

fd_cardinality(+fd_bool_evaluable_list, ?fd_variable)
fd_cardinality(+integer, ?fd_variable, +integer)
fd_at_least_one(+fd_bool_evaluable_list)
fd_at_most_one(+fd_bool_evaluable_list)
fd_only_one(+fd_bool_evaluable_list)

Description fd_cardinality(List, Count)는 List에서 참인 제약의 수와 Count를 통일해요. 이는 제약 B1 + B2 + … + Bn #= Count를 게시하는 것과 동일하며, 각 변수 Bi는 제약 Bi #<=> Ci(Ci는 List의 i번째 제약)로 정의된 새 변수예요. 각 Ci는 불리언 FD 표현식이어야 해요(9.7.1절).

fd_cardinality(Lower, List, Upper)는 fd_cardinality(List, Count), Lower #=< Count, Count #=< Upper와 동일해요.

fd_at_least_one(List)는 fd_cardinality(List, Count), Count #>= 1과 동일해요.

fd_at_most_one(List)는 fd_cardinality(List, Count), Count #=< 1과 동일해요.

fd_only_one(List)는 fd_cardinality(List, 1)과 동일해요.

Errors

  • List가 부분 리스트 — instantiation_error
  • List가 부분 리스트도 리스트도 아님 — type_error(list, List)
  • Count가 FD 변수도 정수도 아님 — type_error(fd_variable, Count)
  • Lower가 변수 — instantiation_error
  • Lower가 변수도 정수도 아님 — type_error(integer, Lower)
  • Upper가 변수 — instantiation_error
  • Upper가 변수도 정수도 아님 — type_error(integer, Upper)
  • List 리스트의 어떤 요소 E가 유효하지 않은 불리언 표현식 — FD 불리언 제약(9.7.1절)

Portability: GNU Prolog 술어.

더 알아보기