离散总复习提纲讲述.pptVIP

命题逻辑翻译（符号化） 只要我有时间，我就来看你。 只有睡好觉才能恢复疲劳。 仅当我有时间且天不下雨，我将去镇上 李强总是在图书馆看书，除非图书馆不开门或李强生病。 假如上午不下雨，我去看电影，否则就在家里读书或看报。 。。。。 证明等价式 证明等价式 P?(Q?R) ?(P ∧ Q) ? R ┐(P?Q) ? (P∧┐Q)∨(┐P∧Q)? (P ? Q)∧ (P ? R) ? P ? (Q∧R) 。。。 真值表法，等值演算法，主范式法 判断命题公式的类型 ((P?Q)∧(Q?R)) ?(P?R) (P ? Q) ? (┐ P ∨ Q) 。。。 真值表法，等值演算法，主范式法 推证蕴含式 推证蕴含式（不构造真值表） P∧(P ? Q) ?Q P ? Q ? (P∧R)?(Q∧R) 。。。 前件真推后件真 后件假推前件假 求主（合）析取范式 求下面公式的主析取范式、主合取范式. (P ? Q)∧ Q (P ? Q)∧ (P ? R) 。。。 真值表法，等值演算法 推理 前提：P∨Q , Q ?R ,P ? S , ?S 结论：R ∧(Q ∨P) 前提：P ? ? Q , ? R ∨Q , R ∧ ? S 结论： ? P 前提：(P ∨ Q)?( R ∧ S), (S ∨ T) ? U 结论：P ?U 。。。。 直接法、反正法、条件证明（CP规则） 和命题翻译相结合的题目 先翻译，再推理 前提： 1). 若大连获得冠军，则北京或上海获得亚军。 2). 若上海获得亚军，则大连不能获得冠军。 3). 若延边获得亚军，则北京不能获得亚军。 4). 最后大连获得冠军。 结论：5). 延边没有获得亚军。 。。。 谓词逻辑翻译 凡是偶数均能被2整除。 存在着偶素数。 没有不犯错误的人。 在北京工作的人未必都是北京人。 兔子比乌龟跑的快。 。。。。 求谓词公式的真值? 寻求下列各式的真假值。 ? (?x)(P→Q(x))∨R(a) 其中P：21, Q(x):x≤3,R(x):x5而a:5, 论域是{-2,3,6}。 。。。。 有限论域上消去公式中的量词 如果论域是集合{a,b,c}，试消去下面公式中的量词。 (x)(P(x)→ Q(x)) 约束变元的换名和自由变元的代入 对下列谓词公式中的约束变元进行换名。 ? (x)(P(x)→ (R(x)∨Q(x))∧($x)R(x)) →($z)S(x,z) 对下列谓词公式中的自由变元进行代入。 ?(($y)A(x,y)→(x)B(x,z))∧($x)(z)C(x,y,z) 前束范式 将公式(?x) P(x) ? (?x) Q(x)转化为前束范式。 将公式(?x)(F(x)?G(x))?((?x) F(x)? (?x)G(x))化为前束范式. 。。。。 谓词逻辑推理 构造推理证明：(?x)(F(x)?(G(a)∧R(x)))∧(?x)F(x)?(?x)(F(x)∧R(x)) 量词的消去和推广规则 US,ES,UG,EG规则 和翻译相结合的推理题目 采用规定的符号翻译并推理 N(x)：x是自然数；O(x)：x是奇数；E(x)：x是偶数；Z(x)：x能被2 整除。 每一个自然数不是奇数就是偶数，自然数是奇数当且仅当它能被2整除，并不是所有的自然数都能被2整除，因此，有的自然数是奇数。 。。。。。 集合的幂集 会求集合的幂集 (1) A={a，{b}，c}； (2) B={?}； (3) C=? 设集合A＝{a,b,c},B={a,b},求P(A)－P(B)和P(B)－P(A) 集合相等的证明 证明 (A-B)-C=(A-C)-B 方法1.任取 x∈(A-B)-C ? x∈(A-B)∧x?C ?(x∈A∧x?B)∧x?C ?(x∈A∧x?C)∧x?B ? x∈(A-C)∧x?B ? x∈(A-C)-B 所以(A-B)-C=(A-C)-B 方法2 (A-B)-C=(A∩~B)∩~C =(A∩~C)∩ ~B =(A-C)-B 笛卡尔积 设集合 A={a,b},B={1,2,3},C={d},求A×B×C，B×A. 设集合A＝{1,2},求A×P(A). 。。。 二元关系 关系的三种表示方法：集合表达式、关系矩阵、关系图 设A＝{1,2,3,4,5}, 给出A上的小于关系的集合表达式、关系矩阵和关系图。. 对P={0，1，2，3，4，5，6}上的二元关系，R={＜x，y＞∣x﹤y∨x是质数}，写出关系矩阵，画出关系图。 。。。 关系的复合运算，关系的逆运算 设集合A＝{2,3,4},B={4,6,7},C={8,9,12,14}. R1是由A到B的二元关系，R2是由B到C的二元关系，定义如下： ,求它们的复合关系，并用关系矩阵表示.