Question

离散数学数理逻辑习题

在公理系统证明：A→(A→B)→B
//注：“在公理系统中”指的是只能使用三个公理
(1)A→(B→A)
(2)(A→(B→C))→((A→B)→(A→C))
(3)(~A→~B)→(B→A)
以及分离规则（MP）。请注意这一点。

Answer 1

主析取范式和主合取范式的概念应该知道吧？
等值演算：(¬p→q)→(¬q∨p)
=(p∨q)→(¬q∨p)=¬(p∨q)∨(¬q∨p)；（条件式转化为析取式）
=(¬p∧¬q)∨(¬q∨p)；（否定转移到到单个逻辑变量）
求主范式和将公式简化的过程正好相反，它要求每个子式都包含所有逻辑变量。这通常就需要用到具有“扩展”功能的运算律：
X=X∧1=X∧(Y∨¬Y)=(X∧Y)∨(X∧¬Y)；——主析取范式；
X=X∨0=X∨(Y∧¬Y)=(X∨Y)∧(X∨¬Y)；——主合取范式；
主合取范式：(¬p∧¬q)∨(¬q∨p)
=(¬p∨¬q∨p)∧(¬q∨¬q∨p)；（析取对合取的分配律）
=1∧(¬q∨p)=p∨¬q；——该主合取范式只包含一项；
主析取范式：(¬p∧¬q)∨(¬q∨p)
=(¬p∧¬q)∨(p∧¬q)∨(¬p∧¬q)∨(p∧q)∨(p∧¬q)；（扩展后面两个变量）
=(p∧q)∨(p∧¬q)∨(¬p∧¬q)；
至于成真赋值或成假赋值法，需要对各种逻辑联结词的真值表熟记于心：
(¬p→q)→(¬q∨p)
观察这个表达式，整体是一个条件式；条件式成真的赋值有3种，成假的赋值有1种；以成假赋值为例：原式的成【假】赋值要求：(¬p→q)真、(¬q∨p)假；
第一项(¬p→q)还是条件式，成真赋值有3：¬p真q真，¬p假q真，¬p假q假；即：
【p假q真】【p真q真】【p真q假】；
第二项(¬q∨p)是析取式，成假赋值有1：¬q假p假；即：【p假q真】；
将两项的要求组合，发现只有【p假q真】能同时满足两项，即：当且仅当【p假q真】时，原式结果为【假】。
对于二元逻辑式，只有4种赋值，排除这唯一的成假赋值，剩下的3种就是成真赋值。
主析取范式，就是成真赋值的析取；
主合取范式，就是成假赋值——取反——的合取，即【p真或q假】；（因为只有一组成假赋值，也就是主合取范式中只包含一项析取式，也就不用再作合取运算了。）