[Algorithm] 수학리부트 - 논리의 기초

논리의 기초

컴퓨터 프로그램도 0과 1을 계산하는 회로들이 복잡하게 ㅇ얽혀 결과를 내어놓는 논리 기계의 일종이라 할 수 있다. 

프로그램을 한 줄 작성할 때마다 우리는 이미 명제나 집합에 관련된 수학을 계산하고 있는 셈이다. 

수학의 토대인 논리의 기초를 공부해본다. 

명제와 논리연산

명제란 참인지 거짓인지 판별할 수 있는 문장이나 수식을 말한다. 

다음은 참인지 거짓인지를 판별할 수 있으므로 명제다.

• 달은 지구의 위성이다. (참 명제)
• 고래는 어류다. (거짓 명제)

다음은 참인지 거짓인지 판별할 수 없으므로 명제가 아니다.

• 수학은 어렵다. ('어렵다'는 것은 주관적인 개념)
• x² - x - 1 = 0 (x값이 정해지지 않았으므로)

명제는 대게 p, q, r 같은 영문자로 표시된다. 명제의 참과거짓을 그 명제의 진리값이라 하며, 참은 true의 첫 글자를 따서 T로, 거짓은 false의 첫 글자를 따서 F로 나타낸다.

 

논리연산	기호	뜻
논리합(OR)	∨	적어도 하나 이상의 명제가 참인가?
논리곱(AND)	∧	주어진 모든 명제가 참인가?
부정(NOT)	￢	원래 명제의 참,거짓을 뒤바꿈
배타적 논리합(XOR)	⊕	둘 중 하나만 참인가?

 

p	q	￢(p ∨ q)
T	T	F
T	F	F
F	T	F
F	F	T

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

 

표에서 보듯이 두 식의 진리값은 동일하다. 이처럼 같은 진리값을 가지는 두 명제를 동치라 하고, 기호 '≡'로 나타낸다. 위의 펴에 나온 두 논리식은 동치이므로 다음과 같이 쓸 수 있다. 

￢(p ∨ q) ≡ ￢p ∧ ￢q

 

유사한 방식으로 논리곱 연산을 부정 연산하면 다음의 동치관계를 얻는다.

￢(p ∧ q) ≡ ￢p ∨ ￢q

 

이 두 개의 동치관계는 특별히 드 모르간의 법칙 이라고 부르며, 복잡한 논리식을 계산할 때 유용하다.

 

숫자의 연산처럼 논리연산에도 몇 가지 기본적인 법칙이 성립한다. 

논리합(∨)은 덧셈과, 논리곱(∧)은 곱셈과 유사한 면이 있고, 진리값 T와 F는 각각 1,0과 비슷한 성질을 가진다. 

그러나 진리값은 숫자가 아니므로 두 부류의 연산은 엄연히 다르다.

 

두 개 이상의 명제를 대상으로 하는 논리연산의 법칙 중에서는 가장 간단한 것으로 교환법칙을 들 수 있다.

p ∨ q ≡ q ∨ p

p ∧ q ≡ q ∧ p

 

 

논리연산 중 배타적(exclusive) 논리합, 즉 XOR(⊕) 연산은 그 이름에서도 알 수 있듯이 두 명제 중 어느 한쪽만 참일 때 결과가 참이다. 이런 성질은 명제의 순서와는 관계가 없으므로 XOR는 교환법칙이 성립한다.

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

 

(p⊕q)⊕q ≡ p

이것은 결합법칙으로 간단히 증명할 수 있다.

(p⊕q)⊕q ≡ p⊕(q⊕q) ≡ p⊕F ≡ p

 

정리

논리연사자를 영어 그대로 or, and, not처럼 사용하는 언어도 있지만, 자바처럼 ||(OR), &&(AND), !(NOT)으로 쓰는 경우도 많다. 이러한 논리연산자는 주로 if나 while 문에서 수행 조건을 지정할 때 쓰이는데, 만약 조건문에 참여하는 변수가 많거나 경우의 수가 복잡하다면 연산법칙으로 간략화할 수도 있다. 예컨대 다음과같은 수도 코드가 있다고 하자.

 

if((!cond1 || cond2) && !(cond1 && cond2)) then ...

 

이 코드는 조건문은 한눈에 의미를 파악하기 쉽지 않고 나중에 수정할 때도 문제가 될 가능성이 크다. 여기에 논리연산의 결과를 적용하면 복잡한 조건문을 한결 간단하게 만들 수 있다. 

 

if( !cond1 ) then...

 

한편, XOR는 비트단위의 데이터를 조작하는데 주로 쓰인다.

 

느낀점

명제는 '참' 혹은 '거짓'임을 검증할 수 있는 명확한 문장이다. 참과 거짓을 판단할 수 있으면 명제가 아니다. 즉 '맞다', '틀리다'

이처럼 코드를 짜는데 있어서 명제를 알고 사용하면 간결한 조건문을 작성할 수 있을것같다.