論理式
命題論理式のこと
式なのでこれ自体も1か0になる
帰納的に定義される
定義
以下の規則から生成される式のみを論理式という
無限個ある
T, Fの二値
\varphi,\psiが論理式ならば、\lnot\varphi、\varphi\land\psi、\varphi\lor\psi、\varphi\rightarrow\psiも論理式
bnfA ::= P | T | F | ¬A | A∧A | A∨A | A→A
以下の問題を論理式で表す
「Oは最小の自然数である」を論理式で示すと
\forall x\in\mathrm{N}\;(x=O\lor O\lt x)
「最小の自然数が存在する」
\exist y\forall x\in\mathrm{N}(y=x\lor y\lt x) v
(x \geq 2) \wedge(\forall y .((y \geq 1) \Rightarrow((\exists z,(x=y z))) \Rightarrow((y=1) \vee(y=x)))))
「素数は無限に存在する」
どんなMを考えてもMより大きい素数がある