离散数学课件 第一章 命题逻辑-3rd.pdf

第一章 命题逻辑 大连理工大学软件学院 陈志奎 教授 办公室 综合楼411 Tel 87571525 实验室 教学楼A318 A323 Tel 87571620 24 MobileEmail zkchen zkchen00 1 36 回顾 命题变元 合式公式 重言式 永真式 矛盾式 永假式 永真蕴含式 代入规则 替换规则 常用逻辑恒等式 30 常用永真蕴含式 16 2 36 1 5对偶原理 定义 注意 求对偶式并不要求将 非 变原 而且对偶式 是相互的 举例 求的对偶式 求 的对偶式 A TFAT FF TA AA 设有公式 其中仅含有逻辑联结词和逻辑常值 和 在 中将分别换以 得公式 则称为 的对偶式 PQR PQR PF PT 3 36 对偶原理 定理1 5 1 证明 由德 摩根律 可知 对公式A求否定 直到 深入到命题变元 之前位置 在这个过程中 所有的 变 变 T变F F变T 得证1 12 1212 1212 1 2 n nn nn AAP PPAA A P PPAPPP APPPA P PP 设 和互为对偶式 是出现于 和 中的 所有命题变元 于是有 PQPQ PQPQ 4 36 对偶原理 定理1 5 2 证明 意味着 永真 于是有 永真 由定理1 5 1知 下式也永真 利用带入规则 以 取代 Pi 得 永真 即 12 n ABABP PP AB L若 且 为命题变元及联结 词构成的公式 则 AB 1212 nn A P PPB P PP 1212 nn A P PPB P PP 1212 nn APPPBPPP 1 2 i P in 1212 nn A P PPBP PP AB 5 36 对偶原理 例 PQPPQPQ PQPPQPQ 若 试证明 证明 设 APQPPQ BPQ 则 APQPPQ BPQ 由于 因此 AB AB 6 36 对偶原理 试证明 1 2 PQPQT PQPQF 27 26 1112 8 1719 1719 16 PQPQ PQPQE PQPQPQE PQPQPQEE PQPQPQPQE PQPQPQPQ PTQTEE TTEE TE 证明 7 36 对偶原理 试证明 1 2 PQPQT PQPQF 26 1112 PQPQ PQPQPQE PQPQ PQPQPQEE PQPQPQPQ TF PQPQF 证明 由 知和互为对偶式 由于 的对偶式是 因此由定理1 5 1知 8 36 对偶原理 定理1 5 3 证明 意味着 永真 由逆反律得 永真 根据定理1 5 1 永真 利用带入规则 以 取代 得 永真 即 12 n ABABPPP BA L若 且 为 命 题 变 元及 联 结 词构 成 的 公 式 则 AB 1212 nn A P PPB P PP 1212 nn B P PPA P PP 1212 nn BPPPAPPP 1 2 i P in i P 1212 nn BPPPAPPP BA 9 36 1 6范式和判定问题 公式的标准形式 范式 用来判定公式永真 永假 可满足 10 36 析取范式和合取范式 定义 若一个命题公式是一些命题变元及其否定的积 则称 之为基本积基本积 若这个命题公式是一些变元及其否定之 和 称为基本和基本和 一个由基本积的和组成的公式 如果与给定的公式A等 价 则称它是A的析取范式析取范式 一个由基本和的积组成的公式 如果与给定的命题公 式A等价 则称它是A的合取范式合取范式 P QPQPQ PQPPQPQ PP QQ PQ PQPP 基本积 基本和 P QPQPQ PQPQ 析取范式 PP QQ PQ PQPP 合取范式 11 36 析取范式和合取范式 定理1 6 1 定理1 6 1 一个基本积是永假式 当且仅 当它含有 形式的两个因子 证明 充分性 由于 是永假式 而 所以含有 和 形式的两个因子时基本积是 永假式 必要性 用反证法 设基本积为假但不含 和 形式的因子 于是给这个基本积中的命题变元 指派真值T 给带有否定的命题变元指派真值 F 得基本积的真值是T 与假设矛盾 证毕 PP PP QFF PP P P 12 36 析取范式和合取范式 定理1 6 2 定理1 6 2 一个基本和是永真式 当且仅 当它含有 形式的两个因子 PP 13 36 析取范式和合取范式 例 求命题公式P Q R 的析取范式 解 P Q R P Q R 这是一个合取范式 P Q P R 使用与对或的分配律 化成析取范式 14 36 析取范式与合取范式 例 求命题公式 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 Q 析取范式 P Q P P Q Q P Q P Q 使用或对与的分配律及补余律 现在是 合取范式的形式 15 36 析取范式和合取范式 PQPQ 例 求的析取范式 PQPQ PQPQPQPQ PQPQPQPQ FPQPQ PQPQ PQPPQQ PPPQPQQQ FPQPQF PQPQ 解 16 36 析取范式和合取范式 PQPQ 例 求的合取范式 APQPQ APQPQ PQPQPQPQ PQPQPQPQ PQPQ AAPQPQ APQPQ 解 令 那么 由于 所以 17 36 主析取范式 定义1 6 4 定义1 6 4 在含n个变元的基本积中 若每个变元与其否定不同时存在 而二 者之一必出现且仅出现一次 则称这种 基本积为极小项 例 两个命题变元P Q的极小项为 n个变元 极小项个数2n PQ PQPQPQ 18 36 主析取范式 假定有P Q R三个变元 PQR PQR PQR PQR PQR PQR PQR PQR 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 0 1 2 3 4 5 6 7 m m m m m m m m 19 36 主析取范式 每个极小项只有一个真值指派 任何两个极小项的合取必为假 因为在2n 种真值指派中 只有一个极小项取值为真 所有极小项的析取必为真 20 36 主析取范式 定义1 6 5定义1 6 5 一个由极小项的和组成的公 式 如果与命题公式A等价 则称它是公 式A的主析取范式 对任何命题公式 永假式除外 都可求得与 其等价的主析取范式 而且主析取范式的 形式唯一 21 36 主析取范式 求主析取范式的方法 先化成与其等价的析取范式 若析取范式的基本积中同一命题变元出现多 次 则将其化成只出现一次 去掉析取范式中所有为永假式的基本积 即去 掉基本积中含有形如P P的子公式的那些基 本积 若析取范式中缺少某一命题变元如P 则可用 公式 将命题变元P补充进 去 并利用分配律展开 然后合并相同的基本 积 PPQQ 22 36 主析取范式 APQR PQRRPPR PQRPQRPRPR PQRPQRPRQQ PRQQ PQRPQRPQR PQRPQRPQR PQRPQRPQR PQRPQR 76531 1 3 5 6 7 mmmmm 23 36 主析取范式 主析取范式和真值 表的关系 右图为 对应的真值表 PQ R PQR PQR PQR PQR PQR PQR PQR PQR PQR 极小项 0 000 0 011 0 100 0 111 1 000 1 011 1 101 1 111 APQR 24 36 主合取范式 定义1 6 6 定义1 6 6 在含n个变元的基本和中 若每个变元与其否定不同时存在 而二 者之一必出现且仅出现一次 则称这种 基本和为极大项 例 两个命题变元P Q的极大项为 n个变元 极大项个数2n PQ PQPQPQ 25 36 主合取范式 假定有P Q R三个变元 PQR PQR PQR PQR PQR PQR PQR PQR 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 0 1 2 3 4 5 6 7 M M M M M M M M 26 36 每个极大项只有一组真值指派使其为F 任何两个极大项的析取必为真 因为在2n 种真值指派中 只有一个极大项取值为假 所有极大项的合取必为假 27 36 主合取范式 定义1 6 7定义1 6 7 一个由极大项的积组成的公 式 如果与命题公式A等价 则称它是公 式A的主合取范式 对任何命题公式 永真式除外 都可求得与 其等价的主合取范式 而且主合取范式的 形式唯一 28 36 主合取范式 024 0 2 4 APQR PRQR PRQQQRPP PQRPQRPQR PQR PQRPQRPQR MMM 29 36 主合取范式 主合取范式和真值 表的关系 右图为 对应的真值表 PQ R PQR PQR PQR PQR PQR PQR PQR PQR PQR 极大项 0 000 0 011 0 100 0 111 1 000 1 011 1 101 1 111 APQR 30 36 极小项和极大项的关系 极小项 和极大项 有下列的关系 i m i M ii Mm ii mM 31 36 由合取 析取 范式求主析取 合取 范式 二者可以互相转化 已知公式A的主合取范式为 求主析取范式 解 A的主合取范式为M1 M3 可知A的主析取范 式为 于是可直接写出A的主析取范式 PQRPQR 0 2 4 5 6 7 PQRPQRPQR PQRPQRPQR 32 36 主析取范式和主合取范式 一个命题公式是永真式 它的命题变元的 所有极小项均出现在其主析取范式中 不 存在与其等价的主合取范式 一个命题公式是永假式 它的命题变元的 所有极大项均出现在其主合取范式中 不 存在与其等价的主析取范式 一个命题公式是可满足的 它既有与其等 价的主析取范式 也有与其等价的主合取 范式 33 36 主析取范式和主合取范式 例 求下列公式的主范式 P Q R 解 P Q R P Q R P Q R P R Q R P R Q Q Q R P P P Q R P Q R P Q R P Q R M1 3 5 其中 表示求合取 m0 2 4 6 7 即该公式是可满足的 应存在与其等 价的主析取范式 34 36 主析取范式和主