1장. 논리, 증명, 집합, 함수 (Logic, Proof, Sets and Functions) 1장 1절. 논리 (Logic) 숭실대학교 IT대학 컴퓨터학부
2008년 1학기
김완섭
wskim92@ssu.ac.kr
1.1 논리 (Logic) 함축(pq)의 의미
비가 오면, 사람들은 우산을 쓴다.
날씨가 추우면, 사람들은 모자를 뒤집어 쓴다.
“If I am elected, then I will lower taxes.”
p : 내가 당선된다.
q : 세금을 낮춘다.
pq : 내가 당선되면, 세금을 낮출 것이다. pq : 컴퓨터 학부 학생이면, IT 대학 학생이다.
p : 컴퓨터학부 학생이다.
q : IT 대학 학생이다. “p implies q” (p는 q를 암시/의미/함축/뜻/한다.)
“q follows from p” (p하고 나서 q하다.)
“if p, then q” (만약, p이면 q이다.)
“if p, q” (p이면 q이다.)
“q if p” (q이다. 만약 p라면)
“p only if q” (q일 경우에만 p일 수 있다.)
“q whenever p” (p일 때마다 q이다.)
“q when p” (p일 때, q이다.)
“p is sufficient for q” (p는 q하는데 충분하다.)
“p is a sufficient condition for q” “a sufficient condition for q is p”
“q is necessary condition for p” “a necessary condition for p is q”
“q is necessary for p” (q하는데 p가 필요하다.)
1.1 논리 (Logic) 역, 이, 대우
어떤 함축 pq가 주어졌을 때
그 함축 pq 로 부터 새로운 함축들을 생각해 볼 수 있다.
pq : 기말고사에서 90점 이상을 맞는다면, A학점을 받을 것이다.
p : 기말고사에서 90점 이상을 맞는다.
q : A학점을 받는다.
역 : A학점을 받았다면, 90점 이상을 맞은 것이다.
이 : 기말고사에서 90점 이상을 맞지 못하면, A학점을 받지 못할 것이다.
대우 : A학점을 받지 못했다면, 기말고사에서 90점 이상을 못 받은 것이다.
1.1 논리 (Logic) 역, 이, 대우
P Q P→Q Q→P ￢Q→￢P ￢P→￢Q T T
T F
F T
F F T
F
T
T T
T
F
T T
F
T
T T
T
F
T ￢q ￢p 대우 (contra-positive) ￢p ￢q 이 (inverse) q p 역 (converse) 함축 pq 로부터 만들어지는 몇 개의 관련 함축이 있다.
PQ는 대우 ￢Q￢P와 모든 경우에 동일한 진리값을 갖는다.
1.1 논리 (Logic) 역, 이, 대우
If the home team does not win, then it is not raining If the home team win, then it is raining. If it is not raining, then home team does not win. 예제 7 다음 함축의 대우, 역, 이는 무엇인가?
“If it is raining, then the home team wins.”
PQ , P : it is raining. , Q : the home team wins.
대우 :
역 :
이 :
1.1 논리 (Logic) 상호조건명제
다시 말하면, p↔q 는
pq 가 참인 경우와
qp 가 참인 경우를
모두 만족하는 것을 의미한다.
즉, (pq)∧(qp) 와 같다. 정의 6 상호조건명제(biconditional)
p와 q가 명제라 하면, “p↔q”를 상호조건명제(biconditional)라 하고,
p와 q가 동일한 진리값을 가질 때 참이 되며,
다른 진리값을 가질 경우에는 거짓이 된다.
1.1 논리 (Logic) 상호조건명제
⇔ P↔Q (PQ) (QP) ∧ T T T F F F F T T F F T F F T T T T T T (PQ)∧(QP) QP PQ Q P
1.1 논리 (Logic) p↔q 의 다른 표현들
pq : p only if q qp : p if q pq : p is sufficient for q qp : p is necessary for q “p if and only if q” (p iff q)
“p is necessary and sufficient for q.” (p는 q의 필요충분조건이다.)
“If p then q, and conversely” (p이면 q이다. 그 반대도 성립한다.)
상호조건을 나타내는 “if and only if” 라는 표현은 실제로는 영어에서도 거의 사용되지 않는 용어이다.
상호 조건을 나타내기 `위해서는 주로 “if, then” 이나 “only if” 라는 표현을 많이 사용한다.
1.1 논리 (Logic) 논리 연산자 우선 순위
연산자 우선순위 참고
-5 + 3 * 2 = (-5) + 3 * 2
= (-5) + (3*2)
= (-5) + (6)
= 1 p∨q∧r 은
p∨(q∧r) 이다.
(p∨q)∧r 이 아니다. 여러 가지 논리 연산자를 이용하여 복합 명제를 만들 수 있다.
논리 연산자는 우선순위를 갖는다. (표8 참고)
p∨q∧~r
p∨q∧(~r)
p∨(q∧(~r))
(p∨(q∧(~r)))
p∨q ~r
p∨q (~r)
(p∨q) (~r)
((p∨q) (~r))
1.1 논리 (Logic) 영어 문장의 논리 표현 변환
예제 9
다음 문장을 논리 표현으로 어떻게 바꿀 수 있는가?
“You can access the Internet from campus only if you are a computer science major or you are not a freshman.”
명제 p, q, r을 아래와 같이 정의하자.
p : “You can access the Internet from campus”
q : “You are a computer science major”
r : “You are a freshman”
위에 의해서, (p) only if (q∨~r) 이라고 표현될 수 있다.
only if 를 사용하는 문장이므로 (A only if B 는 “B일 경우에만 A이다”라는 의미로서 AB로 변환될 수 있다. 앞부분 참고할 것.)
따라서, pq∨~r 로 표현된다.
1.1 논리 (Logic) 영어 문장의 논리 표현 변환
예제 10
다음 문장을 논리 표현으로 어떻게 바꿀 수 있는가?
“You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.”
명제 p, q, r을 아래와 같이 정의하자.
p : “You can ride the roller coaster”
q : “You are under 4 feet tall”
r : “You are older than 16 years old”
그러면, 주어진 문장은 (q∧~r)~p 으로 표현될 수 있다.
1.1 논리 (Logic) 시스템 기능 사양의 논리적 표현
예제 11
아래의 설계 사양에 관련된 문장을 논리 연산자를 사용하여 표현하라. “The automated reply cannot be sent when the file system is full.”
명제 p, q을 아래와 같이 정의하자.
p : “The automated reply can be sent.”
q : “The file system is full.”
그러면, 주어진 문장은 q ~p 으로 표현될 수 있다.
1.1 논리 (Logic) 시스템 기능 사양의 논리적 표현
예제 12 다음 시스템 설계 사양 문장이 일관성이 있는지 판정하라.
“The diagnostic message is stored in the buffer or it is retransmitted”
“The diagnostic message is not stored in the buffer.”
“If the diagnostic is stored in the buffer, then it is retransmitted.”
일관성을 판정하기 위해 먼저 논리 표현으로 변환해보자.
p : “The diagnostic message is stored in the buffer.”
q : “The diagnostic message is retransmitted.”
1라인 : p∨q , 2라인 : ~p , 3라인 : pq
~p가 참이 되기 위해서는 p가 거짓이되어야 한다.
p∨q가 참이 되기 위해서는 (p가 거짓이므로) q가 참이 되어야 한다.
p가 거짓이고 q가 참이므로, pq는 참이 된다. 따라서 일관성 있음!!!.
1.1 논리 (Logic) 논리 수수께끼(Logic Puzzles)
A: 기사
B: 기사 P: B는 기사이다. Q: 우리는 계급이 서로 다르다. P가 참 (즉, B는 기사)
Q가 참 (즉, A는 악당) A: 기사
B: 악당 P가 참 (즉, B는 기사)
Q가 거짓 (즉, A는 기사) A: 악당
B: 기사 P가 거짓 (즉, B는 악당)
Q가 참 (즉, A는 기사) A: 악당
B: 악당 P가 거짓 (즉, B는 악당)
Q가 거짓 (즉, A는 악당) 예제 12 아래의 수수께끼를 풀어보자.
항상 진실만을 이야기하는 기사와 항상 거짓만을 이야기하는 악한들이 사는 섬이
있다. 당신은 이 섬을 여행하는 중에 어떤 두 사람(A,B)을 만났다.
A가 “B는 기사이다.”라고 말하고, B가 “우리는 계급이 서로 다르다”라고 말했다면,
A, B 각 사람은 어떤 계급에 속하는가?
1.1 논리 (Logic) 논리 수수께끼(Logic Puzzles)
예제 13 아래의 수수께끼를 풀어보자.
아버지가 그의 아들과 딸에서 몸을 더럽히지 말고 정원에서 놀라고 했다.
그런데 놀면서 두 아이가 모두 이마에 진흙을 묻혔다. 놀이를 그만 두었을 때,
아버지가 “너희 중 적어도 한 명은 이마에 흙을 묻혔다”라고 말하고
아이들은 각각에게 “네 이마에 흙이 묻은 것을 알고 있니?”라고 하는 물음에
두 차례 묻고, 예, 아니오 로만 대답하게 했다. 아이들은 상대방의 이마에 흙이 묻은 것을 볼 수 있지만, 자신들의 머리에 흙이 묻었는지는 볼 수 없다고 할 때 아이들이 대답은 무엇이 되겠는가? 아이들은 진실만을 이야기하고 각각의 물음에 두 아이가 동시에 대답한다고 가정한다.
아니요. 아니요. 예 예 두 아이가 놀다가 모두 이마에 흙이 묻었다. S∨D 가 참이다. S가 참 D가 참
너희 중 적어도 한 명은 이마에 흙이 묻었다.
Q1. 네 이마에 흙이 묻은 것을 알고 있니?
Q2. 네 이마에 흙이 묻은 것을 알고 있니?
1.1 논리 (Logic) 논리와 비트 연산
컴퓨터는 정보를 비트로 표현한다. (비트는 0 또는 1의 값만 가짐)
컴퓨터 과학 분야에서는 1을 참, 0을 거짓이라고 약속하고 사용한다.
컴퓨터의 비트 연산은 논리 접속사와 대응한다.
1.1 논리 (Logic) 논리와 비트 연산
어떤 정보를 표현하기 위해서는 하나의 비트만으로 부족하므로 이들은 연속적으로 사용하여 정보를 표현한다.
정의 7.
비트 문자열(bit-string)이란 0개 이상의 비트를 갖는 비트열을 말한다.
비트 문자열의 길이(length)란 문자열을 구성하는 비트의 수를 말한다.
예제 17. 101010011은 길이가 9인 비트 문자열이다.
1.1 논리 (Logic) (bitwise 연산 방법)
Example
01 1011 0110
11 0001 1101
11 1011 1111 : bitwise OR
01 0001 0100 : bitwise AND
10 1010 1011 : bitwise XOR Bitwise 연산이란 bit-string에 대한 연산을 의미함.
Comments