명제논리(propositional logic)는 명제변수와 논리결합자, 그리고 공리와 추론규칙으로 이루어진 형식논리의 한 체계이다. 1장에서는 명제와 논리연산을 직관적으로 다루었다. 이 장에서는 같은 대상을 문자열과 형식적 증명의 관점에서 다시 다룬다.
1. 구문론
구문론(syntax)은 주어진 기호로 어떤 문자열을 논리식으로 인정할 것인지 정하는 규칙을 다룬다. 구문론에서는 문자열의 의미나 진릿값을 따지지 않고 기호의 형식만을 고려한다.
가산 개의 명제변수(propositional variable) \[\{p_0,p_1,p_2,\ldots\}\] 가 주어졌다고 하자. 이 장의 형식추론계에서는 부정기호 \(\neg\)와 함의기호 \(\to\)를 기본 결합자로 사용한다. 괄호도 논리식을 만드는 기호로 사용한다.
명제논리의 논리식은 다음 규칙을 사용하여 재귀적으로 정의한다.
- 모든 명제변수는 논리식이다.
- \(\phi\)가 논리식이면 \((\neg\phi)\)도 논리식이다.
- \(\phi\)와 \(\psi\)가 논리식이면 \((\phi\to\psi)\)도 논리식이다.
- 위 규칙을 유한 번 적용하여 얻은 것만 논리식이다.
논리곱, 논리합, 양방향 함의는 다음 약어로 사용한다. \[ \begin{aligned} (\phi\wedge\psi)&:=\neg(\phi\to\neg\psi),\\[3pt] (\phi\vee\psi)&:=(\neg\phi\to\psi),\\[3pt] (\phi\leftrightarrow\psi)&:=((\phi\to\psi)\wedge(\psi\to\phi)). \end{aligned} \] 따라서 \(\wedge,\vee,\leftrightarrow\)를 포함한 식은 위 약어를 풀면 \(\neg,\to\)만을 사용한 논리식이 된다. 이 선택은 뒤에서 사용할 공리틀 (A1)–(A3)과 언어를 일치시키기 위한 것이다.
어떤 유한한 문자열이 논리식인지 여부는 위의 재귀적 문법을 따라 유한한 절차로 판별할 수 있다. 이러한 논리식을 well-formed formula, 줄여서 wff라고 부르기도 한다.
문제 12.1. 위의 재귀적 정의를 문자 그대로 적용하여 다음 질문에 답하시오.
- 다음 문자열이 논리식인지 판정하시오. \[ p_0, \quad (\neg p_0), \quad (p_0\to p_1), \quad (p_0\,p_1), \quad ((p_0\to p_1)), \quad (p_0\to). \]
- 논리식 \[ \phi=((p_0\to(\neg p_1))\to(p_2\to p_0)) \] 의 가장 바깥쪽 결합자와 그 결합자의 두 직접 부분논리식을 찾으시오.
- \((p_0\wedge p_1)\vee p_2\)에서 \(\wedge,\vee\)를 정의에 따라 없애고 \(\neg,\to\)만을 사용하여 나타내시오.
2. 의미론
구문론이 논리식의 형식만을 다룬다면, 의미론(semantics)은 명제변수에 진릿값을 부여했을 때 복합논리식의 진릿값이 어떻게 결정되는지를 다룬다.
명제변수 각각에 \(\mathrm T\) 또는 \(\mathrm F\)를 대응시키는 함수를 먼저 정하자. 이 함수는 다음 재귀규칙에 의하여 모든 논리식에 유일하게 확장된다. 이렇게 확장된 함수를 값매김(valuation) \(v\)라고 한다. \[ \begin{aligned} v(\neg\phi)=\mathrm T &\quad\Longleftrightarrow\quad v(\phi)=\mathrm F,\\ v(\phi\to\psi)=\mathrm F &\quad\Longleftrightarrow\quad v(\phi)=\mathrm T\text{이고 }v(\psi)=\mathrm F. \end{aligned} \] 약어로 정의한 나머지 결합자의 진릿값은 다음 진리표와 같다.
모든 값매김 \(v\)에 대하여 \(v(\phi)=\mathrm T\)이면 \(\phi\)를 항진(tautology)이라고 부른다. 모든 값매김에 대하여 \(v(\phi)=\mathrm F\)이면 \(\phi\)를 모순(contradiction)이라고 부른다.
논리식의 집합 \(\varSigma\)에 대하여, 어떤 값매김 \(v\)가 모든 \(\sigma\in\varSigma\)에 대하여 \(v(\sigma)=\mathrm T\)를 만족시키면 \(v\)를 \(\varSigma\)의 모형(model)이라고 부른다. 이러한 값매김이 하나라도 존재하면 “\(\varSigma\)가 만족 가능(satisfiable)하다”라고 표현한다. 한 논리식 \(\phi\)가 만족 가능하다는 것은 \(\{\phi\}\)가 만족 가능하다는 뜻이다.
모든 \(\varSigma\)의 모형 \(v\)에 대하여 \(v(\phi)=\mathrm T\)이면 \(\phi\)를 \(\varSigma\)의 논리적 귀결(logical consequence)이라고 부르고 \[ \varSigma\models\phi \] 로 나타낸다. \(\varSigma=\varnothing\)이면 \[ \models\phi \] 는 정확히 \(\phi\)가 항진이라는 뜻이다.
문제 12.2. 값매김 \(v\)가 \[ v(p)=\mathrm T,\quad v(q)=\mathrm F,\quad v(r)=\mathrm T \] 를 만족시킨다고 하자.
- 다음 진릿값을 각각 구하시오. \[ v(\neg p),\quad v(p\to q),\quad v((p\to q)\to r),\quad v((p\wedge r)\vee q). \]
- 다음 논리식을 항진, 모순, 그 어느 것도 아닌 것으로 분류하시오. \[ p\to p, \quad p\wedge\neg p, \quad p\to q, \quad (p\to q)\vee(q\to p). \]
문제 12.3. 논리적 귀결의 정의를 사용하여 다음을 판정하시오. 성립하지 않으면 반례가 되는 값매김을 하나 제시하시오.
- \(\{p,p\to q,q\to r\}\models r\).
- \(\{p\vee q\}\models p\).
- \(\{p\to q\}\models\neg q\to\neg p\).
- \(\{p,p\to q,\neg q\}\)는 만족 가능한가?
3. 형식추론계
이제 명제논리의 형식추론계(formal deduction system)를 정한다. 먼저 다음 세 공리틀(axiom scheme)을 사용한다.
(A1) \(\phi\to(\psi\to\phi)\)
(A2) \((\phi\to(\psi\to\theta))\to((\phi\to\psi)\to(\phi\to\theta))\)
(A3) \((\neg\phi\to\neg\psi)\to(\psi\to\phi)\)
여기서 \(\phi,\psi,\theta\)는 임의의 논리식이다. 이들을 임의의 논리식으로 치환하여 얻는 모든 식을 공리라고 한다.
추론규칙은 다음 하나뿐이다. \[ \frac{\phi\quad \phi\to\psi}{\psi}\quad(\mathrm{MP}) \] 이를 modus ponens, 줄여서 MP라고 나타낸다.
11장에서 정의한 증명과 정리의 개념을 이 형식추론계에 적용한다. 따라서 명제논리의 증명은 유한한 논리식의 열이며, 각 항은 공리이거나 앞의 항들에 MP를 적용하여 얻어진다.
논리식의 집합 \(\varSigma\)가 주어졌을 때에는 공리뿐 아니라 \(\varSigma\)의 원소도 증명의 출발점으로 허용한다. 마지막 논리식이 \(\phi\)인 이러한 증명이 존재하면 \[ \varSigma\vdash\phi \] 로 나타낸다. 이때 \(\varSigma\)를 가정 집합이라 한다. 특히 \(\varSigma=\varnothing\)이면 \[ \vdash\phi \] 로 쓰며, \(\phi\)는 명제논리의 정리이다.
문제 12.4. 공리틀과 MP를 직접 적용하여 다음 질문에 답하시오.
- 다음 각 논리식이 (A1), (A2), (A3) 중 어느 공리틀에 해당하는지 판정하시오. 어느 것도 아니면 그렇게 답하시오. \[ \begin{aligned} &p\to(q\to p),\\[3pt] &(p\to(q\to r))\to((p\to q)\to(p\to r)),\\[3pt] &(\neg(p\to q)\to\neg r)\to(r\to(p\to q)),\\[3pt] &p\to(q\to q). \end{aligned} \]
- \(\varSigma=\{p,\;p\to q,\;q\to r\}\)이라고 하자. \(\varSigma\vdash r\)임을 보이는 증명을 쓰고, 각 MP가 어느 두 앞선 논리식에 적용되었는지 밝히시오.
4. 증명 예제
정리 12.1.
임의의 논리식 \(p\)에 대하여 \(p\to p\)는 명제논리의 정리이다.
증명 다음은 길이가 5인 증명이다.
\[ \begin{aligned} &\vdash (p\to((p\to p)\to p))\to((p\to(p\to p))\to(p\to p)) &&\text{(A2)},\\[3pt] &\vdash p\to((p\to p)\to p) &&\text{(A1)},\\[3pt] &\vdash (p\to(p\to p))\to(p\to p) &&\text{(MP)},\\[3pt] &\vdash p\to(p\to p) &&\text{(A1)},\\[3pt] &\vdash p\to p &&\text{(MP)}. \end{aligned} \]
첫째 식과 둘째 식에 MP를 적용하여 셋째 식을 얻고, 셋째 식과 넷째 식에 MP를 적용하여 마지막 식을 얻는다.
다음 메타정리는 가정을 함의의 앞부분으로 옮길 수 있음을 보여 준다.
정리 12.2. (추론 정리)
\(\varSigma\cup\{\psi\}\vdash\phi\)이면 \(\varSigma\vdash\psi\to\phi\)이다.
증명 \(\varSigma\cup\{\psi\}\)로부터의 \(\phi\)의 증명을 \[ \phi_1,\phi_2,\ldots,\phi_n=\phi \] 라 하자. 각 \(i\)에 대하여 \(\varSigma\vdash\psi\to\phi_i\)임을 \(i\)에 대한 귀납법을 사용하여 보인다.
\(\phi_i\)가 공리이거나 \(\varSigma\)의 원소이면 \(\varSigma\vdash\phi_i\)이다. (A1)의 \[ \phi_i\to(\psi\to\phi_i) \] 와 MP를 사용하면 \(\varSigma\vdash\psi\to\phi_i\)이다. \(\phi_i=\psi\)이면 정리 12.1에 의하여 \(\varSigma\vdash\psi\to\psi\)이다.
마지막으로 \(\phi_i\)가 앞선 두 식 \(\phi_j\)와 \(\phi_j\to\phi_i\)에 MP를 적용하여 얻어졌다고 하자. 귀납가정에 의하여 \[ \varSigma\vdash\psi\to\phi_j, \quad \varSigma\vdash\psi\to(\phi_j\to\phi_i) \] 이다. (A2)에서 문자를 바꾼 식 \[ (\psi\to(\phi_j\to\phi_i)) \to((\psi\to\phi_j)\to(\psi\to\phi_i)) \] 에 MP를 두 번 적용하면 \(\varSigma\vdash\psi\to\phi_i\)를 얻는다. 특히 \(i=n\)일 때 원하는 결론이 따른다.
추론 정리를 사용하는 예로 \[ \vdash\neg\phi\to(\phi\to\psi) \] 를 보이자. \(\{\neg\phi\}\)를 가정 집합으로 두면 \[ \begin{aligned} \{\neg\phi\}&\vdash \neg\phi\to(\neg\psi\to\neg\phi) &&\text{(A1)},\\[3pt] \{\neg\phi\}&\vdash \neg\phi &&\text{(가정)},\\[3pt] \{\neg\phi\}&\vdash \neg\psi\to\neg\phi &&\text{(MP)},\\[3pt] \{\neg\phi\}&\vdash (\neg\psi\to\neg\phi)\to(\phi\to\psi) &&\text{(A3)},\\[3pt] \{\neg\phi\}&\vdash \phi\to\psi &&\text{(MP)}. \end{aligned} \] 따라서 추론 정리에 의하여 \(\vdash\neg\phi\to(\phi\to\psi)\)이다.
문제 12.5. \(\varSigma=\{p\to q,\;q\to r\}\)라 하자.
- \(\varSigma\cup\{p\}\vdash r\)임을 MP만 사용하여 보이시오.
- 추론 정리를 사용하여 \(\varSigma\vdash p\to r\)임을 보이시오.
- 추론 정리를 두 번 더 적용하여 \[ \vdash (p\to q)\to((q\to r)\to(p\to r)) \] 임을 보이시오.
문제 12.6. 이 절의 명제논리 형식추론계를 변형한다고 하자. 다음 질문에 답하시오.
- (A1)–(A3)을 모두 제거하고 MP만 남기면 어떤 정리를 증명할 수 있는가?
- MP를 제거하고 (A1)–(A3)만 남기면 어떤 정리를 증명할 수 있는가?
- 모든 논리식이 정리가 되는 형식계를 하나 제시하시오.