할 수 있다는 신념, 하면 된다는 생각

정리에 앞서, 저는 현재 지거국 3학년으로 재학 중인 공대생입니다. 여기에 나와있는 내용들은 제가 직접 공부하고 요약해서 쓰기 때문에 정확하지 않은 정보가 있거나, 원하는 정보를 얻지 못하실 수 있습니다. 최대한 객관적이고 다양하게 준비해서 올리도록 노력하겠습니다. 자료의 출처나 내용에 대한 질문은 댓글이나 hcbeom9635@gmail.com으로 보내주시면 감사하겠습니다.

저는 공부할 때 Discrete Mathematics - Richard Johnsonbaugh 7th 제본판을 사용했습니다.

이산수학 1장. Sets and Logic

연산자(Quantifier)

이산수학 1장에서는 두 가지의 연산자를 배웁니다.

Universal Quantifier ∀

Existential Quantifier ∃

입니다.

• Universal Quantifier  ∀xP(x)

"for every" , "for all" 즉, 모든 x에 대해 만족하는 명제를 나타낼 때 쓰입니다. Universal Quantifier 명제가 참인지 거짓인지 판별하기 위해서는 반례(CounterExample)를 들어서 판별할 수 있습니다. 모든 x에 대해 만족하는 명제가 거짓이라면, 그 명제를 만족하지 않는 x를 찾으면 됩니다. 수식으로 설명해보겠습니다.

Ex)

• Existential Quantifier  ∃

"there exist" 즉, 명제에 해당하는 x의 값이 하나라도 '존재'하는지의 여부를 확인할 때 쓰입니다. 예시를 통해 확인해보겠습니다.

Ex)

그렇다면 이 두 가지를 동시에 쓸 수는 없을까요? 당연히 쓸 수 있습니다. 그런 경우를 Nested Quantifier라고 합니다.

• Nested Quantifier

Ex)

모든 x에 대해 식을 만족하는 모든 y가 있다면 명제는 참입니다. Nested Quantifier에 드모르간 법칙을 사용하면 아래와 같이 됩니다.

드모르간 법칙을 사용할 때 주의할 점은, ∀이 not을 취하면 ∃이 되고, ∃이 not을 취하면 ∀가 되는 것이 핵심입니다. 또한 명제에도 Not을 포함해줘야 합니다.