|| 그리고! 가능한 모든 논리적 표현을하기에 충분한 연산자?
논리식은 ( a && b ) (모두 a및 b부울 값을 갖는다) 과 같이 기록 될 수있다 !(!a || !b), 예를 들면. 이것이 &&"비평 장"을 의미하지 않습니까? 이것은 모든 논리식 이 ||and 만 사용하여 만들 수 있음을 의미합니까 !?
다른 답변이 지적한대로 예, 사업자의 집합의 포함 ||하고 !있다 기능적으로 완전한 . 다음은 부울 변수 A와 사이에 16 개의 가능한 논리적 연결을 표현하는 데 사용하는 방법을 보여주는 건설적인 증거입니다 B.
- 사실 :
A || !A - 낸드 B :
!A || !B - B는 A를 의미합니다 .
!B || A - A는 B를 의미합니다 .
!A || B - A 또는 B :
A || B - B가 아님 :
!B - 아님 :
!A - XOR B :
!(!A || B) || !(A || !B) - XNOR B :
!(!A || !B) || !(A || B) - A :
A - B :
B - A NOR B :
!(A || B) - A는 B를 의미하지 않습니다 .
!(!A || B) - B는 A를 의미하지 않습니다 .
!(!B || A) - A와 B :
!(!A || !B) - 거짓 :
!(A || !A)
NAND와 NOR 모두 자체적으로 기능적으로 완전하므로 (위와 동일한 방법을 사용하여 증명할 수 있음) 일련의 연산자가 기능적으로 완전한지 확인하려면 NAND 또는 NOR을 표현할 수 있음을 표시하는 것으로 충분합니다 그것으로.
다음 은 위에 나열된 각 연결에 대한 벤 다이어그램 을 보여주는 그래프입니다 .
[ 출처 ]
당신이 설명하는 것은 기능적 완전성 입니다.
여기에는 "가능한 모든 진리표를 표현"하기에 충분한 논리 연산자 세트가 설명되어 있습니다. 자바 연산자 세트는, { ||, !}는 충분하다; "최소 기능적으로 완전한 오퍼레이터 세트"섹션에 나열된 {∨, ¬} 세트에 해당합니다.
모든 진리표 세트는 2 개의 부울 값 사이의 연산의 결과 일 수있는 4 개의 부울 값의 모든 가능한 세트를 의미합니다. 부울에는 2 개의 가능한 값이 있으므로 2 4 또는 16 개의 가능한 진리표가 있습니다.
A B | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
----+------------------------------------------------
T T | T T T T T T T T F F F F F F F F
T F | T T T T F F F F T T T T F F F F
F T | T T F F T T F F T T F F T T F F
F F | T F T F T F T F T F T F T F T F
다음은 진리표 번호 (0-15)의 표 ||와 !이를 생성하는 조합 및 설명입니다.
Table | Operation(s) | Description
-------+----------------------------------+-------------
0 | A || !A | TRUE
1 | A || B | OR
2 | A || !B | B IMPLIES A
3 | A | A
4 | !A || B | A IMPLIES B
5 | B | B
6 | !(!A || !B) || !(A || B) | XNOR (equals)
7 | !(!A || !B) | AND
8 | !A || !B | NAND
9 | !(A || !B) || !(!A || B) | XOR
10 | !B | NOT B
11 | !(!A || B) | NOT A IMPLIES B
12 | !A | NOT A
13 | !(A || !B) | NOT B IMPLIES A
14 | !(A || B) | NOR
15 | !(A || !A) | FALSE
Java에는 해당 단일 연산자가없는 하나의 요소 세트 {NAND} 및 {NOR}을 포함하여 기능적으로 완전한 다른 세트가 많이 있습니다.
예.
모든 논리 게이트는 NOR 게이트로 만들 수 있습니다.
NOR 게이트는 NOT 및 OR로 만들 수 있으므로 결과는 다음과 같습니다.
가능하면 DeMorgan 's Laws 를 읽으십시오 .
논리적 증거에 대한 참조뿐만 아니라 거기에서 읽을 수 있습니다.
그러나 본질적으로 대답은 그렇습니다.
편집 : 명시 적으로, 내 요점은 논리적으로 AND 식에서 OR 식을 유추 할 수 있으며 그 반대도 마찬가지입니다. 논리적 동등성과 추론에 대한 법칙이 더 있지만, 이것이 가장 큰 제안이라고 생각합니다.
편집 2 : 다음 표의 논리적 동등성을 보여주는 진리표를 통한 증거가 있습니다.
데모 간의 법칙 : !(!A || !B) -> A && B
_____________________________________________________ | A | B | ! A | ! B | ! A || ! B | ! (! A ||! B) | & B 조 | -------------------------------------------------- ----- | 0 | 0 | 1 | 1 | 1 | 0 | 0 | -------------------------------------------------- ----- | 0 | 1 | 1 | 0 | 1 | 0 | 0 | -------------------------------------------------- ----- | 1 | 0 | 0 | 1 | 1 | 0 | 0 | -------------------------------------------------- ----- | 1 | 1 | 0 | 0 | 0 | 1 | 1 | _______________________________________________________
NAND 와 NOR 는 보편적이며 어디에서나 원하는 논리 연산을 구축하는 데 사용할 수 있습니다. 다른 연산자는 프로그래밍 언어로 제공되어 쉽게 읽고 쓸 수있는 코드를 만들 수 있습니다.
또한 회로에서 하드 와이어가 필요한 모든 논리 연산도 NAND 또는 NOR 전용 IC를 사용하여 개발됩니다.
예, 부울 대수에 따르면 모든 부울 함수는 최소 항의 합 또는 최대 항의 곱으로 표현 될 수 있으며 표준 정규형 이라고 합니다 . 이러한 논리가 컴퓨터 과학에 사용 된 동일한 연산자에 적용될 수없는 이유는 없습니다.
https://en.wikipedia.org/wiki/Canonical_normal_form
'Programing' 카테고리의 다른 글
| 문자열 형식으로 주어진 수학 표현식을 평가하는 방법은 무엇입니까? (0) | 2020.03.17 |
|---|---|
| 문자열을 공백으로 나누는 방법 (0) | 2020.03.17 |
| foreach없이 목록에서 항목으로 항목을 복사하려면 어떻게합니까? (0) | 2020.03.17 |
| 자식 : 치명적 : 프로토콜 'http'를 처리하지 않습니다 (0) | 2020.03.17 |
| byte []를 Java로 파일로 (0) | 2020.03.17 |