1.3命题公式及翻译解析

（完整版）离散数学电子教材1（可编辑修改word版）第1 章命题逻辑逻辑是研究人的思维的科学，包括辩证逻辑和形式逻辑。

辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。

形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。

数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。

所谓的数学方法也就是用一套有严格定义的符号，即建立一套形式语言来研究。

因此数理逻辑也称为符号逻辑。

数理逻辑的基础部分是命题逻辑和谓词逻辑。

本章主要讲述命题逻辑，谓词逻辑将在第2 章进行讨论。

1.1命题及其表示1.1.1命题的基本概念数理逻辑研究的中心问题是推理（Inference)，而推理就必然包含前提和结论，前提和结论都是表达判断的陈述句，因而表达判断的陈述句就成为推理的基本要素。

在数理逻辑中，将能够判断真假的陈述句称为命题。

因此命题就成为推理的基本单位。

在命题逻辑中，对命题的组成部分不再进一步细分。

定义1.1.1 能够判断真假的陈述句称为命题（Proposition）。

命题的判断结果称为命题的真值，常用T(True)（或1）表示真，F(False)（或0）表示假。

真值为真的命题称为真命题，真值为假的命题称为假命题。

从上述的定义可知，判定一个句子是否为命题要分为两步：一是判定是否为陈述句，二是能否判定真假，二者缺一不可。

例1.1.1 判断下列句子是否为命题（1）北京是中国的首都。

（2）请勿吸烟！（3）雪是黑的。

（4）明天开会吗？（5）x+y=5。

（6）我正在说谎。

（7）9+5≤12 。

（8）1+101=110 。

（9）今天天气多好啊！（10）别的星球上有生物。

解在上述的十个句子中，（2）、（9）为祈使句，（4）为疑问句，（5）、（6）虽然是陈述句，但（5）没有确定的真值，其真假随x、y 取值的不同而有改变，（6）是悖论(Paradox)（即由真能推出假，由假也能推出真），因而（2）、（4）、（5）、（6）、（9）均不是命题。

离散数学第一章1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。

1.1.2 命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。

A1:我是一名大学生.[10]：我是一名大学生。

R：我是一名大学生。

1.2命题联结词1.2.1 否定联结词﹁PP P0 11 01.2.2 合取联结词∧P∧P Q Q0 0 00 1 01 0 01 1 11.2.3 析取联结词∨P∨P Q Q0 0 00 1 11 0 11 1 11.2.4 条件联结词→P Q Q0 0 10 1 11 0 01 1 11.2.5 双条件联结词?P?P Q Q0 0 10 1 01 0 01 1 11.2.6 与非联结词↑P↑P Q Q0 0 10 1 11 0 11 1 0性质：（1）P↑P?﹁（P∧P）?﹁P；（2）（P↑Q）↑（P↑Q）?﹁（P↑Q）? P∧Q；（3）（P↑P）↑（Q↑Q）?﹁P↑﹁Q? P∨Q。

1.2.7 或非联结词↓P↓P Q Q0 0 10 1 01 0 0性质：（1）P↓P?﹁（P∨Q）?﹁P；（2）（P↓Q）↓（P↓Q）?﹁（P↓Q）?P∨Q；（3）（P↓P）↓（Q↓Q）?﹁P↓﹁Q?﹁（﹁P∨﹁Q）?P∧Q。

1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、P?Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。

例如，下面的符号串都是公式：（（（（﹁P）∧Q）→R）∨S）（（P→﹁Q）?（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）?（∧Q））（∧Q）1.3.2 命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。

第一章命题逻辑1.1 命题及其表示方法1.2 联结词1.3 命题公式与翻译1.4 真值表与等价公式1.5 重言式与蕴含式1.6 其它联结词1.7 对偶与范式1.8 推理理论1.1 命题及其表示方法命题：具有确定真值的陈述句命题的类型（原子命题和复合命题）命题语句的形式（陈述句）命题的表示（一个命题标识符（比如P）表示确定的命题）1.2 联结词1. 否定⌝2.合取∧（TT T）3. 析取∨（FF F）4. 条件→(TF F)5. 双条件↔(同T异F)1.3 命题公式与翻译命题公式●所谓命题的符号化就是把一个用文字叙述的句子相应地写成由命题标识符、联结词和括号表示的合式公式。

●符号化应该注意下列事项:•①确定给定句子是否为命题。

•②句子中连词是否为命题联结词。

•③要正确地表示原子命题和适当选择命题联结词。

命题符号化的重要性●命题符号化是很重要的，一定要掌握好，在命题推理中最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。

1.4 真值表与等价公式真值表的构造方法1) 找出公式中所含的全体命题变元P1, P2, …, Pn, (若无下角标就按字典顺序排列), 列出2n个赋值. 赋值从00…0开始, 然后按二进制加法依次写出各赋值, 直到11…1为止.(2) 按从低到高的顺序写出公式的各个层次.(3) 对应各个赋值计算出各层次的真值, 直到最后计算出公式的真值.等价公式等价式的判别方法•真值表法•等价演算法基本等价式(1)对合律（双重否定）：⌝⌝P⇔P(2)幂等律：P∧P⇔P，P∨P⇔P(3)结合律：(P∧Q)∧R⇔P∧(Q∧R)，(P∨Q)∨R⇔P∨(Q∨R)(4)交换律：P∧Q⇔Q∧P，P∨Q⇔Q∨P(5)分配律：P∧(Q∨R)⇔(P∧Q)∨(P∧R)，P∨(Q∧R)⇔(P∨Q)∧(P∨R)(6)德·摩根律：⌝ (P∧Q) ⌝⇔P∨⌝Q，⌝ (P∨Q) ⌝⇔P∧⌝Q(7)吸收律：P∧(P∨Q)⇔P，P∨(P∧Q)⇔P(8)同一律：P∧T⇔P，P∨F⇔P(9)零律：P∧F⇔F，P∨T⇔T(10)否定律：P∧⌝P⇔F，P∨⌝P⇔T(11) 条件式转化律：P→Q⌝⇔P∨Q，P→Q⌝⇔Q→⌝P(12) 双条件式转化律：P↔Q ⇔(P→Q)∧(Q→P) ⇔(P∧Q)∨(⌝P∧⌝Q)⌝ (P↔Q) ⇔P⌝↔Q ⌝⇔P↔Q(13) 输出律(CP规则)：P→(Q→R) ⇔(P∧Q)→R1.5 重言式与蕴含式●定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。

✹命题公式（proposition formula）✹由命题常元、变元和联结词组成的形式更为复杂的命题✹命题公式（proposition formula ）定义✹命题常元和命题变元是命题公式，特别的称作原子公式或原子✹如果A,B是命题公式，那么(¬A), (A∧B), (A∨B), (A→B), (A↔B)也是命题公式✹只有有限步引用上述两条所组成的符号串是命题公式✹重言式（永真式）tautology✹命题变元的所有赋值都是命题公式的成真赋值✹矛盾式（永假式、不可满足式）contradiction✹命题变元的所有赋值都是命题公式的成假赋值✹可满足式(contingency)✹命题公式至少有一个成真赋值✹✹重言式的代入原理(rule of substitution)✹将重言式A中的某个命题变元p的所有出现都代换为命题公式B，得到的命题公式记作A(B/p)，A(B/p)也是重言式。

✹命题公式的替换原理(rule of replacement)✹将命题公式A中的子公式C的部分出现替换为和C逻辑等价的公式D（C╞╡D ），得到的命题公式记作B，则A╞╡B。

✹真值函数（truth function）✹如果将联结词看作逻辑运算符，那么包含命题变元p1, p2, …p n的公式A可以看作是p1, p2, …p n的真值函数✹指派（赋值assignments）✹对任意给定的p1, p2, …p n的一种取值状况，称为指派或者赋值✹析取范式(disjunctive normal form)✹公式A’称作公式A的析取范式，如果✹A’╞╡A✹A’为合取子句或者若干合取子句的析取✹合取范式(conjunctive normal form)✹公式A’称作公式A的合取范式，如果✹A’╞╡A✹A’为析取子句或者若干析取子句的合取✹主析取范式(major disjunctive form)✹公式A’称作公式A(p1, p2, …p n)的主析取范式，如果✹A’是A的析取范式✹A’中每一个合取子句里p1, p2, …p n均恰出现一次✹主合取范式(major conjunctive form)✹公式A’称作公式A(p1, p2, …p n)的主合取范式，如果✹A’是A的合取范式A’中每一个析取子句里p1, p2, …p n均恰出现一次✹联结词集的完备性✹如果任意一个真值函数都可以用仅包含某个联结词集中的联结词的命题公式表示，则称这个联结词集为功能完备集✹形式系统是一个符号体系✹系统中的概念由符号表示✹推理过程即符号变换的过程✹以若干最基本的重言式作为基础，称作公理（axioms）✹系统内符号变换的依据是若干确保由重言式导出重言式的规则，称作推理规则（rules of inference）✹公理和推理规则确保系统内由正确的前提总能得到正确的推理结果✹证明(proof)✹公式序列A1,A2,…,A m称作A m的一个证明，如果A i(1≤i≤m)或者是公理，或者由A j1,…,A jk(j1,…,jk<i)用推理规则推得。

离散数学一、逻辑和证明1.1命题逻辑命题：是一个可以判断真假的陈述句。

联接词：A、V、一、f「。

记住“p仅当q”意思是“如果p,则q"，即p-。

记住“q除非p”意思是“」p-q”。

会考察条件语句翻译成汉语。

构造真1.2语句翻译系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。

1.3命题等价式逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。

证逻辑等价是通过p推导出q,证永真式是通过p推导出T。

(p—r)A(q-r) = (pVq)-r(p—q)V(p-r) = p—(qVr)(p—r)V(q-r) = (pAq)-r双条件命题等价式pf = (pfq) A (qfp)pf = -pfqpf Q (pAq) V(-pA-q)「(pf) = pfq1.4量词谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如V x>0P(x)。

当论域中的元素可以一一列举，那么V xP(x)就等价于P(x1)AP(x2)...A P(xn)。

同理，3 xP(x)就等价于 P(x1)VP(x2)...VP(xn)。

两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如V x(P(x)AQ(x))和(V xP(x)) A (V xQ(x))。

量词表达式的否定：「V xP(x) Q 3 x-P(x),「3 xP(x) Q V x-P(x)。

1.5量词嵌套我们采用循环的思考方法。

量词顺序的不同会影响结果。

语句到嵌套量词语句的翻译，注意论域。

嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。

1.6推理规则一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。

但有效论证不代命题和量化命题的组合使用。

二、集合、函数、序列、与矩阵2.1集合£说的是元素与集合的关系，^说的是集合与集合的关系。