[이산수학] 논리와 명제 LOGIC & PROPOSITION

이 글은 전공수업을 복습하며 작성한 글이다.

 

논리 

- 명제 논리: 주어와 술어를 구분하지 않고 전체를 하나의 식으로 처리하여 참과 거짓을 판별

- 술어 논리: 주어와 술어로 구분하여 참과 거짓을 판별

 

명제(proposition): 어떤 사고를 나타내는 문장 중 참과 거짓을 객관적이고 명확하게 구분할 수 있는 문장이나 수학적인 식

명제가 참 또는 거짓의 값을 가질 때 그 값을 진리값이라고 한다. 참(T) / 거짓(F) 명제는 T와 F 두 가지 진리값만 가지므로 

이진 논리라고 함. 명제는 어떤 문장이나 식이 애매하지 않고 참과 거짓이 명백해야한다.

 

단순명제 : 하나의 문장이나 식으로 구성

합성명제: 여러개의 단순 명제들이 논리 연산자로 연결되어 만들어진 명제

 

단순 명제들을 연결시켜주는 연결자들을 논리 연산자라고 한다. 

(1) 부정 (negation)

명제의 반대되는 진리값

 

(2) 논리곱(conjunction)

두 명제가 and 로 연결되어 있을 경우, 두 명제가 모두 참일 때만 참의 진리값을 가진다. 

 

(3) 논리합(disjunction)

두 명제가 or로 연결되어 있을 경우, 두 명제가 모두 거짓일 경우에만 거짓의 진리값을 가진다.

 

(4) 배타적 논리합(exclusive OR)

두 명제 중 하나의 명제가 참이고 하나의 명제가 거짓일 때 참, 그렇지 않으면 거짓의 진리값을 가진다.

 

(5) 조건(implication)

조건은 함축이라고도 함. p -> q 로 표시한다. p 이면 q 이다. 라고 읽음.

 

(6) 쌍방조건

p <-> q로 표시. p 이면 q 이고 q 이면 p이다. p 는 q 의 필요 충분 조건이다.

 

명제 p -> q 에 대하여

역  q -> p

이 ~p -> ~ q

대우 ~ q -> ~p

 

명제와 그의 대우는 논리적 동치 관계이다.

역과 이는 서로 대우 관계이다. 

그 외에는 논리적 동치 관계 존재하지 않음.

 

항진명제: 합성 명제에서 그 명제를 구성하는 단순 명제들의 진리값에 상관 없이 그 합성 명제의 진리값이 항상 참의 값을 가질 때 그 명제를 항진 명제라고 한다.

이와 반대의 개념은 모순 명제.