计算机科学M O O C课程群
离散数学基础
本单元内容比较多，视频分割成三个部分：范式的概念、主范式及其应用和主范式的编码
PART 1 范式的概念
?范式的一些基本定义
?文字：原子命题及其否定式统称为文字（形）。
?例：对变量表 {p, q}，p, ?p, q, ?q 都是文字。
?例：把 F 称为空文字，记作 NIL。
?基本积：由有限个文字的合取构成。(简单合取式)
?例：对变量表 {p, q, r}，基本积有 p, ?p, q∧?p, ?q∧?p∧r 等等。
?基本和：由有限个文字的析取构成。 (简单析取式)
?例：对变量表 {p, q, r}，基本和有 p, ?p, q∨?p, ?q∨?p∨r 等等。
?定理6
?一个基本和是永真的当且仅当其中含有某个原子的互补对；
?由排中律和零律：α∨p∨?p ? α∨1 ? 1
?一个基本积是矛盾的当且仅当其中含有某个原子的互补对。
?由矛盾律和零律： α∧p∧?p ? α∧0 ? 0
?定义：析取范式
?一个命题公式称为是一个析取范式当且仅当其具有形式 A1∨A2∨ …∨A n
(1≤n<∞)，其中 A i 是基本积 (1≤i≤n)。
?例1：?p ∨ (q∧?r) ∨ s， (n=3)
?例2：?p， (n=1)
?例3：?p ∧ q ∧ ?r， (n=1)
?例4：?p ∨ q ∨ ?r， (n=3)
?定义：合取范式
?一个命题公式称为是一个合取范式当且仅当其具有形式 A1∧A2∧…∧A n
(1≤n<∞)，其中 A i 是基本和 (1≤i≤n)。
?例1：(?p∨q∨s)∧(?p∨?r∨s)， (n=2)
?例2：?p， (n=1)
?例3：?p ∧ q ∧ ?r， (n=3)
?例4：?p ∨ q ∨ ?r， (n=1)
?定理7
(1) 一个合取范式是永真的当且仅当其中含有的基本和都是永真的；
(2) 一个析取范式是矛盾的当且仅当其中含有的基本积都是矛盾的。
?证明：留作思考。
?定理8（范式存在基本定理）
?任一命题公式都有与之等值的析取范式和合取范式。
?构造性证明
?以求合取范式为例，重复施行如下的等值变形：
①联结词化归：应用联结词消去等值式，消去→ 和 ? ；
②否定词深入：应用德‐摩根律，使否定词直接作用于原子命题变量；
③重复利用 ∧ 和 ∨ 之间的分配律求得析取范式或合取范式。
?例： (p∧(q→r))→s
? ?(p∧(?q∨r))∨s 联结词化归
? ?p∨?(?q∨r)∨s 德‐摩根律
? ?p∨(q∧?r)∨s 德‐摩根律
? (?p∨q∨s)∧(?p∨?r∨s) 分配律
? (?p∨q∨s)∧(?p∨?r∨s)∧(?p∨?r∨s) 幂等律
?讨论：一个命题公式的合取（析取）范式不是唯一的。
PART 2 主范式及其应用
?定义：极小项
?设命题公式 A(p1, p2, …, p n)，又设 A k∈{p k, ?p k}, k =1..n, 则称 A1∧A2∧…∧A n 为公式 A 的一个极小项。
?极小项也称布尔积。
(1) 关于 A(p1, p2, …, p n) 或原子变量集合 {p1, p2, …, p n} 的极小项有 2n 个。
?例：对 {p, q}，可以构造 22 =4 个极小项 ?p∧?q，?p∧q，p∧?q，p∧q 。
(2) 对变量表的任一解释有且仅有一个极小项的值为1，其余的值为0，称该极
小项为该解释所对应的极小项。
?例：对 {p, q} 的一个解释 t(p)=1, t(q)=0，有且仅有 p∧?q=1, 对其他的三个
极小项，每个极小项中至少有一个文字的值是0，所以这三个极小项的值都
是0 。
(3) 任何一对不同极小项的合取为0。所有极小项的析取为1。
?由(2), 对变量表的任一解释，任何一对极小项中最多有一个极小项取值为
1，另外的取值为0，所以合取为0；所有极小项中恰有一个极小项取值为1，
所以析取为1。
?定义：极大项
?设命题公式 A(p1, p2, …, p n)，又设 A k∈{p k, ?p k}, k =1..n, 则称 A1∨A2∨…∨A n 为公式 A 的一个极大项。
?极大项也称布尔和。
(1) 关于 A(p1, p2, …, p n) 或原子变量集合 {p1, p2, …, p n} 的极大项有 2n 个。
?例：对 {p, q}，可以构造极大项 ?p∨?q，?p∨q，p∨?q，p∨q 。
(2) 对任一解释有且仅有一个极大项的值为0，其余的值为1，称该极大项为该解
释所对应的极大项。
(3) 任何一对不同极大项的析取为1。所有极大项的合取为0。
?定义：主析取范式
?一个命题公式 B(p1, p2, …, p n) 称为是一个主析取范式(形的)，当且仅当其具有形式
B1∨B2∨…∨B m (1≤m≤ 2n)，
其中 B i (1≤i≤m) 为公式 B 的一个极小项，且 B i≠B j (对i≠j)。
?定义：主合取范式
?一个命题公式 B(p1, p2, …, p n) 称为是一个主合取范式(形的)，当且仅当其具有形式
B1∧B2 ∧ …∧B m (1≤m≤ 2n)，
其中 B i (1≤i≤m) 为公式 B 的一个极大项，且 B i≠B j (对i≠j)。
?定理9（主范式存在和唯一性定理）
?任一命题公式都有与之等值的主析取范式和主合取范式。考虑到在交换律下等值的公式形态的同一性，主范式的形态是唯一的。
?证明：留作思考。
?例：利用真值表求 p→q 的主析取范式。
p q p→q
000
011
101
111
?在命题公式 A 的真值表中，令 A 的取值为1的所有解释所对应的极小项的析
取，构成其主析取范式。因此：p→q = (?p∧q)∨(p∧?q)∨(p∧q)
?上述过程的正确性证明：
?设该析取式为 B，显然 B 为主析取范式的形态。
?当 A=1 时，其解释对应于一个取值为1的极小项，且该极小项为构成 B 的
极小项之一，故此时B=1；
?当 A=0 时，其解释所对应的极小项不在构成 B 的极小项中，故此时B中所
有极小项取值0，即B=0。
?综上可得 B?A，即 B 是 A 的主析取范式。
?范式的应用
?例1： 一个双稳态（高、低电平）控制线路，有 A，B，C 三路输入和分别对应的 F A，F B，F C 三路输出。要求：输入均为低电平时，没有高电平输出；至多有一路高电平输出；有高电平输入时，只有按 A，B，C 的次序检测到的第一个高电平输入才有效，其对应的输出获得高电平，此时其他输出被抑制。要求：(1) 写出分别描述上述三路输出的逻辑表达式；(2) 用与非门搭建实现上述控制要求的逻辑电路。
A B C F A F B F C
000000
001001
010010
011010
100100
101100
110100
111100
?由真值表容易写出 FA、FB 和 FC 的主析取范式。
FA = (A∧?B∧?C)∨(A∧?B∧C)∨(A∧B∧?C)∨(A∧B∧C)；
FB = (?A∧B∧?C)∨(?A∧B∧C)
FC = ?A∧?B∧C
?经过化简后的表达式为
FA = A = (A↑A)↑(A↑A)；
FB = ?A∧B = (A↑A)∧B
= ((A↑A)↑B)↑((A↑A)↑B)；
FC = ?A∧?B∧C = (A↑A)∧(B↑B)∧C
= ……
?范式的应用
?例2：一个会议室有4个门，1盏灯，每个门旁边各有一个双稳态开关。要求：任何一个开关状态的改变都能导致灯的亮、灭状态的改变。写出实现上述控制
要求的逻辑表达式。
?解：设初始灯是开路的，而且所有开关处于0状态。则只要令灯在有奇数个开关处于1状态时接通，即满足题目的要求。真值表如下页，A、B、C、D 分别表示4个开关的状态，一共有 24=16 个逻辑解释。由真值表可以写出 L 的主析取范式。请你自行完成。
A B C D L
00000
00011
00101
00110
01001
01010
01100
01111
A B C D L
10001
10010
10100
10111
11000
11011
11101
11110
?等值演算构造主析取范式
（1）构造析取范式并化简合并。
（2）在每一个基本积中利用同一律填满所有的原子命题文字形式，利用分配律构造布尔积（称为基本积的扩展）。
（3）重复第2步直到所有基本积都扩展成布尔积。
（4）合并同类布尔积，经适当排列得到最后结果。
?例：第2步对于 A(p, q, r) 扩展基本积
? p∧q ? p∧q∧(r∨?r) ? (p∧q∧r)∨(p∧q∧?r)
? p ? p∧(q∨?q)∧(r∨?r)
? ? ((p∧q)∨(p∧?q))∧(r∨?r)
? ? ((p∧q)∧(r∨?r))∨((p∧?q)∧(r∨?r))
? ? ((p∧q∧r)∨(p∧q∧?r))∨((p∧?q∧r)∨(p∧?q∧?r))
? ? (p∧?q∧?r)∨(p∧?q∧r)∨(p∧q∧?r)∨(p∧q∧r)
PART 3 主范式的编码
?定义：极小项的成真编码
?对关于 n 个原子的极小项 B i = A1∧A2∧…∧A n (1≤i≤ 2n)， A k∈{p k, ?p k}, k =1..n，令 B i 为真的原子的真值序列 (v1v2…v n) 是唯一的，称之为 B i 的成真编码。以二进制数1表示真值T，0表示真值F，则可构造 B i 的成真 n 位二进制编码 C，记为 m C。
?例：命题公式 A(p, q) 有4个极小项
?p∧?q 对应 m00 或 m0
当 t(p)=0, t(q)=0 时 ?p∧?q=1
?p∧q 对应 m01 或 m1
当 t(p)=0, t(q)=1 时 ?p∧q=1
p∧?q 对应 m10 或 m2
当 t(p)=1, t(q)=0 时 p∧?q=1
p∧q 对应 m11 或 m3
当 t(p)=1, t(q)=1 时 p∧q=1
?定义：极大项的成假编码
?对关于 n 个原子的极大项 B i = A1∨A2∨…∨A n (1≤i≤ 2n)， A k∈{p k, ?p k}, k =1..n，令 B i 为假的原子的真值序列 (v1v2…v n) 是唯一的，称之为 B i 的成假编码。以二进制数1表示真值T，0表示真值F，则可构造 B i 的成假 n 位二进制编码 C，记为 M C。
?例：命题公式 A(p, q) 有4个极大项
?p∨?q 对应 M11 或 M3
当 t(p)=1, t(q)=1 时 ?p∨?q=0
?p∨q 对应 M10 或 M2
当 t(p)=1, t(q)=0 时 ?p∨q=0
p∨?q 对应 M01 或 M1
当 t(p)=0, t(q)=1 时 p∨?q=0
p∨q 对应 M00 或 M0
当 t(p)=0, t(q)=0 时 p∨q=0
?定理10：
?m i 和 M i 如上所述，则 ?m i =M i，?M i =m i 。
?证明：设 m i = A1∧A2∧…∧A n，A k∈{p k, ?p k}, k =1..n，则有令 m i=1 的真值序列 i =(v1v2…v n)，在 t(p k)=v k (1≤k≤n)的赋值下，
A1∧A2∧…∧A n?1，故 A k?1 或 ?A k?0 (1≤k≤n)
构造公式 ?m i = ?(A1∧A2∧…∧A n)? ?A1∨?A2∨…∨?A n ? 0
上述公式化去可能出现的双重否定后，是一个极大项，且在真值序列 i
=(v1v2…v n)，t(p k)=v k (1≤k≤n) 的赋值下成假，依定义记为 M i ，即 ?m i=M i。 易证 ?M i =m i。
?定理11：
?命题公式 A(p1,p2,…p n) 若有主析取范式
A = m i1∨m i2 ∨…∨m i k , 1≤k ≤ 2n
i s< i t 当 1≤s 则有主合取范式 A = M j1∧M j2 ∧…∧M j L , L= 2n ?k j s< j t 当 1≤s ?证明： ?公式 A 的主析取范式 A = m i1∨m i2 ∨…∨m i k 可由A 的真值表写出，则由 ?A 的真值表可写出 ?A 的主析取范式：?A = m j1∨m j2∨…∨m j L , L= 2n ?k, j s 1≤s 故 A = ?m j1∧?m j2∧…∧?m j L ? 由定理10有 ?m j s = M j s ，故 A = M j1∧M j2∧…∧M j L ? ?例： A = (P→ ?Q) ?R 的真值表 P Q R?Q P→?Q(P→ ?Q) ?R 000110 001111 010010 011011 100110 101111 110001 111000 ?A 的主析取范式的极小项由第2,4,6,8行写出；A 的主合取范式的极大项由余下的第1,3,5,7行写出。观察主析取范式和主合取范式的下标编码的互补性 ?主范式的应用： ?判断不同公式的等值性； ?判断公式的重言性、可满足性和矛盾性； ?给出公式的成真赋值和成假赋值； ?。。。。 下一单元内容提示 ?命题逻辑的推理演算‐推理的形式结构 离散数学自学笔记命题公式及其真值表 我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元（proposition constant）。深入的讨论还需要引入命题变元（proposition variable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。相同符号的不同意义，容易从上下文来区别，在未指出符号所表示的具体命题时，它们常被看作变元。 命题常元、变元及联结词是形式描述命题及其推理的基本语言成分，用它们可以形式地描述更为复杂的命题。下面我们引入高一级的语言成分——命题公式。 定义1.1 以下三条款规定了命题公式（proposition formula）的意义： （1）命题常元和命题变元是命题公式，也称为原子公式或原子。 （2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（A？B）也是命题公式。 （3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。 命题公式简称公式，常用大写拉丁字母A，B，C等表示。公式的上述定义方式称为归纳定义，第四章将对此定义方式进行讨论。 例1.8 （┐（p→（q∧r）））是命题公式，但（qp），p→r，p1∨p2∨…均非公式。 为使公式的表示更为简练，我们作如下约定： （1）公式最外层括号一律可省略。 （2）联结词的结合能力强弱依次为┐，（∧，∨），→，？，（∧，∨）表示∧与∨平等。 （3）结合能力平等的联结词在没有括号表示其结合状况时，采用左结合约定。湖南省自考网：https://www.doczj.com/doc/f914521258.html,/整理 例如，┐p→q∨（r∧q∨s）所表示的公式是（（┐p）→（q∨（（r∧q）∨s））） 设A是命题公式，A1是A 的一部分，且A1也是公式，则A1称为公式A的子公式。 逻辑命题与推理 必然性推理（演绎推理）：对当关系推理、三段论、复合命题推理、关系推理和模态推理 可能性推理：归纳推理（枚举归纳、科学归纳）、类比推理 命题 直言命题的种类：（AEIOae） ⑴全称肯定命题：所有S是P（SAP） ⑵全称否定命题：所有S不是P（SEP） ⑶特称肯定命题：有的S是P（SIP） ⑷特称否定命题：有的S不是P（SOP） ⑸单称肯定命题：某个S是P（SaP） ⑹单称否定命题：某个S不是P（SeP） 直言命题间的真假对当关系： 矛盾关系、（上）反对关系、（下）反对关系、从属关系 矛盾关系：具有矛盾关系的两个命题之间不能同真同假。主要有三组： SAP与SOP之间。“所有同学考试都及格了”与“有些同学考试不及格” SEP与SIP之间。“所有同学考试不及格”与“有些同学考试及格” SaP与SeP之间。“张三考试及格”与“张三考试不及格” 上反对关系：具有上反对关系的两个命题不能同真（必有一假），但是可以同假。即要么一个是假的，要么都是假的。存在于SAP与SEP、SAP与SeP、SEP与SaP之间。 下反对关系：具有下反对关系的两个命题不能同假（必有一真），但是可以同真。即要么一个是真的，要么两个都是真的。存在于SIP与SOP、SeP与SIP、SaP与SOP之间。 从属关系（可推出关系）：存在于SAP与SIP、SEP与SOP、SAP与SaP、SEP与SeP、SaP与SIP、SeP与SOP 六种直言命题之间存在的对当关系可以用一个六角图形来表示，“逻辑方阵图” SAP SEP SaP SeP SIP SOP 直言命题的真假包含关系 全同关系、真包含于关系、真包含关系、交叉关系、全异关系 复合命题：负命题、联言命题、选言命题、假言命题 负命题的一般公式：并非P 联言命题公式：p并且q “并且、…和…、既…又…、不但…而且、虽然…但是…” 选言命题：相容的选言命题、不相容的选言命题 相容的选言命题公式：p或者q“或、或者…或者…、也许…也许…、可能…可能…” 【一个相容的选言命题是真的，只有一个选言支是真的即可。只有当全部选言支都假时，相容的选言命题才是假的】不相容选言命题公式：要么p要么q “要么…要么…、不是…就是…、或者…或者…二者必居其一、或者…或者…二者不可兼得” 【一个不相容的选言命题是真的，有且只有一个选言支是真的。当选言支全真或全假时，此命题为假】 假言命题：充分条件假言命题、必要条件假言命题、充要条件假言命题 充分条件假言命题公式：如果p，那么q“如果…就…、有…就有…、倘若…就…、哪里有…哪里有…、一旦…就…、假若…、只要…就…” 【有前件必然有后件。如果有前件却没有后件，这个充分条件假言命题就是假的。因此，对于一个充分条件的假言命题来说，只有当其前件真而后件假时，命题才假。】 必要条件假言命题公式：只有p，才q “没有…就没有…、不…不…、除非…不…、除非…才…” 【没有前件必然没有后件。如果没有前件也有后件，这个必要假言命题为假。对于一个必要条件的假言命题来说，只有当其前件假而后件真时，命题才假。】 充要条件假言命题公式：当且仅当p，才q 【有前件必然有后件，没有前件必然没有后件。充要条件假言命题在前件与后件等值即前件真并且后件真，或者前件假并且后件假时，命题为真，在前件与后件不等值即前真后假，或前假后真时，命题为假】 充分条件与必要条件之间可以相互转化： 形式逻辑公式速查表 在刚刚结束的2012年一月联考中，“形式逻辑”数量为23道，占逻辑总题量的近80%。在这一背景下，能否熟练的运用形式逻辑的公式解题，成为不同考生在综合能力考试中的重大差异。 假设2013年形式逻辑不少于15道题，那么，如果能熟练使用公式计算，逻辑部分将有可能实现“35分钟以内、54分以上”的目标。成为投入产出比和临场得分效率最高的科目。 形式逻辑所涉及的考点及分值预测如下： 直言命题2分、三段论4分、模态命题0分、概念2~4分、关系命题0分、联言选言命题2分、假言命题16~22分（考本类题目中会大量涉及联言选言命题）、分析推理2分、其他零散（如典型逻辑谬误等）2分。 形式逻辑的训练需要按类型集中训练，方能对各类题型形成快速反应的能力。为此，我们精选了2000~2012年的形式逻辑真题，剔除掉和近年真题风格、难度、命题方式不符的题目，供大家使用。 形式逻辑公式速查表 直言命题全称肯定命题（SAP，以下简称A）：所有S都是P；全称否定命题（SEP，以下简称E）：所有S都不是P；特称肯定命题（SIP，以下简称I）：有些S是P； 特称否定命题（SOP，以下简称O）：有些S不是P；单称肯定命题（记作a）：张三是P； 单称否定命题（记作e）：张三不是P。 直言命题的关系及规则矛盾关系（A和O、E和I、a和e）：既不能同真，也不能同假，必有一真，必有一假； 反对关系（A和E）：不能同真，可以同假； 下反对关系（I和O）：可以同真，不能同假； 从属关系（A-a-I、E-e-O）：全称真，则单称真，则特称真；特称假，则单称假，则全称假。 三段论常用规则两特称不能得出结论； 两否定不能得出结论； 前提有否定，结论必为否定，反之亦然；前提有特称，结论必为特称，反之未必。 模态命题的 等价命题 不一定←→可能非，不可能←→必然非 2 命题公式,真值表 (1) 数理逻辑是通过引入表意符号研究人类思维中的推理过程及推理正确与否的数学分支. 数学------??? 符号运算 推理---思维过程:前提 结论 命题逻辑---研究由命题为基本单位构成的前提和结论之间的可推导关系.(逻辑演算) 即将推理(不涉及内函)形式化. 例1 (a) 4是偶数. 张林学习优秀. 太阳系以外的星球上有生物. (b) 这朵花真美丽! 现在开会吗? (c) 3 5.x +> 我正在说慌. 特征分析(a) 陈述句,非真即假. (b) 感叹句,疑问句. (c) 悖论. 定义1 能辩真假的陈述句,称为命题,用,,,P Q Z 表示.其判断结果称为命题的真值. 成真的命题称为真命题,其真值为真,记为,T 或为1.成假的命题称假命题,其真值为假,记为,F 或为0. 例2 (1) 2008年奥运会在北京举行. (2) 22 5.?= (3) 计算机程序的发明者是诗人拜伦. 用符号表是上述命题,并求真值. 解 (1) :P 2008年奥运会在北京举行. .T (2) :Q 22 5.?= .F (3) :R 计算机程序的发明者是诗人拜伦. .F (2) 3, 35,+ 3(4 1).+- 例3 (1) 今天没有数学考试. (2) 下午,我写信或做练习. (3) 王芳不但用功,而且成绩优秀. (4) 如果太阳从西边出来了,那么地球停止转动. (5) 2是素数,当且仅当三角形有三条边. 特征分析(a)存在自然语言中的虚词. (b)语句可以分解,细化. 定义2 称下列符号为逻辑联结词 否定 ? 非 P ? 析取 ∨ 或者 P Q ∨ 合取 ∧ 且 P Q ∧ 蕴涵 → 若----,则----- P Q → 等价 ? 当且仅当 P Q ? 逻辑联结词真值的规定 例4 将下列命题符号化. (1) 小李聪明,但不用功. ()P Q ∧? (2) 单位派小王或小苏出差. P Q ∨ (3) 如果椅子是紫色的,且是园的,那么地是平的. ()P Q R ∧→ (4) n 是偶数当且仅当它能被2整除. P Q ? 注 1 逻辑联结词:运算符.顺序 ,,,,.?∧∨→? 2 自然语言中 虽然---,但是----; 不但---,而且----; ∧ 只有----,才----; 除非----,才-----; → 3 ∨ 可兼或(相容) ∨ 不可兼或(排斥) 小王是山东人或是河北人. ()()P Q P Q P Q ∨?∧?∨?∧ 4 ,P Q -----------------------简单命题 形式逻辑的基本规律的概述形式逻辑的基本规律是各种思想逻辑形式的普遍规律，它包括同一律、矛盾律、排中律和充足理由律。 我们这里所说的基本规律是相对于特殊规律而言的。我们以前曾经讲过许多逻辑规则，例如定义规则、划分规则、三段论规则等等。这些逻辑规则相对于同一律、矛盾律、排中律和充足理由律这四条逻辑规律来说，都带有特殊性。它们只在特定的思想逻辑形式里有效。相对于这些逻辑规律来说，逻辑的基本规律则带有普遍性，是对这些规则的进一步概括。因而它们普遍地适用于各种思想形式，正是在这个意义上，形式逻辑把它们称为基本规律。 形式逻辑的基本规律有以下几个特点： 一、普遍有效性。逻辑规律是思维活动中的基本准则，对一切思维过程都有制约作用。任何正确的思想，无论是概念、命题还是推理，都必须具有确定性。有确定的内容，确定地反映客观对象，这是逻辑思维的基本特征。同一律、矛盾律和排中律正是从不同角度反映这一特征。 同一律提出任何思想与自身同一，矛盾律要求思想不自相矛盾，排中律则排除两个矛盾思想的中间可能性。遵守这三条规律是思想具有确定性的必要条件，违反了它们的要求，则势必犯逻辑错误。这是从逻辑规律在思维中的作用说的。 再者，充足理由律也是逻辑思维的必要条件，它是思想具有论证性的必要条件。违反了它的要求，同样犯逻辑错误。 二、客观必然性。逻辑规律不是客观事物的规律，而是思维自身的规律，因此有其主观性。但逻辑规律不是同客观事物毫无关系的纯思维的产物，它有其自身的客观基础，即一切客观事物在其存在时必须具有的规律。因为一切事物在其存在时只能是该事物而非他物；一切事物在其存在时不能是虚无；一切事物要么存在，要么不存在，二者必居其一；一切事物的存在必有其存在的理由。 三、逻辑思维具有确定性和论证性的特征。其中，思维的确定性又具体表现为思维的同一性、一贯性和明确性。同一律、矛盾律、排中律是有关思维具有确定性的规律，充足理由律是有关思维具有论证性的规律。任何思维活动如若违背了上述四条规律都必然会出现这样或那样的逻辑错误。 任何规律都在一定条件下发生作用。逻辑规律发生作用的条件是同一思维过程，即在同一时间、同一关系下针对同一对象的思维活动。 所谓“同一时间”，是指思想所涉及的对象处于相对稳定状态的那段时间，在此时间内该对象的本质属性保持不变。思维过程中同一时间的长短取决于思想所涉及对象相对稳定状态所持续时间的长短。 所谓“同一关系”，主要指对象的同一方面。任何对象都有许多方面，是多种本质属性的统一。例如“水”就起码有物理属性方面和化学属性方面。水的物理属性方面表明，水是一种无色、无味的透明液体，在一个大气压下气温摄氏零度时结冰，摄氏100度时沸腾；水的化学属性方面表明，水是由两个氢原子和一个氧原子化合成一个水分子而构成的物质。因此，在不同的关系下，对同一对象可以有不同 我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元（proposition constant）。深入的讨论还需要引入命题变元（proposition variable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。相同符号的不同意义，容易从上下文来区别，在未指出符号所表示的具体命题时，它们常被看作变元。 命题常元、变元及联结词是形式描述命题及其推理的基本语言成分，用它们可以形式地描述更为复杂的命题。下面我们引入高一级的语言成分——命题公式。 定义1.1 以下三条款规定了命题公式（proposition formula）的意义： （1）命题常元和命题变元是命题公式，也称为原子公式或原子。 （2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（A？B）也是命题公式。 （3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。 命题公式简称公式，常用大写拉丁字母A，B，C等表示。公式的上述定义方式称为归纳定义，第四章将对此定义方式进行讨论。 例1.8 （┐（p→（q∧r）））是命题公式，但（qp），p→r，p1∨p2∨…均非公式。 为使公式的表示更为简练，我们作如下约定： （1）公式最外层括号一律可省略。 （2）联结词的结合能力强弱依次为┐，（∧，∨），→，？，（∧，∨）表示∧与∨平等。 （3）结合能力平等的联结词在没有括号表示其结合状况时，采用左结合约定。 例如，┐p→q∨（r∧q∨s）所表示的公式是（（┐p）→（q∨（（r∧q）∨s））） 设A是命题公式，A1是A 的一部分，且A1也是公式，则A1称为公式A的子公式。 如对公式A：┐p→q∨（r∧q∨s），则p，┐p ，q ，（r∧q∨s）及q∨（r∧q∨s）都是公式A的子公式，而┐q，┐p→q，虽然是公式，但确不是A的一部分，因此不是A 的子公式；q∨（r∧虽然是公式A的一部分，但不是公式，因而也不是A的子公式。 如果公式A含有命题变元p1，p2，…，pn，记为A（p1，…，pn），并把联结词看作真值运算符，那么公式A可以看作是p1，…，pn的真值函数。对任意给定的p1，…，pn 的一种取值状况，称为指派（assignments），用希腊字母a，b等表示，A均有一个确定的真值。当A对取值状况a 为真时，称指派a弄真A，或a是A的成真赋值，记为a （A）= 1；反之称指派a弄假A，或a是A的成假赋值，记为a （A）= 0.对一切可能的指派， 《普通逻辑》试题样式 一、填空题：(答案仅供参考) 1、“我们必须用逻辑来规范我们的思维。”这里的“逻辑”一词的含义是思维规律。 2、形式逻辑是研究思维的结构及其规律和简单的推理的科学。 3、概念的两个基本特征是内涵和外延。 4、从周延性的角度看，“任何困难都不是不可克服的”，其谓项是周延的。 5、概念“思想家”与概念“政治家”的外延关系是交叉关系。 6、“文学”这一概念可限制为古诗词，概括为艺术。 7、任何逻辑形式都包含有两个部分。其中在逻辑形式中保持不变的部分叫做常项，在逻辑形式中可变的部分叫做变相。 8、具有矛盾关系的两个判断的逻辑值的关系是不能同真，也不能同假，具有反对关系的两个判断的逻辑值的关系是不能同真，可以同假。 9、当SOP假时，SAP 真，SEP 假，SIP 真。 10、根据对当关系，已知SAP真，则SEP的逻辑值为假，SIP的逻辑值为真，SOP的逻辑值为假。 11、要使“p∧﹁q”为真，则q应赋假值；已知“p∨﹁q”为假，则“﹁p←→q”的逻辑值为真。 12、从一个或几个已知判断中推出一个新的判断的思维形式叫归纳判断。 13、推理要有逻辑性，这是指推理的形式要正确。推理的结论有效必须满足的两个条件是前提真实和形式有效。 14、将“所有的诗歌都是文学作品”进行换位推理得到有的文学作品是诗歌。 15、SEP可换质为SA﹁P ，PAS可换位为SIP ，SO﹁P可换质为。 16、三段论MOP∧MAS→SOP属于第 3 格OAO 式。 17、三段论“SAM∧MAP→SAP”属于第 1 格的AAA 式。 18、已知一个三段论的小前提是SOM，则结论应是SOP ，大前提是PAM ，属于第 2 格。 19、在三段论中，大项是指在结论中的谓项，中项是指在前提中 出现两次的项。 #include “离散数学”实验报告（求给定命题公式地真值表并根据真值表求公式地主范式） 专业网络工程 班级 1202班 学号 12407442 姓名张敏慧 2013.12.14 目录 一.实验目地 3 二.实验内容 (3) 求任意一个命题公式地真值表 (3) 三.实验环境 3 四. 实验原理和实现过程（算法描述）3 1.实验原理 (3) 2.实验流程图 (5) 五.实验代码 6 六. 实验结果14 七. 实验总结19 一.实验目地 本实验课程是网络工程专业学生地一门专业基础课程,通过实验,帮助学生更好地掌握计算机科学技术常用地离散数学中地概念.性质和运算；通过实验提高学生编写实验报告.总结实验结果地能力；使学生具备程序设计地思想,能够独立完成简单地算法设计和分析. 熟悉掌握命题逻辑中地真值表.主范式等,进一步能用它们来解 决实际问题. 二.实验内容 求任意一个命题公式地真值表,并根据真值表求主范式 详细说明： 求任意一个命题公式地真值表 本实验要求大家利用C/C＋＋语言,实现任意输入公式地真值表计算.一般我们将公式中地命题变元放在真值表地左边,将公式地结果放在真值表地右边.命题变元可用数值变量表示,合适公式地表示及求真值表转化为逻辑运算结果；可用一维数表示合式公式中所出现地n个命题变元,同时它也是一个二进制加法器地模拟器,每当在这个模拟器中产生一个二进制数时,就相当于给各个命题变元产生了一组真值指派.算法逻辑如下： （1）将二进制加法模拟器赋初值0 （2）计算模拟器中所对应地一组真值指派下合式公式地真值. （3）输出真值表中对应于模拟器所给出地一组真值指派及这组真值指派所对应地一行真值. （4）产生下一个二进制数值,若该数值等于2n-1,则结束,否则转（2）. 三.实验环境； 实验报告 实验名称：任意命题公式的真值表 实验目的与要求：通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算，包括联结词、真值表、运算的优先级等，提高学生编写实验报告、总结实验结果的能力，培养学生的逻辑思维能力和算法设计的思想，能够独立完成简单的算法设计和分析，进一步用它们来解决实际问题，帮助学生学习掌握C/C++语言程序设计的基本方法和各种调试手段，使学生具备程序设计的能力。 实验内容提要：求任意一个命题公式的真值表 实验步骤：（一）、关于命题公式的形式和运算符（即联结词）的运算 首先根据离散数学的相关知识，命题公式由命题变元和运算符（即联结词）组成，命题变元用大写字母英文表示（本次试验没有定义命题常元T和F，即T、F都表示命题变元），每个命题变元都有两种真值指派0和1，对应于一种真值指派，命题公式有一个真值，由所有可能的指派和命题公式相应的真值按照一定的规范构成的表格称为真值表。 目前离散数学里用到的包括扩充联结词总共有九种，即析取（或）、合取（与）、非、蕴含、等值、与非、或非、异或、蕴含否定，常用的为前五种，其中除了非运算为一元运算以外，其它四种为二元运算。所以本次实验设计时只定义了前五种运算符，同时用“/”表示非，用“*”表示合取，用“+”表示析取，用“>”表示蕴含，用“:”表示等值，且这五种运算符的优先级依次降低，如果需用括号改变运算优先级，则用小括号()改变。 以下为上述五种运算符运算时的一般真值表，用P和Q表示命题变元：1．非，用“/”表示 2．合取（与），用“*”表示 3．析取（或），用“+”表示 4.蕴含，用“>”表示 5.等值，用“:”表示 （二）、命题公式真值的计算 对于人来说，计算数学表达式时习惯于中缀表达式，例如a*b+c，a*（b+c）等等，而对于计算机来说，计算a*b+c还好，计算a*（b+c）则困难，因为括号的作用改变了运算的顺序，让计算机识别括号而改变计算顺序显得麻烦。经理论和实践研究，用一种称之为后缀表达式（逆波兰式）的公式形式能让计算机更容易计算表达式的真值。例如上面的a*（b+c），其后缀表达式为abc+*，计算时从左边开始寻找运算符，然后按照运算符的运算规则将与其相邻的前面的一个（非运算时为一个）或两个（其它四种运算为两个）操作数运算，运算结果取代原来的运算符和操作数的位置，然后重新从左边开始寻找运算符，开始下一次计算，比如上式，从左边开始寻找运算符，先找到+，则计算b+c，结果用d表示，这时后缀表达式变为ad*，又重新开始从左边开始寻找运算符，找到*，则计算a*d， 题号：第一题 题目：电梯模拟 1，需求分析： 计算命题演算公式的真值 所谓命题演算公式是指由逻辑变量(其值为TRUE或FALSE )和逻辑运算符人(AND )、 V( OR)和「( NOT )按一定规则所组成的公式(蕴含之类的运算可以用A、V和「来表示)。公式运算的先后顺序为「、人、V,而括号()可以改变优先次序。已知一个命题演算公式及各变量的值，要求设计一个程序来计算公式的真值。 要求： ( 1)利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；然后根据后缀形式, 从 叶结点开始构造相应的二叉树；最后按后序遍历该树, 求各子树之值, 即每到达一个结点, 其子树之值已经计算出来, 当到达根结点时, 求得的值就是公式之真值。 ( 2)逻辑变元的标识符不限于单字母,而可以是任意长的字母数字串。 ( 3)根据用户的要求显示表达式的真值表。 2,设计： 2.1 设计思想： <1> ,数据结构设计： (1) 线性堆栈1 的数据结构定义 typedef struct { DataType stack [MaxStackSize]; int top; /* 当前栈的表长*/ } SeqStack; 用线性堆栈主要是用来存储输入的字符, 它的作用就是将中缀表达式变成后缀表达式。 (2) 线性堆栈2 的数据结构定义 typedef struct { BiTreeNode *stack [MaxStackSize]; int top; /* 当前栈的表长*/ } TreeStack; 这个堆栈和上面的堆栈的唯一不同就是它们存储的数据的类型不同, 此堆栈存储的是树节点,它的作用是将后缀表达式构成一棵二叉树。 （3）树节点数据结构定义typedef struct Node { DataType data; struct Node *leftChild; struct Node *rightChild; }BiTreeNode; <2>算法设计详细思路如下：首先实现将中缀表达式变成后缀表达式：在将中缀表达式变成后缀表达式的 #include "stdio.h" #include "stdlib.h" #include "string.h" #include "math.h" #define N 50 void pd(int b[N],int f); int H1 (char T1[N], char T2[N], int T3[N], int y); int H2 (char T1[N], char T2[N], int T3[N], int y); int main() { int i1,i2,d=1,T3[N],kh=0,jg,j=0,y; int w=0,hequ[N],h=0,x=0,xiqu[N]; char T1[N],T2[N],T10[N],s; hequ[0]=-1; xiqu[0]=-1; printf("#########################################\n"); printf("## 用!表示否定 ##\n"); printf("## 用&表示合取 ##\n"); printf("## 用|表示析取 ##\n"); printf("## 用^表示条件 ##\n"); printf("## 用~表示双条件 ##\n"); printf("#########################################\n\n"); printf("请输入一个合法的命题公式:\n"); gets(T1); strcpy(T10,T1); for(i1=0;i1 第三章判断(一) 学习目得与要求:了解什么就是性质判断及其结构;理解掌握对当关系与主、谓项得周延情况;掌握各种判断得逻辑形式及其特征。 第一节判断得概述 一、判断及其基本特征 1、什么就是判断？ 判断就是对思维对象有所断定得思维形式。 概念就是反映思维对象得。但就是,思维对象不就是孤立存在得,它们之间就是相互联系得。某对象具有某种性质,某对象不具有某种性质;甲对象与乙对象之间具有某种关系或不具有某种关系,这些都就是事物得情况。事物得情况与事物得情况之间也有联系,这种联系也就是一种事物得情况,就是较为复杂得事物情况。反映事物情况不就是概念这种思维形态能够胜任得,必须用概念组成判断这种思维形态,才能反映种种事物情况,即反映对象之间得种种联系。事物情况就是一种客观存在,只有当人们在实践基础上认识了某种事物情况存在或不存在,然后才能在思维中肯定或否定这种事物情况,即对这种事物情况做出断定,形成判断。例如: ①文学就是社会生活得反映。 ②语言不就是生产工具。 2、判断得基本特征 (1)判断总有所断定。 判断反映事物情况得存在就就是在进行断定,它或者肯定某事物情况存在,或者否定某事情情况存在,都就是在断定。任何判断总要对事物情况做出断定。如果一个语句表达得思想无所断定,就不就是判断。 (2)判断总有真有假。 符合客观实际得就是真判断,不符合客观实际得就是假判断。具体判断在事实上得真假问题虽然就是逻辑所关心得,却不就是逻辑所着重研究得。逻辑学主要研究判断得逻辑形式得真假条件及真假关系,从而由判断组成推理,进行有效得思维活动。 二、判断与语句 判断与语句既有密切联系又有区别。 1、判断与语句得密切联系 同任何概念都就是用语词表达得一样,任何判断都就是用语句表达得。语句就是判断得物质载体,而判断则就是语句所表达得思想内容。在传统逻辑中,可表达判断得语句通常叫命题,陈述句都就是命题,也都表达判断。 2、判断与语句得区别 1 析取范式与合取范式 这是命题公式的两种特殊的简明形式。一个重要的结论是，任何命题公式都可以等价地转化为这两种形式。我们将学习这种转化方法及其应用。 1. 析取范式 定义1.1 命题变元及其否定统称为文字（literal ）。由有限个文字组成的合取式称为简单合取式。由有限个简单合取式组成的析取式称为析取范式（disjunction normal form ），简称DNF 。 例1.2 求下列公式的析取范式。 (1) ()(2) () ()p q p p q p q →∧?∨∧?∧ 方法小结： （1） 将蕴含联结词→与等价联结词?都转化为析取与合取联结词。 （2） 用德摩根律将所有否定词转移到括号内，并用双重否定律消除双重 否定词。 （3） 用分配律将析取联结词移到括号之外。 （4） 最后化简，即消除简单合取式中重复出现的变元（用幂等律、矛盾 律、零律） 练习1.3 定理1.4 任何命题公式都有等值的析取范式。 2. 合取范式 定义2.1由有限个文字组成的析取式称为简单析取式，也称为子句（clause ）。 由有限个简单析取式组成的合取式称为合取范式（conjunction normal form ），简称CNF 。 例2.2 求下列公式的合取范式。 (1) ()(2) () ()p q p p q p q ?→∨∧∨?∨ 方法小结： （1）将蕴含联结词→与等价联结词?都转化为析取与合取联结词。 （2）用德摩根律将所有否定词转移到括号内，并用双重否定律消除双重否定词。 （3）用分配律将合取联结词移到括号之外。 （4）最后化简，即消除简单析取式中重复出现的变元（用幂等律、排中律、同一律） 练习2.3 定理2.4 任何命题公式都有等值的合取范式。 3.极小项 为了进一步规范析取范式与合取范式，我们引入极小项与极大项这一对概念。 符号的次序：在符号表中，符号是有先后次序的。在一个命题逻辑语言中，所有的命题变元来自于一个符号表，称为命题变元符号表。我们约定：命题公式中所使用的英文字母在命题变元符号表中的次序与其在英文字母表中的次序相同。也可以用标识符作命题变元，标识符在符号表中的次序为字典序。 定义1.1满足下述两个条件的简单合取式称为极小项：（1）每个变元仅出现一次，（2）变元出现的先后次序与它们在符号表中的先后次序相同。含n 个变元的极小项称为n元极小项。 例如，等等都是极小项。等等都不是极小项。 提问：由n个不同变元组成的n元极小项共有多少个？ 回答：共有2n个。一个极小项有n个变元，每个变元前面可以有否定词也可以没有，所以共有2n个组合。 例如，p, q两个变元可以组成的极小项如下： ?∧??∧∧?∧ p q p q p q p q ,,, 极小项的名称：极小项的成真赋值是唯一的，并对应着一个唯一的二进制数。若该二进制数所对应的十进制是i，则该极小项记为m i。 例如，上述4个极小项分别记为m0, m1, m2, m3。三元极小项的例子见课本第25页表2.4左列。 2 形式逻辑练习题 绪论 一、请指出下列各段文字中“逻辑”一词的涵义： 1．“虽说马克思没有遗留下‘逻辑’（大写字母的），但他遗留下《资本论》的‘逻辑’……”。2．“写文章要讲逻辑。” 3．“跨过战争的艰难路程之后，胜利的坦途就到来了，这是战争的自然逻辑。” 4．“艾奇逊当面撒谎，将侵略写成了‘友谊’……美国老爷的逻辑，就是这样。” 二、单项选择题： 1．思维的逻辑形式之间的区别，取决于（）。 a.思维的内容 b.逻辑常项 c.逻辑变项 d.语言表达形式 2．“所有S是P”与“有的S不是P”（） a.逻辑常项相同但变项不同 b.常项不同但变项相同 c.常项与变项均相同 d.常项与变项均不同 概念 一、下列句子中标有横线的语词表达何种概念（单独或普遍、集合或非集合）？ （1）人民，只有人民才是创造世界历史的真正动力。 （2）在我们的国家里，人民享受着广泛的民主和自由，同时又必须用社会主义的纪律来约束自己。（3）群众是真正的英雄，而我们自己则往往是幼稚可笑的。 （4）我们的干部必须关心群众生活，注意工作方法。 （5）词是最小的能自由运用的语言单位。 （6）根据森林的效益，可以将森林分为防护林、用材林、经济林、薪炭林、特殊用途林。 二、请用欧拉图表示下列各句中标有横线的概念之间的外延关系。 （1）马克思主义哲学就是辩证唯物主义和历史唯物主义。 （2）中国共产党是无产阶级的先锋队，是不谋任何私利的政党。 （3）印度地处亚洲，这个亚洲国家是发展中国家。 （4）小明是个小学生，他表姐是个中学生而且是三好学生，他爸爸是工人。 （5）一个人的知识不外直接经验的知识和间接经验的知识两部分。 （6）科研工作者、教育工作者是脑力劳动者，脑力劳动者也是劳动者。 （7）鲁迅是伟大的文学家、伟大的思想家和伟大的革命家。 （8）小说和剧本都是文学作品。 三、下列语句作为定义是否正确？为什么？ （1）语言不是上层建筑。 （2）机会主义者就是看机会而采取行动的人。 （3）政治经济学是研究资本主义生产关系发展规律的科学。 （4）奇数就是偶数加1或减1而成的数，偶数则是奇数加1或减1而成的数。 （5）狮子是兽中之王。 （6）资本家乃是剥削别人劳动的人。 （7）商品是通过货币进行交换的劳动产品。 （8）正方形就是四边相等的四边形。 四、下列划分是否正确？为什么？ （1）华东师大分为文科各系和理科各系。 （2）逻辑学分为形式逻辑，辩证逻辑，现代逻辑，古典逻辑。 （3）概念分为概念的内涵和概念的外延。 离散数学实验报告 专业班级：12级计算机本部一班姓名：鲍佳珍 学号：201212201401016 实验成绩： 1．【实验题目】 命题逻辑实验二 2．【实验目的】 熟悉掌握命题逻辑中真值表，进一步能用它们来解决实际问题。 3．【实验内容】 求任意一个命题公式的真值表 4、【实验要求】 C或C＋＋语言编程实现 5. 【算法描述】 1.实验原理 真值表:表征逻辑事件输入和输出之间全部可能状态的表格。列出命题公式真假值的表。通常以1表示真，0 表示假。命题公式的取值由组成命题公式的命题变元的取值和命题联结词决定，命题联结词的真值表给出了真假值的算法。真值表是在逻辑中使用的一类数学表，用来确定一个表达式是否为真或有效。 2.实验过程 首先是输入一个合理的式子，生成相应真值表，然后用函数运算，输出结果：要求可生成逻辑非、合取、析取、蕴含、双条件表达式的真值表，例如：输入 !a 输出真值表如下： a !a 0 1 10 输入a&&b 输出真值表如下： a b a&&b 0 0 0 0 1 0 1 0 0 1 1 1 输入a||b 输出真值表如下： a b a||b 0 0 0 0 1 1 1 0 1 1 1 1 输入a->b 输出真值表如下： a b a->b 0 0 1 0 1 1 1 0 0 1 1 1 输入a<>b (其中<>表示双条件) 输出真值表如下： a b a<>b 0 0 1 0 1 0 1 0 0 1 1 1 6.【源程序（带注释）】 #include 离散逻辑学实验 班级：10电信实验班学号：Q 姓名：王彬彬 一、实验目的 熟悉掌握命题逻辑中的联接词、真值表、主范式等，进一步能用它们来解决实际问题。 二、实验内容 1. 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、条件和双条件的真值。（A） 2. 求任意一个命题公式的真值表（B，并根据真值表求主范式（C）） 三、实验环境 C或C＋＋语言编程环境实现。 四、实验原理和实现过程（算法描述） 1.实验原理 （1）合取：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题P∧Q, 读作P、Q的合取, 也可读作P与Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = T, Q = T时方可P∧Q =T, 而P、Q只要有一为F则P∧Q = F。这样看来，P∧Q可用来表示日常用语P与Q, 或P并且Q。 （2）析取：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题P∨Q, 读作P、Q的析取, 也可读作P或Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = F, Q = F时方可P∨Q =F, 而P、Q只要有一为T则P∨Q = T。这样看来，P∨Q可用来表示日常用语P或者Q。 （3）条件：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题P→Q, 读作P条件Q, 也可读作如果P，那么Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为只有当两个命题变项P = T, Q = F时方可P→Q =F, 其余均为T。 （4）双条件：二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题P←→Q, 读作P双条件于Q。这个新命题的真值与构成它的命题P、Q的真值间的关系为当两个命题变项P = T, Q =T时方可P←→Q =T, 其余均为F。 （5）真值表:表征逻辑事件输入和输出之间全部可能状态的表格。列出命题公式真假值的表。通常以1表示真，0 表示假。命题公式的取值由组成命题公式的命题变元的取值和命题联结词决定，命题联结词的真值表给出了真假值的算法。真值表是在逻辑中使用的一类数学表，用来确定一个表达式是否为真或有效。 （6）主范式： 主析取范式：在含有n个命题变元的简单合取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单合取式为小项。由若干个不同的小项组成的析取式称为主析取范式;与A等价的主析取范式称为A的主析取范式。任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式,并且是惟一的。 主合取范式：在含有n个命题变元的简单析取式中,若每个命题变元与其否定不同时存在,而两者之一出现一次且仅出现一次,称该简单析取式为大项。由若干个不同的大项组成的合取式称为主合取范式;与A等价的主合取范式称为A的主合取范式。任意含n个命题变元的非永真命题公式A都存在与其等价的主合取范式,并且是惟一的。 五、代码设计结果： 命题常项与命题变项 真值确定的命题称为命题常项或命题常元。 例如，下面的，都是命题常项。p：2是素数。q：雪是黑色的。 简单陈述句中，由于某个或某些成分取值不同而导致该句真值不确定，这种句子称为命题变项，它不是命题，但这个或这些元素成分一旦取值定下来，句子就成为命题。 例不是命题，但当给定与确定的值后，它的真值也就定下来了，它是命题 变项。命题变项也用表示之。一个符号，例如，它表示的是命题常 项还是命题变项，一般由上下文来确定。一个命题变项经符号化后，如符号化为，就可以表示任意的命题。 析取范式与合取范式 析取 用连词∨把几个公式连接起来所构成的公式叫做析取，而此析取式的每一组成部分叫做析取项。由一些合适公式所构成的任一析取也是一个合适公式。 合取 用连词∧把几个公式连接起来而构成的公式叫做合取，而此合取式的每个组成部分叫做合取项。一些合适公式所构成的任一合取也是一个合取公式。 定义 命题变项及其否定统称作文字。仅由有限个文字构成的析取式称为简单析取式。仅由有限个文字构成的合取式称为简单合取式。 例如，文字：p，┐q，r，q。 简单析取式：p，q，p∨q，p∨┐p∨r，┐p∨q∨┐r。 简单合取式：p，┐r，┐p∧r，┐p∧q∧r，p∧q∧┐q。 定理 （1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定。 （2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定。 矛盾式 contradictory（矛盾式或永假式） 设A为任一命题公式，若A在它的各种指派情况下，其取值均为假，则称A是矛盾式或永假式。 若命题公式A不是矛盾式，则称A为可满足式。 重言式 Tautology （重言式又称为永真式） 设A为任一命题公式，若A在它的各种赋值下取值均为真，则称A是重言式。 定义 （1）由有限个简单合取式构成的析取式称为析取范式。 （2）由有限个简单析取式构成的合取式称为合取范式。 （3）析取范式与合取范式统称为范式。 例如，析取范式：（p┐∧q）∨r，┐p∧q∧r，p∨┐q∨r。 1、逻辑联接词的运算 从键盘输入两个命题变元P和Q的真值，输出它们的合取、析取、条件、双条件和P的否定的真值。 #include { if(P==0) P=P; else P=1; if(Q==0) Q=Q; else Q=1; if(P==1&&Q==0) return(0); else return(1); } int shuangtiaojian(int P,int Q) { if(P==0) P=P; else P=1; if(Q==0) Q=Q; else Q=1; return(!P^Q); } int Pfaoding(int P) { if(P==0) P=P; else P=1; return(!P); } int show(int a,int b) { cout<<"P Q P∧Q P∨Q P→Q P←→Q ┐P"<离散数学自学笔记命题公式及其真值表
逻辑判断推理中常用的逻辑公式
MBA联考形式逻辑公式表
2 离散数学-命题公式,真值表
形式逻辑的基本规律
离散数学自学笔记命题公式及其真值表
最新形式逻辑期末考试卷上课讲义
利用真值表法求取主析取范式以及主合取范式的实现
求给定命题公式真值表并根据真值表求公式主范式
任意命题公式的真值表
逻辑命题公式计算
利用真值表法求取主析取范式以及主合取范式的实现
形式逻辑 第三章 判断
析取范式与合取范式
形式逻辑习题
离散数学命题公式真值表C++或C语言实验报告
离散数学,逻辑学,命题公式求真值表
析取范式与合取范式
离散数学之逻辑运算和命题公式真值表
相关主题
文本预览