[이산수학🔗] 논리와 명제 (2장)

포스팅에 참고하는 교재 : 4차 산업혁명 시대의 이산수학 개정판 (생능출판)

2.0 개요

1) 논리 (Logic, Reasoning)

- 말이나 글에서 사고나 추리 따위를 이치에 맞게 이끌어 가는 과정이나 원리
- 인간의사고가 논리적인지를 판단하는 것은 사고하는 사람이 주어진 문제를 객관적으로 명확한지의 여부와 사고의 법칙을 체계적으로 추구하여 분석하는지의 여부로 결정됨.
 

2) 논리의 목적

- 특정한 논리를 통한 입증이 옳은가를 측정하는 데 필요한 법칙을 제공
- 논리에 대한 연구와 응용 분야임
- 컴퓨터 관련 학문이나 공학 등 여러 분야에 폭넓게 응용됨. 알고리즘의 설계나 증명, 디지털 논리 회로의 설계, 논리 프로그램 관련 분야, 관계형 데이터베이스 이론, 오토마타와 계산 이론, 인공지능 등에 필요한 이론적 기반을 제공함. 
 

2.1 논리와 명제

명제(proposition)

- 어떤 사고를 나타내는 문장 중에서 참이나 거짓을 객관적이고 명확하게 구분할 수 있는 문장이나 수학적 식
- 명제 논리(propositional Logic) : 주어와 술어를 구분하지 않고 전체를 하나의 식으로 처리하여 참 또는 거짓을 판별하는법칙
- 술어 논리(Predicate Logic) : 주어와 술어로 구분하여 참 또는 거짓에 관한 법칙
 - 명제는 통상 영문 소문자 p,q,r 등으로 표기
- 명제의 진릿값 (truth value) : 명제가 참 또는 거짓의 값을 가질 때 그 값
- 명제의 진리 값은 참일 때 T, 거짓일 때 F로 각각 표시.
- 명제는 T와 F의 2가지의 진리 값만을 가지므로 이진 논리라고 함.
 

2.2 논리 연산

1) 단순 명제 (simple proposition) : 하나의 문장이나 식으로 구성되어 있는 명제
2) 합성 명제 (composition proposition) : 여러 개의 단순 명제들이 논리 연산자로 연결되어 만들어진 명제 
3) 논리 연산자(Logical Operators) : 단순명제들을 연결시켜 주는 역힐을 하는 연결자

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

- 부정 (Negation)

• 임의의 명제 p가 주어졌을 때 그 명제에 대한 부정은 명제 p의 반대되는 진리값을 가짐.
• 기호로는 ∼p라고 쓰고, 'not p 또는 p가 아니다'라고 함.
• p의 진리값이 참이면 ∼p의 진리값은 거짓임.
• p의 진리값이 거짓이면 ∼p의 진리값은 참임.

- 논리곱 (Conjunction)

• 임의의 두 명제 p, q가 '그리고(AND)'로 연결되어 있을 때 명제 p, q의 논리곱은 p∧q로 표시함.
• 'p and q 또는 p 그리고 q'라고 함.
• 두 명제의 논리곱  p∧q는 두 명제가 모두 참인 경우에만 참이고 나머지 경우는 모두 거짓이다.

- 논리합(Disjunction)

• 임의의 두 명제 p, q가  '또는(OR)'으로 연결되어 있을 때 명제 p,q의 논리합은 p∨q로 표시함.
• 'p or q나 p 또는 q'라고 표현함.
• 두 명제의 논리합  p∨q는 두 명제가 모두 거짓인 경우에만 거짓의 진리값을 가진다.

- 배타적 논리합 (Exclusive OR)

• 임의의 두 명제 p, q의 배타적 논리합은 p⊕q로 표시
• 익스클루시브 OR(Exclusive OR) 또는 XOR이라고 읽음
• 진리값은 p와 q 두 명제 중에서 하나의 명제가 참이고 다른 하나의 명제가 거짓일 때 참의 진리값을 갖고, 나머지는 거짓의 진리값

- 조건(Implication)

• 조건 연산자를 함축(implication)이라고 함.
• 임의의 명제 p,q의 조건 연산자는 p→q로 표시함
• 'p이면 q이다'라고 읽음
• ∼p∨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에 대하여 q→p를 역(converse), ∼p→∼q를 이(inverse), ∼q→∼p를 대우(contrapositive)라고 한다. 

				명제	역	이	대우
p	q	∼p	∼q	p→q	q→p	∼p→∼q	∼q→∼p
T	T	F	F	T	T	T	T
T	F	F	T	F	T	T	F
F	T	T	F	T	F	F	T
F	F	T	T	T	T	T	T

- 쌍방 조건

• 임의의 명제 p, q의 쌍방 조건은 p↔q로 표시
• 'p이면 q이고, q이면 p이다'라고 함.
• 진리값은 p,q가 모두 참이거나 거짓일 때 참의 값을 갖고, 나머지는 거짓임.
• 아래와 같이 표현할 수 있다.
• p이면 q이고, q이면 p이다. (p if and only if q)
• p는 q의 필요충분조건이다.(p is necessary and sufficient for q)

* 연산자 우선순위
∼ > ∧> ∨ > → > ↔
 

4) 합성 명제의 진리 값

-  그 명제를 구성하는 단순 명제의 진리 값과 논리 연산자의 특성에 따라 값이 정해짐.
- 단순 명제의 진리값은 그 명제가 참이냐 거짓이냐에 따라 T 또는 F로 표시
- 합성 명제의 진리값은 복잡한 경우가 많음
- 진리 표(truth table)를 사용하여 단계적으로 연산함으로써 원하는 합성 명제의 진리값을 보다 쉽고 편리하게 구할 수 있음.
 

2.3 항진 명제와 모순 명제

1) 항진 명제 (tautology) 
합성 명제에서 그 명제를 구성하는 단순 명제들의 진리값에 관계없이 그 합성 명제의 진리값이 항상 참(T)의 값을 가질 때의 그 명제
2) 모순 명제 (contradiciton)
합성 명제에서 그 명제를 구성하는 단순 명제들의 진리값에 관계없이 그 합성 명제의 진리값이 항상 거짓(F)의 값을 가질 때의 그 명제  
 

2.4 논리적 동치 관계

논리적 동치(logical equivalence)

- 두 개의 명제 p, q의 쌍방조건 p↔q가 항진명제이면, 두 명제 p, q는 논리적 동치(logical equivalence)라 하고, p ≡ q 또는
p ⇔ q라고 표시한다.즉 명제 p, q는 같은 논리값을 가진다는 의미이다. 
- 두 명제가 논리적 동치일 경우는 두 명제의 논리값이 서로 같으므로 하나의 명제가 다른 명제를 대신할 수 있음.
- 어떤 복잡한 명제를 좀 더 간단한 명제로 만들기 위해 논리적 동치 관계인 다른명제를 사용하여 간소화함.
- 논리적 동치의 기본 법칙

논리적 동치 관계	법칙 이름
p ∨ p ⇔ p p ∧ p ⇔ p	멱등 법칙 (idempotent law)
p ∨ T ⇔ T p ∨ F ⇔ p p ∧ T ⇔ p p ∧ F ⇔ F	항등 법칙 (identity law)
∼T ⇔ F ∼F ⇔ T p ∨ (∼p) ⇔ T p ∧ (~p) ⇔ F	부정 법칙 (negation law)
∼(∼p) ⇔ p	이중 부정 법칙 (double negation law)
p ∨ q ⇔ q ∨ p p ∧ q ⇔ q ∧ p p ↔ q ⇔ q ↔ p	교환 법칙 (commutative law)
(p ∨ q) ∨ r ⇔ p ∨ (q ∨ r) (p ∧ q) ∧ r ⇔ p ∧ (q ∧ r)	결합 법칙 (associative law)
p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)	분배 법칙 (distributive law)
p ∨ (p ∧ q) ⇔ p p ∧ (p ∨ q) ⇔ p	흡수 법칙 (absorption law)
∼(p ∨ q) ⇔ (∼p) ∧ (∼q) ∼(p ∧ q) ⇔ (∼p) ∨ (∼q)	드 모르간 법칙 (De Morgan’s law)
p → q ⇔ ∼p ∨ q	조건 법칙
p → q ⇔ ∼q → ∼p	대우 법칙

- 두 명제가 논리적 동치 관계임을 입증하는 방법 (적당한 방법을 선택하기)

• 두 명제에대한 진리표를 구하고 두 명제의 진리값이 같음을 증명함
• 하나의 명제로부터 논리적 동치 관계의 기본법칙을 이용하여 다른 명제로 유도해 냄.

 

2.5  추론

추론

- 주어진 명제가 참인 것을 바탕으로 새로운 명제가 참이 되는것을 유도해내는 방법
- 주어진 명제들을 전제(premise)라고 한다.
- 새롭게 유도된 명제 q를 결론(conclusion)이라고 한다.
- 유효 추론(valid argument) : 주어진 전제가 참이고, 결론도 참인 추론
- 허위 추론(fallacious argument) : 추론의 결론이 거짓
-여러 가지 추론 법칙

추론 법칙	법칙 이름
p p → q ∴ q	긍정 법칙 (modus ponens)
∼q p → q ∴ ∼p	부정 법칙 (modus tollens)
p → q q → r ∴ p → r	조건 삼단 법칙 (hypothetical syllogism)
p ∨ q ∼p ∴q	선언 삼단 법칙 (disjunctive dilemma)
(p → q) ∧ (r → s) p ∨ r ∴ (q ∨ s)	양도 법칙 (constructive dilemma)
(p → q) ∧ (r → s) ∼q ∨ ∼s ∴ (∼p ∨ ∼r)	파괴적 법칙 (destructive dilemma)
p ∴ p ∨ q	선전 법칙 (disjunctive addition)
p ∧ q ∴ p	분리 법칙 (simplication)
p q ∴ p ∧ q	연접 법칙 (conjuction)

- 가장 많이 사용되고 잘 알려진 3가지 논리 법칙
긍정 법칙 : p, p → q ├ q (p와 p → q가 참이면 q도 참이다.)
부정 법칙 :  ∼q, p → q ├ ∼p
삼단 법칙 : p → q, q → r ├  p → r
 
 

2.6 술어 논리

1) 술어 논리

- 명제 중에는 값이 정해지지 않는 변수나 객체(object)가 있어서 참과 거짓을 판별하기 힘든 경우가 있다.
; 변수의 값에 따라 그 명제가 참이 되고 거짓이 될 수 있다.
- 위와 같은 형태의 명제를 p(x)라고 표시하고, p(x)를 변수 x에 대한 명제 술어(propositional predicate)라고 함.
- 명제 논리와 구분하여 명제 술어에 대한 논리를 술어 논리(predicate logic)라고 함.
 

2) 술어 한정자 (Predicate Qunatifier)

- 술어를 나타내는 방법 중에서 변수의 범위를 한정시키는 것
- 한정자에는 '모든 것에 대하여(for all)'과 '존재한다(there exist)'의 두 가지가 있다.
- '모든 것에 대하여'는 기호 ∀ 사용

• 변수 x가 가질 수 있는 모든 값에 대하여 p(x)의 전체 한정자(universal quantifier)는 다음과 같이 나타내는 명제를 말한다. '모든 x에 대하여 p(x)는 참이다.'
• 전체 한정자의 기호는 '∀' 로 표시하고, p(x)에 대한 전체 한정자는 ∀x p(x)로 나타내며, ∀x p(x)가 참이 되기 위한 필요충분조건은 술어 p(x)가 x의 전체 집합 U에 대하여 성립하여야 한다.

- '존재한다'는 기호 ∃ 사용

• 변수 x가 가질 수 있는 모든 값에 대하여 p(x)의 존재 한정자(existential quantifier)는다음과 같이 나타내는 명제를 말한다. '어떤 x에 대하여 p(x)가 참인 x가 존재한다.'
• 존재 한정자의 기호는 '∃'로 표시하고, p(x)에 대한 존재 한정자는 ∃x p(x)로 나타내며, ∃x p(x)가 참이기 위한 필요충분조건은 전체 집합 U 안에 p(x)를 만족시키는 x가 적어도 한 개 존재해야 한다.

- 전체 한정자에서 '모든 x에 대하여 p(x)가 성립한다'고 하면, 그의 부정은 'p(x)가 성립하지 않는 x가 존재한다.'가 된다. 
; ∼(∀x p(x))  ⇔ ∃x ∼(p(x))
- 존재 한정자에서 'p(x)가 성립하는 x가 존재한다'라고 하면, 그의 부정은 '모든 x가 p(x)가 성립하지 않는다.'가 된다.
; ∼(∃x p(x)) ⇔ ∀x (∼p(x))
 
 

2.7 논리용 언어 - Prolog

1) 프롤로그(Prolog)

: 논리와 명제를 컴퓨터 프로그램을 통해 보다 빠르고 쉽게 구현할 수 있는 프로그래밍 언어
 

2) Prolog의 특징

- 사실(fact), 규칙(rule), 질문(question)들로 프로그램이 구성됨.
- 사실과 규칙들을 데이터베이스로 구성하고, 프로그램 실행은 자료에 대한 질문의 응답 형식임.
- 대화식의 명령 방식을 사용하고, 사용자의 질문에 답하기 위해 추론 엔진(inference engine)을 사용하고 사용자가 사실과 규칙 등을 입력함.
 

3) Prolog 프로그램

- 우리가 쉽게 접하기 드문 색다른 형태의 언어
- 논리적 연산과 인공지능 분야에서의 논리 판단을 위한 프로그램의 구현에 있어서 매우 중요한 역할을 담당함.
- 사실과 규칙들만 기술하고 프로그램의 실행 순서는 명시하지 않으므로 '제 5세대 컴퓨터 언어'라고도 함.
 
 

2.8 논리의 응용과 4차 산업혁명과의 관계

• 논리와 명제는 현대 컴퓨터 관련 핵심 기술인 디지털 논리와 관계형 데이터베이스의 학문적 바탕이 됨.
• 최근 들어 떠오르는 4차 산업혁명의 핵심 기술인 인공지능 등과 밀접한 관계가 있다.

1) 논리의 응용 분야

- 디지털 논리: 디지털 논리 (Digital Logic)는 현실 세계에서 다양한 방면에 응용되고 있다.
- 관계형 데이터베이스

• 논리는 관계형 데이터베이스(Relational Database)를 통해 수많은 정보들을 체계적으로 저장한다.
• 다양한 질의(query)에 대해 빠르고 정확하게 답변할 수 있는 바탕이 되기도 한다.

 
2) 논리와 4차 산업혁명과의 관계
- 논리와 명제는 최근 떠오르는 4차 산업혁명의 핵심 기술인 인공지능(AI)과 밀접한 관계가 있다.
- 주어진 사실(fact)들과 규칙(rule)들을 이용하여 추론 엔진(inference engine)을 통해 새로운 사실들을 추론해 낼 수 있는 전문가 시스템(Expert system)은 문제 해결, 로보틱스(robotics), 게임, 의료 진단 등에 널리 활용되고 있다.
- 논리와 명제는 인공지능에서 쓰이는 엄밀한 규칙을 제공하기 때문에 논리와 명제에 대한 지식은 4차 산업혁명에 있어서 필수적인 지식으로 활용될 것이다.