一阶逻辑基本概念
一些笔记:
重言式的代换实例都是永真式,矛盾式的代换都是矛盾式。
对公式中的个体域及个体常项、函数符号、谓词符号的指定称作解释,指定自由出现的个体变项的值称为赋值。
注意解题格式。以下给出书上几道例题。
用0元谓词将下列命题符号化:只有2是偶数,4才是偶数。
解: F ( 4 ) → F ( 2 ) F(4) \rightarrow F(2) F(4)→F(2),其中F(x):x为偶数。
在一阶逻辑中将下列命题符号化:有的实数是无理数,有的实数是有理数。
解: ∃ x ( F ( x ) ∧ G ( x ) ) ∧ ∃ y ( F ( y ) ∧ H ( y ) ) \exists x(F(x) \wedge G(x)) \wedge \exists y (F(y)\wedge H(y)) ∃x(F(x)∧G(x))∧∃y(F(y)∧H(y)),其中 F ( x ) : x 是 实 数 , G ( x ) : x 是 有 理 数 , H ( x ) : x 是 无 理 数 F(x):x是实数,G(x):x是有理数,H(x):x是无理数 F(x):x是实数,G(x):x是有理数,H(x):x是无理数。
证明 ∀ x ( F ( x ) → G ( y ) ) \forall x(F(x)\rightarrow G(y)) ∀x(F(x)→G(y))为可满足式,但不是永真式。
证:取解释 I I I为:个体域为全总个体域, F ( x ) : x F(x):x F(x):x为自然数,G(y):y为整数, I I I下的赋值 σ 1 ( y ) = 1 \sigma_1(y)=1 σ1(y)=1。不难看出,在 I I I与 σ 1 \sigma_1 σ1下,题中公式为真命题,所以它为可满足式。
取 σ 2 ( y ) = 1.5 \sigma_2(y)=1.5 σ2(y)=1.5,则在 I I I和 σ 2 \sigma_2 σ2下公式为假命题,所以它不是永真式。