Toggle menu
Toggle preferences menu
Toggle personal menu
Not logged in
Your IP address will be publicly visible if you make any edits.

이산수학 기호

From noriwiki


개요

여기서는 이산수학에서 기초적으로 사용되는 여러 로직 기호들을 서술한다.

여러가지 로직 기호들

  1. Not: ~
  2. Conjunction (AND): [math]\displaystyle{ \land }[/math]
  3. Disjunction (OR): [math]\displaystyle{ \lor }[/math]
  4. Implication (then): [math]\displaystyle{ \rightarrow }[/math] > 가정이 거짓이면 모두 참이고 가정이 참일결우 결론이 거짓일 경우만 거짓이다. > 예를 들어 내가 장동건이면 너는 김태희다 의 경우, 내가 장동건이 아니기 떄문에 너가 김태희가 아니어도 참으로 인정되는 것처럼 말이다.
  5. Counterpositive (대우): [math]\displaystyle{ \sim q\rightarrow \sim p }[/math]
  6. Inverse (역): [math]\displaystyle{ q \rightarrow p }[/math]
  7. Counterpositive (대우): [math]\displaystyle{ \sim p\rightarrow \sim q }[/math]
  8. Biconditional (둘다 같으면 참): [math]\displaystyle{ \leftrightarrow }[/math]
  9. 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 이다.