第四讲 对偶定理、主合取范式、数字电路设计
1.1. 对偶定理
对偶定理针对布尔运算式,是 De.Morgan 率的简单推论。对偶定理的一个最重要的应 用是主范式取非。 对偶定理: L( p1 , , pi , , pn ; , ) 是布尔运算式,那么
L( p1 , , pi , , pn ; , ) = L(p1 , , pi ,, pn ; , )
按照构造定理 理,
A B = ( A B ) = ( A B ) = ( A B ) = M 10 = {M 10 }
也即 即由 A B = F 对应的取 取值情况 A = T , B = F 指定的大项 指 M 10 = A B 。同样由 由
有
A « B = (A B) ( A B)
L ¢( p1 , , pi , , pn ; , ) 为 使 L( p1 , , pi , , pn ; , ) = F 所 有 p1 , , pi , pn 取 值 情
况对 对应大项的合 合取。 证明:对 L( p1 , , pi , pn ; , ) 的主析取范 范式取非,应 应用对偶定理 理可得。证毕。 例如:
因此
( x Î A x Î B x Î C ) x Î C = {M 000 , M 010 , M 100 }
( x Î A x Î B ) x Î C , ( x Î A x Î B x Î C ) x Î C 的主合取范式相同,所以 ( x Î A x Î B ) x Î C = ( x Î A x Î B x Î C ) x Î C
因此
( x Î A x Î B) x Î C = {M 000 , M 010 , M 100 }