命题逻辑中的推理方法(2)
数理逻辑的主要任务是用数学的方法研究推理.所谓推理是指从前提出发推出结论的思文过程，而前提是已知的命题集合，结论是从前提出发应用推理规则推出的命题公式.[2]
设 和 都是命题公式，若对于 和 中出现的命题变项的任意一组赋值，或者 为假，或者当 为真时 也为真，则称由前提 推出结论 的推理的是有效的或正确的，并称 是有效的结论.[2]
设 都是命题公式, 当且仅当
,
称B是 一组前提的有效结论.
命题公式 推B的推理正确当且仅当
是重言式.
2.真值表法
2.1真值表的定义
设 是公式 中的所有的命题变项，给 各指定一个真值，称为对 的一个赋值或者解释.假如指定的一组值使得 为1，则称这组值为 的一组成真赋值；若使得 为0，则称这组值为 的一组成假赋值.
将命题公式 在全部赋值下的取值情况列成表，称为 的真值表.
2.2构造真值表的具体步骤
（1）首先找出公式中所含的全部命题変项 (若无下角标命题变项就按字母顺序排列)，列出 个赋值情况，从00 0开始赋值，然后按二进制加法顺次写出每个赋值，直到写到11 1为止.
（2）然后按从低到高的顺序写出所有公式的各个层次.
（3）最后对应各个赋值计算出各层次的真值，直到计算出公式的真值.
如果两个公式 与 的真值表对所有赋值最后一列都相同，即最后结果都相同，则称这两个真值表相同，而不考虑构造真值表的中间过程.[2]
要想知道推理是否正确就是判断其是不是重言式，所以可以用真值表法判断推理是否正确.
例2.1 判断推理 是否正确.
解：此推理的形式结构为
下一篇：内部排序算法的时间复杂度分析