Answers : propositions and logical operation, equivalences

1 a) 명제, 참

   b) 참, 거짓을 가릴 수 없는 진술이므로 명제가아니다.

   c) 이는 명제 함수propositional function이다. 변수variable에 값이 지정되지 않으므로 참, 거짓을 가릴 수 없다. 따라서 명제가 아니다.

   d) 명제, 참

2 a) 민수 또는 민환은 나의 친구가 아니다.

   b) 주환의 가방에는 책이 3권이 있지 않다.

   c) 121은 11의 제곱이 아니다.

3 a) 나는 이번 주 복권을 사지 않았다.

   b) 나는 이번 주 복권을 샀거나 1등 상금을 얻었다.

   c) 나는 이번 주 복권을 샀다면, 1등 상금을 얻었다.

   d) 나는 이번 주 복권을 샀고, 1등 상금을 얻었다.

   e) 나는 이번 주 복권을 샀다면, 1등 상금을 얻었다. 그리고 1등 상금을 얻었다면, 이번 주 복권을 산것이다.

   f) 나는 이번주 복권을 사지 않는다면, 1등 상금을 얻지 않을 것이다.

   g) 나는 이번 주 복권을 사지 않았고, 1등 상금을 얻지 않을 것이다.

   h) 나는 이번 주 복권을 사지 않거나, 이번 주 복권을 사고 1등 상금을 얻을것이다.

4 a) p∧q 

   b) p∧¬q 

   c) ¬p∧¬q 

   d) p∨q 

   e) p→q 

   f) (p∨q)∧(p→¬q)

   g) (p→q)∧(q→p) 또는 p↔q

5 a) 넌 감기에 걸리면, 마지막 시험을 놓칠 것이다.

   b) 넌 마지막 시험을 놓치지 않는다면, 강의를 수료할 것이고 강의를 수료한다면 마지막 시험을 놓치지 않은 것이다.

   c) 넌 마지막 시험을 놓친다면, 강의를 수료하지 못할 것이다.

   d) 넌 감기에 걸리거나 마지막 시험을 놓치거나 강의를 수료할 것이다.

   e) 넌 감기에 걸린다면 강의를 수료하지 못할 것이고, 강의를 수료하지 못한 것이면 감기에 걸린 것이다.  (-.ㅡ 무서운 감기...) 

   f) 넌 감기에 걸리고 마지막 시험을 놓치거나, 마지막 시험을 치루고 강의를 수료할 것이다.

6 a) r∧¬q

   b) p∧q∧r

   c) p→r

   d) p∧¬q∧r

   e) (p∧q)→r

   f) [r→(p∧q)]∧[(p∧q)→r]

7 

p	q	r	s	p→q	(p→q)→r	((p→q)→r)→s
T	T	T	T	T	T	T
T	T	T	F	T	T	F
T	T	F	T	T	F	T
T	T	F	F	T	F	T
T	F	T	T	F	T	T
T	F	T	F	F	T	F
T	F	F	T	F	T	T
T	F	F	F	F	T	T
F	T	T	T	T	T	T

P	q	r	s	p→q	(p→q)→r	((p→q)→r)→s
F	T	T	F	T	T	F
F	T	F	T	T	F	T
F	T	F	F	T	F	T
F	F	T	T	T	T	T
F	F	T	F	T	T	F
F	F	F	T	T	F	T
F	F	F	F	T	F	T

8

p	q	r	s	p↔q	r↔s	(p↔q)↔(r↔s)
T	T	T	T	T	T	T
T	T	T	F	T	F	F
T	T	F	T	T	F	F
T	T	F	F	T	T	T
T	F	T	T	F	T	F
T	F	T	F	F	F	T
T	F	F	T	F	F	T
T	F	F	F	F	T	F
F	T	T	T	F	T	F

p	q	r	s	p↔q	r↔s	(p↔q)↔(r↔s)
F	T	T	F	F	F	T
F	T	F	T	F	F	T
F	T	F	F	F	T	F
F	F	T	T	T	T	T
F	F	T	F	T	F	F
F	F	F	T	T	F	F
F	F	F	F	T	T	T

10 

명제변수 p는 진리값 T 또는 F를 가진다. 그 진리값의 이중 부정은 그 자신이다.

p	¬p	¬(¬p)
T	F	T
F	T	F

11

a)

p	q	p∨q	q∨p
T	T	T	T
T	F	T	T
F	T	T	T
F	F	F	F

b)

p	q	p∧q	q∧p
T	T	T	T
T	F	F	F
F	T	F	F
F	F	F	F

12, 13 생략-_-ㅎㅎ

14 

p↔q ≡ (p→q)∧(q→p)                                //쌍방조건문을 조건문으로 바꿈

       ≡ (¬p∨q)∧(¬q∨p)                              //조건문을 논리합으로 바꿈

       ≡ ((¬p∨q)∧¬q)∨((¬p∨q)∧p)                 //(¬p∨q)을 이용하여 분배법칙을 수행한다. 

       ≡ ((¬p∧¬q)∨(q∧¬q))∨((¬p∧p)∨(q∧p))    //각 각 ¬q와 p을 이용하여 분배법칙을 수행한다.

       ≡ ((¬p∧¬q)∨F)∨(F∨(q∧p))                   //모순명제들을 확인하여 F로 표현

       ≡ (¬p∧¬q)∨(q∧p)                             //복합명제와 F의 논리합은 명제의 진리값에의해 결정 

       ≡ (q∧p)∨(¬p∧¬q)                             //교환법칙을 이용하여 증명 완료

15 

¬p↔q ≡ (¬p→q)∧(q→¬p)                         //쌍방조건문을 조건문으로 바꿈

         ≡ (p∨q)∧(¬q∨¬p)                           //조건문을 논리합으로 바꿈

         ≡ (q∨p)∧(¬p∨¬q)                           //교환법칙을 이용

         ≡ (¬q→p)∧(p→¬q)                          //논리합을 조건문으로 교환하여 증명 완료

16

p↔q ≡ (p→q)∧(q→p)                             //쌍방조건문을 조건문으로 바꿈

       ≡ (¬p∨q)∧(¬q∨p)                           //조건문을 논리합으로 바꿈

       ≡ (q∨¬p)∧(p∨¬q)                           //교환법칙을 이용

       ≡ (¬q→¬p)∧(¬p→¬q)                      //논리합을 조건문으로 바꿈

       ≡ (¬p→¬q)∧(¬q→¬p)                      //교환법칙을 이용

       ≡ ¬p↔¬q                                      //조건문을 쌍방조건문으로 바꿈으로써 증명 완료

17

(p→q)→(r→s)와 (p→r)→(q→s)이 논리적 동치가 아님을 보이는 것은 각 명제변수에 진리값을 대입하여 전체 복합명제의 진리값을 비교하면된다. 만약 p ≡ F, q ≡ F, r ≡ T, s ≡ F 이면 전자는 F, 후자는 T이다. 따라서 두 복합명제는 동치가 아니다.

18.1

0.2, 0.6

18.2

0.4, 0.2

18.3

0.8, 0.6

19

"이 명제는 거짓입니다." 라는 명제는 참일 경우 자신을 부정하고, 거짓일 경우 명제가 참이된다. 따라서 모순이다.

20

a) 우선 4개의 진술들이 있다고 가정하자. 그런경우 3번째 진술 "4개의 진술들 중에 정확하게 3개의 진술들이 거짓이다."가 참이며, 1,2,4번째가 거짓이다. 따라서 100개의 명제들 중 99번째 진술이 참이며 나머지 진술은 모두 거짓이다. 

b) 우선 4개의 진술이 있다고 가정하자. 그런경우 1,2번째 진술은 참이다. 따라서 100개의 진술들 중 1~50번째 진술이 참이며, 51번째부터 100번째까지의 진술은 거짓이다.

c) 우선 5개의 진술이 있다고 가정하자. 그런경우 이 진술 모음집은 3번째 중앙 진술에 의해 성립할 수 없다. 따라서 99개의 진술들은 모두 명제가 아니다.

21

"이발사들은 자기 스스로 면도를 하지 않는 사람들을 상대로만 면도를 한다." 이 경우, 이발사는 자기 스스로 면도를 하는 경우 "자기 스스로 면도를 하는 사람"이므로 자기 자신을 상대로 면도를 할 수없다. 이는 모순이다. 이발사가 자기 스스로 면도를 하지 않는다면 자신을 상대로 면도를 해야한다. 그러나 하는 경우 앞서 발생한 문제가 다시 발생한다. 따라서, 이 이발사는 존재 할 수 없다.

22

a) p∧¬q

b) p∨(q∧(r∨F))

c) (p∨¬q)∧(q∨T)

d) p∨¬q∨¬r

e) (p∨q∨r)∧s

f) (p∧T)∨(q∧F)

23

p∧F, p∨T, p∧(p∨q), p∨(p∧q)

24

임의의 복합명제의 dual은 기존 복합명제의 ∧를 ∨, ∨를 ∧, T를 F로 바꾸어서 얻을 수 있다. 그 dual의 dual은 다시 ∨를 ∧, ∧를 ∨, F를 T로 바꾸어서 얻을 수 있다. 따라서 원 복합명제와 같아진다.

25

∧, ∨, ¬, T, F로 이루어진 두 복합명제 P와 Q가 있다고 하자. 이 때, ¬P와 ¬Q는 또한 동치이다. 드모르간의 법칙을 기억해보면, 임의의 복합명제 P의 ¬P는 다음을 수행한다. ∧를 ∨, ∨를 ∧, T를 F, F를 T 그리고 마지막으로 각 atomic proposition앞에 ¬이 붙어지거나 떼어진다. P*, Q*와 ¬P, ¬Q의 차이는 atomic proposition의 진리값이 ¬에 의해 반전되는가의 차이 뿐이다. (P*와 ¬P의 차이를 진리표로 확인해보면 모든 row의 진리값이 마치 상하로 반전되어 있을 뿐이다. 상상해보자, 모든 atomic proposition이 반전되어 있다는 것은 진리표 맨 좌측에 기입하는 모든 atomic proposition의 진리값이 반전되어 원 복합명제의 위 아래가 반전되어 있는 모습이다.) 따라서 임의의 두 복합명제 P와 Q가 동치이면, ¬P와 ¬Q가 동치이기 때문에 P*와 Q* 또한 동치이다.

26

p∧q∧¬r

27

(¬p∧q∧r)∨(p∧¬q∧r)∨(p∧q∧¬r). 이는 disjunction normal form(DNF)이다. 

28

14 답 참고(쌍방 조건문)

29

p↔q ≡ (p→q)∧(q→p)                                //쌍방조건문을 조건문으로 바꿈

       ≡ (¬p∨q)∧(¬q∨p)                              //conjunction normal form 완성

30

임의의 복합명제 P가 주어져있을 때, 논리 연산자 모음 { ∧, ∨, ¬ }를 이용하여 동치이면서 DNF 또는 CNF인 복합명제 Q를 작성 할 수있다. 따라서 논리 연산자 모음 { ∧, ∨, ¬ }는 functionally complete이다. 

31

논리합은 논리곱으로 대체될 수 있다. 다음은 한 예이다.

p∨q ≡ ¬(¬p∧¬q)

따라서, 논리 연산자 모음 { ∧, ¬ }는 functionally complete 이다.

32

논리곱은 논리합으로 대체될 수 있다. 다음은 한 예이다.

p∧q ≡ ¬(¬p∨¬q)

따라서, 논리 연산자 모음 { ∨, ¬ }는 functionally complete 이다.

33

a)

p	p	¬p	p↓p
T	T	F	F
F	F	T	T

b)

p	q	p↓q	¬(p∨q)
T	T	F	F
T	F	F	F
F	T	F	F
F	F	T	T

c)

(p↓q)↓(p↓q) ≡ ¬(p∨q)↓¬(p∨q)                //  b)

       ≡ ¬[¬(p∨q)∨¬(p∨q)]             //  b)

        ≡ [(p∨q)∧(p∨q)]                   // double negation law, 이중 부정 법칙에 따라

        ≡ (p∨q)                              // 증명완료

d)

a), b), c)를 통해 논리연산자 ↓는 다음의 논리연산자 모음 { ∨,¬ } 으로 대체가능한 것을 알았다. { ∨,¬ }는 functionally complete 이고, 따라서 논리연연산자 모음 { ↓ } 또한 functionally complete 이다.

34

p→q ≡ ¬p∨q                          //조건문을 논리합으로 표현

       ≡ (p↓p)∨q                      //33 a) ¬p ≡ p↓p

       ≡ ¬((p↓p)↓q)                 //33 b) p↓q ≡ ¬(p∨q)                                   

       ≡ ((p↓p)↓q)↓((p↓p)↓q)   //33 a) ¬p ≡ p↓p

35

p ≡ T, q ≡ T, r ≡ F 일 때 전자 복합명제 p | (q | r)은 F의 진리값을 (p | q) | r은 T의 진리값을 가지므로 논리연산자 |는 결합법칙 조건을 만족하지 않는다.

36

두 명제변수 p,q로 생성한 임의의 복합명제 S는 원자명제 p, q의 4가지 조합 각 경우에 T, F 모두 가능하므로 총 2^4 = 16가지의 다른 진리표들을 기대할 수 있다.

37

세 복합명제 P, Q, R이 있다고 하자. 두 복합명제 P, Q가 동치라면 P, Q는 동일한 원자명제들로 구성된 복합명제이며 각 원자명제들의 진리값 경우에 따라 두 복합명제는 동일한 진리값을 가진다. 두 복합명제 Q, R이 동치인 경우에도 위와 같이 추론할 수 있다. 따라서 P, Q 또한 동치이다.

38

39

1 1열의 각 행은 숫자 1을 가지고 있다.

2 1열의 각 행은 숫자 1에서부터 9사이의 숫자를 가지고 있다.

3 각 열의 각 행은 숫자 1에서부터 9사이의 숫자를 가지고 있다. (이 경우 중복이 허용된다.

40

1 1번째 구역의 각 행은 숫자 1을 가지고 있다.

2 1번째 구역의 각 열의 각 행은 숫자 1을 가지고 있다.

3 1번째 구역의 각 열의 각 행은 1에서부터 9사이의 숫자를 가지고 있다.

4 각 구역의 각 열의 각 행은 1에서부터 9사이의 숫자를 가지고 있다.

문제를 푸시느라 수고하셨습니다.

갑자기 paradox story, fuzzy logic, dual, DNF, CNF, functionally complete, sudoku application 이 나와서 당황하셨을거라 생각합니다. 뜬금없는 아이큐 문제같은 그런 식의 유형은 개인적으로 별로 추구하고 있지 않습니다. 그래서 시험시간을 충분히 생각할 수 있게 48시간을 주어보았습니다. 

이번 장의 가장 중요한 내용은 모든 논리의 구조는 { and, negation }과 같은 functionally complete인 논리연산자로 구성할 수 있다는 것을 아는 것이 중요합니다. 즉, functionally complete인 논리연산자들을 가지고 모든 복합명제와 동치equivalent이게 만들 수 있습니다. 이는 우리가 가장 간단한 논리연산자들을 가지고 어떠한 논리 명제라도 만들 수 있고 그것의 진리값을 판별할 수 있다는 강한 자신감을 불어넣어줍니다. 

이제 좀 더 성장하기 위해 다음 단계로 전진해볼까 합니다. 

다음 포스팅에서는 명제함수와 정량자quantifier에 대해서 살펴볼 것입니다.