当前位置:首页 >> 数学 >>

范式


§ 2.2 命题公式的标准型——范式

L 0 g i c 命 题 逻 辑

给定一个命题公式,判断它是重言式、矛盾 式、还是可满足式,这类问题称为判定问题。在 前面已经讲过解决判定问题的两种方法,即真值 表法和等价演算法。但当命题变项的数目较多时, 上述两种方法都显得不方便,所以必须给出其它 的方法,这就是把命题公式化成标准型(主析取 范式和主合取范式)的方法。根据这种方法,同 一真值函数所对应的所有命题公式具有相同的标 准型,这无疑对判断两个命题公式是否等价以及 判断公式的类型是一种好方法。

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

1

2.2 析取范式和合取范式 定义2.2 命题变项及其否定统称作文字(letters)。 仅由有限个文字构成的析取式称作简单析取式。 仅由有限个文字构成的合取式称作简单合取式。 简单析取式举例: p,┐q p∨┐p,┐p∨q ┐p∨┐q∨r,p∨┐q∨r 简单合取式举例: ┐p,q ┐p∧p,p∧┐q p∧q∧┐r,┐p∧p∧q

L 0 g i c 命 题 逻 辑

说 明

? 一个文字既是简单析取式,又是简单合取式。

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

2

2.2 析取范式和合取范式

L 0 g i c 命 题 逻 辑

为讨论方便,有时用A1,A2,…,As表示s个简单析取式或s个简 单合取式。 设Ai是含n个文字的简单析取式,若Ai中既含某个命题变项pj, 又含它的否定式┐pj, 即pj∨┐pj,则Ai为重言式。 反之,若Ai为重言式,则它必同时含某个命题变项和它的否 定式,否则,若将Ai中的不带否定符号的命题变项都取0值, 带否定号的命题变项都取1值,此赋值为Ai的成假赋值,这与 Ai是重言式相矛盾。 类似的讨论可知,若Ai是含n个命题变项的简单合取式,且Ai 为矛盾式,则Ai中必同时含某个命题变项及它的否定式,反之 亦然。

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

3

L 0 g i c 命 题 逻 辑

定理1 一个简单析取式是永真式当且仅当它同时含 一个命题符号及其否定;一个简单合取式是矛盾式当 且仅当它同时含一个命题符号及其否定。 定义2 由有限个简单合取式 ( 基本积 ) 构成的析取式 称为析取范式(disjunctive normal form),由有限个简 单析取式(基本和)构成的合取式称为合取范式 (conjunctive normal form)。析取范式和合取范式统称 为范式(normal form)。
? 形如┐p∧q∧r的公式既是一个简单合取式构成的析取 范式,又是由三个简单析取式构成的合取范式。 ? 形如p∨┐q∨r的公式既是含三个简单合取式的析取范 式,又是含一个简单析取式的合取范式。
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 4

1、范式

L 0 g i c 命 题 逻 辑

例 1 析取范式和合取范式: (p?q)?(?p??q),(p?r)?(q??r?p)?(?r??p)等是析取范式 (p?q)?(?p??q),(p?r)?(q??r?p)?(?r??p)等是合取范式 根据定义知,一个析取范式的对偶式是合取范式,一个合 取范式的对偶式是析取范式。 定理2 一个析取范式是矛盾式当且仅当它的每个基本积 都是矛盾式。一个合取范式是永真式当且仅当它的每个基 本和都是永真式。 定理3 (范式存在定理)任意命题公式都存在与之等值的 析取范式与合取范式。
说 明

? 研究范式的目的在于,将给定公式化成与之等值的析 取范式或合取范式,进而将公式化成与之等值的主析 取范式或主合取范式。
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 5

1、范式

求一个公式的范式的步骤如下: [1]. 利 用 蕴 涵 等 值 式 (A?B)?(?A?B) 和 等 价 等 值 式 (A?B)?(?A?B)?(A??B) 消除公式中的联结词 ? 和 ? , 使得公式中只含有联结词?、?和?。 [2]. 利用双重否定律 ?? A?A 和德摩尔根律将否定放到 命题符号前。 [3]. 利用分配律,求析取范式利用 ?对?的分配律,求合 取范式则利用?对?的分配律。 例2 求命题公式的析取范式和合取范式 (1). 求(?p?q)?(p?r)的析取范式和合取范式 (2). 求(p?q)?(p?r)的析取范式和合取范式 解 (1)求(?p?q)?(p?r)的析取范式和合取范式: (?p?q)?(p?r)?(??p?q)?(?p?r)
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 6

L 0 g i c 命 题 逻 辑

1、范式

?(p?q)?(?p?r) //合取范式 ?(p??p)?(p?r)?(q??p)?(q?r) // 析取范式 ?(p?r)?(q??p)?(q?r) //析取范式 (2)求(p?q)?(p?r)的合取范式和析取范式: (p?q)?(p?r)?(?p?q)?(p?r) ?(?p)?q?(p?r) //析取范式 ? (?p?q?p)? (?p?q?r) //合取范式 注意:一个命题公式的合取范式和析取范式不具有唯一性。 因而析取范式与合取范式不能作为同一真值函数所对应的 命题公式的标准形式。为了使任意一个命题公式,化成与 其等价的唯一的公式形式,我们引入主析取范式和主合取 范式的概念。
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 7

L 0 g i c 命 题 逻 辑

2、主范式

L 0 g i c 命 题 逻 辑

一、主析取范式 定义3 在含有n个命题变元的简单合取式中,若每个命题 符号和其否定不同时存在,而二者之一必须出现且只出现 一次,且第i个命题变元或者否定出现在从左边算起的第 i 个位置上(若命题变元无下标,则按字典顺序排列),这 样的简单合取式称为极小项。 极小项是特殊的简单合取式。含 n 个命题变元的极小 项中 ,由于每个命题变元以原形或否定出现且仅出现一次 , 因此n 个命题变元共可产生 2n个不同的极小项。若在极小 项中,将命题变元的原形对应1,否定对应0,则每个极小 项唯一地对应一个二进制数,该二进制数的每一位正是使 该极小项的真值为1的真值赋值。
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 8

主析取范式

L 0 g i c 命 题 逻 辑

例3 两个命题变元p, q生成的4个极小项为: ?p??q对应00,记为m0 ?p?q对应01,记为m1 p??q对应10,记为m2 p?q对应11,记为m2 由三个命题变元p, q, r生成的8个极小项为: ?p??q??r对应000,记为m0 ?p??q?r对应001, 记为m1 ?p?q??r对应010,记为m2 ?p?q?r对应011,记为m3 p??q??r对应100,记为m4 p??q?r对应101,记为m5 p?q??r对应110, 记为m6 p?q?r对应111, 记为m7

注(1)任意两个不同的极小项都不等价;
(2)任意两个不同的极小项的合取必为假; (3)所有的极小项的析取必为真。
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 9

主析取范式

定义4 若析取范式中的简单合取式都是极小项,则称该 析取范式为主析取范式。 定理4 任何命题公式存在唯一的主析取范式。 求一个公式的主析取范式是:

L 0 g i c 命 题 逻 辑

[1] 先求该公式的一个析取范式。 [2] 如果该析取范式的某个简单合取式 A 中既不含某个 命题变元p,也不含它的否定?p,则该简单合取式变为如 下形式:(A?p)?(A??p)。 [3] 消除重复出现的命题变元或命题变元的否定,矛盾 式及重复出现的极小项,并将每个极小项的命题变元或其 否定按下标顺序或字典顺序排列。
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 10

主析取范式

例4 求命题公式的主析取范式 (1). 求(?p?q)?(p?r)的主析取范式 (2). 求(p?q)?(p?r)的主析取范式 解 (1) 根 据 例 2 知 (?p?q)?(p?r) 的 一 个 析 取 范 式 是 (p?r)?(q??p)?(q?r),我们将其中的每个简单合取式展开 为含有所有命题变元的极小项的析取: (p?r)展开为:(p?q?r)?(p??q?r); (q??p)展开为: (?p?q?r)?(?p?q??r); (q?r)展开为: (p?q?r)?(?p?q?r) 因此(?p?q)?(p?r)的主析取范式为 (p?q?r)?(p??q?r)?(?p?q?r)?(?p?q??r) 按极小项所对应的二进制数的大小重新排列为 (?p?q??r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m2 ? m3 ? m5 ?m7??(2,3,5,7)。
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 11

L 0 g i c 命 题 逻 辑

主析取范式

(2)由例2知(p?q)?(p?r)的一个析取范式为(?p)?q?(p?r), 将其中每个简单合取式展开为含有所有命题变元的极小项 的析取: ?p展开为 (?p?q?r)?(?p??q?r)?(?p?q??r)?(?p??q??r) q展开为 (p?q?r)?(?p?q?r)?(p?q??r)?(?p?q??r) (p?r)展开为(p?q?r)?(p??q?r) 因此(p?q)?(p?r)的主析取范式为: (?p??q??r)?(?p??q?r)?(?p?q??r)?(?p?q?r) ?(p??q?r) ?(p?q??r)?(p?q?r) ??(0,1,2,3,5,6,7)。 主析取范式也可从命题公式的真值表更容易地得到,对 应地,根据命题公式的主析取范式也可容易地构造其真值 表、判定其类型(矛盾式、可满足式还是永真式)等。
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 12

L 0 g i c 命 题 逻 辑

例5 求命题公式((P?Q)?R)?P的主析取范式 解1: ((P ?Q)? R)?P??(?(P ?Q)?R)?P

L 0 g i c 命 题 逻 辑

? ((P ?Q)??R)?P ? ((P??R)?(Q??R))?P
?((P??R)?P)?(Q??R)? (Q ?? R) ? P (析取范式)

?(P?(Q??Q)?(R??R))?((Q??R)?(P??P))
?(P??Q??R)?(P?Q??R)?(P??Q?R)?(P?Q?R)

?(?P ?Q? ? R) ? (P ?Q? ? R)
?m4 ?m6 ? m5?m7 ?m2 ? m6

? m2 ? m4 ? m5 ? m6 ? m7??(2,4,5,6,7)
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 13

L 0 g i c 命 题 逻 辑

解2: ((P?Q?R)?P ??(?(P ?Q)?R)?P ? ((P ?Q)??R)?P ? ((P??R)?(Q??R))?P ? ((P??R)?P)?(Q??R)?(Q?? R)?P ? mx10 ? m1xx ? m010 ? m110 ? m100 ? m101 ? m110? m111 ? m2 ? m4 ? m5 ? m6 ? m7 ??(2,4,5,6,7) (析取范式)

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

14

求公式A的主析取范式的方法与步骤

L 0 g i c 命 题 逻 辑

方法一、等值演算法 (1)化归为析取范式。 (2)除去析取范式中所有永假的析取项。 (3)将析取式中重复出现的合取项和相同的变元合并。 (4)对合取项补入没有出现的命题变元,即添加如(p∨┐p)式, 然后应用分配律展开公式。 方法二、真值表法 (1)写出A的真值表。 (2)找出A的成真赋值。 (3)求出每个成真赋值对应的极小项(用名称表示),按角标 从小到大顺序析取。

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

15

主合取范式

L 0 g i c 命 题 逻 辑

二、主合取范式 定义5 在含有n个命题变元的简单析取式中,若每个命题 符号和其否定不同时存在,而二者之一必须出现且只出现 一次,且第i个命题变元或者否定出现在从左边算起的第 i 个位置上(若命题变元无下标,则按字典顺序排列),这 样的简单析取式称为极大项。 极大项是特殊的简单析取式。含 n 个命题变元的极大 项中 ,由于每个命题变元以原形或否定出现且仅出现一次 , 因此n 个命题变元共可产生 2n个不同的极大项。若在极大 项中,将命题变元的原形对应0,否定对应1,则每个极大 项唯一地对应一个二进制数,该二进制数的每一位正是使 该极大项的真值为0的真值赋值。
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 16

L 0 g i c 命 题 逻 辑

例 两个命题变元p, q生成的4个极大项为: ?p??q对应11,记为M3 ?p?q对应10,记为M2 p??q对应01,记为M1 p?q对应00,记为M0 由三个命题变元p, q, r生成的8个极大项为: ?p??q??r对应111,记为M7 ?p??q?r对应110, 记为M6 ?p?q??r对应101,记为M5 ?p?q?r对应100,记为M4 p??q??r对应011,记为M3 p??q?r对应010,记为M2 p?q??r对应001, 记为M1 p?q?r对应000, 记为M0

注(1)任意两个不同的极大项都不等价;
(2)所有的极大项的合取必为假; (3)任意两个不同的极大项的析取必为真。
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 17

定义6 若合取范式中的简单析取式都是极大项,则称该 合取范式为主合取范式。 定理5 任何命题公式存在唯一的主合取范式。 求一个公式的主合取范式是:

L 0 g i c 命 题 逻 辑

[1] 先求该公式的一个合取范式。 [2] 如果该合取范式的某个简单析取式 A 中既不含某个 命题变元p,也不含它的否定?p,则该简单析取式变为如 下形式:(A?p)?(A??p)。 [3] 消除重复出现的命题变元或命题变元的否定,重言 式及重复出现的极大项,并将每个极大项的命题变元或其 否定按下标顺序或字典顺序排列。
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 18

例6 求命题公式((P?Q)?R)?P的主合取范式 L 0 g i c
解1: ((P?Q)?R)?P ?(Q ? ? R)?P ? ( P ? Q)? (P? ? R) 合取范式 ? ((P?Q)? (R?? R))?((P?? R)?(Q??Q)) ?(P?Q?R)?(P?Q??R)?(P?Q??R)?(P??Q??R) ? M0 ? M1 ? M3

命 题 逻 辑

? ?(0,1,3)(主合取范式)
??(2,4,5,6,7) (主析取范式)
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 19

解2: ((P ? Q)?R)?P ? ( P?Q)?(P??R)
? M00x ? M0x1 ? M000 ? M001 ? M001 ? M011 ? M 0 ? M1 ? M3 ? ?(0,1,3) 主合取范式 ? m2 ? m4 ? m5 ? m6 ? m7 ??(2,4,5,6,7) 主析取范式

L 0 g i c ( 合取范式)

命 题 逻 辑

主合取范式也可从命题公式的真值表更容易地得到,对 应地,根据命题公式的主合取范式也可容易地构造其真 值表、判定其类型(矛盾式、可满足式还是永真式)等
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 20

求公式A的主合取范式的方法与步骤

L 0 g i c 命 题 逻 辑

方法一、等值演算法 (1)化归为合取范式。 (2)除去合取范式中所有永真的合取项。 (3)将合取式中重复出现的析取项和相同的变元合并。 (4)对析取项补入没有出现的命题变元,即添加如(p∧┐p)式, 然后应用分配律展开公式。 方法二、真值表法 (1)写出A的真值表。 (2)找出A的成假赋值。 (3)求出每个成假赋值对应的极大项(用名称表示),按角 标从小到大顺序析取。

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

21

主合取范式与主析取范式之间的关系

由例6 可以看出,对于一个命题公式若求出了其主 合取范式就可以直接写出其主析取范式,反之依然。为了 研究它们之间的关系,我们首先来研究极大项与极小项之 间的关系。我们已得极大项与极小项具有下列关系。 ? Mi ? mi, ?mi ?Mi 设命题公式A含有n个命题变元,且设A的主析取范式中含 k个极小项 mi1 , mi2 ,..., mik . 则? A的主析取范式中必含有 n 2 ? k个极小项,设为 m j , m j ,..., m j , 即

L 0 g i c 命 题 逻 辑

A ? ??A ? ?(m j1 ? m j2 ? ... ? m j n )
? M j1 ? M j2 ? ... ? M j n
9/21/2015 6:30 PM Discrete Math. , QingTai Wu
2 ?k
2 ?k

?A ? m j1 ? m j2 ? ... ? m j n

1

2

2n ? k

2 ?k

22

主析取范式与主合取范式之间的关系

由以上可知由A的主析取范式求其主合取范式的步骤为: (1)求出A的主析取范式中没有包含的极小项

L 0 g i c 命 题 逻 辑

m j1 , m j2 ,..., m j n
2 ?k

2 ?k

(2)求出(1)中角码相同的极大项 (3)由以上的极大项构成的合取式即为A的主合取范式。

M j1 , M j2 ,..., M j n

即 A ? M j1 ? M j2 ? ... ? M j n

2 ?k

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

23

例7 (1) (p?q)?p?q; (2) p?q?r. 解 (1) (p?q)?p?q ? ?((?p?q)?p)?q ? ?(?p?q)??p?q ? (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)?(p?q) ?m0?m1?m2?m3 ??(0,1,2,3) (主析取范式) ?1(T)(主合析取范式)
9/21/2015 6:30 PM Discrete Math. , QingTai Wu

L 0 g i c 命 题 逻 辑 求下列命题公式的主析取范式和主合取范式

24

L 0 g i c 命 题 逻 辑

解法Ⅰ (2)p?q?r ? (p?q)?(?r? r)?(?p?p)?(?q?q)?r ? (p?q??r)?(p?q?r)?(?p??q?r)?(?p?q?r) ?(p??q?r)?(p?q?r) ?(?p??q?r)?(?p?q?r)?(p??q?r)? (p?q??r) ?(p?q?r) ?m1?m3?m5?m6?m7 ??(1,3,5,6,7) (主析取范式) ??(0,2,4) (主合取范式)

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

25

L 0 g i c 命 题 逻 辑

解法Ⅱ (2)p?q?r ? (p? r)?(q?r) ? (p?(?q?q)?r)?((?p?p)?q?r) ? (p?q?r)?(p??q?r)?(p?q?r)?(?p?q?r) ? (p?q?r)?(p??q?r)?(?p?q?r) ? M0?M2?M4 ??(0,2,4) (主合取范式) ??(1,3,5,6,7) (主析取范式)

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

26

解法Ⅲ L 0 g i c 命 题 逻 辑 (2)p?q?r ? m11X?mXX1 ? m111?m110?m001?m011?m101?m111 ? m001?m011?m101?m110?m111 ? m1?m3?m5?m6?m7 ??(1,3,5,6,7) (主析取范式) ??(0,2,4) (主合取范式) 解法 Ⅳ (2)p?q?r ? (p?r)?(q?r)? M0X0?MX00 ? M000?M010?M000?M100 ? M000?M010?M100 ? M0?M2?M4 ??(0,2,4) (主合取范式) ??(1,3,5,6,7) (主析取范式)
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 27

主析取范式的用途

L 0 g i c 命 题 逻 辑

求公式的成真赋值与成假赋值 判断公式的类型 判断两个命题公式是否等值 应用主析取范式分析和解决实际问题

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

28

求公式的成真赋值与成假赋值

L 0 g i c 命 题 逻 辑

若公式A中含n个命题变项,A的主析取范式含s(0≤s≤2n)个极 小项,则A有s个成真赋值,它们是所含极小项角标的二进制 表示,其余2n-s个赋值都是成假赋值。 例 (p→q)?r ? m1∨m3∨m4∨m7,各极小项均含三个文字, 因而各极小项的角标均为长为3的二进制数,它们分别是001, 011,100,111,这四个赋值为该公式的成真赋值,其余的为成 假赋值。 例p→q ? m0∨m1∨m3,这三个极小项均含两个文字,它们 的角标的二进制表示00,01,11为该公式的成真赋值,10是 它的成假赋值。

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

29

重言式与矛盾式的主析取范式

L 0 g i c 命 题 逻 辑

设公式A中含n个命题变项,容易看出: A为重言式当且仅当A的主析取范式含全部2n个 极小项。 A为矛盾式当且仅当A的主析取范式不含任何极 小项。此时,记A的主析取范式为0。 A为可满足式当且仅当A的主析取范式至少含一 个极小项。

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

30

重言式与矛盾式的主合取范式

L 0 g i c 命 题 逻 辑

设n为公式中命题变项个数 矛盾式无成真赋值,因而矛盾式的主合取范式含2n个极大 项。 重言式无成假赋值,因而主合取范式不含任何极大项。 将重言式的主合取范式记为1。 可满足式的主合取范式中极大项的个数一定小于2n。

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

31

真值表与范式的关系 n个命题变项共可产生2n个极小项(极大项) 可以产生的主析取范式(主合取范式)数目为:

L 0 g i c 命 题 逻 辑

C ? C ??? C
0 2n 1 2n

2n 2n

?2

2n

A?B当且仅当A与B有相同的真值表,又当且仅当A与B 有相同的主析取范式(主合取范式)。 真值表与主析取范式(主合取范式)是描述命题公式标 准形式的两种不同的等价形式。

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

32

本章典型习题

L 0 g i c 命 题 逻 辑

用等值演算法证明重言式和矛盾式 用等值演算法证明等值式 求公式的主析取范式和主合取范式 用主范式判断两个公式是否等值 求解实际问题

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

33

例题

L 0 g i c 命 题 逻 辑

求公式(p∧q)∨(┐p∧r)的主析取范式和主合取范式。
解答 p 0 0 0 q 0 0 1 r 0 1 0 (p∧q)∨(┐p∧r) 0 1 0

0
1 1

1
0 0

1
0 1

1
0 0

1
1

1
1

0
1

1
1

主析取范式为 (┐p∧┐q∧r)∨(┐p∧q∧r)∨(p∧q∧┐r)∨(p∧q∧r)

主合取范式为 (p∨q∨r)∧(p∨┐q∨r)∧(┐p∨q∨r)∧(┐p∨q∨┐r)
9/21/2015 6:30 PM Discrete Math. , QingTai Wu 34

例题

L 0 g i c 命 题 逻 辑

甲、乙、丙、丁四个人有且只有两个人参加围棋比赛。关于 谁参加比赛,下列四个判断都是正确的: (1)甲和乙只有一人参加比赛。 (2)丙参加,丁必参加。 (3)乙或丁至多参加一人。 (4)丁不参加,甲也不会参加。 请推断出哪两个人参加围棋比赛。
解答

设a:甲参加了比赛。 c:丙参加了比赛。 (1) (a∧┐b)∨(┐a∧b) (3) ┐(b∧d)
9/21/2015 6:30 PM

b:乙参加了比赛。 d:丁参加了比赛。 (2) c→d (4) ┐d→ ┐a

Discrete Math. , QingTai Wu

35

L 0 g i c 命 题 逻 辑 ((a∧┐b)∨(┐a∧b))∧(c→d)∧(┐(b∧d))∧(┐d→ ┐a) ?(a∧┐b∧┐c∧d)∨(a∧┐b∧d)∨(┐a∧b∧┐c∧┐d) 根据题意条件,有且仅有两人参赛, 故﹁a∧b∧﹁c∧﹁d为0,所以 (a∧﹁b∧﹁c∧d)∨(a∧﹁b∧d)为1, 即甲和丁参加了比赛。

说 明

(a∨b)∧(c∨d) ? (a∧c)∨(b∧c)∨(a∧d)∨(b∧d)

9/21/2015 6:30 PM

Discrete Math. , QingTai Wu

36


相关文章:
三大研究范式
三大研究范式_哲学/历史_人文社科_专业资料。解读教育研究三大范式 首都师范大学教育学院 潘茂明 内容摘要 在教育研究的发展进程中, 研究范式随着教育本身的发展而发生...
几大范式的区别
数据库的设计范式是数据库设计所需要满足的规范,满足这些规范的数据库是简洁的、 结构明晰的,同时,不会发生插入 (insert) 、删除(delete)和更新(update)操作异常...
注意的研究范式
注意的研究范式 1、 提示范式基本原理是用刺激或指导语来引导被试注意一个明确的输入源, 然后把这输入源的加工和对 其它输入源的加工作比较。其实,提示就是对...
数据库习题范式部分
(A,G) (13)设一个关系为 R(A,B,C,D,E.F.G), 它的最小函数依赖集为 FD={A→B,A →C,C→D,C→E,A→F,F→G},则该关系最高满足( )范式。...
第二讲:社会科学研究范式(1)
第二讲:社会科学研究范式(1)所谓研究范式是在一定研究方法论基础上形成的研究的原 则和方法体系。我们主要介绍四种典型的社会科学研究范式:科 学主义研究范式(实证...
数据库三大范式讲解
数据库三大范式讲解_计算机软件及应用_IT/计算机_专业资料。SQL Sever数据库三大范式讲解。数据库三大范式说明数据库的设计范式是数据库设计所需要满足的规范,满足这些...
三大范式+BCNF
1NF 就是最基本的关系数据库 你现在能用数据库系统做出来的数据库最低都是 1NF 注意,1NF 范式没有主键(码) 1NF 是满足 无重复列,每列都不可分隔 无重复列...
最全的心理学实验范式
最全的心理学实验范式中国心理学 1.快速序列视觉呈现任务(rapid serial visual presentation task, RSVP ) 在快速序列视觉呈现任务中,给被试呈现一系列视觉序列刺激...
标准化第三范式
第三范式第三范式(3NF)是数据库规范化中所使用的一种正规形式,用来检验是否所有非 键属性都只和候选键有相关性,也就是说所有非键属性互相之间应该是无关的。 ...
范式习题
试分析: (1) 根据上述规定,写出关系模式 R 的基本函数依赖; (2) 指出该关系模式 R 的候选码 (3) 指出该关系模式 R 的范式级别,为什么? 若 R 不是 3NF...
更多相关标签: