3．1 用真值表证明推理的无效性
一个推理是有效的，我们可以为其建立一个形式证明。形式证明运用推理规则说明，结论是从前提推演出来的，因此前提真时结论不可能假，推理当然就是有效的。
如果推理是无效的，那么运用推理规则不可能从前提推演出结论。所谓不可能是指：无论怎样推演都推不出结论形式的命题公式。形式证明并没有规定推演到多少步就必须中止。因此，对于无效推理我们面临的是一个无法穷尽的推演过程。这意味着形式证明方法不能证明推理是无效的。
我们的命题逻辑系统不仅要能证明有效推理，而且还应该证明推理的无效性。因此，必须给出证明无效推理的方法。
真值表是判定推理是否有效的可靠方法。一个推理是有效的，那么前提真时结论必真。在真值表上表现为无论变元被赋予什么样的值，作为前提的命题公式真时，作为结论的命题公式一定是真的。如果一个推理是无效的，其前提真时结论可真可假。因此只要在真值表上找到一组变元的赋值使得前提真而结论假，那么推理就是无效的。
例10 用真值表判定下列推理是否有效。
C→（A∧B），A∨C / ∴ B→C
证：给出相应的真值表：
A B C A∧B C→（A∧B） A∨C B→C
T T T T T T T
* T T F T T T F
T F T F F T T
T F F F T T T
F T T F F T T
F T F F T F F
F F T F F T T
F F F F F F T
从标有“*”号的一行可见，两个前提是真的，而结论却是假的，即存在一组赋值使得推理的前提真而结论假。所以推理是无效的。
真值表的行数是由变元的数目决定的，有n个变元就有2n种赋值情况，真值表就有2n行。因此直接用真值表判定一个推理是否有效是很繁琐的。其实，如果推理是无效的，我们把完全不需要把整个真值表都列出来。因为推理是无效的，那么至少有一个例示使得推理形式的前提真而结论假。我们只需要把这个例示，即把使推理形式前提真而结论假的赋值情况列出来，就足以说明推理是无效的。
通过列举使推理形式前提真而结论假的赋值情况，以证明推理无效，这种方法被称作简化真值表方法。
例11 判定如下推理是否有效：
如果水稻长得好，那么水分充足并且肥料充足。只要风调雨顺，这块地就水分充足。所以，只要风调雨顺，那么如果这块地肥料充足水稻就长得好。
证： 首先将推理形式化：
令“水稻长得好”为A，“水分充足”为B，“肥料充足”为C，“风调雨顺”为D，该推理的形式如下：
A→（B∧C）
D→B
∴ D→（C→A）
只要找到一组对变元的赋值，使得推理的前提真而结论假，就足以证明该推理是无效的。现将这组赋列举如下：
A B C D A→（B∧C） D→B D→（C→A）
F T T T T T F
显然，与列出整个真值表相比较，简化真值表能够更清晰地说明推理的无效性。
3．2 用归谬赋值法证明推理的有效或无效性
上述简化真值表方法通过列出一组赋值，使得推理前提真而结论假，简洁清晰地证明了推理的无效性。但这种方法只适用于无效推理，它不能说明推理的有效性。下面讨论简化真值表的另一种形式——归谬赋值法。这种方法能证明一个推理的有效性。
归谬赋值法的基本思路同间接证明方法类似。我们要证明一个推理是有效的，先假设它无效，这就是归谬。然后根据假设对前提和结论进行赋值，即给命题公式的变元指派确定的真值，以使得推理的前提真而结论假。如果找到这样一组的赋值使得假设成立，那么就说明推理是无效的。我们可以运用上述简化真值表方法把这一组赋值列出来，以证明推理的无效性。
如果找不到使假设成立的赋值，那么就说明假设不成立，推理是有效的。所谓找不到使假设成立的赋值是指，根据假设对前提和结论赋值必将导致矛盾，即不可避免地要对同一个变元既赋值T又赋值F。
例12 判定下列推理是否有效：
A→（B∧C）
（C∨D）→F
∴ A→F
证： 假定推理无效，然后根据假定对前提和结论赋值：
A →（B ∧ C） （C ∨ D）→ F A → F
T T T T T F F F T F T F F
从上表可见，假设推理无效，则前提真结论假。结论蕴涵式“A→F”是假的，当且仅当“A”赋值真且“F”赋值假。当“A”的值为真时，必须对“B∧C”赋值真才能使前提“A→（B∧C）”真，因此“B”和“C”都必须赋值真。而“F”的值为假时，“C∨D”必须赋值假才能使前提“（C∨D）→F”真，因此“C”和“D”都必须赋值假。由此不可避免地导致对同一个变元“C”既赋值真又赋值假，这是矛盾。因此，假设不成立，该推理是有效的。
3．3 证明公式集合的协调性
简化真值表方法还可用于证明一个命题公式集合的协调性。一个公式集合的协调性也就是无矛盾性。一个命题公式集合是协调的，当且仅当，存在一组赋值使得该集合的每个公式都真。因此，只要把这样一组赋值列出来，就证明了公式集合的协调性。
例13 证明公式集合{A→（B∧?C），（B∨D）→E，A→E}是协调的。
证： 从如下简化真值表可见，该公式集合是协调的：
A B C D E A→（B∧?C） （B∨D）→E A→E
F T F T T T T T
如果找不到使公式集合的每个元素都真的赋值，那么公式集合是不协调的。对于这样的公式集合，如果假定公式集合的每个元素都真，再根据假设进行赋值，那么一定会导致矛盾。因此，我们一个不协调的公式集合是不可满足的。
例13 证明公式集合{（A∨B）→C，C→D，A∧?D}是不协调的。
证：先假定公式集合的每个元素为真，然后根据假设进行赋值：
（A ∨ B）→ C C → D A ∧ ? D
F F F T F F T F T T T F
从上表可见，假定公式集合的每个元素都真。“A∧?D”真则“A”必须赋值真而“D”赋值假。“D”是假的但“C→D”真则必须对“C”赋值假。既然“C”是假的，要使“（A∨B）→C”真则“A∨B”必假，因此必须对“A”和“B”都赋值假。由此不可避免地导致了“A”既真又假的矛盾。这说明我们找不到满足假设的赋值，因此，假设不成立，该公式集合是不协调的。
我们在1.2的讨论中指出，要推演出可靠的结论除了要求推理形式必须有效外，还要求前提是可靠的。而一个前提集合是可靠的它首先必须是协调的。不协调的公式集合可以推演出任何结论，包括推演出矛盾。现以例13给出的公式集合为例：
①（A∨B）→C P
② C→D P
③ A∧?D P
④ A ③∧-
⑤ A∨B ④∨+
⑥ C ①⑤MP
⑦ D ②⑥MP
⑧ ?D ③Com，∧-
⑨ D∧?D ⑦⑧∧+
第六讲 量化逻辑
