离散数学考前复习:(二)数理逻辑
离散数学考前复习:(二)数理逻辑
2.1 命题及联结词
-
命题:命题是指一个判断(陈述)的语义(实际表达的概念),这个概念是可以被定义并观察的现象。命题不是指判断(陈述)本身,而是指所表达的语义。当相异判断(陈述)具有相同语义的时候,他们表达相同的命题。
-
命题联结词:
非:否定联结词(-p为真仅当p为假)
并:合取联结词(p∧q为真当且仅当q,p同为真)
或:析取联结词(p∨q为真当且仅当p或q有一为真)
蕴涵:蕴涵联结词(p→q为假仅当p为真q为假)
等价:等价联结词(p↔q为真仅当p,q的真值相同) -
命题联结词的优先级
(1)否定<合取<析取<蕴涵<等价
(2)同级的联结词按从左到右确定
(3)括号优先级最高
2.2 命题公式和分类
-
原子命题公式(合式公式,又称命题公式、公式):
(1)单个命题常项或变项是合式公式;
(2)如果A是合式公式,则﹁A也是合式公式;
(3)如果A,B是合式公式,则P∧Q、P∨Q、P→Q、 P↔Q也是合式公式;
(4)只有有限次地应用(1)~(3)所包含的命题变元,联结词和括号的符号串才是合式公式。 -
成真赋值:指定一组值使A为1
-
成假赋值:指定一组值使A为0
-
真值表
-
重言式(永真式):A在它的各种赋值下取值均为真
-
矛盾式(永假式):A在它的各种赋值下取值均为假
-
可满足式:不是矛盾式就是可满足式
2.3等值演算与范式
- 等价(等值):在任意解释下两个命题真值相同,记做G⇔H(充分必要条件是G↔H永真公式)
-
命题公式
- 等值演算
- 简单析取式:每一个析取项或是一个命题变元,或是一个命题变元的否定(p,q,p∨q,p∨┐p∨r,┐p∨q∨┐r.)
- 简单合取式:含有一个变元及其否定的合取式.每一个合取项或为命题变元,或为命题变元的否定的合取式(p,┐r,┐p∧r,┐p∧q∧r,p∧q∧┐q)
- 析取范式:由有限个简单合取式构成的析取式称为析取范式。((┐p∧q)∨r, ┐p∨q∨r, p∨┐q∨r)
- 合取范式:由有限个简单析取式构成的合取式称为合取范式。((p∨q∨r)∧(┐q∨r), ┐p∧q∧r, p∧┐q∧r)
-
范式:析取范式与合取范式统称为范式。
(1)任何命题公式都存在范式
(2)任何命题公式都存在与之等值的析取范式和合取范式 - 极小项(极大项):设由n个命题变项构成的析取范式(合取范式)中所有的简单合取式(简单析取式)都是极小项(极大项),则称该析取范式(合取范式)为主析取范式(主合取范式)。
- 主析取范式:由有限个极小项组成的析取范式称为主析取范式(真值表为1的析取合集)
- 主合取范式:由有限个极大项组成的合取范式称为主合取范式(真值表为0的合取合集)
- 任何命题公式都存在主析取范式和主合取范式,并且是唯一的
2.4 命题逻辑的推理
- 真值表推理:无前提合取式为真,结论为假的情况,推理有效,反之无效
-
演绎证明推理
重要逻辑推理公式:
(1)前提引入
(2)结论引入
(3)置换规则
(吐血ing)