의미론적 귀결과 동치

앞 수업에서 쓰는 것

명제 논리의 의미론 수업은 논리식에 의미를 주었고, 이 수업은 그것을 이미 아는 것으로 한다. 진리값 할당이란 함수 $v\colon V \to \{0, 1\}$을 말하며, 이 함수는 각 변항에 진리값 $1$(참) 또는 $0$(거짓)을 배정한다. 귀납법 수업의 논리식 위의 재귀에 의한 정의 정리에 의해, 각 진리값 할당은 부정논리합의 조항으로 모든 논리식에 오직 한 가지 방식으로 확장된다. 이 조항 하나만 있으면 되는데, 이 언어에는 연결사가 하나뿐이기 때문이다.

확장의 유일성에 의해, 확장의 값도 $v(\varphi)$로 쓴다. 아래첨자 없는 문자 $v$는 언제나 진리값 할당을 나타내고($v'$, $w$, $u$도 다른 할당을 나타낸다), 변항은 언제나 아래첨자를 단다. 형식화 수업에서와 같이, $p$, $q$, $r$, $s$, $t$는 변항 $v_1$부터 $v_5$까지를 나타내고, $V(\varphi)$는 $\varphi$의 변항들의 집합이다. $v$가 $\varphi$를 충족한다고 하며 $v \models \varphi$로 쓴다. 이것은 $v(\varphi) = 1$일 때이다. 또 그 할당이 이 논리식을 반박한다고 하며 $v \not\models \varphi$로 쓴다. 이것은 $v(\varphi) = 0$일 때이다. 논리식이 타당하다(또는 항진식이다)는 것은 모든 진리값 할당이 그것을 충족한다는 것이며, 이때 $\models \varphi$로 쓴다. 충족 가능하다는 것은 어떤 할당이 그것을 충족한다는 것이고, 충족 불가능하다(또는 모순식이다)는 것은 어떤 할당도 그것을 충족하지 않는다는 것이며, 우연식이라는 것은 충족 가능하지만 타당하지 않다는 것이다. 진리값 할당이 논리식 집합 $\Gamma$를 충족한다($v \models \Gamma$)는 것은 그 각 원소를 충족한다는 것이며, 어떤 할당이 $\Gamma$를 충족하면 그 집합은 충족 가능, 그렇지 않으면 충족 불가능하다고 한다. 끝으로, $\top := (v_1 \rightarrow v_1)$, $\bot := \neg\top$로 둔다. 따라서 모든 진리값 할당에 대해 $v(\top) = 1$이고 $v(\bot) = 0$이다.

그 수업에서는 결과 두 가지를 더 쓴다. 첫째는 일치 보조정리이다. 두 진리값 할당이 $\varphi$의 변항들에서 일치하면, 두 할당은 $\varphi$에서도 일치한다. 이에 따라 $n$개의 변항을 가진 논리식의 값은 $2^{n}$이지 조합에만 의존하고, 그 진리표는 유한하다. 둘째는 파생 연결사의 값에 관한 정리로, 공식 약어로부터 각 연결사의 값을 성분들의 값의 다항식으로 계산한다. $a = v(\varphi)$이고 $b = v(\psi)$이라 하면:

이 수업의 증명은 거의 모두 진리값의 비교로 이루어지며, 이 다항식들 덕분에 경우를 하나씩 살피는 대신 계산으로 비교할 수 있다. 추가 규칙은 하나뿐인데, $0$과 $1$만이 자기 제곱과 같은 수라는 것이다. $x$의 값이 $0$ 또는 $1$이면 $x^{2} = x$이고 $x(1 - x) = 0$이다. 또한 같은 값의 다른 세 표기를 곁에 두면 좋다. 이것들은 곱을 전개해서 얻는다.

첫째는 부정논리합의 조항이다($1 - a$와 $1 - b$의 곱이 $1$이 되는 것은 정확히 $a = b = 0$일 때이다). 둘째는 선언이 $0$이 되는 것은 두 성분이 모두 $0$일 때뿐임을 말하고, 셋째는 쌍조건이 $1$이 되는 것은 $a = b$일 때($1 - 2a + 2a^{2} = 1$이므로), $0$이 되는 것은 $a \neq b$일 때(이때 $a + b = 1$이고 $ab = 0$이므로)임을 말한다.