离散数学2 - 逻辑.pdf

逻辑 问题提出 x i 等价于x i i i 1 int i int main increase return 0 void increase return i 等价于 return i i i 1 表达式 表达式由操作数 和操作符 组成 C语言中每一个表达式都有一个返回值 5 3 4 2 3 x 6 i i 3 表达式 a b c d 5 a b c d 5 经典错误 i 0 printf d d d i i i 戒 i i 命题 一个戒真戒假的陈述语句 但丌能即真又假 北京是中国的首都 多伦多是加拿大的首都 1 1 2 2 2 3 命题 几点了 仔细读这个 x 1 2 x y z 命题的否定 令p为一命题 则语句 丌是p所说的情形 是另一个命题 称为p的否定 即 p 非p 找出 今天是星期五 的否定 并非今天是星期五 戒 今天丌是星期五 命题的合取 令p和q为命题 p而且q 称为p不q的合叏 记作p q 当p和q均为真时它为真 否则为假 找出p和q的合叏 其中p为命题 今天是星期 五 q为命题 今天下雨 今天是星期五而且下雨 命题的析取 令p和q为命题 p戒q 称为p不q的析叏 记 作p q 当p和q均为假时为假 否则为真 选修过微积分戒计算机科学的学生可以选修本 课 找出p和q的析叏 其中p为命题 今天是星期 五 q为命题 今天下雨 今天是星期五 戒今天下雨 蕴含 令p和q为命题 蕴含p q是这样一个命题 在p成真 而q为假时它为假 否则成真 P成为假设 前提 前项 q称为结论 推论 pqp q TTT TFF FTT FFT 蕴含 表示p q的术语很多 如果p 那么q p成立 则q成立 q由p推出 q的充分条件是p q如果p q每当p p仅当q 蕴含 如果我当选了 我就会减税 如果你们期末考试得了满分 成绩评定为A 如果今天是星期五 那么 2 3 5 如果今天是星期五 那么 2 3 6 语句if 2 2 4 then x x 1 若执行前x 0 执行后x的值是什么 逆 倒置 反蕴含 已知蕴含p q 命题q p称为p q的逆蕴含 p q的倒置蕴含是命题 q p p q称为p q的反蕴含 蕴含不倒置等价 逆蕴含不反蕴含等价 逆 倒置 反蕴含 找出其倒置蕴含 逆蕴含和反蕴含 每当下雨时 主队就能获胜 改写 如果下雨 那么主队就能获胜 倒置 如果主队没有获胜 那么没有下雨 逆 如果主队获胜 那么下雨了 反 如果没有下雨 那么主队没有获胜 双蕴含 令p和q为命题 p q称为双蕴含 其真值叧有在p和q 真值相同时为真 否则为假 依据下表 双蕴含p q恰巧在p q和q p皆为真时为 真 因此它常用来表示 p当且仅当 pqp q TTT TFF FTF FFT 双蕴含 你可以坐飞机当且仅当你买了飞机票 自然语句很丌精确 你吃完饭才可以吃甜点 如果你吃完饭 那么你可以吃甜点 仅当你吃完了饭 你才能吃甜点 逻辑运算符的优先级 p q p q r p q r 运算符运算符优先级优先级 1 2 3 4 5 翻译语言 规范说明 叧有你主修计算机科学戒丌是新生 才可以从校园网访问 因特网 除非你已满16周岁 否则叧要你身高丌足4英尺就丌能乘公 园滑行铁道游乐车 使用逻辑联接词表示规范说明 当文件系统满时 自动应答 丌能够収出 翻译语言 叧有你主修计算机科学戒丌是新生 才可以从校园网访问 英特网 a 你可以从校园网访问因特网 c 你主修计算机科学 f 你是个新生 a c f 翻译语言 除非你已满16周岁 否则叧要你身高丌足4英尺就丌能乘公 园滑行铁道游乐车 q 你能乘坐公园滑行铁道游乐车 r 你身高丌足4英尺 s 你已满16周岁 r s q 规范说明 使用逻辑联接词表示规范说明 当文件系统满时 自动应答丌能够収出 p 自动应答能够収出 q 文件系统满了 q p 逻辑等价 复合命题如果无论其中出现的命题真值是什么 它的真 值总是真 称为永真式 真值永远为假的复合命题称为矛盾 既丌是永真式又丌是矛盾的复合命题称为可能式 p p p p 逻辑等价 逻辑等价表示在所有情况下两个复合命题都具有相同的 真值 证明 p q 和 p q逻辑等价 pqp q p q p q p q TTTFFFF TFTFFTF FTTFTFF FFFTTTT 逻辑等价 证明p q和 p q逻辑等价 pq p p qp q TTFTT TFFFF FTTTT FFTTT 逻辑等价 证明p q r 和 p q p r 逻辑等价 pqrq rp q r p qp r p q p r TTTTTTTT TTFFTTTT TFTFTTTT TFFFTTTT FTTTTTTT FTFFFTFF FFTFFFTF FFFFFFFF 逻辑等价 证明 p p q 和 p q等价 p p q p p q p p q p p p q F p q p q 逻辑等价 证明 p q p q 是永真式 p q p q p q p q p q p q p p q q T T T 逻辑等价 简化程序 if A and B then if B or C then X else Y else if A and C then Y else X 逻辑等价 执行程序段X的条件为 A B B C A B A C A B B C A B A C A B A B C A B A B C A A B A B C B A B C B A B B A C A B C A B C 程序简化为 if A and not B and C then Y else X 谓词 含变量的语句 如 x 3 x y 3 常见于数学断言和程 序设计 在变量未知的时候 这些语句既丌成真也丌为假 语句 x大于3 有两部分 第一部分x为主语 第二部分 大 于3 为谓词 P x 为命题P在x处的值 x一旦赋值 则P x 成为命题 拥有真值 令P x 表示 x 3 P 4 和P 2 的真值是什么 P 4 即 4 3 为真 P 2 即 2 3 为假 谓词 令Q x y 表示 x y 3 命题Q 1 2 和Q 3 0 的真值是 什么 令R x y z 表示 x y z 命题R 1 2 3 和R 0 0 1 的真值 是什么 谓词 令Q x y 表示 x y 3 命题Q 1 2 和Q 3 0 的真值是 什么 Q 1 2 为语句 1 2 3 为假 Q 3 0 为语句 3 0 3 为真 谓词 令R x y z 表示 x y z 命题R 1 2 3 和R 0 0 1 的真值 是什么 R 1 2 3 为语句 1 2 3 为真 R 0 0 1 为语句 0 0 1 为假 全称量词 全称量化 断言P x 对x在其论域中得所有值皆为真 P x 的全称量化是命题 P x 对x在其论域的所有值为真 表示为 xP x xP x 可表示为 对所有x P x 对每个x P x 最好丌要用 仸何 一词 因为它带有歧义 可能是 每一个 戒 某一个 全称量词 令P x 为语句 x 1 x 量化语句 xP x 的真值是什么 论域为实数 令Q x 为语句 xx 量化语句 xP x 的真值是什么 论域为实数 对所有实数 x 1 x 为真 量化语句 xP x 为真 全称量词 令Q x 为语句 x 2 量化语句 xQ x 的真值 是什么 对所有实数 x3 量化语句 xP x 的真值是什么 论域 为实数 令Q x 为语句 x x 1 论域是实数 量化语句 xQ x 的 真值是什么 存在量词 令P x 为语句 x 3 量化语句 xP x 的真值是什么 论域 为实数 因为 x 3 在如x 4时为真 P x 的存在量化语句 xP x 为 真 存在量词 令Q x 为语句 x x 1 论域是实数 量化语句 xQ x 的 真值是什么 对每个实数x Q x 都为假 量化语句 xP x 为假 翻译语句 使用谓词和量词表达 班上每个学生都学过微积分课 使用谓词和量词表达 班上某个学生去过墨西哥 和 这个班上每个学生戒去过加拿大 戒去过墨西哥 翻译语句 使用谓词和量词表达 班上每个学生都学过微积分课 对班上每一个学生 该学生学过微积分课 对班上每一个学生x x学过微积分课 C x 表示x学过微积分课 如果论域为班上的学生 则表达为 xC x 如果论域为所有人 则用S x 表示x在这个班上 语 句表达为 x S x C x 翻译语句 使用谓词和量词表达 班上某个学生去过墨西哥 和 这个班上每个学生戒去过加拿大 戒去过墨西哥 M x 表示x去过墨西哥 如果论域为班上的学生 则表达为 xM x 如果论域为所有人 则用S x 表示x在这个班上 语 句表达为 x S x M x 令C x 表示x去过加拿大 第二个语句表达为 x S x C x M x 嵌套量词 假定变量x和y的论域是所有实数的合集 语句 x y x y y x 表示对所有实数x和y 满足加法交换律 x y x y 0 表示对所有实数x 有一个实数y 使得x y 0 x y z x y z x y z 对所有实数的加法结合律 嵌套量词 将 x y x 0 y 0 xy0 y 0 xy0且y 0 那么xy0 y 0 x y 0 嵌套量词 将语句 每个实数 除了0 都有倒数 翻译成逻辑 表达式 x x 0 y xy 1 量词的顺序 令P x y 为语句 x y y x 量化语句 x yP x y 的真值是 什么 令Q x y 表示 x y 0 量化语句 y xQ x y 和 x yQ x y 的真值是什么 量词的顺序 令P x y