표준화 이론 표준형 구조나무 표준화 정리  ∧ ∨ → ↔  =.

Presentation on theme: "표준화 이론 표준형 구조나무 표준화 정리  ∧ ∨ → ↔  =."— Presentation transcript:

1 표준화 이론 표준형 구조나무 표준화 정리  ∧ ∨ → ↔  =

2 공접절/이접절의 구성 ∧, ∨ 논리구 A B C D E . . .

3 공접절과 이접절(예) ∧ B A C ∨ B A C ∧(A,B,C) A∧B∧C ∨(A,B,C) A∨B∨C

4 공접/이접 표준형의 구성 논리절 ∧, ∨ 이접절. 공접절 논리구

5 공접/이접 표준형의 구조 (예) 공접 표준형 이접 표준형 ∧ ∨ (A∨B∨C)∧(D ∨E )∧(F ∨G) ∨

6 [예] 공접표준형              (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)

7 표준화 정리 [정리](표준화) ① 모든 논리식은 등가의 공접표준형으로 바꿀수 있다.
     ① 모든 논리식은 등가의 공접표준형으로 바꿀수 있다.      ② 모든 논리식은 등가의 이접표준형으로 바꿀수 있다.      ③ 모든 논리식은 등가의 조건절형으로 바꿀수 있다.      ④ 모든 논리식은 등가의 호른-절형으로 바꿀수 있다.

8 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)로 바꿀 수 있을 때까지 바꾼다.

9 [예] 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)