이산수학 요점정리 (1/5)

Propositional (명제)

1. Statements (Propositions) / 명제

• Propositions (명제) : 참이나 거짓으로 판단할 수 있는 문장. 단, 둘 다 일수는 없다.
• Propositional Logic (명제 논리) : 명제를 다룬다.
• Propositional Constants (명제 상수) : T - 참, F - 거짓
• Propositional Variables (명제 변수) : T나 F값을 가질 수 있는 변수
• Atomic Propositions (원자 명제) : 명제 상수, 명제 변수, 명제는 더 세분화 될 수 없다.
• Compound Propositions (합성 명제) : 원자 명제가 아닌 것을, 논리연산자로 연결한 것.

 

2. Basic logical connectives: AND, OR, NOT / 기본 논리 연산자

Connective	pronounced	Symbol in Logic
Negation	NOT	¬, ~
Conjunction	AND	∧
Disjunction	OR	∨
Conditional	if then	→
Biconditional	if and only if	↔
Exclusive or	either…or but not both	⊕

 

3. Translating from English to symbols / 영어를 심볼로 번역하기

English	Logic	Example
And, but	AND Λ	It is hot and sunny 덥고 화창하다. A: It is hot B: It is sunny A Λ B
Not	NOT ¬	It is not hot:    ¬ A 덥지 않다
Or (inclusive)	OR V	It is hot or sunny 덥거나 화창하다 A V B
Or (exclusive)	A or B but not both	It is either hot or sunny 덥거나 화창하다. (XOR이네, 덥고 화창하면 거짓) (A V B) Λ ¬ (A Λ B)
Neither… nor	¬ A Λ ¬ B	It is neither hot nor sunny 덥지도 않고 화창하지도 않다. ¬ A Λ ¬ B

 

4. Truth tables / 진리표

• Truth tables (진리표) : 논리적 연결 요소의 의미, 합성 문장의 평가를 진리값으로 정의한 표.

p	q	~p	p∧q	p∨q	p⊕q	p→q	p↔q
T	T	F	T	T	F	T	T
T	F	F	F	T	T	F	F
F	T	T	F	T	T	T	F
F	F	T	F	F	F	T	T

 

5. Logical equivalence / 논리적 동치

• 2 개의 명제식 p와 q는 진리표가 다음과 같은 경우 논리적으로 동일하다.

Commutative laws	P V Q ≡ Q V P P Λ Q ≡ Q Λ P
Associative laws	(P V Q) V R ≡ P V (Q V R) (P Λ Q) Λ R ≡ P Λ (Q Λ R)
Distributive laws:	(P V Q) Λ (P V R) ≡ P V (Q Λ R) (P Λ Q) V (P Λ R) ≡ P Λ (Q V R)
Identity	P V F ≡ P, P Λ T ≡ P
Negation	P V ~P ≡ T (excluded middle) P Λ ~P ≡ F (contradiction)
Double negation	~(~P) ≡ P
Idempotent laws	P V P ≡ P P Λ P ≡ P
De Morgan's Laws	~(P V Q) ≡ ~P Λ ~Q ~(P Λ Q) ≡ ~P V ~Q
Universal bound laws (Domination)	P V T ≡ T P Λ F ≡ F
Absorption Laws	P V (P Λ Q) ≡ P P Λ (P V Q) ≡ P
Negation of T and F	~T ≡ F, ~F ≡ T

 

6. Tautologies and contradictions / 동어반복과 모순

• 명제식 P V ¬ P 는 동어반복. 모든 가능한 P에 대하여 T
• 명제식 P Λ ¬ P 는 모순. 모든 가능한 P에 대하여 F

 

7. Implication P → Q / 함축

• P = T 및 Q = F 인 경우에만 거짓.
• P 및 Q의 다른 모든 값에 대해 참.

 

8. Syllogisms / 삼단논법

8-1. Modus Ponens and Modus Tollens / 긍정식과 부정식

Modus ponens (긍정식)

(1) P이면 Q
(2) P
(3) 그러므로 Q

Modus Tollens (부정식)

(1) P이면 Q
(2) ~ Q
(3) 따라서 ~ P

8-2. Disjunctive syllogism / 선언적 삼단논법

(1) P V Q
(2) ~P
(3) 따라서 ~ Q

8-3. Hypothetical syllogism / 가언적 삼단논법

(1) P → Q
(2) Q → R 

(3) 따라서 P → R

 

나머지는 (2/5)에서...