德摩根定律
德摩根定律的集
对于套装,De Morgan的法律只是关于集合与其补充之间关系的观察。可视化这些规则的简单方法是通过Venn图。
观察两组互补的结合。在维恩图,这个联盟涵盖了除了两个集合的交集在维恩图的所有空间。因此,德·摩根定律为两个集合的交集的补充。
两套交叉口的补充
的集合的交集的补 和 等于联盟 和 。
观察的两套互补的交集。在维恩图,这个路口涵盖除两套工会在维恩图的所有空间。因此,德·摩根定律为两套工会的补充。
补的两套联盟
套装联盟的补充 和 等于的交点 和 。
德摩根定律可以推广到任意数量的集合。
集的交集的补泛化
让 是一组 套。这些集合的交集的补充是:
这 和 上面的符号用于表示许多集合的交叉点或联盟。例如,假设有四组: 那 那 , 和 。这些集合的联盟可以由 。然而,它可以更简洁地表示 。
设置的联盟补的泛化
让 是一组 套。这些集合的补充是:
因为这些概括需要找到许多套件的联合和交叉点,所以重要的是考虑包容和排斥的原理在用De Morgan的法律计算集的基数时。
德摩根定律的逻辑命题
De Morgan的法律遵循类似的逻辑主张结构。这些概念的语言似乎令人恐惧,但概念本身就是相当简单的。
否定命题的结合
两个命题的结合的否定 和 相当于这些命题否定的分离。
这可以用命题的真理表确认 和 :
“草坪需要割草和汽车需要洗涤,但我不会做两者,但我不会做什么。”
这两个命题是“我会修剪草坪”,“我会洗车。”简单的声明更改为“或”声明,否定这些命题:
“要么我不会割草坪,要么我不会洗车。”
请注意,这个说法叶打开琐事一个完成的可能性,这也有可能是既不琐事完成。
否定命题的分离
两个命题的析取的否定 和 相当于这些命题否定的联合。
这可以用命题的真理表确认 和 :
什么是等效的声明,“这是不是这样的,狗是棕色或黑色的。”?
这两个命题是“狗是棕色”,“狗是黑色的”。只需将声明更改为“和”声明并否定每个命题:
“狗是不是棕色的,它不是黑色的。”
或者,可以用“既不”和“也不”构建等同的陈述:
“狗既不是棕黑色的,也不。”
De Morgan的法律可以推广到任何一个主张。
否定结合否定的概括
让 是一组 命题。对这些命题的结合的否定相当于否定的否定:
析取的否定的泛化
让 是一组 命题。这些命题的析取的否定是相当于其否定的结合:
应用于逻辑门
在计算机工程中,一个NAND逻辑门被认为是普遍的,意味着任何逻辑门可以单独从NAND门构造。了解De Morgan的法律可以帮助一个了解如何制定这些建筑。
一种与非门有两个输入端, 和 。这些输入中的每一个都可以具有值 (为了高的) 或者 (为了低的)。
输出, ,NAND门的是 只有两个输入都是如此 。否则,输出是 。
非门的建设
一种非门否定信号。如果输入是 ,然后输出将是 , 和反之亦然。
考虑如何从NAND门构成NOT GATE。如果信号相同, ,被路由到NAND门的两个输入,然后输入将看起来像上面的NAND的真实表的顶行或底行。因此,NAND门将产生否定信号。
施工A和门
一个和门工作就像一个逻辑的联合。如果两个输入信号都 ,然后输出信号是 。否则,该输出信号是 。
考虑如何与门可以从与非门来构造。由于NAND门产生的一个与门的否定,就足够了再次否定信号。这可以用NOT建设上面来完成。
或门的建设
一个或门工作就像一个逻辑分离。如果两个输入信号都 ,然后输出信号是 。否则,该输出信号是 。
考虑如何OR门可以从与非门来构造。特别是,考虑德摩根定律如何应用。通过德摩根定律,一种NAND乙相当于A或B(该上划线表示信号的否定)。因此,OR门可以通过否定NAND门的每一输入来构造。
类似地,NOT,AND和OR门可以单纯从NOR(否定OR)门构成。NAND和NOR门也可用于构建衍生的逻辑门,XOR和XNOR。实际上,任何由任意数量的输入和输出的真值表可以仅由与非门或或非门构成。