一階述語論理
項が何らかの対象を表す記号列であったのに対して、論理式は何らかの命題を表すものである。論理式は原子論理式と呼ぶ最も基本的な論理式から結合記号と量化記号を繰り返し用いることによって形成される。まず、原子論理式は次のように定義される:
ある正の整数 n {\displaystyle n} に対するアリティ n {\displaystyle n} の述語記号 P {\displaystyle P} と n {\displaystyle n} 個の項 t 1 , ⋯ , t n {\displaystyle t_{1},\,\cdots ,\,t_{n}} を用いて P ( t 1 , ⋯ , t n ) {\displaystyle P(t_{1},\,\cdots ,\,t_{n})} と表される記号列を原子論理式 (atomic formula) と呼ぶ。
原子論理式を用いて、論理式 (well-formed formula, wff) あるいは式 (formula) は次のように帰納的に定義される:
原子論理式は論理式である。
φ {\displaystyle \phi } と ψ {\displaystyle \psi } が論理式ならば、 ( ¬ φ ) {\displaystyle (\lnot \phi )} , ( φ ∧ ψ ) {\displaystyle (\phi \land \psi )} , ( φ ∨ ψ ) {\displaystyle (\phi \lor \psi )} , ( φ ⇒ ψ ) {\displaystyle (\phi \Rightarrow \psi )} , ( φ ⇔ ψ ) {\displaystyle (\phi \Leftrightarrow \psi )} は論理式である。
次に、論理式 φ において項 t が変数 x に代入可能であるということを定義する。このことの直観的な意味は、φ が x について述べていることと同じことを φx [ t ] が t について述べているということである。例えば、。これに対して、。 代入可能性の正式な定義は次の通りである。
論理式 φ において項 t が変数 x に代入可能 (substitutable) であるということを次のように再帰的に定義する: 原子論理式においては、常に t は x に代入可能である。 (¬ φ) において t が x に代入可能 ⇔ φ において t が x に代入可能 。 (φ ∧ ψ) において t が x に代入可能 ⇔ φ と ψ において t が x に代入可能 。 (φ ∨ ψ) において t が x に代入可能 ⇔ φ と ψ において t が x に代入可能 。 (φ → ψ) において t が x に代入可能 ⇔ φ と ψ において t が x に代入可能 。 (φ ↔ ψ) において t が x に代入可能 ⇔ φ と ψ において t が x に代入可能 。 ∀y φ において t が x に代入可能 ⇔ x ≠ y または x ∉ fr(φ) または(φ において t が x に代入可能かつ t の中に y が現れない)。 ∃y φ において t が x に代入可能 ⇔ x ≠ y または x ∉ fr(φ) または(φ において t が x に代入可能かつ t の中に y が現れない)。
以下の形の論理式すべてを論理公理とする。ここで、x, y は変数、t, t1 , ..., tn は項、φ, ψ は論理式を表す:
トートロジー(命題論理におけるトートロジーの命題記号を一階の論理式で置き換えて得られる論理式)
量化記号に関する公理
∀x φ → φx [ t ] (ただし、φ において t が x に代入可能(後述)の場合に限る)
∀x (φ → ψ) → (∀x φ → ∀x ψ)
∀x (¬ φ) ↔ (¬ ∃x φ)
等号に関する公理(言語が等号を持つ場合に限る)
x = x
x = y → (P t1 ... tn → P u1 ... un) (ただし、P は n 変数述語記号で、ui は ti における x のいくつかを y で置き換えて得られる項である)
量化記号に関する公理 1. における φx [ t ] とは、論理式 φ において "束縛されていない" 変数 x をすべて項 t で置き換えて得られる論理式を表す(正確な定義は後述)。