논리학

논리학은 인공지능과도 밀접한 관계를 가지고 있다. 지금까지 참으로 알려진 문장에서 새로 참인 문장을 유추해내는 것을 논리학에서는 연역이라고 하는데, 인공지능의 경우 연역적 추론을 이용해 사람처럼 행동하고, 때로는 인간이 해결할 수 없는 복잡한 계산을 통해 일기예보와 같은 예측이 어려운 작업을 수행하기도 한다. 논리학의 다양한 이론적 배경이 컴퓨터를 점점 지능적인 형태로 변화시키고 있다.

명제(proposition)

뜻이 분명하여 참과 거짓을 구분할 수 있는 문장을 명제라고 하는데, 프로그래밍 언어의 조건문, 반복문에서도 참과 거짓의 상태가 매우 중요하게 사용된다. 논리학과 철학에서 다루는 모든 내용은 명제로부터 시작한다고 말할 수 있다.

사실과 관계 없이 타당하지 않은 사실도 명제가 될 수 있기에 아래 두 문장은 모두 명제이다. 명제의 내용이 타당할 경우 명제는 참(True,T)이며 타당하지 않을 경우 명제는 거짓(False, F)이다. 또, 이런 참과 거짓을 명제의 진리값(truth value)이라고 한다.

명제인 경우

• 대한민국의 수도는 서울이다. (진리값:T)
• 서울대학교는 미국 LA에 위치해 있다. (진리값:F)
• 바나나는 과일이다. (진리값:T)
• 1 + 3 = 9 (진리값:F)

그런데 아래와 같이 객관적으로 참과 거짓을 명확히 구분할 수 없는 문장은 명제가 될 수 없다.

명제가 아닌 경우

• 건강 조심하세요.
• 제니는 키가 큰 편이다.
• 저는 행복합니다.
• 나는 귀엽고 섹시하다.

논리연산(logical operation)

논리 연산이란 , 거짓을 구별할 수 있는 명제를 연산하는 것이다. 기본적인 논리연산의 종류에는 논리합, 논리곱, 부정, 배타적 논리합이 있다.

논리연산 종류

• 논리합
• 논리곱
• 부정
• 배타적 논리합

논리연산자(logical operator)

실수 집합에서 실수와 실수의 덧셈 연산을 일반적으로 + 기호로 표현하듯 각각의 논리연산도 기호로 나타낼 수 있다. 그리고 이런 기호를 논리연산자라고 부른다. 특별히 문제가 발생하지 않는 선에서 종종 논리연산과 논리연산자를 혼용해서 사용하기도 한다.

진리표

합성명제의 진리값은 합성명제에 참여하는 단순 명제들의 참과 거짓 여부에 따라 결정된다. 참여하는 단순 명제들이 많을경우 명제의 진리값을 자연어로 서술하기 어려우므로 진리표를 사용하여 단계적으로 합성명제의 진리값을 구한다.진리표를 작성하는 방법은 가각의 단순명제들이 가질 수 있는 모든 진리값을 차례대로 나열한뒤 단순명제에서 주어진 합성명제로 단계적 확장해가며 진리값을 계산하는 것이다. 하나의 단순명제는 참 또는 거짓의 두가지 값을 가지므로, n개의 단순명제로 구성된 합성명제는 모두 2의n승개의 경우를 가지게 된다.

논리합(disjunction)

or 연산이라고도 불리며 논리연산자로 V를 사용한다. 또는의 의미를 가지며, 연결된 명제들 중 하나라도 참일 경우 결과는 참이되고 모두 거짓일 경우에만 거짓이 되는 논리연산이다.

예를 들어 명제 p는 날씨가 흐리다 이고 명제 q가 비가 온다라면 두 명제의 논리합 pVq 는 날씨가 흐리거나 비가 온다로 표현할 수 있다. 논리합 pVq의 진리값은 p나 q 둘 중 하나라도 참이면 참이 되고 둘 다 거짓일 경우에만 거짓이 된다.

논리합 pVq 진리표

p	q	pVq
T	T	T
T	F	T
F	T	T
F	F	F

논리곱(conjunction)

and 연산이라고도 불리며 논리연산자로 ∧ 를 사용한다. 그리고의 의미를 가지며, 연결된 명제들이 모두 참일 경우에만 결과가 참이되고 하나라도 거짓이 있을 경우 거짓이 되는 논리연산이다.

논리곱 p∧q 진리표

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

부정(negation)

not 연산이라고도 불리며 논리연산자로 ~ 를 사용한다. 따라오는 명제가 참이라면 결과는 거짓이 되고, 거짓이라면 참이 되는 논리연산이다. 주어진 하나의 명제의 진리값을 반대로 하는 연산이다.

부정 ~p 진리표

p	~p
T	F
F	T

배타적 논리합(exclusive disjunction)

xor 연산이라고도 불리며 논리연산자로 ⊕를 사용한다. 2개의 명제가 주어졌을 때, 1개만 참일 경우에만 결과가 참이 되고, 나머지 경우에는 거짓이 되는 논리연산이다.

배타적논리합 p⊕q 진리표

p	q	p∧~q	~p∧q	(p∧~q)V(~p∧q)	p⊕q
T	T	F	F	F	F
T	F	T	F	T	T
F	T	F	T	T	T
F	F	F	F	F	F

합성명제

하나 이상의 명제와 논리연산자들이 결합되어 만들어진 명제를 합성명제라고 한다.

합성명제 (p∧~q)V(p⊕q) 진리표

p	q	(p∧q)	p⊕q	(p∧~q)V(p⊕q)
T	T	T	F	T
T	F	F	T	T
F	T	F	T	T
F	F	F	F	F

조건명제

어떤 사실의 인과관계를 나타내는 명제이다. 명제 p와 p가 있을 때, 명제 p가 조건의 역할을 수행하고 명제 q가 결론의 역할을 수행하는 경우, p와 q의 합성명제를 조건명제라고 하고 p➡️q로 표시한다. 명제p가 참이고, 명제q가 거짓일 경우만 진리값이 거짓이며 나머지 경우에는 모두 참이라고 정의한다.

예를 들어 "준수가 어제 집에 있었다면 냉장고에 두유가 없을 것이다."는 명제 p "준수가 어제 집에 있었다" 와 명제 q "냉장고에 두유가 없을 것이다"가 결합된 명제다. 이때 명제 q는 결론의 역할을 한다.

조건명제 p➡️q 진리표

p	q	p➡️q
T	T	T
T	F	F
F	T	T
F	F	T

충분조건과 필요조건

충분조건

"if p, then q"

"if p, then q" 형식으로 표현할 수 있는 명제의 경우, p가 발생하면 q도 항상 발생하는 것을 보장한다는 의미에서 p를 q의 충분조건이라고 한다.

필요조건

"if not p, then not q"

"if not p, then not q" 형식으로 표현할 수 있는 명제의 경우, q가 발생하기 위해 필요하다는 의미에서 p를 q의 필요조건이라고 한다.

쌍조건명제

조건=p, 결론=q && 조건=q, 결론=p

명제p가 조건일 때 명제q가 결론이 되고, 동시에 q가 조건일 때 p가 결론이 되는 경우 p와 q의 합성 명제를 쌍조건 명제라고 하고 p↔️q로 표시한다.

쌍조건명제는 두개의 조건명제가 서로 결합이 되어 만들어진다. 즉 p↔️q는 (p➡️q)∧(q➡️p)로 분해할 수 있다. 흔히 "p는 q이기 위한 필요충분조건(p if and only if q)"이라고 한다. 쌍조건명제 p↔️q는 p와 q가 동시에 동일한 진리값을 가질 때 참이 된다.

조건명제 p↔️q 진리표

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

논리적 동치

두 명제 p와 q가 논리적으로 동등하면 논리적 동치라고 하고, p≡q 로 표시한다. 즉, 두 명제 p와 q가 항상 동일한 진리값을 가지면 논리적 동치라고 한다.

논리적 동치와 쌍조건명제
쌍조건명제와 논리적 동치는 동일한 대상에 대한 서로 다른 표현이다. 명제들의 관계를 조건과 결론 관점에서 이야기 하고 싶을 때는 쌍조건명제를, 논리적 동등성 관점에서 이야기하고 싶을 때는 논리적 동치를 사용한다.

역, 이, 대우

조건명제 p➡️q에 대해서 q➡️p를 역(converse), ~p➡️~q 를 이(inverse), ~q➡️~p를 대우(contrapositive)라고 한다.

항진명제, 모순명제

합성명제를 구성하는 명제의 진리값에 상관없이
항상 참인 명제를 항진명제, 항상 거짓인 명제를 모순명제라고 한다.

술어논리

명제논리

주어와 술어를 구분하지 않고 문장 전체를 하나의 명제로 간주하여 참과 거짓을 판별하는 법칙을 다룬다.

술어논리

주어와 술어를 구분하여 참과 거짓을 판별하는 법칙을 다룬다. 술어를 중심으로 그에 딸린 주어를 나열하는 형태로 문장을 표현한다. 그러므로 명제를 주어와 술어로 구분한 뒤 "술어(주어)"와 같은 형태로 나타낸다. 이때 주어는 변수의 역할을 수행한다.

합성명제로 유도할 수 없는 사실

명제	사실
모든 사람은 죽는다.	소크라테스는 죽는다

술어논리로 유도된 사실

명제	술어논리
모든 사람은 죽는다.	∀𝒙{사람(𝒙) -> 죽는다(𝒙)}
소크라테스는 사람이다	사람(소크라테스)
	∴죽는다(소크라테스)

명제함수와 한정자

𝒙+1 = 0

위 수식처럼 변수를 포함하고 변수의 영역이 제한된 문장이나 식을 명제함수라고 하며, 이때 사용된 변수의 영역을 정의역이라고 한다.

전체한정자

"모든"을 의미하며, 명제함수 ∀𝒙P(𝒙)와 같이 사용되었을 경우에는 정의역의 모든 𝒙에 대해서 P(𝒙)가 참임을 의미한다.

"모든 사과는 빨갛다"에 대한 전체한정자의 부정은 "어떤 사과는 빨갛지 않다"이다. "사과 𝒙는 빨갛다"를 P(𝒙)로 두고 위 두 문장을 식으로 나타내면 다음과 같다.

~ ∀𝒙P(𝒙) ≡ ∃𝒙~P(𝒙)

존재한정자

"존재한다"를 의미하며 ∃𝒙P(𝒙)와 같이 사용되었을 때에는 P(𝒙)가 참이 되는 어떤 𝒙가 정의역에 존재한다는 것을 의미한다. 만약 정의역의 모든 원소 𝒙에 대해 P(𝒙)가 거짓인 경우에는 ∃𝒙P(𝒙)는 거짓이 된다.

∃𝒙P(𝒙) : 정의역의 어떤 원소 𝒙에 대하여 P(𝒙)는 참이다.

벤다이어그램

한정자가 사용된 명제함수의 타당성을 분석하기 위해 사용할 수 있다. 논증의 타당성을 제공해주지는 않지만 직관적으로 이해하는데는 도움이 된다.

대전제, 소전제

모든 자연수는 실수이다.
-1은 실수이다.
∴ -1은 자연수이다.

"모든"이 들어간 첫번째 명제를 대전제라고 하고, 두번째 명제를 소전제라고 한다.

추론

참이라고 알려진 명제를 기초로 논리적인 과정을 거쳐 또 다른 명제를 이끌어 내는 과정을 말한다. 추론은 하나 이상의 전제와 하나의 결론으로 구성된다.

추론의 전제와 결론 정의
(1) 결론의 근거를 제공하는 이미 알려진 명제를 전제(premise)라고 한다.
(2) 새로 유도된 명제를 결론(conclusion)이라고 한다.

유효추론

전제를 참이라고 가정했을 때 그에 따른 결론이 항상 참이 되는 추론을 의미한다.

추론법칙

가장 기본적인 추론법칙은 논리적 동치를 이용한 대치법이다. 하나의 명제를 논리적으로 동치인 다른 명제로 바꾸는 것이므로 전제가 참이면 결론도 참이 된다.

👼 Reference

• 손진곤, 『이산수학』, 한국방송통신대학교출판문화원(2021), 제2장 논리