离散数学第二章谓词逻辑--节.pptVIP

（四）量词分配公式(等价式和蕴含式)1.(?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x)E232.(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)E24我们称(1)为“?对∨满足分配律”，(2)为“?对∧满足分配律”。但是要注意：“?对∨”以及“?对∧”不存在分配等价式。即,(?x)(A(x)∧B(x))?((?x)A(x)∧(?x)B(x))(?x)(A(x)∨B(x))?((?x)A(x)∨(?x)B(x))3.(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)I184.(?x)A(x)∨(?x)B(x)?(?x)(A(x)∨B(x))I17第29页，共57页，星期日，2025年，2月5日例1、(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)解释：个体域是party中的人。A(x)：x唱歌，B(x)：x跳舞则(?x)(A(x)∧B(x))表示：party里的所有人既唱歌又跳舞；(?x)A(x)∧(?x)B(x)表示：party里的所有人唱歌且party里的所有人都跳舞。两者意义是相同的。即有：(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)第30页，共57页，星期日，2025年，2月5日例2.(?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x)解释：个体域是party中的人。A(x)：x唱歌，B(x)：x跳舞则(?x)(A(x)∨B(x))表示：Party中有些人唱歌或跳舞；(?x)A(x)∨(?x)B(x)表示：Party中有些人唱歌或Party中有些人跳舞。两者意义是相同的。所以,(?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x)第31页，共57页，星期日，2025年，2月5日注意公式3.和4.不是等价公式，是重言蕴含式。3.(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)解释：个体域是party中的人。A(x)：x唱歌，B(x)：x跳舞(?x)A(x)∧(?x)B(x)：Party中有人唱歌，且有人跳舞。(?x)(A(x)∧B(x))：Party中有人既唱歌又跳舞。(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)(?x)A(x)∧(?x)B(x)?(?x)(A(x)∧B(x))所以说(?x)(A(x)∧B(x))与(?x)A(x)∧(?x)B(x)不等价。第32页，共57页，星期日，2025年，2月5日公式44.(?x)A(x)∨(?x)B(x)?(?x)(A(x)∨B(x))解释：个体域是party中的人。A(x)：x唱歌，B(x)：x跳舞(?x)A(x)∨(?x)B(x)：所有人都唱歌或者所有人都跳舞。(?x)(A(x)∨B(x))：所有人都唱歌或跳舞。(?x)A(x)∨(?x)B(x)?(?x)(A(x)∨B(x))(?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x)所以，?x)A(x)∨(?x)B(x)与(?x)(A(x)∨B(x))不等价。第33页，共57页，星期日，2025年，2月5日公式1的证明(自学)求证1.(?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x)证明：设个体域为{a1,a2,....,an}，(?x)(A(x)∨B(x))?(A(a1)∨B(a1))∨(A(a2)∨B(a2))∨…∨(A(an)∨B(an))?(A(a1)∨A(a2)∨...∨A(an))∨(B(a1)∨B(a2)∨...∨B(an))?(?x)A(x)∨(?x)B(x)第34页，共57页，星期日，2025年，2月5日公式3的证明（自学）证明3.(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)如果(?x)(A(x)∧B(x))为真则存在a使A(a)∧B(a)为真，故该a使A(a)为真，该a使B(a)为真所以(?x)A(x)为真，所以(?x)B(x)为真，故(?x)A(x)∧(?x)B(x)为真证明：假设前件(?x)(A(x)∧B(x))为真，则个体域中至少有一个客体a，使得A(a)∧B(a)为真，于是A(a)和B(a)都为真，所以有(?x)A(x)以及(?x)B(x)为真进而得(?x)A(x)∧(?x)B(x)为