이산수학 요점정리 (3/5)

Propositional logic 명제 논리 문제

1. 진리값 작성

문제 :

표현식에 해당하는 진리값을 T 또는 F로 채우시오. (음영 영역에 정답 표시)

P	Q	expression	Value
T	T	P V Q	T
T	F	P Λ ¬ Q	T
F	T	P → Q	T
F	F	¬P ↔ Q	F

2. 명제식으로 표현하기

문제:

다음을 명제식으로 표현하시오.

 

"톰은 수학 전공이고, 컴퓨터 싸이언스 전공은 아니다."

 

P: 톰은 수학 전공이다.

Q: 톰은 컴싸 전공이다.

 

드 모르간의 법칙을 사용하여 표현의 부정을 작성하고, 의미를 적으시오.

 

답:

명제식으로 표현하기

P Λ ¬ Q (톰은 수학 전공이고, 컴싸 전공은 아니다.)

 

드모르간 법칙 적용하기

¬ (P Λ ¬ Q) = ¬ P V Q (드모르간 법칙)

 

c. 의미

¬ P V Q 는 P → Q 와 같다.

만약 톰이 수학 전공이 아니면, 컴싸 전공이다.

 

3. Let

P = "존은 건강하다"

Q = "존은 부유하다"

R = "존은 현명하다"

 

존은 건강하고, 부유하지만, 현명하지 못하다.

P Λ Q Λ ¬ R

 

존은 부자가 아니지만, 건강하고 현명하다.

¬ Q Λ P Λ R

 

존은 건강하거나 부유하지도 않고, 지혜롭지도 한다.

¬ P Λ ¬ Q Λ ¬R

 

4. 문장을 명제식으로 작성해보자.

문제:

Neither the fox nor the lynx can catch the hare if the hare is alert and quick.

토끼가 놀라고 빠르면, 여우도 살쾡이도 토끼를 잡을 수 없다.

 

답:

P: The fox can catch the hare. 여우는 토끼를 잡을 수 있다.

Q: The lynx can catch the hare. 살쾡이는 토끼를 잡을 수 있다.

R: The hare is alert. 토끼는 놀란다.

S: The hare is quick. 토끼는 빠르다.

 

명제식으로 나타내면

(R Λ S) → ~P Λ ~Q

 

~P Λ ~Q 는 ~( P V Q)와 동일하기 때문에, 다른 번역은

(R Λ S) → ~( P V Q)

 

 

문제:

You can either (stay at the hotel and watch TV ) or (you can go to the museum and spend some time there)

당신은 (호텔에 머무르면서 TV를 보거나) (박물관에 가서 시간을 보내거나) 할 수 있다.

 

The parentheses are used to avoid ambiguity concerning the priority of the logical connectives.

괄호는 논리적 연결 요소의 우선 순위와 관련된 모호성을 피하기 위해 사용되었습니다.

 

답:

P: You stay at the hotel. 호텔이 머무른다.

Q: You watch TV. TV를 본다.

R: You go to the museum. 박물관에 간다.

S: You spend some time in the museum. 박물관에서 시간을 보낸다.

 

(P Λ Q) V (R Λ S)

 

5. 논리 법칙을 적으시오.

Commutative laws	P V Q ≡ Q V P P Λ Q ≡ Q Λ P
Associative laws	(P V Q) V R ≡ P V (Q V R) (P Λ Q) Λ R ≡ P Λ (Q Λ R)
Distributive laws:	(P V Q) Λ (P V R) ≡ P V (Q Λ R) (P Λ Q) V (P Λ R) ≡ P Λ (Q V R)
Identity	P V F ≡ P, P Λ T ≡ P
Negation	P V ~P ≡ T (excluded middle) P Λ ~P ≡ F (contradiction)
Double negation	~(~P) ≡ P
Idempotent laws	P V P ≡ P P Λ P ≡ P
De Morgan's Laws	~(P V Q) ≡ ~P Λ ~Q ~(P Λ Q) ≡ ~P V ~Q
Universal bound laws (Domination)	P V T ≡ T P Λ F ≡ F
Absorption Laws	P V (P Λ Q) ≡ P P Λ (P V Q) ≡ P
Negation of T and F	~T ≡ F, ~F ≡ T

 

6. 조건 명제(함축, 조건문)

6.1 문제:

다음 중 조건 명제 P → ~Q의 대우, 역, 이를 고르시오.

 

답: (중에 고르시오)

P → Q, ~Q → P, ~P → ~Q, ~P → Q, ~Q → ~P, Q → ~P

 

 

6.2 문제:

주어진 조건문 "If we are on vacation we go fishing.(우리가 휴가면, 낚시하러 간다.)"를 다음과 같이 작성하시오.

 

답:

a. 문장을 논리식으로 표현하시오. 

P: we are on vacation. 우리가 휴가다.

Q: we go fishing. 우리는 낚시하러 간다.

논리식 : P → Q

b. 부정 논리 표현을 작성하고, 번역하시오.

부정 : P Λ ¬ Q 

"We are on vacation and we do not go fishing."

우리가 휴가면, 낚시하러 가지 않는다.

c. 역 논리 표현을 작성하고, 번역하시오.

역 : Q → P

"If we go fishing, we are on vacation."

만약 우리가 낚시하러 가면, 우리는 휴가다.

d. 이 논리 표현을 작성하고, 번역하시오.

이 : ¬ P → ¬ Q

"If we are not on vacation, we don't go fishing."

만약 우리가 휴가가 아니면, 낚시하러 가지 않는다.

e. 대우 논리 표현을 작성하고, 번역하시오.

대우 : ¬ Q → ¬ P

"If we don't go fishing, we are not on vacation."

만약 우리가 낚시하러 가지 않으면, 우리는 휴가가 아니다.

 

6.3. 문제: 

역, 이, 대우를 작성하시오.

식	contrapositive (대우)	converse (역)	inverse (이)
P → Q	~Q → ~ P	Q → P	~P → ~Q
P → ~Q	Q → ~ P	~Q → P	~P → Q
~P → Q	~ Q → P	Q → ~P	P → ~Q
~P → ~Q	Q → P	~Q → ~P	P → Q
Q → ~P	P → ~Q	~P → Q	~Q → P
~Q → ~P	P → Q	~P → ~Q	Q → P

7. 다음의 추론이 유효한지 아닌지 판단하시오.

전제(Premises) 1

문제:

A. If I read the newspaper in the kitchen, my glasses would be on the kitchen table.

만약 내가 부엌에서 신문을 읽었다면, 나의 안경은 식탁에 있을 것이다.

 

B. I did not read the newspaper in the kitchen.

나는 부엌에서 신문을 읽지 않았다.

 

결론 : My glasses are not on the kitchen table.

나의 안경은 부엌에 있지 않다.

 

답:

유효하지 않은 추론이다.

 

P: I read the newspaper in the kitchen. 나는 부엌에서 신문을 봤다.

Q: my glasses would be on the kitchen table. 나의 안경은 식탁에 있을 것이다.

 

식으로 표현하면,

(1) P → Q

(2) ~P

(3) Therefore ~Q

 

우리는 P가 거짓이란 것을 안다.

만약 ~P 였으면 Q가 어떤 값이든 참이다.

 

따라서 우리는 Q가 참인지 거짓인지 알 수 없다.

위의 추혼은 역 오류(inverse error)라고 부른다.

 

전제(Premises) 2

문제:

내가 열심히 공부하지 않으면, 나는이 과정을 통과하지 못 할 것이다.

이 과정을 통과하지 못하면 올해 졸업 할 수 없다.

그러므로 열심히 공부하지 않으면 올해 졸업하지 못 할 것이다.

 

답:

이것은 가상적 삼단논법에 기반한(based on the hypothetical syllogism) 유효한 추론이다.

 

P: I don't study hard. 나는 열심히 공부하지 않는다.

Q: I will not pass this course. 나는 이 과정을 통과하지 못 할 것이다.

R: I cannot graduate this year. 나는 올 해 졸업을 할 수 없다.

 

식으로 표현하면,

(1) P → Q

(2) Q → R

(3) Therefore P → R

 

전제(Premises) 3

문제:

You will get an extra credit if you write a paper or if you solve the test problems.

서류를 작성하거나 시험 문제를 풀면 여분의 학점을 얻을 수 있습니다.

 

You don’t write a paper, however you get an extra credit.

당신은 종이를 쓰지 않지만 여분의 신용을 얻습니다.

 

Conclusion: You have solved the test problems.

결론 : 테스트 문제를 해결했습니다.

 

답:

유효하지 않은 추론.

 

P: you get an extra credit

Q: you write a paper 

R: you solve the problems

 

Formal representation:

(1) (Q V R) → P

(2) ~Q

(3) P

(4) Therefore R

 

The above argument is a combination of disjunctive syllogism and modus ponens, however the modus ponens is not applied correctly.

위의 추론은 분리주의 삼단논법과 긍정식의 조합이지만, 긍정식이 올바르게 적용되지 않습니다. 

 

The disjunctive syllogism consists in the following:

분리주의 삼단 논법은 다음과 같이 구성된다.

 

Given that (Q V R) is true, and that Q is false (~Q is true) we conclude that R is true.

However we cannot know whether Q V R is true, given that P is true.

The error in concluding that Q V R is true is called converse error.

 

주어진 (QVR)이 참이고 Q가 거짓 (~ Q는 참)이라면 R은 참이라고 결론을 내립니다.

그러나 P가 사실이라면 QVR이 참인지 여부를 알 수 없습니다. 

QVR이 사실이라고 결론 내릴 때의 오류를 역 오류 라고 합니다.

 

전제(Premises) 4

문제:

You will get an extra credit if you write a paper or if you solve the test problems.

서류를 작성하거나 시험 문제를 풀면 여분의 학점을 얻을 수 있습니다.

 

You don’t write a paper, however you get an extra credit.

당신은 종이를 쓰지 않지만 여분의 신용을 얻습니다.

 

Conclusion: You have not solved the test problems.

결론 : 테스트 문제를 해결 못 했습니다.

 

답:

 

유효한 추론.

 

P: you get an extra credit

Q: you write a paper 

R: you solve the problems

 

Formal representation:

(1) (Q V R) → P

(2) ~Q

(3) ~P

(4) Therefore ~R

 

From ~P we can conclude that Q V R is false (modus tollens). 

~ P에서 우리는 QVR이 거짓 (modus tollens)이라고 결론을 내릴 수 있습니다. 

 

A disjunction is false only when both of its sides are false. Hence R must be false.

분리는 양쪽이 모두 거짓 일 때만 거짓입니다. 따라서 R은 거짓이어야합니다.

 

Note, that the premise ~Q is not necessary. Since both sides of the disjunction must be false, Q must be false too.

전제 ~ Q는 필요하지 않습니다. 분리의 양측이 틀림이 틀림 없으므로 Q도 틀림이 틀림 없습니다. 

 

A valid argument would be the following one:

(1) (Q V R) → P

(2) ~P

(3) Therefore ~Q and ~R

 

유효한 추론은 다음과 같습니다.

(QVR) → P 

(2) ~ P 

(3) 따라서 ~ Q와 ~ R

 

 

 

 

Predicate logic 술어 논리 문제

문장을 술어 논리의 정량화된 표현으로 번역하고, 부정 표현을 적어 놓은 다음, 부정 표현을 영어로 번역하십시오.

사용되는 술어는 괄호 안에 표시됩니다.

 

1. Some problems are difficult. (problem(x), difficult(x))

 

$ x, (problem(x) ∧ difficult(x))

 

부정:

~($ x, (problem(x) ∧ difficult(x))) =

" x (~(problem(x) ∧ difficult(x))) =

" x (~problem(x) V ~ difficult(x)) =

" x (problem(x) → ~ difficult(x))

 

번역: No problems are difficult.

 

2. All students that study discrete math are good at logic. 

(student(x), study_discrete_math(x), good_at_logic(x))

 

" x (student(x) ∧ study_discrete_math(x) → good_at_logic(x))

 

부정:

~ (" x (student(x) ∧ study_discrete_math(x) → good_at_logic(x)) =

$ x (~ (student(x) ∧ study_discrete_math(x) → good_at_logic(x))) =

$ x (~ (~( student(x) ∧ study_discrete_math(x)) V good_at_logic(x))) =

$ x (~ ((~student(x) V ~study_discrete_math(x)) V good_at_logic(x))) =

$ x (~ ( ~student(x) V ~study_discrete_math(x) V good_at_logic(x))) =

$ x ((student(x) ∧ study_discrete_math(x)) ∧ ~ good_at_logic(x)))

 

번역:

There is a student that studies discrete math and is not good at logic

 

3. No students are allowed to carry guns. (student(x), carry_gun(x))

 

" x (student(x) → ~carry_gun(x))

 

부정:

~(" x, (student(x) → ~carry_gun(x))) =

$ x, ~(student(x) → ~carry_gun(x))) =

$ x, ~(~student(x) V ~carry_gun(x)) =

$ x, (student(x) ∧ carry_gun(x))

 

번역:

There is a student that carries a gun

 

4. International students are not eligible for federal loans. 

(international_student(x), eligible(x))

 

" x (international_student(x) → ~eligible(x))

 

부정:

~(" x (international_student(x) → ~eligible(x))) =

$ x, ~(international_student(x) → ~eligible(x)) =

$ x, ~(~international_student(x) V ~eligible(x)) =

$ x, (international_student(x) ∧ eligible(x))

 

번역:

Some international students are eligible for federal loans.

 

 

어렵다 어려워....