离散数学(讲习题课).pptVIP

* 计算机学院 * 实验1 题目：构造任意合式公式的真值表 1、功能：给出任意变元的合式公式，构造该合式公式的真值表 2、基本思想：以用数值变量表示命题变元为前提规范，合式公式的表示及求真值表采用通过将合式公式表示成为条件语句中的条件表达式，对每个赋值其合式公式的真值即为该合式公式的逻辑运算结果；使用一维数组a[N]表示合式公式中所出现的n个命题变元，同时它也是一个二进制加法器的模拟器，每当在这个模拟器中产生一个二进制数时，就相当于给各个命题变元产生了一组真值指派。 * 计算机学院 * 3、算法逻辑 将二进制加法模拟器赋初值， 计算模拟器中所对应的一组真值指派下合式公式的真值（条件语句）。 输出真值表中对应于模拟器所给出的一组真值指派及这组真值指派所对应的一行真值。 在模拟器a[N]中，模拟产生下一个二进制数值。 若a[N]中的数值等于2n ，则结束，否则转②。 4、要求 用C语言编写出相应的程序，并至少通过输入两个合 式公式进行验证，打印出结果。 计算机学院 计算机科学与工程学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * * 计算机学院 * * 计算机学院 * 一、基本概念 全总个体域（全论域）、全称量词、存在量词、特性谓词、指导（作用）变元、辖域（作用域）、约束变元、自由变元、约束变元的改名规则、自由变元的代入规则、常量符号、变量符号、函数符号、谓词符号、谓词公式、公式的解释、永真公式(重言式) 、永假公式(矛盾式，不可满足公式）、 第二章 * 计算机学院 * 可满足公式、前束范式、母式、前束合取(或析取)范式、Skolem范式、US(全称指定规则)、ES(存在指定规则)、UG(全称推广规则)、EG(存在推广规则) * 计算机学院 * 二、基本要求 能准确地将给定命题符号化 深刻理解全称量词、存在量词及量词的辖域、全总个体域的概念 能准确理解约束变元(量)和自由变元的概念 掌握约束变元的改名规则和自由变元的代入规则 * 计算机学院 * 掌握与量词相关的基本等价式和基本蕴涵式 能熟练地运用US、ES、UG、EG规则进行推理 * 计算机学院 * 语句的符号化 1、将下列命题翻译成谓词公式 每个有理数都是实数，但是并非每个实数都是有理数，有些实数是有理数。 A(x):x是实数 B(x):x是有理数 ?(x)(B(x)→A(x))∧??(x)(A(x)→B(x)) ∧?(x)(A(x)∧B(x)) 直线a和b平行当且仅当a和b不相交。 A(x):x是直线 F(x，y):x与y平行 　　G（x,y):ｘ与ｙ相交 　　?(ａ)?(ｂ)（A(ａ)∧A(ｂ)→ 　　　　　　　　　　　　(F(ａ，ｂ)??G（ａ,ｂ)）) * 计算机学院 * 除非所有会员都参加，这个活动才有意义。 　　A(x):ｘ是会员 　　B(x):x有意义　　　ａ：这个活动 　　F(x，y):ｘ参加ｙ 　　B（ａ）→?(x)（A(x)→F(x，ａ)） 　　或　??(x)（A(x)→F(x，ａ)）→?B（ａ） 任何正整数不是合数就是素数。 　　A(x):ｘ是正整数 　　Ｂ(x)：ｘ是合数 　　Ｃ(x)：ｘ是质数 　　　?(x)（A(x)→Ｂ(x)?Ｃ(x)） * 计算机学院 * 凡是存钱的人都想有利息，如果没有利息，人们就不会存钱。 A(x):ｘ是存钱的人 F(x，y):ｘ想有ｙ P：存钱没有利息 Q: 人们不存钱 a: 利息 ?(x)（A(x)→F(x，a)）∧（P→Q） * 计算机学院 * 2、把下列语句符号化，并确定相应谓词公式是永真式、可满足式，还是矛盾式。 如果两个数的积等于0，那么至少其中一个数为0，数x-1不等于0，所以数x-1和数x+1的积也不等于0。 　　A(x):ｘ＝０，ｆ（ｘ，ｙ）＝ｘｙ　 　?x?ｙ［A(ｆ（x，ｙ)）→（A(x)∨A(ｙ)）］∧ ～A(x－１）→ ～A(ｆ（x－１，ｘ＋１)）　 可满足式(Why?) * 计算机学院 * 诚实的人都讲实话。小林不是诚实的，因而小林不讲实话。 A(x):ｘ是诚实的人　　B(x):x讲实话　ａ:小林 　?(x)（ A(x) → B(x) ）∧ ～A(ａ)→ ～B(ａ)　 F 好货不便宜。小王买的衣服很贵，所以小王买的是优质衣服。 　　A(x):ｘ不便宜　　B(x):x是好货 　　ａ：小王买的衣服　　 ?(x)（ B(x)→ A(x)）∧Ａ（ａ）→Ｂ（ａ）　　 F * 计算机学院 * 每个懂得人性本质的作