人工智能的数学基础

李凌均郑州大学振开工程研讨所六月22第二章人工智能的数学根底第二章人工智能的数学根底人工智能的数学根底有：逻辑学、概率论、模糊实际。逻辑经典命题逻辑一阶谓词逻辑2.1命题逻辑与谓词逻辑2.2多值逻辑2.3概率论2.4模糊实际非经典逻辑多值逻辑、模糊逻辑模态逻辑、时态逻辑具有真假意义本章内容：郑州大学振开工程研讨所0371678817922.2.1.命题一个具有真假意义的陈说句，称为命题。命题通常用大写的英文字母P，Q，R等来表示,命题是具有或真或假的含义的。假设一个命题的真值为真那么用T(或1)表示，假设为假那么用F(或0)表示下面的例子均是命题：(1)郑州大学是一所综合性大学。〔T〕(2)2+2=5〔F〕。(3)今天是个好天气。〔T〕(4)每一个奇数都是素数。〔F〕2.1命题逻辑与谓词逻辑郑州大学振开工程研讨所037167881792下面的例子都不是命题：(1)如今是几点钟？(疑问句〕(2)x-y>2〔其真假值随x、y的变化而变化，不能确定。〕(3)我在说假话。〔悖论，真作假时假亦真，假作真时真亦假〕(4)请安静！〔祈使句〕2.1命题逻辑与谓词逻辑郑州大学振开工程研讨所037167881792命题逻辑的局限性：在命题逻辑中我们研讨的最小单位是句子,即命题，它无法把所要描画的客观事物的构造及逻辑关系反映出来。也无法把不同对象的共同特征表述出来。很多问题仅用命题逻辑是处理不了的、表达不清的。由此开展了谓词逻辑。2.1.2.谓词：在谓词逻辑中引入谓词来表示命题。一个谓词分为谓词名和个体2部分，谓词用于描画个体的性质、形状或个体之间的关系。个体就是要被描画的某个独立存在的事物或某个笼统的概念。2.1命题逻辑与谓词逻辑郑州大学振开工程研讨所037167881792例1：张华是大学生。其中“张华〞是个体，“是大学生〞是谓语。于是我们可引入一个谓词S〔x)来表示x是大学生，张华代以x就表示张华是大学生。S〔x)涉及到一个变元，称为一元谓词，一元谓词表示个体的属性。例2：张华比李玲高。其中“张华〞和“李玲〞是个体，“…比…高〞是谓词，由于涉及到两个个体，所以我们可以用一个二元谓词G〔x,y)表示x高于y,将张华代以x,李玲代以y,那么表示张华比李玲高。假设用李玲代以x,张华代以y,那么表示李玲高于张华。也就是说谓词中客体变元的顺序一经定义就不能随意改动了。2.1命题逻辑与谓词逻辑郑州大学振开工程研讨所037167881792有多个变元的谓词称为多元谓词，多元谓词表示多个客体之间的关系。谓词中的个体可以是常量，也可以是变元或函数。谓词的语义是由运用者定义的，一旦被定义意义就明确。当谓词中的变元全部用特定的个体取代时，谓词就有了确定的真值TorF。2.1命题逻辑与谓词逻辑郑州大学振开工程研讨所037167881792衔接词象在整数或实数集合上可以进展+，-，*，/运算一样，在命题集合上也可以进展运算，构成新的命题。常用的命题运算符亦称为衔接词有:¬：非 ：合取(与)， ：析取(或)， ：条件或蕴涵， ：双条件(当且仅当)2.1命题逻辑与谓词逻辑2.1.3.谓词公式：郑州大学振开工程研讨所037167881792逻辑衔接词非“¬〞：假设P是一个命题，那麽¬P是一个命题，它的真值是这样定义的：P真(1)，¬P假；P假(0)，¬P真。可以用如下的一个所谓真值表来表示：这里应该留意的是¬P是对整个命题P的否认，而不是对命题P的部分成分否认。¬是一个一元逻辑衔接词。2.1命题逻辑与谓词逻辑P¬P0110郑州大学振开工程研讨所037167881792逻辑衔接词合取“〞：假设P是一个命题，Q是一个命题，那麽PQ是一个命题，它的真值是这样定义的：当且仅当P和Q同时为真时，PQ的值为真，其他情况均为假。2.1命题逻辑与谓词逻辑PQP

Q000010100111其真值表如右：“〞是一个二元逻辑衔接词。这是一个复合命题，可以读作合取或“和〞、“and〞。郑州大学振开工程研讨所037167881792例如令P：曹教师是教授。Q：王晓离散数学不及格。那么PQ：曹教师是教授并且王晓离散数学不及格留意这两件事在日常生活中能够是毫不相关的事情，但在命题逻辑中是有意义的，即P和Q的真值定下来，PQ的真值就可求。再例如令P：今天是晴天。Q：欢欢是大熊猫。于是PQ：今天是晴天并且欢欢是大熊猫。2.1命题逻辑与谓词逻辑郑州大学振开工程研讨所037167881792逻辑衔接词析取“〞:假设P是一个命题，Q是一个命题，那麽PQ是一个命题，并且它的真值是这样定义的：当且仅当P和Q同时为假的时候PQ的值才为假，否那么其值为真。其真值表如下：2.1命题逻辑与谓词逻辑PQP

Q000011101111“〞可以读作析取也可以读作“或〞、“or〞，它是个二元逻辑衔接词。但它仅代表日常生活中的可兼容或，不代表排斥或。郑州大学振开工程研讨所037167881792例如令P：今天下午3点我去讲课。Q：今天下午3点我去游泳。日常生活中能够会说，今天下午3点我去讲课或今天下午3点我去游泳。这里的或是一种排斥或(也称异或〕，不能运用逻辑衔接词“〞来表示，也就是说不能用PQ：来表示今天下午3点我去讲课或今天下午3点我去游泳。但下面的例子可以用析取来表示。P：李明在教室。Q：王鹏去公园。于是PQ表示：李明在教室或王鹏去公园。2.1命题逻辑与谓词逻辑郑州大学振开工程研讨所037167881792逻辑衔接词单条件“〞：假设P是一个命题，Q是一个命题，那麽PQ是一个命题，表示P蕴涵Q，即：假设P，那么Q。P成为条件的前件，Q成为条件的后件。它的真值是这样定义的：PQP

Q001011100111当且仅当前件为真后件为假的时候，PQ的值才为假，其他情况均为真。其真值表如右：2.1命题逻辑与谓词逻辑郑州大学振开工程研讨所037167881792例如令P：今天有雨。Q：我带雨伞。于是PQ：假设今天有雨，那麽我带雨伞。假设我们指定P为真代表今天有雨，那麽P为假表示今天没有雨，指定Q真为我带雨伞，那麽我没带雨伞为Q假。如今我们来分析上面真值表的各种情况：1、P=0，Q=0即今天没雨，我没带雨伞。PQ=1即胜利。2、P=0，Q=1即今天没雨，我带雨伞。PQ=1也胜利〔带雨伞也没错〕2.1命题逻辑与谓词逻辑郑州大学振开工程研讨所0371678817923、P=1，Q=0,PQ=0即今天有雨，我没带雨伞，挨淋，失败。4、P=1，Q=1,PQ=1即今天有雨，我带雨伞。胜利。由上面的例子可以看出，PQ真值的规定是符合常规逻辑的。再看一个例子令P：学生不听话。〔并指派为真〕Q：教师管教学生。〔并指派为真〕于是P=0，Q=0，PQ：假设学生听话，那麽教师不论教学生，2.1命题逻辑与谓词逻辑郑州大学振开工程研讨所037167881792没缺陷，所以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逻辑衔接词双条件“〞：假设P是一个命题，Q是一个命题，那麽PQ是一个命题，它的真值是这样定义的：2.1命题逻辑与谓词逻辑PQP

Q001010100111当且仅当P和Q同号时PQ的值为真，否那么为假。其真值表如下：郑州大学振开工程研讨所037167881792Q：教师管教学生。于是PQ表示教师管教学生当且仅当学生不听话。单条件和双条件逻辑衔接词均是二元逻辑衔接词。只需P，Q的真值定下来，P当且仅当Q的值就可以定下来。2.1命题逻辑与谓词逻辑郑州大学振开工程研讨所037167881792逻辑衔接词异或“〞：假设P是一个命题，Q是一个命题，那麽PQ是一个命题，并且它的真值是这样定义的，当且仅当P和Q同号时，PQ的值为假否那么为真。由定义我们可以看出，异或和逻辑衔接词双条件“〞有如下的关系：PQ¬〔PQ〕2.1命题逻辑与谓词逻辑郑州大学振开工程研讨所037167881792量词2.1命题逻辑与谓词逻辑在把实践问题符号化的过程中，我们会遇到那样的短语：1、一切的…;任何一个…;每一个…——allof……2、有一个…;有一些…;存在一个…——someof……我们运用量词进展符号化，谓词逻辑中引入两个量词来表达全称量词〔用来表示〕——表示一切〔或任一个……〕存在量词〔用来表示〕——表示存在〔有某个……〕郑州大学振开工程研讨所037167881792例：用谓词逻辑符号化以下命题：一切的整数都是有理数；有些整数是素数；定义谓词：I(x):x是整数Q(x):x是有理数S(x):x是素数于是上述命题可符号化为：〔x)(I(x)Q(x));(x)(I(x)S(x)).2.1命题逻辑与谓词逻辑郑州大学振开工程研讨所037167881792谓词公式〔把实践问题符号化，公式化〕命题演算的公式称为合式公式，又称命题公式，合式公式可按以下规那么生成：(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根据上面的定义可以看出下面的字符串均是合式公式：P，¬P，PQ，¬P〔PQ〕，¬P〔PQ〕R，〔PQ〕¬〔¬P¬Q〕。而下面的字符串那么不是合式公式：¬P，R，¬P，〔PQ〕〕逻辑衔接词的运算优先级为：¬、、、、,括号优先。把一个实践问题符号化为一个命题公式的步骤如下：1.确定给定的句子能否为命题。2.找出各原子命题并确定句子中的连词对应的逻辑连结词。3.用正确的语法把原命题表示成由原子命题、连结词和圆括号组成的合式公式。2.1.4.谓词公式及谓词公式的解释郑州大学振开工程研讨所037167881792例1：符号化以下命题：他既聪明又用功。他虽聪明但不用功。解：令P：他聪明Q：他用功于是PQ：表示他既聪明又用功。P¬Q：表示他虽聪明但不用功。例2：符号化以下命题：老骥自知夕阳晚，无须扬鞭自奋蹄。解：令P：老骥自知夕阳晚Q：无须扬鞭自奋蹄PQ：老骥自知夕阳晚，无须扬鞭自奋蹄。2.1.4.谓词公式及谓词公式的解释郑州大学振开工程研讨所037167881792谓词公式的解释：在命题逻辑中，对命题公式中各个命题变元的一次真值指派称为命题公式的一个解释。不同的变元真值赋值得到不同的命题公式解释，一个解释对应一个命题公式的真值。看下面的例子。2.1.4.谓词公式及谓词公式的解释郑州大学振开工程研讨所037167881792设个体域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定义：设A、B是两个命题公式，P1，P2，，Pn是出如今A和B中的一切命题变元。假设对于P1，P2，，Pn的2n个真值指派的每一组，公式A和B的真值一样，那么称A和B等价。记作AB。显然，要判别两个命题公式能否等价，用真值表法即可以实现。但是当命题变元多时这种方法是不方便的。例如两个公式假设含有4个变元，那么真值表要列出24行。所以，我们普通不采用这种方法，而是采用等价变换的方法。下面列出的是常用的一组等价变换公式。2.1.4.谓词公式的等价性郑州大学振开工程研讨所0371678817922.1.4.谓词公式的等价性常用等价变换公式：1、¬¬PP双重否认律2、PPP，PPP等幂律3、〔PQ〕RP〔QR〕结合律〔PQ〕RP〔QR〕4、PQQP,PQQP交换律5、P〔QR〕〔PQ〕〔PR〕分配律P〔QR〕〔PQ〕〔PR〕6、P〔PQ〕P吸收律P〔PQ〕P郑州大学振开工程研讨所0371678817922.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补余律郑州大学振开工程研讨所037167881792下面我们给出子公式，及关于公式等价的一个定理。定义：设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.谓词公式的等价性郑州大学振开工程研讨所0371678817922.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’也是永真式。〔留意代换过程从左向右要进展究竟〕。对非永真式，这条性质不一定成立。郑州大学振开工程研讨所037167881792定义：当且仅当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以上永真蕴涵公式的证明，均可以从定义出发：例如证明3〕:PPQ,QPQ前件为真时P为假，于是使得PQ必为真，同理：Q为真时使得PQ必为真。再如证明5〕:P(PQ)Q,Q(PQ)PP和(PQ)同时为真时，保证了Q必为真。同理，Q为真，Q就为假，PQ又为真，P就得为假，于是保证了P为真。2.1.5永真式、永假式及蕴涵式郑州大学振开工程研讨所037167881792等价式与永真蕴涵式之间的联络：设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…HmPQ，那么H1,…,HmPQ定理是显然的：H1…HmP为真，保证了P为真，H1…HmPQ，保证了Q为真，于是有PQ为真，得证。2.1.5永真式、永假式及蕴涵式郑州大学振开工程研讨所0371678817922.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所示。三值逻辑的真值：除了“真〞、“假〞外，还存在另一个真值，第三个真值根据详细含义有不同的意义：不能判别其真假：但真假必选其一，非真即假。不确定：不真也不假，无法确定其真值，或者就不存在真值。无意义：非真非假郑州大学振开工程研讨所037167881792在三值逻辑中，对于命题P和Q，由衔接词“与〞〔〕、“或〞〔〕、“非〞〔〕、“蕴涵〞〔→〕和“等价〞〔↔〕所构成的复合命题与二值逻辑中复合命题的定义完全一样，所不同的仅仅是命题P和Q及其复合命题的真假值域由原来的二值{0，1}变为三值{0，1/2，1}。于是复合命题的真假值可由下表给出。2.2多值逻辑郑州大学振开工程研讨所0371678817922.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多值逻辑根据上表，我们不难得到〔P→Q〕→