초등논리(Elementary Logic)

명제와 결합자(Statements and Connectives)

논리(logic) : 타당하지 않은 논증(arguments)으로 부터 타당한 논증을 구별하는데 쓰이는 원리와 방법에 대한것

명제(statement) : 참, 거짓 중 어느 한 경우로되 동시에 양쪽은 아닌 서술문.

명제라면 참, 거짓중 꼭 어느 한쪽이어야함을 분명히 가릴만한 조건이 갖추어져 있어야 한다.

 

 

단순명제(simple statements)의 예

a) 대구는 대한민국의 도시이다.

b) 2 + 1은 5와 같다.

c) 달은 푸른치즈로 만들어졌다.

e) 화성에는 지능을 지닌 생명체가 존재하지 않는다.

f) 지금 비가 내리고 있다.

위의 명제들은 당장 답을 내리기에 곤란할수도 있지만 참과 거짓을 가릴 수 있는 분명한 기준이 존재한다.

 

합성명제(compund statement)는 둘 또는 그 이상의 단순명제들이 결합된 것이다.

합성명제의 예는 아래와 같다.

a) $\sqrt 3$을 십진법으로 전개할 때 소수점 아래 105째 자리수는 7이다.

 

관행상 단순명제는 $p,q,r,s \cdots$ 같은 소문자로 나타내며 합성명제는 $P,Q,R,S \cdots$ 같은 대문자로 나타낸다.

 

아래와 같이 결합자(connectives)를 통해 단순명제 $p,q,r,s \cdots$를 연결하여 합성명제를 구성할 수 있다.

a) $\sim$ : $not$

b) $\wedge$ : $and$

c) $\vee$ : $or$

d) $A ~ \rightarrow ~ B$ : $if ~ A ~ then ~ B$

e) $A ~ if ~ and ~ only ~ if ~ B$ : $A \leftrightarrow B$

성분(components) : 합성명제에 쓰인 각각의 명제를 지칭한다.

 

NOT

$\sim p$는 명제 $p$가 거짓일때 참이고, 참일때 거짓인 명제이다.

가령

"$3$은 홀수이다."를 $p$라 할 때 이 명제는 참 이지만, 그 부정 $\sim p$ "$3$은 홀수가 아니다."는 거짓이다.

$p$	$\sim p$
$T$	$F$
$F$	$T$

즉 $p$가 참이면 $\sim p$는 거짓이고 $p$가 거짓이면 $\sim p$는 참이다.

 

AND

$p \wedge q$는 명제 $p$와 $q$ 가 둘다 참일때만 참인 명제이다. 둘중 하나라도 참이 아니라면 거짓이다.

$p$	$q$	$p \wedge q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$F$

AND 합성명제의 예는 아래와 같다

"하늘은 푸르고 장미는 붉다."

"4는 짝수이다 그리고 5는 홀수이다."

 

OR

$p \vee q$는 명제 $p$와 $q$ 둘중 하나가 참일때 참이되는 명제이다. 둘다 거짓이면 거짓이된다.

$p$	$q$	$p \vee q$
$T$	$T$	$T$
$T$	$F$	$T$
$F$	$T$	$T$
$F$	$F$	$F$

 

 

if A then B

$p \rightarrow q$는 두 명제 $p$와 $q$사이에 조건부(conditional)라고 불리는 결합자 $\rightarrow$를 붙여서 만든 합성명제이다.

$p \rightarrow q$는 $\sim (p \wedge \sim q)$와 동치이다.

$p$	$q$	$\sim q$	$p \wedge \sim q$	$p \rightarrow q [\equiv \sim (p \wedge \sim q) ]$
$T$	$T$	$F$	$F$	$T$
$T$	$F$	$T$	$T$	$F$
$F$	$T$	$F$	$F$	$T$
$F$	$F$	$T$	$F$	$T$

즉, 조건($p$)을 만족해도 결과($q$)가 성립되지 못하는 경우에만 거짓이 된다.

예와 함께 확인해보자.

다음과 같은 2가지 명제 $p$와 $q$를 정의한다.

명제 $p$가 "공항에 늦게 도착한다."

명제 $q$가 "비행기를 탄다"

이때

"공항에 일찍 도착하면 나는 비행기를 탈 수 있다."는 명제 $p \rightarrow q$ 가 된다.

 

4개의 경우의 수와 함께 명제의 진리값을 살펴보겠다.

a) 공항에 일찍 도착하는 경우 명제 $p$는 참이되며 비행기를 타게될 경우 명제 $q$는 참이된다.

b) 공항에 일찍 도착하는 경우 명제 $p$는 참이되며 비행기를 놓칠 경우 명제 $q$는 거짓이된다.

c) 공항에 늦게 도착하는 경우 명제 $p$는 거짓이 되며 비행기를 타게될 경우 명제 $q$는 참이된다.

d) 공항에 늦게 도착하는 경우 명제 $p$는 거짓이 되며 비행기를 놓칠 경우 명제 $q$는 거짓이된다.

위의 예시에서 c)와 d)는 합성명제에서 상정하지 못한 경우이기에 거짓말은 한것은 아니므로 $p \rightarrow q$는 참이 된다.

하지만 b)의 경우는 공항에 일찍 도착하는 합성명제에서 제시한 조건을 만족했음에도 거짓의 결과를 얻었으므로 $p \rightarrow q$는 거짓이된다.

 

그럼 위 합성명제의 부정은 어떻게 될것인가?

$\sim (p \rightarrow q) \equiv p \wedge \sim q$ 이므로

"공항에 일찍 도착했고 비행기를 탈수가 없다" 가 된다. 그렇기에 해당 명제를 만족하는 상황만이 거짓이 됩니다.

 

A if and only if B

$p \leftrightarrow q$ : $p$이면, 그리고 그때에만 $q$

쌍조건부$p \leftrightarrow q$은 $(p \rightarrow q) \wedge (q \rightarrow p)$와 동치이다.

진리표는 아래와 같다.

$p$	$q$	$p \rightarrow q$	$q \rightarrow p$	$p \leftrightarrow q [\equiv (p \rightarrow q) \wedge (q \rightarrow p)]$
$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$F$
$F$	$T$	$T$	$F$	$F$
$F$	$F$	$T$	$T$	$T$

예와 함께 확인해보자.

명제 $p$가 "공항에 늦게 도착한다."

명제 $q$가 "비행기를 탄다"

이때

"공항에 일찍 도착하면, 그리고 그때에만 나는 비행기를 탈 수 있다."는 명제 $p \leftrightarrow q$ 가 된다.

 

4개의 경우의 수와 함께 명제의 진리값을 살펴보겠다.

a) 공항에 일찍 도착하는 경우 명제 $p$는 참이되며 비행기를 타게될 경우 명제 $q$는 참이된다.

b) 공항에 일찍 도착하는 경우 명제 $p$는 참이되며 비행기를 놓칠 경우 명제 $q$는 거짓이된다.

c) 공항에 늦게 도착하는 경우 명제 $p$는 거짓이 되며 비행기를 타게될 경우 명제 $q$는 참이된다.

d) 공항에 늦게 도착하는 경우 명제 $p$는 거짓이 되며 비행기를 놓칠 경우 명제 $q$는 거짓이된다.

먼저 a)를 살펴보자. 공항에 일찍 도착하는 경우를 만족하고 비행기를 탔으므로 이는 참이다.

d)의 경우는 공항에 늦게 도착했기에 비행기를 탈 수 있는 유일한 조건을 만족하지 못했으며 마찬가지로 비행기를 못탔으므로 참이된다.

하지만 b)와 c)의 경우 조건에 반대되는 결과가 나왔으므로 거짓이된다.

 

 

항진명제(Tautology), 함의(Implication), 동치(Equivalence)

모든 논리적 가능성에 대하여 참인 명제를 항진명제라 한다.

항진명제의 예

a) $p \vee \sim p$

b) $p \rightarrow p$

c) $p \wedge q \rightarrow q \wedge p$

d) $p \rightarrow p \wedge p$

e) $p \wedge q \rightarrow q$

단순명제 또는 합성명제 $P, Q$에 대한 조건문 $P \rightarrow Q$가 항진일때 이것을 함의(implication)라 하고 $P \Rightarrow Q$("$P$는 $Q$를 함의한다(implies)." 라고 읽는다.)

수학이나 논리에서의 정리(theorem)는 참인명제이다. 이러한 정리의 타당성을 밝히는 일을 증명(proof)라 한다.

임의의 두 명제 $p,q$에 대하여 다음이 성립한다.
a) 합의 법칙(Law of addition; Add.)                 $p \Rightarrow p \vee q$
b) 단순화법칙(Laws of simplification; Simp.)               $p \wedge q \Rightarrow p, p \wedge q \Rightarrow q$
c) 논리합의 삼단논법(Disjunctive Syllogism(D.S.)     $(p \vee q) \wedge \sim p \Rightarrow q$

대체로 쌍조건문 $P \leftrightarrow Q$가 항진명제일 때 $P$와 $Q$는 동치(equivalence)라 하고 이것을 $P \Leftrightarrow Q$와 같이 나타낸다.

  

두 명제 $P,Q$에 대해 $P \Leftrightarrow Q$ 혹은 $Q \Leftrightarrow P$ 이면 $P$와 $Q$ 의 진리값은 같다.

따라서 $P \Leftrightarrow Q$와 $P \equiv Q$는 같은뜻을 지닌다.

 

즉,

$p \Rightarrow r$ : 무조건 참

$p \Leftrightarrow r$ : $p$와 $r$의 논리값이 항상 동일.

 

임의의 두 명제 $p,q$에 대하여 다음이 성립한다.
a) 이중부정법(Law of Double Negation; D.N.)    $\sim (\sim p) \equiv p$
b) 교환법칙(Commutative Laws; Com.)    $p \wedge q \equiv q \wedge p, \;\;\; p \vee q \equiv q \vee p$
c) 멱등법칙(Laws of Idempotency; Idemp.) : $p \wedge p \equiv p,\;\;\;\; p \vee p \equiv p$
d) 대우법칙(Contrapositive Law; Contrap.) : $(p \rightarrow q) \equiv (\sim q \rightarrow \sim p)$

드 모르간의 법칙(De Morgan's Laws; De M.)
임의의 두 명제 $p,q$에 대하여 다음이 성립한다.
$$\sim (p \wedge q) \equiv \sim p \vee \sim q$$
$$\sim (p \vee q) \equiv \sim p \wedge \sim q$$

임의의 세 명제 $p,q,r$에 대하여 다음이 성립한다.
a) 결합법칙(Associative Laws; Assoc.)
$$(p \wedge q) \wedge r \equiv p \wedge(q \wedge r) \\ (p \vee q) \vee r \equiv p \vee (q \vee r)$$

b) 분배법칙(Distributive Laws; dist.)
$$p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r) \\ p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$$

c) 추이법칙(Transitive Law; Trans.)
$$(p \rightarrow q) \wedge (q \rightarrow r) \Rightarrow (p \rightarrow r)$$

 

임의의 네 명제 $p,q,r,s$에 대하여 다음이 성립한다.
a) 구성적 양도논법(Constructive Dilemmas; C.D.)
$$(p \rightarrow q) \wedge (r \rightarrow s) \Rightarrow (p \vee r \rightarrow q \vee s) \\ (p \rightarrow q) \wedge (r \rightarrow s) \Rightarrow (p \wedge r \rightarrow q \wedge s)$$

b) 파괴정 양도논법(Destructive Dilemmas; D.D.)
$$(p \rightarrow q) \wedge (r \rightarrow s) \Rightarrow (\sim q \vee \sim s \rightarrow \sim p \wedge \sim r) \\ (p \rightarrow q) \wedge (r \rightarrow s) \Rightarrow (\sim q \wedge \sim s \rightarrow \sim p \wedge \sim r )$$

 

임의의 두 명제 $p,q$에 대하여 다음이 성립한다.
a) 긍정식 삼단논법(Modus Ponens; M.P.)
$$(p \rightarrow q) \wedge p \Rightarrow q$$

b) 부정식 삼단논법(Modus Tollens; M.T.)
$$(p \rightarrow q) \wedge \sim q \Rightarrow \sim p$$

c) 귀류법(Reductio ad Absurbum; R.A.)
$$(p \rightarrow q) \Leftrightarrow (p \wedge \sim q \rightarrow q \wedge \sim q)$$

 

흡수법칙(Absorption Laws)
$$p \wedge (p \vee r) \equiv p \\ p \vee (p \wedge q) \equiv p$$

 

이출법칙(Exportation Law)
$$p \wedge q \rightarrow r \equiv p \rightarrow (q \rightarrow r)$$