数理逻辑

以下显示部分文章预览。

一阶语言的语法

一阶语言的字母表,由以下几部分组成:
(1)变量 \(v_0,v_1,\cdots\)
(2)连接词 \(\lnot,\land,\lor,\rightarrow,\leftrightarrow\)
(3)量词 \(\forall,\exists\)
(4)等号 \(\equiv\)
(5)括号 \((,)\)
(6)
[1]\(\forall n\ge 1,\),n元关系符号集;
[2]\(\forall n\ge 1,\),n元函数符号集;
[3]常量集. 这三部分都可能有空集.

前五部分是一阶语言所共有的符号,记作A,第六部分记作S,称为符号集(symbol set),决定了一个一阶语言.
给定符号集S, 一些\(A_S=A\cup S\)的字符串称为由S决定的一阶语言的"公式"(formula)。为了给出公式的精确定义,我们先定义"项"(term):
(T1) 每个变量是一个S的项;
(T2) 每个常量是一个S的项;
(T3) 如果\(t_1,\cdots,t_n\)都是S的项,f是一个n元函数,则\(ft_1\cdots t_n\)也是S的项。
S的项记作\(T^S\).

下面给出S-公式的定义. 以下(F1,F2)左边内容表示S-项,(F3,F4)左边内容表示既得的S公式,右边都表示由左边生成的S-公式.
(F1) \(t_1,t_2 \Rightarrow t_1 \equiv t_2\).
(F2) \( t_1,\cdots ,t_n, R \Rightarrow Rt_1\cdots t_n\).由(F1,F2)生成的公式称为本原公式(atomic formulas).
(F3) \(\varphi \Rightarrow \lnot \varphi\).
(F4) \(\varphi, \psi \Rightarrow (\varphi\land\psi),(\varphi\lor\psi),(\varphi\to\psi),(\varphi\leftrightarrow\psi)\).分别称作合取式,析取式和蕴涵式(conjunction, disjunction, implication)
(F5) \(\varphi\)是既得公式,x是变量,\(\Rightarrow\forall x \varphi,\exists x \varphi.\)
用\(L^S\)表示S-公式。

唯一分解定理
接下来我们将看到,无论是term还是formula,都有唯一的生成路径。先给出几个引理。
引理1. 任意两个term(或formula)互不为真前缀。
引理2. 如果由term(或formula)组成的字符串\(t_1t_2\cdots t_n=t'_1t'_2\cdots t'_m\),则\(n=m\)且\(t_i=t'_i.\)
定理.
(1) 每个term要么是一个变量,要么是一个常量,要么具有形式\(ft_1\cdots t_n,\)且这种形式是唯一确定的。
(2) 和(1)类似,每个formula也是由F1-F5中的唯一一种形式生成的,且在该种生成方式的分解唯一。

在公式中,没有量词约束的变量称为"自由变量"(free variables). 没有自由变量的formula称为"句子"(sentence). 自由变量属于\(\{v_0,v_1,\cdots v_{n-1}\}\)的公式构成集合记作\(L_n^S.\)

    发表于2022-01-20