[이산수학] 필기 2 - Foundations of Logic

이 글은 2018년 1학기에 서울시립대학교에서 수강하였던 이산수학 수업의 필기 내용입니다.

들었던 수업 내용을 복습할 겸 포스팅합니다. 영어 강의 내용이라 한글로 옮기면서 이상한 내용이 있을 수 있습니다.

Foundations of Logic

Mathematical Logic은 복잡한 Statement(일반 문장은 아니다. 뒤에 자세한 설명이 나온다.)을 사용하기 위한 도구이다. 아래와 같은 내용을 포함한다.

  • 그러한 로직을 표현하기 위한 언어
  • 간결한 표기
  • 객관적으로 사실여부를 Reasoning을 하기 위한 방법론

Foundations of Logic은 아래와 같이 크게 두개로 나뉜다.

  • Propositional Logic
  • Predicate Logic

Propositional Logic

Propositional Logic은 간단한 Boolean Connectives(and, or, not과 비슷하다) Statement로부터 구성된 복잡한 Statement에 관한 Logic이다. 여기서 Proposition은 한국말로 명제인데, 이는 Statement라고 부르며, 명확한 의미를 지니고, 참 혹은 거짓만을 지닌다.

Boolean Connectives (Operators)

operator 혹은 connective라고 부르는 것들은 하나 혹은 그 이상의 문장들을 묶어서 더 큰 문장을 만들어준다.

이 operator는 두가지 종류가 있다.

  • Unary Operator: 1개의 Operand(피연산자)만 취한다.
  • Binary Operator: 2개의 Operand(피연산자)를 취한다.

우리는 몇가지 잘 알려진 연산자를 꼭 이산수학이 아니어도 볼 수 있는데, 아래와 같다.

(Latex 문법상 \implies가 존재하는데 \to를 쓴 까닭은 Biconditional과 Logical Equivalence를 구분하기 위해 연산자를 맞추다보니 그렇게 되었다.)

이름 다른 이름 종류 기호
Negation Operator NOT Unary
Conjunction Operator AND Binary
Disjunction Operator OR Binary
Exclusive-OR Operator XOR Binary
Implication Operator IMPLIES Binary
Biconditional Operator IFF Binary

각각의 진리표는 아래와 같다.

Negation

T F
F T

Conjunction

F F F
F T F
T F F
T T T

Disjunction

F F F
F T T
T F T
T T T

Exclusive OR

F F F
F T T
T F T
T T F

Implication

F F T
F T T
T F F
T T T

Biconditional

F F T
F T F
T F F
T T T

Implication같은 경우는 p가 거짓이면 무조건 결과는 참이다. 이는 조금 특이하다고 볼 수 있는데, Implication을 적어본 후 영어로 옮겨보겠다.

위의 문장은 p implies q, if p, then q, q when p 정도로 해석할 수 있다. 즉 p가 거짓인 상황은 신경쓰지 않는다는 말이다.

Implication을 살펴보면 Converse, Inverse, Contrapositive도 짚고 넘어가야 한다.

우리나라 말로 옮기면 역/이/대우 정도이다. 아래 테이블을 보자

원래 문장 Converse Inverse Contrapositive

Binconditional 같은 경우는 위의 Operator들로 정의할 수 있다. (를 같음을 말하는 표기로 보자)

Tautologies, Contraditions

Equivalent를 논하기 위해 아래 두 단어를 알아야 한다.

  • Tautologies: 토톨로지는 복합적인 문장들이 각각의 문장의 참/거짓에 관계없이 무조건 일때를 말한다.
  • Contraditions: Contradiction은 복합적인 문장들이 각각의 문장의 참/거짓에 관계없이 무조건 거짓일때를 말한다.

위 단어는 각각 서로 반대이다.

Equivalence

Propositional Logic에는 명제의 같음을 구분하는 것도 증명 등 다른 작업을 위해 중요하다. 바로 Logical Equivalence이다.

우선 Propositional Equivalence는 두 명제가 Syntax가 달라도 문장의 Semantic이 똑같으면 Equivalent하다고 본다. 즉 명제는 Syntax와 Semantic으로 볼 수 있는데, Syntax는 그 명제를 원하는 뜻으로 구성하기 위한 규칙으로, Semantic은 그 명제의 의미 자체를 뜻한다고 볼 수 있다. 이 때 Propositional Equivalence는 Semantic만 보는 것이다.

이 때 복합적인 두 명제(Atomic한 여러 명제로부터 구성된 명제)가 논리적으로 같다면 (logically Equivalence 하다면) 이를 우리는 Equivalent하다고 한다. 아래처럼 쓸 수 있다.

, if and only if the compound proposition is a tautology


나중에 Equivalence Law부터 작성하기!!

April 22, 2018 에 작성
Tags: discrete mathematics 대학