기본 개념
- 수학적 논리를 통해 명제의 개념을 파악한다.
- 명제의 참과 거짓을 판별한다
명제 : 참 또는 거짓을 명확히 구분할 수 있는 문장이나 수식
진리값 : 명제에서 참 또는 거짓으로 나타내는 값
논리연산자와 진리표
- 다양한 논리연산자를 익힌다.
- 진리표를 통해 명제의 진리값을 구한다.
부정 : 문장 p가 명제일 때 not p도 명제다. 이를 명제 p의 Negation이라고 하며, ¬p또는 ~p로 나타낸다.
논리곱 : 문장 p와 q가 명제일 때 p and q도 명제다. p∧q로 나타낸다.
논리합 : 문장 p와 q가 명제일 때 p or q도 명제다. p∨q로 나타낸다.
XOR : 문장 p와 q가 명제일 때 p XOR q도 명제다. p⊕q로 나타낸다.
함축 : 문장 p와 q가 명제일 때 p implies q도 명제다. p→q로 나타낸다. ( ¬p∨q )
충분조건 / 필요조건 : 명제의 함축 p→q에서 p가 참이면 반드시 q도 참인 경우 p⇒q로 나타내고, ‘p는 q의 충분조건’, ‘q는 p의 필요조건’이라고 한다.
쌍조건문 : 문장 p와 q가 명제일 때 p if and only if q도 명제다. p↔q로 나타낸다.
필요충분조건 : p⇒q인 동시에 q⇒p인 경우를 ‘p는 q에 대한 필요충분조건’, ‘q는 p에 대한 필요충분조건’이라고 하며, p⇔q 또는 q⇔p로 나타낸다.
역 / 이 / 대우 : 명제 p, q에 대하여 p→q 일 때, q→p를 명제의 역, ¬p→¬q를 명제의 이, ¬q→¬p를 명제의 대우라고 한다.
논리적 동치
- 논리적 동치법칙을 익힌다.
- 논리적 동치를 이용하여 명제를 단순화한다.
항진명제 tautology : 합성명제를 구성하고 있는 명제가 어떠한 진리값을 갖든지 합성명제의 진리값이 항상 참이면 이를 항진명제라고 함.
모순명제 contradiction: 합성명제가 항상 거짓인 진리값을 가지면 모순명제라고 함.
논리적 동치 logical equivalence : 합성명제가 서로 같은 진리값을 갖는 경우. p ≡ q로 나타낸다.
|
p∧p≡pp∨p≡p
|
멱등법칙
|
|
p∧T≡pp∨F≡p
|
항등법칙
|
|
p∨T≡Tp∧F≡F
|
지배법칙
|
|
p∨¬p≡Tp∧¬p≡F
|
부정법칙
|
|
p∧q≡q∧pp∨q≡q∨p
|
교환법칙
|
|
p∨(q∨r)≡(p∨q)∨r p∧(q∧r)≡(p∧q)∧r
|
결합법칙
|
|
p∨(q∧r)≡(p∨q)∧(p∨r) p∧(q∨r)≡(p∧q)∨(p∧r)
|
분배법칙
|
|
¬(p∧q)≡¬p∨¬q ¬(p∨q)≡¬p∧¬q
|
드모르간 법칙
|
|
p→q≡¬p∨q
|
함축법칙
|
|
p→q≡¬q→¬p
|
대우법칙
|
|
p→q≡(p∧¬q)→F
|
귀류법칙
|
한정기호
- 논의 영역을 통해 명제함수의 참과 거짓을 판별한다.
명제함수 : 변수 x를 포함한 문장 P(x)와 논리영역 D가 있을 때 변수 x의 값이 D에 포함되면 문장 P(x)를 변수 x에 대한 명제함수라고 함.
전칭기호 : P(x)를 논의 영역 D를 갖는 명제함수라고 하자. 이때 ‘D에 속하는 모든 x에 대하여 P(x)는 참이다’라는 문장은 기호 ∀를 사용하여 ∀xP(x)로 나타낸다. 여기서 ∀를 P(x)의 전칭기호라고 한다.
존재기호 : P(x)를 논의 영역 D를 갖는 명제함수라고 하자. 이때 ‘D에 속하는 어떤 x에 대하여 P(x)가 참인 x가 존재한다’라는 문장은 기호 ∃를 사용하여 ∃xP(x)로 나타낸다. 여기서 ∃를 P(x)의 존재기호라고 한다.