SAT问题的NPC证明学习课程

1、内容提要1.证明思路总览2.证明中用到的知识 2.1 非确定图灵机 2.2 非确定图灵机的运转规则3. 证明的详细过程 3.1 用或逻辑式表达运转规则 3.2 建立NP类问题到可满足性问题的多项式变换4.可能用到的知识附录第1页/共72页第一页，编辑于星期六：十九点 五十五分。证明思路总览 根据NPC问题定义来证明 只要所有NPC问题均可在多项式时间内变换到SAT问题即可证明SAT问题为NPC.1L2L*1*2xf( )f xyxf任意的NP类问题SAT问题第2页/共72页第二页，编辑于星期六：十九点 五十五分。证明思路总览 如何证明所有NP类问题 SAT? 然而，若将每个NP类问题都多项式变

2、换到SAT问题是不现实的，所以要抽取NP类问题的共性，建立NP类问题的统一计算模型-非确定的图灵机（NDTM）.012-1-2-3-4-534567. .有限状态控制器猜想模块猜想头读写头第3页/共72页第三页，编辑于星期六：十九点 五十五分。证明思路总览 如何证明所有NP类问题 SAT? NP类问题的计算过程均可抽象为一个NDTM上的运作过程. 因此，SAT的NPC证明等价于证明NDTM SAT.012-1-2-3-4-534567.有限状态控制器猜想模块猜想头读写头第4页/共72页第四页，编辑于星期六：十九点 五十五分。证明思路总览 如何证明NDTM SAT? 只要找到多项式变换f； 设一

3、个NP类问题所对应语言的一个字符串为x，若x被NDTM接受，则对应SAT问题的例子f(x)回答为“是”。1L2L*1*2xf( )f xyxf任意的NP类问题SAT问题第5页/共72页第五页，编辑于星期六：十九点 五十五分。证明思路总览 现整理证明的思路如下：任意NP类问题012-1-2-3-4-534567.有限状态控制器猜想模块猜想头读写头语言问题例子字符串对应作为输入建立图灵机的运作规则到SAT的多项式时间变换问题得证第6页/共72页第六页，编辑于星期六：十九点 五十五分。NP问题的统一模型 非确定图灵机计算模型012-1-2-3-4-534567. .有限状态控制器猜想模块猜想头读写头

4、01230,.,()nxxxxxxb 空白字符012301Y2N,.,nQqqqqqqqqqq初始状态；接受状态；拒绝状态；第7页/共72页第七页，编辑于星期六：十九点 五十五分。NDTM的运转规则非确定图灵机计算过程与DTM不同（两阶段）： 猜想阶段 检验阶段第8页/共72页第八页，编辑于星期六：十九点 五十五分。NDTM的运转规则012-1-2-3-4-534567. .有限状态控制器猜想模块猜想头读写头agcdBBBBBBBB初始输入字符串x写入图灵机猜想模块起作用，有限状态控制模块不起作用，从-1向左依次写入字符表中的任意多个任意字符猜想阶段：ggg检验阶段：猜想模块不起作用，有限状态

5、模块起作用第9页/共72页第九页，编辑于星期六：十九点 五十五分。NDTM的运转规则NDTM的运转规则被总结为6项： （1）初始时刻，M处于初态 ，读写头瞄准带格 ，x放置在 到 的带格中；而 ， , 皆为空白。 012-1-2-3-4-53.n. .有限状态控制器猜想模块猜想头读写头0q(1)c(1)c( )c n(0)c(1)c n ( )1)c p n 1kx2kx0q3kxnkxn+1bbb第10页/共72页第十页，编辑于星期六：十九点 五十五分。NDTM的运转规则NDTM的运转规则被总结为6项： （2）在每一时刻，M处于且仅处于一个状态。 012-1-2-3-4-53.n.有限状态控

6、制器猜想模块猜想头读写头1kx2kx3kxnkxn+1bbbiqjq第11页/共72页第十一页，编辑于星期六：十九点 五十五分。NDTM的运转规则NDTM的运转规则被总结为6项： （3）在每一时刻，读写头仅瞄准一个带格。 012-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头1kx2kx3kxnkxn+1bbb第12页/共72页第十二页，编辑于星期六：十九点 五十五分。NDTM的运转规则NDTM的运转规则被总结为6项： （4）在每一时刻，每个带格恰好写有一个带符。 012-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头1kx2kx3kxnkxn+1bbbikxjkx

7、第13页/共72页第十三页，编辑于星期六：十九点 五十五分。NDTM的运转规则 NDTM的运转规则被总结为6项： （5）在最后一步，若x被M接受，则当时状态为 。 012-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头1kx2kx3kxnkxn+1bbbikxYqYq第14页/共72页第十四页，编辑于星期六：十九点 五十五分。NDTM的运转规则NDTM的运转规则被总结为6项： （6）M中一步计算的过程如下： xyxzyp( , )( , ,)p xq y rightyq第15页/共72页第十五页，编辑于星期六：十九点 五十五分。用或逻辑式表达运转规则 或逻辑式中的布尔变量： (1

8、) 和状态相关的布尔变量：012-1-2-3-4-53.n. . .有限状态控制器猜想模块猜想头读写头1kx2kx3kxnkxn+1bbbkq第i步i( ,)TMQ i kk若第 步，位于状态qF 否则第16页/共72页第十六页，编辑于星期六：十九点 五十五分。用或逻辑式表达运转规则 或逻辑式中的布尔变量： (2) 和读写头（Head）、带格相关的布尔变量：012-1-2-3-4-53.j.n.有限状态控制器猜想模块猜想头读写头1kx2kxjkxnkxn+1bbb第i步i( , )TH i j若第 步，读写头瞄准带格c(j)F 否则第17页/共72页第十七页，编辑于星期六：十九点 五十五分。用

9、或逻辑式表达运转规则 或逻辑式中的布尔变量： (3) 和带格、带中字符相关的布尔变量：012-1-2-3-4-53.j.n.有限状态控制器猜想模块猜想头读写头1kx2kxlxnkxn+1bbb第i步ix( , , )TS i j ll若第 步，带格c(j)中的带符为F 否则lxj第18页/共72页第十八页，编辑于星期六：十九点 五十五分。 (1)初始时刻的或逻辑式： 012-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头(0,0)Q1kx2kx0q3kxnkxn+1bbb用或逻辑式表达运转规则用或逻辑式表达运转规则(0,1)H (0,0,0)S1 (0,1,)Sk (0, ,)n

10、Sn k (0,1,0)Sn (0,( )1,0)Sp n 第0步第19页/共72页第十九页，编辑于星期六：十九点 五十五分。(2) 在每一时刻，M处于且仅处于一个状态： 012-1-2-3-4-53.n. . .有限状态控制器猜想模块猜想头读写头1kx2kx3kxnkxn+1bbb( ,0),( ,1),( ,2),.,( , )Q iQ iQ iQ i r肯定处于一个状态jqjq第i步用或逻辑式表达运转规则用或逻辑式表达运转规则第20页/共72页第二十页，编辑于星期六：十九点 五十五分。 (2) 在每一时刻，M处于且仅处于一个状态： 012-1-2-3-4-53.n. .有限状态控制器读写

11、头1kx2kx3kxnkxn+1bbbjqjqA B m0 0 0 m0 m3 m2 m1 ( , )Q i j( ,)Q i j0101第i步卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则( , ),( ,)Q i jQ i j第21页/共72页第二十一页，编辑于星期六：十九点 五十五分。(3) 在每一时刻，读写头仅瞄准一个带格： 012-1-2-3-4-53.n.有限状态控制器猜想模块猜想头读写头1kx2kx3kxnkxn+1bbb用或逻辑式表达运转规则用或逻辑式表达运转规则1kx2kx5kx( ,( )( ,( )1),.,( ,( )1)H ip nH ip nH i p n最多在

12、 步内判定一个猜想，而 表示还要多读一个空白符，从而M知道结束了( )p n( ) 1p n 第22页/共72页第二十二页，编辑于星期六：十九点 五十五分。(3) 在每一时刻，读写头仅瞄准一个带格： 012-1-2-3-4-5j.n. . . . .有限状态控制器读写头1kx2kx3kxnkxn+1bbbjA B m0 0 0 m0 m3 m2 m1 ( , )H i j( ,)H i j0101( , ),( ,)H i jH i j第i步卡诺图用或逻辑式表达运转规则用或逻辑式表达运转规则第23页/共72页第二十三页，编辑于星期六：十九点 五十五分。 (4) 在每一时刻，每个带格恰好写有一个

13、带符: 012-1-2-3-4-53.j.n.有限状态控制器猜想模块猜想头读写头1kx2kx3kxnkxn+1bbblxlx ( , ,0),( , ,1),.,( , , )S i jS i jS i j s肯定有0s中的一个字符第i步用或逻辑式表达运转规则用或逻辑式表达运转规则第24页/共72页第二十四页，编辑于星期六：十九点 五十五分。(4) 在每一时刻，每个带格恰好写有一个带符: 012-1-2-3-4-53.j.n.有限状态控制器读写头1kx2kx3kxnkxn+1bbblxlx第i步A B m0 0 0 m0 m3 m2 m1 ( , ,)S i j l0101卡诺图( , , )

14、S i j l ( , , ),( , ,)S i j lH i j l用或逻辑式表达运转规则用或逻辑式表达运转规则第25页/共72页第二十五页，编辑于星期六：十九点 五十五分。 (5) 在最后一步，若x被M接受，则当时状态为 :012-1-2-3-4-53.n. . .有限状态控制器猜想模块猜想头读写头1kx2kx3kxnkxn+1bbbikxYqYq( ),1)Q p n第 步( )p n用或逻辑式表达运转规则用或逻辑式表达运转规则第26页/共72页第二十六页，编辑于星期六：十九点 五十五分。 (5) 在最后一步，若x被M接受，则当时状态为 :012-1-2-3-4-53.n.有限状态控制

15、器猜想模块猜想头读写头1kx2kx3kxnkxn+1bbbikxYqYq( ),1)Q p n第 步( )p n用或逻辑式表达运转规则用或逻辑式表达运转规则第27页/共72页第二十七页，编辑于星期六：十九点 五十五分。1(,)(, )klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第i+1步计算过程的或逻辑式: 读写头指向的带格，字符才有可能改变A B m0 0 0 m0 m3 m2 m1 (1, , )S ij l0101卡诺图( , , )S i j l( , )1H i j 第28页/共72页第二十八页，编辑于星期六：十九点 五十

16、五分。1(,)(, )klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第i+1步计算过程的或逻辑式: 读写头没指向的带格，字符不可能改变A B m0 0 0 m0 m3 m2 m1 (1, , )S ij l0101卡诺图( , , )S i j l( , )0H i j 第29页/共72页第二十九页，编辑于星期六：十九点 五十五分。用或逻辑式表达运转规则用或逻辑式表达运转规则 (6) 第i步到第i+1步计算过程的或逻辑式: 合并两卡诺图A B m0 0 0 m0 m3 m2 m1 (1, , )S ij l0101卡诺图( , , )

17、S i j l( , )0H i j A B m0 0 0 m0 m3 m2 m1 (1, , )S ij l0101( , , )S i j l( , )1H i j 第30页/共72页第三十页，编辑于星期六：十九点 五十五分。0 01 10101111110100000( , , )S i j l(1, , )S ij l( , )H i j用或逻辑式表达运转规则用或逻辑式表达运转规则 (6) 第i步到第i+1步计算过程的或逻辑式: 合并两卡诺图( , )( , , ) (1, , )( , , )*(1, , )H i jS i j l S ij lS i j lS ij l第31页/共

18、72页第三十一页，编辑于星期六：十九点 五十五分。0 01 10101111110100000( , , )S i j l(1, , )S ij l( , )H i j用或逻辑式表达运转规则用或逻辑式表达运转规则 (6) 第i步到第i+1步计算过程的或逻辑式:书错了？！( , )( , , ) (1, , )( , , )*(1, , )H i jS i j l S ij lS i j lS ij l ( , , ),( , ),(1, , )S i j lH i jS ij l我看了Cook71年原文，没有这个式子，关于(6)的式子，他仅举一例，一笔带过，只告诉大家有这个东西而已。第32页/

19、共72页第三十二页，编辑于星期六：十九点 五十五分。用或逻辑式表达运转规则用或逻辑式表达运转规则 (6) 第i步到第i+1步计算过程的或逻辑式：( , )( , , )(1, , )H i jS i j lS ij l( , )( , , ) (1, , )( , , )*(1, , )H i jS i j l S ij lS i j lS ij l()()()()ABABABABAABBA BAAB BABAB( , , ) (1, , )( , , )*(1, , )*S i j l S ij lS i j lS ij lABAB第33页/共72页第三十三页，编辑于星期六：十九点 五十五分

20、。0 01 10101111110100000( , , )S i j l(1, , )S ij l( , )H i j用或逻辑式表达运转规则用或逻辑式表达运转规则 (6) 第i步到第i+1步计算过程的或逻辑式: ( , , ),( , ),(1, , )S i j lH i jS ij l ( , , ),( , ),(1, , )S i j lH i jS ij l两式相与，代入无误第34页/共72页第三十四页，编辑于星期六：十九点 五十五分。1(,)(, )klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第i+1步计算过程的或逻辑

21、式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 ( ,)Q i k0101卡诺图( , , )S i j l( , )0H i j ( ,)0H i j 第35页/共72页第三十五页，编辑于星期六：十九点 五十五分。1(,)(, )klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 ( ,)Q i k0101卡诺图( , , )S i j l( , )0H i j ( ,)1H i

22、 j 第36页/共72页第三十六页，编辑于星期六：十九点 五十五分。1(,)(, )klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 ( ,)Q i k0101卡诺图( , , )S i j l( , )1H i j ( ,)0H i j 第37页/共72页第三十七页，编辑于星期六：十九点 五十五分。1(,)(, )klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第

23、i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 ( ,)Q i k0101卡诺图( , , )S i j l( , )1H i j ( ,)1H i j 第38页/共72页第三十八页，编辑于星期六：十九点 五十五分。用或逻辑式表达运转规则用或逻辑式表达运转规则 (6) 第i步到第i+1步计算过程的或逻辑式: 合并四个卡诺图得00 01 11 100000010111111010( ,)Q i k( , , )S i j l( , )H i j( ,)H i j ( , )( , ,)( , ,)*( ,)( , )*( ,)H

24、 i jS i j kS i j kQ i kH i jH i j ( , ),( , ,),( ,),( ,)H i jS i j kQ i kH i j 书上代入出错？！第39页/共72页第三十九页，编辑于星期六：十九点 五十五分。用或逻辑式表达运转规则用或逻辑式表达运转规则 (6) 第i步到第i+1步计算过程的或逻辑式: 或逻辑式推导( , )( , ,)( , ,)*( ,)( , )*( ,)*H i jS i j kS i j kQ i kH i jH i jABBCAD ()()()()ABBCADA DDB CCBCADADADBCBCBCADADAA DBCBB CDCADB

25、C第40页/共72页第四十页，编辑于星期六：十九点 五十五分。用或逻辑式表达运转规则用或逻辑式表达运转规则 (6) 第i步到第i+1步计算过程的或逻辑式: 或逻辑式推导ABBCADDCADBC()()()()ABBCADABBCADDCADBCAADBBCCBCDADABCD第41页/共72页第四十一页，编辑于星期六：十九点 五十五分。用或逻辑式表达运转规则用或逻辑式表达运转规则 (6) 第i步到第i+1步计算过程的或逻辑式: 合并四个卡诺图得00 01 11 100000010111111010( ,)Q i k( , , )S i j l( , )H i j( ,)H i j ( , ),

26、( , ,),( ,),( ,)H i jS i j kQ i kH i j 现在代入所有的取值都对Cook71中和书上的式子一致，可能是他的笔误第42页/共72页第四十二页，编辑于星期六：十九点 五十五分。1(,)(, )klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 ( ,)Q i k0101卡诺图( , , )S i j l( , )0H i j ( ,)0Q i k 第43页/共72页第四十三页，编辑于星期六：十

27、九点 五十五分。1(,)(, )klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 ( ,)Q i k0101卡诺图( , , )S i j l( , )0H i j ( ,)1Q i k 第44页/共72页第四十四页，编辑于星期六：十九点 五十五分。1(,)(, )klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带

28、格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 ( ,)Q i k0101卡诺图( , , )S i j l( , )1H i j ( ,)0Q i k 第45页/共72页第四十五页，编辑于星期六：十九点 五十五分。1(,)(, )klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 ( ,)Q i k0101卡诺图( , , )S i j l( , )1H i j ( ,)1Q i k 第46页/共72页第四

29、十六页，编辑于星期六：十九点 五十五分。用或逻辑式表达运转规则用或逻辑式表达运转规则 (6) 第i步到第i+1步计算过程的或逻辑式: 合并四个卡诺图得00 01 11 100000010111111010( ,)Q i k( , , )S i j l( , )H i j( , )( , ,)( , ,)*( ,)( , )*( ,)H i jS i j kS i j kQ i kH i jQ i k( , ),( , ,),( ,),( ,)H i jS i j kQ i kQ i k书上代入出错？！( ,)Q i k第47页/共72页第四十七页，编辑于星期六：十九点 五十五分。1(,)(,

30、)klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 ( ,)Q i k0101卡诺图( , , )S i j l( , )0H i j ( , ,)0S i j l 第48页/共72页第四十八页，编辑于星期六：十九点 五十五分。1(,)(, )klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A

31、B m0 0 0 m0 m3 m2 m1 ( ,)Q i k0101卡诺图( , , )S i j l( , )0H i j ( , ,)1S i j l 第49页/共72页第四十九页，编辑于星期六：十九点 五十五分。1(,)(, )klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 ( ,)Q i k0101卡诺图( , , )S i j l( , )1H i j ( , ,)0S i j l 第50页/共72页第五十页，

32、编辑于星期六：十九点 五十五分。1(,)(, )klklqxqx用或逻辑式表达运转规则用或逻辑式表达运转规则jj lxkq1lxkqlx (6) 第i步到第i+1步计算过程的或逻辑式:全过程只有状态和第j个带格上字符串可能变化A B m0 0 0 m0 m3 m2 m1 ( ,)Q i k0101卡诺图( , , )S i j l( , )1H i j ( , ,)1S i j l 第51页/共72页第五十一页，编辑于星期六：十九点 五十五分。用或逻辑式表达运转规则用或逻辑式表达运转规则 (6) 第i步到第i+1步计算过程的或逻辑式: 合并四个卡诺图得00 01 11 100000010111

33、111010( ,)Q i k( , , )S i j l( , )H i j( , )( , ,)( , ,)*( ,)( , )*( , ,)H i jS i j kS i j kQ i kH i jS i j l( , ),( , ,),( ,),( , ,)H i jS i j kQ i kS i j l书上代入出错？！( , ,)S i j l第52页/共72页第五十二页，编辑于星期六：十九点 五十五分。NDTM到SAT问题的多项式变换 以上6组逻辑式集合的并，即为一个SAT问题的句子集。 显然可以在多项式时间内得到该SAT问题，而且若NP类问题的例子回答为”是”，则对应的字符串x可

34、被M接受，则对应的SAT问题有解。 这就建立了一个NP类问题到SAT问题的多项式时间变换。 从而问题得到证明；第53页/共72页第五十三页，编辑于星期六：十九点 五十五分。第一章第一章 数字逻辑基础数字逻辑基础1.1 数制和BCD码1.2 逻辑代数1.3 逻辑函数的表示和化简返回第 1 章上页下页第54页/共72页第五十四页，编辑于星期六：十九点 五十五分。数字电路数字电路电路的特点电路的特点：1.1.所处理的数字信号只有两种取值所处理的数字信号只有两种取值( (1 1、0 0）；）；2.2.电路抗干扰能力强；电路抗干扰能力强；3.3.信息便于长期存储，便于计算机处理。信息便于长期存储，便于计

35、算机处理。数字电路数字电路 组合逻辑电路：门组成组合逻辑电路：门组成 时序逻辑电路：触发器组成时序逻辑电路：触发器组成集成电路数字集成电路数字集成电路模拟集成电路模拟集成电路概述：概述：上页下页返回第 1 章第55页/共72页第五十五页，编辑于星期六：十九点 五十五分。 逻辑代数运算规则 逻辑代数又称布尔代数，是分析与设计逻逻辑代数又称布尔代数，是分析与设计逻辑电路的工具。逻辑代数表示的是逻辑关系，辑电路的工具。逻辑代数表示的是逻辑关系，它的变量取值只有它的变量取值只有1 1和和0 0，表示两个相反的逻辑，表示两个相反的逻辑关系。关系。第 1章上页下页 基本运算有：基本运算有： 乘（与）运算、

36、加（或）乘（与）运算、加（或）运算、求反（非）运算。运算、求反（非）运算。返回1.2 1.2 逻辑代数逻辑代数第56页/共72页第五十六页，编辑于星期六：十九点 五十五分。“与与” 门门ABFF = A B“与非与非”门门FABF = A B“或非或非”门门ABF11F = A + B“或或” 门门AB11FF = A+B“非非” 门门1 1FAF = A名称图形符号逻辑表达式功能说明输入全输入全1 1，输出为，输出为1 1输入有输入有0 0，输出为，输出为0 0输入有输入有1 1，输出为，输出为1 1输入全输入全0 0，输出为，输出为0 0输入为输入为1 1，输出为，输出为0 0输入为输入为

37、0 0，输出为，输出为1 1输入全输入全1 1，输出为，输出为0 0输入有输入有0 0，输出为，输出为1 1输入有输入有1 1，输出为，输出为0 0输入全输入全0 0，输出为，输出为1 1基本逻辑关系基本逻辑关系上页下页第1章返回第57页/共72页第五十七页，编辑于星期六：十九点 五十五分。1.1.基本运算规则基本运算规则 A A=0 , A A=A , A=A上页下页第 1 章A+0=A , A+1=1 , A 0=0A 1=A , A+A=1 , A+A=A返回第58页/共72页第五十八页，编辑于星期六：十九点 五十五分。2.2.逻辑代数的基本定律逻辑代数的基本定律交换律：交换律：A+B=

38、B+A , A B=B A结合律：结合律：A+(B+C)=(A+B)+C A (B C)=(A B) C上页下页 A B=A+B ，A+B=A B吸收定律：吸收定律：A+AB=A+B ,A+AB=A反演定理：反演定理：分配律：分配律：A(B+C)=A B+A C A+B C=(A+B) (A+C)返回第 1 章第59页/共72页第五十九页，编辑于星期六：十九点 五十五分。上页下页第1章例题例题1.2.1 证明证明 AB+AC+BC=AB+AC解：解：AB+AC+BC=AB+AC+(A+A)BC =AB+AC+ABC+ABC=AB+ABC+AC+ABC=AB(1+C)+A(C+BC)=AB+AC

39、返回第60页/共72页第六十页，编辑于星期六：十九点 五十五分。1.3 逻辑函数的表示和化逻辑函数的表示和化简简 逻辑函数的表示方法逻辑函数的表示方法逻辑函数的化简法逻辑函数的化简法上页下页第1章返回第61页/共72页第六十一页，编辑于星期六：十九点 五十五分。第1章上页下页 逻辑函数的表示方法返回 逻辑式：逻辑式：用基本运算符号列出输入、输出变量间 的逻辑代数式 逻辑状态表逻辑状态表：列出输入、输出变量的所有逻辑状态 卡诺图：卡诺图：与变量的最小项对应的按一定规则排列 的方格图 用逻辑符号表示输入、输出变量间的逻辑关系 逻辑图：逻辑图： 最小项是指所有输入变量各种组合的乘积项，输入变量最小项

40、是指所有输入变量各种组合的乘积项，输入变量包括原变量和反变量。例如，二变量包括原变量和反变量。例如，二变量A，B B的最小项有四项：的最小项有四项：AB，AB, AB, AB; 三变量的最小项有八项三变量的最小项有八项; ; 依此类推，依此类推，n 变变量的最小项有量的最小项有2 2 n n 项项第62页/共72页第六十二页，编辑于星期六：十九点 五十五分。上页下页返回第1章 设一个三输入变量的偶数判别电路，输入变量为A，B，C，输出变量为F。当输入变量中有偶数个1时，F=1；有奇数个1时，F=0。试用不同的逻辑函数表示法来表示。例例输 入输 出A B CF 0 0 0 10 0 0 1 0

41、0 0 0 1 1 0 00 1 0 00 1 0 00 0 1 1 1 1 1 11 0 0 01 0 0 01 0 1 1 0 1 1 11 1 01 1 0 1 11 1 1 1 1 1 0 0 三个输入变量的最小项有 23 = 8个，即有8 个组合状态，将这 8 个组合状态的输入，输出变量都列出来，就构成了逻辑状态表，如表所示。解：解：( 1 )逻辑状态表逻辑状态表第63页/共72页第六十三页，编辑于星期六：十九点 五十五分。上页下页返回第1章 把逻辑状态表中的输入，输出变量写成与或形式的逻辑表达式，将F = 1的各状态表示成全部输入变量的与函数，并将总输出表示成这些与项的或函数，即逻

42、辑表达式：F =A B C + A B C + A B C + A B C输 入输 出A B CF 0 0 0 10 0 0 1 0 0 1 0 0 1 0 00 1 0 0 1 0 0 00 1 1 0 1 1 1 11 0 0 1 0 0 0 01 0 1 1 0 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 0 0( 2 ) 逻辑表达式逻辑表达式第64页/共72页第六十四页，编辑于星期六：十九点 五十五分。上页下页返回第1章 若将逻辑表达式中的逻辑运算关系用相应的图形符号和连线表示，则构成逻辑图。ABCABCA BCF111&1若将逻辑状态表按一定规则行列式化则构成图下图所示。ABC0 01 10101111110100000 1 1 0 0 1 0 1 1 0(卡诺图内容见 节）( 3 ) 逻辑图逻辑图( 4 )卡诺图卡诺图第65页/共72页第六十五页，编辑于