西交《离散数学》第二章拓展资源2

在线作业答案

西交《离散数学》 第二章 关系 拓展资源2
  ◆逻辑
逻辑的第一种含义，是指一组关系密切的人工语言。
逻辑的另一种较为古老的含义，是指对可靠论证的规则的研究。
一阶语言并不指任何事物，它包括一些符号，这些符号称为常项。
世界上的某种事物被指派到一阶语句的某个常项上，这个一阶语句有意义，这种指派称为解释
一阶语句的意义，也就是它的语义这样确定：对一个一阶语句和它的一个解释，该解释总是使得这个一阶语句要么为真，要么为假。也就是，如果一个解释使得一个句子为真，则该句子在这一解释下的真值是真；如果一个解释使得一个句子为假，则该句子在这一解释下的真值是假。这就是一阶语句的语义。
构成一解语言的常项的集合，称作该语言的名册
如果某个解释对一个名册中的所有常项都有指派，则称该解释是该名册的一个解释。
以上讲的概念中有：逻辑、一阶语言的构成、常项、指派、解释、一阶语言的语义、名册、名册的解释。
◆模型
关于模型的定义：一个解释使得一个句子为真，那么称这个解释满足这个句子，也就是说该解释是该句子的一个模型。
被一个解释满足的所有的句子统称为这个解释的（一阶）理论。
因此，可以说任意一个句子集都可称作一个理论。如果一个解释是一个理论中的任意一个句子的模型，则称该解释是该理论的一个模型。
上面讲了理论、理论的模型。下面讲模型类和公理集。对于一个句子，所有满足该句子的解释，统称为该句子的模型类
一个理论的模型类是满足该理论的所有解释的类。如果一个解释类是理论的模型类，那么该理论就称为该解释类的一个公理集。
◆等价、矢列、可靠性和完全性
如果两个理论具有相同的模型，则称它们等价, 或逻辑等价。对句子而言，如果两个句子在同一解释下为真，则它们等价。如果一个理论至少有一个模型，则称它（语义）一致。否则，称它（语义）不一致。
对一个理论T和一个句子S，如果，凡是满足T的解释都满足S，则称T衍推S。用排斥法描述为：如果不存在这样的解释，它满足T但不满足S，则称T衍推S。如果一个句子在任何一个解释下都为真，则称这个句子有效。
这样就可以得出一个推论：一个句子有效，当且仅当它由一个空理论衍推。有效实际上是衍推的一个特例。
因为空理论中不存在假句子，所以，每个解释都可以是空理论的模型。所以，当一个空理论衍推一个句子时，就意味着每个解释都可以使得该句子为真。也就是该句子有效。
◆矢列
先引入一个符号“|-”，读作推出（turnstile）一个矢列指的是这样一个表达式：T |- S。
左边是理论，理论中的句子称为矢列的前提；右边是一个句子，称为矢列的结论。如果矢列左边的理论衍推右边的句子，则称矢列有效，否则成矢列无效。如果矢列的理论是一个有穷的句子集，则称矢列为一有穷矢列。
◆可判定性、可靠性和完全性
对于一阶语言来说，如果存在一个算法，能确定任一有穷矢列是否有效，则称该语言可判定。
如果一个证明演算中的某个形式证明是一个矢列的证明，则称该矢列在该演算中可推导。
如果所有无有效矢列在某个演算中都不可推导，则称该演算是可靠的（恰当的）。
如果所有有效的矢列在某个演算中均可推导，则称该演算是完全的。
◆一阶逻辑等值式
　　若
为逻辑有效式 (其中
为逻辑公式)，则称
与
等值，记
，称
为等值式。
　　

　　以下，再给出其他一些重要的等值式(证明略去)
1、量词否定等值式。
　　(1)

　　(2)

2、量词辖域收缩与扩张等值式。
　　(1)

　　(2)

　　(3)

　　(4)

　　(5)

　　(6)

　　(7)

　　(8)

　　在以上各公式中，
是含
自由出现的任意的公式，而
中不含
的出现。
3、量词分配等值式。
　　(1)

　　(2)

注意：

　　　

4、多个量词间的次序排列等值式。
　　(1)

　　(2)

本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986