1.1 命题
1.1.1 基本概念
断言:一个陈述语句。祈使句、疑问句一定不是断言。
命题:要么为真,要么为假,不能二者都是的断言。
原子命题(本源命题):一个命题已不能分解成更简单的命题
命题和本源命题常用大写字母P、Q、R表示 eg.P:4是质数
1.1.2 命题联结词
复合命题:命题和原子命题可通过一些联结词构成新命题
联结词:命题验算中的运算符,叫逻辑运算符或逻辑联结词
常用的逻辑联结词
- 否定词 ¬
- 合取词 ^
P^Q称为P和Q的合取,P并且Q - 析取词 v
PvQ称为P和Q的析取,P或Q - 蕴涵词 ->
P->Q称为P蕴含Q,如果P,那么Q,P叫做前提、假设或前件,Q叫做结论或后件
P->Q 等价与 ¬PvQ
形式蕴含:用蕴含式来断言前提和结论之间的因果或实质关系
实质蕴含:前提和结论并不需要有因果和实质关系
P->Q的逆命题:Q->P
P->Q的反命题:¬P -> ¬Q
P->Q的逆反命题:¬Q -> ¬P - 等值词↔
P↔Q称为等值式,读做P等值于Q(当且仅当P则Q)
P↔Q 等价于 P->Q ^ Q->P
运算符结合力的由强至弱的顺序为¬ 、 ^ 、 v 、 -> 、 ↔。凡符合此顺序的,括号均可省去
1.1.3 命题变元和命题公式
命题变元:真值未指定的任意命题
命题常元:真题已指定的命题
原子公式:单个命题变元或命题常元
命题公式:命题变元的断言,由以下规则生成的公式叫命题公式
- 单个原子公式是命题公式
- 若A和B是命题公式,则¬A,(A^B)、(AVB)、(A->B)、(A↔B)是命题公式
- 有限步的应用规则1和2生成的公式,才叫命题公式
命题公式的真假值一般是不确定的。当命题公式中所有的命题变元代以命题时,命题公式就变为命题
两个命题公式如果有相同的真值,则称它们是逻辑等价命题
1.2 重言式
1.2.1 基本概念
指派:对有n个命题变元的命题公式,命题变元的真值有2n种不同的组合,每一种组合叫做一种指派
重言式(永真式):对应于所有指派,命题公式均取值为真,eg.Pv¬P
矛盾式(永假式):对应于所有指派,命题公式均取值为假,eg.P^¬P
偶然式:不是重言式,也不是矛盾式,这种命题公式叫偶然式
可满足的:一个公式如果至少存在一个指派,使其值为真
非永真:如果至少存在一个指派,使其值为假
1.2.2 恒等式
逻辑恒等式:如果A↔B是重言式,则A与B对任何指派都有相同的真值。记为<=>
注意:区分等值词↔和等价<=>的关系:↔是逻辑联结词(运算符),而<=>是表示A和B有逻辑等价这个关系的符号,它的作用相当于代数中的"="
1.2.3 永真蕴含式
证明方法
- 假定前件是真,若能推出后件是真,则此蕴含式是真
- 假定后件是假,若能推出前件是假,则此蕴含式是真
1.2.6 对偶原理
对偶规则:^ -> v、v -> ^、T->F、F->T
注意:对偶不涉及否定联结词¬
对偶的对偶仍为自身,对偶是相互的
对偶原理
若A<=>B,且A、B为由命题变元P1,P2,……,Pn及联结词^ 、v、¬构成的公式,则A*<=>B*
若A=>B,且A、B为由命题变元P1,P2,……,Pn及联结词^ 、v、¬构成的公式,则B*=>A*
1.3 范式
1.3.1 析取范式和合取范式
基本积:命题公式中的一些命题变元和一些命题变元的否定之积
eg.P ^ Q、¬P ^ Q
基本和:命题公式中的一些命题变元和一些命题变元的否定之和
eg.PvQ、PvQv¬Q
任何一个命题公式都可求得它的析取范式,因为->和<=>可用^、v和¬表达,但一个命题公式的析取范式不是唯一的,把运算符最少的称为最简析取范式
如果给定的公式的析取范式中每个基本积都是永假式,则该式也必定是永假式
任何一个命题公式都可求得它的合取范式,因为->和<=>可用^、v和¬表达,但一个命题公式的合取范式不是唯一的,把运算符最少的称为最简合取范式
如果给定的公式的合取范式中每个基本积都是永真式,则该式也必定是永真式
1.3.2 主合取范式和主析取范式
极小项:在n个变元的基本积中,若每一个变元与其否定不同时存在,而两者之一必出现一次且仅出现一次,则这种基本积叫极小项
主析取范式:一个由极小项之和组成的公式
一个命题的主析取范式可通过真值表求解,真值表是唯一的,因此一个命题公式的主析取范式也是唯一的。
两个命题公式如果有相同的主析取范式,那么这两个命题公式是逻辑等价的
极大项:在n个变元的基本和中,若每一个变元与其否定不同时存在,而两者之一必出现一次且仅出现一次,则这种基本和叫极大项
主合取范式:一个由极大项之积组成的公式
一个命题公式的主合取范式也是唯一的。
两个命题公式如果有相同的主析取范式,那么这两个命题公式是逻辑等价的
一个命题公式的主析取范式和主合取范式紧密相关,代表极小项和极大项的足标是互补的。eg.P ^ Q v R <=> ∑(1,3,5,6,7) <=> π(0,2,4)
1.3.3 主析取范式/主合取范式的个数
n个命题变元可构造2的2n次幂个不同的主析取范式/主合取范式
1.4 联结词的扩充与归约
与非:P↑Q <=> ¬(P^Q)
或非:P↓Q <=> ¬(PvQ)
异或:P⊕Q <=> ¬PvQ ^ Pv¬Q
蕴含否定:¬(P->Q)
只用^、v、¬三个联结词构造的式子,就足以把一切命题公式等价地表示出来
1.5 推理规则和证明方法
规则P:在推导的任何步骤上都可以引入前提
规则T:在推导中,如果前面有一个或多个公式永真蕴含S,则可把S引进推导过程
1.6 谓词和量词
谓词
个体:命题中所涉及的对象
谓词:刻画个体的性质或若干个体间关系的模式。一般用大写字母P、Q、R…表示
eg.Q(x,y):x生于y
量词
全称量词:∀x P(x)表示对一切x,P(x)为真
存在量词:Ex P(x)表示存在一些x使P(x)为真