01-命题逻辑-16~17.ppt

第一章命题逻辑 2020年3月14日星期六 第六节范式 第六节范式问题对一个命题公式 除了真值表以外 怎样才能判定其类型 已知一个公式为真和为假的所有赋值 能否写出该公式的表达式 如何能找出命题公式的标准形式 使我们仅根据这种标准形式就能判断两个公式是否等值 2020年3月14日星期六 范式 一 简单合取式与简单析取式1 简单合取式定义 在一个公式里 仅由命题变元及其否定构成的合取式 叫做简单合取式 或基本积 质合取式 其中 每个命题变元或其否定 成为合取项 例如 P Q P Q P Q Q 2020年3月14日星期六 简单合取式 定理 简单合取式为永假式的充要条件是 它同时含有某个命题变元及其否定证明 1 充分性 对于任意命题变元P P P为F若P P在简单合取式中出现 它必为永假式2 必要性 设某简单合取式为永假式 但它并不同时包含任何命题变元及其否定若对各不带否定的命题变元赋值T 对带否定的命题变元赋值F 则该简单合取式的值为T 与假设矛盾 证毕 2020年3月14日星期六 简单析取式 2 简单析取式定义 在一个公式里 仅由命题变元及其否定构成的析取式 叫做简单析取式 或基本和 质析取式 其中 每个命题变元或其否定 成为析取项 例如 P Q P Q P Q Q定理 简单析取式为永真式的充要条件是 它同时含有某个命题变元及其否定 2020年3月14日星期六 范式 二 析取范式与合取范式1 析取范式定义 给定的命题公式若能表示为与之等价的简单合取式的析取 即A Ai Ai为简单合取式则称该简单合取式的析取为给定公式的析取范式 例如 P Q P Q Q 2020年3月14日星期六 析取范式 定理 一个析取范式为矛盾式 当且仅当它的每个简单合取式都是矛盾式 证明略 2020年3月14日星期六 合取范式 2 合取范式定义 给定的命题公式若能表示为与之等价的简单析取式的合取 即A Ai Ai为简单析取式则称该简单析取式的合取为给定公式的合取范式 例如 P Q P Q Q 定理 一个合取范式为重言式 当且仅当它的每个简单析取式都是重言式 2020年3月14日星期六 范式 定理 任何一个命题公式 都可以表示成为析取范式和合取范式 2020年3月14日星期六 求范式的方法 求范式的方法 利用命题定律 消去公式中除 以外的所有联结词使用双否定律 A A 以及德 摩根律将公式中出现的联结词 都移到命题变元前利用结合律 分配律等 将公式化为析取或合取范式 2020年3月14日星期六 范式 例1 33 求P P Q 的析取范式与合取范式解 P P Q P P Q 合取范式 P P P Q 析取范式 P Q既是析取范式 也是合取范式 2020年3月14日星期六 范式 例1 34求证 Q P Q P Q是永真式证明 Q P Q P Q Q P P Q Q P P Q Q 在这个合取范式中 每个简单析取式都是重言式 因此 该公式为重言式 2020年3月14日星期六 范式 例1 35求 P Q P Q 的析取范式与合取范式解 P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q P P Q Q P Q P Q P Q P Q P Q P Q P Q 合取范式 P P Q P P Q Q Q 析取范式 2020年3月14日星期六 范式 例1 36求公式 P Q P的判定问题解 P Q P P Q P P Q P P根据该合取范式可知 该公式不是重言式根据该析取范式可知 该公式不是矛盾式因此该公式是偶然式由本例可知 范式是不唯一的 2020年3月14日星期六 第七节主范式 第七节主范式一 主析取范式定义 在含有n个命题变元P1 P2 Pn简单合取式中 若每一个Pi和 Pi恰好有一个出现一次 而且正好出现在左起第i个变元的位置上 若无下标 按字典顺序 则该简单合取式称为极小项 或最小项 布尔积 2020年3月14日星期六 主析取范式 n个命题变元可以构成2n个不同的极小项例如三个变元P Q R 可以构成8 23 个极小项 我们把命题变元看作1 把其否定看作0 那么每个极小项对应一个二进制数 因此也对应一个十进制数 2020年3月14日星期六 主析取范式 我们把对应的二进制或十进制数当作下标i 用mi表示该极小项 则 2020年3月14日星期六 主析取范式 极小项性质 没有两个极小项是等价的 任意两个不同的极小项的合取mi mj是永假的 所有极小项的析取为永真 每个极小项只有一个解释为真 且位于主对角线上 采用此编码方法 当m的下标与P Q R取值相同时 mi的真值为1 每行每列都只有一个1 2020年3月14日星期六 主析取范式 每个极小项与它下标的二进制数一一对应 因而和每种指派一一对应 当且仅当将对应的指派代入该极小项 该极小项的值才为真 2020年3月14日星期六 主析取范式 定义 全部由极小项构成的析取范式 称为主析取范式定理 任意含有n个命题变元的非永假命题公式A 都存在与其等价的主析取范式 主析取范式的求法 真值表法公式化归法 2020年3月14日星期六 主析取范式 真值表法 例1 37 求 P Q Q的主析取范式 P Q Q P Q P Q m01 m11 2020年3月14日星期六 主析取范式 公式化归法 把给定公式化为析取范式删除析取范式中所有为永假的简单合取式用等幂律 A A A 化简简单合取式中 某一命题变元重复出现的情况用同一律和互补律 A A B B 补充简单合取式中未出现的命题变元 并用分配律展开A A B A B 这样补充没有出现过的的变元B T 2020年3月14日星期六 主析取范式 例1 38 求 P Q Q的主析取范式解 P Q Q P Q Q Q P P Q P Q P Q m01 m11 m1 m3 E9吸收律 E4分配律 用同一律和互补律 A A B B 补充简单合取式中未出现的命题变元 并用分配律展开 2020年3月14日星期六 主析取范式 由于一个命题公式的真值表是唯一的 因此一个命题公式的主析取范式也是唯一的 两个命题公式如果有相同的主析取范式 那么两个命题公式是等价的 2020年3月14日星期六 主析取范式 定理 任意含n个命题变元的非永假命题公式 其主析取范式是唯一的 证明 设一个含有n个命题变元的非永假命题公式A有两个不同的主析取范式A1和A2 显然A1 A2 由于A1和A2不同 故必然存在一个极小项mi 只出现在A1和A2的其中一个式子中 不妨设mi仅出现在A1中 取mi的成真指派S 在该指派下 A1为真而A2为假 这与A1 A2矛盾 证毕 2020年3月14日星期六 主析取范式 例1 39 求证 P Q与P P Q Q P 逻辑等价 解 P Q P Q Q Q P P P Q P Q P Q m00 m01 m11 m0 m1 m3P P Q Q P P P Q Q P P P Q P Q Q P P F P Q P Q Q P Q m0 m1 m3证毕 2020年3月14日星期六 主合取范式 二 主合取范式定义 在含有n个命题变元P1 P2 Pn简单析取式中 若每一个Pi和 Pi恰好有一个出现一次 而且正好出现在左起第i个变元的位置上 若无下标 按字典顺序 则该简单析取式称为极大项 或最大项 布尔和 2020年3月14日星期六 主合取范式 n个命题变元可以构成2n个不同的极大项例如三个变元P Q R 可以构成8 23 个极大项 我们把命题变元看作0 把其否定看作1 那么每个极大项对应一个二进制数 因此也对应一个十进制数 与主析取范式的编码规则相反 2020年3月14日星期六 主合取范式 我们把对应的二进制或十进制数当作下标i 用Mi表示该极大项 则 2020年3月14日星期六 主合取范式 极大项的性质 没有两个极大项是等价的 任何两个极大项的析取Mi Mj是永真的 所有极大项的合取为永假 每个极大项只有一个解释为假 且位于主对角线上 采用此编码方法 当M的下标与P Q R取值相同时 Mi的真值为0 每行每列都只有一个0 2020年3月14日星期六 主合取范式 每个极大项与它下标的二进制数一一对应 因而和每种指派一一对应 当且仅当将对应的指派代入该极大项 该极大项的值才为假 2020年3月14日星期六 主合取范式 定义 全部由极大项构成的合取范式 称为主合取范式定理 任意含有n个命题变元的非永真命题公式A 都存在与其等价的主合取范式 主合取范式的求法 真值表法公式化归法 2020年3月14日星期六 主合取范式 真值表法 例1 40 求 P Q Q的主合取范式 P Q Q P Q P Q M00 M10 2020年3月14日星期六 主合取范式 公式化归法 把给定公式化为合取范式删除合取范式中所有为永真的简单析取式用等幂律 A A A 化简简单析取式中 某一命题变元重复出现的情况用同一律和互补律 A A B B 补充简单析取式中未出现的命题变元 并用分配律展开A A B A B 这样补充没有出现过的的变元B F 2020年3月14日星期六 主合取范式 例1 41 求 P Q Q的主合取范式解 P Q Q P Q Q Q Q P P P Q P Q M00 M10 M0 M2我们曾求得 P Q Q的主析取范式是m01 m11思考 主析取范式与主合取范式之间有什么关系 用同一律和互补律 A A B B 补充简单析取式中未出现的命题变元 并用分配律展开 2020年3月14日星期六 主合取范式 定理 任意含n个命题变元的非永真命题公式 其主合取范式是唯一的 证明略 2020年3月14日星期六 主合取范式 例1 42 求证 P Q与P P Q Q P 逻辑等价 解 P Q M10 M2P P Q Q P P P Q Q P P P Q P Q Q P P F P Q P P P Q P Q M10 M2命题得证 m00 m01 m11 思考 主析取范式与主合取范式之间有什么关系 2020年3月14日星期六 主析取范式与主合取范式的关系 三 主析取范式与主合取范式的关系由极小项和极大项的定义可知 mi Mi Mi mi因此 主析取范式与主合取范式有 互补 的关系也就是说 可以根据主析取范式求得主合取范式 反之亦然 2020年3月14日星期六 主析取范式与主合取范式的关系 根据主析取范式A求主合取范式 求出A的主析取式中没有包含的极小项mi求出与mi下标一致的极大项Mi将上面求出的各极大项Mi做合取 即为A的主合取范式 2020年3月14日星期六 主析取范式与主合取范式的关系 例1 43已知 P Q Q m01 m11求其主合取范式 解 P Q Q m01 m11 其中缺少的极小项是m00和m10 对应的极大项是M00和M10因此 P Q Q M00 M10 2020年3月14日星期六 主析取范式与主合取范式的关系 例1 44一个命题公式A P Q R 为真的所有真值指派是000 001 010 100 110则其主合取范式是什么 解 A P Q R m000 m001 m010 m100 m110 M011 M101 M111 P Q R P Q R P Q R 2020年3月14日星期六 主范式的应用 我们在一开始提出三个问题 对一个命题公式 除了真值表以外 怎样才能判定其类型 已知一个公式为真和为假的所有赋值 能否写出该公式的表达式 如何能找出命题公式的标准形式 使我们仅根据这种标准形式就能判断两个公式是否等值 2020年3月14日星期六 主范式的应用 四 主范式的应用1 公式的判定问题一个含有n个命题变元的命题公式A属于那种类型 A T 或A可以化为与其等价的 含有2n个极小项的主析取范式 则A为永真式A F 或A可以化为与其等价的 含有2n个极大项的主合取范式 则A为永假式如果A不属于上面两种情况 则A为偶然式 2020年3月14日星期六 主范式的应用 例1 45判断公式 P Q Q为何种类型 解 P Q Q m01 m11 M00 M10所以 该式为偶然式 2020年3月14日星期六 主范式的应用 例1 46判断公式 P Q P Q 为何种类型 解 P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q m00 m01 m10 m11所以 该式为永真式 2020年3月14日星期六 主范式的应用 2 根据真值指派求公式当给出命题公式的真值指派时 可以直接写出其主范式例1 47一个命题公式A P Q R 为真的所有真值指派是000 001 010 100 110则其主合取范式是什么 解 A P Q R m000 m001 m010 m100 m110 M011 M101 M111 2020年3月14日星期六 主范式的应用 3 求命题公式的真值指派求出公式A的主析取 主合取 范式 可以求得A为真 为假 的真值指派 例1 48A B C D四个人中要派两个人出差 按下述条件 有几种派法 如何派 若A去 则C和D中要去一个人B和C不能都去C去则D要留下 2020年3月14日星期六 主范式的应用 解 A A去 B B去 C C去 D D去可知 A C D B C C D A C D B C C D m0000 m0001 m0010 m0100 m0101 m1001 m1010 m1101所以 有3种派法 B和D A和D A和C 2020年3月14日星期六 主范式的应用