에 대해 x=x+1이다. 명 제
서술문으로서 그 내용에 대하여 진리값 참이나 거짓 중 어느 하나만을 부여할 수 있는 문장을 명제(命題, statement)라고 한다. 진리값인 참과 거짓은 각각 T(True)와 F(False), 혹은 1과 0으로 표시한다. 예를들어,
울릉도는
섬이다. 임의의
정수 에 대해 x=x+1이다.
와 같은 문장은 참이나 거짓 중 하나의 진리값을 갖는 서술문이므로 명제인 반면에, 아래의 문장은 명제라고 할 수 없다.
울릉도는 섬입니까? (서술문이 아님)
이 명제는 참이다. (참·거짓의 판별이 불가능함)
명제는 더 이상 분해될 수 없는 기본명제와, 이들을 연결사에 의해 결합한 합성명제가 있다. 연결사는 명제연산에 있어서의 연산자로서 부정, 논리곱, 논리합, 조건(혹은함의), 쌍조건, 배타적논리합 등이 있다. 이들 각각의 연산에 대하여 명제 P, Q를 이용하여 정의해 보자.
정의) 1.1 명제연산을 위한 연결사(connective) 혹은 논리연산자는 다음과 같다.
■ 부정(否定, negation) : 한 명제에 대하여 그것이 "아님"을 나타낸다. 따라서 명제가 참이면 그의 부정은 거짓이 되며, 명제가 거짓이라면 그의 부정은 참이 된다. 명제 P의 부정은 ∼P, ￢P, NOT P, P' 등으로 기호화 한다.
■ 논리곱(conjunction) : 논리적(論理積)이라고도 하며, 두 명제의 논리곱은 모두가 참일 때만 참이 되며, 어느 하나라도 거짓이면 거짓이 된다. P 와 Q 의 논리곱은 P∧Q, P&Q, P AND Q, P·Q, PQ 등과 같이 표현한다.
■ 논리합(論理合, disjunction) : 두 명제의 논리합은 모두가 거짓일 때만 거짓이 되며, 어느 하나라도 참이면 참이 된다. P와 Q 의 논리합은 P∨Q, P OR Q, P+Q 등과 같이 표현한다. 'P OR Q' 라는 표현은, 영어 'or' 의 일반적인 의미에 따르면 아래의 배타적논리합과의 혼동을 초래할 수 도 있다는 점에 유의하여야 한다.
■ 배타적논리합(exclusive disjunction) : 두 개의 명제 중 어느 하나만이 참일 대 결과값이 참이 되는 경우를 배타적논리합이라고 한다. 즉, 두 명제가 모두 참이거나 거짓이면 그 결과는 거짓이 된다. P +Q, P EOR Q, P XOR Q 등으로 나타낸다.
■ 조건(conditional) 혹은 함의(含意, implication) : 'P →Q' 는 조건명제로서 '(만일) P이면 Q 이다.' 라고 읽는다. P가 참이고 Q 가 거짓일 때만 P → Q는 거짓이 되고, 그 외의 경우에 대해서는 참이 된다. 여기에서 P는 전건(前件), Q는 후건(後件) 이라고 부른다. 즉, 조건명제는 전건이 거짓인 경우이거나 후건이 참인 경우에 참인 진리값을 갖는다.(함의원리)
■쌍조건(雙條件, biconditional) : (P → Q) ∧ (Q → P)인 경우를 말하며, 'P ↔ Q'로 표기하고 'P이면 Q이고, Q 이면 P이다' 혹은 'P는 Q 이기 위한 필요충분 조건이다' 라고 읽는다. 다른 표현으로는 'P if mad only if Q'(P iff Q)가 있다. 쌍조건명제 P ↔ Q는 P, Q 모두가 같은 진리값을 가질 때만 참이 된다.
이들의 연산은 표 1.1 에 보인 진리표에 의해 정의될 수 있다. 두 개 이상의 연결사가 같은 식에서 함께 사용될 때, 괄호에 의해 연산의 우선순위가 정해지지 않는 경우에는, 다음과 같은 순서로 연산을 수행해야 한다.
부정(가장놓음) → 논리곱 → 논리합 → 조건 → 쌍조건(가장낮음) |
표 1.1 연결사에 대한 진리표
P |
Q |
∼P |
~Q |
P ∧ Q |
P ∨ Q |
P +Q |
P → Q |
P ↔ Q |
T T F F |
T F T F |
F F T T |
F T F T |
T F F F |
T T T F |
F T T F |
T F T T |
T F F T |
우리가 대수연산에서 변수, 상수, 연산자 등을 이용하여 대수식을 구성하는 것과 마찬가지로, 논리연산을 위하여 명제와 연결사를 이용하여 논리식을 만들 수 있다.
이 때, 명제는 특정명제와 명제변수를 모두 포함한다. 명제변수란 임의의 명제를 지칭하는 것으로서, 정해진 진리값을 갖는 특정명제를 대입하여 진리값을 부여할 수 있다. 명제식은 이러한 명제변수, 연결사 및 괄호로 구성되는 문자열로서, 다음의 규칙에 의거하여 생성되는 정합논리식(整合論理式, well-formed formula, wff)에 의해 정형화될 수 있다.
(1) 모든 명제변수와 상수(참, 거짓)는 논리식이다.
(2) 만일 A와 B가 논리식이면 다음도 논리식이다.
~A, ~B, (A ∨ B), (A ∧ B), (A → B), (A ↔ B)
(3) 위의 (1), (2) 항을 유한 회 반복 적용하여 만든 식만이 논리식이다.
예) 1.1 논리식의 예를 들면 다음과 같다.
(1) P ∨ Q, (P ∧ Q)
(2) (P ∧ Q) ∧ R → S ∧ ~S
(3) (P ↔ Q) ∨ (R ↔~ S) ∧ (~T ↔ R)
단, 실제 사용하는 데 있어 괄호는 편의상 생략할 수 있다. 이 때, 괄호를 생략하더라도 그 논리식의 의미는 바뀌지 말아야 한다. 다음부터는 정합논리식을 단순히 논리식이라 부르기로 한다.
정의)1.2 논리식 혹은 합성명제에 있어 각 명제의 참·거짓의 모든 조합에 대하여 항상 참인 것을 항진(恒眞)명제(tautology)라고 한다. 또 각 명제의 참·거짓에 관계없이 결과가 항상 거짓인 것을 모순(矛盾)명제라고 하며, 모순명제(contradiction)가 아닌 경우는 충족명제(contingency)라고 한다.
즉, 충족명제란 어떤 논리식에 대하여 논리식을 구성하는 명제들의 진리값의 조합 중 적어도 하나의 조합이 이 논리식을 참으로 만드는 경우를 일컫는다.
예) 1.2
(1) 항진명제 (P ∨ ~P), [A ∧ (A → B)] → B
(2) 모순명제 (Q ∧ ~Q), ~A ∧(A ∨ F)
(3) 충족명제 (P ∧ ~Q), ~A ∧(A → B)
정의) 1.3 또 두 개의 명제 P, Q로부터 만들어지는 조건명제 (P → Q)에 대한 역(逆), 이(裏)및 대우(對偶)는 다음과 같이 정의된다.
역(converse) : Q → P
이(inverse) : ∼Q → ∼P
대우(contrapositive) : ∼P → ∼Q
한편, 일반적으로 명제 P, Q에 대하여는 다음과 같은 관계가 성립하며, 이를 드 모르간(De Morgan) 법칙이라 부른다.
∼(P ∨ Q) = ∼P ∧ ∼Q
∼(P ∧ Q) = ∼P ∨ ∼Q
정의) 1.4 두 개의 논리식 A, B가 동치(同値, equivalence)라 함은 A, B가 각각 n 개의 명제변수 P₁,P₂,....., Pʼn으로 구성되어 있을 때, 이들 변수들에 어떠한 진리값의 조합(2ⁿ개)을 대입하여도 두 식의 결과값이 같은 경우이다. 이러한 동치관계는 A ≡B 혹은 A⇔B로 표현되며, 동치식(同値式)이라 한다.
정의) 1.5 논리식 A의 쌍대(雙對) A＊는 다음고 k같이 A의 연결사와 상수를 대치시킴으로써 얻어지는 논리식이다.
∨→∧ ∧→∨ T→F F→T
표 1.2는 논리연산에 대한 기본적인 속성을 동치식에 의해 보인다.
표 1.2 동 치 식
|
|
|
멱등률 결합률 교환율 분배율
흡수율 드 모르간 법칙 기타공식
|
P∨P⇔ P (P∨Q)R∨ ⇔P∨(Q∨R) P∨Q ⇔Q∨P P∨(Q∧R) ⇔(P∨Q)∧(P∨R) P∨(P∧Q) ⇔P ∼(P∨Q) ⇔∼P∧∼Q
P∨F ⇔P P∨T ⇔T P∨∼P ⇔T |
P∧P ⇔P (P∧Q)∧R ⇔P∧(Q∧R) P∧Q ⇔Q∧P P∧(Q∨R) ⇔ (P∧Q)∨(P∧R) P∧(P∨Q) ⇔P ∼(P∧Q) ⇔∼P∨∼Q
P∧F ⇔F P∧T ⇔P P∧∼P ⇔F |
표 1.2에서 A0, A1, B0, B1을 각각 논리식이라 할 때, 이 표의 각 행은
A0 ⇔ B0 A1 ⇔ B1
의 형태로 주어진다. 이 두 개의 동치식을 비교해 보며 ,A0과 A1 그리고 B0, 와 B1 은 서로 연결사와 상수가 상응되는 것을 알 수 있다. 예를 들면, 논리식A0, 에 포함된, ∨, T, F는 A1에서 각각 ∧, F, T로 대치된다. 이때 A0와 A1, 그리고 B0, 와 B1은 서로의 쌍대(dual)가 된다. A0 , B0 와 A1,B1은 쌍대등식이라고 한다.
정리) 1.1 논리식 A 와 A＊를 쌍대라 하고 P1, P2, .. Pn을 A 와 A＊에서 사용되는 단순명제변수라고 한다. 즉, A=A(P1, P2, .. Pn), A＊=A＊(P1, P2, .. Pn)이라 한다. 이때, 다음과 같은 관계가 성립한다. ∼A(P1, P2, .. Pn)≡A＊(P1, P2, .. Pn) A(∼P1,∼ P2, .. ∼Pn)≡∼A＊(P1, P2, .. Pn) |
이 정리는 드 모르간 법칙을 이용하여 증명할 수 있다.
