4.1 집합과 집합의 연산 79
4. 집합과 논리
집합은 순서를 무시한 대상들의 모임을 말한다. 집합은 수학적 대상 중에서 가 장 단순한 대상이기 때문에, 종종 수학의 다른 개념이나 사실을 기술하기 위한 도구로 활용된다. 예를 들어 사고의 옳고 그름을 공부하는 논리학에서, 집합은 명제들 사이의 관계를 기술하는데 활용되어진다. 이 장에서는 집합의 개념을 바탕으로 논리학의 기본 을 살펴보고자 한다. 4.1절에서는 집합과 집합에 대한 기본연산을 다루고, 4.2절에서는 이와 관련하여 명제 또는 명제함수의 진위관계와 논리회로에 대해 배운다. 4.3절에서는 동치명제와 논리적 추론 등 보다 확장된 논리학 개념들에 대해 살펴보고자 한다.
4.1 집합과 집합의 연산
집합(Set)은 단순히 원소들의 모임이다. 원소의 수가 적은 경우, 집합은 A = {1, 2, 3, 4}
와 같이 원소를 나열(원소나열법)하여 표시할 수 있다. 이때 집합은 구성 원소에 의해 서만 결정되고, 원소의 순서나 반복여부는 중요하지 않다. 집합과 유사하지만 약간의 차이를 가진 개념으로는 1차원 배열(array)과 목록(list)이 있다. 목록은 구성 원소에 순서가 있느냐 없느냐에 따라 순차목록(ordered list)과 무순목록(unordered list)으 로 나눌 수 있는데, 1차원 배열은 순서가 있는 목록라고 생각할 수 있다. 배열(순차목 록)과 무순목록 그리고 집합의 관계를 살펴보기 위해, 세 배열
A={1, 2, 3, 4}, B={1, 3, 4, 2}, C={4, 3, 2, 2, 1}
를 생각해 보자. 세 배열은 집합으로는 서로 같다. 하지만 순서가 없는 목록이라는 관 점에서 A와 B는 같은 무순목록이지만, C는 5개의 원소로 구성되어 있는 다른 목록이 다. 순서가 있는 목록 혹은 배열로 생각하면 A={1, 2, 3, 4}와 B={1, 3, 4, 2}는 차이가 있다. 정리하여 보면 배열, 무순목록, 집합 순으로 추상화된 개념이라는 것을 알 수 있 다. 집합을 직접적으로 다룰 수 있는 컴퓨터 언어도 있기는 하지만 MATLAB과 같은 많은 프로그래밍 언어는 가장 단순한 배열 혹은 순차목록만을 다루고 있어, 무순목록이 나 집합을 구현하기 위해서는 목적에 따라 다양한 자료구조로 구현하여야 한다.
원소의 개수가 많거나 무한일 경우, 원소를 나열하는 대신 구성 원소를 판정하 는 조건을 기술(조건제시법)하여 표시할 수도 있다. 예를 들어, {2, 4, 6, 8, ...}과 같이 무한히 많은 양의 짝수로 구성된 집합은
D = { x : x는 양수이며 x는 짝수 }
와 같이 표시할 수 있다. 수학에서 자주 사용되는 집합으로는 자연수 집합 N, 정수 집 합 Z, 유리수 집합 Q, 무리수 집합 I, 실수 집합 R 등이 있다.
집합 X의 원소의 개수가 유한한 경우, 를 집합의 크기라 부르고 그 값은 (중복되지 않은) 원소의 개수를 나타낸다. 집합 중 원소를 하나도 가지지 않은 집합을 공집합 이라 부르고, 공집합의 크기는 이다.
예제 1.1 (집합과 집합의 크기)
배열을 정렬하여 서로 다른 원소를 찾아주는 MATLAB unique() 함수를 이용하여, 집합 C={4, 3, 2, 2, 1}의 원소의 개수를 구하고, 두 집합이 같은지를 판정하는 함수를 만들어 A={1, 2, 3, 4}와 B={1, 3, 4, 2}가 같음을 보여라.
>> C = [4 3 2 2 1]; uC = unique(C), nC = length(uC) uC =
1 2 3 4 nC =
4
function TF = setEquiv(A, B)
% setEquiv(A, B) returns true if set A = set B uA = unique(A); uB = unique(B);
if length(uA)==length(uB) && all(uA==uB) TF = true;
else
TF = false;
end
>> A = [1 2 3 4]; B = [1 3 4 2]; TF = setEquiv(A, B) TF =
1
집합 안에 특정 원소 가 포함되는 경우는 ∈로 표시하고, 그렇지 않은 경우 ∉로 표시한다. 만약
모든 ∈에 대하여 ∈이면, ⊂
로 표시하고, 를 의 부분집합이라 부른다. 공집합 는 모든 집합 의 부분집합이 다. 두 집합 와 에 대하여, 서로에 대하여 부분집합 ⊂이고 ⊂이면 두 집 합은 같다고 하고, 로 표시한다. 때에 따라 가 의 부분집합이지만, 둘이 같지 않은 경우, 를 의 진부분집합이라 부르고 ⊊으로 표시하기도 한다. 집합 에
대하여, 공집합을 포함한 모든 부분집합의 모임을 멱집합(power set)이라고 하고,
또는 라고 표시한다. 예를 들어, 개의 원소를 가진 집합
⋯
의 멱집합은
⋯
⋯
이고, 그 크기는 이 된다.4.1 집합과 집합의 연산 81
예제 1.2 (멱집합 출력하기)
집합 X의 임의의 부분집합을 2진수로 표현하면 각각의 비트가 1일 때 해당하는 위치의 원소가 있는 것으로 생각하여, X의 모든 부분집합을 공집합(00..00_2)부터 X(11..11_2)까지로 표현할 수 있다. 이러한 성질을 이용하여, 집합 X의 모든 부분집합 (멱집합)을 출력하는 프로그램을 작성하여라. (힌트: MATLAB함수 bitget(m, pos)은 자연수 m의 pos번째 bit 값을 알려준다.)
function powerSet(X)
% powerSet(X) prints out all subset of X uX = unique(X); nX = length(uX);
for m = 0 : 2^nX-1 fprintf('%d: {', m);
for pos = 1:nX
if bitget(m, pos)==1
fprintf(' %d', uX(pos));
end end
fprintf(' }\n');
end
>> powerSet([1 2 3]) 0: { }
1: { 1 } 2: { 2 } 3: { 1 2 } 4: { 3 } 5: { 1 3 } 6: { 2 3 } 7: { 1 2 3 }
두 집합 와 에 대하여, 합집합 ∪는 ∈ or ∈을, 교집합
∩는 ∈ and ∈을, 차집합 또는 ∖는 ∈ and ∉ 를 나타낸다. 때에 따라 관심이 되는 모든 원소를 포함하는 집합을 전체집합 (Universal set)이라 부르고, 일반적으로 로 표시한다. 여집합 또는 는
∈ ∉이므로 는 로 볼 수 있고, 차집합 는 ∩로 쓸 수 있 다. 예를 들어 유리수 집합 Q와 실수 집합 R에 대하여, ∪, ∩,
이다. 또한 실수 전체 집합 R에 대하여, 무리수 집합 I는 유리수 집합 Q의 여집합 이다.
밴다이어그램(Venn diagram)은 집합들 사이의 관계를 시각적으로 보여주기 위하여 사용되는 그림이다. 아래 그림은 밴다어그램을 이용하여 몇몇 집합연산의 결과
를 보여준 그림이다. 정리 1.3와 1.5, 1.6은 집합연산에 대한 주요한 법칙들인데, 벤다이 어그램을 이용하면 집합연산의 결과를 엄밀한 증명 없이 직관적으로 살펴볼 수 있다.
∪ ∖ ∪∩
정리 1.3 (집합연산의 주요법칙) 전체집합 와 세 집합 에 대한 합집합, 교 집합, 차집합, 여집합의 주요 관계식을 정리하여 보면 아래와 같다.
1. 결합법칙 Associative
∪∪∪∪
∩∩∩∩ Commutative2. 교환법칙
∪∪
∩∩
3. 배분법칙 Distribution
∩∪ ∩∪∩
∪∩ ∪∩∪
4. 대합법칙
Involution
5. 상보법칙
Complement
∪
∩
6. 경계법칙 Bound
∪
∩ 7. 항등법칙
Identity
∪
∩
8. 멱등법칙 Idempotent
∪
∩
9. 흡수법칙 Absorption
∪∩
∩∪ De Morgan’s10. 드모르강
∪∩
∩∪
예제 1.4 (집합의 연산)
집합 A, B의 합집합, 교집합, 차집합을 구하는 함수를 작성하고, 10이하의 자연수 중에서 짝수, 3의 배수, 5이상의 집합 A, B, C에 대한 배분법칙을 확인하여라.
function C = setCup(A, B)
% C = setCup(A,B) returns union of set A and set B C = unique([A B]);
function C = setCap(A, B)
% C = setCap(A,B) returns intersection of set A and set B uA = unique(A); uB = unique(B);
iA = 1; iB = 1; C = [];
while iA<=length(uA) && iB<=length(uB) if uA(iA) < uB(iB)
iA = iA + 1;
elseif uB(iB) < uA(iA)
4.1 집합과 집합의 연산 83
iB = iB + 1;
else % uA(iA) == uB(iB) C = [C uA(iA)];
iA = iA + 1; iB = iB + 1;
end end
function C = setMinus(A, B)
% C = setCap(A,B) returns difference of set A and set B uA = unique(A); uB = unique(B);
iA = 1; iB = 1; C = [];
while iA<=length(uA) && iB<=length(uB) if uA(iA) < uB(iB)
C = [C uA(iA)];
iA = iA + 1;
elseif uB(iB) < uA(iA) iB = iB + 1;
else % uA(iA) == uB(iB) iA = iA + 1; iB = iB + 1;
end end
>> A = [2:2:10]; B = [3:3:10]; C = [5:10];
>> A_BC = setCap(A, setCup(B,C)), AB_AC = setCup(setCap(A,B), setCap(A,C)) A_BC =
6 8 10 AB_AC =
6 8 10
정리 1.5 (합집합과 교집합의 크기) 두 집합 에 대한 합집합, 교집합의 원소의 개수는 다음과 같은 공식을 만족한다.
∪ ∩
정리 1.6 (부분집합의 연산) 두 집합 가 에 대하여, 가 의 부분집합이란 조건
⊂과 다음 세 조건은 각각 동치이다.
∩, ∪, ∪
예제 1.7 (합집합과 교집합의 크기)
전체집합 U=1:10에 대하여, 임의의 원소를 가진 부분집합은 U(rand(size(U))>.5)와 같은 방법으로 만들 수 있다. 임의의 두 집합 A, B를 만들고, 합집합과 교집합의 크기를 비교하여 정리 1.5 성립함을 보여라.
>> A=U(rand(size(U))>.5), B=U(rand(size(U))>.5) A =
1 6 7 9 B =
3 4 8 9 10
>> n_AuB = length(unique([A B])) n_AuB =
8
>> n_AnB = length(A)+length(B)-length(setCap(A,B)) n_AnB =
8
집합 에 대하여 부분집합 ⋯이
이고 ≠ 일 때∩ 이면 집합 ⋯를 의 분할(partition)이라고 한다. 분할이 서로 (교집합이 없는) 다른 집합의 합집합이라는 의미를 강조하여
·와 같이 표기하기도 한다. 예를 들어 에 대하여,
는 분할의 한 예이고, 이러한 분할의 모든 경우의 수는 4,140개나 된다. 분할의 경우의 수를 세는 방법은 ‘7장 조합론’에서 보다 자세히 살펴볼 예정이다.
집합
⋯
과
⋯
에 대하여 순서쌍(ordered pair) 집합 ×는 ×개의 원소를 가진 집합 ∈ ∈를 나타낸다.두 순서쌍 와 는 이고 일 때 같다. 즉, 이다. 따라서 순서쌍 와 는 일반적으로는 같지 않고, ×≠×이다. 순서쌍의 개념 을 확장하여 개의 집합 ⋯에 대하여, 차 순서쌍(n-tuple) ⋯ 의 집합을 정의할 수 있고, 그 크기는 ××⋯× ⋅⋅ ⋯ ⋅이다.
4.2 명제와 논리회로
명제(P roposition)는 참(Ture) 또는 거짓(False)을 판정할 수 있는 서술 (statement)을 말한다. 예를 들어, ‘: 2를 제외한 모든 소수는 홀수이다’는 참인 명제이 고, ‘: 1+1=3이다’는 거짓 명제이다. ‘: 태양계에서 생명체를 가진 천체는 지구뿐이다’
는 현재 진위여부를 모르지만 참 또는 거짓 중 하나이므로 명제인 반면, ‘ ’는
의 값에 따라 진위여부가 바뀌므로 명제라고 볼 수 없다.
명제 와 에 대하여, 논리곱(conjunction, AN D) ∧는 두 명제가 모두
4.2 명제와 논리회로 85
참(T)일 경우만 참(T)인 명제를 말하고, 논리합(disjunction, OR) ∨는 두 명제 중 하나라도 참(T)이면 참(T)인 명제를 말한다. 명제 에 대하여, 논리부정(negation, N OT) ∼는 참(T)은 거짓(F)으로, 거짓(F)은 참(T)으로 바꾼 명제이다. 논리곱, 논리 합, 논리부정은 아래와 같은 진리표로 정의할 수도 있다. MATLAB을 포함한 대부분 의 프로그래밍 언어에서 명제의 참(T)은 1, 거짓(F)은 0으로 표현한다.
∧ ∨
T T T T
T F F T
F T F T
F F F F
∼
T F
F T
예제 2.1 (논리연산)
명제 p는 ‘7이 5보다 크다’이고, 명제 q는 ‘3이 5보다 크다’이라고 할 때, 두 명제의 논리곱, 논리합과 p명제의 부정을 구하여라.
>> p = 7 > 5; q = 3 > 5; TF = [p&&q p||q ~p]
TF =
0 1 0
논리연산 ∧, ∨은 교환법칙과 결합법칙이 성립한다. 논리곱, 논리합 연산 이 함께 나올 경우 논리곱(AND)이 논리합(OR)에 비해 우선 계산되어진다. 따라서
∨∧∼는 ‘이거나 (이고 이 아닌) 경우’를 나타낸다. 참고로 나중에 살펴보게 될 조건명제 →와 쌍조건명제 ↔는 논리합보다 나중에 계산된다. 따라서
∧ → ∨∼는 ‘(이고 )이면 (이거나 가 아니다)’를 나타낸다.
예제 2.2 (논리연산의 연산순서)
명제 p, q, r을 각각이 ‘0과 1사이에서 임의로 만든 세 수가 0.5보다 크다’라는 명제라 할 때, p, q의 교환법칙과 p, q, r의 결합법칙이 성립함을 보여라. 아울러 논리연산 ∨ ∼ ∧에서 논리곱이 논리합보다 우선됨을 보여라.
>> p=rand>0.5, q=rand>0.5, r=rand>0.5 p =
0 q = 1 r = 1
>> [p&&q q&&p p||q q||p]
ans =
0 0 1 1
>> [(p&&q)&&r p&&(q&&r) (p||q)||r p||(q||r)]
ans =
0 0 1 1
>> [p||~q&&r (p||~q)&&r p||(~q&&r)]
ans =
1 0 1
명제는 논리학뿐만 아니라 컴퓨터 프로그램과 논리회로에서도 중요한 역할을 담당한다. 논리곱( ×, &q)과 논리합( , q) 그리고 논리부정(∼, )의 3개의 기본 연산을 이용하면 오늘날 우리가 사용하는 컴퓨터를 제어하는 다양한 불리언 대 수(Boolean algebra)를 구현할 수 있다. 두 명제 와 중 딱 하나만 참일 때 참이 되 는 배타적 논리합(exclusive-or, XOR) ⊻ 또는 ⊕는 새로운 연산은 아니고
∧∼∨∼∧을 간단히 기술한 것이지만 논리연산에 요긴하게 사용되어진다. 다 음은 불리언 대수의 기본연산 3개와 배타적 논리합 XOR을 구현하는 논리소자의 기호 이다. 그림에서 좌측 선(들)은 입력을 우측 선은 결과를 표시한다.
AND( ×) Gate OR( ) Gate NOT(∼) Gate XOR(⊕) Gate
다음은 논리곱, 논리합, 논리부정과 배타적 논리합의 진리 값을 1과 0으로 표 시한 표이다.
× ⊕
1 1 1 1 0
1 0 0 1 1
0 1 0 1 1
0 0 0 0 0
∼
1 0
0 1
마찬가지로 AND, OR, XOR의 결과 값을 부정한 NAND, NOR, XNOR도 널리 사용되어지는 논리연산이다. 이들 연산에 대응되는 논리소자의 기호는 다음과 같다. 아 래 기호에서 알 수 있듯이 NOT은 입력이나 출력에 동그라미(◦) 붙여 사용한다.
NAND(~( ×)) NOR(~( )) XNOR(~(⊕))
4.2 명제와 논리회로 87
이러한 논리 소자를 조합하면 다양한 입력 값에 대한 임의의 출력 값을 가지 는 논리 회로를 설계할 수 있다. 예를 들어 0(0000_2)부터 9(1001_2)까지 10개의 숫자 에 대하여, 4자리 논리(2진) 입력 값(p3, p2, p1, p0)으로부터 아래와 같은 7개의 표시등 (7 Segment Display)의 점멸여부를 표시하는 논리회로를 설계할 수 있다.
입 력 값 점 멸 표 시 등 수 p3 p2 p1 p0 a b c d e f g
0 0 0 0 0 1 1 1 1 1 1 0 1 0 0 0 1 0 1 1 0 0 0 0 2 0 0 1 0 1 1 0 1 1 0 1 3 0 0 1 1 1 1 1 1 0 0 1 4 0 1 0 0 0 1 1 0 0 1 1 5 0 1 0 1 1 0 1 1 0 1 1 6 0 1 1 0 1 0 1 1 1 1 1 7 0 1 1 1 1 1 1 0 0 0 0 8 1 0 0 0 1 1 1 1 1 1 1 9 1 0 0 1 1 1 1 1 0 1 1
예들 들어 표시등 c의 논리 값은 2(0010_2)만 거짓이므로, ∼ ∼ ∧ ∼ ∧∧ ∼ 와 같이 표현할 수 있다. 나중에 살펴볼 드로르강의 논리법칙에 의하면 ∨∨ ∼ ∨ 와 같이 표현할 수도 있다. 이와 같이 동일한 논리 값을 가지는 다양한 논리회로가 존 재하므로, 최소한의 부품을 이용하여 논리회로를 만드는 문제는 매우 중요한 문제이다.
일반적으로 NOT은 1개의 트랜지스터, NAND와 NOR은 2개의 트랜지스터 그리고 AND와 OR는 최대 4개의 트랜지스터가 있으면 구현할 수 있는데, 주어진 논리회로를 최소한의 트랜지스터를 이용하여 설계하는 프로그램은 실용적으로 널리 활용되어진다.
예제 2.3 (논리회로와 논리연산)
0부터 9까지의 이진 입력 값을 (p3, p2, p1, p0)이라 할 때, 7-표시등의 c를 논리회로로 구현하면 다음과 같다. 각각의 입력 값에 대한 표시등 c의 점멸 논리 결과 값을 표시하는 프로그램을 작성하여라.
p0
p1
p2
p3
>> for i = 0:9 p = bitget(i,1:4);
fprintf('%d = %d%d%d%d_2 : c=%d\n', i, p, p(1)||~p(2)||p(3)||p(4));
end
0 = 0000_2 : c=1 1 = 1000_2 : c=1 2 = 0100_2 : c=0 3 = 1100_2 : c=1 4 = 0010_2 : c=1 5 = 1010_2 : c=1 6 = 0110_2 : c=1 7 = 1110_2 : c=1 8 = 0001_2 : c=1 9 = 1001_2 : c=1
앞서 명제의 정의가 참 거짓을 판정할 수 있는 서술임을 살펴보았다. 따라서
‘은 홀수이다’는 명제가 아니지만, 명제의 개념을 확장하여 보면 이 서술은 에 따라 진위를 판정할 수 있는 명제가 됨을 알 수 있다. 이와 같이 변수 에 의해 명제가 만 들어지는 을 명제함수(propositional function)라 하고, 변수 의 집합을 명제 의 정의역이라고 한다. 예를 들어 실수 집합 R에 대하여, : 는 또는 일 때만 참이고 정의역 R의 나머지 값에 대해서는 모두 거짓인 명제함수 이다.
명제함수 이 참 값을 가지는 정의역의 원소들을 모두 모은 집합을 진리 집합(ture set)이라 말한다. 예를 들어, 자연수에 대한 명제함수 ‘: 은 소수이다’
의 진리집합은 = {2, 3, 5, 7, 11, 13, 17, 19, ...}이다. 집합 , , 을 각각 명제함
수 , , 의 진리집합이라 하자. 그러면 논리곱 ∧, 논리합 ∨, 논리부 정 ∼의 진리집합은 각각 ∩, ∪, 이 된다. 또한 정리 1.3(집합연산의 주요 법칙)에서 살펴 본 집합연산법칙들을 이용하여 논리연산에 대한 여러 법칙들을 유도할 수 있다. 예를 들어 논리곱과 논리합의 교환, 결합법칙이 성립하는 것은 물론이고, 논리 연산의 배분법칙, 흡수법칙 및 드모르강 법칙을 쉽게 구할 수 있다.
법칙 이름 진리집합 법칙 논리연산 법칙
1. 배분법칙 Distribution
∩∪ ∩∪∩
∪∩ ∪∩∪
∧∨ ∧∨∧
∨∧ ∨∧∨
2. 흡수법칙 Absorption
∪∩
∩∪
∨∧
∧∨ 3. 드모르강
De Morgan’s
∪∩
∩∪
∼∨ ∼∧∼
∼∧ ∼∨∼
예제 2.4 (명제함수와 논리연산)
전체집합 U=1:10에 대하여, 명제함수 ‘p(n): n은 홀수’, ‘q(n): n은 3의 배수’,
‘r(n): n은 5이상’이라 하자. 논리연산의 배분법칙 ∧∨ ∧∨∧과 드모르강 법칙 ∼ ∧ ∼ ∨ ∼ 이 성립함을 보여라. (Hint: MATLAB에서
4.2 명제와 논리회로 89
&&와 ||는 논리곱과 합을 &와 |는 원소끼리의 논리곱과 합을 말한다.)
>> U = 1:10; P = rem(U,2)==1, Q = rem(U,3)==0, R = U>=5 P =
1 0 1 0 1 0 1 0 1 0 Q =
0 0 1 0 0 1 0 0 1 0 R =
0 0 0 0 1 1 1 1 1 1
>> P_QR = P & (Q|R), PQ_PR = P&Q | P&R P_QR =
0 0 1 0 1 0 1 0 1 0 PQ_PR =
0 0 1 0 1 0 1 0 1 0
>> nPQ = ~(P&Q), nPnQ = ~P | ~Q nPQ =
1 1 0 1 1 1 1 1 0 1 nPnQ =
1 1 0 1 1 1 1 1 0 1
어떤 명제함수 가 ‘모든 ∈에 대하여, 이다’라는 명제는 하나의 예외 없이 정의역의 모든 원소 에 대하여 가 참인 경우에만 참이고, 단 하나의
에 대해서라도 가 거짓이면 거짓이다. 영어로 ‘for all , ’라고 읽는 전칭(한 정)명제(universal quantified statement) ‘ ∀’에서, ∀는 ‘모든’을 나타내는 전칭 기호(universal quantifier)라 한다. 예를 들어 ‘모든 실수 에 대하여, ’ 은 참인 전칭명제이지만, ‘ ∀’는 거짓 전칭명제이다. 유사한 꼴로 ‘어떤 ∈
에 대하여, 이다’ 또는 ‘∃ ’라는 명제는 ‘단 하나의 에 대해서라도 가 참’이면 참이 되는 존재(한정)명제이다. 이를 영어로는 ‘there exists ∈ such that
’ 또는 ‘for some ∈, ’라고 읽고, ∃는 ‘최소한 하나’를 의미하는 존재기호 (existential quantifier)라 한다.
전칭(한정)명제 ∀ 의 부정은 정의역의 모든 원소를 ⋯ 이라 할 때 ∼
∧∧ ⋯ ∧
이므로, 드모드르강 법칙을 앞에서부터 적용 하면 ∼∨∼
∧ ⋯ ∧
, ⋯, ∼∨∼∨ ⋯ ∨∼임을 알 수 있다. 유사한 방법으로 존재(한정)명제를 부정하여 정리하면, 다음과 같은 논리 드 모르강의 일반법칙을 유도할 수 있다.∼∀ ⇒ ∃ ∼, ∼∃ ⇒ ∀ ∼
예제 2.5 (전칭명제와 존재명제의 드모르강 법칙)
p(1), p(2), p(3)를 ‘임의의 0과 1사이의 세 수가 0.25보다 크다’는 명제의 진리 값이라 할 때, ∼ ∀ ⇒ ∃ ∼ 이 성립함을 실험적으로 보여라.
>> p = rand(1,3)>0.25; nAp = ~all(p), Enp = any(~p) nAp =
1 Enp = 1
4.3 동치명제와 논리적 추론
조건명제(conditional proposition) →는 ‘가설(hypothesis) 이면 결론 (consequent) 이다’의 형태로 표현되는 명제이다. (영어로는 if then 또는 only if 로 표현한다.) 조건명제는 가 참이고 가 거짓일 때만 거짓이고, 나머지는 모 두 참으로 약속한다. 다소 일반인의 상식과 차이가 있을 수 있으나, 전제가 거짓이면 결론에 상관없이 참으로 약속한 것이므로 ‘1+1=3이라면 2*2=5’이라는 명제는 참이다.
이러한 경우를 공허한 참(vacuously true)라 부르고, 전제가 되는 경우가 공집합인 경우 흔히 보게 된다. 예를 들어, ‘방정식 에서 근이 유리수( )이라면, 는 2의 배수이다’는 참인 명제이다.
모든 입력 값 ⋯에 대해 같은 진리 값을 가지는 두 명제 와 는 논리적동치(logically equivalent)라고 하고, 두 동치명제는 ≡로 표시한다. 예를 들어 배타적논리합 (XOR) ⊻는 ∧∼∨∼∧와 논리적 동치이다. 조건명제
→는 ‘가 거짓이거나 가 참일 때’ 참이므로 ∼∨로 표시할 수 있다. 명제 와
에 대한 다양한 조건명제들의 진리표를 살펴보면 다음과 같다.
→ → ∼→∼ ∼→ ∼
T T T T T T
T F F T T F
F T T F F T
F F T T T T
이 진리표로부터 →와 ∼→ ∼는 서로 동치이고, 서로 동치인 →≡∼ →∼
와는 다름을 알 수 있다. 즉 명제 →와 그 역명제(converse) →은 같지 않다.
예를 들어 ‘한 사람이 초등학생이면 그 사람은 미성년자이다’이라는 명제는 참이지만, 그 역 ‘미성년자이면 초등학생이다’는 참이 아니다. 마찬가지로 이명제(inverse)
∼→∼인 ‘초등학생이 아니면 미성년자가 아니다’도 역시 참이 아니다. 하지만 대우
4.3 동치명제와 논리적 추론 91
명제(contraposition) ∼→ ∼인 ‘미성년자가 아니면 초등학생도 아니다’는 참이다.
이 명제들의 관계를 정리해 보면, 명제와 대우는 동치이고 →≡∼∨≡∼→∼, 역과 이도 서로 동치 → ≡∼∨ ≡∼ →∼임을 알 수 있다. 쌍조건명제 (bidirectional) ↔는 ‘이면 이고, 이면 이다’의 형태로 표현되는 명제이다. (영 어로는 ‘ if and if ’ 또는 ‘ if and only if ’로 표현한다.) 동치명제를 표시해 보면, ↔≡→∧→이고 이를 다른 동치명제로 표현해 보면 다음과 같다.
↔≡→∧→≡∼∨∧∼∨≡∧∨∼∨∼
즉 ↔는 , 가 둘 다 참이거나 둘 다 거짓일 때 참인 명제이다.
예제 3.1 (동치명제)
명제 p1, p2, p3의 가능한 모든 입력 값들에 대해 두 명제 ∼ ∧∧와
∼ ∨ ∼ ∨ ∼ 가 동치임을 보여라
>> for i = 0:7
p = bitget(i,1:3);
c1 = ~(p(1)&&p(2)&&p(3)); c2 = ~p(1)||~p(2)||~p(3);
fprintf('%d %d %d -> %d %d\n', p(1),p(2),p(3), c1,c2);
end
0 0 0 -> 1 1 1 0 0 -> 1 1 0 1 0 -> 1 1 1 1 0 -> 1 1 0 0 1 -> 1 1 1 0 1 -> 1 1 0 1 1 -> 1 1 1 1 1 -> 0 0
주장(argument)이란 명제들을 (복수의) 전제(premises)와 결론(conclusion)으 로 구별하여 ⋯ ⇒ 꼴로 나타낸 것으로, ‘전제 ⋯가 모두 성 립하면 결론 이다’라는 표현되는 명제이다. 주장에서 결론이 참이 되기 위해 필요한 전제를 필요조건(necessary condition)이라고 한다. ‘: 그는 아시아에 있다’는 ‘: 그 는 한국에 있다’는 결론을 얻기 위한 필요조건 중 하나이다. 필요조건을 만족하지 않으 면 결론이 참이 될 수는 없으나, 필요조건만으로 결론에 도달할 수는 없다. 반면 충분 조건(sufficient condition)은 참이면 결론이 항상 참이 되는 조건이다. ‘: 그는 서울 에 있다’는 ‘: 그는 한국에 있다’는 결론의 충분조건 중 하나이다. 따라서 조건 , , 의 관계를 살펴보면, ‘⇒이고 ⇒’이고 ‘는 의 충분조건, 는 의 필요조건’이 된 다. 일반적으로 ‘주장 ⇒’에서 를 의 충분조건, 는 의 필요조건이라 한다.
추론(inference)은 올바른 전제(들)로부터 올바른 결론을 얻기 위한 일련의 작업을 말한다. 예를 들어 우리는 두 전제 와 →가 모두 참이면 도 참이 됨을 추 론할 수 있다
추론명 전제 결론
연역추론 Modus ponens →,
대우추론 Modus tollens →, ∼ ∼
삼단논법 Hypothetical syllogism →, → →
배타논법 Disjunctive syllogism ∨, ∼
논리곱 Conjuction , ∧
논리합 Addition ∨
논리축약 Simplification ∧
4.4 연습문제
#1. 1부터 30까지 자연수 중에서 2의 배수 또는 3의 배수의 집합을 uniq() 함수를 이용 하여 구하여라.
#2. 전체집합 U=1:20의 임의의 세 부분집합 A, B, C를 만들어 정리 1.3의 결합법칙과 배분법칙이 성립함을 실험적으로 보여라.
#3. 전체집합 U=1:20의 임의의 두 부분집합 A, B를 만들어 정리 1.3의 교환법칙, 흡수법 칙과 드모르강의 법칙이 성립함을 실험적으로 보여라.
#4. 조건 ⊂와 ∪ 는 동치이다. 이 성질을 이용하여, ⊂이면 true=1
를 계산하는 MATLAB함수 isSubset(A, B)를 작성하여라.
#5. 0부터 3까지 정수 p를 2진법으로 표시했을 때 2의 자리 값을 p(2), 1의 자리 값을 p(1)이라 하자. 0부터 3까지 정수 p에 대하여 논리회로 XOR(p(1), p(2))와 NAND(p(1), p(2)), NOR(p(1), p(2))의 값을 출력하는 프로그램을 작성하여라.
4.4 연습문제 93
#6. 논리연산의 드모르강 법칙∼∨ ∼∧∼와 ∼∧ ∼∨∼가 성립함 을 증명하기 위해, 가능한 모든 논리 값 p, q에 대하여 각각의 법칙에 대하여 좌변 과 우변의 논리 값이 항상 같음을 보여라.
#7. 주어진 n개의 명제에 대한 임의의 논리 값 p(1), p(2), ..., p(n)에 대하여, 두 논리 값
∼ ∧ ∧ ⋯ ∧ 와 ∼ ∨ ∼ ∨ ⋯ ∨ ∼ 가 같음을 보여라.
#8. 0(=000_2)부터 7(=111_2)까지의 정수를 이용하여 의 가능한 모든 논리 값 만 들고, 이들에 대해 →이고 → (=∼ ∨∧∼ ∨)의 논리 값과 → (=
∼ ∨)의 논리 값이 항상 같음을 보임으로써 삼단논법이 성립합을 증명하여라.
