내가이 감소 할 것으로 예상 부울 표현

Question

나는 가정, 식을 데,

a = 1 && (b = 1 || b != 0) && (c >= 35 || d != 5) && (c >= 38 || d = 6) 

,

이

a = 1 && b != 0 && (c >= 38 || d = 6) 

이 가

사람이 어떤 제안이 있습니까 감소? 어떤 알고리즘에 대한 포인터?

Nota Bene : Karnaugh Map 또는 Quine-McCluskey는 여기에 포함되지 않습니다. 이 방법은 회색 케이스를 처리하지 않으므로 즉, 표현은 A 나 A '또는 무언가, 또는 검은 색 또는 흰색 또는 색이없는 색과 같은 것으로 만 축소 될 수 있습니다. 하지만 여기에서는 여러분이 볼 수있는 것처럼 회색 음영을 보입니다.

해결책 : 나는 이것을 위해 Clojure에서 프로그램을 작성했다. 나는 값으로 함수를 포함하는지도의지도를 사용했다. 꽤 편리 해졌고, 몇 가지 조합에 대한 몇 가지 규칙 만 있으면 좋았습니다. 도움이되는 답변에 감사드립니다.

Answer 1

Constraint Handling Rules을 사용하여 원하는 것을 달성 할 수 있어야한다고 생각합니다. OR 및 AND 식을 단순화하는 규칙을 작성해야합니다.

가장 큰 어려움은 드롭 할 수있는 부분을 알려주는 제한 조건 수표입니다. (c> = 38 || d = 6)은 전자가 후자에 의해 수반되므로 (c> = 38 || d = 6) 단순화된다. 즉, (c> = 35 || d = 6) & & 후자는 더 구체적입니다. OR 표현식의 경우보다 일반적인 부분을 선택해야합니다.

Google은 paper on an extension of CHR with entailment check for user-defined constraints을 발견했습니다. 그러한 확장이 필요한지 여부를 말할 수있을만큼 충분한 CHR을 알지 못합니다.

Answer 2

이런 종류의 일들이 정기적으로 constraint logic programming에서 이루어집니다. 불행히도 나는 더 정확한 세부 사항을 제공하기에는 충분히 경험이 없지만 좋은 출발점이되어야합니다.

일반 원칙은 간단합니다. 언 바운드 변수는 모든 값을 가질 수 있습니다. 불평등에 대해 테스트 할 때 가능한 값 집합은 하나 이상의 간격으로 제한됩니다. 이러한 간격이 단일 지점으로 수렴 될 경우/그 변수는 해당 값에 바인딩됩니다. OTOH가 간격의 모든 값에 대해 불완전한 것으로 간주되면 [프로그래밍] 논리 오류가 발생합니다.

또한 this을 참조하십시오. 실제로 이것이 swi-prolog를 사용하여 수행되는 방법의 예를 참조하십시오. 다행히도 기본 알고리즘에 대한 링크 또는 참조를 찾을 수 있으므로 원하는 플랫폼에서 재현 할 수 있습니다 (어쩌면 기성품 라이브러리를 찾을 수도 있습니다).

업데이트 : swi-prolog 및 clpfd를 사용하여 예제를 재현하려고했지만 예상 한 결과를 얻지 못하고 닫기 만했습니다.

?- [library(clpfd)]. 
simplify(A,B,C,D) :- 
    A #= 1 , 
    (B #= 1 ; B #\= 0) , 
    (C#>= 35 ; D #\= 5) , 
    (C#>= 38 ; D #= 6). 

그리고 내 결과, (읽기 쉽도록 줄 바꿈 삽입) 역 추적에 : 여기 내 코드는

10 ?- simplify(A,B,C,D). 

A = 1, 
B = 1, 
C in 38..sup ; 

A = 1, 
B = 1, 
D = 6, 
C in 35..sup ; 

A = 1, 
B = 1, 
C in 38..sup, 
D in inf..4\/6..sup ; 

A = 1, 
B = 1, 
D = 6 ; 

A = 1, 
B in inf.. -1\/1..sup, 
C in 38..sup ; 

A = 1, 
D = 6, 
B in inf.. -1\/1..sup, 
C in 35..sup ; 

A = 1, 
B in inf.. -1\/1..sup, 
C in 38..sup, 
D in inf..4\/6..sup ; 

A = 1, 
D = 6, 
B in inf.. -1\/1..sup. 

11 ?- 

그래서, 프로그램은 그 중 8 개 결과를 굴복 2는 5 일 (에 관심 및 8) :

A = 1, 
B in inf.. -1\/1..sup, 
C in 38..sup ; 

A = 1, 
D = 6, 
B in inf.. -1\/1..sup. 

다른 하나는 중복했고, 어쩌면 간단 오토메이션 로직 규칙을 사용하여 제거 할 수 있습니다 :

,691을

1st or 5th ==> 5th   [B == 1 or B != 0 --> B != 0] 
2nd or 4th ==> 4th   [C >= 35 or True --> True ] 
3rd or 1st ==> 1st ==> 5th [D != 5 or True --> True ] 
4th or 8th ==> 8th   [B == 1 or B != 0 --> B != 0] 
6th or 8th ==> 8th   [C >= 35 or True --> True ] 
7th or 3rd ==> 3rd ==> 5th [B == 1 or B != 0 --> B != 0] 

나는 그것이 일반적인 솔루션 인 뒤에 긴 방법을 알고 있지만, 내가 말했듯이, 희망이 시작입니다 ...

P.S. clpfd의 것 (#/\ 및 #\/)이 나 자신을 이해할 수없는 매우 이상한 결과를 주었기 때문에 "regular"AND 및 OR (, 및 ;)을 사용했습니다.