論理式 - mrsekut-p

論理式

命題論理式のこと

式なのでこれ自体も1か0になる

帰納的に定義される

定義

以下の規則から生成される式のみを論理式という

無限個ある

T, Fの二値

$ \varphi,\psiが論理式ならば、$ \lnot\varphi、$ \varphi\land\psi、$ \varphi\lor\psi、$ \varphi\rightarrow\psiも論理式

BNF記法を用いた論理式の定義

code:bnf

A ::= 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は素数である ref p.1

$ (x \geq 2) \wedge(\forall y .((y \geq 1) \Rightarrow((\exists z,(x=y z))) \Rightarrow((y=1) \vee(y=x)))))

「素数は無限に存在する」

どんなMを考えてもMより大きい素数がある