티스토리 뷰
//이 자료는 Discrete mathmatics and its application 7th edition에서 나오는 예제를 간추린 것입니다. 저는 코딩에 관심 있는 학생이며, 타인의 지적재산을 단지 학습을 위해 사용할 뿐 개인의 금리적 이윤을 위한 상업적인 용도로 쓰지 않습니다. 만약 저작권 관련 문제가 될 시 즉시 문서를 삭제하겠습니다.//
1.3 논리적 동치 logical equivalent
동어반복 tautology 모순 contradiction
수학적 논증에서 사용되는 중요한 접근법은 한 명제를 같은 진리값을 가지는 다른 명제로 대체하는 것입니다. 주어진 복합명제와 같은 진리값을 가지는 명제를 만드는 방법론은 수학적 논증을 만드는데 보편적으로 사용됩니다. 복합명제는 p^q와 같이 논리 연결사를 이용해 명제 변수로 이루어진 표현식을 말합니다.
정의 1
명제 변수의 진리값에 상관없이 항상 참인 복합명제는 동어반복이라고 불립니다. 항상 거짓인 복합명제는 모순이라고 불립니다. 동어반복이나 모순이 아닌 복합명제는 contingeny 입니다.
명제변수 하나와 논리연결사를 이용하여 동어반복과 모순의 예를 만들 수 있습니다. 아래의 진리표는 p v ¬p, p ^ ¬p에 관한 것입니다. p v ¬p 는 항상 참이므로 동어반복이고 p ^ ¬p는 항상 거짓이므로 모순입니다.
논리적 동치
모든 경우에 같은 진리값을 가지는 복합 명제를 논리적 동치라고 부릅니다.
정의 2
p<->q가 동어반복이라면 p와 q는 논리적 동치라고 불립니다. 기호 p≡q는 p와 q가 논리적 동치임을 표현합니다.
주의
기호≡는 논리 연결사가 아니며, p≡q는 p <-> q가 동어반복임을 나타내는 명제입니다. 두 복합명제가 동치인지 확인하는 방법은 진리표를 사용하는 것입니다.
예제 2
¬(p v q) 와 ¬p^¬q가 논리적 동치인 것을 보이세요
정답
복합명제들은 아래의 진리표에서 확인 가능합니다. ¬(p v q) 와 ¬p^¬q 두 복합명제의 진리 값은 어떠한 p 와 q의 어떠한 진리값 조합조건과 같습니다. ¬(p v q) <-> (¬p^¬q)는 동어반복이고 두 복합명제는 논리적 동치입니다.
예제 3
p -> q와 ¬p v q는 논리적 동치인 것을 보이세요.
정답
아래의 진리표를 확인합시다. ¬p v q 와 p -> q의 진리값은 일치하므로 논리적 동치입니다.
서로 다른 세가지 명제변수 p, q, r을 포함하는 두 복합명제를 논리적 동치로 만들 것입니다. 세가지 변수의 진리값 조합 수는 8 열을 가집니다. 8개 조합 조건의 진리값은 다음과 같습니다. TTT, TTF, TFT, TFF, FTT, FTF, FFT 그리고 FFF 입니다. 진리표의 열을 표현할 때 이 순서를 사용할 것입니다. 추가적인 명제변수로, 복합명제가 논리적인 동치임을 보여주기 위해서는 열의 수는 2배가 됩니다. 보통, n 개의 명제변수를 포함한 복합명제는 2^n 열이 필요로 합니다.
예제 4
p v (q ^ r)과 (p v q) ^ (p v r)은 논리적 동치인지 확인합시다. 이를 논리곱의 분배법칙이라 합니다.
정답
문제의 복합명제로 아래의 진리표를 만들 수 있습니다. 두 복합명제의 진리값이 일치하므로, 논리적 동치입니다.
예제 5
“미구엘은 핸드폰을 가지고있고 노트북을 가지고 있다”와 “헤서는 콘서트에 가거나 스티브가 콘서트에 갈 것이다”의 부정형을 드 모르간의 법칙을 이용하여 표현하세요
정답
P를 “미구엘은 핸드폰을 가지고 있다”와 q는 “미구엘은 노트북을 가지고 있다”라고 하자. “미구엘은 핸드폰과 노트북을 가지고 있다”는 p^q로 표현될 수 있습니다. 드 모르간 법칙의 첫 번째를 따르면, ¬(p^q)가 ¬p v ¬q 와 같습니다. 따라서, 원 명제의 부정형으로 "미구엘은 핸드폰을 가지고 있지 않거나 노트북을 가지고 있지 않다."로 쓸 수 있습니다.
r을 "헤서는 콘서트에 갑니다" 와 s는 "스티브는 콘서트에 갑니다"라 합시다. 그렇다면 "헤서는 콘서트에 가거나 스티브가 콘서트에 갑니다"를 r v s로 표현할 수 있습니다. 드 모르간의 법칙에 따라, ¬(r v s)는 ¬r ^ ¬s와 같습니다. 결과적으로, 우리는 원 명제의 부정형으로 "헤서는 콘서트에 가지 않을 것이고 스티브는 콘서트에 가지 않을것 입니다."로 쓸 수 있습니다.
새로운 논리적 동치를 만들기
예제 6
정답
예제 7
정답
예제 8
(p ^ q) -> (p v q) 가 동어반복임을 보이시오.
정답
(p ^ q) -> (p v q) ≡ ¬(p ^ q) v (p v q) //예제 3
≡ (¬p v ¬q) v (p v q) //드 모르간의 법칙
≡ (¬p v p) v (¬q v q) //교환법칙과 결합법칙
≡ T v T //예제 1과 교환법칙
≡ T
명제 만족 가능성 Propositional Satisfiability
명제변수가 특정 진리값을 가질 때, 복합명제가 참이된다면 복합명제는 만족될 수 있다(satisfiable)고 표현합니다. 어떠한 경우에도 복합명제가 참을 가질 수 없을 때 만족될 수 없다(unsatisfiable)고 표현합니다. 명제변수에 할당되었을 때 복합명제를 참으로 만드는 특정한 진리값을 찾았을 때, 복합명제는 만족될 수 있다고 합니다. 할당된 진리값을 해당 만족 문제에 대한 솔루션이라고 부릅니다. 그러나, 해당 복합명제가 만족 될 수 없다고 보이기 위해서는, 모든 진리 값을 명제변수에 넣어야 합니다. 진리표를 활용하여 복합명제가 만족 될 수 있음을 보일 수는 있어도, 보통 그런 방법보다는 아래의 방법을 사용하는것이 더 효율적입니다.
예제 9
정답
만족 가능성의 응용
로보틱스, 소프트웨어 검사, 컴퓨터 디자인, 컴퓨터 비젼, 집적 회로 디자인, 컴퓨터 네트워크, 유전학 등 분야에서 다양한 문제들이 명제 만족 가능성 문제로 모델링 될 수 있습니다. 이런 많은 응용물들은 책의 범위를 뛰어넘지만, 한 가지 응용사례를 앞으로 살펴볼 것 입니다. 다음은 스도쿠 퍼즐을 모델링하는법을 볼 것입니다.
..생략..
문제 9 다음이 동어반복임을 진리표를 이용하여 보이시오
'Discrete mathmatics and Problem Solving > 1 논리' 카테고리의 다른 글
0 Introduction (0) | 2016.12.26 |
---|---|
1 기초: 논리와 증명 5 (0) | 2016.09.26 |
1 기초: 논리와 증명 4 (0) | 2016.09.17 |
1 기초: 논리와 증명 2 (0) | 2016.09.12 |
1 기초: 논리와 증명 (0) | 2016.09.10 |
- Total
- Today
- Yesterday
- grafana cloud
- javascript
- 아레나
- 대규모 시스템 설계 기초
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 시뮬레이션
- 그라파나
- 최단경로 알고리즘
- arena simulation
- 로젠
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
- Propositional and Predicate Logic
- 자바스크립트 예제
- rosen
- 백준
- Simulation
- 이산 수학
- Trie
- 조합 코딩
- 데이터 중심 애플리케이션 설계
- Arena
- Discrete Mathematics
- paul wilton
- 자바스크립트
- 명제논리
- beginning javascript
- flutter
- 아레나시뮬레이션
- 아레나 시뮬레이션
- 이산수학
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |