命题与联结词

命题

定义： 可以判断真假的 陈述句 称为命题
命题具有两个特征：首先，命题应当是一个陈述句，感叹句、疑问句、祈使句均不是命题；其次，这个陈述句所表达的内容可决定真假，且真假不可兼。

举例：

  1. 微信是一种智能手机应用程序

    它是陈述句，可决定其真值为T，所以为命题

  2. 2021年12月21日是玛雅人说的世界末日

    它是陈述句，可决定其真值为F，所以为命题

  3. 这盆花真漂亮！

    它不是陈述句，所以不是命题

  4. 我正在说谎

    悖论，虽然为陈述句，但是不能判断其真值，所以不是命题

  5. 太阳系外有外星人

    虽然我们不知道太阳系外是否有外星人，但是太阳系外要么有外星人，要么没有，真值是客观存在的，而且是唯一的，所以这是一个命题

  6. 微博是一种网络应用服务吗？

    很明显是疑问句，它不是陈述句，所以不是命题

  7. x+y=z

    不能确定语句的真假性，所以不是命题

不可剖开或分解为更简单命题的命题称为原子命题
由成分命题利用联结词构成的命题称为复合命题

命题变元

当 P 表示命题时则称 P 为命题变元
命题变元和命题是两个不同的概念
命题之具体的陈述句，有确定的真值；命题变元没有确定的真值

联结词

  1. 否定词 ¬
    为一元联结词。顾名思义，P为真，则¬P为假；¬P为假，P为真（后续真用‘T’,假用‘F’表示）

    日常语言中的“非”、“不”、“并非”等均表示合取

  2. 合取词 ∧
    是一个二元联结词。当有两个命题变元 P 和 Q ，且它们同为 T 时，该复合命题 P ∧ Q 为 T，其他为 F

    日常语言中的“且”、“与”等均表示合取

    例1：华为Mate 60 Pro+手机至少有16GB内存和512GB的存储容量。
    解：令 P 表示为“华为Mate 60 Pro+手机至少有16GB内存”，Q 表示为“华为Mate 60 Pro+手机至少有512GB的存储容量” ，则原句译为：

    P ∧ Q

    例2：你喜欢唱跳Rap，但我喜欢打篮球。
    解：令 P 表示为“你喜欢唱跳Rap”，Q 表示为“我喜欢打篮球”，则原句译为：

    P ∧ Q

注意：句子中出现并且或者；时，应当使用合取词

  1. 析取词 ∨
    是一个二元联结词。当有两个命题变元 P 和 Q ，且它们同为 F 时，该复合命题 P ∨ Q 为 F，其他为 T

    日常语言中的“或”等均表示合取

    例1：今天下雨或下雪。
    解：令 P 表示“今天下雨”，Q 表示“今天下雪”，则原句译为：

    P ∨ Q

    例2：Tom喜欢人工智能或机器学习是不对的。
    解：令 P 表示“Tom喜欢人工智能”，Q 表示“Tom喜欢机器学习”，则原句译为：

    ¬（P ∨ Q）

  2. 蕴含词 →
    是一个二元联结词。利用成分命题 P 和 Q 可构成复合命题 P → Q,读为 P 蕴含 Q，其中 P → Q称为蕴含式。P → Q 为假当且仅当 P 真 Q 假，其他情况均为 T。

    日常语言中的“如果····则····”等均表示合取

    例1：如果Tom没有学好离散数学，则他不可能学好数据结构。
    解：令 P 表示“Tom学好离散数学”，Q 表示“Tom学好数据结构”，则原句译为：

    ¬P → ¬Q

    例2：只有努力学习数据挖掘和机器学习，才能在大数据分析方面有所成就。
    解：令 P 表示“努力学习数据挖掘”，Q 表示“努力学习机器学习”，R 表示“在大数据分析方面有所成就”，则原句译为：

    R → (P ∧ Q)

如果···则··· P → Q
只有···才··· Q → P

  1. 等价词 ↔
    是一个二元联结词。利用成分命题 P 和 Q 可构成复合命题 P ↔ Q,读为 P 等价于 Q，其中 P ↔ Q称为等价式。P ↔ Q 为真当且仅当 P 和 Q 均为真或为假。日常语言中的“当且仅当”等均表示合取 例1：你可以唱跳Rap打篮球当且仅当你是个人练习生。
    解：令 P 表示“你可以唱跳Rap打篮球”，Q 表示“你是个人练习生”，则原句译为：P ↔ Q 例2：当且仅当我启动《原神》，我才休息。
    解：令 P 表示“我启动《原神》”，Q 表示“我才休息”，则原句译为：P ↔ Q

等价公式（核心，极其重要）

重要的等价公式

  1. 双重否定律：

    ¬¬P = P

  2. 结合律：

    （P ∧ Q）∧ R = P ∧ (Q ∧ R) （P ∨ Q）∨ R = P ∨ (Q ∨ R)

  3. 分配率：

    P ∨ （Q ∧ R）= (P ∨ Q) ∧ (P ∨ R) P ∧ （Q ∨ R）= (P ∧ Q) ∨ (P ∧ R)

  4. 交换律：

    P ∧ Q = Q ∧ P P ∨ Q = Q ∨ P

  5. 等幂律：

    P ∧ P = P P ∨ P = P P → P = T P ↔ P = T

  6. 等值公式：

    P → Q = ¬P ∨ Q P ↔ Q = (P → Q) ∧ (Q → P) P ↔ Q = (¬P ∨ Q) ∧ (P ∨ ¬Q) = (P ∧ Q) ∨ (¬P ∧ ¬Q) ¬(P ∧ Q) = ¬P ∨ ¬Q ¬(P ∨ Q) = ¬P ∧ ¬Q

  7. 吸收律：

    P ∨ (P ∧ Q) = P P ∧ (P ∨ Q) = P

↓：有真为假，全假为真

对偶式和内否式

对偶式定义：将不含蕴含词和等价词的命题演算公式A中的∨换为∧、∧换为∨后所得的公式称为A的对偶式,记为，同时满足
例如：

A = P ∨ (P ∧ Q) ∧ S 对偶式为 = P ∧ (P ∨ Q) ∧ S

再次注意：求合式公式的对偶式时，应先消去公式中的蕴含词和等价词，否则所求对偶式不满足以上定义

内否式定义：将命题演算公式A中的所有肯定形式换为否定形式、否定形式换为肯定形式后所得的公式称为A的内否式,记为，同样的也满足这符号真不会打，只能用图了

范式及其应用

范式

定义1：命题变元或命题变元的否定或由它们利用合取词∧组成的合式公式称为合取式，简单举例就是P ∧ Q,这里给出了更为准确的定义
定义2：命题变元或命题变元的否定或由它们利用析取词∨组成的合式公式称为析取式，简单举例就是P ∨ Q,这里给出了更为准确的定义

析取范式与合取范式的定义

上图上图，这符号要命了

析取范式与合取范式的求解方法

  1. 等价变换法
    等价变换法的步骤如下：
    （1）利用等价公式消去初始公式中的联结词 → 和 ↔。
    （2）重复利用等值公式，把否定词移到内部的命题变元上，例如以下等值公式：

    （3）重复利用分配率将公式化成合取式的析取或析取式的合取，例如：

  2. 解释法

    不太会用，不写了= =，逻辑表达没等价变换法强

主范式

  1. 主合取范式
    定义：用通俗的语言理解为在一个合取范式中，组成合取范式的每一个析取项都包含有所有的命题变元（也称为极大项）;或者说仅由极大项构成的合取范式称为主合取范式

依此类推，n个命题变元组成的极大项有2^n个，例如三个命题变元P,Q,R就可构成8个极大项，把命题变元的否定形式看成1，肯定形式看成0，则每个极大项对应一个二进制数，具体如下
P ∨ Q ∨ R 与000或0对应
P ∨ Q ∨ ¬R 与001或1对应
P ∨ ¬Q ∨ R 与010或2对应
P ∨ ¬Q ∨ ¬R 与011或3对应
¬P ∨ Q ∨ R 与100或4对应
¬P ∨ Q ∨ ¬R 与101或5对应
¬P ∨ ¬Q ∨ R 与110或6对应
¬P ∨ ¬Q ∨ ¬R 与111或7对应

  1. 主析取范式
    定义：略其实就是主合取范式定义反过来，仅由极小项构成的析取范式称为主析取范式

依此类推，n个命题变元组成的极大项有2^n个，例如三个命题变元P,Q,R就可构成8个极大项，把命题变元的否定形式看成0，肯定形式看成1，则每个极大项对应一个二进制数，具体如下
¬P ∨ ¬Q ∨ ¬R 与000或0对应
¬P ∨ ¬Q ∨ R 与001或1对应
¬P ∨ Q ∨ ¬R 与010或2对应
¬P ∨ Q ∨ R 与011或3对应
P ∨ ¬Q ∨ ¬R 与100或4对应
P ∨ ¬Q ∨ R 与101或5对应
P ∨ Q ∨ ¬R 与110或6对应
P ∨ Q ∨ R 与111或7对应