离散数学考前复习（（二）数理逻辑）离散数学

离散数学考前复习：（二）数理逻辑 2.1 命题及联结词

命题：命题是指一个判断（陈述）的语义（实际表达的概念），这个概念是可以被定义并观察的现象。命题不是指判断（陈述）本身，而是指所表达的语义。当相异判断（陈述）具有相同语义的时候，他们表达相同的命题。
命题联结词：
非：否定联结词（-p为真仅当p为假）
并：合取联结词（p∧q为真当且仅当q,p同为真）
或：析取联结词（p∨q为真当且仅当p或q有一为真）
蕴涵：蕴涵联结词（p→q为假仅当p为真q为假）
等价：等价联结词（p?q为真仅当p,q的真值相同）
命题联结词的优先级
（1）否定<合取<析取<蕴涵<等价
（2）同级的联结词按从左到右确定
（3）括号优先级最高

2.2 命题公式和分类

原子命题公式（合式公式，又称命题公式、公式）：
(1)单个命题常项或变项是合式公式;
(2)如果A是合式公式，则﹁A也是合式公式;
(3)如果A，B是合式公式，则P∧Q、P∨Q、P→Q、 P?Q也是合式公式;
(4)只有有限次地应用(1)~(3)所包含的命题变元，联结词和括号的符号串才是合式公式。
成真赋值：指定一组值使A为1
成假赋值：指定一组值使A为0
真值表
【离散数学考前复习（（二）数理逻辑）】重言式（永真式）：A在它的各种赋值下取值均为真
矛盾式（永假式）：A在它的各种赋值下取值均为假
可满足式：不是矛盾式就是可满足式

2.3等值演算与范式

等价（等值）：在任意解释下两个命题真值相同，记做G?H（充分必要条件是G?H永真公式）
命题公式

文章图片

文章图片
等值演算
简单析取式：每一个析取项或是一个命题变元，或是一个命题变元的否定（p,q,p∨q,p∨┐p∨r,┐p∨q∨┐r.）
简单合取式：含有一个变元及其否定的合取式.每一个合取项或为命题变元，或为命题变元的否定的合取式（p,┐r,┐p∧r,┐p∧q∧r,p∧q∧┐q）
析取范式：由有限个简单合取式构成的析取式称为析取范式。（(┐p∧q)∨r, ┐p∨q∨r, p∨┐q∨r）
合取范式：由有限个简单析取式构成的合取式称为合取范式。（(p∨q∨r)∧(┐q∨r), ┐p∧q∧r, p∧┐q∧r）
范式：析取范式与合取范式统称为范式。
（1）任何命题公式都存在范式
（2）任何命题公式都存在与之等值的析取范式和合取范式
极小项（极大项）：设由n个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取式）都是极小项（极大项），则称该析取范式（合取范式）为主析取范式（主合取范式）。
主析取范式：由有限个极小项组成的析取范式称为主析取范式（真值表为1的析取合集）
主合取范式：由有限个极大项组成的合取范式称为主合取范式（真值表为0的合取合集）
任何命题公式都存在主析取范式和主合取范式，并且是唯一的