1.1 Propositional Logic
Propositional Logic(명제 논리)에서 말하길, proposition(명제)이란 atomic formula(원자식)를 말하는 것.
예를 들어 다음은 모두 atomic formula.
\[A = ``\textrm{17 is a prime number.”}\] \[B = ``\textrm{Korea belongs to Europe.”}\] \[C = ``\textrm{Mike got a good score on the math test.”}\]
Atomic formula는 sentence(문장)을 구성하는 벽돌이라고 생각할 수 있다. Propositional logic에서 sentence(문장)과 formula(논리식)는 같은 의미.
Propositional logic에서 각각의 sentence는 true(참)이거나 false(거짓)이며, 이에 따라 1 또는 0의 truth value(진릿값)이 할당된다. 위 예시에서 A에 할당되는 진릿값은 1, B에 할당되는 진릿값은 0이 된다.
C의 경우는…참인지 아닌지 논란의 여지가 있다.1
Propositional logic에서 명제의 내용은 신경쓰지 않는다. 원자식은 그저 알파벳 대문자 $A$, $B$, $C$로 나타낸다. 명제 논리는 참이라고 생각되는 한 명제와 다른 명제 사이에 어떤 관계가 있는지에만 관심이 있다.
다음은 propositional logic에서 쓰이는 단어를 symbol(기호)로 표현한 것. 우리가 일상생활에서 사용하는 언어로 표현하자면 대략,
\[\neg : \textrm{not}\] \[\wedge : \textrm{and}\] \[\vee : \textrm{or}\] \[\rightarrow : \textrm{implies}\] \[\leftrightarrow : \textrm{if and only if(iff)}\]
사실, 약간의 차이는 있다. $\vee$는 “or”과 비슷하지만 완전히 동일하지는 않다. 일상 언어에서 ‘$A$ or $B$’는 $A$와 $B$ 양쪽의 가능성이 모두 있다는 걸 의미하지만, 명제 논리에서 atomic formula $A$, $B$에 대해 $A \vee B$는 ‘either $A$ or $B$’, ‘both $A$ or $B$’라는 뜻이다. 마찬가지로 $\wedge$도 ‘and’랑은 조금 다르다.
위 기호들을 정확히 정의해야 하는데… 아무것도 없는 상태에서 첫 번째 단어를 정의할 수는 없는 노릇이다. 이중에서 두 기호, $\neg$, $\wedge$를 골라 primitive symbols(원시 기호)로 삼자. 나머지 기호들은 이 둘만으로 정의된다.
먼저 우리에게 필요한 것은 syntax(구문론), 즉 문법이다.
Syntax of Propositional Logic
당연히, 임의의 atomic formula는 formula. 우리에게는 다음 두 규칙이 있다.
\[\textrm{(R1) If } F\textrm{ is a formula, then }\neg F\textrm{ is a formula.}\]
\[\textrm{(R2) If } F\textrm{ and }G\textrm{ are formulas, then } F\wedge G\textrm{ is a formula.}\]
Definition 1.1.1
Formula $\neg F$는 $F$의 negation(부정)이고, formula ($F\wedge G$)는 $F$와 $G$의 conjunction(연언)이다.
Definition 1.1.2
Atomic formula들에 규칙 $\textrm{(R1)}$, $\textrm{(R2)}$를 반복적으로 사용해 만들어진 기호들의 finite string을 명제 논리의 formula라고 한다.
Example 1.1.3
$\neg(\neg(A \wedge B) \wedge \neg C)$는 formula지만, $(( A \neg \wedge)B(C\neg$은 formula가 아니다.
이것으로 formula의 정의가 $\neg$, $\wedge$만으로 한정되었다. 다음 관습은 가독성을 위해 만들어졌다.
\[\textrm{(C1) If } F\textrm{ or } (F)\textrm{ is a formula, then we view }F\textrm{ and }(F)\textrm{ as the same formula.}\]
즉 제일 바깥에 있는 괄호는 무시해도 된다는 의미. 따라서 엄밀히 말하면 $A \wedge B$는 formula가 아니다. $(C1)$을 적용해야 $A \wedge B$는 $(A \wedge B)$와 같게 된다.
이 다음 순서는 subformula의 정의. Formula $F$의 subformula는 스스로 formula가 되는 $F$의 substring.
그런데, $\textrm{(C1)}$으로부터 약간 애매한 점이 생겨나게 된다. $F$가 $A \wedge B$를 나타낸다고 하자. 3 그러면, $\neg F$는 $\neg(A \wedge B)$가 아니라 $\neg A \wedge B$를 나타내게 된다. 물론 이 둘은 의미가 다르다. 게다가 substring들이 모두 subformula가 되지도 않는다. $F \wedge G$는 $(F) \wedge (G)$와 같은데, 그럼 $F) \wedge G($도 formula란 말인가?
결국, $\textrm{(C1)}$ 때문에 다른 정의가 필요하다.
Definition 1.1.4
다음 규칙에 의해 formula의 subformula들을 정의.
- 임의의 formula는 자기 자신의 subformula이다.
- $F$의 임의의 subformula는 $\neg F$의 subformula이기도 하다.
- $F$ 또는 $G$의 임의의 subformula는 $F \wedge G$의 subformula이기도 하다.
Example 1.1.5
$A$, $B$ 를 atomic, $F$ 를 formula $\neg(\neg A \wedge \neg B)$라고 하자.
Formula $A \wedge \neg B$는 $F$의 substring이나, $F$의 subformula는 아니다.
$F$의 subformula들은 $A$, $B$, $\neg A$, $\neg B$, $(\neg A \wedge \neg B)$, $\neg(\neg A \wedge \neg B)$이다.
Semantics of Propositional Logic
명제 논리의 semantics(의미론)은 다음 진리표에 의해 정의된다.
| \[A\] | \[B\] | \[A \wedge B\] |
|---|---|---|
| \[0\] | \[0\] | \[0\] |
| \[0\] | \[1\] | \[0\] |
| \[1\] | \[0\] | \[0\] |
| \[1\] | \[1\] | \[1\] |
| \[A\] | \[\neg A\] |
|---|---|
| \[0\] | \[1\] |
| \[1\] | \[0\] |
”$\neg$”와 “$\wedge$”의 의미가 정의된다. $\wedge$의 진리표 두 번째 행은 $A$가 거짓이고 $B$가 참인 경우 ($A \wedge B$)가 거짓이 된다고 해석할 수 있다. Table 1.1.2에서 보면 $\neg A$는 $A$의 반대 진릿값을 가진다.
이 두 진리표로부터 어떤 formula든 진리표를 그려낼 수 있다. 모든 formula는 atomic formula와 규칙 $\textrm{(R1)}$, $\textrm{(R2)}$로부터 만들어지니까!
위 두 진리표를 이용해 이번에는 Example 1.1.5의 formula $\neg(\neg A \wedge \neg B)$의 진리표를 만들어 보자. 이는 $(\neg A \wedge \neg B)$와 반대 진릿값을 가질 것이고, 이는 $\neg A \wedge \neg B$와 같은데… 맨 앞의 “$\neg$”는 어디에 붙어 있는 거지?
Rule 1.1.6
Formula에 괄호가 존재하지 않을 경우, $\neg$는 $\wedge$에 선행한다.
Rule 1.1.6은 order of operation(연산 순서)를 말해준다. “$\neg$”와 “$\wedge$”의 정의와 더불어 formula의 해석에 꼭 필요하다. 이에 따르면,
\[\neg (A \wedge \neg B) =``\textrm{ not both }A\textrm{ and not }B” \]
\[\neg A \wedge \neg B =``\textrm{ both not }A\textrm{ and not }B” \]
이제 $\neg(\neg A \wedge \neg B)$의 진리표를 그릴 수 있다.
| \[A\] | \[B\] | \[\neg A\] | \[\neg B\] | \[(\neg A \wedge \neg B)\] | \[\neg(\neg A \wedge \neg B)\] |
|---|---|---|---|---|---|
| \[0\] | \[0\] | \[1\] | \[1\] | \[1\] | \[0\] |
| \[0\] | \[1\] | \[1\] | \[0\] | \[0\] | \[1\] |
| \[1\] | \[0\] | \[0\] | \[1\] | \[0\] | \[1\] |
| \[1\] | \[1\] | \[0\] | \[0\] | \[0\] | \[1\] |
위 table에 따르면, $\neg(\neg A \wedge \neg B)$는 $A$와 $B$가 모두 진릿값 0을 가질 때 진릿값 0을 가지며, 그 외의 경우에는 진릿값 1을 가진다. 이는 우리가 생각하는 “or”과 일치. 따라서, 이를 $\vee$로 정의하면 좋을 것이다.
Definition 1.1.7
기호 $\vee$를 다음과 같이 정의:
임의의 formula $F$, $G$에 대해, $(F \vee G)$를 $\neg(\neg A \wedge \neg B)$로 정의한다. Formula $(F \vee G)$를 $F$와 $G$의 disjunction(선언)이라고 한다.
나머지 두 기호들도 정의.
Definition 1.1.8
임의의 formula $F$, $G$에 대해:
$(F \rightarrow G)$를 $(G \vee \neg F)$,
$(F \leftrightarrow G)$를 $((F\rightarrow G)\wedge (G\rightarrow F))$로 정의한다.
| \[A\] | \[B\] | \[\neg A\] | \[(B \vee \neg A)\] | \[(A \rightarrow B)\] |
|---|---|---|---|---|
| \[0\] | \[0\] | \[1\] | \[1\] | \[1\] |
| \[0\] | \[1\] | \[1\] | \[1\] | \[1\] |
| \[1\] | \[0\] | \[0\] | \[0\] | \[0\] |
| \[1\] | \[1\] | \[0\] | \[1\] | \[1\] |
$(A \rightarrow B)$는 $A$가 참이고 $B$가 거짓이 아니면 모조리 거짓. 특히 $A$가 거짓인 경우에는 반드시 참이 된다. 심지어는, $A$가 거짓이면 $(A \rightarrow \neg A)$조차도 참. 즉, 논리적으로 말하자면 거짓 명제는 아무 내용이나 imply(함의)하게 된다. 이것이 일상 언어와의 차이.
$(A \leftrightarrow B)$는 $A$와 $B$가 같은 진릿값을 가질 때 참, 나머지에서는 거짓.
이제 이 기호들의 순서를 결정한다. 단 하나의 규칙만 있으면 된다.
Rule 1.1.9
$\neg$는 $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$에 선행한다.2
Example 1.1.10
다음 formula를 생각.
\[F=((\neg A \rightarrow B)\wedge C)\vee \neg (A \wedge D)\]
$A$, $B$, $C$, $D$의 진릿값이 1, 0, 1, 0일 때 $F$의 진릿값을 구해 보자. 먼저 $\neg$는 다른 기호에 선행하므로, subformula $\neg A$부터 시작한다. 그 다음 가장 안쪽 괄호 $(\neg A \rightarrow B)$를 해석하고…
| \[A\] | \[B\] | \[C\] | \[D\] | \[\neg A\] | \[(\neg A \rightarrow B)\] | \[((\neg A \rightarrow B)\wedge C)\] | \[(A \wedge D)\] | \[\neg (A \wedge D)\] | \[F\] |
|---|---|---|---|---|---|---|---|---|---|
| \[1\] | \[0\] | \[1\] | \[0\] | \[0\] | \[1\] | \[1\] | \[0\] | \[1\] | \[1\] |
이는 formula의 진리표 중 한 행을 나타낸 것뿐. 이 formula에는 $A$, $B$, $C$, $D$ 4개의 atomic formula가 포함되어 있으므로, 이들의 참·거짓에 따라 $2^{4}=16$가지 진릿값을 할당할 수 있다. 즉 전체 진리표는 16행.
괄호는 연산 순서를 결정할 뿐만 아니라 formula의 가독성을 높이는 역할을 한다. $\textrm{(C1)}$에서 우리는 가장 바깥쪽 괄호만을 생각했다. 하나 더 추가.
\[\textrm{(C2) For any formulas } F, G,\textrm{ and } H,\]
\[\textrm{we view }F \wedge G \wedge H \textrm{ as the same formula as }(F \wedge G) \wedge H \\ \textrm{and }F \vee G \vee H \textrm{ as the same formula as }(F \vee G) \vee H.\]
Formula $(F \wedge G) \wedge H$와 $F \wedge (G \wedge H)$는 같은 진리표를 가지므로, 괄호를 떼어내고 간단히 $F \wedge G \wedge H$로 쓸 수 있다. 그러나 $F \wedge G \vee H$는 제대로 된 명제 논리의 formula로 볼 수 없는데, $(F \wedge G) \vee H$와 $F \wedge (G \vee H)$가 각기 다른 진리표를 갖기 때문.