命题逻辑_.ppt

第1章 命题逻辑 1.5 范式 1.5.1析取范式与合取范式 定义1.5.1由一些命题变元或其否定构成的析取式称为基本和，也叫简单析取式。约定单个变元或其否定是基本和。 例如，?p∨q、p∨?q、p∨q、?q、?p、q都是基本和。 定义1.5.2 由一些命题变元或其否定构成的合取式称为基本积，也叫简单合取式。约定单个变元或其否定是基本积。 例如，?p∧q、p∧?q、p∧q、?p、?q、p都是基本积。 定义1.5.3由基本和的合取构成的公式叫做合取范式。约定单个基本和是合取范式。 定义1.5.4由基本积的析取构成的公式叫做析取范式。约定单个基本积是析取范式。 1)基本和和基本积既是析取范式，又是合取范式。 2)析取范式和合取范式都仅含联结词? ,∧,∨。 ⑵利用双重否定律消去否定联结词“?”或利用德摩根律将否定联结词“?”移到各命题变元前(?内移)。 ⑶利用分配律，结合律将公式归约为合取范式和析取范式。 任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下： ⑴ 消去联结词“→”和“?” 【例1.21】求命题公式(p∨q)?p的合取范式和析取范式。 解：⑴求合取范式 (p∨q)?p ?((p∨q)→p)∧(p→(p∨q)) (消去?) ?(?(p∨q)∨p)∧(?p∨(p∨q)) (消去→) ?((?p∧?q)∨p)∧(?p∨(p∨q)) (?内移) ?(?p∨p)∧(?q∨p)∧(?p∨p∨q) (分配律) ?1∧(?q∨p)∧(1∨q) (排中律) ?1∧(?q∨p)∧1 (零律) ?(?q∨p) (同一律，合取范式) ←合取范式 ⑵求析取范式 (p∨q)?p ?((p∨q)∧p)∨(?(p∨q)∧?p) (消去?) ?((p∨q)∧p)∨((?p∧?q)∧?p) (?内移) ?p∨(?p∧?q∧?p) (吸收律) ?p∨(?p∧?p∧?q) (交换律) ?p∨(?p∧?q) (幂等律，析取范式) 由此例可以看出，命题公式的析取范式也不惟一。 ←析取范式 ←析取范式 A?B ?(A∧B) ∨(?A∧?B) 1.5.2主析取范式 由于析取范式和合取范式不惟一，所以使用起来很不方便。为此，引入主析取范式和主合取范式的概念。当命题变元的顺序约定以后，主析取范式和主合取范式是惟一的。 析取范式和合取范式的基本成分是基本积和基本和，而主析取范式和主合取范式的基本成分是极小项和极大项，它们分别是特殊的基本积和基本和。 p，q的极小项为：p∧q，p∧?q，?p∧q，?p∧?q 定义1.5.5在基本积中，每个变元及其否定不同时存在，但两者之一必须出现且仅出现一次，这样的基本积叫做布尔合取也叫小项或极小项。 表1.12是两个变元p和q的极小项的真值表。极小项有下列的性质： 两个命题变元的极小项共4(=22)个, 三个命题变元的极小项共8(=23)个, …。一般地说，n个命题变元共有2n个极小项。 表1.12 p q p∧q p∧?q ?p∧q ?p∧?q 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 表1.13 极小项 成真赋值 名称 ?p∧?q 00 m0 ?p∧q 01 m1 p∧?q 10 m2 p∧q 11 m3 ⑴每个极小项只有一个成真赋值，且各极小项的成真赋值互不相同。极小项和它的成真赋值构成了一一对应的关系。可用成真赋值为极小项进行编码，并把编码作为m的下标来表示该极小项，叫做该极小项的