본 게시글은 대학 전공수업을 들으며 노션에 정리한 내용을 블로그로 옮긴 것으로, 노션 웹을 통해 최적화된 형태로 읽으시길 권장드립니다.(➡️ 노션 링크)
2강 - 논리
명제
참과 거짓을 구별할 수 있는 문장이나 수학적 식
진리값(truth value) : 참(True, T) / 거짓(False, F)
예 :
✅ 6은 2의 배수다.
✅ 2 + 3 = 7
❌ x + 2 = 0 (참/거짓 판별 불가)
❌철수는 공부를 잘한다.
명제의 종류
합성명제
compound proposition,
하나 이상의 명제와 논리연산자가 결합되어 만들어진 명제
논리연산(logical operation)
참 거짓을 구별할 수 있는 명제를 대상으로 하는 연산
논리 연산자 : logical operator
: 논리연산의 기호
논리합(∨, or연산, disjunction)
연결된 명제중 하나 이상의 참이 있을경우 참,
모두 거짓일 경우 거짓.
‘또는’의 의미.
자바에서의 ||
p=T, q=F ⇒ p ∧ q = T
p: 3>1 / q: 4>8 이라고 할 때, p and q = ?
논리곱(∧, and연산, conjunction)
연결된 명제들이 모두 참일경우 참,
하나의 거짓이 있을 경우 거짓.
‘그리고’의 의미.
자바에서의 &&
p:홀수와 홀수를 더하면 짝수이다.
q:짝수와 홀수를 곱하면 짝수이다. p∧q = ?
p = T, q = T ⇒ p∧q = T
부정(~, not연산, negation)
따라오는 명제가 참일 경우 거짓,
거짓일경우 참이 됨.
*다른 연산자와 달리 1항 연산자
자바에서의 !
배타적 논리합(⨁ , xor연산, exclusive disjunction)
연결된 2개 명제 가운데, 1개만 참일 경우 참이되고,
나머지 경우에는 거짓.
자바에서의 ≠
p: 배트맨이 등장한다. q: 슈퍼맨이 등장한다.
⇒ p ⨁ q = 배트맨 또는 배트맨 중 한명만 등장할 때 참.
조건명제
conditional proposition, →
명제 𝒑 와 𝒒 가 있을 때, 명제 𝒑 가 조건의 역할을 수행하고 명제 𝒒 가 결론의 역할을 수행하는 경우
𝒑와 𝒒의 합성명제를 조건명제라고 하고 𝒑 → 𝒒라고 표시한다.
implication(함의)라고 부르기도 함.
𝒑 → 𝒒 ( 𝒑 ⇒ 𝒒)
- 𝑝는 𝑞의 충분조건
- 𝑞는 𝑝의 필요조건
ex) 1+2 = 3이면, 10-2 = 8이다.( T / T / T)
image source: https://math.libretexts.org/Bookshelves/Applied_Mathematics/Math_in_Society_(Lippman)/17%3A_Logic/17.06%3A_Section_6-
충분조건
p와 q가 명제일때, “if p, then q”형식으로 표현할 수 있으면 p가 항상 q가 일어나는 것을 보장한다 ⇒ p를 q의 충분조건
필요조건
p와 q가 명제일때, “if not p, then not q”형식으로 표현할 수 있으면 q가 일어나는데 필요하다 ⇒ p를 q의 충분조건
쌍조건 명제
biconditional proposition, ↔
명제 𝒑 와 𝒒 가 있을 때, 명제 𝒑 와 𝒒 가 조건의 역할과 결론의 역할을 동시에 수행하는 경우,
𝒑와 𝒒의 합성명제를 조건명제라고 하고 𝒑 ↔ 𝒒라고 표시한다.
A biconditional is written as 𝑝↔𝑞 and is translated as ′′ 𝑝 if and only if 𝑞’’.
논리적 동치 (logical equivalence, ≡)
두 명제 𝒑 와 𝒒 가 논리적으로 동등한 경우, 𝒑 ≡ 𝒒 로 표시한다.
( * ‘논리적으로 동등하다는 말’은 두 명제가 항상 동일한 진리값을 가진다는 뜻이다.)
- 𝒑 ↔ 𝒒 , 𝒑 ⇔ 𝒒, 𝒑 = 𝒒, 𝒑 ≡ 𝒒
- 논리적 동치는 위와 같이 표현하기도 함.
역, 이, 대우
조건명제 𝒑 → 𝒒에 대하여,
- *역 *(converse) : 𝒒 → 𝒑
- *이 *(inverse) : ~𝒑 → ~𝒒
- *대우 *(contrapositive) : ~𝒒 → ~𝒑
- ✅조건명제와 그의 대우는 진리값은 항상 같다(논리적 동치관계이다.)
논리적 동치 법칙
- 교환법칙 (commutation law)
- and/or연산, 쌍조건 명제는 위치를 교환해도 결과가 같다.
- 𝒑 ∨ 𝒒 ≡ 𝒒 ∨ 𝒑
- 𝒑 ∧ 𝒒 ≡ 𝒒 ∧ 𝒑
- 𝒑 ↔ 𝒒 ≡ 𝒒 ↔ 𝒑
- 결합법칙(associative law)
- and(∧)를 *로, or(∨)을 +로 실수와 같이 계산해볼 때 그 결과가 같음을 증명 가능하다.
- ( 𝒑 ∨ 𝒒 ) ∨ 𝒓 ≡ 𝒑 ∨ ( 𝒒 ∨𝒓 )
- ( 𝒑 ∧ 𝒒 ) ∧ 𝒓 ≡ 𝒑 ∧ ( 𝒒 ∧𝒓 )
- 분배법칙 (distributive law)
- 𝒑 ∨ ( 𝒒 ∧ 𝒓 ) ≡ ( 𝒑 ∨ 𝒒 ) ∧ ( 𝒑 ∨ 𝒓 )
- 실수 집합과 다르다!!
- p + (q * r) = (p + q) * (p + r)
- 𝒑 ∧ ( 𝒒 ∨ 𝒓 ) ≡ ( 𝒑 ∧ 𝒒 ) ∨ ( 𝒑 ∧ 𝒓 )
- 실수집합과 같다.
- p * (q + r) = (p * q) + (p * r)
- 항등법칙 (identity law)
- 𝒑 ∨ F ≡ 𝒑
- or연산에서, p가 T일 때, 𝒑 ∨ F는 T이고,
p가 F일때, 𝒑 ∨ F는 F이다.
- or연산에서, p가 T일 때, 𝒑 ∨ F는 T이고,
- 𝒑 ∧ T ≡ 𝒑
- and연산에서, p가 T일때 𝒑 ∧ T는 T이고,
- p가 F일때, 𝒑 ∧ F는 F이다.
- 지배법칙 (domination law)
- 𝒑 ∨ T ≡ T
- or연산에서, p값과 상관없이 T
- 𝒑 ∧ F ≡ F
- and연산에서, p값과 상관없이 F
- 부정법칙 (negation law)
- ~ T ≡ F
- ~ F ≡ T
- 𝒑 ∨ ( ~ 𝒑 ) ≡ T
- 𝒑 ∧ ( ~ 𝒑 ) ≡ F
- 이중 부정 법칙(double negation law)
- ~ (~ 𝒑 ) ≡ 𝒑
- 멱등법칙 (idempotent law)
- p끼리는 and하든 or하든 p다. ( 연산을 반복하여 적용 하더라도 결과값이 달라지지 않는다.)
- 𝒑 ∨ 𝒑 ≡ 𝒑
- 𝒑 ∧ 𝒑 ≡ 𝒑
- 드 모르간 법칙(de Morgan’s law)
- ~ ( 𝒑 ∨ 𝒒 ) ≡ (~ 𝒑 ) ∧ (~ 𝒒 )
- 집합론에선 ∁(A∪B)=∁A∩∁B
- ~ ( 𝒑 ∧ 𝒒 ) ≡ (~ 𝒑 ) ∨ (~ 𝒒 )
- ∁(A∩B)=∁A∪∁B
- *흡수법칙 *(absorption law)
- 𝒑 ∨ ( 𝒑 ∧ 𝒒 ) ≡ 𝒑
- 𝒑 ∧ ( 𝒑 ∨ 𝒒 ) ≡ 𝒑
- **함축법칙(implication law)**
- *𝒑 *→ 𝒒 ≡ ~ 𝒑 ∨ 𝒒
if p then q “ = either not p or q
오늘 비가 오면, 나는 우산을 가져간다 = 오늘 비가 오지 않는다 OR 우산을 가져간다. ⇒ 오늘 비가 오지 않거나 우산을 가져간다면, 비가 오는 경우 우산을 가져간 것과 같다.
- ****대우법칙
- *𝒑 *→ 𝒒 ≡ ~ 𝒒 → ~ 𝒑
드 모르간 법칙을 사용해 다음 식의 부정을 나타내시오.
[ −𝟐 < 𝒙 < 𝟑 ]
[풀이] −𝟐 < 𝒙 < 𝟑 ⇔ −𝟐 < 𝒙 ∧ 𝒙 < 𝟑
⇒ ~(−𝟐 < 𝒙 < 𝟑) ⇔ ~( −𝟐 < 𝒙 ∧ 𝒙 < 𝟑 )
⇔ ~ −𝟐 < 𝒙 ∨~ 𝒙 < 𝟑
⇔ (𝒙 ≤ −𝟐)∨(𝒙 ≥ 𝟑)항진명제 (tautology)
항상 참인 명제
모순명제(contradiction)
항상 거짓 명제
술어논리(predicate logic)
주어와 술어를 구분하여 참과 거짓을 판별.
명제가 “소크라테스는 사람이다” 라면, 술어논리로는 사람(소크라테스)로 표시한다.
명제논리로는 “사람은 죽는다”와 “소크라테스는 사람이다”를 결합하여 “소크라테스는 죽는다”라는 사실을 유도할 수 없는 문제점이 있지만, 술어논리로는 표현이 가능하다.
술어논리와 명제함수
논리의 구조를 살펴보면,
- 논리
- 명제논리(proposition)
- 명제 // 이전까지 배운 내용
- 술어논리(predicate) //서술어 논리
- 명제함수
- 명제논리(proposition)
명제함수
변수의 값에 의해 함수의 진리값이 결정되는 문장이나 식.
- 변수의 명세
- 변수의 값을 적시
- (예) 명제함수 𝒑 (𝒙, 𝒚) 가 𝒙^𝟐 + 𝒚^𝟐 = 𝟒 일 때 𝒑 𝟏, 𝟐 의 진리값은?
- 변수의 범위를 제시 (한정화: ∀, ∃)
한정화(quantification)
- 전체 한정자 (universal quantifier, ∀)∀ 𝒙 𝑷(𝒙) = ‘정의역의 모든 𝒙에 대해서 𝑷(𝒙)는 참’
- “given any", "for all", or "for any".
- : “모든” “임의의”를 의미
- 존재 한정자 (existential quantifier, ∃)∃𝒙𝑷(𝒙) = ‘정의역 어떤 x에 대해, 𝑷(𝒙)는 참’)
- "there exists", "there is at least one", or "for some”
- : “존재한다”를 의미
타당성 검사
- 벤 다이어그램 (Venn diagram)을 사용
- :한정자가 사용된 명제함수의 타당성을 직관적으로 검사
추론(inference)
: 참으로 알려진 명제를 기초로 하여 다른 명제를 유도해 내는 과정.
- 결론의 근거를 제공하는 알려진 명제를 전제(premise)라고 한다.
- 새로 유도된 명제는 결론(conclusion).
유효추론
유효추론은 전제를 참(T)이라고 가정하였을 때 결론이 항상 참(T)이 되는 추론
예 : ( 𝒑 → 𝒒 ) ∧ (𝒒 → 𝒓 )) → ( 𝒑 → 𝒓 )
𝒑 = 사람은 척추동물이다.
𝒒 = 사람이 등뼈를 가지고있다.
𝒓 = 목뼈와 허리뼈를 가진다.
: 사람이 척추동물이면, 사람은 등뼈를 가진다(( 𝒑 → 𝒒 ), 전제) or 사람이 등뼈를 가지고 있으면 목뼈와 허리뼈를 가진다.((𝒒 → 𝒓 ),전제)
= 사람은 목뼈와 허리뼈를 가진다. ( 𝒑 → 𝒓 ), 결론
