第1章逻辑代数(上):命题演算
1.1 逻辑联结词与命题公式
1.1.1 逻辑联结词
否定词(negation)“并非”(not),用符号?(或~)表示。设p表示一命题,那么?p表示命题p的否定。当p真时?p假,而当p假时?p真。?p读作“并非p”或“非p”。用类似表1.1的真值表(truth table)规定联结词的意义。
表1.1
p ?p
1 1 0
合取词(c onjunction)“并且”(and),用符号∧表示。设p,q表示两命题,那么p∧q 表示合取p和q所得的命题,即当p和q同时为真时p∧q真,否则p∧q为假。p∧q读作“p并且q”或“p且q”。合取词∧的意义和命题p∧q的真值状况可由表1.2来刻划。
表1.2
p q p∧q
0 0 1 1 0
1
1
1
析取词(disjunction)“或”(or)用符号∨表示。设p,q表示两命题,那么p∨q表示p和q的析取,即当p和q有一为真时,p∨q为真,只有当p和q均假时p∨q为假。p∨q 读作“p或者q”,“p或q”。析取词∨的意义及复合命题p∨q的真值状况由表1.3描述。
表1.3
p q p∨q
0 0 1 1 0
1
1
1
1
1
蕴涵词(implication)“如果……,那么……”(if…then…),用符号→表示。设p,q 表示两命题,那么p→q表示命题“如果p,那么q”,它常被称作条件命题。当p真而q
假时,命题p→q为假,否则均认为p→q为真。p→q中的p称为蕴涵前件,q称为蕴涵后件。p→q的读法较多,可读作“如果p则q”,“p蕴涵q”,“p是q的充分条件”,“q是p 的必要条件”,“q当p”,“p仅当q”等等。数学中还常把q→p,?p→?q,?q→?p分别叫做p→q的逆命题,否命题,逆否命题。蕴涵词→的意义及复合命题p→q的真值状况规定见表1.4。
表1.4
p q p→q
0 0 1 1 0
1
1
1
1
1
双向蕴涵词(two-way implication)“当且仅当”(if and only if),用符号?表示之。设p,q为两命题,那么p?q表示命题“p当且仅当q”,“p与q等价”,即当p与q 同真值时p?q为真,否则为假。p?q读作“p双向蕴涵q”,“p当且仅当q”,“p等价于q”。由于“当且仅当”“等价”常在其它地方使用,因而用第一种读法更好些。双向蕴涵词的意义及p?q的真值状况由表1.5给出。
表1.5
p q p?q
0 0 1 1 0
1
1
1
1
1.1.2 命题公式
定义1.1 归纳定义命题公式(简称公式proposition formula):
(1)命题常元和命题变元是命题公式,也称为原子公式或原子。
(2)如果A,B是命题公式,那么(?A),(A∧B),(A∨B),(A→B),(A?B)也是命题公式。
(3)只有有限步引用条款(1),(2)所组成的符号串是命题公式。
定义1.2设公式A含有命题变元p1,p2,…,p n(有时用A(p1,p2,…,p n)表示这一状况),称p1,p2,…,p n每一取值状况为一个指派(assignments),用希腊字母α,β等表示,
当A对取值状况α为真时,称指派α弄真A,或α是A的弄真指派,记为α(A) = 1;反之称指派α弄假A,或α是A的弄假指派,记为α(A) = 0。
1.1.3 语句形式化
将自然语言表述的命题“翻译”成命题公式,常称为语句形式化。语句形式化要注意以下几个方面:
●要善于确定原子命题,不要把一个概念硬拆成几个概念,例如“弟兄”是一个概念,
不要拆成“弟”和“兄”、“我和他是弟兄”是一个原子命题。
●要注意语句的语用,不同的语用有不同的逻辑含义。例如“狗急跳墙”可能说的是
一个规律,也可能说的是一个现象。
●要善于识别自然语言中的联结词(有时它们被省略)。例如“风雨无阻,我去北京”
一句,可理解为“不管是否刮风、是否下雨我都去北京”。
●否定词的位置要放准确。
●需要的括号不能省略;而可以省略的括号,在需要提高公式可读性时亦可不省略。
●注意“只要?,就?”“只有?,才?”的正确理解。因果关系也常常用蕴涵词来
表示,这一点是有争议的。
●语句的形式化的结果未必是唯一的。
练习1.1题解
1、选择题
(1)设P:我将去镇上,Q:我有时间。命题“我将去镇上,仅当我有时间”符号化为()A.P→Q; B. Q→P ; C. P?Q ; D. Q∨?P.。
【答案】:A
(2)设P:张三可以做这件事,Q李四可以做这件事。命题“张三或李四可以做这件事”符号化为()
A.P∨Q; B.P∨?Q ; C. P??Q ; D. (?P∨?Q)
【答案】:A
(3)设P:我们划船,Q:我们跑步。命题“我们不能既划船又跑步”符号化为()A.?P∧?Q ; B.?P∨?Q ; C.?(P?Q) ; D. P??Q
【答案】:B
(4)下列语句中哪个是真命题()
A.我正在说谎
B. 如果1+2=3,那么雪是黑的
C. 如果1+2=5,那么雪是黑的
D. 严禁吸烟
【答案】:C
(5)?P→Q的逆命题是()
A .Q→?P B. P→?Q C.?Q→?P D.?P→?Q
【答案】:A
(6)下面哪一个命题是命题“2是偶数或-3是负数”的否定()
A.2是偶数或-3不是负数
B. 2是奇数或-3不是负数
C. 2不是偶数且-3不是负数
D. 2是奇数且-3不是负数
【答案】:C
2、填空题
(1)下列句子中,是命题的有 .
(a)我是教师。
(b)禁止吸烟。
(c)蚊子是鸟类动物。
(d)上课去!
【答案】:(a),(c)
(2)设P:我生病,Q:我去学校
(a)命题“我虽然生病但我仍去学校”可符号化为。
(b)命题“只有我生病的时候,我才不去学校” 可符号化为。
(c)命题“只要我生病,我就不去学校” 可符号化为。
(d)命题“当且仅当我生病,我才不去学校” 可符号化为。
【答案】:(a)P∧Q;(b).?Q→P;(c)P→?Q;(d)P??Q
(3)“a≥0”表示a>0 a=0 ;“a是非负实数”表示a≥0 a是实数(在空格中填上适当的命题联结词)。
【答案】:∨;∧
(4)在空格中填上表(表1.6)各列所定义的命题联结词:
表1.6
P Q P Q P Q
0 0 1 1
0 1 1 0
1 0 0 0
1 1 1 1
【答案】:→;?
(5)P,Q为两个命题,当且仅当时,P→Q的真值为0。
【答案】:P真且Q假
(6)公式P→Q的否命题为,逆否命题为。
【答案】:﹁P→﹁Q;﹁Q→﹁P
3.将下列命题形式化:
(1)你是博士,但我是硕士。
【答案】:可表示为 (p∧q),其中p:你是博士;q:我是硕士
(2)我今天或明天去泰山的说法是谣传。
【答案】:可表示为? (p∨q),其中p:我今天去泰山;q:我明天去泰山
(3)如果买不到飞机票,我不去海南岛。
【答案】:可表示为?p→?q,其中,p:我买到飞机票,q:我去海南岛
(4)只要他出门,他必买书,不管他带的钱多不多。
【答案】:可表示为(p∧q→r)∧(?p∧q→r)或q→r,其中p:他带的钱多,q:他出门,r:他买书。
(5)除非你陪伴我或代我雇辆车子,否则我不去。
【答案】:可表示为(p∨q) ? r,其中p:你陪伴我,q:你代我雇车,r:我去
(6)只要充分考虑一切论证,就可得到正确见解;必须充分考虑一切论证,才能得到正确见解。
【答案】:可表示为(p→q) ∧(q→p )或p?q,其中p:你充分考虑了一切论证,q:你得到了正确见解
(7)除非你是成年人,否则只要你身高不超过1米3,就能到儿童游乐场玩耍。
?r?(?s→t),其中r:你是成年人,s:你身高超过1米3,t: 你到儿童游乐场玩耍(8)如果只有懂得希腊文才能了解柏拉图,那么我不了解柏拉图。
【答案】:可表示为(q→p ) →?q,其中p:我懂得希腊文,q:我了解柏拉图
(9)侈而惰者贫,而力而俭者富。(韩非:《韩非子?显学》)
【答案】:可表示为((p∧q)→r) ∧((?p∧?q)→?r),其中p:你奢侈,q:你懒惰,r:你贫困
(10)骐骥一跃,不能十步;驽马十驾,功在不舍;锲而舍之,朽木不折;锲而不舍,金石可镂。(荀况:《荀子?劝学》)
【答案】:可表示为(p→?q) ∧(s→r) ∧(m∧n→?o) ∧(m∧?n→v),其中p:骐骥一跃,q:骐骥行十步,r:驽马行千里,s:驽马不断奔跑,m:你雕刻,n:你放弃,o:你将朽木折断,v:你将金石雕刻
4.根据命题公式的定义和括号省略的约定,判定下列符号串是否为公式,若是,请给出它的真值表,并请注意这些真值表的特点(p,q,r,s为原子命题):
(1)? (p)
【答案】:? (p) 不是公式
(2)(p∨qr)→s
【答案】:(p∨qr)→s 不是公式
(3)(p∨q)→p
【答案】:(p∨q)→p 是公式,其真值表如表1.7所示:
表1.7
(4)p→(p∨q)
【答案】:p→(p∨q) 是公式,其真值表如表1.8所示(恒真):
表1.8
(5)p∧(p→q)→q
【答案】:p∧(p→q)→q 是公式,其真值表如表1.9所示(恒真):
表1.9
(6)p∧(p→q)∧(p→?q)
【答案】:p∧(p→q)∧(p→?q) 是公式,其真值表如表1.10所示(恒假):
表1.10
(7)?(p∨q) ??q∧?p
【答案】:?(p∨q) ??q∧?p 是公式,其真值表如表1.11所示(恒真):
表1.11
(8)?p∨q?(p→q)
【答案】:?p∨q?(p→q) 是公式,其真值表如表1.12所示(恒真):
表1.12
(9)(p→q)∧(q→r)→(p→ r )
【答案】:(p→q)∧(q→r)→(p→r) 是公式,其真值表如表1.13所示(恒真):
表1.13
(10)(p∨q→r) ?(p→r)∧(q→r)
【答案】:(p∨q→r)?(p→r)∧(q→r) 是公式,其真值表如表1.14所示(恒真):
表1.14
5.给出弄真下列命题公式的指派:
(1)((p→q)∧q)→┐p
【答案】:弄真指派有(0,0),(0,1),(1,0)
(2)((p→q)→r)→((q→p)→r)
【答案】:弄真指派有(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1) (3)((p?q)→r)→((q→p) ?r)
【答案】:弄真指派有(0,0,0),(0,0,1),(0,1,0), (1,0,1),(1,1,0),(1,1,1) (4)?((p∨q)∧r)→(r→p)
【答案】:弄真指派有(0,0,0),(0,1,0), (0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)
1.2 逻辑等价式和逻辑蕴涵式
1.2.1 重言式
定义1.3如果对命题公式A中命题变元的一切指派均弄真A,那么,称A为重言式(tautology);重言式又称永真式;如果至少有一个这样的指派弄真A,那么,称A为可满足式(satisfactable formula),否则称A为不可满足式或永假式、矛盾式。
1.2.2 逻辑等价式和逻辑蕴涵式
定义1.4 当命题公式A?B为永真式时,称A逻辑等价于B,记为A┝┥B,它又称为逻辑等价式(logically equivalent)。
以下是一些重要的逻辑等价式,其中A,B,C表示任意命题公式:
E1??A┝┥A 双重否定律
E2A∨A┝┥A ,A∧A┝┥A 幂等律
E3 A∨B┝┥B∨A ,A∧B┝┥B∧A 交换律
E4 (A∨B)∨C┝┥A∨(B∨C) 结合律
(A∧B)∧C┝┥A∧(B∧C)
E5 A∧(B∨C)┝┥(A∧B)∨(A∧C) 分配律
A∨(B∧C)┝┥(A∨B)∧(A∨C)
E6 ? (A∨B)┝┥?A∧?B 德摩根律
? (A∧B)┝┥?A∨?B
E7 A∨(A∧B)┝┥A 吸收律
A∧(A∨B)┝┥A
E8 A→B┝┥?A∨B
E9 A? B┝┥(A→B)∧(B→A)
E10 A∨t┝┥t , A∧f┝┥f
E11 A∨f┝┥A , A∧t┝┥A
E12 A∨?A┝┥t ,A∧?A┝┥f
E13 ?t┝┥f, ?f┝┥t
E14 A∧B→C┝┥A→(B→C)
E15 A∨B→C┝┥(A→C)∧(B→C)
E16 A→B┝┥?B→?A
E17 (A→B)∧(A→?B)┝┥?A
E18 A? B┝┥(A∧B)∨(?A∧?B)
定义1.5当命题公式A→B为永真式时,称A逻辑蕴涵B,记为A┝ B,它又称为逻辑蕴涵式(logically implication)。
一些十分重要的逻辑蕴涵式:
I1 A┝ A∨B,B┝ A∨B
I2 A∧B┝ A,A∧B┝ B
I3 B┝A→B
I4 A∧(A→B)┝ B
I5 (A→B)∧?B┝?A
I6 ?A∧(A∨B)┝ B,?B∧(A∨B)┝ A
I7 (A→B)∧(B→C)┝A→C
I8 (A→B)∧(C→D)┝ (A∧C)→(B∧D)
I9 (A?B)∧(B?C)┝ A?C
I10 A┝ t ; f┝ A
逻辑等价式与逻辑蕴涵式有如下明显性质。
定理1.1对任意命题公式A,B,C,A',B',
(1)A┝┥B当且仅当┝ A?B
(2)A┝ B当且仅当┝ A→B
(3)若A┝┥B,则B┝┥A
(4)若A┝┥B,B┝┥C,则A┝┥C
(5)若A┝ B,则┐B┝ ┐A
(6)若A┝ B,B┝ C,则A┝ C
(7)若A┝ B,A┝┥A',B┝┥B',则A'┝ B'
定理1.2设A为永真式,p为A中命题变元,A(B/p)表示将A中p的所有出现全部代换为公式B后所得的命题公式(称为A的一个代入实例),那么A(B/p)亦为永真式。
定理1.2常被称为代入原理(rule of substitution),简记为RS
定理1.3设A为一命题公式,C为A的子公式,且C┝┥D。若将A中子公式C的某些(未必全部)出现替换为D后得到的公式记为B,那么A┝┥B。
定理1.3常被称为替换原理(rule of replacement)简记为RR。
请注意RS与RR的区别,详见表1.15。
表1.15
代入原理 RS 替换原理 RR 使用对象任意永真式任一命题公式
被代换对象任一命题变元任一子公式
代换对象任一命题公式任一与代换对象等价的命题公式
代换方式代换同一命题变元的所有出现代换子公式的某些出现
代换结果仍为永真式与原公式等价当然,证明逻辑蕴涵式A┝ B不成立的方法只有一个,那就是:找出一个指派使得A为真,却使 B为假。证明逻辑等价式A┝┥B不成立的方法是:证明A┝ B不成立或者证明B┝A不成立。推而广之,为证Γ┝ B(Γ为公式集合)不成立,只要找出一个指派使得Γ中所有公式为真,却使B为假。
1.2.3 对偶原理
定义1.6设公式A仅含联结词?,∧,∨,A*为将A中符号∧,∨,t,f分别改换为∨,∧,f,t后所得的公式,那么称A*为A的对偶(dual)。
下面两定理所描述的事实常称为对偶原理。
定理1.4 设公式A中仅含命题变元p1,…,p n,及联结词?,∧,∨,那么
A┝┥?A* (?p1/p1,…,?p n/p n)
这里,A* (?p1/p1,…,?p n/p n)表示在A*中对p1,…,p n分别作代入?p1,…, ?p n后所得的公式。
定理1.5设A,B为仅含联结词?,∧,∨和命题变元p1,…,p n的命题公式,且满足A┝B,
那么有B*┝ A*。进而当A┝┥B时有A*┝┥B*。
定义1.7 B*┝ A*,A*┝┥B*分别称为A┝ B和A┝┥B的对偶式。
1.2.4 应用逻辑
命题逻辑的相关知识,特别是逻辑等价式和逻辑蕴含式所反映的逻辑思维规律,如,排中律、矛盾律、双重否定律、德摩根律等,是人们逻辑推理的基础,在逻辑训练和实际生活中有十分广泛的应用。
练习1.2题解
1.选择题
(1)K是重言式,那么K的否定是()
A.重言式
B.矛盾式
C.可满足式
D. 不能确定
【答案】:B
(2)K不是重言式,那么它是()
A.永假式
B.矛盾式
C.可满足式
D.不能确定
【答案】:C
(3)命题公式(P∧(P→Q)) →Q是()
A.矛盾式 B. 可满足式 C. 重言式 D. 不能确定
【答案】:C
(4)命题公式(P∧( P∨Q)) ∧Q是()
A.矛盾式 B. 可满足式 C. 重言式 D. 不能确定
【答案】:B
(5)如果P→Q为真时我们称命题P强于Q,那么最强的命题是(),最弱的命题是()。
A.永假式 B. 可满足式 C. 永真式 D. 不能确定
【答案】:A,C
2.填空题
(1)两个重言式的析取是,一个重言式与一个矛盾式的析取是。两个重言式的合取是,一个重言式与一个矛盾式的合取是。一个重言式蕴涵一个矛盾式的是,一个矛盾式蕴涵一个重言式的是。【答案】:重言式,重言式,重言式,矛盾式,矛盾式,重言式
(2)在下列各式中,是永真式的有。
(a)(P∧(P→Q)) →Q
(b)P→(P∨Q)
(c)Q→(P∧Q)
(d)(﹁P∧(P∨Q))→Q
(e)(P→Q)→Q
【答案】:(a),(b),(d)
(3)化简下列各式:
(a)(﹁P∧Q) ∨(﹁P∧﹁Q)可化简为。
(b)Q→(P∨(P∧Q))可化简为。
(c)((﹁P∨Q)?(Q∨﹁P))∧P可化简为。
【答案】:(a)﹁P;(b)Q→P;(c)P
(4)公式(P∨Q)→R的只含联结词?,∧的等价式为,它的对偶式为。【答案】:?(?(?P∧?Q)∧?R);?(P∧Q) ∧R
3.试判定以下各式是否为重言式:
(1)(p→q)→(q→p)
【答案】:否
(2)﹁p→(p→q)
【答案】:是
(3)q→(p→q)
【答案】:是
(4)p∧q→(p?q)
【答案】:是
(5)(p→q)∨(r→q)→((p∨r)→q)
【答案】:否
(6)(p→q)∨(r→s)→((p∨r)→(q∨s))
【答案】:否
4.试用真值表验证E6,E8,E15,E17。
(1)【答案】: E 6 ﹁(A∨B)┝┥﹁A∧﹁B 的真值表如表1.16所示:
表1.16
﹁(A∧B)┝┥﹁A∨﹁B 的真值表如表1.17所示:
表1.17
(2)【答案】: E 8 A→B┝┥﹁A∨B的真值表如表1.18所示:
表1.18
(3)【答案】:E 15 A∨B→C┝┥(A→C)∧(B→C) 的真值表如表1.19所示:
表
1.19
(4)【答案】:E17(A→B)∧(A→?B)┝┥?A的真值表如表1.20所示:
表1.20
5.不用真值表,用代入、替换原理证明E16,E17。
(1)E16A→B┝┥?B→?A
【答案】:A→B┝┥﹁A∨B 据E8
┝┥﹁A∨﹁ (﹁B) 据E1用RR
┝┥?B→?A 对E8用RS
(2)E17 (A→B)∧(A→﹁B)┝┥﹁A
【答案】:(A→B)∧(A→﹁B)┝┥(﹁A∨B) ∧(﹁A∨﹁B) 据E8用RR
┝┥﹁A∨ (B∧﹁B) 对E5用RS
┝┥﹁A∨f 据E12用RR
┝┥﹁A 据E11用RS
6.试用真值表验证I3,I4,I6,I7。
(1)【答案】: I3 B┝A→B的真值表如表1.21所示:
表1.21
(2)【答案】:I4 A∧(A→B)┝B的真值表如表1.22所示:
表1.22
(3)【答案】:I6 ﹁A∧(A∨B)┝B 的真值表如表1.23所示:
表1.23
﹁B∧(A∨B)┝A的真值表如表1.24所示:
表1.24
(4)【答案】:I7 (A→B) ∧(B→C) ┝(A→C) 的真值表如表1.25所示:
表1.25
7.不用真值表,用代入、替换原理证明I8,I9 。
【答案】:(1)I8:(A→B)∧(C→D)┝ (A∧C)→(B∧D)
证(A→B)∧(C→D) ∧(A∧C) ┝┥(﹁A∨B)∧(﹁C∨D) ∧(A∧C)
┝┥(﹁A∧﹁C∧A∧C) ∨(B∧﹁C∧A∧C) ∨(﹁A∧D∧A∧C) ∨(B∧D∧A∧C)
┝┥f∨f∨f∨(A∧B∧C∧D)
┝┥A∧B∧C∧D
┝B∧D
因此,(A→B)∧(C→D) ∧(A∧C) →(B∧D)为一重言式
又(A→B)∧(C→D) ∧(A∧C) →(B∧D) ┝┥(A→B)∧(C→D) →((A∧C) →(B∧D)) 所以(A→B)∧(C→D) →((A∧C) →(B∧D)) 为一重言式
即(A→B)∧(C→D)┝ (A∧C)→(B∧D)
【答案】:(2)I9:(A?B)∧(B?C)┝ (A?C)
证 (A?B)∧(B?C)∧A ┝┥(A→B)∧(B→A)∧(B→C)∧(C→B)∧A
┝(A→B)∧(B→C)∧A
┝┥(﹁A∨B) ∧(﹁B∨C) ∧A
┝┥(﹁A∧﹁B∧A) ∨(﹁A∧C∧A) ∨(B∧﹁B∧A) ∨(B∧C∧A)
┝┥f∨f∨f∨(A∧B∧C)
┝┥A∧B∧C
┝ C
因此,(A?B)∧(B?C)∧A →C为一重言式
又(A?B)∧(B?C)∧A →C ┝┥(A?B)∧(B?C)→(A →C)
所以(A?B)∧(B?C)→(A →C) 为一重言式
仿上可证(A?B)∧(B?C)→(C →A) 为一重言式
又根据(1),((A?B)∧(B?C)→(A →C)) ∧((A?B)∧(B?C)→(C →A)) ┝(A?B)∧(B?C) →(A →C) ∧(C →A)
┝┥(A?B)∧(B?C) →(A?C)
所以(A?B)∧(B?C) →(A?C)也是重言式,
即(A?B)∧(B?C)┝ (A?C)
8.用三种不同方法证明下列逻辑等价式和逻辑蕴涵式:
(1)A?B┝┥(A∧B)∨(﹁A∧﹁B)
【答案】证法1:真值表(表1.26)的最后两列等值,故A?B┝┥(A∧B)∨(﹁A∧﹁B)
表1.26
证法2:A?B┝┥(A→B)∧(B→A)
┝┥(﹁A∨B)∧(﹁B∨A)
┝┥(﹁A∧﹁B)∨(﹁A∧A)∨(B∧﹁B)∨(B∧A)
┝┥(A∧B)∨(﹁A∧﹁B)
证法3:先证A?B┝ (A∧B)∨(﹁A∧﹁B) (a)
设α为任一指派,使(A?B)=1,那么α (A)= α (B)=1或α(A)= α (B)=0,从而α(A∧B)=1或α (﹁A∧﹁B)=1,即α((A∧B)∨(﹁A∧﹁B))=1。(a)得证;
再证(A∧B)∨(﹁A∧﹁B)┝ A?B (b)
设α为任一指派,使α (A?B)=0,那么α (A)=1,α(B)=0,或者α(A)=0,α(B)=1,从而α(A∧B)=0且α (﹁A∧﹁B)=0,即α((A∧B)∨(﹁A∧﹁B))=0。(b)得证。
(2)A→(B→C)┝┥B→(A→C)
【答案】证法1:真值表(表1.27)的最后两列等值,故A→(B→C)┝┥B→(A→C)
表1.27
证法2:A→(B→C)┝┥﹁A∨(﹁B∨C)
┝┥(﹁A∨﹁B)∨C
┝┥(﹁B∨﹁A)∨C
┝┥﹁B∨(﹁A∨C)
┝┥B→(A→C)
证法3:先证A→(B→C)┝ B→(A→C) (a)
设α为任一指派,使α(A→(B→C))=1,那么
ⅰ)α (A)= 0,则α( A→C)=1,从而α( B→(A→C))=1
ⅱ)α (A)= 1,α (B)=0,则α( B→(A→C))=1
ⅲ)α (A)= α (B)=α (C)=1,则α( B→(A→C))=1综上,(a)得证;同理可证B→(A→C)┝ A→(B→C)。
(3)A→(A→B)┝┥A→B
【答案】证法1:真值表(表1.28)的最后两列等值,故A→(A→B)┝┥A→B
表1.28
证法2:A→(A→B)┝┥A∧A→B
┝┥A→B
证法3:先证A→(A→B)┝ A→B (a)
设α为任一指派,使α( A→B)=0,那么α (A)=1,α(B)=0,从而
α( A→(A→B))=0。(a)得证;
再证A→B┝ A→(A→B) (b)
设α为任一指派,使α(A→(A→B))=0,那么α (A)=1,α(A→B)=0。(b)得证。
(4)A→(B→C)┝┥(A→B)→(A→C)
【答案】证法1:真值表(表1.29)的最后两列等值,故A→(B→C)┝┥(A→B)→(A→C)
表1.29
证法2:(A→B)→(A→C)┝┥﹁(﹁A∨B) ∨ (﹁A∨C)
┝┥(A∧﹁B) ∨ (﹁A∨C)
┝┥( (A∧﹁B)∨﹁A)∨C
┝┥((A∨﹁A)∧(﹁B∨﹁A) )∨C
┝┥(t∧(﹁A∨﹁B) )∨C
┝┥(﹁A∨﹁B)∨C
┝┥﹁A∨(﹁B∨C)
┝┥A→(B→C)
证法3:先证A→(B→C)┝ (A→B)→(A→C) (a)
设α为任一指派,使α((A→B)→(A→C))=0,那么α( A→B)=1,
α(A→C)=0,即α(A)=α(B)=1,α(C)=0,从而α(B→C)=0,
第2章 逻辑代数基础 2.1 明下列异或运算公式。 (7)1A B A B A B ⊕= ⊕=⊕⊕ 2.2 用逻辑代数的基本公式和定律将下列逻辑函数式化简为最简与-或表达式。 (4) Y AB BD DCE AD =+++ =D(A+B)+AB+DCE =DAB+AB+DCE =D+AB+DCE =D+AB (6) ()()Y A B CD A CD AC A D =++++ ()CD A B A ACD CD ACD CD C D +++=+==+ = (9) ()()()Y A C BD A BD B C DE BC =+++++()()A BD AC B C C DE ABD B B =++++=+= (10) ()Y AC BC BD A B C ABCD ABDE =++++++ ()(1)A C B C BDE BC BD A C A BC BD ++++++++= = 2.3 证明下列恒等式(证明方法不限)。
()()()A B C A B C A B C A BC A B C A B C A BC A B C A BC A B C ⊕⊕=⊕⊕⊕+⊕+⊕+= (6)解:左式= = = = =右式 结果与等式右边相恒等,证毕。 (10)()()BC D D B C AD B B D ++++=+ ()()BC D D BC AD B BC D AD B B D =++?+=+++=+ 2.4 根据对偶规则求出下列逻辑函数的对偶式。 (2) ()()Y A B C AB C D ABC D =+++++ 解:'()[()]()Y A BC A B CD A B C D =+++++ (3) Y AB BC CA =++ 解:'()()()Y A B B C C A =+++ 2.5 根据反演规则,求出下列逻辑函数的反函数。 (2) [()]Y A BC CD E F =++ 解:[()()]Y A B C C D E F =++++ (3) Y A B CD C D AB =+++++ 解:()()Y AB C D CD A B =++ 2.6 将下列逻辑函数变换为最小项之和的表达式: (4) ()Y A B C A B C =+++++
第一章逻辑代数基础 一、简答题: 1、什么叫做算术运算,什么叫做逻辑运算? 答:当两个二进制数码表示数量大小时,它们之间进行的数值运算,称之为算术运算; 当两个二进制数码表示不同的逻辑状态时,它们之间可以按照指定的某种因果关系进行的运算,称之为逻辑运算。 2 逻辑代数中三种最基本的逻辑运算是什么?各遵循什么运算关系? 答:分别为与运算、或运算和非运算。 与逻辑的定义:仅当决定事件(Y)发生的所有条件(A,B,C,…)均满足 时,事件(Y)才能发生。表达式为:Y=ABC…… 或逻辑的定义:当决定事件(Y)发生的各种条件(A,B,C,…)中,只要 有一个或多个条件具备,事件(Y)就发生。表达式为: Y=A+B+C+…… 非逻辑:决定事件发生的条件只有一个,条件不具备时事件发生(成立),条 件具备时事件不发生。表达式为:A Y 3 逻辑函数的五种表示方法是什么?各有什么特点? 答:分别为真值表、逻辑表达式、卡诺图、逻辑图、波形图。 4 什么叫最小项?最小项有什么性质? 答:定义:对于n个变量,如果P是一个含有n个因子的乘积项,而且每一个变量都以原变量或者反变量的形式,作为一个因子在P中出现且仅出现一次,那么就 称P是这n个变量的一个最小项。 性质:(1)每一个最小项都有一组也只有一组使其值为1的对应变量取值; (2)任意两个不同的最小项之积恒为0; (3)全部最小项之和恒为1。
5 卡诺图 中合并最小项的规则是什么? 答:合并逻辑相邻项。 (1)相邻单元的个数是2n 个,并组成矩形时,可以合并。 (2)卡诺圈尽可能大:利用吸收规则, 2n 个相邻单元合并,可吸收掉n 个变量。 (3)不要圈出多余圈:各最小项可以重复使用,但每一次新的组合,至少包含一个 未使用过的项,直到所有为1的项都被使用后化简工作方算完成。 (4)注意边沿和四角。 (5)如果是具有约束的逻辑函数,要注意利用约束项,可以使结果大大简化。 二、化简逻辑函数 1、将下列逻辑表达式化成最简与-或式。 (1)B AD CD B A Y ?+++= (2)A D DCE B D B A Y +++= (3)C B C A C B C A Y +++= (4)B)CD A (B A Y ++= 解:(1)B AD CD B A Y ?+++= B A B C D )(B AD)(A B AD BCD A +=+++=+++= (2)A D DCE B D B A Y +++= DCE )A D(B B A +++= DCE A B D B A ++= (摩根定理) DCE D B A ++=D B A += (吸收定理) (3)C B C A C B C A Y +++=
第8章 §8.5 逻辑代数公式化简习题2 1 第8章 §8.5 逻辑代数公式化简习题2 (一)考核内容 1、第8章掌握逻辑运算和逻辑门;掌握复合逻辑运算和复合逻辑门;掌握逻辑函数的表示方法;掌握逻辑代数的基本定理和常用公式;掌握逻辑函数的化简方法。 8.6 逻辑函数的化简 8.6. 1 化简的意义 1、所谓化简就是使逻辑函数中所包含的乘积项最少,而且每个乘积项所包含的变量因子最少,从而得到逻辑函数的最简与–或逻辑表达式。 逻辑函数化简通常有以下两种方法: (1)公式化简法 又称代数法,利用逻辑代数公式进行化简。它可以化简任意逻辑函数,但取决于经验、技巧、洞察力和对公式的熟练程度。 (2)卡诺图法 又称图解法。卡诺图化简比较直观、方便,但对于5变量以上的逻辑函数就失去直观性。 2、逻辑函数的最简形式 同一逻辑关系的逻辑函数不是唯一的,它可以有几种不同表达式,异或、与或、与或非—非、与非—与非、或与非、与或非、或非—或非。 一个逻辑函数的表达式可以有与或表达式、或与表达式、与非-与非表达式、或非-或非表达式、与或非表达式5种表示形式。 (1)与或表达式:AC B A Y += (2)或与表达式:Y ))((C A B A ++= (3)与非-与非表达式:Y AC B ?= (4)或非-或非表达式:Y C A B A +++= (5)与或非表达式:Y C A B A += 3、公式化简法 (1)、并项法:利用公式A B A AB =+,把两个乘积项合并起来,消去一个变量。 例题1: B B A A B =+= (2)、吸收法:利用公式 A A B A =+,吸收掉多余的乘积项。 例题2:E B D A AB Y ++= B A E B D A B A +=+++= (3)、消去法:利用公式B A B A A +=+,消去乘积项中多余的因子。 例题3:AC AB Y += C B A A C B A ++=++= (4)、配项消项法:利用公式C A AB BC C A AB +=++,在函数与或表达式中加上多余的项— —冗余项,以消去更多的乘积项,从而获得最简与或式。 例题4: B A C AB ABC Y ++=
第1章 逻辑代数基础 1. 用真值表证明下列等式。 (1) (A B)C=A (B C)⊕⊕⊕⊕ (2) C B A C B A A +=++ (1) A+ABC+ABC+CB+CB ( C A B B C BC BC A +=++++=) ()1( 2) ABC+ABC+ABC+ABC A AB B A C C AB C C B A =+=+++=) ()( 3.将下列各函数化为最小项之和的形式。 (1) Y=ABC+BC+AB 7 543)()(m m m m C B A C B A BC A ABC BC A C C B A A A BC BC A +++=++++=++++= (2) )( AB Y D C B C ABD +++=
D C AB D C B D C AB D C B C D B D A D C B C AD B BD A D C B C ABD B A =+=+++++=+++++=++++=)() () ()( 4.根据下列各逻辑式, 画出逻辑图。 ①Y=(A+B )C ; ②Y=AB+BC ; ③Y=(A+B )(A+C ); 5.试对应输入波形画出下图中 Y 1 ~ Y 4 的波形。 6.如果“与”门的两个输入端中, A 为信号输入端, B 为控制端。 设当控制端B=1和B=0两种状态时,输入信号端A 的波形如图所示, 试画出输出端Y 的波形。 如果A 和B 分别是“与非”门、“或”门、“或非”门的两个输入端,则输出端Y 的波形又如何?总结上
述四种门电路的控制作用。
第2章 组合逻辑电路 1.分析图示电路的逻辑功能。要求写出逻辑式,列出真值表,然后说明逻辑功能。 AB Y B A B A Y =+=21 半加器 真值表略 2.已知逻辑式B A AB Y +=: ①列出逻辑真值表,说明其逻辑功能; ②画出用“与非”门实现其逻辑功能的逻辑图; ③画出用双2/4线译码器74LS139实现其逻辑功能的逻辑图; ④画出用4选1数据选择器74LS153实现其逻辑功能的逻辑图; ③双2/4线译码器74LS139 有两个2-4线译码器 ④用4选1数据选择器74LS153
第一章逻辑代数基础 一、内容提要 逻辑代数是数字电子技术的基础。本章主要介绍逻辑代数中的数制转换、逻辑运算、基本定理和基本规则、逻辑函数及其表示方法、逻辑函数的变换与化简。 二、重点难点 本章的重点内容包括以下四个方面: 1、数制转换与码制的表达方式:掌握二进制、十进制及其相互转换方法; 掌握8421 BCD码、2421 BCD码、余3码和余3循环码的编码方法;掌握格雷码的编码规律、格雷码与二进制相互转换方法。 2、逻辑代数中的三种基本运算和基本定理:掌握逻辑代数中与、或、非三种基本运算;逻辑代数基本公式;代入规则、反演规则、对偶规则三个规则。 3、逻辑函数的表示方法及相互转换:掌握真值表、逻辑表达式、逻辑图、卡诺图、波形图等常用的逻辑函数表示方法和几种表示方法之间的相互转换;掌握逻辑函数的两种标准形式。 4、逻辑函数的公式法化简方法和卡诺图化简方法:逻辑函数表达式越简单,所表示的逻辑关系越明显,越有利于用最少的电子器件实现该逻辑关系,电路的可靠性越高。常用的化简方法有公式法和卡诺图法。 三、习题精解 知识点:数制转换 例1.1 将二进制数111011.101转换成十进制数。 解:10 3 1 1 3 4 5 2 ) 625 . 59 ( 125 .0 5.0 1 8 16 32 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ) 101 . 111011 ( = + + + + + = ? + ? + ? + ? + ? + ? + ? =- - 例1.2将十进制数65转换为二进制数。 解:整数部分用“辗转相除”法:
所以 D B (65)=(1000001) 例1.3 将十进制数0.625转换为二进制数。 解:乘 2 法;将十进制数的小数部分乘2,取其整数得D -1, ;再将小数部分乘2,取其整数得D -2 ;再将小数部分乘2… 所以 D B (0.625)=(0.101) 知识点:逻辑代数基本规则应用 例1.4 已知0++?=CD B A F ,求F 。 解:用反演规则得:1))((?++=D C B A F 用反演律得))((D C B A CD B A CD B A F ++=??=+?= 例1.5 已知 ) )((C A B A F ++=,求F 的对偶式。 解:用对偶规则得:AC B A F +=' 例1.6 求函数)]([G E D C B A F ?+?+?=的反函数。 解:
第一章:逻辑代数基础 一、单选题: 1: 逻辑函数B A F ⊕= 和 G=A ⊙B 满足关系( )相等。 A. G F = B. G F =' C. G F = D. G F = 2: 下列逻辑门类型中,可以用( )一种类型门实现另三种基本运算。 A .与门 B .非门 C .或门 D .与非门 3:下列各门电路符号中,不属于基本门电路的是 ( ) 图2201 4:逻辑函数)(AB A F ⊕=,欲使1=F ,则AB 取值为( ) A .00 B .01 C .10 D .11 5:已知逻辑函数的真值表如下,其表达式是( ) A .C Y = B .AB C Y = C .C AB Y += D .C AB Y += 图2202 6:已知逻辑函数 CD ABC Y +=,可以肯定Y = 0的是 ( ) A . A = 0,BC = 1; B . B C = 1, D = 1; C . AB = 1,CD =0; D . C = 1,D = 0。 7:能使下图输出 Y = 1 的 A ,B 取值有( ) A .1 种; B . 2 种; C .3 种; D .4 种
图2203 8:下图电路,正确的输出逻辑表达式是( )。 A . CD A B Y += B . 1=Y C . 0=Y D . D C B A Y +++= 图2204 9:根据反演规则,E DE C C A Y ++?+=)()(的反函数为( ) A. E E D C C A Y ?++=)]([ B. E E D C C A Y ?++=)( C. E E D C C A Y ?++=)( D. E E D C C A Y ?++=)( 10:若已知AC AB C A B A =+=+,,则( ) A . B=C = 0 B . B= C =1 C . B=C D . B ≠C 11:在什么情况下,“与非”运算的结果是逻辑0。 ( ) A .全部输入是0 B. 任一个输入是0 C. 仅一个输入是0 D. 全部输入是1 12:逻辑函数=⊕⊕=)(B A A F ( ) A . B B .A C .B A ⊕ D . B A ⊕ 13:逻辑式=?+?+A A A 10 ( ) A . 0 B . 1 C . A D .A 14:逻辑函数ACDEF C AB A Y +++=的最简与或式为( )
逻辑代数的基本公式和常用公式 一.基本定义与运算 代数是以字母代替数,称因变量为自变量的函数,函数有定义域和值域。——这些都是大家耳熟能详的概念。如 或; 当自变量的取值(定义域)只有0和1(非0即1)函数的取值也只有0和1(非0即1)两个数——这种代数就是逻辑代数,这种变量就是逻辑变量,这种函数就是逻辑函数。 逻辑代数,亦称布尔代数,是英国数学家乔治布尔(George Boole)于1849年创立的。在当时,这种代数纯粹是一种数学游戏,自然没有物理意义,也没有现实意义。在其诞生100多年后才发现其应用和价值。其规定: 1.所有可能出现的数只有0和1两个。 2.基本运算只有“与”、“或”、“非”三种。 与运算(逻辑与、逻辑乘)定义为(为与运算符,后用代替) 00=0 01=0 10=0 11=1 或 00=0 01=0 10=0 11=1 或运算(逻辑或、逻辑加)定义为(为或运算符,后用+代替) 00=0 01=1 10=1 11=1 或 0+0=0 0+1=1 1+0=1 1+1=1 非运算(取反)定义为:
至此布尔代数宣告诞生。 二、基本公式 如果用字母来代替数(字母的取值非0即1),根据布尔定义的三种基本运算,我们马上可推出下列基本公式: A A=A A+A=A A0=0 A+0=A A1=A A+1=1 =+= 上述公式的证明可用穷举法。如果对字母变量所有可能的取值,等式两边始终相等,该公 式即告成立。现以=+为例进行证明。对A、B两个逻辑变量,其所有可能的取值为00、01、10、11四种(不可能有第五种情况)列表如下:
由此可知: =+ 成立。 用上述方法读者很容易证明: 三、常用公式 1. 左边==右边 2. 左边==右边 例题:将下列函数化为最简与或表达式。 (公式1:) = (公式2:) ()
第一章数字逻辑基础 第一节重点与难点 一、重点: 1.数制 2.编码 (1)二—十进制码( BCD 码) 在这种编码中,用四位二进制数表示十进制数中的 0~9 十个数码。常用的编码有 8421BCD 码、 5421BCD 码和余 3 码。 8421BCD 码是由四位二进制数0000 到 1111 十六种组合中前十种组合,即0000~1001 来代表十进制数0~9 十个数码,每位二进制码具有固定的权值8、 4、 2、1,称有权码。 余 3 码是由 8421BCD 码加 3( 0011)得来,是一种无权码。 (2)格雷码 格雷码是一种常见的无权码。这种码的特点是相邻的两个码组之间仅有一位不同,因而 其可靠性较高,广泛应用于计数和数字系统的输入、输出等场合。 3.逻辑代数基础 (1)逻辑代数的基本公式与基本规则 逻辑代数的基本公式反映了二值逻辑的基本思想,是逻辑运算的重要工 具,也是学习数字电路的必备基础。 逻辑代数有三个基本规则,利用代入规则、反演规则和对偶规则使逻辑函 数的公式数目倍增。 (2)逻辑问题的描述 逻辑问题的描述可用真值表、函数式、逻辑图、卡诺图和时序图,它们各具特点又相互关联,可按需选用。 (3)图形法化简逻辑函数 图形法比较适合于具有三、四变量的逻辑函数 的简化。二、难点: 1.给定逻辑函数,将逻辑函数化为最简 用代数法化简逻辑函数,要求熟练掌握逻辑代数的基本公式和规则,熟练运 用四个基本方法—并项法、消项法、消元法及配项法对逻辑函数进行化简。 用图形法化简逻辑函数时,一定要注意卡诺图的循环邻接的特点,画 包围圈时应把每个包围圈尽可能画大。 2.卡诺图的灵活应用 卡诺图除用于简化函数外,还可以用来检验化简结果是否最简、判断函数间的关系、 求函数的反函数和逻辑运算等。 3.电路的设计 在工程实际中,往往给出逻辑命题,如何正确分析命题,设计出逻辑电路 呢?通常的步骤如下:
逻辑代数基础 一、选择题(多项选择) 1. 以下表达式中符合逻辑运算法则的是 。 ·C =C 2 +1=10 C.0<1 +1=1 2. 逻辑变量的取值1和0可以表示: 。 A.开关的闭合、断开 B.电位的高、低 C.真与假 D.电流的有、无 3. 当逻辑函数有n 个变量时,共有 个变量取值组合 A. n B. 2n C. n 2 D. 2n 4. 逻辑函数的表示方法中具有唯一性的是 。 A .真值表 B.表达式 C.逻辑图 D.卡诺图 =A B +BD+CDE+A D= 。(加一个盈余项AD ) A.D B A + B.D B A )(+ C.))((D B D A ++ D.))((D B D A ++ 6.逻辑函数F=)(B A A ⊕⊕ = 。 C.B A ⊕ D. B A ⊕ 7.求一个逻辑函数F 的对偶式,可将F 中的 。 A .“·”换成“+”,“+”换成“·” B.原变量换成反变量,反变量换成原变量 C.变量不变 D.常数中“0”换成“1”,“1”换成“0” E.常数不变 8.A+BC= 。 A .A + B + C C.(A +B )(A +C ) +C 9.在何种输入情况下,“与非”运算的结果是逻辑0。 D A .全部输入是0 B.任一输入是0 C.仅一输入是0 D.全部输入是1 10.在何种输入情况下,“或非”运算的结果是逻辑0。 A .全部输入是0 B.全部输入是1 C.任一输入为0,其他输入为1 D.任一输入为1 二、判断题(正确打√,错误的打×) 1. 逻辑变量的取值,1比0大。( × )。 2. 异或函数与同或函数在逻辑上互为反函数。( √ )。 3.若两个函数具有相同的真值表,则两个逻辑函数必然相等。( × )。
第二章 逻辑代数基础(选择、判断共20题) 一、选择题 1. 以下表达式中符合逻辑运算法则的是 。 A.C ·C =C 2 B.1+1=10 C.0<1 D.A +1=1 2. 逻辑变量的取值1和0可以表示: 。 A.开关的闭合、断开 B.电位的高、低 C.真与假 D.电流的有、无 3. 当逻辑函数有n 个变量时,共有 个变量取值组合? A. n B. 2n C. n 2 D. 2n 4. 逻辑函数的表示方法中具有唯一性的是 。 A .真值表 B.表达式 C.逻辑图 D.卡诺图 5.F=A B +BD+CDE+A D= 。 A.D B A + B.D B A )(+ C.))((D B D A ++ D.))((D B D A ++ 6.逻辑函数F=)(B A A ⊕⊕ = 。 A.B B.A C.B A ⊕ D. B A ⊕ 7.求一个逻辑函数F 的对偶式,可将F 中的 。 A .“·”换成“+”,“+”换成“·” B.原变量换成反变量,反变量换成原变量 C.变量不变 D.常数中“0”换成“1”,“1”换成“0” E.常数不变 8.A+BC= 。 A .A + B B.A + C C.(A +B )(A +C ) D.B +C 9.在何种输入情况下,“与非”运算的结果是逻辑0。 A .全部输入是0 B.任一输入是0 C.仅一输入是0 D.全部输入是1 10.在何种输入情况下,“或非”运算的结果是逻辑0。 A .全部输入是0 B.全部输入是1 C.任一输入为0,其他输入为1 D.任一输入为1 二、判断题(正确打√,错误的打×) 1. 逻辑变量的取值,1比0大。( )。 2. 异或函数与同或函数在逻辑上互为反函数。( )。
复习思考题 1-1 离散信号就是数字信号吗? 答:离散信号不一定是数字信号,如对连续信号在时间上进行采样,成为时间上离散、幅度上连续的信号就不是数字信号。 1-2 模拟信号转换成数字信号有哪些基本环节?数字系统比模拟系统有哪些优越性? 答:模拟信号转换成数字信号包括采样、保持、量化、编码等基本环节。与模拟电路相比,数字电路具有以下显著的优点: 1)数字电路的基本工作信号是用1和0表示的二进制的数字信号,反映在电路上就是高电平和低电平,运算简单。 2)结构简单、设计技术成熟、容易制造,便于集成及系列化生产,通用性强,价格便宜。 3)数字电路能对输入的数字信号进行各种算术运算和逻辑运算、逻辑判断,具有“逻辑思维”能力。 4)可编程数字系统,使用更灵活。 5)速度快,抗干扰性强,可靠性高。 6)易于存储、加密、压缩、传输和再现,便于和计算机连接。 1-3 为什么数字电路采用二进制作为其基本工作信号? 答:数字电路采用二进制作为其基本工作信号,主要原因是: 1)技术实现容易。二进制信号只有1和0两种信号,反映在电路上就是高电平和低电平,在电路上很容易由电子器件的开关特性实现。 2)运算规则简单。二进制的数值运算规则简单,在实现上可以简化电路结构、提高系统的运行速度。 3)与逻辑运算吻合。数字电路中采用1和0表示高低电平的方式和逻辑运算的数学方法—布尔代数,采用1和0表示不同的逻辑状态不谋而合,一方面可以将布尔代数广泛应用于开关电路和数字电路的设计中,设计方法简单;另一方面,可以由数字电路实现逻辑运算,而采用其它进制是很难实现的。 1-4 逻辑函数有哪两种标准表达式? 答:逻辑函数有与-或表达式(最小项和的形式)和或-与表达式(最大项积的形式)两种标准表达式。 1-5 何为最小项?简述其编号方法。 答:设m为包含n个变量的乘积项,且这n个变量以原变量形式或者反变量形式在m中出现且只出现一次,称m为n变量的一个最小项。最小项的编号规则:把最小项m中的原变量取值为1 ,反变量取值为0,所构成二进制数对应的十进制数即为该最小项的编号i,记作m i。 1-6 什么是真值表?如何得到一个逻辑函数的真值表? 答:所谓真值表是指描述逻辑关系的图表。将输入变量所有可能组合的逻辑函数的值依序对应列于一张二维表中,即可得到该逻辑函数的真值表。 1-7 与、或、非三种基本逻辑运算可以实现其它任何复杂的逻辑函数吗?
第二章逻辑代数基础 [题] 选择题 以下表达式中符合逻辑运算法则的是。 ·C=C2+1=10 C.0<1 +1=1 2. 逻辑变量的取值1和0可以表示:。 A.开关的闭合、断开 B.电位的高、低 C.真与假 D.电流的有、无 3. 当逻辑函数有n个变量时,共有个变量取值组合。 A. n B. 2n C. n2 D. 2n 4. 逻辑函数的表示方法中具有唯一性的是。 A .真值表 B.表达式 C.逻辑图 D.卡诺图 5.在输入情况下,“与非”运算的结果是逻辑0。 A.全部输入是0 B.任一输入是0 C.仅一输入是0 D.全部输入是1 6.在输入情况下,“或非”运算的结果是逻辑0。 A.全部输入是0 B.全部输入是1 C.任一输入为0,其他输入为1 D.任一输入为1 7.求一个逻辑函数F的对偶式,可将F中的。 A .“·”换成“+”,“+”换成“·” B.原变量换成反变量,反变量换成原变量 C.变量不变 D.常数中“0”换成“1”,“1”换成“0” E.常数不变 8. 在同一逻辑函数式中,下标号相同的最小项和最大项是 关系。 A.互补 B.相等 C.没有关系 9. F=A +BD+CDE+ D= 。 A. A B. A+D C. D D. A+BD 10.A+BC= 。 A .A+ B + C C.(A+B)(A+C) +C 11.逻辑函数F== 。 C. D. [题]判断题(正确打√,错误的打×) 1.逻辑变量的取值,1比0大。() 2.异或函数与同或函数在逻辑上互为反函数。()3.若两个函数具有相同的真值表,则两个逻辑函数必然相等。()
4.因为逻辑表达式A+B+AB=A+B成立,所以AB=0成立。()5.若两个函数具有不同的真值表,则两个逻辑函数必然不相等。()6.若两个函数具有不同的逻辑函数式,则两个逻辑函数必然不相等。()7.逻辑函数两次求反则还原,逻辑函数的对偶式再作对偶变换也还原为它本 身。 ( )8.逻辑函数Y=A + B+ C+C 已是最简与或表达式。()9.对逻辑函数Y=A + B+ C+B 利用代入规则,令A=BC代入,得Y= BC + B+ C+B = C+B 成立。() [题] 填空题 1. 逻辑代数又称为代数。最基本的逻辑关系有、、三种。常用的几种导出的逻辑运算为、、、、。 2. 逻辑函数的常用表示方法有、、。 3. 逻辑代数中与普通代数相似的定律有、、。摩根定律又称为。 4. 逻辑代数的三个重要规则是、、。 5.逻辑函数化简的方法主要有化简法和化简法两种。 6.利用卡诺图化简法化简逻辑函数时,两个相邻项合并,消去一个变量,四个相邻项合并,消去个变量等。一般来说,2n 个相邻一方格合并时,可消去个变量。 7. 和统称为无关项。 8.逻辑函数F= B+ D的反函数 = 。 9.逻辑函数F=A(B+C)·1的对偶函数是。 10.添加项公式AB+ C+BC=AB+ C的对偶式为。 11.逻辑函数F=+A+B+C+D= 。 12.逻辑函数F== 。 13.已知函数的对偶式为+,则它的原函数为。 [题] 将下列各函数式化成最小项表达式。 (1) (2) (3) [题] 利用公式法化简下列逻辑函数。 (1)
第二章逻辑代数的基本运算…………………………………………………………… 2.1 逻辑代数 2.1.1 与运算…………………………………………………………………… 2.1.2 或运算…………………………………………………………………… 2.1.3 非运算…………………………………………………………………… 2.1.4 几种常见的复合逻辑关系………………………………………………… 2.2 逻辑函数及其表示方法……………………………………………………… 2.3 逻辑代数的基本定律和恒等式………………………………………………… 2.3.1 逻辑代数的基本定律和恒等式…………………………………………… 2.3.2 逻辑代数的三个规则……………………………………………………… 2.3.3 逻辑函数的代数变换与化简法……………………………………………… 2.4 逻辑函数的卡诺图化简法…………………………………………………… 2.4.1 最小项的定义和性质……………………………………………………… 2.4.2 逻辑函数的卡诺图表达法………………………………………………… 2.4.3 利用卡诺图化简逻辑函数………………………………………………… 本章小结……………………………………………………………………………
第二章逻辑代数的基本运算 本章要点: 基本逻辑关系与逻辑运算 逻辑代数基本定律与基本规则 逻辑函数的表示方法 逻辑函数的变换与化简 2.1 逻辑代数 逻辑代数又称布尔代数,其基本思想是19世纪英国数学家乔治.布尔首先提出的。所谓逻辑就是事物因果之间所遵循的规律。为了避免用冗繁的文字来描述逻辑问题,逻辑代数采用逻辑变量和一套运算符组成逻辑函数表达式来描述食物的因果关系。它是用数学的方法来研究、证明、推理放逻辑问题的一种数学工具。逻辑代数虽然和普通代数一样也是用字母表示变量,但是两种代数中的变量含义是完全不同的,逻辑代数中的每个变量(逻辑变量)只有0和1两种取值。0和1不再表示数量的大小,而是表示对立的两种逻辑状态。例如,电灯的亮与灭、电动机的工作与停止。 在数字电路中,输入的信号是“条件”,输出的信号是“结果”,因此输入、输出信号之间存在一定的因果关系,这种因果关系称为逻辑关系。描述逻辑关系可以用语句、逻辑表达式、图形和表格等来描述,描述逻辑关系的表格又称为真值表。表示逻辑运算所用的规定的图形符号称为逻辑符号。逻辑代数中有三种基本运算:“与”运算、“或”运算和“非”运算。下面就分别讨论这三种基本逻辑运算。 2.1.1 与运算 首先,我们来看一个具体的电路试验,电路图如图2-1所示,电源E通过A、B两个串联的开关给电灯Y供电。 图2-1(a)与逻辑的逻辑电路图(b)与逻辑的电路符号
第2章逻辑代数基础 一、学习目的 逻辑代数是分析和研究数字逻辑电路的基本工具。通过本章的学习要掌握逻辑代数的各种表示 二、内容概要 本章在介绍基本逻辑运算和常用的导出运算后, 三、学习指导 本章重点: 本章难点: 方法提示 2、1概述 理解逻辑值
理解逻辑体制的含义。 逻辑代数又称为布尔代数。它是由英国数学家乔治·布尔于19世纪中叶首先提出并用于描述客观事物逻辑关系的数学方法,后来将其应用于继电器开关电路的分析和设计上,从而形成了二值开关代数。之后便更为广泛地被用于数字逻辑电路和数字系统中,成为逻辑电路分析和设计的有力工具,这就是现在的逻辑代数。 逻辑代数与普通代数相似之处在于它们都是用字母表示变量,用代数式描述客观事物间的关系。但不同的是,逻辑代数是描述客观事物间的逻辑关系,逻辑函数表达式中的逻辑变量的取值和逻辑函数值都只有两个值,即0和1。这两个值不具有数量大小的意义,仅表示客观事物的两种相反的状态,如开关的闭合与断开;晶体管的饱和导通与截止;电位的高与低;真与假等。因此,逻辑代数有其自身独立的规律和运算法则,而不同于普通代数。 数字电路在早期又称为开关电路,因为它主要是由一系列开关元件组成,具有相反的二状态特征,所以特别适于用逻辑代数来进行分析和研究,这就是逻辑代数广泛应用于数字电路的原因。本章主要介绍逻辑代数的基本运算、基本定律和基本运算规则,然后介绍逻辑函数的表示方法及逻辑函数的代数化简法和卡诺图化简法。 2、2 逻辑函数及其表示方法 掌握逻辑代数的常用运算。 理解并初步掌握逻辑函数的的建立和化简方 掌握真值表、 一、基本逻辑函数及运算 基本的逻辑关系有与逻辑、或逻辑和非逻辑三种。与之对应的逻辑运算为与运算(逻辑乘)、或运算(逻
逻辑代数的运算规则 逻辑代数的基本定律 逻辑代数的三个规则 1、代入规则 在任一逻辑等式中,如果将等式两边所有出现的某一变量都代之以一个逻辑函数,则此等式仍然成立,这一规则称之为代入规则。 2、反演规则 已知一逻辑函数F,求其反函数时,只要将原函数F中所有的原变量变为反变量,反变量变为原变量;“+”变为“·”,“·”变为“+”;“0”变为“1”;“1”变为“0”。这就是逻辑函数的反演规则。 3、对偶规则 已知一逻辑函数F,只要将原函数F中所有的“+”变为“·”,“·”变为“+”;“0”变为“1”;“1”变为“0”,而变量保持不变、原函数的运算先后顺序保持不变,那么就可以得到一个新函数,这新函数就是对偶函数F'。 其对偶与原函数具有如下特点: 1.原函数与对偶函数互为对偶函数; 2.任两个相等的函数,其对偶函数也相等。这两个特点即是逻辑函数的对偶规则。 逻辑运算的常用公式 逻辑代数的总结 基本逻辑运算: 与(或称“积”)---符号(&、?、无、∧、∩) 或(或称“和”)---符号(| 、+、∨、∪)
非(或称“反”)---符号(! 、) 1 0-1律: 0?A=0 0+A=1 1?A=A 1+A=A 同一律: A?A=A A+A=A 互补律: A?A=0 A+A=0 反演律 A?B =A+B A+B=A? 还原律 A =A √⊕⊙??+A=0 2、常用公式 交换律: A?B=B?A A+B=B+A 结合律: A?(A?B)=(A?B)?C A+(A+B)=(A+B)+C 分配律: A?(A+B)=A?B+A?C A+(A?B)=(A+B)?(A+C) 吸收律: A?(A+B)=AB A+(A?B)=AB A?B+(A?B)=A (A+B)?(A+B)=A
第二章 逻辑代数基础 [题2.1] 选择题 以下表达式中符合逻辑运算法则的是 。 A.C ·C=C 2 B.1+1=10 C.0<1 D.A+1=1 2. 逻辑变量的取值1和0可以表示: 。 A.开关的闭合、断开 B.电位的高、低 C.真与假 D.电流的有、无 3. 当逻辑函数有n 个变量时,共有 个变量取值组合。 A. n B. 2n C. n 2 D. 2n 4. 逻辑函数的表示方法中具有唯一性的是 。 A .真值表 B.表达式 C.逻辑图 D.卡诺图 5. 在 输入情况下,“与非”运算的结果是逻辑0。 A .全部输入是0 B.任一输入是0 C.仅一输入是0 D.全部输入是1 6.在 输入情况下,“或非”运算的结果是逻辑0。 A .全部输入是0 B.全部输入是1 C.任一输入为0,其他输入为1 D.任一输入为1 7. 求一个逻辑函数F 的对偶式,可将F 中的 。 A .“·”换成“+”,“+”换成“·” B.原变量换成反变量,反变量换成原变量 C.变量不变 D.常数中“0”换成“1”,“1”换成“0” E.常数不变 8. 在同一逻辑函数式中,下标号相同的最小项和最大项是 关系。 A .互补 B.相等 C.没有关系 9. F=A +BD+CDE+ D= 。 A. A B. A+D C. D D. A+BD 10.A+BC= 。 A .A+ B B.A+ C C.(A+B )(A+C ) D.B+C 11.逻辑函数F=)(B A A ⊕⊕= 。 A.B B.A C.B A ⊕ D. B A ⊕ [题2.2]判断题(正确打√,错误的打×) 1. 逻辑变量的取值,1比0大。 ( ) 2. 异或函数与同或函数在逻辑上互为反函数。 ( ) 3.若两个函数具有相同的真值表,则两个逻辑函数必然相等。 ( )
逻辑代数的三个规则 1、代入规则 在任一逻辑等式中,如果将等式两边所有出现的某一变量都代之以一个逻辑函数,则此等式仍然成立,这一规则称之为代入规则。 2、反演规则 已知一逻辑函数F,求其反函数时,只要将原函数F中所有的原变量变为反变量,反变量变为原变量;“+”变为“·”,“·”变为“+”;“0”变为“1”;“1”变为“0”。这就是逻辑函数的反演规则。 3、对偶规则 已知一逻辑函数F,只要将原函数F中所有的“+”变为“·”,“·”变为“+”;“0”变为“1”;“1”变为“0”,而变量保持不变、原函数的运算先后顺序保持不变,那么就可以得到一个新函数,这新函数就是对偶函数F'。 其对偶与原函数具有如下特点: 1.原函数与对偶函数互为对偶函数; 2.任两个相等的函数,其对偶函数也相等。这两个特点即是逻辑函数的对偶规则。 逻辑运算的常用公式 逻辑代数的总结 基本逻辑运算: 与(或称“积”)---符号(&、?、无、∧、∩) 或(或称“和”)---符号(| 、+、∨、∪) 非(或称“反”)---符号(! 、) 1 0-1律: 0?A=0 0+A=1 1?A=A 1+A=A 同一律: A?A=A A+A=A 互补律: A?A=0 A+A=0 反演律 A?B =A+B B=A?B
还原律 A =A √⊕⊙??+A=0 2、常用公式 交换律: A?B=B?A A+B=B+A 结合律: A?(A?B)=(A?B)?C A+(A+B)=(A+B)+C 分配律: A?(A+B)=A?B+A?C A+(A?B)=(A+B)?(A+C)吸收律: A?(A+B)=AB A+(A?B)=AB A?B+(A?B)=A (A+B)?(A+B)=A
1 逻辑代数基础
教学目的与要求: 本章是数字电子技术的重要基础。首先在了解数字信号与数字电路、数制与码制、算术运算 与逻辑运算等概念基础上,要求学生深刻理解逻辑代数中的与、或、非三种基本运算,熟悉 由它们导出的其它逻辑运算,掌握逻辑代数中的基本公式、常用公式和基本定理;其次要求 学生理解逻辑函数概念, 掌握逻辑函数的各种表示方法与转换, 最小项与最大项的性质特点 及逻辑函数的范式; 本章最后介绍逻辑函数的公式与卡诺图化简方法, 要求学生对这些方法 与技巧做到熟练掌握、灵活运用。 教学重点与难点: 1、基本逻辑运算与复合逻辑运算; 2、逻辑代数的基本公式、基本定理; 3、逻辑函数的表示及其公式与卡诺图化简方法与技巧。 教学时数:共计 8 学时 (其中理论课 8 学时,实验课 学时,习题课 学时,讨论课 学时) 教学内容与方法: 结合典型例题,运用启发式、课堂练习、课后思考与作业等多种教学方法与手段,详细分析 讲解数制与码制、基本逻辑运算与复合逻辑运算方法、逻辑代数基本公式与基本定理、逻辑 函数的表示与转换方法、逻辑函数的公式化简与卡诺图化简方法与技巧等重要教学内容。
1.1 概述
一、数字信号与模拟信号
1、模拟信号与模拟电路: 在数值大小和时间上都连续的物理量为模拟量。 对模拟信号进行传输和处理的电子电路为模 拟电路。 2、数字信号与数字电路: 在数值大小和时间上都不连续即离散(每次以某最小单位的整数倍变化)的物理量为数字量。 对数字信号进行传输和处理的电子电路为数字电路。 3、数字电路的类型与特点 ①数字电路的分类: 按电路结构分:分立、集成;按器件制作工艺分:双极型与 MOS 型;按工作原理分:组合 逻辑电路和时序逻辑电路;按集成度分:SSI、MSI、LSI、VLSI。 ②数字电路的优点:易集成、高可靠、通用成本低、易保密
二、数制与码制
1、数制 1)数制的概念及要素: 数制的定义:多位数码中各数位的构成方法及运算时的进位规则称为数制。 数制的要素:任意数位上的可用数码、可用数码的个数(基数,实质为进位规则)、权(与各数 位对应的固定数值)。 一般地,设 (an 1an 2
(an 1an 2
a1a0 .a1a2 a m ) N 为一个 N 进制数,则该数对应的数值大小为: a1a0 .a1a2 a m ) N = ∑ in=1 m ai N i (按权展开式)。
2)常见数制: ①10 进制:
《逻辑代数基础》练习题及答案 [1.1]将下列二进制数转为等值的十六进制数的等值的十进制数。 (1)(10010111)2 ;(2)(1101101)2 ;(3)(0.01011111)2 ;(4)(11.001)2 。 [解] (1)(10010111)2 = (97)16 = (151)10,(2)(11011101)2 = (6D)16 = (109)10(3)(0.01011111)2 = (0.5F)16 = (0.37109375)10,(4)(11.001)2 = (3.2)16 = (3.125)10 [1.2]将下列十六进制数化为等值的二进制数和等值的十进制数。 (1)(8C)16 ;(2)(3D.BE)16;(3)(8F.FF)16 ;(4)(10.00)16 [解] (1)(8C)16 = (10001100)2 = (140)10 (2)(3D·BE)16 = (111101.1011111)2 = (61.7421875)10 (3)(8F·FF)16 = (10001111.11111111)2 = (143.99609375)10 (4)(10.00)16 = (10000.00000000)2 = (16.00000000)10 [1.3]将下列十进制数转换成等效的二进制数和等效的十进制数。要求二进制数保留小数点以后4位有效数字。 (1)(17)10 ;(2)(127 )10 ;(3)(0.39)10 ;(4)(25.7)10 [解] (1)(17)10 =(10001)2 =(11)16 ;(2)(127)10 = (1111111)2 = (7F)16 (3)(0.39)10 = (0.0110)2 = (0.6)16;(4)(25.7)10 = (11001.1011)2 = (19.B)16 [1.4]写出下列二进制数的原码和补码。 (1)(+1011)2 ;(2)(+00110)2 ;(3)(-1101)2 ;(4)(-00101)2 。 [解] (1)(+1011)2的原码和补码都是01011(最高位的0是符号位)。 (2)(+00110)2的原码和补码都是000110(最高位的0是符号位)。 (3)(-1101)2的原码是11101(最高位的1是符号位),补码是10011。 (4)(-00101)2的原码是100101(最高位的1是符号位),补码是111011。 [1.5]试总结并说出 (1)从真值表写逻辑函数式的方法;(2)从函数式列真值表的方法; (3)从逻辑图写逻辑函数式的方法;(4)从逻辑函数式画逻辑图的方法。 [解] (1)首先找出真值表中所有使函数值等于1的那些输入变量组合。然后写出每一组变量组合对应的一个乘积项,取值为1的在乘积项中写为原变量,取值为0的在乘积项中写为反变量。最后,将这些乘积项相加,就得到所求的逻辑函数式。 (2)将输入变量取值的所有状态组合逐一代入逻辑函数式,求出相应的函数值。然后把输入变量取值与函数值对应地列成表,就得到了函数的真值表。 (3)将逻辑图中每个逻辑图形符号所代表逻辑运算式按信号传输方向逐级写出,即可得到所求的逻辑函数式。 (4)用逻辑图形符号代替函数式中的所有逻辑运算符号,就可得到由逻辑图形符号连接成的逻辑图了。