knowledge/math

[ 이산수학 ] 9. 공리와 정의, 그리고 정리와 증명, 증명법

공리와 정의 - 공리 : 별도의 증명없이 참으로 가정한 진술(statement)을 의미 - 정의 : 기호의 의미를 확실하게 규정한 것을 의미하며 수학에서는 의미론적인 정의가 아니라 형식적인 정의를 사용한다. 형식적 정의란 현실에서의 의미를 중요시 여기는 것이 아니라, 기호적인 의미가 강한 것을 의미한다. 정리와 증명 - 정리 : 공리와 정의, 또는 다른 정리를 통해 참이라는 것을 확인할 수 있는 진술(statement)을 의미한다 1) 보조정리(lemma) : 정리를 증명하는 데 도움이 되는 정리를 의미한다. 2) 따름정리(corollary) : 증명된 정리로부터 직접적으로 귀결시킬 수 있는 정리 3) 가설(conjecture) : 직관이나 부분적 증거를 통해 참이라고 주장되는 문장 - 증명 : 특정한 ..

[ 이산수학 ] 8. 술어 논리와 한정기호

명제함수(조건)와 술어 명제함수란 '조건'이라고도 하는데 명제 안에 포함된 변수의 값에 따라 참과 거짓이 달라지는 명제를 뜻한다. 예를 들어, "n은 짝수이다." 라는 명제를 명제함수 P(n) 이라고 할 수 있는 것이다. 술어란 주어에 대한 서술을 의미한다. 예를 들어, "x는 10보다 크다.( =x is greater than 10)" 이라는 명제함수 q(x)가 있다고 하자. 이 명제함수에서 "~는 10보다 크.(= is greater than 10)" 라는 문장이 술어가 되는 것이다. 이러한 술어에 대해서 '한정기호'라는 것을 사용하여 나타낸 것을 '술어 논리'라고 한다. 술어 논리(함수 논리 또는 양화 논리) 주어와 술어의 구조로부터 주어가 될 수 있는 대상에 대해 한정기호를 사용하는 논리를 말한다..

[ 이산수학 ] 7. 추론

추론 참인 명제를 바탕으로 새로운 명제가 참이 되는 것을 유도하는 방법을 말한다. 1) 전제 (premise) : 주어진 명제들을 말하며 p₁, p₂, p₃ ... 으로 나타낸다. 2) 결론 (conclusion) : 새로이 유도된 명제 q를 말한다. 3) 추론 (argument) : 전제 p₁, p₂, p₃ ... 를 통해 결론 q의 추론을 "p₁, p₂, p₃ ... ⊢ q" 이렇게 표현한다. - 유효 추론 (valid argument) : 주어진 전제와 결론이 모두 참인 추론 - 허위 추론 (fallacious argument) : 결론이 거짓인 추론 추론 규칙 세 줄 또는 두 줄로 이루어져 있는데 위의 두 개를 전제라고 하고 ∴ 에는 결론이 들어가게 된다. 아래에서 전제를 참이고 가정한다면 결론도..

[ 이산수학 ] 6. 명제의 동치

항진 명제와 모순 명제 항진 명제는 합성명제에서 명제를 구성하는 단순명제의 진리값에 관계없이 항상 참인 명제를 의미하며, 모순 명제는 단순명제의 진리값에 관계 없이 항상 거짓인 명제를 의미한다. 참고로 항진명제도 아니고 모순명제도 아닌 경우네는 불확정ㅁㅇ제라고도 한다. 여기서 약자를 사용하여 항진명제를 t, 모순명제는 c라고도 표시한다. 논리적 동치 두 복합명제 p,q에 대하여 가능한 모든 경우에 대하여 같은 진리값을 가지면 p, q는 논리적 동치라고 한다. 즉, p↔q가 항진명제이면 p,q는 논리적 동치이며 p≡q라고 표현한다. 이 때, ≡는 논리연산자가 아닌 논리적 동치를 ㅛ현하는 기호이며, ⇔를 사용하기도 한다. 조건-논리합 동치 : p→q는 ~p∨q와 논리적 동치이다. 이것을 조건-논리합 동치라고..