什么叫静态网站,帮忙建站的公司,如何让自己的网站被百度收录,案例学习网站建设方案1. 数理逻辑
1.1 命题逻辑的基本概念
1.1.1 命题的概念
命题#xff08;Proposition#xff09;#xff1a;是一个陈述句#xff0c;它要么是真的#xff08;true#xff09;#xff0c;要么是假的#xff08;false#xff09;#xff0c;但不能同时为真和假。例如…1. 数理逻辑
1.1 命题逻辑的基本概念
1.1.1 命题的概念
命题Proposition是一个陈述句它要么是真的true要么是假的false但不能同时为真和假。例如“北京是中国的首都”是一个真命题“225”是一个假命题。
注意感叹句、祈使句、疑问句都不是命题陈述句中的悖论判断结果不惟一确定的不是命题。 简单命题与复合命题
简单命题原子命题一个不能被进一步分解为更简单的命题的陈述句。例如“北京是中国的首都”就是一个简单命题。复合命题由两个或多个简单命题通过逻辑联结词组合而成的命题。例如“北京是中国的首都并且上海是中国最大的城市”就是由两个简单命题通过“并且”这个联结词组合成的复合命题。
1.1.2 否定、析取、合取连结词
联结词
Connectives是用来组合一个或多个命题以形成新的命题的逻辑运算符。常见的联结词包括
否定Negation通常表示为 ¬ 或 ~合取Conjunction通常表示为 ∧ 或 析取Disjunction通常表示为 ∨ 或 |条件Conditional通常表示为 → 或 双条件Biconditional通常表示为 ↔ 或
例题2 将下列命题符号化 (1) 吴颖既用功又聪明. (2) 吴颖不仅用功而且聪明. (3) 吴颖虽然聪明但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解 定义基本的原子命题 P吴颖用功。Q吴颖聪明。R张辉是三好生。S王丽是三好生。T张辉与王丽是同学。 每个命题符号化如下 (1)吴颖既用功又聪明。 符号化P∧Q 这里使用了合取联结词 ∧and来表示“既…又…”。 (2)吴颖不仅用功而且聪明。 符号化P∧Q 尽管表述方式不同但逻辑上与第(1)题相同都是表示吴颖同时具有用功和聪明这两个属性。 (3)吴颖虽然聪明但不用功。 符号化Q∧¬P使用了合取联结词 ∧ 和否定 ¬ 来表示“虽然…但是…”。这里表示吴颖聪明Q并且不是用功的¬P。 (4)张辉与王丽都是三好生。 符号化R∧S 使用了合取联结词 ∧ 来表示两个人都满足某个条件即张辉是三好生R且王丽也是三好生S。 (5)张辉与王丽是同学。 符号化T 这是一个简单的原子命题直接用 T 表示张辉与王丽是同学这一事实。 例题3 将下列命题符号化(1) 2 或 4 是素数.(2) 2 或 3 是素数.(3) 4 或 6 是素数.(4) 小元元只能拿一个苹果或一个梨.(5) 王小红生于 1975 年或 1976 年. 解 (1) 令 p: 2 是素数, q: 4 是素数, p ∨ q (2) 令 p: 2 是素数, q: 3 是素数, p ∨ q (3) 令 p: 4 是素数, q: 6 是素数, p ∨ q (4) 令 p: 小元元拿一个苹果, q: 小元元拿一个梨, (p ∧ ¬q) ∨ (¬p ∧ q) (5) p: 王小红生于 1975 年, q: 王小红生于 1976 年 (p ∧ ¬q) ∨ (¬p ∧ q) 或 p ∨ q (1) — (3) 为相容或表示两个条件中至少一个为真但也可以同时为真。 (4) — (5) 为排斥或表示两个条件中恰好有一个为真不能同时为真也不能同时为假。 符号化时 (5) 可有两种形式而 (4) 则不能 (4) 小元元只能拿一个苹果或一个梨 解释这是一个典型的排斥或exclusive or的情况。小元元要么拿一个苹果要么拿一个梨但不能同时拿两者也不能什么都不拿。 (5) 王小红生于 1975 年或 1976 年 解释这里存在两种可能的解释 相容或王小红可能生于 1975 年或者生于 1976 年或者两个年份都可以虽然实际上一个人不可能同时出生于两个年份。 排斥或王小红必须且只能生于 1975 年或 1976 年中的一个年份不能同时出生在两个年份也不能都不在这两个年份出生。 1.1.3 蕴含联结词
设 p p p 和 q q q 为两个命题复合命题“如果 p p p则 $q $”称作 $ $ 与 q q q 的蕴涵式记作 p → q p\rightarrow q p→q并称 p p p 是蕴涵式的前件 q q q 为蕴涵式的后件 → \rightarrow → 称作蕴涵联结词。规定 p p p → \rightarrow → q q q 为假当且仅当 p p p 为真而 q q q 为假。
例题4 只要天冷小王就穿羽绒服。 ◦ 符号化→ ◦ 解释这里的“只要…就…”结构暗示了一个条件语句即如果前提条件(天冷)满足那么结论(小王穿羽绒服)必然发生。这是标准的蕴含关系用逻辑符号表示就是→。 因为天冷所以小王穿羽绒服。 ◦ 符号化→ ◦ 解释“因为…所以…”同样表达了因果关系即(天冷)是(小王穿羽绒服)发生的充分条件。这也是一种蕴含关系符号化为→。 若小王不穿羽绒服则天不冷。 ◦ 符号化¬→¬ ◦ 解释这句话的意思是如果观察到 (小王穿羽绒服)的否定情况即小王没穿羽绒服那么可以推断出(天冷)的否定情况即天不冷。这是一种反向的蕴含关系符号化为¬→¬。 只有天冷小王才穿羽绒服。 ◦ 符号化→ ◦ 解释“只有…才…”强调了必要条件即要使(小王穿羽绒服)成为现实(天冷)是必不可少的。换句话说如果没有就没有。这可以通过→来表示。 除非天冷小王才穿羽绒服。 ◦ 符号化→ ◦ 解释“除非…才…”与“只有…才…”类似都在说明(天冷)是(小王穿羽绒服)的必要条件。因此符号化仍然是→。 除非小王穿羽绒服否则天不冷。 ◦ 符号化¬→¬ ◦ 解释这句话的意思是如果小王不穿羽绒服¬那么我们可以得出天不冷¬的结论。这也是一个反向的蕴含关系符号化为¬→¬。 如果天不冷则小王不穿羽绒服。 ◦ 符号化¬→¬ ◦ 解释这句话直接给出了一个条件语句即如果前提条件¬ (天不冷)满足那么结论¬(小王不穿羽绒服)必然发生。这是另一种形式的蕴含关系符号化为¬→¬。 小王穿羽绒服仅当天冷的时候。 ◦ 符号化→ ◦ 解释“仅当…时候…”再次强调了必要条件即(天冷)是 (小王穿羽绒服)发生的唯一条件。因此符号化为→。 1.1.4 等价联结词
设 p, q 为两个命题复合命题 “p 当且仅当 q” 称作 p 与 q 的等价式记作 p↔q↔ 称作等价联结词。规定 p↔q 为真当且仅当 p 与 q 同时为真或同时为假。
p↔q 的逻辑关系p 与 q 互为充分必要条件。这意味着如果 p 为真则 q 也为真如果 q 为真则 p 也为真。同样如果 p 为假则 q 也为假如果 q 为假则 p 也为假。这种关系在逻辑上是对称的表明两个命题在逻辑上是等价的。
例题 解 (1) 224 当且仅当 336。 • : 224 是真的。 • : 336 也是真的。 • 因为 和 都是真的所以 ↔是真的。 (2) 224当且仅当 3 是偶数。 • : 224 是真的。 • : 3 是偶数这是假的因为3是奇数。 • 因为 为真而 为假所以 ↔ 是假的。 (3) 224 当且仅当太阳从东方升起。 • : 224 是真的。 • : 太阳从东方升起这是一个自然规律是真的。 • 因为 和 都是真的所以 ↔ 是真的。 (4) 224 当且仅当美国位于非洲。 • : 224 是真的。 • : 美国位于非洲这是假的因为美国位于北美洲。 • 因为 为真而 为假所以 ↔ 是假的。 (5) 函数 () 在 0 可导的充要条件是它在 0 连续。 • 这是一个数学定理如果一个函数在某个点可导那么它在该点必然连续。但是一个函数在某个点连续并不一定意味着它在该点可导。例如绝对值函数在0点连续但不可导。 • 因此这个命题是假的因为可导性是连续性的一个更强的条件而不是充要条件。 1.2 命题公式及其赋值
1.2.1 合式公式 几点说明归纳或递归定义, 元语言与对象语言, 外层括号可以省去
1.2.2 合式公式的层次 1.2.3 公式赋值 1.2.4 真值表
将命题公式A在所有赋值下取值的情况列成表, 称作A的真值表.
构造真值表的步骤: 找出公式中所含的全部命题变项p1, p2, … , pn(若无下角标 则按字母顺序排列), 列出 2 n 2^n 2n个全部赋值, 从00…0开始, 按二进制加法, 每次加1, 直至11…1为止. 按从低到高的顺序写出公式的各个层次. 对每个赋值依次计算各层次的真值, 直到最后计算出公式 的真值为止.
例题
1.2.5 公式的类型
公式的类型
(1) 若A在它的任何赋值下均为真, 则称A为重言式或永真式;
(2) 若A在它的任何赋值下均为假, 则称A为矛盾式或永假式;
(3) 若A不是矛盾式, 则称A是可满足式.
注意重言式是可满足式但反之不真.
真值表的用途:
求出公式的全部成真赋值与成假赋值, 判断公式的类型
1.3 练习题
练习1 将下列命题符号化 (1) 豆沙包是由面粉和红小豆做成的. (2) 苹果树和梨树都是落叶乔木. (3) 王小红或李大明是物理组成员. (4) 王小红或李大明中的一人是物理组成员. (5) 由于交通阻塞他迟到了. (6) 如果交通不阻塞他就不会迟到. (7) 他没迟到所以交通没阻塞. (8) 除非交通阻塞否则他不会迟到. (9) 他迟到当且仅当交通阻塞. 解 (1) 是简单命题 (2) 是合取式 (3) 是析取式相容或(4) 是析取式排斥或 5–9题的解 练习2 习题3 解 2. 命题逻辑等值演算
2.1 等值式
2.1.1 等值式概念 例题1 解 2.1.2 基本等值式 特别提示必须牢记这16组等值式这是继续学习的基础
2.1.3 等值演算与置换规则 等值演算——由已知的等值式推演出新的等值式的过程 等值演算的基础 (1) 等值关系的性质自反性、对称性、传递性 (2) 基本的等值式 (3) 置换规则见3 置换规则设Φ(A)是含公式A的命题公式Φ(B)是用公式B置换,Φ(A)中所有的A后得到的命题公式,若Φ(B) Φ(A)则 Φ(B) Φ(A) 写题的时候可以省去注明中的置换规则
注意用等值演算不能直接证明两个公式不等值。 2.1.4 等值演算的应用举例 2.2 析取范式与合取范式
2.2.1 概念 2.2.2 范式的性质
定理2.1
(1) 一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定式。
例子 假设有一个简单析取式 P∨¬P。根据逻辑的定义无论 P 是真还是假P∨¬P 总是为真。因此P∨¬P 是一个重言式。反之如果一个简单析取式不包含任何命题变项及其否定式如 P∨Q则它不是重言式因为存在 P 和 Q 都为假的情况使得整个表达式为假。
(2) 一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式。
例子 假设有一个简单合取式 P∧¬P。根据逻辑的定义无论 P 是真还是假P∧¬P 总是为假。因此P∧¬P 是一个矛盾式。反之如果一个简单合取式不包含任何命题变项及其否定式如 P∧Q则它不是矛盾式因为存在 P 和 Q 都为真的情况使得整个表达式为真。
定理2.2
(1) 一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式。
例子 假设有一个析取范式 (P∧¬P)∨(Q∧¬Q)。由于 P∧¬P 和 Q∧¬Q 都是矛盾式因此整个析取范式也是矛盾式。反之如果析取范式中有一个简单合取式不是矛盾式如 (P∧Q)∨(R∧S)则整个析取范式不是矛盾式因为存在 P,Q,R,S 的某些真值组合使得整个表达式为真。
(2) 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。
例子 假设有一个合取范式 (P∨¬P)∧(Q∨¬Q)。由于 P∨¬P 和 Q∨¬Q 都是重言式因此整个合取范式也是重言式。反之如果合取范式中有一个简单析取式不是重言式如 (P∨Q)∧(R∧¬R)则整个合取范式不是重言式因为存在 P,Q,R 的某些真值组合使得整个表达式为假。
定理2.3范式存在定理
任何命题公式都存在与之等值的析取范式与合取范式
小练习 例题 5 解 2.2.3 极小项与极大项
概念
在含有n个命题变项的简单合取式简单析取式中若每个命题变项均以文字的形式在其中出现且仅出现一次而且第i个文字出现在左起第i位上1 ≤ \leq ≤ i ≤ \leq ≤ n称这样的简单合取式简单析取式为极小项极大项.
几点说明
n个命题变项有 2 n 2^n 2n个极小项和 2 n 2^n 2n个极大项 2 n 2^n 2n个极小项极大项均互不等值用 m i m_{i} mi表示第i个极小项其中i是该极小项成真赋值的十进制表示. 用 M i M_{i} Mi表示第i个极大项其中i是该极大项成假赋值的十进制表示. m i m_{i} mi M i M_{i} Mi称为极小项极大项的名称.
实例 2.2.4 主析取范式与主合取范式
概念 主范式的存在唯一定理
任何命题公式都存在与之等值的主析取范式和主合取范式,并且是唯一的
2.2.5 求公式主范式的步骤 例题 2.2.6 主范式的应用 2.3 联结词的完备集
暂时没学期末考试不严格的出这方面的题。
2.4 习题 第一题 设A与B为含n个命题变项的公式判断下列命题是否为真 (1) AB当且仅当A与B有相同的主析取范式 (2) 若A为重言式则A的主合取范式为0 (3) 若A为矛盾式则A的主析取范式为1 (4) 任何公式都能等值地化成{∧, ∨}中的公式 (5) 任何公式都能等值地化成{¬, -, ∧}中的公式 答1真。2假。3假。4假。5真。 说明: (2) 重言式的主合取范式不含任何极大项为1. (3) 矛盾式的主合析范式不含任何极小项, 为0. (4){∧, ∨}不是完备集如矛盾式不能写成{∧, ∨}中的公式. (5) {¬, -, ∧}是完备集. 解此类问题的步骤 设简单命题并符号化 用复合命题描述各条件 写出由复合命题组成的合取式 将合取式成析取式最好是主析取范式 求成真赋值, 并做出解释和结论 第五题的解题步骤
第六、七题用消解法 3.命题逻辑的推理理论
3.1 推理的形式结构
3.1.1 概念 3.1.2 推理定律–重言蕴含式 3.2 自然推理系统P
3.2.1 定义 3.2.2 在自然推理系统P中构造证明 3.2.3 附加前提证明法 3.2.4 归谬法 3.3 习题
