离散数学：第二章 第二节 项和公式 [兼容模式].pdfVIP

2009-11-5 第二章谓词逻辑 §2.2 项和公式 §2.1 谓词和量词 本节讨论一阶逻辑的语法概念。 §2.2 项和公式 项是用于表达个体的符号串，相当于汉语中的名词。 §2.3 解释和赋值 公式是用于表达命题的符号串，相当于汉语中的句 子子。。 §2.4 永真式 项和公式是语法概念，它们都是符号串。两个项 §2.5 等值演算 （公式）相同当且仅当它们是同样的符号串。与汉 §2.6 逻辑推论 语不同，一阶逻辑的语言是形式语言，即一个符号 作业 串是不是项（公式）是可以用计算机判别的。 §2.3 讨论一阶逻辑的语义概念，即项和公式的解 释。 谓词逻辑中使用的符号分为以下几组。 5. 量词符号∀。 1. 个体变元，简称变元，有无穷多个，用加或不 6. 联结词符号¬，→。 加下标的小写英文字母x , y , z, u, v, w 等表示。 7. 圆括号和逗号。 2. 个体常元，简称常元，有无穷多个，用加或不 因为{¬, →} 是联结词的完全集，其它联结词（除 加下标的小写英文字母a, b, c, d 等表示。 了0 元联结词）都可以用¬和→定义，所以只取 3. 函数符号，每个函数符号都联系一个正整数n ， ¬和→为初始符号，而将其它常用联结词符号作 并称该函数符号为并称该函数符号为n 元函数符号元函数符号。对每个正整对每个正整 为被定义符号引入。 数n ，有无穷多个n 元函数符号。用加或不加 下标的小写英文字母f , g, h 等表示函数符号。 有的书采用¬, ∨或者¬, ∧为初始符号。 4. 谓词符号，每个谓词符号都联系一个正整数n ， 因为用∀ 和 ¬ 可以定义存在量词 ∃，所以只取∀ 并称该谓词符号为n 元谓词符号。对每个正整 为初始符号，而将∃作为被定义符号引入。 数n ，有无穷多个n 元谓词符号。用加或不加 有的书采用∃为初始符号。 下标的大写英文字母P, Q, R 等表示谓词符号。 在一阶逻辑中只有一种变元（个体变元）。如果有 定义2.1 项是按以下规则构成的有穷长符号串。 函数变元和谓词变元，并且允许对它们量化，就成 1. 每个变元是项。 为二阶谓词逻辑。二阶逻辑与一阶逻辑的性质有很 大差别。二阶逻辑的表达能力比一阶逻辑更强。例 2. 每个常元是项。 如，论域的有穷性、良序集、自然数的归纳原理等 3. 若f 是n 元函数符号且t1,…, tn 是项，则 用一阶逻辑都无法表达，而可以用二阶逻辑表达。 f (t ,…, t ) 是项。 例如，自然数的归纳原理可表达为二阶逻辑公式 1 n ∀P(P(a) ∧∀x(P(x) →P(f (x))) →∀xP(x)) 例如，x , c 是项。 其中P 是一元谓词变元。 若f 是