앞만 보는 사람

정리에 앞서, 저는 현재 지거국 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을 포함해줘야 합니다.