명제논리와 증명: 단계별 풀이가 있는 연습 문제

그림, 힌트, 자세한 풀이가 있는 무료 명제논리와 증명 연습 문제. 매번 새로운 값으로, 세 가지 난이도: 진리표, 동치와 증명 방법, 한정자와 논증.

무료 연습 문제쉬움
pqr(p → r) ↔ (r ∨ q)111?110?101?100?011?010?001?000?

진리표를 완성하시오(1 = 참, 0 = 거짓). (p → r) ↔ (r ∨ q)이(가) 참인 행은 몇 개(N)인가?

(p → r) ↔ (r ∨ q)

정확한 답: 정수, 반올림하지 않음.

다음 문제 →
명제논리와 증명 무료로 연습하기지금 명제논리와 증명 연습하기매일 무료 문제 5개. 카드 등록이 필요 없습니다.

연습 내용

  1. 쉬움진리표
  2. 보통동치와 증명 방법
  3. 어려움한정자와 논증

명제논리와 증명 문제 푸는 방법

  1. 서로 다른 변수의 개수를 세세요. 진리표는 2ⁿ개의 행을 가지며, 첫 행은 모두 1입니다.
  2. 모든 부분식에 각각 열을 하나씩 주고, 안쪽부터 바깥쪽으로 열을 채우세요.
  3. 각 연결자의 규칙을 적용하세요. →는 1 → 0일 때만 0이고, ↔는 양쪽이 같을 때 1입니다.
  4. 동치는 마지막 열을 행마다 비교하고, 논증은 모든 전제가 1인 행만 살펴보세요.
  5. 한정된 문장을 부정하려면 ¬를 안쪽으로 옮기고, ∀와 ∃를 서로 바꾸고, 안쪽 식을 부정하세요.

흔한 실수

  • p가 거짓일 때 p → q를 거짓으로 보는 것.
  • 행의 개수를 구할 때 반복되는 변수를 두 번 세는 것.
  • 대우 ¬q → ¬p를 역 q → p와 혼동하는 것.
  • ∀x P(x)의 부정을 ∃x ¬P(x) 대신 ∀x ¬P(x)로 쓰는 것.
  • ∧와 ∨를 바꾸지 않고 드모르간 법칙을 적용하는 것.

핵심 공식

진리표의 행 수
2ⁿ
함의
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
함의의 부정
¬(p → q) ≡ p ∧ ¬q
쌍조건
p ↔ q ≡ (p → q) ∧ (q → p)
드모르간 법칙
¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
분배법칙
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
한정자의 부정
¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
전건 긍정법, 후건 부정법
p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

명제논리와 증명 처음부터 배우기

1명제와 연결자

명제는 참이거나 거짓인 문장으로, 예를 들어 “7은 소수이다”가 있습니다. 명제는 p나 q 같은 문자로 쓰고, 참값은 1(참) 또는 0(거짓)으로 씁니다.

연결자는 작은 식으로 더 큰 식을 만듭니다.

  • ¬p(p가 아니다)는 값을 뒤집습니다.
  • p ∧ q(그리고)는 둘 다 1일 때만 1입니다.
  • p ∨ q(또는)는 둘 다 0일 때만 0입니다. 포괄적 또는이며 둘 다 참일 수 있습니다.
  • p → q(p이면 q이다)는 p = 1이고 q = 0일 때만 0입니다.
  • p ↔ q(p일 때 그리고 그때에만 q이다)는 p와 q의 값이 같을 때 1입니다.
pqp → q111100011001

함의는 많은 학생을 놀라게 합니다. p가 거짓이면 q가 무엇이든 p → q는 참입니다. “비가 오면 우산을 쓴다”라는 약속은 비 오는 날 우산 없이 나갔을 때만 깨집니다.

자가 점검 p = 0이고 q = 1이다. p → q의 값은 무엇인가?
  1. 0
  2. 1
  3. 문맥에 따라 다르다
  4. 정의되지 않는다

답: 1. 함의는 조건이 성립하는데 결론이 성립하지 않을 때(p = 1, q = 0)만 거짓입니다. p = 0이면 q가 무엇이든 참입니다.

2진리표

진리표는 변수들의 참값의 모든 조합을 나열합니다. 서로 다른 변수가 n개이면 2ⁿ개의 행이 있습니다. 변수 두 개는 4개, 세 개는 8개, 네 개는 16개입니다. 두 번 나오는 변수도 한 번만 셉니다.

안쪽부터 바깥쪽으로 작업하세요. 모든 부분식에 각각 열을 하나씩 주면, 새 열은 이미 있는 열에 연결자 하나만 적용하면 됩니다.

  1. 변수를 나열하고 2ⁿ개의 조합을 모두 쓰세요. 모두 1인 조합부터 시작합니다.
  2. 가장 안쪽 부분식부터 부분식마다 열을 추가하세요.
  3. 각 열을 그 열의 주 연결자의 규칙에 따라 채우세요.
  4. 마지막 열에서 답을 읽으세요. 1의 개수를 세거나 묻는 행을 찾습니다.
자가 점검 (p ∧ q) → (r ∨ p)의 진리표는 행이 몇 개인가?
  1. 16
  2. 4
  3. 6
  4. 8

답: 8. 이 식에는 서로 다른 변수 p, q, r이 세 개 있으므로 2³ = 8개의 행입니다. p는 두 번 나오지만 하나의 변수입니다. 16은 출현 네 번에 대한 2⁴입니다.

3풀이 예제

모든 단계를 따라가 보세요. 다음 단계를 열기 전에 미리 예측해 보세요.

풀이 예제

(p → q) ∧ ¬q는 진리표의 몇 개 행에서 참인가?

1

변수와 행

변수가 p와 q 두 개이므로 행은 4개입니다: (1, 1), (1, 0), (0, 1), (0, 0).

2

p → q 열

p = 1, q = 0인 행에서만 0입니다.

p → q: 1, 0, 1, 1
3

¬q 열

¬q: 0, 1, 0, 1
4

논리곱

두 열이 모두 1이어야 합니다. 이는 마지막 행, 곧 p = 0, q = 0에서만 일어납니다.

(p → q) ∧ ¬q: 0, 0, 0, 1
답

이 식은 p = 0, q = 0인 행, 곧 1개의 행에서 참입니다. 그래서 p → q와 ¬q를 함께 쓰면 ¬p가 나옵니다(후건 부정법).

4동치와 증명 방법

두 식은 진리표의 열이 같을 때 동치(≡)입니다. 항진명제는 모든 행에서 1이고, 모순은 모든 행에서 0이며, 우연명제는 둘 다 아닙니다.

가장 자주 쓰는 법칙:

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

이 법칙들이 증명 방법의 바탕입니다. p → q의 대우에 의한 증명은 동치인 ¬q → ¬p를 대신 증명합니다. 귀류법은 함의가 거짓이 될 수 있는 유일한 경우인 p ∧ ¬q를 가정하고 불가능한 결과를 이끌어 냅니다.

주의: 역 q → p와 이(裏) ¬p → ¬q는 p → q와 동치가 아닙니다.

자가 점검 ¬(p ∧ q)와 동치인 식은 무엇인가?
  1. p ∨ q
  2. ¬p ∧ q
  3. ¬p ∧ ¬q
  4. ¬p ∨ ¬q

답: ¬p ∨ ¬q. 드모르간 법칙에 따라 ∧는 ∨가 되고 두 부분이 모두 부정됩니다. ¬p ∧ ¬q는 p ∨ q의 부정으로 다른 명제입니다. p와 q 중 정확히 하나만 참일 때 ¬p ∧ ¬q는 거짓이지만 ¬(p ∧ q)는 참입니다.

5한정자와 타당한 논증

변수가 어떤 영역 위에 있을 때 ∀x P(x)는 “모든 x에 대해 P가 성립한다”를, ∃x P(x)는 “P가 성립하는 x가 적어도 하나 있다”를 뜻합니다. 부정하면 한정자가 바뀝니다.

¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)

부정을 한 단계씩 안쪽으로 옮기고, 안쪽에서는 명제 논리 법칙을 쓰세요. 예를 들어 ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x))입니다. “모든 P가 Q인 것은 아니다”는 “Q가 아닌 P가 있다”는 뜻입니다.

모든 전제가 1인 모든 행에서 결론이 1이면 논증이 타당합니다. 대표적인 타당한 형식은 전건 긍정법(p → q, p, 따라서 q), 후건 부정법(p → q, ¬q, 따라서 ¬p), 가언 삼단논법(p → q, q → r, 따라서 p → r)입니다.

모든 전제가 1이고 결론이 0인 행이 반례입니다. 후건 긍정(p → q, q, 따라서 p)은 타당하지 않습니다. p = 0, q = 1인 행이 반례입니다.

자가 점검 “모든 학생이 합격했다”, 곧 ∀x P(x)의 부정은 무엇인가?
  1. ∀x ¬P(x): 합격한 학생이 없다
  2. ∃x P(x): 합격한 학생이 있다
  3. ∃x ¬P(x): 합격하지 못한 학생이 있다
  4. 고정된 한 학생 x에 대한 ¬P(x)

답: ∃x ¬P(x): 합격하지 못한 학생이 있다. 불합격한 학생 한 명이면 “모든 학생이 합격했다”가 거짓이 되기에 충분합니다. “합격한 학생이 없다”는 부정보다 훨씬 강한 주장입니다.

6흔한 실수

  • p가 거짓일 때 p → q를 거짓으로 보는 것. p = 1이고 q = 0일 때만 거짓입니다.
  • 행의 개수를 구할 때 반복되는 변수를 두 번 세는 것.
  • 대우 ¬q → ¬p를 역 q → p나 이(裏) ¬p → ¬q와 혼동하는 것.
  • ∀x P(x)의 부정을 ∀x ¬P(x)로 쓰는 것: 한정자가 ∃로 바뀌어야 합니다.
  • ¬(p ∧ q)를 ¬p ∧ ¬q로 쓰는 것: 드모르간 법칙은 연결자도 바꿉니다.
자가 점검 “n²이 짝수이면 n도 짝수이다”의 대우는 어느 것인가?
  1. n²은 짝수이고 n은 홀수이다
  2. n²이 홀수이면 n도 홀수이다
  3. n이 짝수이면 n²도 짝수이다
  4. n이 홀수이면 n²도 홀수이다

답: n이 홀수이면 n²도 홀수이다. 두 부분을 바꾸고 둘 다 부정합니다: (n이 짝수가 아니다) → (n²이 짝수가 아니다). “n이 짝수이면 n²도 짝수이다”는 역이고, 마지막 보기는 귀류법에서 가정하는 것입니다.

7시험 문제의 유형

  • 쉬움: 진리표. 행의 수를 구하고, 식이 참인 행의 수를 세거나, 식이 참 또는 거짓이 되는 단 하나의 행을 클릭합니다.
  • 보통: 동치와 증명 방법. 식이 항진명제, 모순, 우연명제 중 무엇인지 판단하고, 동치인 식을 고르거나, 대우법이나 귀류법으로 증명할 문장을 고릅니다.
  • 어려움: 한정자와 논증. 한정된 문장을 부정하고, 전제로부터 따라 나오는 결론을 고르고, 타당하지 않은 논증의 반례 행을 클릭하고, 변수 네 개짜리 표에서 참인 행을 셉니다.

앱에서 단계별로 배우기앱에서 단계별로 배우기

예제 풀이

예제 1쉬움
pq¬(p ∨ q) → q11100100

진리표에서 ¬(p ∨ q) → q이(가) 거짓이 되는 행은 정확히 하나입니다. 그 행을 클릭하세요.

¬(p ∨ q) → q
  1. 1p = 1, q = 1
  2. 2p = 1, q = 0
  3. 3p = 0, q = 1
  4. 4p = 0, q = 0
힌트 보기
  1. a → b는 a = 1이고 b = 0일 때만 0입니다. ¬a는 값을 뒤집습니다. a ∨ b는 둘 다 0일 때만 0입니다.
  2. 주 연결자를 먼저 따져 보세요. 전체 식이 0이(가) 되려면 양쪽이 무엇이어야 할까요?
  3. 각 부분에 열을 하나씩 주세요: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
정답과 설명 보기

진리표: 서로 다른 변수가 n개인 식은 참값(1 = 참, 0 = 거짓)의 모든 조합마다 하나씩 2ⁿ개의 행을 가집니다. 안쪽부터 바깥쪽으로 작업하고 모든 부분식에 각각 열을 주세요. ¬a는 값을 뒤집습니다. a ∧ b는 둘 다 1일 때만 1입니다. a ∨ b는 둘 다 0일 때만 0입니다. a → b는 a = 1이고 b = 0일 때만 0입니다. a ↔ b는 양쪽이 같을 때 1입니다.

행별 진리표

p = 1, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 1, q = 0: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 0: p ∨ q = 0, ¬(p ∨ q) = 1, ¬(p ∨ q) → q = 0

행

p = 0, q = 0 → ¬(p ∨ q) → q = 0

답

p = 0, q = 0
예제 2보통
(b → a) ∧ (c → a)b → (c → a)b ∧ (c → a)(b → c) → a

(b ∧ c) → a와(과) 논리적으로 동치인 식은 어느 것인가? 클릭하세요.

(b ∧ c) → a
  1. 1(b → a) ∧ (c → a)
  2. 2b → (c → a)
  3. 3b ∧ (c → a)
  4. 4(b → c) → a
힌트 보기
  1. 동치인 식은 진리표의 모든 행에서 값이 같습니다. 값이 다른 행이 하나라도 있으면 그 보기는 제외됩니다.
  2. (b ∧ c) → a이(가) 0이 되는 행을 하나 골라 어느 보기도 그 행에서 0인지 확인하세요.
  3. 수출 법칙: (a ∧ b) → c ≡ a → (b → c). 둘 다 a = 1, b = 1, c = 0일 때만 0입니다.
정답과 설명 보기

논리적 동치: 두 식은 진리표의 모든 행에서 값이 같으면 동치(≡)입니다. 항진명제는 모든 행에서 1이고, 모순은 모든 행에서 0이며, 우연명제는 둘 다 아닙니다. 유용한 법칙: 드모르간 법칙 ¬(a ∧ b) ≡ ¬a ∨ ¬b와 ¬(a ∨ b) ≡ ¬a ∧ ¬b, a → b ≡ ¬a ∨ b ≡ ¬b → ¬a(대우), ¬(a → b) ≡ a ∧ ¬b, 그리고 분배법칙 a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

법칙

수출 법칙: (a ∧ b) → c ≡ a → (b → c). 둘 다 a = 1, b = 1, c = 0일 때만 0입니다.
(b ∧ c) → a ≡ b → (c → a)

진리표로 확인

a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0

답

b → (c → a)

막대 뒤의 열은 보기를 표시된 순서대로 나타낸 것입니다.

예제 3어려움
pp ∧ ¬r¬pr

전제 (q ∧ p) → r; q; ¬r이(가) 주어져 있다. 이로부터 따라 나오는 결론은 어느 것인가? 클릭하세요.

(q ∧ p) → rq¬r
  1. 1p
  2. 2p ∧ ¬r
  3. 3¬p
  4. 4r
힌트 보기
  1. 모든 전제가 1인 모든 행에서 결론이 1이면 그 결론이 따라 나옵니다.
  2. 모든 전제를 1로 만드는 행을 찾은 다음, 그 행들에서 각 보기를 검사하세요.
  3. 이것은 표준 규칙입니다: 논리곱이 있는 후건 부정법.
정답과 설명 보기

한정자와 논증: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x). 부정을 안쪽으로 옮기고, 지나가는 모든 한정자를 바꾸고, ¬(a → b) ≡ a ∧ ¬b 같은 명제 논리 법칙으로 안쪽 식을 부정하세요. 모든 전제가 1인 모든 행에서 결론이 1이면 논증이 타당합니다. 전제는 참인데 결론이 거짓인 행이 하나라도 있으면 그것이 반례이며 그 논증은 타당하지 않음을 보여 줍니다.

모든 전제가 참인 행

p = 0, q = 1, r = 0: p = 0, p ∧ ¬r = 0, ¬p = 1, r = 0

결론

¬p (논리곱이 있는 후건 부정법)

답

¬p

질문과 답변

명제논리와 증명: 무엇인가요?

연결자는 작은 식으로 더 큰 식을 만듭니다.

함의는 많은 학생을 놀라게 합니다. p가 거짓이면 q가 무엇이든 p → q는 참입니다. “비가 오면 우산을 쓴다”라는 약속은 비 오는 날 우산 없이 나갔을 때만 깨집니다.

명제논리와 증명 문제는 어떻게 단계별로 푸나요?
  1. 서로 다른 변수의 개수를 세세요. 진리표는 2ⁿ개의 행을 가지며, 첫 행은 모두 1입니다.
  2. 모든 부분식에 각각 열을 하나씩 주고, 안쪽부터 바깥쪽으로 열을 채우세요.
  3. 각 연결자의 규칙을 적용하세요. →는 1 → 0일 때만 0이고, ↔는 양쪽이 같을 때 1입니다.
  4. 동치는 마지막 열을 행마다 비교하고, 논증은 모든 전제가 1인 행만 살펴보세요.
  5. 한정된 문장을 부정하려면 ¬를 안쪽으로 옮기고, ∀와 ∃를 서로 바꾸고, 안쪽 식을 부정하세요.
명제논리와 증명에서 자주 하는 실수는?
  • p가 거짓일 때 p → q를 거짓으로 보는 것.
  • 행의 개수를 구할 때 반복되는 변수를 두 번 세는 것.
  • 대우 ¬q → ¬p를 역 q → p와 혼동하는 것.
  • ∀x P(x)의 부정을 ∃x ¬P(x) 대신 ∀x ¬P(x)로 쓰는 것.
  • ∧와 ∨를 바꾸지 않고 드모르간 법칙을 적용하는 것.
명제논리와 증명 연습에서는 무엇을 다루나요?
  • 쉬움: 진리표
  • 보통: 동치와 증명 방법
  • 어려움: 한정자와 논증

문제마다 값이 새로 바뀌므로 답이 아니라 푸는 방법을 익히게 됩니다. 막혔나요? 먼저 작은 힌트를 열고, 필요할 때만 전체 해설을 보세요.

연습 방법

  • 문제마다 값이 새로 바뀌므로 답이 아니라 푸는 방법을 익히게 됩니다.
  • 막혔나요? 먼저 작은 힌트를 열고, 필요할 때만 전체 해설을 보세요.
  • 진행 상황, 틀린 문제, 저장한 문제가 보관되므로 시험 전에 복습할 수 있습니다.

이 주제의 앞뒤 주제

다음 단계

집합, 관계, 함수

이 주제가 포함된 강의

컴퓨터과학 기초이산수학

수학과 통계의 다른 주제

극한도함수최적화적분수열과 급수다변수 미적분미분방정식복소수수치해석행렬과 행렬식벡터: 내적과 외적집합, 관계, 함수그래프 이론정수론과 모듈러 연산확률기술통계정규분포신뢰구간가설 검정과 신뢰구간선형 회귀와 상관카이제곱 검정

인쇄용 학습지

정답이 있는 명제논리와 증명 학습지
명제논리와 증명 무료로 연습하기지금 명제논리와 증명 연습하기매일 무료 문제 5개. 카드 등록이 필요 없습니다.