[이산수학] 논리와 명제

논리와 명제

논리

#1 논리

사고하는 사람이 주어진 문제를 객관적으로 명확한지 여부와 사고의 법칙을 체계적으로 추구하여 분석하는지 여부로 결정

#2 논리의 목적

• 특정한 논리를 통한 입증이 옳은가를 측정하는 데 필요한 법칙을 제공
• 알고리즘의 설계나 증명, 논리 프로그램 관련, 관계형 데이터베이스 이론 등에 필요한 이론적 기반을 제공

#3 명제 논리 (Propositional Logic)

주어와 술어를 구분하지 않고 전체를 하나의 식으로 처리하여 참 또는 거짓을 판별하는 법칙

#4 술어 논리 (Predicate Logic)

주어와 술어로 구분하여 참 또는 거짓을 판별하는 법칙

명제

#1 명제

어떤 사고를 나타내는 문장 중에서 true나 false를 객관적이고 명확하게 구분할 수 있는 문장이나 수학적 식

어떤 문장이나 식이 애매하지 않고 참과 거짓이 명백해야함

→ 3 + 2 =4 이다 ( 거짓인 명제 )

→ 지금 몇 시인가? ( 참, 거짓을 판단할 수 없으므로 명제가 아님 )

논리 연산

#1 단순 명제와 합성 명제

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

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

→ 장미꽃은 빨갛다, 유채꽃은 노랗다 ( 단순 명제 )

→ 장미꽃은 빨갛고 유채꽃은 노랗다 ( 합성 명제)

#2 논리 연산자

단순 명제를 연결시켜 주는 역할을 하는 and, or, not 연산자를 논리 연산자라고 함

이를 통해 합성 명제의 진리 값이 정해짐

#3 부정 (NOT)

임의의 명제 p가 주어졌을때 그 명제에 대한 부정은 p의 반대되는 진리 값을 가짐

p가 참이라면 p의 부정은 거짓, p가 거짓이라면 p의 부정은 참

#4 논리곱 (AND)

임의의 두 명제 p,q가 **‘그리고’**로 연결되어 있을 때

→ 두 명제가 모두 참일 경우에만 두 명제의 논리곱이 참

→ 나머지 경우에는 모두 거짓

#5 논리합 (OR)

임의의 두 명제 p,q가 **‘또는’**으로 연결되어 있을 때

→ 두 명제 중 하나가 참 일 경우 두 명제의 논리합은 참

→ 두 명제가 모두 거짓일 경우에만 두 명제의 논리합이 거짓

#6 베타적 논리합 (XOR)

임의의 두 명제 p,q에 대해

XOR연산 시

→ 두 명제 중 하나만 참인 명제가 존재할 때 베타적 논리합이 참이다

→ 두 명제가 같은 진리 값을 가질 때 베타적 논리합이 거짓

#7 조건 (p이면 q이다)

조건 연산자를 함축이라고 함

q가 필요 조건으로 q의 진리 값을 따라감

#8 쌍방 조건 (p이면 q이고, q이면 p이다)

임의의 명제 p,q에 대해 쌍방 조건의 진리 값은

두 명제가 모두 참이거나 거짓일때 참이며 그 외에는 거짓을 가짐

항진 명제와 모순 명제

#1 항진 명제

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

#2 모순 명제

합성 명제에서 그 명제를 구성하는 단순 명제들의 진리 값에 관계없이 그 합성 명제의 진리 값이 항상 거짓을 가질 때 그 명제를 모순 명제라고 함

논리적 동치 관계

#1 논리적 동치

두 개의 명제 p,q의 쌍방 조건이 항진 명제면, 두 명제 p,q는 논리적 동치

두 명제가 논리적 동치일 경우 두 명제의 논리값이 서로 같음 → 하나의 명제가 다른 명제를 대신 가능

복잡한 명제를 간단한 명제로 만들어 주기 위해 논리적 동치를 사용하여 간소화

추론

#1 추론

주어진 명제가 참인 것을 바탕으로 새로운 명제가 참이 되는 것을 유도해내는 방법

주어진 명제들 - 전제

새로이 유도된 명제 - 결론

• 유효 추론 : 전제와 결론 모두 참인 추론
• 허위 추론 : 추론의 결론이 거짓

#2 술어 논리

명제 중에는 값이 정해지지 않은 변수나 객체가 있어 참/거짓 판별이 어려운 경우가 존재

변수의 값에 따라 명제의 참/거짓이 변함

→ 변수에 대한 명제 술어라고 정의

→ 명제 논리와 구분하여 명제 술어에 대한 논리를 술어 논리라고 함

• 술어 한정자 : 변수의 번위를 한정시키는 것

→ 모든 것에 대해 (for all) / 존재한다 (exist)의 두 가지로 사용