北京大学离散数学教材 1

命题逻辑基本概念1逻辑是解决推理方法的学科，中心是推理，基本要素是命题，所以称为命题逻辑。

数理逻辑则是用数学方法研究推理。

学习目的本章首先要深刻理解命题的概念，理解原子命题和符合命题的关系，在此基础之上理解逻辑联结词的定义，命题公式的定义和分类，最后熟练掌握并应用真值表的构造基本内容：z命题概念；z逻辑联结词概念，复合命题和联结词的关系；z命题符号化和翻译z合式公式概念及分类；z构造真值表判定公式类型命题(statement, proposition)概念在二值逻辑中，命题是或真或假，而不会同时又真又假的陈述句。

z陈述句；z或真或假，唯一真值；例：(1) 地球是圆的；真的陈述句，是命题(2) 2+3=5；真的陈述句，是命题(3) 你知道命题逻辑吗？非陈述句，故非命题(4) 3-x=5；陈述句,但真假随x的变化而变化，非命题(5) 请安静！非陈述句，故非命题(6) 火星表面的温度是800°C；现时不知真假的陈述句，但只能要么真要么假，故是命题(7) 明天是晴天；尽管要到第二天才能得知其真假，但的确是要么真要么假，故是命题(8) 我正在说谎；无法得知其真假，这是悖论注意: (4)不是命题，后续章节中会提到，这被称为谓词，命题函数或命题变项。

分类：z简单命题，通常用p, q, r,…,等表示命题变项，命题常项用1(T)，0(F)表示；z复合命题，由简单命题和联结词构成；逻辑联结词和复合命题多个命题变项由联结词联结起来成为复合命题。

否定式和否定联结词(negation)命题p的非或否定，称为p的否定式，表示为¬p；符号¬即为否定联结词。

真值表：p¬ pT FF T严格说，¬ p不是复合命题。

例：p：今天天气好；¬p：今天天气不好p：2+5>1；¬p： 2+5≤1；在此情形下，p为真，¬p为假。

合取式和合取联结词(conjunction)p且q称为p, q的合取式，记为p∧q；符号∧即为合取联结词。

这是逻辑“与”。

p Q p∧qT T TT F FF T FF F F相应的日常用语为：“既…又…”，“不但(仅)…而且…”，“虽然…但是…”等等。

例：1) p: 今天大太阳，q: 今天热，p∧q: 今天大太阳且热；2)p: 今天上课有人迟到，q:2+5>1，p∧q: 今天上课有人迟到且2+5>1；注意 2)中的结果，我们可以用逻辑联结词来联结两个日常生活中无关的命题。

析取式和析取联结词(disjunction)p或者q称为p, q的析取式，记为p∨q；符号∨即为析取联结词。

p q p∨qT T TT F TF T TF F F这是逻辑“或”。

注意p和q可以同时为真，所以这是“相容或”。

另外还有p、q不可能同时为真的“相斥或”。

在数学和计算机学科中“或”是指“相容或”，“相斥或”用另一名称“异或”表示。

异或式和异或联结词(exclusive or)p或q中只可能有一个为真称为p, q的异或式，记作p∨q，读作“p异或q”。

符号∨称为异或联结词。

p q p∨q p q p∨qF F F000F T T或011T F T101T T F110p∨q为真当且仅当p, q只有一个为真。

例(1) p：今天大太阳，q：今天热；p∨q: 今天大太阳或者热。

(2) p：今天上课有人迟到，q：2+5>1；p∨q：今天上课有人迟到或2+5>1。

(3) p：他生于1966年，q：他生于1965年；p∨q：他生于1966年或1965年。

(4) p: 他今天骑车来上课，q: 他今天走路来上课，p、q为异或蕴涵式和蕴涵联结词(conditional statement, implication)如果p则q称作p、q的蕴涵式，记为p→q。

→为蕴涵联结词，p、q分别为蕴涵式的前件和后件。

p q p→qT T TT F FF T TF F T注意p是q的充分条件，q是p的必要条件。

“只要p就q”、“p仅当q”、“只有q才p”等可表示成p→q蕴涵式的一个应用：数学归纳法(1) 证明P(n0)成立；(2) 证明k≥n0, P(k)→P(k+1)总是成立在(1)中，P(k)→P(k+1)总是成立意味着P(k)→P(k+1)的真值为T，从而只可能是真值表中的1,3,4情形，而(1)中证明前件为真，所以后件也一定为真。

等价式和等价联结词(equivalence, biconditional) p当且仅当q称作p、q的等价式，记p↔q。

↔称为等价联结词，p是q的充要条件。

p q p↔qT T TT F FF T FF F T以上介绍了六种常用的逻辑联结词以及与之相关的复合命题。

这些联结词反映了复合命题及其支命题之间抽象的逻辑关系。

复合命题的符号化一般可以根据上述定义进行，基本步骤如下：z1) 找出各个支命题，并逐个符号化；z2) 找出各个连接词，符号成相应联结词；z3) 用联结词将各支命题逐个联结起来；例1.7将下列命题符号化：(1) 李明是计算机系的学生，他住在312室或313室．(2) 辱骂和恐吓决不是战斗；(3) 李瑞和李珊是姐妹。

(4) 除非天气好，否则我是不会去公园的；解 (1)首先用字母表示简单命题．p：李明是计算机系的学生．q：李明住在312室．r：李明住在313室．该复合命题可表示为p∧(q∨r)，因为李明不会既住在312室，又住在313室，所以这里不用∨，而用∨。

(2) 设p：辱骂不是战斗。

q：恐吓不是战斗。

p∨q(3) 设p：李瑞和李珊是姐妹p(4)设p：今天天气好。

q：我去公园。

q→p合式公式和真值函数命题形式各种复合命题的符号化表达式，即为此命题的命题形式，它给出的是复合命题及其简单命题之间真值关系的逻辑骨架。

命题形式必定是合式公式。

合式公式：合式公式，也称命题公式，递归定义为：(1) p, q, r, … ,1 , 0 是合式公式；(2) 如果A是合式公式，则¬A也是；(3) 如果A和B是合式公式，则由逻辑联结词联结A和B的符号串也是；(4) 有限次应用(1)-(3)构成的符号串才是合式公式。

(1)是递归定义的基础，直接规定简单的内容；(2), (3)是递归定义的归纳，规定了是由简单到复杂的过程；4)是递归定义的界限，规定了满足前述(1)~(3)条件的最小范围。

在一个复杂的公式中，为了避免歧义需要引进许多的括号，但如果括号太多会使人眼花缭乱，如((p∧(q∨r))→((p∨q)∧(r∨s)))，共有6对括号，为了减少括号并不引起歧义，引进如下省略括号的约定：z(1) 公式最外层的括号可以省略；z(2) 规定联结词运算优先级别由高到低是：¬、∧、∨、∨、→、↔，若无括号，优先级高的先运算；z(3) 若同一个联结词连续多次出现且无括号，则按从左到右的顺序运算。

按照上述约定，((p∧(q∨r))→((p∨q)∧(r∨s)))省略了三对括号简化为p∧(q∨r) →(p∨q)∧(r∨s)。

省略括号只是让公式书写简便，但并不能改变起复杂性。

合式公式的层次：递归定义：(1) 如果A是单个命题常项或命题变项p, q, r,s, …,0 , 1，则称A是0层公式；(2) 称A是n+1(n≥0)层公式，是指A符合下列情况之一：z(a) A=¬B，B是n层公式；z(b) A=(A∧B)，其中B、C分别是i层和j层公式，且n=max(i, j)；z(c) A=(A∨B)，其中B、C的层次同(b)；z(d) A=(A∨B)，其中B、C的层次同(b)；z(e) A=(A→B)，其中B、C的层次同(b)；z(f) A=(A↔B)，其中B、C的层次同(b)；(3) 若A的最高层次为k，则称A是k层公式。

注意(1) “=”即为通常意义上的等号。

(2) 定义中不仅有p, q, r, s,…,0 ,1等，而且引入了大写的A、B、C等代表任意的合式公式，不同于p,q, r,…,及联结词构成的表示某个具体的公式，两者是命题逻辑中不同层次上的语言。

真值赋值及公式分类, p2,…p n是出现在A中的所有令A是命题形式，p1命题变项，给p, p2,…p n指派一组真值，称为对A1的一个赋值，也称为一个解释。

若一个赋值使得A的真值为真，则称此赋值满足A，而称此赋值为A的一个成真赋值，相应地若A的值为假，称此赋值不满足A，而称此赋值为A的一个成假赋值。

一个含有n个命题变项的命题形式，共有2n个赋值。

例已知A是含命题变项p, q, r的命题形式，其成真赋值为000,010,101，求¬A的成真赋值和成假赋值。

解：A的成假赋值为001,011,100,110,111，所以¬A的成真赋值为：001,011,100,110,111；成假赋值为：000,010,101。

,B2,…B n分别替换命题形式A中的命用命题形式B1, p2,…p n得到的新的命题形式。

称为A的题变项p1一个替换实例。

例如，p→(¬p→q)，以p→q替换p，以r替换q，则得到原式的一个替换实例为(p→q)→(¬ (p→q )→r)。

命题形式的分类：z重言式(tautology)：值总是为真的命题形式。

如果一个蕴涵式A→B是重言式，则记作A⇒B，表示由A可推导出B；同样如果一个等价式A↔B是重言式，则记作A⇔B，表示A和B等值。

注意⇒和⇔不是逻辑联结词，它们表示的分别是逻辑推理和逻辑等值运算，下面的章节将分别讨论。

z矛盾式(contradiction)：值总是为假的命题形式。

z可满足式(contingency)。

重言式也是可满足式，不过还是将命题形式分成三类：重言式、矛盾式、可满足式；即可满足式不包含重言式。

这种分类主要是为了体现重言式的重要性，实际上在命题逻辑中公理、定理都是重言式，在自然推理的过程中，一个正确的推理也必须是重言式。

设A命题形式，则z A是重言式，则A的任何替换实例都是重言式；z A是矛盾式，则A的任何替换实例都是矛盾式；真值表和构成真值表的方法：真值表：命题形式在其命题变项取所有可能真值时对应的真值列成的表。

构成真值表的方法：z找出给定命题形式中的所有命题变项，列出所有可能的取值：z由低到高列出命题形式的各层次；z计算各层次的的值，直至最后计算命题形式的值。

总可以在有限步内构造一个命题形式的真值表，并根据该真值表来判断其类型。

这种在有限步内判定一个命题形式是重言式、矛盾式还是可满足式的问题，称为命题形式的判定问题，真值函数：一个n元真值函数是指F：{0，1}n→{0，1}，(n≥1)，即此函数以n个命题变项为变元，其定义域和值域均由真、假两值构成。

真值函数同样可以用真值表表示，这是真值函数在其命题变项所有可能取值下得到的值列成的表。