일반화된 드모르간 법칙과 분배 법칙

임의 개수의 항에 대한 법칙

의미론적 귀결과 동치 수업에서는 두 항에 대한 동치 법칙들을 세웠다. 그 가운데에는 $\wedge$와 $\vee$의 교환 법칙과 결합 법칙, 드모르간 법칙, 두 분배 법칙이 있다. 그런데 선언 표준형의 논리식은 연언들의 선언이고, 각 연언은 필요한 만큼의 항을 가진다. 논리식을 이 형태로 바꾸려면 임의 길이의 연언과 선언을 부정하고, 다시 묶고, 분배해야 한다. 그렇다면 두 항의 법칙은 그대로는 충분하지 않다. 이를 $n$개의 항으로 확장해야 하며, 그것도 모든 $n$에 대해 한꺼번에 확장해야 한다.

고정된 각 $n$에 대해, $n$개 항의 드모르간 법칙은 $2^n$개의 행을 가진 진리표($n$개의 변항으로 쓰인다)로 검증할 수 있고, 앞 수업의 균일 대입을 양변 사이의 쌍조건에 적용하면 임의의 논리식으로 확장된다. 그러나 $n$의 값은 무한히 많으며, 아무리 많은 표로도 그것들을 다 할 수 없다. 이로부터 “모든 $n$에 대해”라는 주장은 두 논리식 사이의 동치가 아니라 무한히 많은 동치에 관한 진술이며, 메타언어로 정식화된 것임이 따라 나온다. 그 증명은 자연수와 논리식에 관한 귀납법 수업의 증명들처럼 외부의 증명이며, 그 도구는 항의 개수에 관한 귀납법이다. 표기 $\bigwedge_{i=1}^{n} \varphi_i$ 역시 메타언어에 속한다. 그것은 언어의 새 기호가 아니라 흰 원과 검은 원으로 된 기호열의 이름이며, $(\varphi \wedge \psi)$의 경우와 마찬가지이다.

여기서 혼동해서는 안 되는 세 관계를 정해 두자. 등식 $\alpha = \beta$는 $\alpha$와 $\beta$가 같은 기호열임을 말한다. 정의는 $:=$로 쓰며 기호열에 이름을 붙인다. 정의를 펼쳐서 얻는 것은 같은 것이지, 단지 동치인 것이 아니다. 의미론적 동치 $\alpha \eqsem \beta$는 $v(\alpha) = v(\beta)$가 모든 진리값 할당 $v$에 대해 성립함을 말한다. 연역 단원의 증명 가능한 동치 $\alpha \dashv\vdash \beta$는 두 논리식 각각이 다른 하나로부터 연역됨을 말한다. 이 수업은 앞의 두 관계를 다루며, 세 번째는 한 주석에만 나타난다.

사용하는 것

명제 논리의 의미론 수업에서는 다음을 가져온다. 진리값 할당, 즉 변항 $v_1, v_2, \ldots$에서 $\{0, 1\}$로 가는 함수와 그것의 모든 논리식으로의 확장(같은 문자 $v$로 쓴다). 공식 약어로부터 계산한 파생 연결사의 값 $v(\neg\varphi) = 1 - v(\varphi)$, $v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi)$(따라서 연언이 값 $1$을 가질 필요충분조건은 두 성분이 모두 값 $1$을 가지는 것이고, $v((\varphi \vee \psi)) = 1$일 필요충분조건은 $v(\varphi) = 1$ 또는 $v(\psi) = 1$인 것이다). 일치 보조정리(두 진리값 할당이 어떤 논리식의 변항들에서 일치하면 그 논리식에서도 일치한다). 그리고 논리식 $\top$와 $\bot$, 즉 고정된 항진식과 고정된 모순식. 의미론적 귀결과 동치 수업에서는 다음을 가져온다. $\eqsem$가 반사적이고 대칭적이며 추이적이라는 것, 의미론적 대체 정리, 그리고 이름 붙은 법칙들의 목록이다. 교환 법칙 $(\varphi \wedge \psi) \eqsem (\psi \wedge \varphi)$와 $(\varphi \vee \psi) \eqsem (\psi \vee \varphi)$, 결합 법칙 $(\varphi \wedge (\psi \wedge \chi)) \eqsem ((\varphi \wedge \psi) \wedge \chi)$ 및 $\vee$에 대한 같은 꼴의 법칙, 드모르간 법칙 $\neg(\varphi \wedge \psi) \eqsem (\neg\varphi \vee \neg\psi)$와 $\neg(\varphi \vee \psi) \eqsem (\neg\varphi \wedge \neg\psi)$, 분배 법칙 $(\varphi \wedge (\psi \vee \chi)) \eqsem ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$와 $(\varphi \vee (\psi \wedge \chi)) \eqsem ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$, 이중 부정 $\neg\neg\varphi \eqsem \varphi$, 멱등 법칙 $(\varphi \vee \varphi) \eqsem \varphi$, 항등 법칙 $(\varphi \wedge \top) \eqsem \varphi$, 그리고 배중률 $\models (\varphi \vee \neg\varphi)$. 이 법칙들은 임의의 논리식 $\varphi$, $\psi$, $\chi$에 대해 성립하며, 이것들은 메타변항이다.

이어지는 증명의 각 단계에서는 논리식의 한 부분을 그것과 동치인 다른 부분으로 바꾼다. 의미론적 대체 정리는 이를 한 번에 한 출현에 대해 허용한다. 다음 보조정리는 그 특수한 경우로서, 부정, 연언, 선언의 각 부분에 대해 이를 한꺼번에 준다. 이것이 구문상 자명한 일이 아니라는 점에 주의해야 한다. $\neg\alpha$는 기호열 $(\alpha \downarrow \alpha)$이며, 그 안에 $\alpha$는 두 번 나타난다. 따라서 $(\alpha \wedge \beta)$는 $\alpha$의 출현을 여덟 개, $\beta$의 출현을 여덟 개 포함한다.