离散复习

基本概念

• 命题 proposition 陈述句，不能既真又假
• 复合命题 compound proposition 包含连接词（connective），就称之为复合命题
• 否定 negation
• 和取 conjunction 就是^，析取 disjunction（inclusive or）
• 异或 exclusive or 当两个命题真值不同时异或为真

• 条件语句condition statement
  p->q仅仅只有p真q假的时候为假
• converse 把条件和结论交换；contrapositive 条件结论都取反并交换；inverse 条件结论都取反
• 双条件语句 biconditional statement （或bi-implications）"p if and only if q" 当且仅当p、q有相同真值时为真
• 真值始终相同则称equivalent，或者说A能推出B且B能推出A ，那个A、B等价
  对于符合命题也一样，推真值表，真值完全一样就等价
• identity laws 恒等律； domination law 支配~
  idempotent laws 幂等律； commutative laws 交换律；
  associative laws 结合律； distributive laws 分配率；
  de morgan's laws 德摩根定律（important）

• 条件语句等价关系（见下表）

  
  条件语句等价关系.png

题型 用已有逻辑表达式证明新的逻辑表达式：充分运用上面所提到的等价关系，所以上面的要去记 例题 P30 E7等

• 可满足 satisfiable 只要找到一次赋值使其可满为真就是可满足的

• 重言式 tautology 矛盾式 contradiction

  
  例子
• predicates and quantifires 谓词与量词
  只能对和取分配全称量词，对析取分配存在量词
• 没有必要... = 存在一个...不....