이산수학 논리 - 명제, 논리 연산, 술어 논리, 추론

명제

명제

참과 거짓을 구별할 수 있는 문장이나 수학적 식을 명제라고 한다.

명제의 진리값

• 참 (True), T: 명제가 타당한 경우
• 거짓 (False), F: 명제가 타당하지 않은 경우

명제의 종류

• 합성명제
• 조건명제, 쌍조건명제
• 항진명제, 모순명제

명제의 예

1. 다음 문장이 명제인지 아닌지 구분해보자

(1) 6은 2의 배수다. -> 명제이다
(2) 철수는 공부를 잘한다 -> 명제가 아니다.
(3) 2+3=7 -> 명제이다(진리값이 거짓임).
(4) x +2 = 0 -> x의 값에 따라서 참일 수도 있고, 거짓일 수도 있다. 따라서 명제가 아니다.

 

 

2. 다음 명제의 진리값을 구하라

(1) 2,3,6는 소수이다. -> F
(2) 소수의 개수는 무한하다. -> T
(3) 126 = 2^6 -> F
(4) 지구에서 가장 높은 산은 에베레스트이다. -> T

 

논리 연산

기본적인 논리 연산의 종류에는 논리합, 논리곱, 부정, 배타적 논리합이 있다.

합성명제

하나 이상의 명제와 논리연산자 그리고 괄호로 이루어진 명제

논리합 (disjunction; or, ∨)

• p $\vee$ v
• 진리표

p	q	p $\vee$ v
T	T	T
T	F	T
F	T	T
F	F	F

논리곱 (conjunction; and, $\wedge$)

• p $\wedge$ v
• 진리표

p	q	p $\wedge$ v
T	T	T
T	F	F
F	T	F
F	F	F

부정 (negation; ~, $\neg$)

• $\neg$ p
• 진리표

p	~p
T	F
F	T

배타적 논리합 (exclusive or; xor, $\oplus$)

• p$\oplus$q $\equiv$ (p $\wedge$ $\neg$ q) $\vee$ ($\neg$ p $\wedge$ q)

조건 명제

명제 p와 q가 있을 때, 명제 p가 조건의 역할을 수행하고 명제 q가 결론의 역할을 수행하는 경우

• p $\rightarrow$ q (p$\Rightarrow$q)

p는 q의 충분조건
q는 p의 필요조건

p	q	p $\rightarrow$ q
T	T	T
T	F	F
F	T	T
F	F	T

쌍조건명제 (conditional proposition, $\longleftrightarrow$)

명제 p와 q가 있을 때, 명제 p와 q가 조건의 역할과 결론의 역할을 동시에 수행하는 경우

• p $\longleftrightarrow$ q (p $\Leftrightarrow$ q)
• (p $\rightarrow$ q) $\wedge$ ( q $\rightarrow$ p)

p	q	p $\rightarrow$ q	q $\rightarrow$ p	p $\longleftrightarrow$ q
T	T	T	T	T
T	F	F	T	F
F	T	T	F	F
F	F	T	T	T

동치

논리적 동치

두 명제 p와 q가 논리적으로 동등하면 논리적 동치라고 하고, p $\equiv$ q로 표시한다.
-> 논리적으로 동등하다는 말은 두 명제가 항상 동일한 진리값을 가진다는 의미

역, 이, 대우

• 조건 명제 p $\rightarrow$ q
  • 역(converse): q $\rightarrow$ p
  • 이(inverse): ~p $\rightarrow$ ~q
  • 대우(contrapositive): ~q $\rightarrow$ ~p

항진명제와 모순명제

합성명제를 구성하는 명제의 진리값과 상관없이

1) 항상 참인 명제를 항진명제라고 한다
2) 항상 거짓인 명제를 모순명제라고 한다

술어논리

"소크라테스는 사람이다"라는 명제는 술어논리로는 다음과 같이 표현된다. 

→ 사람(소크라테스) 

명제함수

변수의 값에 의해 함수의 진리값이 결정되는 문장이나 식 

• 변수의 명세

-> 변수의 값을 적시 -> 명제함수 p(x,y)가 x^2 + y^2 = 4일때 p(1,2)의 진리값은?
-> 변수의 범위를 제시 -> 한정화: $\forall$, $\exists$

한정화

전체 한정사(universal quantifier, $\forall$)

전체한정자는 "모든" 또는 "임의의"를 의미하며, 명제함수 $\forall$xP(x)와 같이 사용되었을 경우에는 정의역의 모든 임의의 x에 대해서 P(x)가 참임을을 의미한다.

존재 한정자(existential quantifier, $\exists$)

존재한정자는 "존재한다"를 의미하며, 명제 $\exists$ xP(x)와 같이 사용되었을 때는 정의역의 어떤 x에 대해서 P(x)가 참임을 의미한다.

타당성 검사

• 벤다이어그램 : 한정자가 사용된 명제함수의 타당성을 직관적으로 검사함

추론

참으로 알려진 명제를 기초로 하여 다른 명제를 유도해 내는 과정을 추론이라고 한다.

1) 결론을 근거로 제공하는 알려진 명제를 전제라고 한다.
2) 새로 유도된 명제는 결론이다.

유효추론

• 유효추론은 전제를 참이라고 가정하였을 때 결론이 항상 참이되는 추론

사람이 척추동물이면, 사람은 등뼈를 가질 것이다.
사람이 등뼈를 가지고 있다면, 사람은 목뼈와 허리 뼈를 가질 것이다. 

∴ 사람이 척추동물이면 목뼈와 허리뼈를 가질 것이다.

"사람은 척추동물이다"를 명제 p, "사람이 등뼈를 가지고 있다"를 명제 q, "사람이 목뼈와 허리뼈를 가질 것이다"를 명제 r이라고 한다면 위 결론은 다음과 같은 식으로 표현될 것이다. 

 

((p→q)∧q→r))→(p→r)

 

위의 추론은 전제 p→q 와 q→r이 모두 참일 경우 결론 p→r도 참이므로 올바른 추론이라고 할 수 있다. 

 

추론 규칙

기본적인 추론규칙은 논리적 동치(항진명제)를 이용함

법칙이름	추론법칙	항진명제
선언적부가	p $\therefore$ p$\vee$ q	p $\rightarrow$ (p $\vee$ q)
단순화	p $\wedge$ q $\therefore$ p	(p $\wedge$ q) $\rightarrow$ p
긍정논법	p p$\rightarrow$q $\therefore$ q	(p $\wedge (p $\rightarrow$ q)) $\rightarrow$ q

---

 

 

 

예제

1. 다음 명제들의 논리합을 작성하고 진리값을 구하시오.

(1)
p: 3>1 
q: 4>8

(2)
p: 2X3 = 8
q: 4-2 = 3
r: 소크라테스는 살아 있다. 

풀이

1) p ∨ q는 "3 > 1이거나 4> 8이다"가 된다. 여기서 p는 참이므로 q의 진리값과 상관없이 합성 명제 p ∨ q의 진리값은 참이다. 

2) p∨q∨r은 "2X3=8 또는 4-2=3 또는 소크라테스는 살아 있다"가 된다. 여기서 p, q, r은 모두 거짓이므로 합성명제 p∨q∨r은 거짓이다. 

 

 

 

2. 다음 명제의 논리곱을 작성하고 진리값을 구하시오.

 

1)

p: 홀수와 홀수를 더하면 짝수이다.

q: 짝수와 홀수를 곱하면 짝수이다. 

 

2) 

p: 키보드는 입력장치이다.

q: USB는 메모리이다.

r: 모니터는 기억장치이다. 

 

풀이: 

1) p∧q는 "홀수와 홀수를 더하면 짝수이고 짝수와 홀수를 곱하면 짝수이다"가 된다. 여기서 명제 p와 q는 모두 참이므로 합성명제 p∧q의 진리값은 참이다. 

2)p∧q∧r은 "모니터는 기억장치이고, USB는 메모리이고, 키보느는 입력장치이다"이다. 여기서 명제 r은 거짓이므로 명제 p와 q의 진리값에 상관없이 합성명제 p∧q∧r은 거짓이다.

 

 

3. 합성명제 (p∧q)∨(p⊕q)의 진리표를 작성하시오 

 

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

 

 

 

4. 다음 조건 명제의 진리값을 구하시오. 

1) 이탈리아의 수도가 뉴욕이라면 대한민국의 수도는 서울이다.

2) 지구가 평면이면 지구인은 모두 화성에 산다.

3) 1+3=4이면, 2x3=5이다.

4) 삼각형 내각의 합이 180도 라면, 포도는 과일이다. 

 

풀이: 

1) T: 조건이 거짓이므로 결론과 상관없이 참

2) T: 조건이 거짓이므로 결론과 상관없이 참

3) F: 조건은 참이지만, 결론이 거짓이므로 주어진 조건명제는 거짓

4) T: 조건과 결론이 모두 참이므로 주어진 조건 명제는 T 

 

 

 

 

5. 다음의 명제를 "만약 A라면 B이다"와 같은 조건 명제로 나타내시오. 

1) 키가 140cm 이상인 조건은 놀이기구를 타기 위한 충분조건이다. 

2) 3^2 >1 은 3>1이기 위한 필요조건이다. 

 

풀이: 

1) 만약 키가 140cm 이상이라면 놀이기구를 탈 수 있다.

2) 만약 3>1이면 3^2 >1 이다. 

 

 

 

6. 다음의 쌍조건명제는 참인가?

1) 사람이 살아 있다 <-> 사람이 호흡을 한다

2) 6X2 =8 <-> 4+5=20 

 

풀이:

1) T: 조건명제 p → q와 q → p 가 둘 다 참이므로 쌍조건명제는 참이다. 

2) T: 명제 p,q가 모두 거짓이므로 쌍조건명제는 참이다. 

 

 

 

7. 조건명제와 그 대우가 서로 논리적 동치관계임을 보이시오. 

풀이: 조건명제 p → q와 그 대우명제 ~q → ~p가 서로 논리적 동치관계임을 보이기 위해서는 모든 경우에 대해 두 명제의 진리값이 같음을 보이면 된다. 

p	q	p→q	~q	~p	~q→~p
T	T	T	F	F	T
T	F	F	T	F	F
F	T	T	F	T	T
F	F	T	T	T	T

 

진리표를 보면 명제 p와 q가 어떤 값을 같더라도 두 명제의 진리값은 항상 같다. 따라서 조건명제와 그의 대우는 서로 논리적 동치관계이다. 

 

 

8. 드 모르간 법칙을 이용하여 다음 식의 부정을 나타내시오. 

 

-5 < x < 2

 

풀이: 드 모르간 법칙을 적용하여 주어진 식 -5 < x < 2의 부정을 구하면, 이 식은 x가 -5보다 크고 2보다 작은 값을 가지는 구간을 의미한다. 이 구간의 부정은 x가 -5 이하 또는 2 이상인 경우이다. 따라서, 부정된 식은 x ≤ -5 또는 x ≥ 2이다. 

 

 

9. 논리적 동치법칙을 이용하여 ~ (p∨q) ∨ (~p∧q)를 간단히 하시오. 

풀이: 

~ (p∨q) ∨ (~p∧q)

≡ (~p ∧~q) ∨(~p∧q) 드 모르간 법칙 

≡~p∧(~q∨q) 분배법칙 

≡ ~p ∧T 부정법칙
≡ ~p 항등법칙

 

 

10. 진리표를 이용하여 명제 p ∨ ~(p∧q)가 항진명제임을 보이시오. 

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

 

 

 

12. 다음 명제들은 항진명제들이다. 

1) p → p

2) p ∨~p

3) p∧q → p∧q

 

13. 다음 명제들은 모순 명제들이다. 

1) p ∧~p

2) (p∧q) ∧ ~p 

3) (p⟷q)∧(p⊕q)

 

 

 

14. 명제함수 P(x,y)가 x^2 + y^2 = 2 일때, P(2,1)의 진리값을 구하시오. 

 

풀이: P(2,1) = 2^2 + 1^2 = 5이므로 거짓이다. 

 

 

15. 명제함수 P(x)가 "x는 정수이다"이고, x의 정의역이 음수일 경우 ∀xP(x)는 참이다. 

풀이: 음수는 정수에 포함되므로 모든 음수는 실수가 된다. 

 

16. P(x)가 "x는 유리수이다"이고 x의 정의역이 무리수일 경우 ∃xP(x)는 거짓이다.

풀이: "유리수=실수-무리수"이므로 무리수와 유리수는 서로 같은 값을 가지지 않는다. 따라서 어떠한 유리수도 무리수가 될 수 없다. 

 

 

17. x는 농장에서 수확되는 오렌지이고, 명제함수 P(x)는 "x는 외국으로 수출된다"라고 했을 때, "농장에서 수확되는 모든 오렌지는 외국으로 수출된다"를 부정으로 나타내보시오. 

 

풀이: "농장에서 수확되는 모든 오렌지는 외국으로 수출된다"를 명제함수로 나타내면, ∀xP(x)이다. 전체한정자가 포함된 명제함수의 부정은 ~∀xP(x) = ∃x~P(x)이다. 따라서, "농장에서 수확되는 오렌지 중에는 외국으로 수출되지 않는 오렌지도 존재한다."이다. 

 

 

 

18. 다음 명제에 대한 역, 이, 대우를 각각 작성하시오.

 

어떤 정수가 -보다 작으면 그 정수의 제곱은 16보다 크다.

 

풀이: 조건 명제의 역, 이, 대우를 구할 때 한정자는 부정되지 않는다는 점을 주의해야 한다. 

- 역: 어떤 정수의 제곱이 16보다 크면 그 정수는 -4보다 작다.

- 이: 어떤 정수가 -4보다 크거나 같으면 그 정수의 제곱은 16보다 작거나 같다.

- 대우: 어떤 정수의 제곱이 16보다 작거나 같으면 그 정수는 -4보다 크거나 같다. 

 

 

 

19. x, y가 정수일 때 다음 명제의 진리값을 구하시오. 

1) ∃x∀y(x+y=1)

2) ∀x∃y(x+y=1)

 

풀이: 명제 1의 경우, "어떤 x는 모든 y에 대해 x+y=1이다"를 의미한다. 이러한 x는 존재할 수 없으므로 거짓이다. 명제 2의 경우 "모든 x에 대해 x+y=1을 만족하는 어떤 y가 존재한다"를 의미한다. 모든 x에 대해 y=1-x로 두면 x+y=1이므로 참이다. 

 

 

 

20. 다음 추론이 유효한 추론인지 진리표를 이용하여 판별하시오. 

 

p→q

q

∴ p 

 

풀이: todo ->

 

 

 

진리표를 작성하면 다음과 같다. 

 

p(결론)	q(전제)	p→q(전제)
T	T	T
T	F	F
F	T	T
F	F	T

 

주어진 논증에서는 'q는 참이다'라는 전제가 추가된다. 진리표를 작성해 보면, p가 거짓이고 q가 참인 경우에도 전제는 모두 참이 되지만, 결론인 'p는 참이다'는 거짓이 된다. 따라서 이 추론은 유효하지 않다. 다른 선택지를 평가하는 데 이 추론의 무효함은 'q가 참일 때 p도 반드시 참이라는 보장이 없다'는 점에서 중요하다. 이러한 이유로, 결론 p가 거짓일 수 있음을 알 수 있다.

 

 

 

---

 

참고자료: 이산수학 | 손진곤 (지은이) 한국방송통신대학교출판문화원