工科离散数学课件 第一章 1_5_命题公式的真值与逻辑等价(3) - 最小联结词组.pptx

1.5.3 联结词的功能完备集问：为什么定义9个联结词呢？ 答：2个变元有4种解释；每种解释命题有2种可能的真值，共24 种可能。由表所知，9个联结词能表示所有复合命题。pq10pq?p?qp?qp↑q1110110010101010010101100110010010001101pqp?qp↓qp→qp →C qp?qp—? qq→pq →C p1110101010101001011001101001010001101010 [联结词功能完备集]一个联结词集合，任何命题均可由此集合中的联结词表示出来。联结词功能完备集 = (功能完备的)联结词组。1.5 命题公式的分类与逻辑等价-最小联结词组长见识： 9个联结词集合是功能完备的。[最小联结词功能完备集(最小联结词组)] 联结词个数最少的功能完备集。问：{┐, ?, ?}是功能完备的吗？ 等价转换 ——重要p→q ? ┐p?qp?q ? (p→q)?(q→p)p—? q ? ┐(p?q)p→C q ? ┐(p→q)p↑q ? ┐(p?q)p↓q ? ┐(p?q)答：是。 问：功能完备最少需要多少个联结词？1.5 命题公式的分类与逻辑等价-最小联结词组答：1个。{↑}和{↓}都是最小功能联结词组。长见识：能用单个联结词（元件）表示任何复杂的逻辑能降低制造复杂性，是大规模集成电路能够实现的依据。等价转换┐p ? p↑pp?q ? (p↑p)↑(q↑q)p?q ? (p↑q)↑(p↑q)┐p ? p↓pp?q ? (p↓p)↓(q↓q)p?q ? (p↓q)↓(p↓q)——教材视频：命题逻辑作为模型描述语言-逻辑电路（门电路）；大规模集成电路制造；华为鲲鹏芯片的成功；发展集成电路与软件的国家政策；大有可为 1.5 命题公式的分类与逻辑等价-最小联结词组用于表决的电路2个开关控制的灯具的电路半加法器复合命题原子命题复合命题的表示集成电路：多个电子器件集成在一起。巨大规模集成电路（GSIC ，?109个组件）。我国集成电路产业已具备一定基础。 1.5 命题公式的分类与逻辑等价-最小联结词组——众志、C—Core、龙芯、汉芯