离散数学4联结词(条件)

注意/技巧：析取符号为V，大写字母Vx + y = 3不是命题前件为假时，命题恒为真运用吸收律命题符号化过程中要注意命题间的逻辑关系，认真分析命题联结词所对应的自然语言中的联结词，不能只凭字面翻译。

也就是说，在不改变原意的基础上，按照最简单的方式翻译通用的方法：真值表法VxP（x）蕴含存在xP（x）利用维恩图解题证明两个集合相等：证明这两个集合互为子集常用的证明方法：任取待证集合中的元素<,>构造相应的图论模型第一章命题逻辑命题和联结词命题的条件：表达判断的陈述句、具有确定的真假值。

选择题中的送分题原子命题也叫简单命题，与复合命题相对简单联结词的真值表要记住非（简单）合取（当且仅当P，Q都为真时，命题为真）析取（当且仅当P，Q都为假时，命题为假），P，Q可以同时成立，是可兼的或条件（→）（当且仅当P为真，Q为假时，命题为假）P是前件，Q是后件只要P，就Q等价于P→Q只有P，才Q等价于非P→非Q，也就是Q→PP→Q特殊的表达形式：P仅当Q、Q每当P双条件（↔）（当且仅当P与Q具有相同的真假值时，命题为真，与异或相反）命题公式优先级由高到低：非、合取和析取、条件和双条件括号省略条件：①不改变先后次序的括号可省去②最外层的括号可省去重言式（永真式）、矛盾式（永假式）、偶然式可满足式：包括重言式和偶然式逻辑等价和蕴含（逻辑）等价:这是两个命题公式之间的关系，写作“⇔”，要与作为联结词的↔区分开来。

如果命题公式A为重言式，那么A⇔T常见的命题等价公式：需要背过被标出的，尽量去理解。

关键是掌握公式是将哪个符号转换为了哪个符号，这对于解证明题有很大的帮助！验证两个命题公式是否等价：当命题变元较少时，用真值表法。

当命题变元较多时，用等价变换的方法，如代入规则、替换规则和传递规则定理：设A、B是命题公式，当且仅当A↔B是一个重言式时，有A和B逻辑等价。

蕴含:若A→B是一个重言式，就称作A蕴含B，记作A⇒B常见的蕴含公式的运用方法同上面的命题等价公式证明A⇒B：①肯定前件，推出后件为真②否定后件，推出前件为假当且仅当A⇒B且B⇒A时，A⇔B，也就是说，要证明两个命题公式等价，可以证明它们相互蕴含联结词的完备集新的联结词：条件否定、异或（不可兼或）、或非（析取的否定）、与非（合取的否定）任意命题公式都可由仅含{非，析取}或{非，合取}的命题公式来等价地表示全功能联结词集合极小全功能联结词集合对偶式对偶式：将仅含有联结词非、析取、合取（若不满足，需先做转换）的命题公式A中的析取变合取，合取变析取，T变F，F变T得到的命题公式A*称为A的对偶式范式析取式：否定+析取合取式：否定+合取析取范式：（合取式）析取（合取式）……析取（合取式）。

离散数学-----命题逻辑逻辑：是研究推理的科学。

公元前四世纪由希腊的哲学家亚里斯多德首创。

作为一门独立科学，十七世纪，德国的莱布尼兹(Leibniz)给逻辑学引进了符号, 又称为数理逻辑(或符号逻辑)。

逻辑可分为：1. 形式逻辑（是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。

）→数理逻辑（是用数学方法研究推理的形式结构和规律的数学学科。

它的创始人Leibniz，为了实现把推理变为演算的想法，把数学引入了形式逻辑中。

其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。

）2. 辩证逻辑（是研究反映客观世界辩证发展过程的人类思维的形态的。

）一、命题及其表示方法1、命题数理逻辑研究的中心问题是推理,而推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位。

基本概念：命题：能够判断真假的陈述句。

命题的真值：命题的判断结果。

命题的真值只取两个值:真（用T(true)或1表示）、假（用F(false)或0表示）。

真命题：判断为正确的命题，即真值为真的命题。

假命题：判断为错误的命题，即真值为假的命题。

因而又可以称命题是具有唯一真值的陈述句。

判断命题的两个步骤：1、是否为陈述句；2、是否有确定的、唯一的真值。

说明：（1）只有具有确定真值的陈述句才是命题。

一切没有判断内容的句子，无所谓是非的句子，如感叹句、祁使句、疑问句等都不是命题。

（2）因为命题只有两种真值，所以“命题逻辑”又称“二值逻辑”。

（3）“具有确定真值”是指客观上的具有，与我们是否知道它的真值是两回事。

2、命题的表示方法在书中，用大写英文字母A,B,…,P,Q或带下标的字母P1,P2,P3 ,…,或数字(1),*2+, …,等表示命题，称之为命题标识符。

命题标识符又有命题常量、命题变元和原子变元之分。

命题常量：表示确定命题的命题标识符。

命题变元：命题标识符如仅是表示任意命题的位置标志，就称为命题变元。

离散数学复习要点第一章命题逻辑一、典型考查点1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。

其它疑问句、祈使句、感叹句、悖论等皆不是。

详见教材P12、联结词运算定律┐∧∨→记住特殊的：1∧1⇔1，0∨0⇔0，1→0⇔0，11⇔1，00⇔1详见P53、命题符号化步骤：A划分原子命题，找准联结词。

特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。

B设出原子命题写出符号化公式。

详见P54、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。

详见P95、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。

②对每个指派，以二进制数从小到大或从大到小顺序列出。

③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。

详见P8。

6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P157、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A⇔B的充要条件是A⇒B且B⇒A。

主要等价式：(1)双否定：⎤⎤A⇔A。

(2)交换律：A∧B⇔B∧A，A∨B⇔B∨A，A↔B⇔B↔A。

3)结合律：(A∧B)∧C⇔A∧(B∧C)，(A∨B)∨C⇔A∨(B∨C)，(A↔B)↔C⇔A↔(B↔C)。

(4) 分配律：A∧(B∨C)⇔(A∧B)∨(A∧C)，A∨(B∧C)⇔(A∨B)∧(A∨C)。

(5) 德·摩根律：⎤(A∧B)⎤⇔A∨⎤B，⎤(A∨B)⎤⇔A∧⎤B。

(6) 等幂律：A∧A⇔A，A∨A⇔A。

(7) 同一律：A∧T⇔A，A∨F⇔A。

(8) 零律：A∧F⇔F，A∨T⇔T。

(9) 吸收律：A∧(A∨B)⇔A，A ∨(A∧B)⇔A。

(10) 互补律：A∧⎤A⇔F，(矛盾律)，A∨⎤A⇔T。

离散数学第一章1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。

1.1.2 命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。

A1:我是一名大学生.[10]：我是一名大学生。

R：我是一名大学生。

1.2命题联结词1.2.1 否定联结词﹁PP P0 11 01.2.2 合取联结词∧P∧P Q Q0 0 00 1 01 0 01 1 11.2.3 析取联结词∨P∨P Q Q0 0 00 1 11 0 11 1 11.2.4 条件联结词→P Q Q0 0 10 1 11 0 01 1 11.2.5 双条件联结词?P?P Q Q0 0 10 1 01 0 01 1 11.2.6 与非联结词↑P↑P Q Q0 0 10 1 11 0 11 1 0性质：（1）P↑P?﹁（P∧P）?﹁P；（2）（P↑Q）↑（P↑Q）?﹁（P↑Q）? P∧Q；（3）（P↑P）↑（Q↑Q）?﹁P↑﹁Q? P∨Q。

1.2.7 或非联结词↓P↓P Q Q0 0 10 1 01 0 0性质：（1）P↓P?﹁（P∨Q）?﹁P；（2）（P↓Q）↓（P↓Q）?﹁（P↓Q）?P∨Q；（3）（P↓P）↓（Q↓Q）?﹁P↓﹁Q?﹁（﹁P∨﹁Q）?P∧Q。

1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、P?Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。

例如，下面的符号串都是公式：（（（（﹁P）∧Q）→R）∨S）（（P→﹁Q）?（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）?（∧Q））（∧Q）1.3.2 命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。

自考离散数学命题演算笔记本章的重点是命题概念及其表示、命题公式化简、主范式及其互化、P规则、T规则以及CP规则。

难点是推理理论及应用。

一、命题概念(领会)学习本章首先要深刻理解命题的概念。

理解原子命题与复合命题的关系，在了解复合命题的基础上，理解联结词的定义。

命题：具有唯一真值的陈述句称为命题，又简称语句。

注意，这里有两个条件，首先它是一个陈述句，其次，它具有唯一的一个真值。

真值：就是语句为真或假的性质。

一个语句的真值可以为真也可以为假。

真值不是说该语句的值必为真。

任一命题必有其真值，也称这个命题的值。

既然是命题了，那它必有一个确定的真值，不管这个真值为真还是为假。

当一个陈述句能够分辩其值的真假时(也就是说，总可以肯定是其中的某一个)，它就是命题，即使我们不知道它是真还是假。

另外要理解命题常量、命题变元及指派的含义。

复合命题就是一些原子命题经过一些联结词复合而成的命题。

常用的联结词有：(1)否定、(2)合取、(3)析取、(4)条件、(5)双条件复合命题与联系词是密切相关的，不包含联结词的命题就是原子命题，至少包含一个联结词的命题才是复合命题。

复合命题的真值只取决于构成它们的各原子命题的真值，而与它们的内容含义无关。

对联结词所联结的两原子命题之间有无关系无关。

(这一条很重要，因为一个命题用自然语言表达时，我们往往会受到自然逻辑的影响，比如"我如果不上班，那么天下雨"这种命题，在自然的逻辑里，是不成立的，一个人不上班怎么会导致天下雨呢? 但是在这里，这个复合命题的值实际上是由两个原子命题的真值决定的，与它的含义无关，这个复合命题是|P->Q ,前一个原子命题的真值为假，后一命题值为真，根据条件的定义，这个复合命题值为真)∧、∨、←→具有对称性，|、→无对称性，(教材提示，也可用iff表示双向箭头←→，由于字符集的限制，本网页在表示否定关联词时用"|"，请在书写时注意规范写法。

离散数学联结词
嘿，朋友们！今天咱来聊聊离散数学里超有意思的联结词呀！
你说这联结词像不像我们生活中的那些关系纽带呀？就好比与朋友之间的友谊，把大家联结在一起。

离散数学里的联结词呢，就起着类似的作用，把各种命题巧妙地联结起来，形成更复杂但也更有趣的逻辑表达。

咱先说说“且”这个联结词吧。

这就好像你去超市买东西，你既想要巧克力，又想要薯片，这两个条件都得满足才行，这就是“且”的作用呀！想象一下，你说“我今天既完成了作业，又看了喜欢的电影”，是不是只有这两件事都做到了，这句话才成立呢？这就是“且”在帮忙呀！
还有“或”呢，它就像是给了你更多的选择。

比如说你周末可以选择去爬山，或者去逛街，只要其中一个实现了，那“或”的条件就满足啦。

它可没那么死板，给了你很大的灵活性呢。

“非”就更有意思啦！就像你原本觉得一件事是对的，“非”一下，嘿，就变成错的啦！这多神奇呀。

比如你说“今天天气很好”，那“非今天天气很好”不就是说今天天气不好嘛。

这些联结词呀，就像生活中的调味剂，让逻辑变得丰富多彩。

它们能帮我们把复杂的事情梳理清楚，搞明白其中的关系。

你看，要是没有这些联结词，那逻辑表达得多无趣呀！就好像一道菜没有了调料，那还有啥滋味呢？它们让我们能更准确地表达自己的想法，也能更好地理解别人的意思。

在学习离散数学的时候，可别小瞧了这些联结词哦！它们虽然看起来简单，但是用处可大着呢！就像一颗颗小螺丝钉，看似不起眼，却是整个机器运转不可或缺的一部分。

所以呀，大家要好好理解和掌握这些联结词呀，它们会给你带来意想不到的收获呢！这可不是我在瞎忽悠，你自己去试试看就知道啦！。

第1章命题逻辑逻辑是研究人的思维的科学,包括辩证逻辑和形式逻辑。

辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。

形式逻辑是研究思维的形式结构和规律的科学,它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。

数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。

所谓的数学方法也就是用一套有严格定义的符号，即建立一套形式语言来研究.因此数理逻辑也称为符号逻辑。

数理逻辑的基础部分是命题逻辑和谓词逻辑。

本章主要讲述命题逻辑，谓词逻辑将在第2章进行讨论。

1.1命题及其表示1。

1。

1命题的基本概念数理逻辑研究的中心问题是推理（Inference),而推理就必然包含前提和结论，前提和结论都是表达判断的陈述句，因而表达判断的陈述句就成为推理的基本要素。

在数理逻辑中，将能够判断真假的陈述句称为命题.因此命题就成为推理的基本单位。

在命题逻辑中，对命题的组成部分不再进一步细分。

定义1.1.1 能够判断真假的陈述句称为命题(Proposition）。

命题的判断结果称为命题的真值，常用 T （True)（或1）表示真，F（False）（或0）表示假.真值为真的命题称为真命题，真值为假的命题称为假命题。

从上述的定义可知,判定一个句子是否为命题要分为两步:一是判定是否为陈述句，二是能否判定真假，二者缺一不可。

例1。

1.1判断下列句子是否为命题（1）北京是中国的首都。

（2）请勿吸烟!（3）雪是黑的。

（4）明天开会吗？（5）x+y=5.（6）我正在说谎。

（7）9+5≤12.（8）1+101=110。

（9）今天天气多好啊！（10）别的星球上有生物。

解在上述的十个句子中，（2）、（9）为祈使句，(4）为疑问句，（5）、(6）虽然是陈述句，但(5)没有确定的真值，其真假随x、y取值的不同而有改变,（6）是悖论(Paradox）（即由真能推出假，由假也能推出真），因而(2）、（4)、(5)、（6）、(9)均不是命题.（1）、（3）、（7)、（8）、(10）都是命题，其中（10）虽然现在无法判断真假，但随着科技的进步是可以判定真假的。

离散数学笔记第一章命题逻辑合取析取定义 1. 1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4条件联结词，表示“如果……那么……”形式的语句定义 1. 1.5双条件联结词，表示“当且仅当”形式的语句定义 1.2.1合式公式(1)单个命题变元、命题常元为合式公式，称为原子公式。

(2)若某个字符串A 是合式公式，则⌝A、(A)也是合式公式。

(3)若A、B 是合式公式，则A ∧B、A∨B、A→B、A↔B 是合式公式。

(4)有限次使用(2)~(3)形成的字符串均为合式公式。

1.3等值式1.4析取范式与合取范式将一个普通公式转换为范式的基本步骤1.6推理定义 1.6.1 设 A 与 C 是两个命题公式， 若 A → C 为永真式、 重言式，则称 C 是 A 的有 效结论，或称 A 可以逻辑推出 C ，记为 A => C 。

（用等值演算或真值表）第二章 谓词逻辑2.1、基本概念∀：全称量词 ∃：存在量词一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如"∀x(H(x)→B(x))，即量词的后面为条件式，带“存在量词”的谓词公式形如∃x(H(x)∨WL(x))，即量词的后面为合取式 例题R(x)表示对象 x 是兔子，T(x)表示对象 x 是乌龟， H(x,y)表示 x 比 y 跑得快，L(x,y)表示x 与 y 一样快，则兔子比乌龟跑得快表示为： ∀x ∀y(R(x)∧T(y)→H(x,y))有的兔子比所有的乌龟跑得快表示为：∃x ∀y(R(x)∧T(y)→H(x,y))2.2、谓词公式及其解释定义 2.2.1、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22y x 的 f(x,y))、 谓词常元(如表示人类的 H(x))。

定义 2.2.2、逻辑符号：个体变元、量词(∀∃)、联结词(﹁∨∧→↔)、逗号、括号。

1.1 命题1-1-1 命题命题是一个能表达判断并具有确定真值的陈述句。

1-1-2 真值作为命题的陈述句所表达的判断结果称为命题的真值。

真值只有真和假两种，通常记为T和F。

真值为真的命题称为真命题，真值为假的命题称为假命题。

真命题表达的判断正确，假命题表达的判断错误。

任何命题的真值都是唯一的。

1-1-3 命题变项用命题标识符（大写字母）来表示任意命题时，该命题标识符称为命题变项。

1-1-4 简单命题无法继续分解的简单陈述句称为简单命题或原子命题。

(不包含任何与、或、非一类联结词的命题)1-1-5 复合命题由一个或几个简单命题通过联结词复合所构成的新的命题，称为复合命题，也称分子命题。

1.2 命题联结词及真值表1-2-1 命题联结词命题联结词可将命题联结起来构成复杂的命题，是由已有命题定义新命题的基本方法。

命题联结词又可分为一元命题联结词、二元命题联结词和多元命题联结词。

常用的命题联结词包括否定词、合取词、析取词、蕴涵词和双条件词。

其它联结词还包括异或（不可兼或）、与非和或非等。

1-2-2 否定词否定词是一元命题联结词。

设P为一命题，P的否定是一个新的命题，记作P，读作非P。

若P为T，P为T；若P为F，P为T。

1-2-3 合取词合取词是二元命题联结词。

两个命题P和Q的合取构成一个新的命题，记作P∧Q。

读作P、Q的合取（或读作P与Q，P且Q）。

当且仅当P、Q 同时为T时，P∧Q为T。

否则，P∧Q的真值为F。

1-2-4 析取词析取词是二元命题联结词。

两个命题P和Q的析取构成一个新的命题，记作P∨Q。

读作P、Q的析取（也读作P或Q）。

当且仅当P、Q同时为F 时，P∨Q的真值为F。

否则，P∨Q的真值为T。

1-2-5 蕴涵词蕴涵词是二元命题联结词。

两个命题P和Q用蕴涵词“→”联结起来，构成一个新的命题，记作P→Q。

读作如果P则Q，或读作P蕴涵Q。

当且仅当P 的真值为T，Q的真值为F时，P→Q的真值为F，否则P∨Q的真值为T。