复旦大学：《离散数学 Discrete Mathematics（下）》英文课件（赵一鸣）25/32

定理20.9可满足性定理:设A是P(X的协 调子集,则存在赋值v:P(xX)>Z2,使得 v(A)c{1} 构造P(X)→z2的函数v 证明所构造的v是赋值即为同态映射) 0元运算v(F)=0 二元运算v(p→>q)?=v(p)-V(q) (1)q∈M (2)pE M (3)p∈M,q≌M

 定理20.9(可满足性定理):设A是P(X)的协 调子集，则存在赋值v:P(X)→Z2，使得 v(A) {1}。  构造P(X)→Z2的函数v,  证明所构造的v是赋值(即为同态映射)  0元运算:v(F)=0  二元运算:v(p→q)?=v(p)→v(q) (1)qM (2)pM (3)pM, qM

定理2010宏备性定到设 AcP(X,peP(X,若在Prop(X)中有AFp, 则在Prop(X)中有AFp 引理206:设w=w(x1…,xn)∈P(X,则Hw 当且仅当w的真值函数f是常值函数1。 定理2011Prop(X)的有效性是可判定的 推论204Prop(X是可证明性可判定的

 定理20.10(完备性定理):设 AP(X),pP(X)，若在Prop(X)中有A╞p， 则在 Prop(X)中有A┣p。  引理20.6:设w=w(x1 ,…,xn )P(X)，则╞w 当且仅当w的真值函数fw是常值函数1。  定理20.11:Prop(X)的有效性是可判定的  推论20.4:Prop(X)是可证明性可判定的

x>3,就无法用命题的形式来表示, 含有变量。 ■不能断定x>3是真还是假。 只有用变量x代之以具体的值时, ■如以5代替x的值时:就变成5>3这是一个真 命题。 而当x取值为2时,就是2>3,成了一个假命 题

 x>3,就无法用命题的形式来表示，  含有变量。  不能断定x>3是真还是假。  只有用变量x代之以具体的值时，  如以5代替x的值时：就变成5>3,这是一个真 命题。  而当x取值为2时，就是2>3，成了一个假命 题

在数学中有下面三个命题: P:所有的有理数都是实数。 nQ:3是有理数。 所以R:3是实数。 ■当前面两个命题为真时,可得出第三个命 题也是真的。即第三个命题是前两个命题 的逻辑推论。 n用符号P,QR分别表示这三个命题,则应 有P,Q}R, 但在命题逻辑中是无法得出此结论的。 需要引进新的逻辑系统—谓词逻辑

 在数学中有下面三个命题：  P： 所有的有理数都是实数。  Q： 3是有理数。  所以 R：3是实数。  当前面两个命题为真时，可得出第三个命 题也是真的。即第三个命题是前两个命题 的逻辑推论。  用符号P,Q,R分别表示这三个命题，则应 有{P,Q}╞R，  但在命题逻辑中是无法得出此结论的。  需要引进新的逻辑系统——谓词逻辑

第二十一章谓词逻辑

第二十一章 谓词逻辑

§1谓词代数 一、项与原子公式 一数的平方与一数的平方根之和大于0”。 命题涉及3个个体对象两个不确定数,x1X2 一个常数0,用c表示; 涉及3个函数,两个一元运算即平方与平方根),分别记为 求和运算则是二元运算,用f20表示; 最后,还有一个关于数的二元关系“大于”,用R2表示。 命题表示成R1(f20(61(x),f12(x2)1 这个命题是否正确,取决于对x1x2所作的赋值。 若x1x2都是非负实数且至少有一个不为0,则命题正确 ■若x1x2都为0,则命题不正确

§1 谓词代数  一、项与原子公式  一数的平方与一数的平方根之和大于0”。  命题涉及3个个体对象:两个不确定数，x1 ,x2  一个常数0，用c1表示；  涉及3个函数，两个一元运算(即平方与平方根)，分别记为 f1 (1),f1 (2) ，  求和运算则是二元运算，用f2 (1)表示；  最后，还有一个关于数的二元关系“大于”，用R2 (1)表示。  命题表示成R2 (1)(f2 (1)(f1 (1)(x1 ),f1 (2)(x2 )),c1 )。  这个命题是否正确，取决于对x1 ,x2所作的赋值。  若x1 ,x2都是非负实数且至少有一个不为0，则命题正确  若x1 ,x2都为0，则命题不正确

■通过分解命题可以发现,命题的内部结构包 含了下述内容: n(1)一些个体对象及对它们进行的某些运算 (2关于这些对象的一个关系

 通过分解命题可以发现，命题的内部结构包 含了下述内容：  (1)一些个体对象及对它们进行的某些运算；  (2)关于这些对象的一个关系

思考:P40023

思考： P400 23