第62页，共113页，星期日，2025年，2月5日从列表可知，除命题常元F，T及命题变元本身外，命题联结词一共有9个就够了。为了方便，可规定其优先级，由高到低次序为?，?，?，?，?等。第63页，共113页，星期日，2025年，2月5日３.联结词功能完全组已知有9个联结词就够用了，能不能少呢？若能少，表明有些联结词的逻辑功能可由其他联结词替代。事实上，也确实如此，因为有下列等价式：P?Q??(P?Q)P?Q??(P?Q)P?Q??(P?Q)P?Q??(P?Q)可见，扩充的4个联结词?，?，?和?能由原有5个联结词分别替代之。第64页，共113页，星期日，2025年，2月5日又由命题定律：P?Q?(?P?Q)?(?Q?P)P?Q??P?QP?Q??(?P??Q)P?Q??(?P??Q)可知，原有5个联结词?，?，?，?和?又能由联结词组{?，?}或{?，?}取代。那么，究竟最少用几个联结词？就是说，用最少的几个联结词就能等价表示所有的命题公式。或者说，用最少的几个联结词就能替代所有联结词的功能。这便是所要定义的联结词功能完全组。第65页，共113页，星期日，2025年，2月5日定义1.5.2称G为联结词功能完全组，如果G满足下列两条件：①由G中联结词构成的公式能等价表示任意命题公式；②G中的任一联结词不能用其余下联结词等价表示。可以证明，{?，?}，{?，?}，{?，?}，{?}，{?}都是联结词功能完全组；而{?，?}，{?}，{?}，{?}，{?，?}都不是联结词功能完全组，但为了表示方便，仍经常使用联结词组{?，?，?}。第66页，共113页，星期日，2025年，2月5日1.6公式标准型——范式１.简单合取式与简单析取式定义1.6.1在一公式中，仅由命题变元及其否定构成的合取式，称该公式为简单合取式，其中每个命题变元或其否定，称为合取项。定义1.6.2在一公式中，仅由命题变元及其否定构成的析取式，称该公式为简单析取式，其中每个命题变元或其否定，称为析取项。第67页，共113页，星期日，2025年，2月5日例如，公式P，?Q，P?Q和?P?Q?P等都是简单合取式，而P，Q和?P为相应的简单合取式的合取项；公式P，?Q，P?Q，?P?Q?P等都是简单析取式，而P，Q和?P为相应简单析取式的析取项。注意，一个命题变元或其否定既可以是简单合取式，也可是简单析取式，如例中P，?Q等。第68页，共113页，星期日，2025年，2月5日定理1.6.1简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。定理1.6.2简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。第69页，共113页，星期日，2025年，2月5日２.析取范式与合取范式定义1.6.3一个命题公式A称为析取范式，当且仅当A可表为简单合取式的析取，即A?Ai；其中Ai为简单合取式，i=1，2，…，n。定义1.6.4一个命题公式A称为合取范式，当且仅当A可表为简单析取式的合取，即A?Ai；其中Ai为简单析取式，1≤i≤n。第70页，共113页，星期日，2025年，2月5日定理1.6.3对于任何一命题公式，都存在与其等价的析取范式和合取范式。求范式算法：①使用命题定律，消去公式中除?、?和?以外公式中出现的所有联结词；②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。第71页，共113页，星期日，2025年，2月5日３.范式的应用利用析取范式和合取范式可对公式进行判定。定理1.6.4公式A为永假式的充要条件是A的析取范式中每个简单合取式至少包含一个命题变元及其否定。定理1.6.5公式A为永真式的充要条件是A的合取范式中每个简单析取式至少包含一个命题变元及其否定。第72页，共113页，星期日，2025年，2月5日４.范式不唯一性第73页，共113页，星期日，2025年，2月5日1.7公式的主范式范式基本解决了公式的判定问题。但由于范式不唯一性，对识别公式间是否等价带来一定困难，而公式的主范式解决了这个问题。下面将分别讨论主范式中的主析取范式和主合取范式。第74页，共113页，星期日，2025年，2月5日１.主析取范式(1)小项的概念和性质定义1.7.1在含有n个命题变元的简单合取式中，若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现一次，则称该简单合取式为小项，或布尔积。第75页，共113页，星期日，2025年，2月5日例如，两个命题变元P和Q，其构成的小项有P?