珠海城乡建设网站,ppt模板下载平台,网站安全建设模板下载,wordpress图文安装教程1.数理逻辑 2. 集合论 3. 代数系统 4. 图论 离散数学#xff1a;研究离散量结构及相互关系的学科 数理逻辑集合论代数系统图论 逻辑#xff1a;研究推理的科学
数学方法#xff1a;引进一套符号系统的方法 数理逻辑是用数学方法研究形式逻辑的科学#xff0c;即使用符号化…1.数理逻辑 2. 集合论 3. 代数系统 4. 图论 离散数学研究离散量结构及相互关系的学科 数理逻辑集合论代数系统图论 逻辑研究推理的科学
数学方法引进一套符号系统的方法 数理逻辑是用数学方法研究形式逻辑的科学即使用符号化系统研究推理的方法。又称符号逻辑。 1. 数理逻辑
1.1 命题逻辑 1.1.1 命题 命题具有确定真值的陈述句 断言一个 陈述句真值命题的结果为真真值为真命题结果为假真值为假 悖论真假无法确定的断言称为悖论 命题分类
原子命题(本原命题)一个不能分解成更简单的命题复合命题由联结词标点符号和原子命题复合构成的命题
1. 命题联结词 命题演算中的运算符 命题和原子命题通过 命题联结词 构成新的 复合命题
否定词¬ P表示命题¬P(P的否定)表示P不真 P¬P0110
注
P都是… ¬P不都是 ≠\neq 都不是
合取∧ 若P和Q都是命题则 “P并且Q” 这一命题表示为 P∧QP和Q的合取 PQP∧Q000010100111
析取∨ 若P和Q命题那么 “P或Q” 这一命题表示为 P∨QP和Q的析取 可兼或不排除P、Q都会发生 如 P今晚我写字Q今晚我看书。为可兼或P他今年30岁Q他今年40岁。为排斥或 PQP∨Q000011101111
蕴含词(条件次)→ 设P和Q是命题新命题 “P蕴含Q” 表示为 P→QP蕴含Q P前提、假设或前件Q结论、后件 蕴含式 P→Q 的多种陈述方式
若P则QP是Q的充分条件Q是P的必要条件Q每当P只要P就Q因为P所以QP仅当Q只有Q才P除非Q否则¬P
PQP→Q001011100111
理解Q表示没有犯罪P表示证据如果没有证据则无法证明Q犯罪了
应用P→Q为假当且仅当P真Q假
以假的条件为前提不管结论真假新命题 P→Q 都是真的以真的条件为前提结论的真值就是新命题 P→Q 的真值
蕴含式 P→Q 的关联命题
逆反命题¬Q→¬P逆命题Q→P反命题¬P→¬Q
蕴含式分类不重要
因果蕴含用于断言前提和结论之间的因果或实质关系 PG是正方形QG的四边相等实质蕴含前提和结论之间无因果或实质关系这种蕴含式叫实质蕴含 P桔子是紫色的Q大地是不平的
等值(双条件词)↔ 设P和Q是命题新命题 “P等值于Q” 表示为 P↔QP等值于Q 多种陈述方式 P是Q的充要条件P当且仅当Q
PQP↔Q001010100111
P↔Q⟺(P→Q)∧(Q→P)⟺(P∨Q)∧(¬P∨¬Q)P\leftrightarrow Q\iff(P\rightarrow Q)∧(Q\rightarrow P) \iff (P∨Q)∧(¬P∨¬Q) P↔Q⟺(P→Q)∧(Q→P)⟺(P∨Q)∧(¬P∨¬Q)
与非
P↑Q⟺¬(P∧Q)P\uparrow Q \iff ¬(P∧Q)P↑Q⟺¬(P∧Q)
PQP ↑\uparrow↑ Q001011101110
1.P↑P⟺¬(P∧P)⟺¬P2.(P↑Q)↑(P↑Q)⟺¬(P↑Q)⟺P∧Q3.(P↑P)↑(Q↑Q)⟺¬P↑¬Q⟺P∨Q\begin{aligned} 1. P\uparrow P\iff ¬(P∧P) \iff ¬P\\ 2. (P\uparrow Q) \uparrow(P\uparrow Q) \iff ¬(P\uparrow Q) \iff P∧Q\\ 3.(P\uparrow P)\uparrow(Q\uparrow Q) \iff ¬P\uparrow¬Q \iff P∨Q\\ \end{aligned} 1.2.3.P↑P⟺¬(P∧P)⟺¬P(P↑Q)↑(P↑Q)⟺¬(P↑Q)⟺P∧Q(P↑P)↑(Q↑Q)⟺¬P↑¬Q⟺P∨Q
或非
P↓Q⟺¬(P∨Q)P\downarrow Q\iff ¬(P∨Q)P↓Q⟺¬(P∨Q)
PQP ↓\downarrow↓ Q001010100110
1.P↓P⟺¬(P∨P)⟺¬P2.(P↓Q)↓(P↓Q)⟺¬(P↓Q)⟺P∨Q3.(P↓P)↓(Q↓Q)⟺¬P↓¬Q⟺P∧Q\begin{aligned} 1. P\downarrow P\iff ¬(P∨P) \iff ¬P\\ 2. (P\downarrow Q) \downarrow(P\downarrow Q) \iff ¬(P\downarrow Q) \iff P∨Q\\ 3.(P\downarrow P)\downarrow(Q\downarrow Q) \iff ¬P\downarrow¬Q \iff P∧Q\\ \end{aligned} 1.2.3.P↓P⟺¬(P∨P)⟺¬P(P↓Q)↓(P↓Q)⟺¬(P↓Q)⟺P∨Q(P↓P)↓(Q↓Q)⟺¬P↓¬Q⟺P∧Q
2. 联结词优先级
强弱顺序 ¬ ∧ ∨ → ↔相同的运算符按从左至右的顺序计算括号可省略最外层的圆括号可以省略 如(¬((P∧¬Q)∨R)→((R∨P)∨Q)) 可写成 ¬(P∧¬Q∨R)→R∨P∨Q
3. 命题翻译
设P明天下雨Q明天下雪R我去学校 如果明天不是雨夹雪则我去学校¬(P∧Q)→R如果明天不下雨且不下雪则我去学校¬P∧¬Q→R如果明天下雨或下雪则我不去学校P∨Q→¬R明天雨雪无阻我一定去学校P∧Q∧R∨¬P∧Q∧R∨P∧¬Q∧R∨¬P∧¬Q∧R当且仅当明天不下雪且不下雨时我才去学校¬P∧¬Q↔R 说小学生编不了程序或说小学生使用不了个人计算机那是不对的 设P小学生会变成Q小学生会用个人计算机 ¬(¬P∨¬Q)若不是他生病或出差了我是不会同意他不参加学习的 设P他生病了Q他出差了R我同意他不参加学习 ¬(P∨Q)↔¬R 或 P∨Q↔R
4. 联结词归纳 一个联结词集合用其中联结词构成的式子足以把一切命题公式等价表达出来则这个联结词集合称为全功能的 {¬,∨}、{¬,∧}及其变形都是全功能集\begin{aligned} \{¬,∨\}、\{¬,∧\}及其变形都是全功能集 \end{aligned} {¬,∨}、{¬,∧}及其变形都是全功能集
判断联结词集合A是不是全功能集选全功能联结词集合B若B中每一联结词都能用A中联结词表示则A是全功能的
1.1.2 命题公式 命题变元以”真“、”假“为变域的变量 T和F称为命题常元 原子公式单个命题变元或命题常元 命题公式定义由命题、命题联结词、命题常元、命题变元组成的符号串满足下列条件 单个原子公式是命题公式如果A和B是命题公式则由命题联结词关联的A和B也是命题公式命题公式是 有限的 命题公式的指派 有 n 个命题变元的命题公式( P1,P2,...,PnP_1,P_2,...,P_nP1,P2,...,Pn )命题变元的真值有 2n2^n2n 种不同的组合。每种组合为一个指派 对应每一指派命题公式得到确定的值即命题公式成为命题。
1. 重言式 重言式(永真式)对所有指派命题公式的取值均为 T 矛盾式(永假式)对所有指派命题公式的取值均为 F 偶然式不是永真式及永假式可满足的一个公式至少存在一个指派使其值为真非永真一个命题公式至少存在一个指派使其值为假
重言式性质
重言式的否定是矛盾式矛盾式的否定是重言式重言式的合取、析取、蕴含、等值等都是重言式
两类重要的重言式
恒等式(真值为1的等值式) 由相同命题公式组成的命题组 A(P1,P2,...,Pn)A(P_1,P_2,...,P_n)A(P1,P2,...,Pn) 和 B(P1,P2,...,Pn)B(P_1,P_2,...,P_n)B(P1,P2,...,Pn) 如果 A↔B 是重言式则对A与B的任何指派都有相同的真值(全0或全1)则 A恒等于B 或 A等价于B。记为 A⟺BA \iff BA⟺B (逻辑恒等式) 逻辑恒等式描述¬¬p ⟺\iff⟺ P双否定P ∨ P ⟺\iff⟺ P等幂律P∧P ⟺\iff⟺ P等幂律P ∨ Q ⟺\iff⟺ Q ∨ P交换律P∧Q ⟺\iff⟺ Q∧P交换律(P∨Q)∨R ⟺\iff⟺ P∨(Q∨R)结合律(P∧Q)∧R ⟺\iff⟺ P∧(Q∧R)结合律P∨(Q∧R) ⟺\iff⟺ (P∨Q)∧(P∨R)分配律P∧(Q∨R) ⟺\iff⟺ P∧Q∨ P∧R分配律¬(P∨Q) ⟺\iff⟺ ¬P∧¬Q德摩根律¬(P∧Q) ⟺\iff⟺ ¬P∨¬Q德摩根律P∨(P∧Q) ⟺\iff⟺ P吸收律P∧(P∨Q) ⟺\iff⟺ P吸收律P→Q ⟺\iff⟺ ¬P∨Q蕴含表达式P↔Q ⟺\iff⟺ (P→Q)∧(Q→P) ⟺\iff⟺ (¬P∨Q)∧(¬Q∨P)⟺\iff⟺ ¬P∧¬Q ∨ Q∧P等值表达式P∨¬P ⟺\iff⟺ T排中律P∧¬P ⟺\iff⟺ F矛盾律P→Q ⟺\iff⟺ ¬Q→¬P逆反律
永真蕴含式 如果 A→B 是以永真式则称为永真蕴含式记为 A ⇒\Rightarrow⇒ B(A永真蕴含B) 证明蕴含式永真
方法一真值表
方法二命题演算
永真式推导P⇒\Rightarrow⇒P∨Q¬P∨P∨QT∨QTP∧Q⇒\Rightarrow⇒P¬(P∧Q)∨P¬P∨¬Q∨PTP∧(P→Q)⇒\Rightarrow⇒ Q¬(P∧(P→Q)∨Q¬P∨¬(¬P∨Q)∨Q¬P∨P∧¬Q∨Q¬(P∧¬P∨Q∧¬Q)¬(F∨F)T
方法三分情况讨论 肯定前件否定后件 假定前件真若能推出后件真则此蕴含式真 假定后件假若能退出前件假则此蕴含式真
例证明 ¬Q∧(P-Q)⇒\Rightarrow⇒¬P 真值表 若前件真则¬Q与P-Q为真即Q为假进而推出P是假因而后件是真满足蕴含式的定义 分情况讨论 设P是真即后件假若能证明前件假则为永真蕴含式 (1) 若Q为真则¬Q为假P→\rightarrow→Q为真故 ¬Q∧(P-Q) 为假 (2) 若Q为假则¬Q为真P→\rightarrow→Q为假故 ¬Q∧(P-Q) 为假 故等式为永真蕴含式
方法四将永真蕴含变为蕴含式与1等价 (A⇒B)⟺(A→B⟺1)(A\Rightarrow B) \iff (A\rightarrow B \iff 1) (A⇒B)⟺(A→B⟺1)
恒等式与永真蕴含关系
A⟺BA\iff BA⟺B就是 A⇒BA\Rightarrow BA⇒B 且 B⇒AB\Rightarrow AB⇒A 同时成立
恒等式和永真蕴含式的性质
传递性
若 A⟺\iff⟺B、B⟺\iff⟺C则 A⟺\iff⟺C若 A ⇒\Rightarrow⇒ B、B⇒\Rightarrow⇒C则 A⇒\Rightarrow⇒C
永真蕴含结合律
若A ⇒\Rightarrow⇒ B、A ⇒\Rightarrow⇒ C则 A⇒\Rightarrow⇒B∧C
代入规则 (变形式) 用同一命题公式代替出现在重言式中的某个命题变元所得的仍是重言式 代入后所得公式称为原公式的代入实例
对于非重言式不做代入运算因为所得的代入实例性质不确定
替换规则 (真值不变)
若A⟺\iff⟺B在公式C中出现A的地方可替换为B得到公式D则 C⟺\iff⟺D
在公式C和D中除替换部分外均相同但对任一指派A与B的真值相等故C与D的真值也相等 代入规则和替换规则是命题演算的基础 2. 对偶原理 对偶公式设有公式A仅有联结词∧、∨、¬。将A中∧、∨、T、F分别换为∨、∧、F、T得到公式 A∗A^*A∗ 则 A∗A^*A∗ 称为A的对偶公式 对偶是相互的 设A与 A∗A^*A∗ 是对偶式关系 设 P1,P2,...,PnP_1,P_2,...,P_nP1,P2,...,Pn 是出现于A和 A∗A^*A∗ 的所有命题变元则 ¬A(P1,P2,...,Pn)⟺A∗(¬P1,¬P2,...,¬Pn)¬A(P_1,P_2,...,P_n)\iff A^*(¬P_1,¬P_2,...,¬P_n)¬A(P1,P2,...,Pn)⟺A∗(¬P1,¬P2,...,¬Pn) 等价命题公式的对偶式相互等价 若A⟺BA\iff BA⟺B ,且A、B为由命题变元P1,P2,...,PnP_1,P_2,...,P_nP1,P2,...,Pn及联结词∧、∨、¬构成的公式则 A∗⟺B∗A^*\iff B^*A∗⟺B∗ 若A⇒BA\Rightarrow BA⇒B且A、B为由命题变元P1,P2,...,PnP_1,P_2,...,P_nP1,P2,...,Pn及联结词∧、∨、¬构成的公式则B∗⇒A∗B^*\Rightarrow A^*B∗⇒A∗
3. 范式 将命题公式转化为其逻辑等价的标准形式 给定一个命题公式范式一定存在但不一定唯一所以引入主范式一个命题公式的主范式是唯一的
范式 基本积若干命题变元及其否定的合取式 基本和若干命题变元及其否定的析取式 例
P、P∧Q、¬P∧Q等都是基本积P、P∨Q、¬P∨Q等都是基本和
单个命题变元既是基本积又是基本和
性质
一个基本积是永假式当且仅当他只含有P、¬P形式的两个因子 ¬P∧PF一个基本和是永真式当且仅当他含有P、¬P形式的两个因子 ¬P∨PT 析取范式一个基本积之和的公式如果与给定的命题公式A等价则称它为A的析取范式 A⟺A1∨A2∨...∨An,n≥1,Ai是基本积A\iff A_1∨A_2∨...∨A_n,n\ge1,A_i是基本积 A⟺A1∨A2∨...∨An,n≥1,Ai是基本积
任何一个命题公式的析取范式否是不唯一的运算符最少的称为 最简析取范式
¬(P∨Q)↔(P∧Q)⟺¬(¬(P∨Q))∧¬(P∧Q)∨¬(P∨Q)∧(P∧Q)⟺(P∨Q)∧(¬P∨¬Q)∨(¬P∧¬Q)∧(P∧Q)⟺Q∧¬P∨P∧¬Q\begin{aligned} ¬(P∨Q)↔(P∧Q) \\ \iff¬(¬(P∨Q))∧¬(P∧Q)∨¬(P∨Q)∧(P∧Q)\\ \iff(P∨Q)∧(¬P∨¬Q)∨(¬P∧¬Q)∧(P∧Q)\\ \iff Q∧¬P∨P∧¬Q \end{aligned} ¬(P∨Q)↔(P∧Q)⟺¬(¬(P∨Q))∧¬(P∧Q)∨¬(P∨Q)∧(P∧Q)⟺(P∨Q)∧(¬P∨¬Q)∨(¬P∧¬Q)∧(P∧Q)⟺Q∧¬P∨P∧¬Q 合取范式一个基本和之积组成的公式如果与给定的命题公式A等价则称它是A的合取范式 A⟺A1∧A2∧...∧An,n≥1,Ai是基本和A\iff A_1∧A_2∧...∧A_n,n\ge1,A_i是基本和 A⟺A1∧A2∧...∧An,n≥1,Ai是基本和
任何一个命题公式的合取范式否是不唯一的运算符最少的称为 最简合取范式
¬(P∨Q)↔(P∧Q)⟺¬(¬(P∨Q))∧¬(P∧Q)∨¬(P∨Q)∧(P∧Q)⟺(P∨Q)∧(¬P∨¬Q)\begin{aligned} ¬(P∨Q)↔(P∧Q) \\ \iff¬(¬(P∨Q))∧¬(P∧Q)∨¬(P∨Q)∧(P∧Q)\\ \iff(P∨Q)∧(¬P∨¬Q) \end{aligned} ¬(P∨Q)↔(P∧Q)⟺¬(¬(P∨Q))∧¬(P∧Q)∨¬(P∨Q)∧(P∧Q)⟺(P∨Q)∧(¬P∨¬Q)
极大项与极小项 极小项在n个变元的基本积中若每一个变元与其否定不同时存在而两者之一必出现且仅出现一次 n个变元可构成 2n2^n2n 个不同的极小项
m0⟺¬P1∧¬P2∧...∧¬Pnm1⟺¬P1∧¬P2∧...∧Pn⋮m2n−1⟺P1∧P2∧...∧Pn\begin{aligned} m_0 \iff ¬P_1∧¬P_2∧...∧¬P_n\\ m_1 \iff ¬P_1∧¬P_2∧...∧P_n\\ \vdots\\ m_{2^n-1} \iff P_1∧P_2∧...∧P_n \end{aligned} m0m1⋮m2n−1⟺¬P1∧¬P2∧...∧¬Pn⟺¬P1∧¬P2∧...∧Pn⟺P1∧P2∧...∧Pn
极小项下标与指派真值关系命题变元指派为1命题变元的否定指派为0 极大项在n个变元的基本和每个变元与其否定不同时存在而二者之一必出现且仅出现一次 n个变元可构成 2n2^n2n 个不同的极大项
M0⟺¬P1∨¬P2∨...∨¬PnM1⟺¬P1∨¬P2∨...∨Pn⋮M2n−1⟺P1∨P2∨...∨Pn\begin{aligned} M_0 \iff ¬P_1∨¬P_2∨...∨¬P_n\\ M_1 \iff ¬P_1∨¬P_2∨...∨P_n\\ \vdots\\ M_{2^n-1} \iff P_1∨P_2∨...∨P_n \end{aligned} M0M1⋮M2n−1⟺¬P1∨¬P2∨...∨¬Pn⟺¬P1∨¬P2∨...∨Pn⟺P1∨P2∨...∨Pn
极大项下标与指派真值关系命题变元指派为0命题变元的否定指派为1
极小项和极大项的性质 越交越小(极大项)大交小(F) mi∧mj⟺F,(i≠j)m_i∧m_j\iff F,(i\neq j)mi∧mj⟺F,(ij)∧i02n−1Mi⟺F∧_{i0}^{2^n-1}M_i\iff F∧i02n−1Mi⟺F¬mi⟺Mi¬m_i \iff M_i¬mi⟺Mi 越并越大极小项小交大(T) Mi∨Mj⟺T(i≠j)M_i∨M_j\iff T(i\neq j)Mi∨Mj⟺T(ij)∨i02n−1mi⟺T∨_{i0}^{2^n-1}m_i \iff T∨i02n−1mi⟺T¬Mi⟺mi¬M_i \iff m_i¬Mi⟺mi
主析取范式与主合取范式 主析取范式一个由极小项之和组成的公式且与给定的命题公式A等价 P∧TP⟺P∧(Q∨¬Q)mi∨mk⟺∑(i,k)P∧TP\iff P∧(Q∨¬Q) \\ m_i∨m_k \iff \sum(i,k) P∧TP⟺P∧(Q∨¬Q)mi∨mk⟺∑(i,k)
一个命题公式的真值表是唯一的因此一个命题公式的主析取范式是唯一的具有相同的主析取范式的命题公式二者逻辑等价 主合取范式一个由极大项之积组成的公式且与给定的命题公式A等价 P∨FP⟺P∨(Q∧¬Q)Mi∧Mk⟺π(i,k)P∨FP\iff P∨(Q∧¬Q)\\ M_i∧M_k \iff \pi(i,k) P∨FP⟺P∨(Q∧¬Q)Mi∧Mk⟺π(i,k)
一个命题公式的真值表唯一因此一个命题公式的主合取范式是唯一的具有相同的主合取范式的命题公式二者逻辑等价
主析取范式与主合取范式关系
代表极小项和极大项的下标是互补的即二者一起构成 1,2,...,2n−11,2,...,2^n-11,2,...,2n−1
主析取范式的个数
n个命题变元的命题公式其数量是无限的但任何一个命题公式都有等价的主析取范式
两个命题公式有相同的主析取范式那两个命题公式属于一个等价类
n个命题变元可构造22n个主析取范式或主合取范式n个命题变元可构造2^{2^n}个主析取范式或主合取范式 n个命题变元可构造22n个主析取范式或主合取范式
当n1,极小项有 2122^12212 ,即P、¬P主析取范式有
f1⟺Ff2⟺Pf3⟺¬Pf4⟺¬P∨P\begin{aligned} f_1\iff F \\ f_2\iff P \\ f_3 \iff ¬P \\ f_4 \iff ¬P∨P \end{aligned} f1⟺Ff2⟺Pf3⟺¬Pf4⟺¬P∨P
1.1.3 推理规则和证明方法
1. 推理基本概念
论证列出的前提和结论待证的结论若是文字形式则将论证转化为命题形式
证明有效论证的展开由一系列命题公式根据推理规则得出 若 H1∧H2∧...∧Hn⇒CH_1∧H_2∧...∧H_n\Rightarrow CH1∧H2∧...∧Hn⇒C 则称C是 H1∧H2∧...∧HnH_1∧H_2∧...∧H_nH1∧H2∧...∧Hn 的有效结论有效 推理正确≠\neq结论正确 永真蕴含式为真不等价于结论是真 若再加上前提是真则可得结论是真 若前提是假当结论为假时蕴含式也可能为真
2. 常用的推理规则
假言推理(分离规则) 析取三段论 规则P在推导的任何步骤上都可以引入前提规则T在推导中如果前面有一个或多个公式永真蕴含 S则可以把S引入推导过程
例 3. 证明方法
不常用方法
无义证明法P是假则蕴含式是真平凡证明法Q是真则蕴含式是真
直接证明法
假设P是真的如果能推得Q是真则 P→Q 是真
间接证明法(逆反证明法)
P→Q⟺¬Q→¬PP→Q\iff ¬Q→¬PP→Q⟺¬Q→¬P 若Q是假且P是假则 ¬Q→¬P¬Q→¬P¬Q→¬P 是真也就是 P→QP→QP→Q 是真
一.逆反命题 P1∧P2∧...∧Pn→QP_1∧P_2∧...∧P_n→QP1∧P2∧...∧Pn→Q
间接证明逆反公式是 ¬Q→P1∨P2∨...∨Pn¬Q→P_1∨P_2∨...∨P_n¬Q→P1∨P2∨...∨Pn 只需证明至少有一个i使 ¬Q→¬Pi¬Q→¬P_i¬Q→¬Pi 是真
二.附加前提 P1∧P2∧...∧Pn→(P→Q)P_1∧P_2∧...∧P_n→(P→Q)P1∧P2∧...∧Pn→(P→Q)
CP规则演绎定理等价公式 P1∧P2∧...∧Pn∧P→QP_1∧P_2∧...∧P_n∧P→QP1∧P2∧...∧Pn∧P→Q
若结论为蕴含式则前提可作为附加条件
三. P1∨P2∨...∨Pn→QP_1∨P_2∨...∨P_n→QP1∨P2∨...∨Pn→Q
分情况 证明
P1∨P2∨...∨Pn→Q⟺¬P1∧¬P2∧...∧¬Pn∨Q⟺(¬P1∨Q)∧(¬P2∨Q)∧...∧(¬Pn∨Q)⟺(P1→Q)∧(P2→Q)∧...∧(Pn→Q)\begin{aligned} P_1∨P_2∨...∨P_n→Q\\ \iff ¬P_1∧¬P_2∧...∧¬P_n∨Q\\ \iff (¬P_1∨Q)∧(¬P_2∨Q)∧...∧(¬P_n∨Q)\\ \iff (P_1→Q)∧(P_2→Q)∧...∧(P_n→Q) \end{aligned} P1∨P2∨...∨Pn→Q⟺¬P1∧¬P2∧...∧¬Pn∨Q⟺(¬P1∨Q)∧(¬P2∨Q)∧...∧(¬Pn∨Q)⟺(P1→Q)∧(P2→Q)∧...∧(Pn→Q)
反证法(归谬法)
一致性若公式 H1,H2,...,HnH_1,H_2,...,H_nH1,H2,...,Hn 的原子命题变元 P1,P2,...,PnP_1,P_2,...,P_nP1,P2,...,Pn 存在某一指派使得命题变元的积 P1∧P2∧...∧PnP_1∧P_2∧...∧P_nP1∧P2∧...∧Pn 具有真值T则命题公式集合 {H1,H2,...,Hn}\{H_1,H_2,...,H_n\}{H1,H2,...,Hn} 是一致的 反证法定理设 {H1,H2,...,Hn}\{H_1,H_2,...,H_n\}{H1,H2,...,Hn} 是一致的C是一命题公式如果 {H1,H2,...,Hn,¬C}\{H_1,H_2,...,H_n,¬C\}{H1,H2,...,Hn,¬C} 是非一致的则能从 H1,H2,...,HnH_1,H_2,...,H_nH1,H2,...,Hn 能推出 C。 欲证H1∧H2∧...∧Hn⇒C,只需证明H1∧H2∧...∧Hn∧¬C⇒F\begin{aligned} 欲证H_1∧H_2∧...∧H_n\Rightarrow C,只需证明H_1∧H_2∧...∧H_n∧¬C\Rightarrow F \end{aligned} 欲证H1∧H2∧...∧Hn⇒C,只需证明H1∧H2∧...∧Hn∧¬C⇒F
¬C假设前提
1.2 谓词逻辑
命题是谓词形式的一种特殊情况
由于原子命题不可拆
1.2.1 谓词和量词 将原子命题拆分成三部分个体词谓词量词 1. 个体词 个体代表个体的变元叫个体变元 个体域(论述域)谓词公式中个体变元的取值范围 每个论述域都至少有一个个体
2. 谓词 可以理解为函数表示变量间的某一种关系 谓词刻画个体的性质或个体间的关系的词个体用小写字母表示谓词用大写字母表示 谓词谓词命名式F(x)、G(x,y)等 F(x)表示x是质数 n元谓词表示n个个体间关系的谓词 谓词常元指定一个谓词的具体意义谓词变元一个字母代表任意谓词
全总个体域 不同个体变元的论述域集合可以理解为全体论述域大集合 不同的论述对象需用不同的 特性谓词 加以刻画
例子设F(x)表示“x是不怕死的”D(x)表示“x是要死的”,M(x)表示“x是人” 论述域是人类 “人总是要死的”—— ∀xD(x)\forall xD(x)∀xD(x)“有些人不怕死”——∃xF(x)∃xF(x)∃xF(x) 论述域全总个体域 由于论述域是全总个体域故需要添加特性谓词M(x) 人总是要怕死的——∀x(M(x)→D(x))有些人不怕死——∃x(M(x)∧F(x))\begin{aligned} 人总是要怕死的——\forall x(M(x)\rightarrow D(x))\\\\ 有些人不怕死——∃ \ x(M(x)∧F(x)) \end{aligned} 人总是要怕死的——∀x(M(x)→D(x))有些人不怕死——∃ x(M(x)∧F(x))
特性谓词的加入规则
全称量词特性谓词作为蕴含式的前件加入存在量词特性谓词作为合取项加入
在翻译命题时遇到全称量词提取特性谓词作为前件遇到存在量词提取特性谓词作为合取项
3. 量词
全称量词 ∀x\forall x∀x :“对一切x”、“对任一x”——变元的全称量化 存在量词 ∃x 存在一x、至少有一x——变元的存在量化 变元x的全称量化或存在量化量化的作用是约束变元
量化后所得命题的真值与论述域有关
量化断言和命题的关系 论述域有限的 ∀xP(x)⟺P(x1)∧P(x2)∧...∧P(xn)∃xP(x)⟺P(x1)∨P(x2)∨...∨P(xn)\begin{aligned} \forall xP(x) \iff P(x_1)∧P(x_2)∧...∧P(x_n)\\ ∃ xP(x) \iff P(x_1)∨P(x_2)∨...∨P(x_n) \end{aligned} ∀xP(x)⟺P(x1)∧P(x2)∧...∧P(xn)∃xP(x)⟺P(x1)∨P(x2)∨...∨P(xn) 论述域可数无限 ∀xP(x)⟺P(x1)∧P(x2)∧...∧P(xn)∧…∃xP(x)⟺P(x1)∨P(x2)∨...∨P(xn)∨…\begin{aligned} \forall xP(x) \iff P(x_1)∧P(x_2)∧...∧P(x_n)∧ \dots \\ ∃ xP(x) \iff P(x_1)∨P(x_2)∨...∨P(x_n)∨ \dots \end{aligned} ∀xP(x)⟺P(x1)∧P(x2)∧...∧P(xn)∧…∃xP(x)⟺P(x1)∨P(x2)∨...∨P(xn)∨… 论述域不可数无限无法表示
1.2.2 谓词公式
谓词演算的原子公式不出现命题联结词和量词的谓词命名式 P(x1,x2,...,xn)(n0,1,2...)P(x_1,x_2,...,x_n) (n0,1,2...)P(x1,x2,...,xn)(n0,1,2...)
P(x1,x2,...,xn)P(x_1,x_2,...,x_n)P(x1,x2,...,xn) 是n元谓词公式其中 x1,x2,...,xnx_1,x_2,...,x_nx1,x2,...,xn 是个体变项 谓词演算的合式公式 谓词演算的原子公式是谓词演算公式若AB是谓词演算公式则¬P、A∧B、A∨B、A→B、A↔B、∀xA(x)、∃xA(x)\forall xA(x)、∃ xA(x)∀xA(x)、∃xA(x)是谓词演算公式有限步骤的 1,2 构成的公式才是谓词演算公式 1. 自由变元与约束变元
辖域紧接于量词之后的最小的子公式叫量词的辖域 约束变元在辖域内的变元出现叫约束出现辖域内的变元叫约束变元 自由变元在辖域外的变元出现叫自由出现辖域外的变元叫自由变元 代入规则与改名规则 对于谓词公式A(x)x不出现在y的量词辖域中则称A(x)对y是自由的 代入规则 ≠\neq 改名规则代入规则——自由变元改名规则——约束变元
改名规则
若要改名则该变元在量词及其辖域中的所有出现均需一起更改改名时所选用的符号必须是量词辖域中未出现的符号最好是公式中未出现的符号
代入规则
在一公式中任一自由个体变元可用另一个体变元代替需全部替换该公式中的变元。且不能用约束变元的符号替换用以代入的变元与原公式中所有变元的名称都不能相同
2. 谓词公式的解释 解释I由非空区域D和对谓词公式G中常项符号、函数符号、谓词符号有下列规则进行的一组指定 对每一个常项符号指定D中一个元素对每一个n元函数符号指定一个函数对每一个n元谓词符号指定一个谓词 给定G的一个解释I则G在解释I下有一个真值记作 TI(G)T_I(G)TI(G) 若存在解释I使得G在解释I下取值为真则称G是可满足的建成满足G 若G的所有解释I都满足I则G为永真式重言式
1.2.3 谓词演算的永真式
1. 永真的定义
给定任一谓词公式A如果在论述域E上对公式A的谓词和个体变元进行上述两种指派所得命题
都真则称 A在E上有效 或 在E上永真至少有一个是真则称 A在E上可满足都假则称 A在E上永假 或 在E上不可满足
给定任一谓词公式A如果在任一论述域上对上述两种指派
A永真则称 A永真 或 有效A至少在一个域上可满足则称 A可满足A永假则称 A永假 或 不可满足
永真的判定
若谓词公式A的个体域和谓词的解释是有限的则可用真值表判定谓词公式A是否永真
2. 谓词公式的等价 两个任意谓词公式A和BE是A、B公有的论述域若对E上的任意解释所得的命题具有相同的真值则称公式A和B 遍及E等价即为 在E上 A⟺BA\iff BA⟺B A和B等价定义A⟺BA\iff BA⟺B 在 任一论述域 上都等价
谓词演算的基本等价式
命题演算的永真公式也是谓词演算的永真公式
含有量词的谓词演算的基本永真公式 常元的量词辖域 ∀xA⟺A∃xA⟺A\begin{aligned} \forall xA \iff A\\ ∃ xA \iff A \end{aligned} ∀xA⟺A∃xA⟺A 量词辖域对命题常元的扩展和收缩 ∀xA(x)∨P⟺∀x(A(x)∨P)∀xA(x)∧P⟺∀x(A(x)∧P)∃xA(x)∨P⟺∃x(A(x)∨P)∃xA(x)∧P⟺∃x(A(x)∧P)∀x(A(x)→B)⟺∃xA(x)→B∀x(B→A(x))⟺B→∀xA(x)∃x(A(x)→B)⟺∀xA(x)→B∃x(B→A(x))⟺B→∃xA(x)\begin{aligned} \forall xA(x)∨P \iff \forall x(A(x)∨P) \\ \forall xA(x)∧P \iff \forall x(A(x)∧P) \\ ∃ xA(x)∨P \iff ∃ x(A(x)∨P) \\ ∃ xA(x)∧P \iff ∃ x(A(x)∧P) \\ \forall x(A(x)\rightarrow B)\iff ∃ xA(x)\rightarrow B\\ \forall x(B\rightarrow A(x)) \iff B \rightarrow \forall xA(x)\\ ∃ x(A(x)\rightarrow B)\iff \forall xA(x)\rightarrow B\\ ∃ x(B\rightarrow A(x)) \iff B \rightarrow ∃ xA(x)\\ \end{aligned} ∀xA(x)∨P⟺∀x(A(x)∨P)∀xA(x)∧P⟺∀x(A(x)∧P)∃xA(x)∨P⟺∃x(A(x)∨P)∃xA(x)∧P⟺∃x(A(x)∧P)∀x(A(x)→B)⟺∃xA(x)→B∀x(B→A(x))⟺B→∀xA(x)∃x(A(x)→B)⟺∀xA(x)→B∃x(B→A(x))⟺B→∃xA(x) 全称量词与存在量词具有对偶性 ¬(∀xP(x))⟺∃x¬P(x)¬(∃xP(x))⟺∀x¬P(x)\begin{aligned} ¬(\forall xP(x)) \iff ∃ x¬P(x)\\ ¬(∃ xP(x)) \iff \forall x¬P(x)\\ \end{aligned} ¬(∀xP(x))⟺∃x¬P(x)¬(∃xP(x))⟺∀x¬P(x) 量词的分配形式 交起来的辖域小于分开交并起来的辖域大于分开并 对一切xA(x)∧B(x)是真。等价于。对一切xA(x)是真并且对一切xB(x)是真 ∀x(A(x)∧B(x))⟺∀xA(x)∧∀xB(x)\forall x(A(x)∧B(x)) \iff \forall xA(x)∧\forall xB(x) \\ ∀x(A(x)∧B(x))⟺∀xA(x)∧∀xB(x) 存在一个x使A(x)∨B(x)是真。等价于。存在一个x使A(x)是真或存在一个x使B(x)是真 ∃x(A(x)∨B(x))⟺∃xA(x)∨∃xB(x)∃ x(A(x)∨B(x)) \iff ∃ xA(x)∨∃ xB(x) \\ ∃x(A(x)∨B(x))⟺∃xA(x)∨∃xB(x) 量词对 →与↔ 的处理 只需用其对全功能集合{¬,∨,∧} 的恒等式即可推出
3. 谓词公式的永真蕴含式 全称推存在∀xP(x)⇒∃xP(x)\forall xP(x) \Rightarrow ∃ xP(x)∀xP(x)⇒∃xP(x) ∀xP(x)⇒P(y)或∀xP(x)⇒P(x)P(y)⇒∃xP(x)P(x)⇒∃xP(x)\begin{aligned} \forall xP(x) \Rightarrow P(y)\quad 或 \forall xP(x) \Rightarrow P(x)\\ P(y)\Rightarrow ∃ xP(x) P(x)\Rightarrow ∃ xP(x) \end{aligned} ∀xP(x)⇒P(y)P(y)⇒∃xP(x)或∀xP(x)⇒P(x)P(x)⇒∃xP(x) 上如果断言“对一切xP(x)是真”成立那么 “对任一确定x,P(x)是真” 下如果对某一确定的xP(x)是真那么断言 “存在一x使P(x)是真”成立 小范围 ⇒\Rightarrow⇒ 大范围大范围 ⇏\nRightarrow⇏ 小范围 交起来的辖域小于分开交并起来的辖域大于分开并 $∃ x(A(x)∧B(x)) \Rightarrow ∃ xA(x)∧∃ B(x) $ 小范围中存在的元素 ⇒\Rightarrow⇒ 大范围中存在该元素 大范围中存在的元素 ⇏\nRightarrow⇏ 小范围中存在的元素 $\forall xA(x)∨\forall xB(x) \Rightarrow \forall x(A(x)∨B(x)) $ 小范围中的所有元素 一定全部 被包含在大范围中 大范围中的所有元素 不一定全部 被包含在小范围 量词对前后件都是蕴含式的分配 ∃xA(x)→∀xB(x)⇒∀x(A(x)→B(x))∀x(A(x)→B(x))⇒∃xA(x)→∃xB(x)证明由CP规则,若上式成立则有下式成立⟺∀x(A(x)→B(x))∧∃xA(x)→∃xB(x)⟺¬∀x(A(x)→B(x))∨¬∃xA(x)∨∃xB(x)⟺¬∀x(A(x)→B(x))∨(∃xA(x)→∃xB(x))⟺∀x(A(x)→B(x))→(∃xA(x)→∃xB(x))∀x(A(x)→B(x))⇒∀xA(x)→∀xB(x)\begin{aligned} ∃ xA(x)\rightarrow \forall xB(x) \Rightarrow \forall x(A(x)\rightarrow B(x))\\ \forall x(A(x)\rightarrow B(x)) \Rightarrow ∃ xA(x)\rightarrow ∃ xB(x)\\ 证明由CP规则,若上式成立则有下式成立\\ \iff \forall x(A(x)\rightarrow B(x))∧∃ xA(x) \rightarrow ∃ xB(x)\\ \iff ¬\forall x(A(x)\rightarrow B(x))∨¬∃ xA(x) ∨ ∃ xB(x)\\ \iff ¬\forall x(A(x)\rightarrow B(x))∨(∃ xA(x) \rightarrow ∃ xB(x))\\ \iff \forall x(A(x)\rightarrow B(x))\rightarrow(∃ xA(x) \rightarrow ∃ xB(x))\\ \forall x(A(x)\rightarrow B(x)) \Rightarrow \forall xA(x)\rightarrow \forall xB(x)\\ \end{aligned} ∃xA(x)→∀xB(x)⇒∀x(A(x)→B(x))∀x(A(x)→B(x))⇒∃xA(x)→∃xB(x)证明由CP规则,若上式成立则有下式成立⟺∀x(A(x)→B(x))∧∃xA(x)→∃xB(x)⟺¬∀x(A(x)→B(x))∨¬∃xA(x)∨∃xB(x)⟺¬∀x(A(x)→B(x))∨(∃xA(x)→∃xB(x))⟺∀x(A(x)→B(x))→(∃xA(x)→∃xB(x))∀x(A(x)→B(x))⇒∀xA(x)→∀xB(x)
4. 多个量词的永真式
量词的次序同可互换异注意次序 ①对一切x和一切yP(x,y)为真。等价于。对一切y和一切xP(x,y)为真 ∀x∀yP(x,y)⟺∀y∀xP(x,y)\forall x\forall yP(x,y) \iff \forall y\forall xP(x,y) ∀x∀yP(x,y)⟺∀y∀xP(x,y)
②存在一个x和存在一个yP(x,y)为真。等价于。存在一个y和存在一个x,P(x,y)为真
∃x∃yP(x,y)⟺∃y∃xP(x,y)∃ x∃ y P(x,y) \iff ∃ y ∃ xP(x,y) ∃x∃yP(x,y)⟺∃y∃xP(x,y)
③全称存在存在 ⇏\nRightarrow⇏ 全称
∀x∀yP(x,y)⇒∃y∀xP(x,y)∀x∃yP(x,y)⇒∃x∃yP(x,y)\begin{aligned} \forall x\forall yP(x,y) \Rightarrow ∃ y\forall xP(x,y)\\ \forall x∃ yP(x,y) \Rightarrow ∃ x∃ y P(x,y) \end{aligned} ∀x∀yP(x,y)⇒∃y∀xP(x,y)∀x∃yP(x,y)⇒∃x∃yP(x,y)
④存在一切⇒\Rightarrow⇒一切存在一切存在⇏\nRightarrow⇏存在一切
∃y∀xP(x,y)⇒∀x∃yP(x,y)∃ y\forall xP(x,y) \Rightarrow \forall x∃ yP(x,y) ∃y∀xP(x,y)⇒∀x∃yP(x,y)
5. 谓词演算永真式的规则 替换规则 设 A(x1,x2,...,xn)⟺B(x1,x2,...,xn)A(x_1,x_2,...,x_n) \iff B(x_1,x_2,...,x_n)A(x1,x2,...,xn)⟺B(x1,x2,...,xn) 而A是公式C中的子公式用B替换C中之A得D则 C⟺DC \iff DC⟺D 对偶原理 在公式 A⟺BA\iff BA⟺B 或 A⇒BA\Rightarrow BA⇒B 中A、B仅含运算符∧、∨、¬将上式中的全称量词与存在量词互换∧、∨互换TF互换则
A∗⟺B∗,B∗⇒A∗A^* \iff B^*,B^*\Rightarrow A^* A∗⟺B∗,B∗⇒A∗
1.2.4 谓词演算的推理规则
1. 前束范式 所有量词均在谓词公式开头且辖域延伸到公式的末尾则该公式称为前束范式 对任意一个谓词公式都可以化为与他等价的前束范式
步骤
利用等价公式将谓词公式中的联结词 →与→去掉利用量词的对偶律将量词前面的否定深入谓词前面利用改名和代入规则以及量词辖域扩张的公式将量词转移到全式前面
例
¬∀x(∃yP(x,y)→∃x∀y(Q(x,y)∧∀y(P(y,x)→Q(x,y))))⟺¬∀x∃yP(x,y)→∃x∀y(Q(x,y)∧∀z(P(z,x)→Q(x,z)))⟺¬∀x∃yP(x,y)→∃u∀v(Q(u,v)∧∀z(P(z,u)→Q(u,z)))⟺∃x∀y¬(¬P(x,y)∨∃u∀v(Q(u,v)∧∀z(P(z,u)→Q(u,z)))⟺∃x∀y∃u∀v∀zP(x,y)∧¬(Q(u,v)∧P(z,u)→Q(u,z))⟺∃x∀y∃u∀v∀zP(x,y)∧(¬Q(u,v)∨¬(P(z,u)→Q(u,z))⟺∃x∀y∃u∀v∀zP(x,y)∧(¬Q(u,v)∨¬(¬P(z,u)∨Q(u,z))⟺∃x∀y∃u∀v∀zP(x,y)∧(¬Q(u,v)∨(P(z,u)∧¬Q(u,z))\begin{aligned} ¬∀x(∃yP(x,y)→∃x∀y(Q(x,y)∧∀y(P(y,x)→Q(x,y))))\\ \iff ¬∀x∃yP(x,y)→∃x∀y(Q(x,y)∧∀z(P(z,x)→Q(x,z)))\\ \iff ¬∀x∃yP(x,y)→∃u∀v(Q(u,v)∧∀z(P(z,u)→Q(u,z)))\\ \iff ∃x∀y¬(¬P(x,y)∨∃u∀v(Q(u,v)∧∀z(P(z,u)→Q(u,z)))\\ \iff ∃x∀y∃u∀v∀zP(x,y)∧¬(Q(u,v)∧P(z,u)→Q(u,z))\\ \iff ∃x∀y∃u∀v∀zP(x,y)∧(¬Q(u,v)∨¬(P(z,u)→Q(u,z))\\ \iff ∃x∀y∃u∀v∀zP(x,y)∧(¬Q(u,v)∨¬(¬P(z,u)∨Q(u,z))\\ \iff ∃x∀y∃u∀v∀zP(x,y)∧(¬Q(u,v)∨(P(z,u)∧¬Q(u,z))\\ \end{aligned} ⟺⟺⟺⟺⟺⟺⟺¬∀x(∃yP(x,y)→∃x∀y(Q(x,y)∧∀y(P(y,x)→Q(x,y))))¬∀x∃yP(x,y)→∃x∀y(Q(x,y)∧∀z(P(z,x)→Q(x,z)))¬∀x∃yP(x,y)→∃u∀v(Q(u,v)∧∀z(P(z,u)→Q(u,z)))∃x∀y¬(¬P(x,y)∨∃u∀v(Q(u,v)∧∀z(P(z,u)→Q(u,z)))∃x∀y∃u∀v∀zP(x,y)∧¬(Q(u,v)∧P(z,u)→Q(u,z))∃x∀y∃u∀v∀zP(x,y)∧(¬Q(u,v)∨¬(P(z,u)→Q(u,z))∃x∀y∃u∀v∀zP(x,y)∧(¬Q(u,v)∨¬(¬P(z,u)∨Q(u,z))∃x∀y∃u∀v∀zP(x,y)∧(¬Q(u,v)∨(P(z,u)∧¬Q(u,z))
任何谓词公式都可转化为与其等价的前束析取范式和束合取范式
2. 推理规则
XS——删X
转化为命题演算
XG——生X
使结论呈现为量化形式
全称指定规则——全称量词可以删除(Universal Specification) 可以是个体变元A(y)也可以是个体常元A©
存在指定规则(Existential Specification)
假设某一确定个体y使A(y)为真 使用条件 使用ES消去存在量词条件是P(x)中除x没有其他个体变元 y是A(x)中未出现的字母表示个体常元 A(x)对于y必须是自由的A(y)是暂用前提不能用作结论所以在结束前必须使用EG使之称为约束变元
存在推广原则(Existential Generalization) 全称推广(Universal Generalization) 使用条件
在推出A(x)的前提中x都必须不是自由的A(x)中的x不是由使用ES而引入的使用US引出自由变元x后ES引入的新变元不能在A(x)中自由出现 但上述推理中(2)-(3)是错误的违反UG规则的第二条使用US后ES引入的新变元d不能是自由变元违背UG的第二条所以错误
含义角度
∀x∃yP(x,y)\forall x∃ yP(x,y)∀x∃yP(x,y) 表示 “对所有x存在一个对应的y使得P(x,y)为真”而经过推导变为P(c,d)表示对于任一个体c,存在同一个体d使得P(c,d)成立显然不等价
3. 推理举例 ∀x(C(x)→(W(x)∧R(x)))∧∃xC(x)∧Q(x)⇒∃Q(x)∧∃xQ(x)\forall x(C(x) \rightarrow (W(x)∧R(x)))∧∃ xC(x)∧Q(x)\Rightarrow ∃ Q(x)∧∃ xQ(x)∀x(C(x)→(W(x)∧R(x)))∧∃xC(x)∧Q(x)⇒∃Q(x)∧∃xQ(x) 1.∃xC(x)P2.C(y)ES(1)3.∀x(C(x)→(W(x)∧R(x)))P4.C(y)→(W(y)∧R(y))US(3)5.W(y)∧R(y)6.R(y)7.∃xR(x)EG(6)8.Q(x)P9.∃xQ(x)EG(8)10.∃xQ(x)∧∃xQ(x)\begin{aligned} 1.\quad∃ xC(x) \quad P\\ 2. \quadC(y) \quad ES(1)\\ 3. \quad\forall x(C(x) \rightarrow (W(x)∧R(x))) \quad P\\ 4. \quadC(y) \rightarrow (W(y)∧R(y)) \quadUS(3)\\ 5. \quad W(y)∧R(y) \\ 6. \quadR(y)\\ 7. \quad∃ xR(x)\quad EG(6)\\ 8. \quad Q(x)\quad P\\ 9. \quad ∃ xQ(x)\quad EG(8)\\ 10. \quad ∃ xQ(x)∧∃ xQ(x) \end{aligned} 1.2.3.4.5.6.7.8.9.10.∃xC(x)C(y)∀x(C(x)→(W(x)∧R(x)))C(y)→(W(y)∧R(y))W(y)∧R(y)R(y)∃xR(x)Q(x)∃xQ(x)∃xQ(x)∧∃xQ(x)PES(1)PUS(3)EG(6)PEG(8) 给定前提 ∃x(P(x)∧∀y(Q(y)→R(x,y)))∀x(P(x)→∀y(S(y)→¬R(x,y)))\begin{aligned} ∃x(P(x)∧∀y(Q(y)→R(x,y)))\\ ∀x(P(x)→∀y(S(y)→¬R(x,y))) \end{aligned} ∃x(P(x)∧∀y(Q(y)→R(x,y)))∀x(P(x)→∀y(S(y)→¬R(x,y))) 证明∀x(Q(x)→¬S(x))∀x(Q(x)→¬S(x))∀x(Q(x)→¬S(x)) ∃x(P(x)∧∀y(Q(y)→R(x,y)))PP(a)∧∀y(Q(y)→R(a,y))ES(1)P(a)T(2)∀x(P(x)→∀y(S(y)→¬R(x,y)))PP(a)→∀y(S(y)→¬R(a,y))US∀y(S(y)→¬R(a,y))T(3)(5)S(z)→¬R(a,z)US(6)∀y(Q(y)→R(a,y))T(2)Q(z)→R(a,z)US(8)R(a,z)→¬S(z)逆反(7)Q(z)→¬S(z)传递性(9)(10)∀xQ(x)→¬S(x)UG(11)\begin{aligned} \quad ∃x(P(x)∧∀y(Q(y)→R(x,y)))\quad P\\ \quadP(a)∧∀y(Q(y)→R(a,y))\quadES(1)\\ \quadP(a)\quad T(2)\\ \quad∀x(P(x)→∀y(S(y)→¬R(x,y)))\quad P\\ \quadP(a)→∀y(S(y)→¬R(a,y))\quad US\\ \quad∀y(S(y)→¬R(a,y))\quad T(3)(5)\\ \quadS(z)→¬R(a,z)\quad US(6)\\ \quad∀y(Q(y)→R(a,y))\quad T(2)\\ \quadQ(z)→R(a,z)\quadUS(8)\\ \quadR(a,z)→¬S(z)\quad逆反(7)\\ \quadQ(z)→¬S(z)\quad传递性(9)(10)\\ \quad∀xQ(x)→¬S(x)\quadUG(11) \end{aligned} ∃x(P(x)∧∀y(Q(y)→R(x,y)))P(a)∧∀y(Q(y)→R(a,y))P(a)∀x(P(x)→∀y(S(y)→¬R(x,y)))P(a)→∀y(S(y)→¬R(a,y))∀y(S(y)→¬R(a,y))S(z)→¬R(a,z)∀y(Q(y)→R(a,y))Q(z)→R(a,z)R(a,z)→¬S(z)Q(z)→¬S(z)∀xQ(x)→¬S(x)PES(1)T(2)PUST(3)(5)US(6)T(2)US(8)逆反(7)传递性(9)(10)UG(11) 所有的有理数都是实数所有的无理数也是实数任何虚数都不是实数所以任何虚数既不是有理数也不是无理数 设 P(x):x是有理数 Q(x):x是无理数 R(x):x是实数 S(x):x是虚数 本题符号化为: ∀x(P(x)→R(x)),∀x(Q(x)→R(x)),∀x(S(x)→¬R(x))⇒∀x(S(x)→¬P(x)∧¬R(x))\begin{aligned} \forall x(P(x)\rightarrow R(x)),\forall x(Q(x)\rightarrow R(x)),\forall x(S(x)\rightarrow ¬R(x)) \\ \Rightarrow \forall x(S(x)\rightarrow ¬P(x)∧¬R(x)) \end{aligned} ∀x(P(x)→R(x)),∀x(Q(x)→R(x)),∀x(S(x)→¬R(x))⇒∀x(S(x)→¬P(x)∧¬R(x)) 推理过程 1.∀x(S(x)→¬R(x))P2.S(y)→¬R(y)US(1)3.∀x(P(x)→R(x))P4.P(y)→R(y)US(3)5.∀x(Q(x)→R(x))P6.Q(y)→R(y)US(5)7.¬R(y)→¬Q(y),¬R(y)→¬P(y)逆反(4)(6)8.S(y)→¬Q(y),S(y)→¬P(y)传递性(2)(7)9.(S(y)→¬Q(y))∧(S(y)→¬P(y))10.(¬S(y)∨¬Q(y))∧(¬S(y)∨¬P(y))等价(9)11.¬S(y)∨(¬Q(y)∧¬P(y))分配律(10)12.S(y)→(¬Q(y)∧¬P(y))等价(12)13.∀xS(x)→(¬Q(x)∧¬P(x))UG(12)\begin{aligned} 1.\quad \forall x(S(x)\rightarrow ¬R(x)) \quad P\\ 2.\quad S(y)\rightarrow ¬R(y) \quad US(1)\\ 3.\quad \forall x(P(x)\rightarrow R(x))\quad P\\ 4.\quad P(y)\rightarrow R(y)\quad US(3)\\ 5.\quad \forall x(Q(x)\rightarrow R(x))\quad P\\ 6.\quad Q(y)\rightarrow R(y)\quadUS(5)\\ 7.\quad ¬R(y)\rightarrow ¬Q(y),¬R(y)\rightarrow ¬P(y)\quad逆反(4)(6)\\ 8.\quad S(y)\rightarrow ¬Q(y),S(y)\rightarrow ¬P(y)\quad传递性(2)(7)\\ 9.\quad (S(y)\rightarrow ¬Q(y))∧(S(y)\rightarrow ¬P(y))\\ 10.\quad (¬S(y)∨¬Q(y))∧(¬S(y)∨¬P(y))\quad 等价(9)\\ 11.\quad ¬S(y)∨(¬Q(y)∧¬P(y))\quad分配律(10)\\ 12.\quad S(y)\rightarrow (¬Q(y)∧¬P(y))\quad 等价(12)\\ 13.\quad \forall xS(x)\rightarrow (¬Q(x)∧¬P(x))\quad UG(12) \end{aligned} 1.2.3.4.5.6.7.8.9.10.11.12.13.∀x(S(x)→¬R(x))S(y)→¬R(y)∀x(P(x)→R(x))P(y)→R(y)∀x(Q(x)→R(x))Q(y)→R(y)¬R(y)→¬Q(y),¬R(y)→¬P(y)S(y)→¬Q(y),S(y)→¬P(y)(S(y)→¬Q(y))∧(S(y)→¬P(y))(¬S(y)∨¬Q(y))∧(¬S(y)∨¬P(y))¬S(y)∨(¬Q(y)∧¬P(y))S(y)→(¬Q(y)∧¬P(y))∀xS(x)→(¬Q(x)∧¬P(x))PUS(1)PUS(3)PUS(5)逆反(4)(6)传递性(2)(7)等价(9)分配律(10)等价(12)UG(12) 反证
