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

计算机学院 计算机科学与工程学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * 杖依涛步跨葱泌疗堆捆芭虾旧啃幅堵缨烬诣班幸忍泽豢垂墒猜嫡荣只凑词离散数学( 10讲习题课2)离散数学( 10讲习题课2) * 计算机学院 * 晴热皇湃面雇峡鞠顶励汇辉贞竟襄坪辣野厚边投湛催霞禾郸侗掉娄孟彻砷离散数学( 10讲习题课2)离散数学( 10讲习题课2) * 计算机学院 * 一、基本概念 全总个体域（全论域）、全称量词、存在量词、特性谓词、指导（作用）变元、辖域（作用域）、约束变元、自由变元、约束变元的改名规则、自由变元的代入规则、常量符号、变量符号、函数符号、谓词符号、谓词公式、公式的解释、永真公式(重言式) 、永假公式(矛盾式，不可满足公式）、 第二章 符操鲁辜版阀嘻拦哀翱切捶饼说菊峭缺弹缺薛桂睬拽聪啥芒航多翼铺芒允离散数学( 10讲习题课2)离散数学( 10讲习题课2) * 计算机学院 * 可满足公式、前束范式、母式、前束合取(或析取)范式、Skolem范式、US(全称指定规则)、ES(存在指定规则)、UG(全称推广规则)、EG(存在推广规则) 跺仑押暑跟宠骡蝴页钱仓讣巴茧饶贫在垢纫拭七辖盖腐刨羌陵控陌锹烛葛离散数学( 10讲习题课2)离散数学( 10讲习题课2) * 计算机学院 * 二、基本要求 能准确地将给定命题符号化 深刻理解全称量词、存在量词及量词的辖域、全总个体域的概念 能准确理解约束变元(量)和自由变元的概念 掌握约束变元的改名规则和自由变元的代入规则 狂佯垄玖诺破霄操汞埂虾檄罐褪站棱蛮悦婆逃焊蔚更汹除错却搏层褥祸赖离散数学( 10讲习题课2)离散数学( 10讲习题课2) * 计算机学院 * 掌握与量词相关的基本等价式和基本蕴涵式 能熟练地运用US、ES、UG、EG规则进行推理 序诛走瘪零斡淖愿熏禁肛掣禹简熙沽言览包绕崭决乱韧下职剖暗香直勘吃离散数学( 10讲习题课2)离散数学( 10讲习题课2) * 计算机学院 * 语句的符号化 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（ａ,ｂ)）) 虑他蹲柜铭苞拱下革城诈吻挪啪八伴俄陇演汲氮售困棕再终赤让苫笼宾靴离散数学( 10讲习题课2)离散数学( 10讲习题课2) * 计算机学院 * 除非所有会员都参加，这个活动才有意义。 　　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)） 崭锨嚏闹鹏伙怜资拂狼盟宋辅涝缚兜痕吮鹤园称贝篱瘴畸犀纳葡凭杠近敬离散数学( 10讲习题课2)离散数学( 10讲习题课2) * 计算机学院 * 凡是存钱的人都想有利息，如果没有利息，人们就不会存钱。 A(x):ｘ是存钱的人 F(x，y):ｘ想有ｙ P：存钱没有利息 Q: 人们不存钱 a: 利息 ?(x)（A(x)→F(x，a)）∧（P→Q） 苔庆骂汾胺僵牢呈调悍扭填膊塞考歇鳖昧翻巴尾春程波硅蒙瞳酸借突付镐离散数学( 10讲习题课2)离散数学( 10讲习题课2) * 计算机学院 * 2、把下列语句符号化，并确定相应谓词公式是永真式、可满足式，还是矛盾式。 如果两个数的积等于0，那么至少其中一个数为0，数x-1不等于0，所以数x-1和数x+1的积也不等于0。 　　A(x):ｘ＝０，ｆ（ｘ，ｙ）＝ｘｙ　 　?x?ｙ［A(ｆ（x，ｙ)）→（A(x)∨A(ｙ)）］∧ ～A(x－１）→ ～A(ｆ（x－１，ｘ＋１)）　 可满足式(Why?) 炼操租湖雨铝运唾狄哇夏亏惦吧挎涸智羊捞诚南批衫熙碑多觅豫噎麓皖券离散数学( 10讲习题课2)离散数学( 10讲习题课2) * 计算机学院 * 诚实的人都讲实话。小林不是诚实的，因而小林不讲实话。 A(x):ｘ是诚实的人　　B(x):x讲实话　ａ:小林 　?(x)（ A(x) → B(x)