개요
여기서는 이산수학에서 기초적으로 사용되는 여러 로직 기호들을 서술한다.
여러가지 로직 기호들
- Not: ~
- Conjunction (AND): [math]\displaystyle{ \land }[/math]
- Disjunction (OR): [math]\displaystyle{ \lor }[/math]
- Implication (then): [math]\displaystyle{ \rightarrow }[/math] > 가정이 거짓이면 모두 참이고 가정이 참일결우 결론이 거짓일 경우만 거짓이다. > 예를 들어 내가 장동건이면 너는 김태희다 의 경우, 내가 장동건이 아니기 떄문에 너가 김태희가 아니어도 참으로 인정되는 것처럼 말이다.
- Counterpositive (대우): [math]\displaystyle{ \sim q\rightarrow \sim p }[/math]
- Inverse (역): [math]\displaystyle{ q \rightarrow p }[/math]
- Counterpositive (대우): [math]\displaystyle{ \sim p\rightarrow \sim q }[/math]
- Biconditional (둘다 같으면 참): [math]\displaystyle{ \leftrightarrow }[/math]
- Exclusive Or (XOR 둘이 다르면 참): [math]\displaystyle{ \oplus }[/math]
연산 순서
[math]\displaystyle{ \forall , \exists }[/math] -> () -> ~ -> [math]\displaystyle{ \land }[/math] -> [math]\displaystyle{ \lor }[/math] -> [math]\displaystyle{ \rightarrow }[/math] -> [math]\displaystyle{ \leftrightarrow }[/math]
비트 연산자
윗 식들을 각각의 비트에 적용시킴으로써, 비트연산을 구현할 수 있다.
Tautology 와 contradiction
항등 (Tautology)과 모순(Contradiction)은 언제나 참이되거나 거짓이 되는 명제의 조합이다. 여기서 항등도 모순도 아닌것은 중간 명제 (Contingency)라 한다. > 항등명제: [math]\displaystyle{ p \lor \sim q }[/math]
모순: [math]\displaystyle{ p \land\sim p }[/math]
Logical Equivalence
두 식이 항등식이란 두 식의 Biconditional 이 항등일경우이다. > p [math]\displaystyle{ \Leftrightarrow q \; if \; p \leftrightarrow q \; is \; Tautology }[/math]
Predicate 와 Quantifier
만약 로직에 변수가 할당되어 있어서, 변수에 따라 참 거짓이 달라지면 이를 Predicate 라고 부른다.
x > 3 는 Predication 이다.
이때 Predicate 에서 변수가 도메인으로 주어지면, 주어진 모든 도메인에 대하여 참인지 거짓인지 확인할 수 있다. 이를 Quantification 이라고 한다. 또한 주어진 도메인 전체에 대해서 참일 경우 참인 명제를 Universal Quantification 이라고 한다. 또한 기호로 [math]\displaystyle{ \forall xF(x) }[/math] 로 표기한다. 또한 Existential Quantification 은, 적어도 하나의 변수에 대해서 Predication 이 참일경우 참이된다. > [math]\displaystyle{ \forall xP(x) }[/math] is true If P(x) is true for all (or every) x in given domain
[math]\displaystyle{ \exists x P(x) }[/math] is true If P(x) is true for at least one element in x
여기서 Quantifier 가 중첩하여 사용되면 이를 Nested Quantifier 이라고 한다. 이떄 같은 Quantifier가 사용된경우 순서를 바꾸어도 아무 문제 없다. 그러나 서로 다른 Quantifier 가 사용된경우 순서를 바꾸면 결과과 달라지는 경우가 있기 떄문에 순서를 바꾸면 안된다.
예) 어떤 y 에 대하여, 모든 x 가 x + y = 0 이다.