14、 Peking University23 A的一个赋值赋值: n个命题变元 成真赋值成真赋值 成假赋值成假赋值 重言式重言式（永真式（永真式tautology） P P = 1 矛盾式矛盾式（永假式（永假式contradiction） P P = 0 可满足式可满足式 Peking University24 公式分类 重言式 矛盾式 可满足式 重言式 Peking University25 p q pq pp p(pq)p 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 0 1 赋值 可满足式 矛盾式 重言式 (永假式) (永真式) Peking University2 。

15、6 等值式（等价公式） 给定两个命题公式（给定两个命题公式（P P1 1, P, P2 2 ， , P, Pn n）和和 （P P1 1, P, P2 2 ， , P, Pn n） ， ） ， 若对若对P P1 1, P, P2 2 ， , , P Pn n的任的任 一组真值指派 ， 与的真值都相同 ， 则称一组真值指派 ， 与的真值都相同 ， 则称 与等价或逻辑相等 。
记作与等价或逻辑相等 。
记作 。
例4 构造命题公式构造命题公式 （PQ）和和 P Q的真值表的真值表 。
P Q PQ （PQ） P Q PQ 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 对于、的任一 。

16、种真值指派 ， 对于、的任一种真值指派 ，（PQ）与与 P Q 都有相同的真值 ， 都有相同的真值 ， 所以这所以这两个命题公式是等价的两个命题公式是等价的 。
Peking University27 为书写方便而省略括号 公式最外层的括号可以省略 联结词运算优先级别 同一个联结词连续多次出现且 无括号 ， 则从左到右运算 Peking University28 例题：层次法构造真值表 (p (pq) (pq)(p (pq) (pq)(p (pq) (pq)(p (pq) (pq) p q pq pq p(pq) (pq)公式公式 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 1 0 0 1 1。

17、1 0 0 0 1 1 0 0 Peking University29 等值式等值式(logical equivalences) , ()(),()() ()()(),()()() , (),() 11,00 0,1 1 ABBA ABBA ABCABCABCABC ABCABACABCABAC ABABABAB AABA AABA AA AA AA AA 幂等律AAA, AAA 交换律 结合律 分配律 的摩根律()() 吸收律 零律 同一律 排中律 矛盾律0 ()() ()() AA AA ABAB ABABBA ABAB ABBA ABABA 双重否定律 蕴涵等值式 等价等值式 等价否定等 。

18、值式 假言易位 归缪论 Peking University30 AAA, AAA A(BC) (AB)(AC) A(BC) (AB)(AC) ABBA, ABBA (AB)C A(BC) (AB)C A(BC) Peking University31 Peking University32 A1 1, A0 0 A0 A, A1 A AA 1 AA 0 (对偶原理: -互换, 0-1互换) Peking University33 A A AB AB AB (AB)(BA) Peking University34 AB AB AB BA (AB)(AB) A Peking University3 。

19、5 设是合式公式中的一个部分 ， 且也是一个合设是合式公式中的一个部分 ， 且也是一个合 式公式 ， 则称是的式公式 ， 则称是的子公式子公式 。
例例如 ， 设：如 ， 设： ( (PQ)PQ)（Q(RQ(R S)S)） ， ） ， 则则PQPQ、 RR S S、 S S、 Q(R Q(R S)S)都是的子公式 。
都是的子公式 。
置换规则 定理（置换规则）： 设X是合式公式中的子公式 ， 若是一个合式公式 ，且， 用置换中的 ， 得到新的合式公式 ， 则。
证明：证明：与除替换部分外均相同 ， 又由于替换部分与除替换部分外均相同 ， 又由于替换部分， 即是说对任一指派 ， 与真值相同 ， 那么与对 ， 即是说对任一指派 ， 与真值相同 ， 那么与对 任一真值指派也 。

20、应有相同的真值 。
故任一真值指派也应有相同的真值 。
故 。
Peking University36 等值演算： 由已知的等值式 ， 应用置换规则推演出新的等值式的 过程 。
等值演算 P (Q R) P ( Q R) P ( Q R) ( P Q) R ( P Q) R ( P Q) R Peking University37 给定命题公式(P1, P2 ， , Pn) ， 如果用某个命题公 式Bi取代中的某个变元Pi ， 并且用Bi取代中出现的所有 Pi ， 这样得到的命题公式称为命题公式的代入实例 。
例例如 ， 设：如 ， 设：P(QP) ， 用用(RS)取代中的命题取代中的命题 变元得：变元得：(RS)(Q(RS) ， 是的代入实 。

21、例 。
是的代入实例 。
代入代入规则规则 定理（代入规则）： 一个重言式的代入实例仍然是一个重言式 。
证明证明： 由于重言式的真值与真值指派无关 ， 故对同一命题由于重言式的真值与真值指派无关 ， 故对同一命题 变元变元都用某个都用某个命题公式命题公式代替代替 ， 该重言式的真值仍为 。
， 该重言式的真值仍为 。
例例 证明证明(PS)R) (PS)R)为重言式为重言式 证：证：因因P P T ， 根据根据代入规则代入规则 (PS)R) (PS)R)T Peking University38 命题逻辑推理 “”“”ABAB 若推理的形式结构为重言式 ， 则称推理正确 。
用表示是重言式 1. 推理的形式结构 前提: A1,。

22、A2, , Ak 结论: B 推理的形式结构: (A1A2Ak)B Peking University39 ( () () () B CC CC CDBD 附加律AAB 化简律AB)A, AB) 假言推理定律 (AB) AB 拒取式推理定律 (AB)BA 析取三段论推理定律 (AB)BA;

稿源：(未知)

【傻大方】网址：/a/2021/0822/0023896813.html

标题：第一编|第一编 集合论( 三 )