이산수학 기호: 두 판 사이의 차이

(새 문서: 분류:이산수학 ==개요 == 여기서는 이산수학에서 기초적으로 사용되는 여러 로직 기호들을 서술한다. == 여러가지 로직 기호들 == # Not: ~ # Conjunction (AND): <math display="inline">\land</math> # Disjunction (OR): <math display="inline">\lor</math> # Implication (then): <math display="inline">\rightarrow</math> > 가정이 거짓이면 모두 참이고 가정이 참일결우 결론이 거짓일 경우만 거짓이다. > 예...)
 
편집 요약 없음
 
16번째 줄: 16번째 줄:


== 연산 순서 ==
== 연산 순서 ==
 
<math display="inline">\forall , \exists</math> -&gt; () -&gt; ~ -&gt; <math display="inline">\land</math> -&gt; <math display="inline">\lor</math> -&gt; <math display="inline">\rightarrow</math> -&gt; <math display="inline">\leftrightarrow</math>
<math display="inline">\forall , \exist</math> -&gt; () -&gt; ~ -&gt; <math display="inline">\land</math> -&gt; <math display="inline">\lor</math> -&gt; <math display="inline">\rightarrow</math> -&gt; <math display="inline">\leftrightarrow</math>


== 비트 연산자 ==
== 비트 연산자 ==
윗 식들을 각각의 비트에 적용시킴으로써, 비트연산을 구현할 수 있다.
윗 식들을 각각의 비트에 적용시킴으로써, 비트연산을 구현할 수 있다.


== Tautology 와 contradiction ==
== Tautology 와 contradiction ==
항등 (Tautology)과 모순(Contradiction)은 언제나 참이되거나 거짓이 되는 명제의 조합이다. 여기서 항등도 모순도 아닌것은 중간 명제 (Contingency)라 한다. &gt; 항등명제: <math display="inline">p \lor \sim q</math>
항등 (Tautology)과 모순(Contradiction)은 언제나 참이되거나 거짓이 되는 명제의 조합이다. 여기서 항등도 모순도 아닌것은 중간 명제 (Contingency)라 한다. &gt; 항등명제: <math display="inline">p \lor \sim q</math>


41번째 줄: 38번째 줄:
이때 Predicate 에서 변수가 도메인으로 주어지면, 주어진 모든 도메인에 대하여 참인지 거짓인지 확인할 수 있다. 이를 Quantification 이라고 한다. 또한 주어진 도메인 전체에 대해서 참일 경우 참인 명제를 Universal Quantification 이라고 한다. 또한 기호로 <math display="inline">\forall xF(x)</math> 로 표기한다. 또한 Existential Quantification 은, 적어도 하나의 변수에 대해서 Predication 이 참일경우 참이된다. &gt; <math display="inline">\forall xP(x)</math> is true If P(x) is true for all (or every) x in given domain
이때 Predicate 에서 변수가 도메인으로 주어지면, 주어진 모든 도메인에 대하여 참인지 거짓인지 확인할 수 있다. 이를 Quantification 이라고 한다. 또한 주어진 도메인 전체에 대해서 참일 경우 참인 명제를 Universal Quantification 이라고 한다. 또한 기호로 <math display="inline">\forall xF(x)</math> 로 표기한다. 또한 Existential Quantification 은, 적어도 하나의 변수에 대해서 Predication 이 참일경우 참이된다. &gt; <math display="inline">\forall xP(x)</math> is true If P(x) is true for all (or every) x in given domain


<blockquote><math display="inline">\exist x P(x)</math> is true If P(x) is true for at least one element in x
<blockquote><math display="inline">\exists x P(x)</math> is true If P(x) is true for at least one element in x
</blockquote>
</blockquote>
여기서 Quantifier 가 중첩하여 사용되면 이를 Nested Quantifier 이라고 한다. 이떄 같은 Quantifier가 사용된경우 순서를 바꾸어도 아무 문제 없다. 그러나 서로 다른 Quantifier 가 사용된경우 순서를 바꾸면 결과과 달라지는 경우가 있기 떄문에 순서를 바꾸면 안된다.
여기서 Quantifier 가 중첩하여 사용되면 이를 Nested Quantifier 이라고 한다. 이떄 같은 Quantifier가 사용된경우 순서를 바꾸어도 아무 문제 없다. 그러나 서로 다른 Quantifier 가 사용된경우 순서를 바꾸면 결과과 달라지는 경우가 있기 떄문에 순서를 바꾸면 안된다.


예) 어떤 y 에 대하여, 모든 x 가 x + y = 0 이다.
예) 어떤 y 에 대하여, 모든 x 가 x + y = 0 이다.

2023년 2월 25일 (토) 11:05 기준 최신판


개요

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

여러가지 로직 기호들

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

연산 순서

[math]\forall , \exists[/math] -> () -> ~ -> [math]\land[/math] -> [math]\lor[/math] -> [math]\rightarrow[/math] -> [math]\leftrightarrow[/math]

비트 연산자

윗 식들을 각각의 비트에 적용시킴으로써, 비트연산을 구현할 수 있다.

Tautology 와 contradiction

항등 (Tautology)과 모순(Contradiction)은 언제나 참이되거나 거짓이 되는 명제의 조합이다. 여기서 항등도 모순도 아닌것은 중간 명제 (Contingency)라 한다. > 항등명제: [math]p \lor \sim q[/math]

모순: [math]p \land\sim p[/math]

Logical Equivalence

두 식이 항등식이란 두 식의 Biconditional 이 항등일경우이다. > p [math]\Leftrightarrow q \; if \; p \leftrightarrow q \; is \; Tautology[/math]

Predicate 와 Quantifier

만약 로직에 변수가 할당되어 있어서, 변수에 따라 참 거짓이 달라지면 이를 Predicate 라고 부른다.

x > 3 는 Predication 이다.

이때 Predicate 에서 변수가 도메인으로 주어지면, 주어진 모든 도메인에 대하여 참인지 거짓인지 확인할 수 있다. 이를 Quantification 이라고 한다. 또한 주어진 도메인 전체에 대해서 참일 경우 참인 명제를 Universal Quantification 이라고 한다. 또한 기호로 [math]\forall xF(x)[/math] 로 표기한다. 또한 Existential Quantification 은, 적어도 하나의 변수에 대해서 Predication 이 참일경우 참이된다. > [math]\forall xP(x)[/math] is true If P(x) is true for all (or every) x in given domain

[math]\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 이다.