第一章 命题逻辑
1,否定
?P读作非P P ?P T F F T 2,合取(*) P ∧ Q 读作“P且Q”，“P合取Q”。 P Q P∧Q T T T T F F F T F F F F 合取的性质 1) 幂等律 p ∧ p ? p
2) 交换律 p ∧ q ? q ∧ p
3) 结合律 （ p ∧q）∧ r ? p ∧ (q ∧ r ) 4) 零律 p ∧ F ? F 5) 同一律 p ∧ T ? p 6) 否定律 p ∧ ? p ? F 3,析取(+)
P ∨ Q，读作“P或Q”，“P析取Q”。 P Q P ∨ Q T T T T F T F T T F F F 析取的性质 1) 幂等律 2) 交换律 3) 结合律 4) 同一律 5) 零律 6) 否定律 7) 吸收律 8) 分配律 9) 德、摩根律 4,蕴含
P→ Q读作“P蕴含Q”，“如果P则Q”，“当P，则Q”，“P件”。 P Q P→ Q T T 是Q的充分条T F F T F F 5,等价 P ?Q读作“P等价于Q”，“ P当且仅当Q”，“P是Q的充要条件”。
P Q P ?Q T T T F F F T F 等价的性质 1. 1) 交换律 2. 2) 结合律
3. 说明：1)?是逻辑联结词，而 ? 是公式关系符。A、B是命题，A ?B仍是命题，而A ? B不是命题。(2) P、Q两命题，没有内在联系 P ?Q仍有意义。例：2+2=5的充要条件是太阳从西边升起。 该命题为真 几个重要定理
? 1.若A ? B， B ? C，则A ? C.传递性
? 2. A ? B的充要条件是A ? B且B ? A(逻辑等价的另一种定义） 其他的连接词符号 ? 或非词符号
? 定理: A↓B等价于?(AVB) ? 定理:{↓}是功能完备集 ? 与非词符号
? 定理:A↑B等价于?(A∧B) ? 定理:{↑}是功能完备集 ? 异或词符号
? 举例说明:周末,我或者在北京或者在上海 ? 定理:A异或B等价于?(A?B)
第二章谓词逻辑
谓词演算的推理规则
? US 全称指定规则（消去量词）
? UG 全称推广规则 对命题量化（添加量词） ? ES 存在指定规则（消去量词） ? EG 存在推广规则（添加量词）
第三章 集合 第四章关系
（R ? S）
（R·S）2=（R·S）·（R·S） = R·（S·R）·S R-1
? 逆运算的性质
? 定理：设R和S均是A到B的关系，则 ? （1）（R-1）-1=R，
? （2）（R∪S）-1=R-1∪S-1， ? （3）（R∩S）-1= R-1∩S-1， ? （4）（R-S）-1=R-1-S-1， ? （5）（~R）-1=~(R-1),（A×B）-1=B×A ? （6）ФA-1=ФA，EA -1 =EA, IA -1 = IA ? （7）R=S iff R-1=S-1。
? (8)（R-S）-1=（R∩?S）-1=R-1∩（?S）-1=R-1∩?S-1=R-1-S-1 EG:
如|A|=n， A上自反关系共有?个 |A×A|=n2 ,其中n个有序对对应自回路， 故A上自反关系共有 2n(n-1)个。
例|A|=3，A上关系共有29个，而自反关系共有26个。