[Discrete Mathematics] 명제(proposition)와 논리 연산

---

명제 (Proposition)

 

참인지 거짓인지 알 수 있는 문장

특정 명제를 $ p, q, r $ 등으로 나타냄

$ p: 1 + 1 = 3 $ 과 같은 형식

 

---

논리 연산과 진리표

 

• $ \land $ | 논리곱 (Conjunction)

둘 다 참일 때만 참이다.

$$ p $$	$$ q $$	$$ p \land q $$
True	True	True
True	False	False
False	True	False
False	False	False

• $ \lor $ | 논리합 (Disjunction)

둘 다 거짓일 때만 거짓이다.

$$ p $$	$$ q $$	$$ p \lor q $$
True	True	True
True	False	True
False	True	True
False	False	False

• $ \lnot $ | 부정 (Negation)

명제가 거짓이면 참이고, 참이면 거짓이다.

$$ p $$	$$ \lnot \text{ } p $$
True	False
False	True

• $ \oplus $ 혹은 $ \veebar $ | 배타적 논리합 (Exclusive-OR)

둘 중 하나가 참이면, 즉 두 명제의 참, 거짓이 다르면 참이다.

$$ p $$	$$ q $$	$$ p \oplus q $$
True	True	False
True	False	True
False	True	True
False	False	False

• $ p \rightarrow q $ | 조건 명제 (Conditional Proposition)

조건 명제는 두 명제를 연결하는 형식의 논리 명제로 "만약 $ p $ 라면 $ q $ 이다" 와 같은 형태를 가진다. 여기서 $ p $ 는 가설(hypothesis) 혹은 전제(antecedent)라 하고, $ q $ 는 결론(conclusion) 혹은 결과(consequent)라 한다.

$$ p $$	$$ q $$	$$ p \rightarrow q $$
True	True	True
True	Fasle	False
False	True	True
False	False	True

주의할 점은 조건 명제의 결과가 참이라는 것이 결과가 참이라는 뜻은 아니다.

• $ q \rightarrow p $ | 역 명제 (Converse of Propopsition)

조건 명제에서 가설과 결론을 뒤집는 것이다. 조건 명제일 때와 진리값이 달라질 수 있다.

$$ p $$	$$ q $$	$$ q \rightarrow p $$
True	True	True
True	False	True
False	True	False
False	False	True

• $ p \leftrightarrow q $ 혹은 $ \text{iff} $ | 쌍조건 명제 (Biconditional Proposition)

두 명제가 모두 참이거나 모두 거짓이면 참이다.

$$ p $$	$$ q $$	$$ p \leftrightarrow q $$
True	True	True
True	False	False
False	True	False
False	False	True

• $ \equiv $ | 논리적 동치 (Logically Equivalent)

명제들로 이루어진 명제, 예를 들어 조건 명제 둘이 같은 조건에서 항상 진리값이 같다면 논리적 동치라 한다. 예를 들어 $ \lnot \text{ } ( p \lor q ) $ 와 $ \lnot \text{ } p \land \lnot \text{ } q $ 는 아래와 같이 같은 조건이라면 같은 진리값을 가지기 때문에 동치이다. 즉 $ \lnot \text{ } ( p \lor q ) \equiv \lnot \text{ } p \land \lnot \text{ } q $ 이다.

$$ p $$	$$ q $$	$$ \lnot \text{ } ( p \lor q ) $$	$$ \lnot \text{ } p \land \lnot \text{ } q $$
True	True	False	False
True	False	False	False
False	True	False	False
False	False	True	True

 

---

성질

 

• 논리의 드 모르간의 법칙 (De Morgan's Law for Logic)

$$ \lnot \text{ } ( p \lor q ) \equiv \lnot \text{ } p \land \lnot \text{ } q $$

$$ \lnot \text{ } ( p \land q ) \equiv \lnot \text{ } p \lor \lnot \text{ } q $$

• 대우 (Contrapositive)

조건 명제에서 가설과 결론 모두 진리값을 뒤집는 것이다. 예를 들어 가설이 참이고 결론이 거짓인 조건 명제의 대우는 가설이 거짓이고 결론이 참인 조건 명제이다. 이때 원래 명제와 그 대우는 동치이다.

$$ p $$	$$ q $$	$$ p \rightarrow q $$	$$ \lnot \text{ } p \rightarrow \lnot \text{ } q $$
True	True	True	True
True	False	False	False
False	True	True	True
False	False	True	True

 

---

연산자 우선순위

 

일반적인 수학 수식과 마찬가지로 괄호를 최우선으로 계산한다. 괄호가 없다면 아래 표를 따른다. 표는 상위에 있을수록 연산 우선순위가 높다는 뜻이다.

$ \lnot $	부정
$ \land $	논리곱
$ \lor $	논리합
$ \oplus $	배타적 논리합
$ \rightarrow $	조건
$ \leftrightarrow $	쌍조건