命题演算的形式证明

3 命题逻辑形式系统（FSPC ）3.1 命题逻辑与命题演算Leibniz 提出逻辑推理变成符号演算不久，英国数学家BOOL 提出了布尔代数。

布尔代数把逻辑命题与逻辑推理归结为代数计算。

把命题看作是计算对象；把联结词看作算子；讨论计算的性质。

1、 命题（Propositions ）：可以判断真假的陈述句。

不涉及任何联结词的命题称为原子命题。

2、 联结词：⌝, →, ↔, ∨, ∧为联结词，用于联结一个或者多个命题。

->如果A 成立则B 成立，<->如果A 成立则B 成立，并且如果B 成立则A 成立；A ∨B ，或者A 成立或者B 成立；A ∧B ，A 成立并且B 成立。

3、 真值表：命题的真假称为命题的真值，用0表示假；用1表示真。

True(⌝A)，如果True(A)＝0，True(⌝A)=1：True(A)=1, True(⌝A)＝0A ＝0,1；如果True(A)=1,则 True （B ）=1,True(A->B)=1:或者True(A)=0或者True(B)=1：或者A 不成立，或者B 成立=⌝A ∨B ；如果True(A)=0,则 True （B ）=0，1；True(A)=<True （B ）；True(A) =True(B)，True(A<->B)=1；True(A ∨B)=max(True(A), True(B)); True(A ∧B)= min(True(A), True(B));A->A4、 命题变元：以真值为值域的变量称为命题变元。

A5、 赋值映射：命题变元集合到{0,1}上的函数。

如果公式A 对任意的赋值映射，取值为真，则称A 为永真式。

如果公式A 对于所有赋值映射为假，称为A 为矛盾式。

对于任意赋值映射，公式A 的真值等于公式B 的真值，成A 与B 等价。

True(A->A)＝1, True(⌝(A->A))＝0 A=1，True(⌝A->A)=1 A=0, True(⌝A->A)＝0命题逻辑有以下特点：1、 从语义角度研究逻辑命题之间真值变化规律。

第四章命题演算的一致性﹑完全性与公理的独立性4.1 命题演算的一致性和完全性*命题演算是一公理系统. 公理系统的作用在于, 从一些公理和推演规则出发, 把某一范围的真命题推演出来.*一方面我们希望, 从它能推演出较多的真命题, 希望能够完全, 能够把某一范围里的真命题完全推演出来.*另一方面, 我们也要求, 从它不能推演出我们所不要的东西, 特别是逻辑矛盾.这是所谓的完全性和一致性问题. 是否完全和是否一致, 是公理系统的两个重要问题.*推演和证明: 推演一词含义较广, 而证明一词含义较狭. 在第三章里, 我们引入了一些推演规则, 在 3.7节也定义了什么是证明. 一般说来, 推演的前提可以是任何公式或任何命题(如3.10节), 证明的根据则是一公理系统的公理(如:3.6―3.9节). 只有从公理可推演的公式或命题才是可证的, 才是定理.一. 命题演算的一致性*一个理论里如果存在逻辑矛盾, 这个理论就是不正确的. 无矛盾性, 也就是一致性, 是公理系统首先要满足的条件. 1. 一致性的几种定义:(1) 一致性的古典定义: 一个公理系统是一致的, 当且仅当, 不存在任何公式A, A和┐A都在这系统里可证.(2) 一致性的语义定义: 一个公理系统是一致的, 当且仅当,在这系统里可证的公式都是真的.*由于A和┐A不能同真, 故该系统没有逻辑矛盾.(3) 一致性的语法定义: 一个公理系统是一致的, 当且仅当, 并非任一合式公式都在这系统里可证.*如果任一公式都在系统里可证, 当然A和┐A也都在系统里可证, 因之系统按古典意义是不一致的.2. 一致性定理一致性定理一: 命题演算是语义一致的. 命题演算的定理都是重言式.证明的主要论证是:(1) 命题演算的公理都是重言式.(2) 应用命题演算的推演规则, 从重言式只能得到重言式.因之可得结论: 命题演算的定理都是重言式.逐步说明如下:(1) 命题演算的公理都是重言式.由3.3节的真值表可证4个公理都是重言式.(2) 命题演算共有三个推演规则: 代入, 分离和定义置换. 现分别加以说明.(甲) 应用代入规则, 从重言式只能得到重言式.设φ(p)为一重言式, 其中含有命题变项p. 由于φ(p)为重言式, 故不论p取值真或假, φ(p)皆为真. 真值表如下: p φ(p)0 11 1再设A为任一公式, 根据代入规则, 以A代入p后得φ(A), 而φ不变. 由于不论A如何复杂, 其值不外乎真或假, 而φ(p)是重言式, 因之, φ(A)的值都是真的. 真值表如下:A φ(A)0 11 1可以看出, φ(A)也是一重言式.(乙) 应用分离规则, 从重言式只能得到重言式.设A和A→B皆为重言式, 则它们的值常真, 在→的真值表中A B A→B0 0 10 1 11 0 01 1 1只有在第4种情况下, A和A→B同时为真, 而在这情况下, B 也为真. 如果A和A→B为重言式, 则它们的值常真, 那么B 的值也必为常真. 因之, B也是重言式.(丙) 应用定义置换规则, 从重言式只能得到重言式.由2.1节例2.4的真值表(5), (6)及德•摩根律(自己验证), 可知定义A∧B⇔┐(┐A∨┐B), A→B⇔┐A∨B,A↔B⇔(A→B)∧(B→A)的左右两方真值相同. 置换不改变真值, 置换后所得的公式和原公式真值也相同. 所以, 如原公式为重言式, 置换后的结果还是一个重言式.根据以上结果, 可知命题演算的定理都是重言式.一致性定理二: 命题演算是语法一致的. 并非任一公式都是命题演算的定理.证明: 既然一切定理都是重言式, 那么, 非重言式, 例如:p∨q 就不是定理.一致性定理三: 命题演算在古典意义下是一致的. 对于任一公式A, A和┐A不能都是命题演算的定理.证明: 对任一公式A, 有时A和┐A都不是重言式, 例如:┐p∨q和┐(┐p∨q). 则A和┐A都不是命题演算的定理. 若A是重言式, 则┐A为矛盾式, 因而不是重言式, 则A是定理, 而┐A不是定理. 因而, 命题演算是古典意义下一致的.二. 命题演算的完全性*关于公理系统的另一个重要问题是, 它能不能包括某一范围里的一切真命题, 是不是完全的. 虽然有些公理系统是完全的, 很多公理系统却是不完全的. 但是即使不完全, 公理化方法和公理系统仍然是数学科学的有力工具, 有重要的价值.1. 完全性的几种定义:(1) 完全性的语义定义: 一公理系统是完全的, 当且仅当, 一切属于某一特定范围内的真命题都是在这系统里可证的. (2) 完全性的语法定义: 一公理系统是完全的, 当且仅当, 如果把一个推演不出的公式作为公理, 其结果, 所得的系统就是不一致的.(3) 完全性的古典定义: 一公理系统是完全的, 当且仅当, 对任一合式公式A而言, 或者A是可证的, 或者┐A是可证的. *这种意义下的完全性是针对着某种公理系统而言的, 在这种系统里, 合式公式中没有自由变项. 命题演算不是这种公理系数. 在这种意义下, 命题演算不是完全的. 例如:┐p∨q 和┐(┐p∨q) 都在命题演算中不可证.2. 完全性定理完全性定理一: 命题演算在语义意义下是完全的. 一切重言式在命题演算里都是可证的.证明: 设A为一重言式.A有一合取范式. 设A的合取范式为B, B也是一重言式, 并且B为B1∧B2∧…∧B nB i (1≤i≤n)是简单析取, B i必是重言式.因之, 每一B i里必有一变项π, 并且π和┐π都作为B i的支命题出现. 每一B i都具有形式π∨┐π∨C .由定理4, p∨┐p可证, 再由附加规则, p∨┐p∨q 可证.所以, 由代入规则可知, 每一B i都可证.根据定理├p→(q→p∧q), B1∧B2∧…∧B n可证. 所以, B可证.B是A的范式, 是从A根据置换规则得到的. 如果B可证, 则A也可证.可见, 如A是重言式, 则A可证.凡重言式皆可证, 故命题演算是完全的.*这个完全性定理也提供了一个有效的证明方法.完全性定理二: 命题演算在语法意义下是完全的. 如果把一不可证的公式作为公理, 其结果将是不一致的.证明: 设A在命题演算里不可证.因凡重言式皆可证, 所以A不是重言式.设B为A的合取范式, 则B不是重言式.设B = B1∧B2∧…∧B n , 则有一B i (1≤i≤n), B i不是重言式. 所以, 在B i里, 不可能有一变项π, π和┐π都作为B i 的支命题出现. B i的支命题中, 虽然有些是否定的, 有些是肯定的, 但是命题变项不相同. 例如: p∨┐q∨┐r∨s .假若把A作为公理, 因B是A的范式, 则B可证. 所以, 根据定理├p∧q→p, B i可证.如以p代入B i中的肯定支命题, 以┐p代入B i中前面带有否定符的命题变项, 例如: 在p∨┐q∨┐r∨s中进行这样的代入, 则可得p∨┐┐p∨┐┐p∨p销去双重否定, 则得一命题变项的析取, 例如:p∨p∨p∨p所以, 如果B i可证, 则p∨p∨…∨p可证.根据公理1, ├p∨p→p, 则p可证.如p可证, 则p为一定理. 即├p . 如果A代入p, 可得├A. 如再用┐A代入p, 又可得├┐A . 如p可证, 则A 和┐A皆可证. 这是逻辑矛盾.所以, 如将一不可证的公式作为公理, 则将导致逻辑矛盾. 可见命题演算具有语法意义下的完全性.4.2 公理的独立性1. 独立性的意义: 一公式集合M是独立的, 如果M中的任一公式A都不能根据给定的推演规则从M中其它公式推演出来.*对于一公理系统的诸公理, 我们希望它们是独立的. 作为出发点的诸公理最好是缺一不可, 任何一个公理都不能从其它公理推演出来.*独立性和一致性不同, 和完全性也有所不同, 一公理系统的诸公理, 其中即使有不独立的, 也不能算是很大的缺点. 2. 算术解释方法:为了证明独立性, 我们通常采用一种算术解释方法. 以下先说明什么是算术解释方法及其可以作独立性证明的理由.设给定一公式集合{A1, A2, A3, A4}和两个推演规则R1和R2. 求证: 根据R1和R2, A4对于{A1, A2, A3}是独立的.我们先从反面着想, 假若A4不独立, 它可以从{A1, A2, A3}根据R1和R2推出. 那么, 下面的断定必然成立: 对于任一性质φ而言, 如果(1) A1, A2, A3都有性质φ,(2) 应用R1和R2, 从有性质φ的公式只能得到有性质φ的公式, 那么,(3) A4必有性质φ.根据以下断定, 假若存在着一性质φ, 并且(1) A1, A2, A3都有性质φ,(2) 应用R1和R2, 从有性质φ的公式只能得到有性质φ的公式,但是(3) A4没有性质φ.那么, 这样一个φ的存在就充分说明了, 应用R1和R2从{A1, A2, A3}不可能推演出A4, A4是独立的.采用解释方法要求我们能够发现一种解释, 这种解释与A1, A2, A3, A4以及R1和R2里的符号以特定的意义, 从而产生独立性证明所需要的性质φ.由于通常采用的解释是赋予变项和公式以数值, 所以这种方法被称为算术解释方法.3. 独立性证明:(一) 独立性证明一: 命题演算的公理1不能从公理2, 3, 4用推演规则推演出来.算术解释: 给予命题演算的原始符号如下解释.(1) 命题变项p, q, r, s, p1, …等可以有三个值: 0, 1, 2 .(2) 初始联结词的数值表如下:A ┐A AB A∨B0 1 0 0 01 0 0 1 02 2 0 2 01 0 01 1 11 2 22 0 02 1 22 2 0根据这种解释, 可有以下结果:(1) 公理2, 3, 4的值常为0. 数值表从略.(2) 应用推演规则, 从数值常为0的公式只能得到数值常为0的公式. 关于代入和定义置换的说明如下.φ(p)中p被代以A,得φ(A). 无论A多复杂, 它只取值0, 1, 2, 相当于p取值0, 1, 2, φ(p)(公理2, 3, 4或它们的推论)取值始终为0, 故φ(A)取值常为0.定义置换也类似. 定义两边A B同时取值0或1或2.在φ(A)中用B置换A得φ(B), 由于在任一解释下B与A等值, 故φ(B)与φ(A)等值.以下证明分离规则:A B ┐A A→B(┐A∨B)0 0 1 00 1 1 10 2 1 21 0 0 01 1 0 01 2 0 02 0 2 02 1 2 22 2 2 0从表上可以看出, 当A和A→B的数值皆为0时, B的值也是0. 所以, 如A和A→B的值常为0, 则B的值也常为0. 应用分离规则, 从公理2, 3, 4只能得到其值常为0的公式.*此处的“数值常为0”,就是独立性证明所需要的性质φ.公理1如果不是独立的, 是可以推出的, 它的数值也必常为0. 但公理1的数值不常为0.(见下表).p p∨p ┐(p∨p) ┐(p∨p)∨p0 0 1 01 1 0 02 0 1 2可见公理1不能从其它公理推出.(二) 独立性证明二: 公理2不能从公理1, 3, 4用推演规则推出.算术解释:(1) 命题变项有四个值: 0, 1, 2, 3 .(2) ┐和∨的数值解释, 用等式表示为:(甲)┐0=1, ┐1=0, ┐2=3, ┐3=2 .(乙) 0∨0=0∨1=0∨2=0∨3=01∨1=1∨2=1∨3=12∨2=2∨3=23∨3=3交换律对∨适用.根据这种解释, 公理1, 3, 4的值常为0或2, 推演规则也传递“等于0或2”这性质, 但公理2并不常“等于0或2”. 当p取值2, q取值1时,p→p∨q的值为2→2∨1=┐2∨(2∨1)=3∨1=1 .所以公理2是独立的.(三)独立性证明三: 公理3不能从公理1, 2, 4用推演规则推出.此处算术解释是:(1) 命题变项有四个值: 0, 1, 2, 3 .(2) ┐和∨的数值解释, 用等式表示为:(甲) ┐0=1, ┐1=0, ┐2=0, ┐3=2(乙) 0∨0=0∨1=1∨0=0∨2=2∨0=0∨3=3∨0=01∨1=1,1∨2=2∨1=2,1∨3=3∨1=32∨3=0,3∨2=3,2∨2=2,3∨3=3根据这个解释, 公理1, 2, 4的值常为0, 推演规则传递“常为0”的性质. 但公理3的值不常为0.当p取值2, q取值3时, 公理3的值为3.(四) 独立性证明四: 公理4不能从公理1, 2, 3用推演规则推出.在此我们用以下的算术解释.(1) 命题变项有四个值: 0, 1, 2, 3 .(2) ┐和∨的数值解释为:(甲) ┐0=1, ┐1=0, ┐2=3, ┐3=0 .(乙) 0∨0=0∨1=1∨0=0∨2=2∨0=0∨3=3∨0=01∨1=1,1∨2=2∨1=2,1∨3=3∨1=32∨2=2,2∨3=3∨2=0,3∨3=3 .根据这个解释, 公理1, 2, 3以及从它们推演出来的公式, 其值都常为0, 而公理4的值不常为0. 当p取值2, q取值2,r取值2时, 公理4的值为2.作业:1. 在自然推理系统P中, 证明以下推理:今天下雨或明天后天都下雨, 明天不下雨或后天不下雨而今天下雨. 可以推出“今天下雨”.2. 在自然推理系统P中, 证明以下推理:如果李敏来通信工程学院, 若王军不生病, 则王军一定去看望李敏. 如果李敏出差到南京, 那么李敏一定来通信工程学院. 王军没有生病. 所以, 如果李敏出差到南京, 王军一定去看望李敏.3. 在自然推理系统P中, 证明以下推理:前提: B∧C, (B C)→(H∨G)结论: G∨H .4. 在自然推理系统P中, 证明以下推理:前提: P→Q, (┐Q∨R)∧┐R, ┐(┐P∧S)结论: ┐S .。

第二部分集合、矩阵、关系和函数集合论是处理集合，函数和关系的数学理论。

集合包括最基本的数学概念，例如集合，元素和成员关系。

在大多数现代数学公式中，集合论提供了一种描述数学对象的语言。

集合可用来表示数及其运算，还可表示和处理非数值计算，如数据间关系的描述等。

集合论，逻辑和一阶逻辑构成了数学公理化的基础。

同时，函数和关系是基于集合的映射，它们是满足某些属性的特殊集合。

接下来，我们将在两个单独的章节中介绍它们。

集和矩阵将在第3章中介绍，而关系和函数将在第4章中介绍。

第三章集合和矩阵3.1 集合3.1.1 集合概念集合没有确定的概念。

一般地，我们把研究的对象统称为元素；把一些元素组成的总体叫做集合，也简称集。

通常用大写英文字母表示集合。

例如，N代表是自然数集合，Z代表是整数集合，R代表是实数集合。

用小写英文字母表示集合内元素。

若元素a是集合A的一个元素，则表示为a A∈，读作元素a属于集合A；若元素a不是集合A的一个元素，则表示为a A∉，读作a不属于集合A。

集合分为有限集合和无限集合两种，下面给出定义。

表示集合方法有列举法和描述法两种方式，下面分别介绍。

1. 列举法当集合是有限集合时，可以列出集合的所有元素，用逗号隔开各元素，并用花括号把所有元素括起来。

这种表述方式为列举法。

例如：S1={a, b, c, d, e, f}，S2={a, b, b, c, d, e, f}，S3={ d, e, a, b, c, f}上述三个集合S1、S2和S3是相同集合，尽管有重复元素。

且集合元素之间没有次序关系。

一个集合可以作为另个集合的元素。

例如，S1={a, b,{ c, d, e, f }}集合S1包含元素a, b和{ c, d, e, f }。

因为{ c, d, e, f }是集合S1中的元素，故可记为：{}∈。

,,,c d e f A以上给出的集合实例都是有限集合。

当集合是无限集合时，无法列出集合的所有元素，可先列出一部分元素，若剩余元素与已给出元素存在一定规律，那剩余元素的一般形式很明显可用省略号表示。

1、设简单图G所有结点的度数之和为12，则G一定有_____条边。

问题反馈【教师释疑】正确答案：【6 】62、设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X 上的等价关系，R应取_______. 问题反馈【教师释疑】正确答案：【{〈a,c〉,〈c,b〉} 】{〈a,c〉,〈c,b〉}3、命题公式的任意两个不同极小项的合取式一定为_________. 问题反馈【教师释疑】正确答案：【永假式】永假式4、一个公式在等价意义下，_______范式写法是唯一的。

问题反馈【教师释疑】正确答案：【主析取】主析取5、若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为_______ 问题反馈【教师释疑】正确答案：【P∧┐Q 】P∧┐Q6、设R是A上的二元关系,且RRR为R的子集,可以肯定R应是_____关系。

问题反馈【教师释疑】正确答案：【传递】传递7、设集合A＝{1, 2, 3, 4}，A上的二元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。

则R×S ＝__________________, 问题反馈【教师释疑】正确答案：【{(1,3),(2,2)} 】{(1,3),(2,2)}8、设谓词的定义域为{a, b},将表达式"任意xR(x)→彐xS(x)"中量词消除，写成与之对应的命题公式是__________________. 问题反馈【教师释疑】正确答案：【(R(a)∧R(b))→(S(a)∨S(b)) 】(R(a)∧R(b))→(S(a)∨S(b))9、设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; 问题反馈【教师释疑】正确答案：【{3} 】{3}10、设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________ 问题反馈【教师释疑】正确答案：【12 】1211、设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A∩B＝_________________________; 问题反馈【教师释疑】正确答案：【{4} 】{4}12、设A={a, b, {a, b}}，B={a, b}，则B－A =________ 问题反馈【教师释疑】正确答案：【Φ】Φ13、设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。