Exercises : propositions and logical operation, equivalences

수학 원리에서...

1.01 p→q = ~p∨q Df.

앞으로 "Df"의 단어는 정의를 뜻한다. 이 단어와 같다라는 기호 equal symbol은 왼쪽 항의 복합명제가 우항의 복합명제를 의미한다고 정의한다. 즉, 정의되는 것은 왼쪽 항이다. 우리는 가장 단순한 논리연산자 부정형negation과 논리합disjunction을 기초로 사용하기 때문이다. 조건문의 필요성은 다음에 의해 기인한다. "한 명제 p가 참일 때 그것이 의미하는 q가 반드시 참이여야 한다." 조건문은 증명에 반드시 필요하다. 그러나 어떠한 명제 p가 거짓일 때 그것이 의미하는 어떠한 것들에 대해서 진리값을 판단하려는 의미는 아니다. 그러므로, p가 참일 때 q가 거짓일 때만 거짓이라고 판단한다. p가 거짓이거나 q가 참일때는 항상 참이다. 따라서 조건문은 다음과 같이 볼 수 있다. "p가 거짓이거나 q가 참이다" 

1.1 한 명제가 참일 때 그것이 의미하는 임의의 명제는 반드시 참이다.

위의 명제은 "p가 참이면 다음을 만족한다. p이면 q가 참일 때, q는 참이다." 를 뜻하는 것이 아니다. (기호논리로는 p→[(p→q)→q]) 앞서 설명한 명제는 참이지만, p가 참이 아니거나 p이면 q가 아니더라도 참이다. 우리는 어떤 참인 전제도 없이 q를 주장하려는 것이 아니다. 1.1 명제는 기호로 표시할 수가 없는 것이 조건문에서 p라는 명제변수는 조건문의 전제로써 p가 참임을 전제하는 것이지만, 실제로 우리가 참이라고 이미 정의 내린 명제(공리) 등은 실제로 참이기 때문이다. (우리는 참인 블럭들을 쌓아 올린다는 것을 명심하자.)

ㅈ ㅏ~ 이번 포스팅에서는 문제를 살펴볼 것입니다. 소요시간 48시간

Exercises

1 다음 중 명제인 것은? 명제의 진리값은 무엇인가?

a) 대한민국의 수도는 서울이다.

b) 이 질문에 답하시오.

c) x+2 = 11

d) 5+7 = 12

2 다음 명제들의 부정형은 무엇인가?

a) 민수와 민환은 나의 친구이다.

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

c) 121은 11의 제곱이다.

3 p와 q를 명제라고 하자.     p: 나는 이번 주 복권을 샀다. q: 나는 1등 상금을 얻었다.

다음의 명제들을 한글로 표현하라.

a) ¬p      b) p∨q        c) p→q       d) p∧q    

e) p↔q    f) ¬p→¬q    g)¬p∧¬q    h) ¬p∨(p∧q)

4 p와 q를 명제라고 하자.     p: 지금은 영하이다. q: 눈이 내리고 있다.

다음의 문장들을 명제변수와 논리 연산자를 이용하여 명제로 표현해보자.

a) 지금 영하이고 눈이 내리고 있다.                b) 지금 영하이지만 눈이 내리지는 않는다.

c) 지금 영하가 아니고 눈이 내리고 있지 않다.   d) 지금 영하이거나 눈이 내리고 있다.

e) 지금 영하이면, 눈이 내리고 있다.                f) 영하이거나 눈이내리고 있지만, 영하이면 눈이 내리지는 않는다.

g) 영하이면 눈이오고, 눈이오면 영하이다.

5 p, q, r이 명제라고 하자.    p: 넌 감기가 걸렸다. q: 넌 마지막 시험을 놓쳤다. r: 넌 강의를 수료했다.

다음의 명제들을 한글로 표현하라.

a) p→q                 b) ¬q↔r               c) q→¬r            d)p∨q∨r

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

6 p, q, r이 명제라고 하자.    p : 넌 기말 시험에서 A를 받는다. q : 넌 이 책의 모든 예제를 푼다. r : 이 강의에서 A 학점을 받는다.

다음의 문장들을 명제변수와 논리 연산자를 이용하여 명제로 표현해보자.

a) 넌 이 강의에서 A학점을 받지만, 이 책의 모든 예제를 풀지는 않았다.

b) 넌 기말시험에서 A를 받고, 이 책의 예제를 모두 풀고, 강의에서 A학점을 받는다.

c) 넌 이 강의에서 A학점을 받기위해서는, 기말시험에서 A를 받는 것이 필요하다.(필요조건)

d) 넌 기말시험에 A를 받지만, 이 책의 모든 예제를 푼 것은 아니다. 그럼에도, 이 강의에서 A학점을 받는다.

e) 기말시험에서 A를 받고 이 책의 모든 예제를 푸는 것은, 이 강의에서 A학점을 받기엔 충분하다.(충분조건)

f) 이 강의에서 A를 받을 거라면, 이 책의 예제를 모두 다 풀어보거나 기말 시험에 A를 받은 것이다. 그리고 이 책의 예제를 모두 다 풀어보거나 기말 시험에 A를 받은 것이면, 이 강의에서 A를 받을 것이다. 

7 다음 복합명제의 진리표를 작성하시오. ((p→q)→r)→s

8 다음 복합명제의 진리표를 작성하시오. (p↔q)↔(r↔s)

9 다음의 동치들을 진리표를 이용하여 증명하시오

a) p∧T ≡ p     b) p∨F ≡ p    c) p∧F ≡ p    d) p∨F ≡ T    e) p∨p ≡ p    f) p∧p ≡ p

10 ¬(¬p)가 p와 논리적으로 동치임을 보여라.

11 다음의 교환법칙을 진리표를 이용하여 증명하시오

a) p∨q ≡ q∨p                b) p∧q ≡ q∧p

12 다음의 결합법칙을 진리표를 이용하여 증명하시오

a) (p∨q)∨r ≡ p∨(q∨r)       b) (p∧q)∧r ≡ p∧(q∧r)   

13 다음의 분배법칙을 진리표를 이용하여 증명하시오

p∧(q∨r) ≡ (p∧q)∨(p∧r)

14 p↔q와 (p∧q)∨(¬p∧¬q)가 동치임을 증명하라.

15 ¬p↔q와 p↔¬q이 논리적 동치임을 증명하라.

16 p↔q와 ¬p↔¬q이 논리적 동치임을 증명하라.

17 (p→q)→(r→s)와 (p→r)→(q→s)이 논리적 동치가 아님을 증명하라.

18 퍼지논리fuzzy logic은 인공지능에서 사용됩니다. 퍼지논리에서는, 명제는 0과 1을 포함한 그 사이의 진리값을 가집니다. 진리값이 0인 명제는 거짓이고 1인 명제는 참입니다. 0과 1사이의 진리값은 참의 정도를 나타냅니다. 예로, 명제 "민수는 기쁘다"에 진리값 0.8이 지정될 수 있습니다. 이 경우 민수는 대부분의 시간동안 행복했었던 것입니다. 다른 예로, 명제 "재우는 기쁘다"에 진리값 0.4가 지정되는 경우 재우는 그것보다 한 반 시간정도 행복했기 때문입니다.

18.1 퍼지논리fuzzy logic에서 명제의 부정은 1에서 명제의 진리값을 뺀 값 입니다. 다음 두 명제 "민수는 기쁘지 않다." "재우는 기쁘지 않다." 의 진리값은 무엇입니까?

18.2 퍼지논리에서 두 명제의 논리곱conjunction의 진리값은 두 명제의 진리값 중 가장 작은minimum 진리값을 따릅니다. 다음 두 명제의 진리값은 무엇입니까? "민수와 재우는 기쁘다." "민수도 재우도 기쁘지 않다."

18.3  퍼지논리에서 두 명제의 논리합disjunction의 진리값은 두 명제의 진리값 중 가장 큰maximum 진리값을 따릅니다. 다음 두 명제의 진리값은 무엇입니까? "민수는 기쁘거나 재우가 기쁘다." "민수가 기쁘지 않거나, 재우가 기쁘지 않다."

19 다음 진술 "이 명제는 거짓입니다." 는 명제입니까?

20 100개의 진술들이 존재한다. n번 째의 진술은 다음과 같다. "100개의 진술들 중에 정확하게 n개의 진술들이 거짓이다." 

a) 이 때 이 진술들로부터 어떤 결론을 도출할 수 있습니까?

b) 만약 n 번째 진술이 "100개의 진술들 중에 적어도 n개의 진술들이 거짓이다." 일때 a)를 답하시오.

c) 만약 진술들이 99개 존재할 때, b)에 답하시오.

21 고대 시칠리안에서 한 동네에는 이발사들은 자기 스스로 면도를 하지 않는 사람들을 상대로만 면도를 했었습니다. 이 때, 이런 이발사는 존재할 수 있을까요?

복합명제의 쌍대dual은 다음의 논리 연산자 ∨,∧,¬만으로 이루어져 있습니다. 한 복합명제 dual은 그 복합명제의 다음의 논리연산자 ∨를 ∧로, ∧를 ∨로, 각 T를 F로, 각 F를 T로 바꾸면 얻을 수 있습니다. 앞으로 복합명제 s의 dual을 s*로 표현하겠습니다.

22 다음 복합명제들의 dual을 구하시오.

a) p∨¬q                b) p∧(q∨(r∧T))            c) (p∧¬q)∨(q∧F)

d) p∧¬q∧¬r           e) (p∧q∧r)∨s              f) (p∨F)∧(q∨T)

23 s는 복합명제일 때, s*=s 를 언제 만족합니까?

24 s가 복합명제일 때, (s*)*=s 임을 증명하시오.

25 두 복합명제가 동치일 때, 그 두 복합명제의 dual이 서로 동치임을 증명하시오.

26 한 복합명제가 명제변수 p, q, r로 이루어져있다. 이 복합명제는 p와 q가 참이고 r이 거짓일 때 참이다. 이 복합명제는 나머지 경우에는 모두 거짓이다. 이 때 이 복합명제를 찾아라. [힌트 : 각 명제변수 또는 그 부정의 논리곱을 이용하라] 

27 한 복합명제가 명제변수 p, q, r로 이루어져있다. 이 복합명제는 정확히 p, q, r 중 두 개가 참일때 참이다. 그 외에는 이 복합명제는 모두 거짓이다. 이 때 이 복합명제를 찾아라. [힌트 : 논리곱의 논리합을 이용하라. 각 항에서는 논리곱이 괄호(높은 우선순위)로 먼저 수행되는데 이 조합이 위의 조건을 만족해야한다. 여기서 각 항은 반드시 세 명제변수, 또는 그 부정을 포함해야한다.]

아래는 두 명제변수와 각 논리연산자의 조합을 표현한 진리표이다. 후의 문제를 풀 때 참고하시오. 

p	q	p∨q	p∧q	p→q	p↔q	p→¬q	p⊕q	p↓q	p|q
T	T	T	T	T	T	F	F	F	F
T	F	T	F	F	F	T	T	F	T
F	T	T	F	T	F	T	T	F	T
F	F	F	F	T	T	T	F	T	T

28 n개의 명제변수를 사용하는 진리표를 가정해보자. 이 진리표에서 각 명제변수 또는 그 부정을 모두 이용한 논리곱의 논리합 형태로 임의의 복합명제를 만들어 보자. 이는 문제27의 확장이다. n을 임의의 자연수로 두고 복합명제를 생성해보시오. 이 결과를 논리합 정규식disjunctive normal form(DNF)이라고 한다. [힌트 : p↓q는 ¬(p∨q)와 동치이다. 이 것의 DNF는 ¬p∧¬q 이고, CNF는 (¬p∨¬q)∧(¬p∨q)∧(p∨¬q) 이다.]

29 n개의 명제변수를 사용하는 진리표를 가정해보자. 이 진리표에서 각 명제변수 또는 그 부정을 모두 이용한 논리합의 논리곱 형태로 임의의 복합명제를 만들어 보자. 이는 문제28의 연장이다. n을 임의의 자연수로 두고 복합명제를 생성해보시오. 이 결과를 논리곱 정규식conjunctive normal form(CNF)이라고 한다.[힌트 : p|q는 ¬(p∧q)와 동치이다. 이 것의 DNF는 (p∧¬q)∧(¬p∧q)∧(¬p∧¬q) 이고, CNF는 ¬p∨¬q 이다.]

만약 모든 복합명제가 임의의 논리 연산자들을 포함한 한 복합명제와 논리적으로 동치라면 그 논리 연산자들의 모음을 기능적으로 완벽functionally complete하다고 한다. 즉, 어떠한 논리연산자들로만 이용해서 임의의 복합명제들을 만들 수 있다면 그 논리연산자들이 functionally complete하다고 한다. 참고로 principia mathematica에서도 { ∧,∨,¬ } 으로 부터 조건문과 쌍방조건문 등 그 외의 여러 연산자들을 정의하였다. 따라서 { ∧,∨,¬ }는 functionally complete이다. or 연산자 ∨는 ¬(¬p∧¬q)로 정의되므로 { ∧,¬ } 또한 functionally complete이다. and 연산자 ∧ 또한 ¬(¬p∨¬q)로 정의되므로 { ∨,¬ }는 functionally complete이다.  그외의 functionally complete logical operator set은 다음과 같다. { | }, { ↓ }.

30 다음 논리 연산자 모음 { ∧,∨,¬ }이 functionally complete인지 증명하시오. [ 힌트 : 모든 복합 명제와 논리적으로 동치인 어느 한 논리합 정규식disjunctive normal form 반드시 존재한다는 사실을 이용하시오.]

31 다음 논리 연산자 모음 { ∧,¬ }이 functionally complete인지 증명하시오. [ 힌트 : 먼저 드 모르간의 법칙을 이용하여 논리합을 논리곱으로 표현할 수 있음을 보이시오 ]

32 다음 논리 연산자 모음 { ∨,¬ }이 functionally complete인지 증명하시오.

33 이제부터 논리 연산자 모음 {↓}이 functionally complete인지 증명할겁니다.

a) p↓p가 ¬p와 논리적 동치임을 증명하시오.

b) p↓q가 ¬(p∨q)와 논리적 동치임을 증명하시오.

c) (p↓q)↓(p↓q)가 p∨q가 논리적 동치임을 증명하시오.

d) a)와 b)의 c)의 결론을 이용하여, 논리 연산자 모음 {↓}이 functionally complete인지 증명하시오.

34 논리 연산자 모음 {↓}을 이용하여 p→q와 논리적 동치인 복합명제를 찾으시오. 

35 p | (q | r) 과 (p | q) | r이 논리적 동치이지 않음을 보이시오. 이는 논리 연산자 |는 결합법칙이 성립하지 않음을 보여줍니다.

36 명제변수 p, q를 이용하여 생성할 수 있는 진리표의 수는 몇 가지가 있습니까? 이는 진리표가 포함하는 논리연산자의 수에 상관없습니다.

37 P, Q, R이 복합명제라고 하자. P와 Q가 논리적으로 동치이고 Q와 R이 논리적 동치이면, P와 R이 논리적 동치임을 보이시오.

38 9*9 스도쿠 퍼즐에서 각 셀은 반드시 적어도 하나의 숫자를 가지고 있어야 한다는 복합명제를 만들어 보아라.

39 9*9 스도쿠 퍼즐에서 모든 열은 반드시 1에서 부터 9까지의 숫자를 가지고 있어야 한다는 복합명제를 만들어 보아라. 각 단계들을 설명하여라. 

40 9*9 스도쿠 퍼즐에서 모든 3*3 작은 사각형 9개에는 각각 반드시 1에서 부터 9까지의 숫자를 가지고 있어야 한다는 복합명제를 만들어 보아라. 각 단계들을 설명하여라.