표준화 이론 표준형 구조나무 표준화 정리 ∧ ∨ → ↔ =
공접절/이접절의 구성 ∧, ∨ 논리구 A B C D E . . .
공접절과 이접절(예) ∧ B A C ∨ B A C ∧(A,B,C) A∧B∧C ∨(A,B,C) A∨B∨C
공접/이접 표준형의 구성 논리절 ∧, ∨ 이접절. 공접절 논리구
공접/이접 표준형의 구조 (예) 공접 표준형 이접 표준형 ∧ ∨ (A∨B∨C)∧(D ∨E )∧(F ∨G) ∨
[예] 공접표준형 (A∨B∨C)∧(D∨E)∧(F∨G) A∧(B∨C) ( ≡ (A∨A)∧(B∨C) ) A∧B ( ≡ (A∨A)∧(B∨B) ) (ꍃA∨B)∧(ꍃB∨C)∧(ꍃC∨D) [예] 이접표준형 (A∧B∧C)∨(D∧E)∨(F∧G) A∨(B∧C) ( ≡ (A∧A)∨(B∧C) ) A∨B ( ≡(A∧A)∨(B∧B) ) (D∧ꍃE)∨(E∧ꍃF)∨(ꍃA∨F)
표준화 정리 [정리](표준화) ① 모든 논리식은 등가의 공접표준형으로 바꿀수 있다. ① 모든 논리식은 등가의 공접표준형으로 바꿀수 있다. ② 모든 논리식은 등가의 이접표준형으로 바꿀수 있다. ③ 모든 논리식은 등가의 조건절형으로 바꿀수 있다. ④ 모든 논리식은 등가의 호른-절형으로 바꿀수 있다.
8.1. 표준형으로 바꾸기 논리구 A, B 를 갖는 다음의 간단한 논리식들은 다음과 같이 바꿀 수 있다: A∧B 는 A∧B≡(A∨A)∧(B∨B)≡(A∧B)∨(A∧B) A∨B 는 A∨B≡ (A∨B)∧(A∨B)≡(A∧A)∨(B∧B) 임으로 이 에 따라 공접 표준형 혹은 공접 이접형으로 바꿀 수 있다. A→B ≡ ꍃA∨B 를 이용하여 위의 방법으로 적절히 변형한다. 그 외의 식들은 다음과 같이 하여 바꾼다: (가) 예비적 단계: 다음 형식의 부분 문장들은 우선 다음과 같이 바꾼다. ① F↔G 는 (F→G)∧(G→F)로 ② F→G 는 ꍃF∨G로 ③ ꍃ(F∧G)는 ꍃF∨ꍃG로 ④ ꍃ(F∨G)는 ꍃF∧ꍃG로 바꾼다. (나) 공접 표준형으로 바꾸기: 분배의 법칙을 이용하여 F∨(G∧H)의 형식을 갖는 부분식들을 모두 (F∨G)∧(F∨H)로 바꿀 수 있을 때까지 바꾼다. (다) 이접 표준형으로 바꾸기: 분배의 법칙을 이용하여 F∧(G∨H)의 형식을 갖는 부분식들을 모두 (F∧G)∨(F∧H)로 바꿀 수 있을 때까지 바꾼다.
[예] A↔B ≡ (A→B)∧(B→A) ≡ (ꍃA∨B)∧(ꍃB∨A) . . . . . . . . . . . . .(공접표준형) ≡ ((ꍃA∨B)∧ꍃB)∨(ꍃA∨B)∧A) ≡ (ꍃA∧ꍃB)∨(B∧ꍃB)∨(ꍃA∧A)∨(B∧A) (이접표준형) ≡ (ꍃA∧ꍃB)∨(B∧A) ≡ (A∧B)∨(ꍃA∧ꍃB) A XOR B ≡ (A∧ꍃB)∨(ꍃA∧B) . . . . . . . . . . . . . (이접표준형) ≡ ((A∧ꍃB)∨ꍃA)∧((A∧ꍃB)∨B) ≡ (A∨ꍃA)∧(ꍃB∨ꍃA)∧(A∨B)∧(ꍃB∨B) (공접표준형) ≡ (ꍃB∨ꍃA)∧(A∨B) ≡ (A∨B)∧(ꍃA∨ꍃB)