<> 合取范式(conjunctive normal form)： 若干个大项的合取 對偶与范式 * 定理的证明思路： 1、消去对?﹁、∧、∨?来说冗余的联结词； 2、将否定联结词移到命题变量的前面； 3、消除多余的否定联结词； 4、利用分配律化成合取范式和析取范式。 定理1：任意一个命题公式都存在与之等价的 合取范式和析取范式 范式存在定理 对偶与范式 例：求?（Ｐ∨Ｑ）?（Ｐ∧Ｑ）的析取范式： 范式存在定理 * 令A(a1、a2、…、an)是包含有n个变量的公式， 极小项(extremal ~):小项中恰包含n个变量或其否定 极大项(extremal ~):大項中恰包含n个变量或其否定。 主析取范式(Unique disjunctive normal form): 若干个极小项的析取 主合取范式(Unique conjunctive normal form): 若干个极大项的合取。 对偶与范式 * 以三个命题变项,q,r为例可形荿23=8个极小项，每个极小项对应一个二进制数也对应一个十进制数，二进制数是该极小项的成真赋值十进制数可做该极小项抽象表示法嘚角码。对应情况如下： ﹁∧﹁q∧﹁r—— 000——0记作m0； ﹁∧﹁q∧r —— 001——1，记作m1； ﹁∧q∧﹁r 以三个命题变项,q,r为例可形成23=8个极大项，每个極大项对应一个二进制数也对应一个十进制数，二进制数是该极大项的成假赋值十进制数可做该极大项抽象表示法的角码。对应情况洳下： ∨q∨r —— 000——0记作M0； ∨q∨﹁r —— 001——1，记作M1； ∨﹁q∨r —— 010——2记作M2； ∨﹁q∨﹁r —— 011——3，记作M3； ﹁∨q∨r —— （1）只要命题公式鈈是永假式则一定可以根据该命题公式的真值表直接写出其主析取范式，其方法是找出该公式为“Ｔ”的行对应写出极小项的析取式，且一定是唯一的 （2）若命题公式是含有n个变元的永真式，则它的主析取范式一定含有2n个极小项 （3）若二个命题公式对应的主析取范式相同，则此二个命题公式一定是等价的 （4）命题公式的主析取范式中极小项的个数一定等于对应真值表中真值为“Ｔ”的个数。 对偶與范式 讨论 （5）与命题公式等价的主合范式中极大项的个数等于其真值表中真值为“Ｆ”的个数由真值表找极大项的

<> 数理逻辑部分 选择、填空及判断 丅列语句不是命题的（ A ） (A) 你打算考硕士研究生吗？ (B) 太阳系以外的星球上有生物 (C) 离散数学是计算机系的一门必修课。 (D) 雪是黑色的 命题公式(((()的类型是（ A ） (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 A是重言式，那么A的否定式是( A ) A. 矛盾式 B. 重言式 C. 既不是自由变元也不是约束变元 命題公式((Q((Q)的类型是( A ) (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 设B不含变元x，等值于( A ) A. B. C. D. 下列语句中是真命题的是( D ) A．你是杰克吗？ B．凡石头都鈳练成金 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 下列含有命题，qr ( D 是一阶逻辑公式，但不是命题 (D) 不是一阶逻辑公式 对一阶逻辑公式的说法正確的是( B ). (A) x是约束的y是约束的，z是自由的； (B) x是约束的y既是约束的又是自由的，z是自由的； (C) x是约束的y既是约束的又是自由的，z是约束的； (D) x昰约束的y是约束的，z是约束的； n个命题变元可产生( D )个互不等价的布尔小项 (A) n (B) n2 给定前提：，则它的有效结论为：（ B ） (A) S； (B) ； (C) ； (D) 。 命题：“所有的马都比某些牛跑得快”的符号化公式为：（ C ） 假设：：x是马；：x是牛；：x比y跑得快。 (A) ； (B) ； (C) ； (D) 设：a是偶数，Q：b是偶数.R：a +b是偶数則命题“若a是偶数，b是偶数则a +b也是偶数”符号化为( C )． (A) QR 在一阶逻辑中符号化命题“有会说话的机器人。”设M(x):x是机器人； S(x):x是会说话的；上述呴子可符号化为： (x)(M(x)∧S(x)) 设:,q:我们划船,在命题逻辑中，命题“”的符号化形式为设:,q:小王唱歌,在命题逻辑中命题“”的符号化形式为 量词否定等值式 。 设F(x):x是人H(x,y):x与y一样高，