资源描述：
《《计算机数学基础(1)》第二单元辅导.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《计算机数学基础（1）》第二单元辅导本单元重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明.集合概念，集合的运算，集合恒等式的证明，笛卡儿积.一、重点内容1.谓词与量词•谓词，在谓词逻辑屮，原子命题分解成个体词和谓词.个体词是可以独立存在的客体,它可以是具体事物或抽彖的概念。谓词是用來刻划个体词的性质或事物之间关系的词.个体词分个体常项（用必,C,...表示）和个体变项（用心忆,…表示）；谓词分谓词常项（表示具体性质和关系）和谓词变项（表示抽象的或泛指的谓词），用FGP,…表示.注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题.•量词，是在命题屮表示数量的词
2、，量词有两类：全称量词也表示“所有的”或“每一个”；存在量词日，表示“存在某个”或“至少有一个”•在谓词逻辑中，使用量词应注意以下儿点：（1）在不同个体域屮，命题符号化的形式可能不同，命题的真值也可能会改变.（2）在考虑命题符号化时，如果对个体域未作说明，一律使用全总个体域.（3）多个量词出现吋，不能随意颠倒它们的顺序，否则可能会改变命题的含义.谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成-个命题.所谓解释就是使公式屮的每一个变项都有个体域屮的元索相对应.在谓词逻辑屮，命题符号化必须明确个体域，无特别说明认为是全总个体域。一般地,使用全称量
3、词V,特性谓词后用T；使用存在量词弓，特性谓词后用入2.公式与解释•谓词公式，由原子公式、联结词和量词可构成谓词公式（严格定义见教材）.命题的符号化结果都是谓词公式.例如V龙,"（尸（劝“（力）,P畑ylFIDnF®Llx、劝t〃（乙y））等都是谓词公式.•变元与辖域，在谓词公式bxA和弘4屮,x是指导变元，人是相应最词的辖域.在Vx和％的辖域4屮，x的所有出现都是约束出现，即尤是约束变元，不是约束岀现的变元，就是自由变元.也就是说，量词后血的式子是辖域.量词只对辖域内的同一变元有效.•换名规则，就是把公式屮量词的指导变元及其辖域屮的该变元换成该公式屮没有出现的个体变元，公式的其
4、余部分不变.•代入规则，就是把公式屮的某一白由变元，用该公式中没有出现的个体变元符号替代,且要把该公式中所有的该白由变元都换成新引入的这个符号.•解释（赋值），谓词公式4的个体域D是非空集合，则（1）每一个常项指定D屮一个元素；（2）每一个舁元函数指定D'1到D的一个函数；（3）每一个n元谓词指定D"到｛0,1｝的一个谓词；按这个规则做的一组指派，称为A的一个解释或赋值.在有限个体域下，消除量词的规则为：如D={4,d2,...,d“}，贝UVxA(x)<=>)aA(a2)a...aA(an)3xA(x)<=>A(a})vA(6f2)v...vA(alt)•谓词公式分类，在任何解释
5、下，谓词公式A取真值1,公式A为逻辑有效武（永真武）；在任何解释下谓词公式A取真值0,公式A为永假式；至少有一个解秣使公式4取真值1,公式4称为可满足式.3•前束范式一个谓词公式的前束范式仍是谓词公式.若谓词公式F等值地转化成Q入"1…Qf；xpB那么Q]xlQ2x2...QkxkB就是F的前束范式，其中0i，@，…，0只能是b或玉X]/2,...Kt是个体变元，B是不含量词的谓词公式.每个谓词公式尸都可以变换成与它等值的前束范式.其步骤如下：%1消去联结词<->,V；%1将联结词「移至原子谓词公式之前；%1利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符
6、号也不同；%1将0x,3x移至整个公式最左边；%1得到公式的前束范式.4•谓词逻辑的推理理论谓词演算的推理是命题演算推理的推广和扩充，命题演算屮的基本等值公式，重言蕴含式以及P,T,CP规则在谓词演算屮仍然使用.在谓词演算推理屮，某些前提和结论可能受到最词的限制，为了使用这些推理，引入消去和附加量词的规则，有VS规则(全称量词消去规则)，规则(全称量词附加规则)，ES规则(存在量词消去规则)，EG规则(存在量词附加规则)等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行.二、实例例2・1将下列命题符号化：(1)有某些实数是有理数；(2)所有的人都呼吸；⑶每个母亲都爱自己的孩
7、子.注意：一般地，全称量词“X/”后，跟蕴含联结词“T”；存在量词T”后，跟合取联结词“△”・解(1)设X是实数，Q(x)：x是有理数。该命题符号化3x(/?(x)Ae(x)).(2)设全总个体域，设A/(x)：X是人.，H(x)：x要呼吸，该命题符号化为：Vx(W)->//W)该命题等价说法：“不存在不需要呼吸的人”，符号化为：「mx(M(x)A「H(x)).其实它们是等值的，Vx(A/(x)->H(x))-i-.F(x))o「(->Vx(-1M(x)vH(x
