文档库

最新最全的文档下载
当前位置:文档库 > 离散数学定义与定理

离散数学定义与定理

第一章命题逻辑

表示命题的符号称为命题标识。

一个命题标识符表示确定的命题,称为命题常量。

若命题标识符只表示任意命题的位置标志,称为命题变元或命题变项。

只有当命题变元(例P)被确定的命题取代时(例雪是黑的),才有确定的真值这时称对P 进行指派。

表示原子命题时的命题变元,称为原子变元。

定义1.1 设p为一命题,复合命题p的否定称为p的否定式,记为?p,读作“非p”。若p 为t ,若?p为f ;若p 为f ,若?p 为t 。联结词“?”表示命题的否定。

否定联结词有时也记为“▔”。

定义1.2 设p和q为两个命题。复合命题“p并且q” (或“p 和q”)称为p和q的合取式,记为p∧q。当且仅当p、q同时为t 时,p∧q 为t。∧为合取联结词。

定义1.3 设p 和q是两个命题,复合命题“p 或q”称为p 与q的析取式。记为p ∨q。“∨”为析取联结词,当且仅当p、q 同时为f 时,p ∨q为f 。

注意:这儿的“或”是可兼或,是与自然语言中的“或”有区别的。

定义1.4 设p 和q是两个命题,复合命题“如果p ,则q”,称为p 和q的蕴涵式,记为p →q 。称p 为蕴涵式的前件,q 为蕴涵式的后件。当且仅当p 的真值为t,q 的真值为f 时,p →q 为f,否则p →q 的真值为t 。

定义1.5 设p 和q是两个命题,复合命题“p 当且仅当q” 称为p 和q的等价式,记为p ?q 。称?为等价联结词。当且仅当p 与q 的真值相同时,p ? q 真值为t 。

不包含任何联结词的命题称为原子命题,至少包含一个联结词的命题称为复合命题。

★命题公式是没有真假值的,仅当在公式中的所有命题变元都用真值代入时,才得到一个命题。该命题的真值依赖于各命题变元的代入真值。