[이산수학] 논리와 명제-1

논리와 명제

논리란?

사고가 논리적인지 판단하는 것으로 주어진 문제를 객관적으로 명확하게, 사고의 법칙을 체계적으로 분석하는지의 여부에 따라 결정된다.

 

논리는 명제 논리(Propositional Logic)와 술어 논리(Predicate Logic)으로 구분된다. 

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

주어와 술어
뫄뫄는 솨솨다. 라는 문장이 있을 때 뫄뫄는 주어, 솨솨는 술어라고 한다.

명제는 어떤 사고를 나타내는 문장 중에서 참과 거짓을 객관적이고 명확하게 구분할 수 있는 문장이나 수학적 식을 말하는데, 명제 논리는 하나의 명제가 최소의 단위로 판단하여 참과 거짓을 판멸하고 술어 논리는 하나의 명제를 술어와 그 술어의 수식(= 주어)을 받는 객체로 분리하여 판단한다.

 

명제는 참(T, true), 거짓(F, false)의 2가지의 진리값을 가지므로 이진 논리라고 하며, 명제는 소문자 p,q,r 등으로 표기한다.

💡진리값 : 명제가 가지는 값(참 또는 거짓의 값을 가진다.)
바나나는 맛있다. -> 명제 X( 참과 거짓의 진리값을 가질 수 없음)
3 + 6 = 8 -> 명제 O

논리연산

명제는 단순 명제와 합성 명제 2가지로 나눌 수 있다.

• 단순 명제 : 하나의 문장이나 식으로 구성되어 있는 명제
• 합성 명제 : 여러 개의 단순 명제들이 논리 연산자로 연결되어 만들어진 명제

논리 연산자에 의해 명제들을 연결할 수 있으며 논리 연산자의 역할에 따라 합성 명제의 진리값을 복합적으로 나타난다.

연산자의 이름	기호	연산자의 의미
부정	~	NOT
논리곱	∧	AND
논리합	∨	OR
배타적 논리합	⊕	Exclusive OR
조건	→	if ... then
쌍방 조건	↔	if and only if(iff)

부정(~p)

not p 또는 p가 아니다.

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

p	~p
T	F
F	T

논리곱(p ∧ q)

p and q 또는 p 그리고 q

두 명제의 논리곱은 두 명제가 참인 경우에만 참의 진리값을 가지고 그렇지 않으면 거짓의 진리값을 가진다.

p	q	p∧q
T	T	T
T	F	F
F	T	F
F	F	F

논리합(p ∨ q)

p or q, p 또는 q

두 명제의 논리합은 두 명제가 모두 거짓인 경우메나 거짓의 진리값을 가지고 그렇지 않으면 참의 진리값을 가진다.

p	q	p∨q
T	T	T
T	F	T
F	T	T
F	F	F

배타적 논리합(p⊕q)

익스클루시브(Exclusive) OR 또는 XOR

배타적 논리합의 진리값은 두 명제의 진리값이 서로 다를 때 참의 진리값을 가진다.

p	q	p⊕q
T	T	F
T	F	T
F	T	T
F	F	F

조건(p → q)

p이면 q이다.

조건 연산자는 함축이라고도 하며, p의 진리값이 참일 때, q의 진리값에 따라 진리값이 결정된다. p의 진리값이 거짓일 경우 q의 진리값과는 상관없이 참의 진리값을 가진다.

조건 연산자는 'p이면 q이다.' 뿐만 아니라 다양하게 표현할 수 있다.

• p이면 q이다. (if p, then q)
• p는 q의 충분조건이다.(p is sufficient for q)
• q는 p의 필요조건이다. (q is necessary for p)
• p는 q를 함축한다.(p implies q)

p	q	p→q
T	T	T
T	F	F
F	T	T
F	F	T

💡p이면 q이다.
p는 가정, q는 결과라고 할 수 있는데 p가 거짓이라면 그에 따른 결과값이 어떠하든 상관하지 않고 참으로 간주한다.

쌍방 조건(p↔q)

p이면 q이고, q이면 p이다.

두 명제가 모두 참이거나 거짓일 때, 참의 값을 가지고 그 외에는 거짓의 값을 가진다. p↔q는 (p→q) ∧ (q→p)의 값과 같다.

• p이면 q이고, q이면 p이다.(p if and only if q)
• p는 q의 필요충분조건이다.(p is necessary and sufficient fo q)

p	q	p↔q
T	T	T
T	F	F
F	T	F
F	F	T

논리 연산자의 우선순위

NOT(~) 👉 AND(∧) 👉OR(∨) 👉조건(→) 👉쌍방 조건(↔)

조건 연산자의 역, 이, 대우

명제 p→q의 역, 이, 대우를 구해보자.

• 역(converse) : q→p
• 이(inverse): ~p→~q
• 대우(contrapositive) : ~q→~p

여기서 이는 역의 대우이며 이들 명제의 상호관계는 아래와 같다. 

또한, 이들 명제의 진리표를 통해 명제와 대우는 같은 진리 값을 가지고, 역과 이는 같은 진리값을 가진다는 것을 확인할 수있다.

역, 이, 대우 간의 관계에 대한 진리표

따라서 이들은 다음과 같은 관계가 성립한다.

• 명제와 그의 대우는 논리적 동치 관계이다.
• 역과 이는 서로 대우 관계이다.
• 그 이외에는 논리적 동치 관계가 존재하지 않는다.

💡논리적 동치(logical equivalance)
두 개의 명제 p, q의 쌍방 조건 p↔q가 항진 명제(항상 참인 명제)이면, 두 명제는 논리적 동치 관계라 하고 p ≡ q 또는 p ⇔ q라고 표시한다. 즉 명제 p와 q는 같은 논리값을 가진다는 의미.