一階述語論理
φx [ t ] は、論理式 φ において "束縛されていない" 変数 x をすべて項 t で置き換えて得られる論理式を表すと述べた。正確には、φx [ t ] は再帰によって次に述べるような仕方で定義される。
まず、それぞれの項 u に対して ux [ t ] を次のように再帰的に定義する: xx [ t ] = t 。 y が x と異なる変数ならば、yx [ t ] = y 。 c 定数記号ならば、cx [ t ] = c 。 t1 , ..., tn が項で、f がアリティ n の関数記号ならば、(f t1 ... tn)x [ t ] = f (t1)x [ t ] ... (tn)x [ t ] 。
そして、φx [ t ] を次のように再帰的に定義する: 原子論理式 P t1 ... tn に対しては、(P t1 ... tn)x [ t ] = P (t1)x [ t ] ... (tn)x [ t ] 。 (¬ φ)x [ t ] = (¬ φx [ t ]) (φ ∧ ψ)x [ t ] = (φx [ t ] ∧ ψx [ t ]) (φ ∨ ψ)x [ t ] = (φx [ t ] ∨ ψx [ t ]) (φ → ψ)x [ t ] = (φx [ t ] → ψx [ t ]) (φ ↔ ψ)x [ t ] = (φx [ t ] ↔ ψx [ t ]) (∀x φ)x [ t ] = ∀x φ 、(∃x φ)x [ t ] = ∃x φ 。 y が x と異なる変数ならば、(∀y φ)x [ t ] = ∀y φx [ t ] 、(∃y φ)x [ t ] = ∃y φx [ t ] 。
はじめに述べたように、一階述語論理の論理式の解釈は構造と呼ぶものによって与えられる。構造は変数が動く領域とそれぞれの非論理記号に対する "意味" の割り当てからなる。正式には、構造は次のように定義される。
一階の言語に対する構造 (structure) とは、空でない集合 D {\displaystyle D} と、非論理記号全体の集合を定義域とする関数 F {\displaystyle F} の組 M = ( D , F ) {\displaystyle M=(D,\,F)} で次をみたすものをいう: P {\displaystyle P} がアリティ n {\displaystyle n} の述語記号ならば、 F ( P ) ⊆ D n {\displaystyle F(P)\subseteq D^{n}} 、すなわち F ( P ) {\displaystyle F(P)} は D {\displaystyle D} 上の n {\displaystyle n} 項関係である。 f {\displaystyle f} がアリティ n {\displaystyle n} の関数記号ならば、 F ( f ) : D n → D {\displaystyle F(f):D^{n}\to D} 、すなわち F ( f ) {\displaystyle F(f)} は D {\displaystyle D} 上の n {\displaystyle n} 項演算である。
型つき一階述語論理は変項や項に型または種を導入したものである。型の個数が有限個であれば普通の一階述語論理と大きな違いはなく、有限個の単項述語で型を記述し、いくつかの公理を追加すればよい。真理値として Ω という特殊な型を持つ場合があるが、その場合の論理式は Ω 型の項となる。
弱二階述語論理は有限個の部分集合の量化を許すものである。
単項二階述語論理は部分集合、すなわち単項述語の量化のみを許すものである。
二階述語論理は部分集合および関係、すなわち全ての述語の量化を許すものである。
高階述語論理は述語を引数とする述語など、さらに一般化したものの量化を許す。
直観主義的一階述語論理は古典命題計算ではなく直観主義を導入するものである。例えば、¬¬φ は必ずしも φ と等しいとは限らない。
様相論理は様相演算子を追加したものである。これは、直観的に説明すれば、「~は必然的である」および「~は可能である」を意味する演算子である。
無限論理は無限に長い文を許す。
自然数論の言語における論理式 ( S 0 + S 0 ) = S S 0 {\displaystyle (S0+S0)=SS0} の各記号を通常の意味で解釈すれば「 1 + 1 = 2 {\displaystyle 1+1=2} 」となり、これは真である論理式である。 ¬ [ ( S 0 + S 0 ) = S S 0 ] {\displaystyle \lnot [(S0+S0)=SS0]} は「 1 + 1 ≠ 2 {\displaystyle 1+1\neq 2} 」となるので通常の解釈で偽なる論理式である。また、変数の動く範囲(議論領域)は自然数全体の集合だとすれば、論理式 [ ∀ x 1 ( 0 = S x 1 ) ] {\displaystyle [\forall x_{1}(0=Sx_{1})]} は「すべての自然数 n {\displaystyle n} について 0 = n + 1 {\displaystyle 0=n+1} 」という意味になり、これは偽である論理式であることが分かる。一方、論理式 ( 0 + x 5 ) = S 0 {\displaystyle (0+x_{5})=S0} の意味を考えてみると、「 0 + x 5 = 1 {\displaystyle 0+x_{5}=1} 」となるがこれは真であるか偽であるかを判断することができない。なぜなら、 x 5 {\displaystyle x_{5}} という変数が何を表しているかが決まっていないからである。