离散数学04861.pptVIP

1.8 命题公式的范式 1.8.1 基本积与基本和 1.8.2 合取范式与析取范式 1.8.3 小项与大项 1.8.4 主合取范式与主析取范式 1.8.1 基本积与基本和 基本积 仅由命题变量或其否定构成的合取式 单个命题变量或其否定 基本和 仅由命题变量或其否定构成的析取式 单个的命题变量或其否定 P∧Q∧┐R，P∧P∧┐Q，P，┐P都是基本积 P∨Q∨┐R，P∨P∨┐Q，P，┐P都是基本和 1.8.2 合取范式与析取范式 合取范式(conjunction normal form) A ? A1∧A2∧…∧An(n≥1) 其中Ai(i＝1,2,…,n)为基本和 析取范式(disjunction normal form) A ? A1∨A2∨…∨An(n≥1) 其中Ai(i＝1,2,…,n)为基本积 1.8.2 合取范式与析取范式 例1.8.1 求(P→Q)→R的合取范式与析取范式 解 (P→Q)→R ?┐(┐P∨Q)∨R ?(P∧┐Q)∨R （析取范式） ?(P∨R)∧(┐Q∨R) （合取范式） 1.8.2 合取范式与析取范式 例1.8.2求P→((Q∧R)→S)合取范式析取范式 解P→((Q∧R)→S) ?┐P∨(┐(Q∧R)∨S) ?┐P∨((┐Q∨┐R)∨S) ?┐P∨┐Q∨┐R∨S （析取范式） ?(┐P∨┐Q∨┐R∨S) （合取范式） 1.8.3 小项与大项 定义1.8.1 含n个命题变量的基本积，称作布尔合取(Boolean conjunction) 或小项(miniterm) ，当且仅当每个命题变量与其否定不能同时存在，但两者必须出现一个且仅一个。 P,Q,R的小项 二进制编码 P∧Q∧R m111 P∧┐Q∧┐R m100 ┐P∧Q∧┐R m010 ┐P∧┐Q∧R m001 ┐P∧Q∧R m011 P∧┐Q∧R m101 P∧Q∧┐R m110 ┐P∧┐Q∧┐R m000 1.8.3 小项与大项 定义1.8.2 含n个命题变量的基本和，称作布尔析取(Boolean disjunction) 或大项(maxterm) ，当且仅当每个命题变量与其否定不能同时存在，但两者必须出现一个且仅一个。 P,Q,R的大项 二进制编码 P∨Q∨R M000 P∨┐Q∨┐R M011 ┐P∨Q∨┐R M101 ┐P∨┐Q∨R M110 ┐P∨Q∨R M100 P∨┐Q∨R M010 P∨Q∨┐R M001 ┐P∨┐Q∨┐R M111 1.8.3 小项与大项 相同变元的小项与大项,有mi? ┐Mi P∨Q∨R 000 ┐P∧┐Q∧┐R P∨┐Q∨┐R 011 ┐P∧Q∧R ┐P∨Q∨┐R 101 P∧┐Q∧R ┐P∨┐Q∨R 110 P∧Q∧┐R ┐P∨Q∨R 100 P∧┐Q∧┐R P∨┐Q∨R 010 ┐P∧Q∧┐R P∨Q∨┐R 001 ┐P∧┐Q∧R ┐P∨┐Q∨┐R 111 P∧Q∧R 1.8.3 小项与大项 每个小项当其真值指派与其编码相同时，其真值为1；否则为0。 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.8.3 小项与大项 每个大项当其真值指派与其编码相同时，其真值为0；否则为1。 P Q P∨Q P∨┐Q ┐P∨Q ┐P∨┐Q 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1