第一章 命题逻辑 1.5联结词的完备集
1.5联结词的完备集
定义:设S是一个联结词集合,如果任何n (n>1)元真值函数都可以由仅含S的联结词构成的公式表示,则称S是联结词的完备集。
在讲完备集之前,先给大家补充几个联结词。我们知道一个有两个命题变元p,q构成的命题公式中p,q的组合真值情况有4种,而每种所对应的都有0,1两种情况。所以共有=16种情况。如图:
有些版本的异或也表示为⊕,清华大学出版社那个版本在此节并没有提及这里补充的前两个联结词。这里也不再详细说了,细心的读者可能会发现异或的真值表和我们之前讲的不可兼并或一样。
来道例题:
注意:与非和或非都不满足结合律