离散数学教程-王元元-第1章 逻辑代数（上）：命题演算.pptVIP

离散数学 第1章 逻辑代数（上）：命题演算 第1章 逻辑代数（上）：命题演算 1.1.1 逻辑联结词 例1.1 （1）雪不是白的（并非雪是白的）。 （2）今晚我去商店或者去打球。 （3）我看完了书，并且做完了作业。 （4）他去了学校，又去了工厂。 （5）你织布，我耕田。（逗号也是一种连接） （6）如果我有钱，那么我替你付学费。 （7）偶数a是质数，当且仅当a=2（a是常数）。 1.1.1 逻辑联结词 否定词：“并非”，用符号 ?（或~）表示。 设 p 表示一命题，那么 ?p 表示命题 p 的否定。 p真时?p假，而p假时?p真。 1.1.1 逻辑联结词 合取词：“并且”，用符号∧表示。 设p，q表示两命题，那么p∧q表示合取p和q所得的命题，即p 和q同时为真时p∧q真，否则p∧q为假。 1.1.1 逻辑联结词 析取词：“或”，用符号∨表示。 设p，q表示两命题，那么p∨q表示p和q的析取，即当p和q有 一为真时，p∨q为真，只有当p和q均假时p∨q为假。 1.1.1 逻辑联结词 “不可兼或”，用符号 表示。 当p和q都为真时p q却为假。 1.1.1 逻辑联结词 蕴涵词：“如果…，那么…”，用符号→表示。 设p，q表示两命题，那么p→q表示命题“如果p，那么q”。 其中的p称为蕴涵前件，q称为蕴涵后件。 1.1.1 逻辑联结词 实质蕴涵：不要求p→q中的p，q有什么关系，只要p，q为命题， p→q就有意义。 例如：“如果2+2=5，那么雪是黑的”是一个有意义的命题。 实质蕴涵的数学应用： 证明对任何集合A，? ? A： 因为没有任何对象x ，x?? (x??为假)，故x?? 蕴涵x?A 为真，即? ? A真。 1.1.1 逻辑联结词 双向蕴涵词： “当且仅当”，用符号?表示。 设p，q为两命题，那么p?q表示命题“p当且仅当q”，“p与q等 价”，即当p与q同真值时p?q为真，否则为假。 1.1.2 命题公式 符号化过程的最基本步骤： 用拉丁字母 p，q，r，s 等表示具体命题， 用 f，t 表示两个特殊的常命题：常真命题和常假命题。 命题常元： p，q，r，s，f，t 统称为命题常元。 命题变元：以“真、假”或“1，0”为取值范围的变元， 为简单计，命题变元仍用 p，q，r，s 等表示。 (但不使用 f，t ) 1.1.2 命题公式 定义1.1 命题公式的归纳定义： (1) 命题常元和命题变元是命题公式，也称为原子公式或原子。 (2) 如果A，B是命题公式，那么(?A),(A∧B),(A∨B),(A→B)， (A?B)也是命题公式。 (3) 只有有限步引用条款(1)，(2)所组成的符号串是命题公式。 命题公式简称公式，常用大写字母A、B、C 等表示。 子公式：如果B是公式A中的字母相互毗连的一部分，且B自身为一 公式，则B称为公式A的子公式。 1.1.2 命题公式 约定：（1）公式最外层括号一律可省略。 （2）联结词的结合能力强弱依次为 ?，(∧，∨)，→，? 结合能力平等的联结词采用左结合约定，当运算从左向 右依次实施时，可省略其括号。 1.1.2 命题公式 定义1.2 设公式A含有命题变元p1，p2，…，pn，称p1，p2， …， pn每一取值状况为一个指派，用希腊字母?，? 等 表示，当A对取值状况 ? 为真时，称指派?弄真A，或 ?是A的弄真指派，记为?(A) = 1；反之称指派?弄假A， 或?是A的弄假指派，记为?(A) = 0。 1.1.2 命题公式 1.1.3 语句的形式化 例1.9 将下列语句形式化，并表示为命题公式 (1) 我和他既是弟兄又是同学。 p∧q