计算机导论课件：陈勃2.2

计算机导论陈勃bo.chen@

命题逻辑基础计算以计算数量大小为目的以判断和推理为目的（数值表示、数值运算）（逻辑表示、逻辑运算）抽象化（符号化、规则化）进位计数制度、四则运算等命题逻辑、谓词逻辑等

命题命题：有具体意义且能够判断真假的陈述句。命题的真值：命题判断真假后的结果。可能是“真”(true，简记T)或“假”（false,简记F）其中之一。命题标识符：表示命题的符号（如p,q,r等），该标识符称为命题常元。原子命题：不能分解为更为简单的陈述句的命题；复合命题：将多个原子命题用连接词和括号组合而成的命题。连接词“与”（∧）

pqp∧qTTTTFFFTFFFF两个命题p和q的“与”(又称为p和q的“合取”)是一个复合命题，记为p∧q。复合命题的真值可以由组成它的更简单的命题以及连接词求得。“与”式的真值：当且仅当p和q同时为真时p∧q为真，在其他情况下p∧q的真值均为假。真值表：连接词“或”（∨）

pqp∨qTTTTFTFTTFFF两个命题p和q的“或”（又称为p和q的“析取”）是一个复合命题，记为p∨q

。“或”式的真值：当且仅当p和q同时为假时p∨q为假，在其他情况下p∨q的真值均为真。真值表：连接词“非”（┑）

p┑pTFFT命题p的“非”（又称为p的“否定”）是一个复合命题，记为┑p。“非”式的真值：若p为真，则┑p为假；若p为假，则┑p为真。“非”是一个一元连接词真值表：连接词“异或”（⊕）

pqp⊕qTTFTFTFTTFFF两个命题的p和q的“异或”（又称为p和q的“不可兼或”）是一个复合命题，记为p⊕q

。“异或”式的真值：当且仅当p和q真值相同时p⊕q为假，在其他情况下p⊕q的真值为真。真值表：连接词“等价”（

）

两个命题p和q的“等价”（又称为p和q的“双条件”）是一个复合命题，记为pq。“等价”式的真值：当且仅当p和q真值相同时，pq为真，在其他情况下pq的真值均为假。真值表：pqpqTTTTFFFTFFFT连接词“蕴含”（→）

前件命题p和后件命题q的“蕴含”（又称为p和q的“条件”）是一个复合命题，记为p→q。“蕴含”式的真值：当且仅当p为真，q为假时，p→q为假，在其他情况下p→q的真值均为真。p→q可以读作：“如果p则q”、“只有q才p”、“p是q的充分条件”、“q是p的必要条件”等。pqp→qTTTTFFFTTFFT

命题公式命题变元：相对于命题（常元）而言，真值可变化、不确定，是变量命题公式：由命题变元、连接词和括号组成的合式的式子称为命题公式。对于命题公式P，若无论命题变元取什么值P的真值都为真，则称P为重言式（永真式）；若无论命题变元取什么值P的真值都为假，则称P为矛盾式（永假式）如果两个不同的命题公式P和Q，无论命题变元取什么值它们的真值都相同（PQ是重言式），则称这两个命题公式等值，记为P

Q（或P＝Q）。

命题公式例证明“蕴含等值式”：A→B=┑A∨B真值表法

ABA→B┑A∨BTTTTTFFFFTTTFFTT命题公式的等值定律

蕴含式：

A→B

=┑A∨B等价式：

AB=(A∧B)∨(┓A∧┓B)

异或式：

A⊕B=(A∨B)∧(┓A∨┓B)

连接词完备集：{∧，∨，┓}命题公式的等值定律

其中A、B、C等为命题变元，T表示“真”，F表示“假”零律： A∧F＝F A∨F＝A幺律： A∨T＝T A∧T＝A幂等律：A∨A＝A A∧A＝A求补律：A∨┓A＝T A∧┓A＝F交换律：A∨B＝B∨A A∧B＝B∧A结合律： A∨(B∨C)＝(A∨B)∨C A∧(B∧C)＝(A∧B)∧C分配律： A∧(B∨C)＝A∧B∨A∧C A∨B∧C＝(A∨B)∧(A∨C)吸收律： A∧B∨A∧┓B＝A (A∨B)∧(A∨┓B)＝A 狄－摩根定律：

┓(A∨B)＝┓A∧┓B ┓(A∧B)＝┓A∨┓B双重否定律：

┓┓A＝A命题公式的等值定律

利用等值定律可进行等值演算，以证明命题公式等值或将命题公式化简例 ((pq)(pq))r

p(qq)r

（分配律）

pTr

（求补律）

pr （幺律）命题公式的等值定律

逻辑代数与门电路

命题逻辑逻辑代数门电路逻辑思维的抽象化命题逻辑的运算化逻辑代数的电路化关注逻辑思维的形式化表达以及基于此的逻辑推演关注命题逻辑中的运算过程关注逻辑代数的电路实现人机器真(T)、假(F)0、1低电位、高电位p∧qAB与门p∨qA＋B或门┑pA非门_利用逻辑代数和门电路进行逻辑运算例(