人工智能的数学基础 课件

李凌均郑州大学振动工程研究所十二月22第二章人工智能的数学基础李凌均第二章人工智能的数学基础1第二章人工智能的数学基础人工智能的数学基础有：逻辑学、概率论、模糊理论。逻辑经典命题逻辑一阶谓词逻辑2.1命题逻辑与谓词逻辑2.2多值逻辑2.3概率论2.4模糊理论非经典逻辑多值逻辑、模糊逻辑模态逻辑、时态逻辑具有真假意义本章内容：郑州大学振动工程研究所电话037167881792第二章人工智能的数学基础人工智能的数学基础有：逻辑学、概率2.2.1.命题一个具有真假意义的陈述句，称为命题。命题通常用大写的英文字母P，Q，R等来表示,命题是具有或真或假的含义的。如果一个命题的真值为真则用T(或1)表示，若为假则用F(或0)表示下面的例子均是命题：(1)郑州大学是一所综合性大学。（T）(2)2+2=5（F）。(3)今天是个好天气。（T）(4)每一个奇数都是素数。（F）2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话0371678817922.2.1.命题2.1命题逻辑与谓词逻辑郑州大学振动工程下面的例子都不是命题：(1)现在是几点钟？(疑问句）(2)x-y>2（其真假值随x、y的变化而变化，不能确定。）(3)我在说假话。（悖论，真作假时假亦真，假作真时真亦假）(4)请安静！（祈使句）2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792下面的例子都不是命题：2.1命题逻辑与谓词逻辑郑州大学振动命题逻辑的局限性：

在命题逻辑中我们研究的最小单位是句子,即命题，它无法把所要描述的客观事物的结构及逻辑关系反映出来。也无法把不同对象的共同特征表述出来。很多问题仅用命题逻辑是解决不了的、表达不清的。由此发展了谓词逻辑。2.1.2.谓词：在谓词逻辑中引入谓词来表示命题。一个谓词分为谓词名和个体2部分，谓词用于描述个体的性质、状态或个体之间的关系。个体就是要被描述的某个独立存在的事物或某个抽象的概念。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792命题逻辑的局限性：2.1.2.谓词：在谓词逻辑中引入谓词来表例1：张华是大学生。其中“张华”是个体，“是大学生”是谓语。于是我们可引入一个谓词S（x)来表示x是大学生，张华代以x就表示张华是大学生。S（x)涉及到一个变元，称为一元谓词，一元谓词表示个体的属性。例2：张华比李玲高。其中“张华”和“李玲”是个体，“…比…高”是谓词，因为涉及到两个个体，所以我们可以用一个二元谓词G（x,y)表示x高于y,将张华代以x,李玲代以y,则表示张华比李玲高。若用李玲代以x,张华代以y,则表示李玲高于张华。也就是说谓词中客体变元的顺序一经定义就不能随意改变了。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792例1：张华是大学生。其中“张华”是个体，“是大学生”是谓语。有多个变元的谓词称为多元谓词，多元谓词表示多个客体之间的关系。谓词中的个体可以是常量，也可以是变元或函数。谓词的语义是由使用者定义的，一旦被定义意义就明确。当谓词中的变元全部用特定的个体取代时，谓词就有了确定的真值TorF。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792有多个变元的谓词称为多元谓词，多元谓词表示多个客体之间的关系连接词象在整数或实数集合上可以进行+，-，*，/运算一样，在命题集合上也可以进行运算，形成新的命题。常用的命题运算符亦称为连接词有:¬：非

：合取(与)， ：析取(或)， ：条件或蕴涵， ：双条件(当且仅当)2.1命题逻辑与谓词逻辑2.1.3.谓词公式：郑州大学振动工程研究所电话037167881792连接词2.1命题逻辑与谓词逻辑2.1.3.谓词公式：郑州逻辑连接词非“¬”：如果P是一个命题，那麽¬P是一个命题，它的真值是这样定义的：P真(1)，¬P假；P假(0)，¬P真。可以用如下的一个所谓真值表来表示：这里应该注意的是¬P是对整个命题P的否定，而不是对命题P的部分成分否定。¬是一个一元逻辑连接词。2.1命题逻辑与谓词逻辑P¬P0110郑州大学振动工程研究所电话037167881792逻辑连接词非“¬”：如果P是一个命题，那麽¬P是一个命题，它逻辑连接词合取“”：如果P是一个命题，Q是一个命题，那麽PQ是一个命题，它的真值是这样定义的：当且仅当P和Q同时为真时，PQ的值为真，其余情况均为假。2.1命题逻辑与谓词逻辑PQPQ000010100111其真值表如右：“”是一个二元逻辑连接词。这是一个复合命题，可以读作合取或“和”、“and”。郑州大学振动工程研究所电话037167881792逻辑连接词合取“”：如果P是一个命题，Q是一个命题，那麽P例如令P：曹老师是教授。

Q：王晓离散数学不及格。则PQ：曹老师是教授并且王晓离散数学不及格注意这两件事在日常生活中可能是毫不相干的事情，但在命题逻辑中是有意义的，即P和Q的真值定下来，PQ的真值就可求。再例如令P：今天是晴天。

Q：欢欢是大熊猫。于是PQ：今天是晴天并且欢欢是大熊猫。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792例如令P：曹老师是教授。2.1命题逻辑与谓词逻辑郑州大学振逻辑连接词析取“”:如果P是一个命题，Q是一个命题，那麽PQ是一个命题，并且它的真值是这样定义的：当且仅当P和Q同时为假的时候PQ的值才为假，否则其值为真。其真值表如下：2.1命题逻辑与谓词逻辑PQPQ000011101111“”可以读作析取也可以读作“或”、“or”

，它是个二元逻辑连接词。但它仅代表日常生活中的可兼容或，不代表排斥或。郑州大学振动工程研究所电话037167881792逻辑连接词析取“”:如果P是一个命题，Q是一个命题，那麽P例如令P：今天下午3点我去讲课。

Q：今天下午3点我去游泳。日常生活中可能会说，今天下午3点我去讲课或今天下午3点我去游泳。这里的或是一种排斥或(也称异或），不能使用逻辑连接词“”来表示，也就是说不能用PQ：来表示今天下午3点我去讲课或今天下午3点我去游泳。但下面的例子可以用析取来表示。P：李明在教室。Q：王鹏去公园。于是PQ表示：李明在教室或王鹏去公园。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792例如令P：今天下午3点我去讲课。2.1命题逻辑与谓词逻辑郑逻辑连接词单条件“”：如果P是一个命题，Q是一个命题，那麽PQ是一个命题，表示P蕴涵Q，即：如果P，则Q。P成为条件的前件，Q成为条件的后件。它的真值是这样定义的：PQPQ001011100111当且仅当前件为真后件为假的时候，PQ的值才为假，其余情况均为真。其真值表如右：

2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792逻辑连接词单条件“”：如果P是一个命题，Q是一个命题，那麽例如令P：今天有雨。Q：我带雨伞。于是PQ：如果今天有雨，那麽我带雨伞。如果我们指定P为真代表今天有雨，那麽P为假表示今天没有雨，指定Q真为我带雨伞，那麽我没带雨伞为Q假。现在我们来分析上面真值表的各种情况：1、P=0，Q=0即今天没雨，我没带雨伞。PQ=1即成功。2、P=0，Q=1即今天没雨，我带雨伞。PQ=1也成功（带雨伞也没错）2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792例如令P：今天有雨。Q：我带雨伞。2.1命题逻辑与谓词逻3、P=1，Q=0,PQ=0即今天有雨，我没带雨伞，挨淋，失败。4、P=1，Q=1,PQ=1即今天有雨，我带雨伞。成功。由上面的例子可以看出，

PQ真值的规定是符合常规逻辑的。再看一个例子令P：学生不听话。（并指派为真）Q：老师管教学生。（并指派为真）于是P=0，Q=0，PQ：如果学生听话，那麽老师不管教学生，2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话0371678817923、P=1，Q=0,PQ=0即今天有雨，我没带雨没毛病，所以PQ=1。P=0，Q=1，PQ：如果学生听话，那麽老师管教学生。也没毛病，PQ=1；P=1，Q=0，PQ：如果学生不听话，那麽老师不管教学生。失败，所以PQ=0；最后一种情况：P=1，Q=1，PQ：如果学生不听话，那麽老师管教学生。没毛病PQ=1。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792没毛病，所以PQ=1。2.1命题逻辑与谓词逻辑郑州大学逻辑连接词双条件“”：如果P是一个命题，Q是一个命题，那麽PQ是一个命题，它的真值是这样定义的：2.1命题逻辑与谓词逻辑PQPQ001010100111当且仅当P和Q同号时PQ的值为真，否则为假。其真值表如下：郑州大学振动工程研究所电话037167881792逻辑连接词双条件“”：如果P是一个命题，Q是一个命题，那麽Q：老师管教学生。于是PQ表示老师管教学生当且仅当学生不听话。单条件和双条件逻辑连接词均是二元逻辑连接词。只要P，Q的真值定下来，P当且仅当Q的值就可以定下来。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792Q：老师管教学生。于是PQ表示老师管教学生当且仅当学生不逻辑连接词异或“”：如果P是一个命题，Q是一个命题，那麽PQ是一个命题，并且它的真值是这样定义的，当且仅当P和Q同号时，PQ的值为假否则为真。由定义我们可以看出，异或和逻辑连接词双条件“”有如下的关系：PQ¬（PQ）2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792逻辑连接词异或“”：如果P是一个命题，Q是一个命题，那麽P量词2.1命题逻辑与谓词逻辑在把实际问题符号化的过程中，我们会遇到那样的短语：1、所有的…;任何一个…;每一个…——allof……2、有一个…;有一些…;存在一个…——someof……我们使用量词进行符号化，谓词逻辑中引入两个量词来表达全称量词（用来表示）——表示所有（或任一个……）存在量词（用来表示）——表示存在（有某个……）郑州大学振动工程研究所电话037167881792量词2.1命题逻辑与谓词逻辑在把实际问题符号化的过程中，我例：用谓词逻辑符号化下列命题：所有的整数都是有理数；有些整数是素数；定义谓词：I(x):x是整数

Q(x):x是有理数

S(x):x是素数于是上述命题可符号化为：（x)(I(x)Q(x));(x)(I(x)

S(x)).2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792例：用谓词逻辑符号化下列命题：2.1命题逻辑与谓词逻辑郑州谓词公式（把实际问题符号化，公式化）命题演算的公式称为合式公式，又称命题公式，合式公式可按下列规则生成：(1)单个谓词是合式公式，称为原子谓词公式。(2)如果A是合式公式，则¬A是合式公式。(3)如果A和B是合式公式，那麽AB，AB，AB，AB是合式公式。(4)当且仅当有限次使用(1)、(2)、(3)条规则、由圆括号、逻辑连接词所组成的有意义的字符串是合式公式。(5)若A是合式公式，x是个体变元。则(x)A和(x)A也是合式公式。2.1.4.谓词公式及谓词公式的解释郑州大学振动工程研究所电话037167881792谓词公式（把实际问题符号化，公式化）2.1.4.谓词公式及谓根据上面的定义可以看出下面的字符串均是合式公式：P，¬P，PQ，¬P（PQ），¬P（PQ）R，（PQ）¬（¬P¬Q）。而下面的字符串则不是合式公式：¬P，R，¬P，（PQ））逻辑连接词的运算优先级为：¬、

、、、,括号优先。把一个实际问题符号化为一个命题公式的步骤如下：1.确定给定的句子是否为命题。2.找出各原子命题并确定句子中的连词对应的逻辑连结词。3.用正确的语法把原命题表示成由原子命题、连结词和圆括号组成的合式公式。2.1.4.谓词公式及谓词公式的解释郑州大学振动工程研究所电话037167881792根据上面的定义可以看出下面的字符串均是合式公式：2.1.4.例1：符号化下列命题：他既聪明又用功。他虽聪明但不用功。解：令P：他聪明Q：他用功于是PQ：表示他既聪明又用功。

P¬Q：表示他虽聪明但不用功。例2：符号化下列命题：老骥自知夕阳晚，无须扬鞭自奋蹄。解：令P：老骥自知夕阳晚Q：无须扬鞭自奋蹄P

Q：老骥自知夕阳晚，无须扬鞭自奋蹄。2.1.4.谓词公式及谓词公式的解释郑州大学振动工程研究所电话037167881792例1：符号化下列命题：2.1.4.谓词公式及谓词公式的解释郑谓词公式的解释：在命题逻辑中，对命题公式中各个命题变元的一次真值指派称为命题公式的一个解释。不同的变元真值赋值得到不同的命题公式解释，一个解释对应一个命题公式的真值。看下面的例子。2.1.4.谓词公式及谓词公式的解释郑州大学振动工程研究所电话037167881792谓词公式的解释：2.1.4.谓词公式及谓词公式的解释郑州大学设个体域D＝{1,2},求公式A＝(x)(y)P(x,y)在D上的解释，并指出在每一种解释下公式A的真值。指派一组真值：P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F,这是其中的一个解释，在此解释下，x=1和x=2时分别有P(1,1)和P(2,1)=T，即对于个体域中的所有x都有y使得P(x,y)=T,所以在这种解释下公式A的值为T。还可以指派另外一组真值：P(1,1)=T,P(1,2)=T,P(2,1)=F,P(2,2)=F,这时公式A的值为F.这样的真值指派共有16种2.1.4.谓词公式及谓词公式的解释郑州大学振动工程研究所电话037167881792设个体域D＝{1,2},求公式A＝(x)(y)P(x,定义：设A、B是两个命题公式，P1，P2，，Pn

是出现在A和B中的所有命题变元。如果对于P1，P2，，Pn的2n

个真值指派的每一组，公式A和B的真值相同，则称A和B等价。记作AB。显然，要判断两个命题公式是否等价，用真值表法即可以实现。但是当命题变元多时这种方法是不方便的。例如两个公式若含有4个变元，则真值表要列出24行。所以，我们一般不采用这种方法，而是采用等价变换的方法。下面列出的是常用的一组等价变换公式。2.1.4.谓词公式的等价性郑州大学振动工程研究所电话037167881792定义：设A、B是两个命题公式，P1，P2，，Pn是出现在2.1.4.谓词公式的等价性常用等价变换公式：1、¬¬PP双重否定律2、PPP，P

PP等幂律3、（PQ）RP（QR）结合律

（P

Q）RP（QR）4、PQQP,P

QQ

P交换律5、P（QR）（PQ）（PR）分配律P（QR）（PQ）（PR）6、P（PQ）P吸收律P（PQ）P郑州大学振动工程研究所电话0371678817922.1.4.谓词公式的等价性常用等价变换公式：郑州大学振动工2.1.4.谓词公式的等价性7、¬（PQ）¬P¬Q德.摩根律

¬（PQ）¬P¬Q8、PQ¬PQ，连接词化归律

PQ(PQ)(QP)

PQ(PQ)（¬P¬Q）9、(x)(PQ)(x)P(x)Q量词分配律

(x)(PQ)(x)P(x)Q10、¬(x)P(x)(¬P),量词转换律

¬(x)P(x)(¬P),11、P¬PT，P¬PF补余律郑州大学振动工程研究所电话0371678817922.1.4.谓词公式的等价性7、¬（PQ）¬P下面我们给出子公式，及关于公式等价的一个定理。定义：设A是一个命题公式，A是A的一部分，且A也是一个命题公式，则称A是A的子公式。定理：设A是公式A的子公式，B是一命题公式且AB，将A中的A用B来取代，则所得到的是一个新公式，

记为B，且AB。例1：证明（P(QR))(PQR)P证明：左边(P(QR))(P(QR))

P((QR)

(QR))

PTP.2.1.4.谓词公式的等价性郑州大学振动工程研究所电话037167881792下面我们给出子公式，及关于公式等价的一个定理。2.1.4.谓2.1.5永真式、永假式及蕴涵式一个命题公式若含有N个变元，则应有2n种组合，所以要证明两个命题公式的等价，当命题变元多时使用真值表法是不现实的，只能采用上面的等价变换的方法。有两种特殊的命题公式值得一提，即不依赖变元的真值指派总是取值为T的公式(称为永真式)，不依赖变元的真值指派总是取值为F的公式(称为永假式)，其余的情况则为可满足的式子。例如：PPT,PPF永真式与永假式取决于公式本身的结构，不依赖变元的真值指派。例如(PQR)(PQR)就是一个永真式(PQR)(PQR)就是一个永假式永真式的性质：若公式A是永真式，并且P1，P2，…，Pn是出现于A中的变元，若用公式B代换A中的原子变元Pi(i=1,2,…,n),所得到的公式设为A’，则A’也是永真式。（注意代换过程从左向右要进行到底）。对非永真式，这条性质不一定成立。

郑州大学振动工程研究所电话0371678817922.1.5永真式、永假式及蕴涵式一个命题公式若含有N个变元，定义：当且仅当AB是一个永真式时，则称A蕴涵B，记作AB.要证明AB.只要证明A为真时B必为真即可，也可以使用真值表来证明。即证明使A为真的那些组真值指派必然使B取值为真。下面是一些常用的永真蕴涵式：1）PQP,PQQ化简式2）PPQ,QPQ附加式3)PPQ,QPQ4)(PQ)P,(PQ)Q5)P(PQ)Q,Q(PQ)P6)P(PQ)Q7)(PQ)(QR)PR8)(PQ)(PR)(QR)R2.1.5永真式、永假式及蕴涵式郑州大学振动工程研究所电话037167881792定义：当且仅当AB是一个永真式时，则称A蕴涵B，记作AB以上永真蕴涵公式的证明，均可以从定义出发：例如证明3）:PPQ,QPQ前件为真时P为假，于是使得PQ必为真，同理：Q为真时使得PQ必为真。再如证明5）:P(PQ)Q,Q(PQ)P

P和(PQ)同时为真时，保证了Q必为真。同理，Q为真，Q就为假，PQ又为真，P就得为假，于是保证了P为真。2.1.5永真式、永假式及蕴涵式郑州大学振动工程研究所电话037167881792以上永真蕴涵公式的证明，均可以从定义出发：2.1.5永真式、等价式与永真蕴涵式之间的联系：设P，Q是命题公式，PQ的充分必要条件是：PQ且QP。永真蕴涵具有传递性：即PQ且QR则PR。同理等价关系也具有传递性：PQ且QR则有PR。定义1.4-2假设H1,…,Hm,Q是命题公式。如果（H1…

Hm）Q，则称H1,…,Hm共同蕴涵Q，并记作H1,…,HmQ定理：如果H1…

Hm

PQ，则H1,…,HmPQ定理是显然的：H1…

Hm

P为真，保证了P为真，H1…

Hm

PQ，保证了Q为真，于是有PQ为真，得证。2.1.5永真式、永假式及蕴涵式郑州大学振动工程研究所电话037167881792等价式与永真蕴涵式之间的联系：2.1.5永真式、永假式及蕴涵2.2多值逻辑经典的命题逻辑和谓词逻辑的语义解释只有2个真值：TorF，而在现实世界中，并非都是非真即假的情况，真真假假，有真有假的情况时常存在，所以，它们不能完全描述客观世界的真实情况，在经典逻辑的基础上提出了多值逻辑。用T(A)表示命题A为真的程度。T(A)的取值介于0(假)与1(真)之间：0≤T(A)≤1多值逻辑的运算：T(A)=1-T(A)T(AB)=min{T(A),T(B)}T(AB)=max

{T(A),T(B)}T(AB)=min{1,1-T(A)+T(B)}T(AB)=1-|T(A)-T(B)|郑州大学振动工程研究所电话0371678817922.2多值逻辑经典的命题逻辑和谓词逻辑的语义解释只有2个真2.2多值逻辑三值逻辑是多值逻辑的一个特例，有关真值表在书上有解释,书中表2-2所示。三值逻辑的真值：除了“真”、“假”外，还存在另一个真值，第三个真值根据具体含义有不同的意义：不能判断其真假：但真假必选其一，非真即假。不确定：不真也不假，无法确定其真值，或者就不存在真值。无意义：非真非假郑州大学振动工程研究所电话0371678817922.2多值逻辑三值逻辑是多值逻辑的一个特例，有关真值表在书在三值逻辑中，对于命题P和Q，由连接词“与”（）、“或”（）、“非”（）、“蕴涵”（→）和“等价”（↔）所构成的复合命题与二值逻辑中复合命题的定义完全相同，所不同的仅仅是命题P和Q及其复合命题的真假值域由原来的二值{0，1}变为三值{0，1/2，1}。于是复合命题的真假值可由下表给出。2.2多值逻辑郑州大学振动工程研究所电话037167881792在三值逻辑中，对于命题P和Q，由连接词“与”（）2.2多值逻辑三值逻辑运算PQPQPQPQP→QP↔Q1100111111/201/21/211/21/2100101001/211/201/2111/21/21/21/21/21/21/2111/201/2101/21/21/20110011001/211/201/211/200110011郑州大学振动工程研究所电话0371678817922.2多值逻辑三值逻辑运算PQPQPQP2.2多值逻辑根据上表，我们不难得到（P→Q）→Q、PP以及PP的真假值，见下表。PQPP→Q（P→Q）→QPPPP110110111/201/210110001011/211/2111/21/21/21/21/211/21/21/21/201/21/21/21/21/2011110101/2111/2010011001郑州大学振动工程研究所电话0371678817922.2多值逻辑根据上表，我们不难得到（P→Q）→Q、P二值逻辑是用0和1两个值来表示命题的真或假。三值逻辑则是将区间[0，1]二等分，并在中间增加一个值1/2来表示命题的不确定性。如果我们将区间[0，1]分成n-1等分（），并用

作为命题的真假值域，这样一个命题就可有多个取值。象这样可在中取多个值的命题称为多值逻辑。由上式知，当n=2时，有2.2多值逻辑就是2值逻辑郑州大学振动工程研究所电话037167881792二值逻辑是用0和1两个值来表示命题的真或假。三值逻辑则是将区当n=3时，有当n=9时，有在n=9时，若命题P和命题Q的值分别为P=3/8,和Q=7/8，则P和Q的复合命题的值为P=1-3/8=5/82.2多值逻辑郑州大学振动工程研究所电话037167881792当n=3时，有2.2多值逻辑郑州大学振动工程研究所PQ=PQ=P→Q=min（1，1+Q-P）=P↔Q=1-=1-当n→时，区间[0，1]就被所有实数充满。此时命题的真假值域就变为整个[0，1]区间，即。象这样命题的真假值域为整个[0，1]区间的多值逻辑称为无限值逻辑。2.2多值逻辑郑州大学振动工程研究所电话037167881792PQ=2.2多值逻辑郑州大学振动工程研究所2.3概率论概率论是研究随机现象中数量规律的科学，是研究事物的一种不确定性——随机性。我们在其他课程中学过，此处略去，自己看书。郑州大学振动工程研究所电话0371678817922.3概率论概率论是研究随机现象中数量规律的科学，是研究事李凌均郑州大学振动工程研究所十二月22第二章人工智能的数学基础李凌均第二章人工智能的数学基础45第二章人工智能的数学基础人工智能的数学基础有：逻辑学、概率论、模糊理论。逻辑经典命题逻辑一阶谓词逻辑2.1命题逻辑与谓词逻辑2.2多值逻辑2.3概率论2.4模糊理论非经典逻辑多值逻辑、模糊逻辑模态逻辑、时态逻辑具有真假意义本章内容：郑州大学振动工程研究所电话037167881792第二章人工智能的数学基础人工智能的数学基础有：逻辑学、概率2.2.1.命题一个具有真假意义的陈述句，称为命题。命题通常用大写的英文字母P，Q，R等来表示,命题是具有或真或假的含义的。如果一个命题的真值为真则用T(或1)表示，若为假则用F(或0)表示下面的例子均是命题：(1)郑州大学是一所综合性大学。（T）(2)2+2=5（F）。(3)今天是个好天气。（T）(4)每一个奇数都是素数。（F）2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话0371678817922.2.1.命题2.1命题逻辑与谓词逻辑郑州大学振动工程下面的例子都不是命题：(1)现在是几点钟？(疑问句）(2)x-y>2（其真假值随x、y的变化而变化，不能确定。）(3)我在说假话。（悖论，真作假时假亦真，假作真时真亦假）(4)请安静！（祈使句）2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792下面的例子都不是命题：2.1命题逻辑与谓词逻辑郑州大学振动命题逻辑的局限性：

在命题逻辑中我们研究的最小单位是句子,即命题，它无法把所要描述的客观事物的结构及逻辑关系反映出来。也无法把不同对象的共同特征表述出来。很多问题仅用命题逻辑是解决不了的、表达不清的。由此发展了谓词逻辑。2.1.2.谓词：在谓词逻辑中引入谓词来表示命题。一个谓词分为谓词名和个体2部分，谓词用于描述个体的性质、状态或个体之间的关系。个体就是要被描述的某个独立存在的事物或某个抽象的概念。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792命题逻辑的局限性：2.1.2.谓词：在谓词逻辑中引入谓词来表例1：张华是大学生。其中“张华”是个体，“是大学生”是谓语。于是我们可引入一个谓词S（x)来表示x是大学生，张华代以x就表示张华是大学生。S（x)涉及到一个变元，称为一元谓词，一元谓词表示个体的属性。例2：张华比李玲高。其中“张华”和“李玲”是个体，“…比…高”是谓词，因为涉及到两个个体，所以我们可以用一个二元谓词G（x,y)表示x高于y,将张华代以x,李玲代以y,则表示张华比李玲高。若用李玲代以x,张华代以y,则表示李玲高于张华。也就是说谓词中客体变元的顺序一经定义就不能随意改变了。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792例1：张华是大学生。其中“张华”是个体，“是大学生”是谓语。有多个变元的谓词称为多元谓词，多元谓词表示多个客体之间的关系。谓词中的个体可以是常量，也可以是变元或函数。谓词的语义是由使用者定义的，一旦被定义意义就明确。当谓词中的变元全部用特定的个体取代时，谓词就有了确定的真值TorF。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792有多个变元的谓词称为多元谓词，多元谓词表示多个客体之间的关系连接词象在整数或实数集合上可以进行+，-，*，/运算一样，在命题集合上也可以进行运算，形成新的命题。常用的命题运算符亦称为连接词有:¬：非

：合取(与)， ：析取(或)， ：条件或蕴涵， ：双条件(当且仅当)2.1命题逻辑与谓词逻辑2.1.3.谓词公式：郑州大学振动工程研究所电话037167881792连接词2.1命题逻辑与谓词逻辑2.1.3.谓词公式：郑州逻辑连接词非“¬”：如果P是一个命题，那麽¬P是一个命题，它的真值是这样定义的：P真(1)，¬P假；P假(0)，¬P真。可以用如下的一个所谓真值表来表示：这里应该注意的是¬P是对整个命题P的否定，而不是对命题P的部分成分否定。¬是一个一元逻辑连接词。2.1命题逻辑与谓词逻辑P¬P0110郑州大学振动工程研究所电话037167881792逻辑连接词非“¬”：如果P是一个命题，那麽¬P是一个命题，它逻辑连接词合取“”：如果P是一个命题，Q是一个命题，那麽PQ是一个命题，它的真值是这样定义的：当且仅当P和Q同时为真时，PQ的值为真，其余情况均为假。2.1命题逻辑与谓词逻辑PQPQ000010100111其真值表如右：“”是一个二元逻辑连接词。这是一个复合命题，可以读作合取或“和”、“and”。郑州大学振动工程研究所电话037167881792逻辑连接词合取“”：如果P是一个命题，Q是一个命题，那麽P例如令P：曹老师是教授。

Q：王晓离散数学不及格。则PQ：曹老师是教授并且王晓离散数学不及格注意这两件事在日常生活中可能是毫不相干的事情，但在命题逻辑中是有意义的，即P和Q的真值定下来，PQ的真值就可求。再例如令P：今天是晴天。

Q：欢欢是大熊猫。于是PQ：今天是晴天并且欢欢是大熊猫。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792例如令P：曹老师是教授。2.1命题逻辑与谓词逻辑郑州大学振逻辑连接词析取“”:如果P是一个命题，Q是一个命题，那麽PQ是一个命题，并且它的真值是这样定义的：当且仅当P和Q同时为假的时候PQ的值才为假，否则其值为真。其真值表如下：2.1命题逻辑与谓词逻辑PQPQ000011101111“”可以读作析取也可以读作“或”、“or”

，它是个二元逻辑连接词。但它仅代表日常生活中的可兼容或，不代表排斥或。郑州大学振动工程研究所电话037167881792逻辑连接词析取“”:如果P是一个命题，Q是一个命题，那麽P例如令P：今天下午3点我去讲课。

Q：今天下午3点我去游泳。日常生活中可能会说，今天下午3点我去讲课或今天下午3点我去游泳。这里的或是一种排斥或(也称异或），不能使用逻辑连接词“”来表示，也就是说不能用PQ：来表示今天下午3点我去讲课或今天下午3点我去游泳。但下面的例子可以用析取来表示。P：李明在教室。Q：王鹏去公园。于是PQ表示：李明在教室或王鹏去公园。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792例如令P：今天下午3点我去讲课。2.1命题逻辑与谓词逻辑郑逻辑连接词单条件“”：如果P是一个命题，Q是一个命题，那麽PQ是一个命题，表示P蕴涵Q，即：如果P，则Q。P成为条件的前件，Q成为条件的后件。它的真值是这样定义的：PQPQ001011100111当且仅当前件为真后件为假的时候，PQ的值才为假，其余情况均为真。其真值表如右：

2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792逻辑连接词单条件“”：如果P是一个命题，Q是一个命题，那麽例如令P：今天有雨。Q：我带雨伞。于是PQ：如果今天有雨，那麽我带雨伞。如果我们指定P为真代表今天有雨，那麽P为假表示今天没有雨，指定Q真为我带雨伞，那麽我没带雨伞为Q假。现在我们来分析上面真值表的各种情况：1、P=0，Q=0即今天没雨，我没带雨伞。PQ=1即成功。2、P=0，Q=1即今天没雨，我带雨伞。PQ=1也成功（带雨伞也没错）2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792例如令P：今天有雨。Q：我带雨伞。2.1命题逻辑与谓词逻3、P=1，Q=0,PQ=0即今天有雨，我没带雨伞，挨淋，失败。4、P=1，Q=1,PQ=1即今天有雨，我带雨伞。成功。由上面的例子可以看出，

PQ真值的规定是符合常规逻辑的。再看一个例子令P：学生不听话。（并指派为真）Q：老师管教学生。（并指派为真）于是P=0，Q=0，PQ：如果学生听话，那麽老师不管教学生，2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话0371678817923、P=1，Q=0,PQ=0即今天有雨，我没带雨没毛病，所以PQ=1。P=0，Q=1，PQ：如果学生听话，那麽老师管教学生。也没毛病，PQ=1；P=1，Q=0，PQ：如果学生不听话，那麽老师不管教学生。失败，所以PQ=0；最后一种情况：P=1，Q=1，PQ：如果学生不听话，那麽老师管教学生。没毛病PQ=1。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792没毛病，所以PQ=1。2.1命题逻辑与谓词逻辑郑州大学逻辑连接词双条件“”：如果P是一个命题，Q是一个命题，那麽PQ是一个命题，它的真值是这样定义的：2.1命题逻辑与谓词逻辑PQPQ001010100111当且仅当P和Q同号时PQ的值为真，否则为假。其真值表如下：郑州大学振动工程研究所电话037167881792逻辑连接词双条件“”：如果P是一个命题，Q是一个命题，那麽Q：老师管教学生。于是PQ表示老师管教学生当且仅当学生不听话。单条件和双条件逻辑连接词均是二元逻辑连接词。只要P，Q的真值定下来，P当且仅当Q的值就可以定下来。2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792Q：老师管教学生。于是PQ表示老师管教学生当且仅当学生不逻辑连接词异或“”：如果P是一个命题，Q是一个命题，那麽PQ是一个命题，并且它的真值是这样定义的，当且仅当P和Q同号时，PQ的值为假否则为真。由定义我们可以看出，异或和逻辑连接词双条件“”有如下的关系：PQ¬（PQ）2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792逻辑连接词异或“”：如果P是一个命题，Q是一个命题，那麽P量词2.1命题逻辑与谓词逻辑在把实际问题符号化的过程中，我们会遇到那样的短语：1、所有的…;任何一个…;每一个…——allof……2、有一个…;有一些…;存在一个…——someof……我们使用量词进行符号化，谓词逻辑中引入两个量词来表达全称量词（用来表示）——表示所有（或任一个……）存在量词（用来表示）——表示存在（有某个……）郑州大学振动工程研究所电话037167881792量词2.1命题逻辑与谓词逻辑在把实际问题符号化的过程中，我例：用谓词逻辑符号化下列命题：所有的整数都是有理数；有些整数是素数；定义谓词：I(x):x是整数

Q(x):x是有理数

S(x):x是素数于是上述命题可符号化为：（x)(I(x)Q(x));(x)(I(x)

S(x)).2.1命题逻辑与谓词逻辑郑州大学振动工程研究所电话037167881792例：用谓词逻辑符号化下列命题：2.1命题逻辑与谓词逻辑郑州谓词公式（把实际问题符号化，公式化）命题演算的公式称为合式公式，又称命题公式，合式公式可按下列规则生成：(1)单个谓词是合式公式，称为原子谓词公式。(2)如果A是合式公式，则¬A是合式公式。(3)如果A和B是合式公式，那麽AB，AB，AB，AB是合式公式。(4)当且仅当有限次使用(1)、(2)、(3)条规则、由圆括号、逻辑连接词所组成的有意义的字符串是合式公式。(5)若A是合式公式，x是个体变元。则(x)A和(x)A也是合式公式。2.1.4.谓词公式及谓词公式的解释郑州大学振动工程研究所电话037167881792谓词公式（把实际问题符号化，公式化）2.1.4.谓词公式及谓根据上面的定义可以看出下面的字符串均是合式公式：P，¬P，PQ，¬P（PQ），¬P（PQ）R，（PQ）¬（¬P¬Q）。而下面的字符串则不是合式公式：¬P，R，¬P，（PQ））逻辑连接词的运算优先级为：¬、

、、、,括号优先。把一个实际问题符号化为一个命题公式的步骤如下：1.确定给定的句子是否为命题。2.找出各原子命题并确定句子中的连词对应的逻辑连结词。3.用正确的语法把原命题表示成由原子命题、连结词和圆括号组成的合式公式。2.1.4.谓词公式及谓词公式的解释郑州大学振动工程研究所电话037167881792根据上面的定义可以看出下面的字符串均是合式公式：2.1.4.例1：符号化下列命题：他既聪明又用功。他虽聪明但不用功。解：令P：他聪明Q：他用功于是PQ：表示他既聪明又用功。

P¬Q：表示他虽聪明但不用功。例2：符号化下列命题：老骥自知夕阳晚，无须扬鞭自奋蹄。解：令P：老骥自知夕阳晚Q：无须扬鞭自奋蹄P

Q：老骥自知夕阳晚，无须扬鞭自奋蹄。2.1.4.谓词公式及谓词公式的解释郑州大学振动工程研究所电话037167881792例1：符号化下列命题：2.1.4.谓词公式及谓词公式的解释郑谓词公式的解释：在命题逻辑中，对命题公式中各个命题变元的一次真值指派称为命题公式的一个解释。不同的变元真值赋值得到不同的命题公式解释，一个解释对应一个命题公式的真值。看下面的例子。2.1.4.谓词公式及谓词公式的解释郑州大学振动工程研究所电话037167881792谓词公式的解释：2.1.4.谓词公式及谓词公式的解释郑州大学设个体域D＝{1,2},求公式A＝(x)(y)P(x,y)在D上的解释，并指出在每一种解释下公式A的真值。指派一组真值：P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F,这是其中的一个解释，在此解释下，x=1和x=2时分别有P(1,1)和P(2,1)=T，即对于个体域中的所有x都有y使得P(x,y)=T,所以在这种解释下公式A的值为T。还可以指派另外一组真值：P(1,1)=T,P(1,2)=T,P(2,1)=F,P(2,2)=F,这时公式A的值为F.这样的真值指派共有16种2.1.4.谓词公式及谓词公式的解释郑州大学振动工程研究所电话037167881792设个体域D＝{1,2},求公式A＝(x)(y)P(x,定义：设A、B是两个命题公式，P1，P2，，Pn

是出现在A和B中的所有命题变元。如果对于P1，P2，，Pn的2n

个真值指派的每一组，公式A和B的真值相同，则称A和B等价。记作AB。显然，要判断两个命题公式是否等价，用真值表法即可以实现。但是当命题变元多时这种方法是不方便的。例如两个公式若含有4个变元，则真值表要列出24行。所以，我们一般不采用这种方法，而是采用等价变换的方法。下面列出的是常用的一组等价变换公式。2.1.4.谓词公式的等价性郑州大学振动工程研究所电话037167881792定义：设A、B是两个命题公式，P1，P2，，Pn是出现在2.1.4.谓词公式的等价性常用等价变换公式：1、¬¬PP双重否定律2、PPP，P

PP等幂律3、（PQ）RP（QR）结合律

（P

Q）RP（QR）4、PQQP,P

QQ

P交换律5、P（QR）（PQ）（PR）分配律P（QR）（PQ）（PR）6、P（PQ）P吸收律P（PQ）P郑州大学振动工程研究所电话0371678817922.1.4.谓词公式的等价性常用等价变换公式：郑州大学振动工2.1.4.谓词公式的等价性7、¬（PQ）¬P¬Q德.摩根律

¬（PQ）¬P¬Q8、PQ¬PQ，连接词化归律

PQ(PQ)(QP)

PQ(PQ)（¬P¬Q）9、(x)(PQ)(x)P(x)Q量词分配律

(x)(PQ)(x)P(x)Q10、¬(x)P(x)(¬P),量词转换律

¬(x)P(x)(¬P),11、P¬PT，P¬PF补余律郑州大学振动工程研究所电话0371678817922.1.4.谓词公式的等价性7、¬（PQ）¬P下面我们给出子公式，及关于公式等价的一个定理。定义：设A是一个命题公式，A是A的一部分，且A也是一个命题公式，则称A是A的子公式。定理：设A是公式A的子公式，B是一命题公式且AB，将A中的A用B来取代，则所得到的是一个新公式，

记为B，且AB。例1：证明（P(QR))(PQR)P证明：左边(P(QR))(P(QR))

P((QR)

(QR))

PTP.2.1.4.谓词公式的等价性郑州大学振动工程研究所电话037167881792下面我们给出子公式，及关于公式等价的一个定理。2.1.4.谓2.1.5永真式、永假式及蕴涵式一个命题公式若含有N个变元，则应有2n种组合，所以要证明两个命题公式的等价，当命题变元多时使用真值表法是不现实的，只能采用上面的等价变换的方法。有两种特殊的命题公式值得一提，即不依赖变元的真值指派总是取值为T的公式(称为永真式)，不依赖变元的真值指派总是取值为F的公式(称为永假式)，其余的情况则为可满足的式子。例如：PPT,PPF永真式与永假式取决于公式本身的结构，不依赖变元的真值指派。例如(PQR)(PQR)就是一个永真式(PQR)(PQR)就是一个永假式永真式的性质：若公式A是永真式，并且P1，P2，…，Pn是出现于A中的变元，若用公式B代换A中的原子变元Pi(i=1,2,…,n),所得到的公式设为A’，则A’也是永真式。（注意代换过程从左向右要进行到底）。对非永真式，这条性质不一定成立。

郑州大学振动工程研究所电话0371678817922.1.5永真式、永假式及蕴涵式一个命题公式若含有N个变元，定义：当且仅当AB是一个永真式时，则称A蕴涵B，记作AB.要证明AB.只要证明A为真时B必为真即可，也可以使用真值表来证明。即证明使A为真的那些组真值指派必然使B取值为真。下面是一些常用的永真蕴涵式：1）PQP,PQQ化简式2）PPQ,QPQ附加式3)PPQ,QPQ4)(PQ)P,(PQ)Q5)P(PQ)Q,Q(PQ)P6)P(PQ)Q7)(PQ)(QR)PR8)(PQ)(PR)(QR)R2.1.5永真式、永假式及蕴涵式郑州大学振动工程研究所电话037167881792定义：当且仅当AB是一个永真式时，则称A蕴涵B，记作AB以上永真蕴涵公式的证明，均可以从定义出发：例如证明3）:PPQ,QPQ前件为真时P为假，于是使得PQ必为真，同理：Q为真时使得PQ必为真。再如证明5）:P(PQ)Q,Q(PQ)P

P和(PQ)同时为真时，保证了Q必为真。同理，Q为真，Q就为假，PQ又为真，P就得为假，于是保证了P为真。2.1.5永真式、永假式及蕴涵式郑州大学振动工程研究所电话037167881792以上永真蕴涵公式的证明，均可以从定义出发：2.1.5永真式、等价式与永真蕴涵式之间的联系：设P，Q是命题公式，PQ的充分必要条件是：PQ且QP。永真蕴涵具有传递性：即PQ且QR则PR。同理等价关系也具有传递性：PQ且QR则有PR。定义1.4-2假设H1,…,Hm,Q是命题公式。如果（H1…

Hm）Q，则称H1,…,Hm共同蕴涵Q，并记作H1,…,HmQ定理：如果H1…

Hm

PQ，则H1,…,HmPQ定理是显然的：H1…

Hm

P为真，保证了P为真，H1…

Hm

PQ，保