Total
Search
1. 명제
1.1. 명제의 정의
•
명제(Proposition)
◦
참과 거짓을 구별할 수 있는 문장이나 수학적 식
•
진리값
◦
참(True, T)
◦
거짓(False, F)
1.2. 명제의 종류
•
합성명제 (Compound Proposition): 하나 이상의 명제와 논리연산자(∨, ∧ 등)를 포함
•
조건명제 (Conditional Proposition): "𝑝 → 𝑞" 형태로 나타내며, 𝑝가 참이면 𝑞도 참
•
쌍조건명제 (Bi-Conditional Proposition): "𝑝 
𝑞" 형태로 나타내며, 𝑝와 𝑞가 같은 진리값을 가질 때 참
𝑞" 형태로 나타내며, 𝑝와 𝑞가 같은 진리값을 가질 때 참•
항진명제 (Tautology): 항상 참인 명제
•
모순명제 (Contradiction): 항상 거짓인 명제
1.3. 예시
1.3.1. 명제
•
"6은 2의 배수다" → 명제 (참).
•
"철수는 공부를 잘 한다" → 명제가 아님 (평가 기준에 따라 다름).
•
"2 + 3 = 7" → 명제 (거짓).
•
"𝑥 + 2 = 0" → 명제가 아님 (𝑥 값에 따라 달라짐).
1.3.2. 명제의 진리값
•
"2, 3, 6는 소수이다" → 명제 (거짓).
◦
6은 소수가 아니기 때문에 명제 전체가 거짓
•
"소수의 개수는 무한하다" → 명제 (참)
•
"126 = 2⁶" → 명제 (거짓)
◦
2⁶ = 64로, 126과 같지 않음
•
"지구에서 가장 높은 산은 에베레스트이다" → 명제 (참)
2. 논리연산
2.1. 논리연산자
•
논리연산은 명제를 조합하여 새로운 명제를 만드는 연산
•
연산자 종류
◦
논리합 / 논리곱 / 부정 / 배타적 논리합
•
합성 명제
◦
하나 이상의 명제와 논리연산자 그리고 괄호로 이루어진 명제
2.1.1. 논리합 (∨)
•
𝑝 ∨ 𝑞
•
의미: "또는 (OR)" 연산으로, 두 명제 중 하나라도 참이면 결과가 참
•
진리표
𝑝 | 𝑞 | 𝑝 ∨ 𝑞 |
T | T | T |
T | F | T |
F | T | T |
F | F | F |
2.1.2. 논리곱 (∧)
•
𝑝 ∧ 𝑞
•
의미: "그리고 (AND)" 연산으로, 두 명제가 모두 참일 때 결과가 참
•
진리표
𝑝 | 𝑞 | 𝑝 ∧ 𝑞 |
T | T | T |
T | F | F |
F | T | F |
F | F | F |
2.1.3. 부정 (~)
•
의미: 명제의 진리값을 반대로 만듦
•
예: "~𝑝"은 명제 𝑝가 참이면 거짓, 거짓이면 참
•
진리표
𝑝 | ~𝑝 |
T | F |
F | T |
2.1.4. 배타적 논리합 (xor, ⊕)
•
𝑝 ⊕ 𝑞
•
의미: 두 명제가 서로 다를 때만 참
•
예: "오늘은 비가 온다 ⊕ 바람이 분다"는 두 명제의 진리값이 다를 때 참
•
진리표
𝑝 | 𝑞 | 𝑝 ⊕ 𝑞 |
T | T | F |
T | F | T |
F | T | T |
F | F | F |
예시 문제: 합성명제 (𝑝 ∧ 𝑞) ∨ (𝑝 ⊕ 𝑞) 진리표를 작성하라
𝑝 | 𝑞 | 𝑝 ∧ 𝑞 | 𝑝 ⊕ 𝑞 | (𝑝 ∧ 𝑞) ∨ (𝑝 ⊕ 𝑞) |
T | T | T | F | T |
T | F | F | T | T |
F | T | F | T | T |
F | F | F | F | F |
2.2. 조건 명제
2.2.1. 조건 명제 정의
•
"𝑝 → 𝑞"로 표시되며, 이는 "𝑝라면 𝑞이다"라는 의미
•
구성 요소
◦
𝑝: 조건 (Antecedent, 선행 조건)
◦
𝑞: 결과 (Consequent, 후행 조건)
•
𝑝 는 𝑞의 충분조건 → 𝑝가 참이면 반드시 𝑞도 참
•
𝑞 는 𝑝의 필요조건 → 𝑞가 거짓이면 반드시 𝑝도 거짓
2.2.2. 조건 명제의 진리표
•
조건 𝑝가 거짓인 경우, 결과와 상관없이 전체 조건 명제가 참이 됨
•
조건 𝑝가 참이고 결과 𝑞가 거짓인 경우, 조건 명제가 거짓이 됨
𝑝 | 𝑞 | 𝑝 → 𝑞 |
T | T | T |
T | F | F |
F | T | T |
F | F | T |
2.2.3. 예제
•
명제: "1 + 2 = 3이면 10 - 2 = 8이다"
◦
𝑝: "1 + 2 = 3" (참)
◦
𝑞: "10 - 2 = 8" (참)
◦
결과: 조건 명제 "𝑝 → 𝑞"는 참
•
명제: "1 + 2 = 3이면 10 - 2 = 7이다"
◦
𝑝: "1 + 2 = 3" (참)
◦
𝑞: "10 - 2 = 7" (거짓)
◦
결과: 조건 명제 "𝑝 → 𝑞"는 거짓
2.2.4. 쌍조건 명제
•
정의: "𝑝 𝑞"로 표시되며, "𝑝라면 𝑞이고, 𝑞라면 𝑝이다"를 의미
𝑞"로 표시되며, "𝑝라면 𝑞이고, 𝑞라면 𝑝이다"를 의미•
진리표
𝑝 | 𝑞 | 𝑝 𝑞 |
T | T | T |
T | F | F |
F | T | F |
F | F | T |
•
예제
1.
명제 1: 사람이 살아 있다 사람이 호흡을 한다
사람이 호흡을 한다•
𝑝: "사람이 살아 있다" → 참 (T)
•
𝑞: "사람이 호흡을 한다" → 참 (T)
•
결과: 𝑝 𝑞 = 참 (T)
𝑞 = 참 (T)•
이유: 두 명제가 모두 참이므로, 쌍조건명제는 참
2.
명제 2: 1+2=9 1×2=9
1×2=9•
𝑝: 1+2=9 → 거짓 (F)
•
𝑞: 1×2=9 → 거짓 (F)
•
결과: 𝑝 𝑞 = 참 (T)
𝑞 = 참 (T)•
이유: 두 명제가 모두 거짓이므로, 쌍조건명제는 참
2.3 동치
2.3.1. 논리적 동치의 정의
•
논리적 동치 (Logical Equivalence)
◦
두 명제 𝑝와 𝑞가 항상 동일한 진리값을 가지면, 두 명제는 논리적으로 동치라 하며, "𝑝 ≡ 𝑞"로 표시
◦
논리적으로 동등하다는 말은, 두 명제가 항상 동일한 진리 값을 가진다는 의미
•
역 / 이 / 대우
◦
역 (Converse): "𝑞 → 𝑝"
◦
이 (Inverse): "~𝑝 → ~𝑞"
◦
대우 (Contrapositive): "~𝑞 → ~𝑝"
2.3.2. 동치의 주요 특징
1.
논리적 동치는 진리표를 통해 검증 가능
2.
동치 명제는 서로 대체 가능하며, 논리적 증명에서 자주 사용됨
3.
논리적 동치는 항상 참인 명제(항진명제)로 표현될 수 있음
2.3.3. 동치의 응용
1.
조건 명제의 동치 변환
•
𝑝 → 𝑞 ≡ 𝑝∨𝑞
◦
조건 명제를 "부정과 논리합"으로 표현 가능
•
예: "비가 오면 땅이 젖는다" → "비가 오지 않거나 땅이 젖는다"
2.
대우의 동치
•
𝑝 → 𝑞 ≡ ~𝑞→ ~𝑝
◦
조건 명제는 항상 그 대우와 동치임
•
예: "비가 오면 땅이 젖는다" "땅이 젖지 않으면 비가 오지 않는다"
"땅이 젖지 않으면 비가 오지 않는다"2.3.4. 논리적 동치 법칙
1.
교환법칙 (Commutation Law)
•
𝑝 ∨ 𝑞 ≡ 𝑞 ∨ 𝑝
•
𝑝 ∧ 𝑞 ≡𝑞 ∧ 𝑝
•
예: "A 또는 B" "B 또는 A"
"B 또는 A"2.
결합법칙 (Associative Law)
•
(𝑝∨𝑞)∨𝑟 ≡ 𝑝∨(𝑞∨𝑟)
•
(𝑝∧𝑞)∧𝑟 ≡ 𝑝∧(𝑞∧𝑟)
3.
분배법칙 (Distributive Law)
•
𝑝∨(𝑞∧𝑟) ≡ (𝑝∨𝑞)∧(𝑝∨𝑟)
•
𝑝∧(𝑞∨𝑟) ≡ (𝑝∧𝑞)∨(𝑝∧𝑟)
4.
항등법칙 (Identity Law)
•
𝑝∨F ≡ 𝑝
•
𝑝∧T ≡ 𝑝
5.
지배법칙 (Domination Law)
•
𝑝∨T ≡ T
•
𝑝∧F ≡ F
6.
부정법칙 (Negation Law)
•
𝑝∨(~𝑝) ≡ T
•
𝑝∧(~𝑝) ≡ F
7.
이중부정법칙 (Double Negation Law)
•
~(~ 𝑝) ≡ 𝑝
8.
멱등법칙 (Idempotent Law)
•
𝑝∨𝑝 ≡ 𝑝
•
𝑝∧𝑝 ≡ 𝑝
9.
드 모르간 법칙 (De Morgan’s Law)
•
~(𝑝∨𝑞) ≡ (~𝑝)∧ (~𝑞)
•
~(𝑝∧𝑞) ≡ (~𝑝)∨ (~𝑞)
10.
흡수법칙 (Absorption Law)
•
𝑝∨(𝑝∧𝑞) ≡ 𝑝
•
𝑝∧(𝑝∨𝑞) ≡ 𝑝
11.
함축법칙 (Implication Law)
•
𝑝→𝑞 ≡ ~𝑝∨𝑞
12.
대우법칙 (Contrapositive Law)
•
𝑝→𝑞 ≡ ~𝑞 → ~𝑝
2.3.5. 예제: 드 모르간 법칙을 사용한 명제의 부정
•
다음 식의 부정을 드 모르간 법칙을 사용하여 나타내시오
◦
식: -2 < 𝑥 < 3
•
풀이
1.
원래 명제의 의미
•
−2 < 𝑥 ∧ 𝑥 < 3
2.
명제의 부정
•
~(−2 < 𝑥 ∧ 𝑥 < 3)
3.
드 모르간 법칙 적용
•
∼(𝑝∧𝑞) ≡ (∼𝑝∨∼𝑞)
•
이를 적용하면
◦
~(−2 < 𝑥 ∧ 𝑥 < 3) ≡ (∼(−2 < x)∨∼( x < 3))
4.
부정 연산 계산
•
∼(−2 < x) → −2 ≤ x
•
∼( x < 3) → x ≥ 3
◦
따라서 부정된 식은
▪
𝑥 ≤−2∨𝑥 ≥ 3
2.3.6. 항진명제와 모순명제
•
항진명제 (Tautology)
◦
정의: 항상 참(True)인 명제
◦
합성명제를 구성하는 개별 명제의 진리값과 관계없이 항상 참인 명제를 의미
◦
예: 𝑝 ∨∼𝑝
▪
진리표에서 모든 경우에 참으로 나타남
•
모순명제 (Contradiction)
◦
정의: 항상 거짓(False)인 명제
◦
합성명제를 구성하는 개별 명제의 진리값과 관계없이 항상 거짓인 명제를 의미
◦
예: 𝑝∧∼𝑝
▪
진리표에서 모든 경우에 거짓으로 나타남
3. 술어논리
3.1. 술어논리의 정의
•
술어논리 (Predicate Logic)
◦
명제논리의 확장으로, 변수와 술어를 사용하여 명제를 표현하는 논리 체계
•
명제논리와의 차이점
◦
명제논리는 참(True) 또는 거짓(False)으로 평가되는 완전한 문장을 다룸
◦
술어논리는 변수와 이를 포함한 논리적 관계를 포함하며, 변수의 값에 따라 명제가 참 또는 거짓으로 평가
3.2. 술어논리와 명제 함수
3.2.1. 명제함수
•
변수의 값에 따라 진리값이 결정되는 문장이나 식
•
변수의 값을 명시적으로 지정
•
변수의 범위 제시 (한정화)
3.2.2. 전체한정자(∀)
•
"모든" 또는 "임의의"를 의미
•
명제 함수 ∀𝑥𝑃(𝑥)와 같이 사용된 경우, 정의역의 모든[임의의] x에 대하여 𝑃(𝑥)가 참(T)임을 의미
•
예시)
◦
𝑃(𝑥)가 𝑥는 실수이고 𝑥의 정의역이 양수인 경우 ∀𝑥𝑃(𝑥)는 참이다.
◦
𝑃(𝑥)가 𝑥^2 + 𝑥 - 2 > 0이고, 𝑥의 정의역이 실수인 경우 ∀𝑥𝑃(𝑥)는 거짓이다.
▪
-2와 1 사이의 값이 들어가면 음수가 됨
3.2.3. 존재한정자 (∃)
•
"존재한다"를 의미
•
명제 함수 ∃𝑥𝑃(𝑥)와 같이 사용된 경우, 정의역의 어떤 x에 대하여 𝑃(𝑥)가 참(T)임을 의미
•
예시)
◦
𝑃(𝑥)가 𝑥는 무리수이고 𝑥의 정의역이 유리수인 경우 ∃𝑥𝑃(𝑥)는 거짓이다.
3.3. 타당성 검사
•
명제함수에 사용된 한정자(전체한정자, 존재한정자)에 따라 명제의 참/거짓 여부를 직관적으로 판단하거나 증명하는 과정
•
벤 다이어그램을 사용한 직관적 분석:
◦
정의역과 술어의 관계를 시각적으로 표현하여 판단
◦
예: "모든 평행사변형은 사각형이다"를 평행사변형 집합이 사각형 집합에 포함된 관계로 표현
•
예제: 삼단논법을 활용한 타당성 검사
◦
전제: "영희는 서울에 있다", "서울은 한국에 있다"
◦
결론: "영희는 한국에 있다"
◦
타당성 검사: 전제가 참인 경우, 결론도 참이므로 논증이 타당
3.4 추론
•
참으로 알려진 명제를 기초로 새로운 명제를 도출하는 과정
•
구성 요소
◦
전제 (Premise): 결론의 근거가 되는 명제
◦
결론 (Conclusion): 전제를 기반으로 도출된 명제
•
유효 추론
◦
전제가 참이라고 가정했을 때 결론이 항상 참이 되는 추론
◦
삼단 논법
•
추론 규칙
◦
논리적 동치(항진명제)를 이용함