离散数学及其应用（离散数学笔记1）

本文系今日头天作者“骑着猪猪的CodeMonkey”个人原创，其他媒体转载请注明出处。

离散数学笔记

逻辑与证明

命题定义：一个语句，如果或真或假（但不是既真又假），称为一个命题。

定义1.1.1

p,q命题

p and q，p∧q,合取

p or q，p∨q，析取

例：

p：1+1=3

q：一个世纪时一百年

p∧q：1+1=3 并且 一个世纪是一百年

p∨q：1+1=3 或者 一个世纪是一百年

复合命题p∧q的真值表

T为真，F为假

复合命题p∨q的真值表

T为真，F为假

P的否定，表为¬p，是命题 not p

真值表

T为真，F为假

条件命题

如p则q称为条件命题

并表为p→q

命题p称为假设（或前件）

命题q称为结论（或后件）

真值表

T为真，F为假

当A,B

必要条件 A是B的必要条件（B成立是A必须成立，但A成立是B不一定成立）B→A

充分条件 A是B的充分条件（A成立的时候B成立）A→B

当且仅当 A是B的充分必要条件 A↔B

当且仅当的真值表

T为真，F为假

设复合命题p和q是由p1...pn组成，如果不管p1...pn取什么值，p和q总是同时为真或同时为假，就说p和q逻辑上是等价的，表为

p≡q

德·摩根定律

¬（p∨q）≡¬p∧¬q

真值表

一个条件命题p→q的逆反式（或转置）是命题¬q→¬p

量词

p：n是一个奇

p 不是一个命题

真假值取决于n

p是一个命题函数

定义

令p（x）为包括变量x的语句，令D是一个集合。

如果对于D中的任意一个x，p（x）是一个命题，我们称p是一个命题函数（对于D），而称D是p的个体域（定义域）。

命题函数，本身既不为真，也不为假，而对于每一个个体x，p（x）是一个命题。

语句：所有x，p（x）可以写为Ax，p（x）(备注：Ax的A应该是上下旋转180度的A，这个符号我打不出来)

语句：存在x，p（x）可以写成Ex，p（x）（备注:Ex的E应该是左右旋转180度的A，这个符号我打不出来）

Ax，p（x，y）

x是约束变量

y是自由变量

有自由变量的语句不是命题

没有自由变量的语句可以是命题