부울 표현식을 단순화하는 알고리즘을 아는 사람은 누구입니까?부울 표현 알고리즘 단순화
나는 부울 대수와 Karnaught지도를 기억하지만, 이것은 EVERITHING이 부울 인 디지털 하드웨어를위한 것입니다. 일부 하위 표현식이 부울이 아니라는 점을 고려한 무언가를 원합니다. 이것은 순수한 부울 표현식으로 변환 할 수
a == 1 && a == 3
:
예를 들어a1 && a3
하지만이를 arithmetics의 지식의 조금으로 everibody 결정할 수 있지만 표현, 기약입니다 표현식은 단지 :
false
일부 신체는 오메 링크? 물론
http://hopper.unco.edu/KARNAUGH/Algorithm.html
, 비 부울 표현식을 처리하지 않습니다 구글을 사용
첫 이미지 촬영이 종이를 발견했다. 그러나 임의의 산술 표현식이 참인지 거짓인지를 확인할 알고리즘이 없기 때문에 일반적인 형태의이 부분은 정말 어렵습니다. 당신이 요구하는 것은 compiler optimization의 분야에 깊숙이 들어가 있습니다.
나는 이전에이 논문을 읽었었지만, 아직 명확하지 않고 코드도 제공되지 않았다. – Olmo
K-maps 및 Quine–McCluskey algorithm에 관심이있을 수 있습니다.
SymPy가 부울 표현식을 해결하고 단순화 할 수 있다고 생각합니다. 소스를 보면 유용 할 수 있습니다.
가능한 고유 값의 수는 유한하고 알려져 있습니까? 그렇다면 각 표현식을 부울 표현식으로 변환 할 수 있습니다. 예를 들어, a가 3 개의 구별 된 값을 가지고 있다면 변수 a1, a2 및 a3을 가질 수 있습니다. a1이 참이면 a == 1 등을 의미합니다. 일단 Quine-McCluskey 알고리즘을 사용할 수 있습니다. Karnaugh지도보다). 다음은 Quine-McCluskey의 Java code입니다.
이 디자인이 실제로 단순화하거나 복잡한 것으로 말할 수는 없지만 적어도 고려해 볼 수는 있습니다.
정확히!, 그게 무슨 뜻이야?하지만이 알고리즘은 내 예제에서는 a1 && a3이 실제로 거짓이라는 것을 전혀 모를 것이다. 왜냐하면 a는 동시에 1과 3이 될 수 없기 때문입니다. 나는 Karnaught의 미주에서는 변수들을 변수에 바인딩하고 모순을 찾는 것이 필요하다고 생각합니다. – Olmo
귀하의 특정 예는 SMT solver으로 해결됩니다. (변수를 설정하지 않으면 표현식이 참이 될 수 없으므로 항상 거짓입니다.보다 일반적인 단순화는 그러한 해결 자의 범위를 벗어납니다.) 표현식이 true 또는 false과 동일하다는 것을 나타내는 것은 당연히 NP- 거래에 산술을 사용하지 않아도 열심히 일하므로 매우 실용적인 소프트웨어가 있다는 점도 매우 좋습니다. 산술 지식의 범위가 어느 정도인지에 따라 문제는 may be undecidable입니다.
이 문제에는 논리적 단순화 및 표현 단순화의 두 부분이 있습니다.
논리적 단순화를 위해 Quine-McCluskey.표현의 단순화를 위해, 분포 식별 (0 & 1 | 0 & 2) == 0 & (1 | 2)을 사용하여 용어를 반복적으로 추출하십시오.
자세한 과정은 here입니다. 이는 단지 &과 |를 사용하여 설명을 제공하지만 모든 부울 연산자를 포함하도록 수정할 수 있습니다.
이것은 어려운 사람입니다. 내가 찾은 가장 간단한 방법의 알고리즘은 각 입력 조합마다 모든 출력 조합을 각 조합과 일치시키는 것입니다. 그러나 그것은 모든 알고리즘을 풀지는 못했던 기본적인 알고리즘입니다.
모든 출력 (Q1, Q2, Q3, Q4)는 다음의 단순화의 결과
아니라면 A. 것이다 입력 조합을 즉위한와 동일한 경우, 다른 variabel/입력 의존성을 시도 할 것이다.
'a'가 허용되는 언어/런타임의 휘발성 변수/필드로 선언되고 다른 스레드에서 값이 1에서 3까지 변동하면 어떻게됩니까? 나는 이것이 좋은 디자인이라고 말하지는 않지만, 소프트웨어에서 "항상"과 "결코"는 보통 상대적인 용어입니다. –
이것은 문제가되지 않으며 실제 사용은 LINQ Provider를위한 것이며 실제 값은 쿼리가 변환 될 때의 값입니다. 조회가 다시 실행되면 단순화가 갱신 된 값으로 다시 실행됩니다. – Olmo
일반적으로 불가능합니다. 예를 들어'a> 0 and b> 0 and n> 2 그리고 a^n + b^n = c^n'은 항상 false이지만 증명하기는 쉽지 않습니다. 즉, 당신은 ad-hoc 단순화에 빠져 있고 질문에 깨끗한 답은 없습니다 (당신이 보게 될 표현의 본성에 달려 있기 때문에). –