野味少女心1.2 命题公式和真值赋值
[教学重点] 合式公式及层次，解释的含义，真值表的构成。
[教学目的]1：使学生了解合式公式和公式层次的定义，理解递归定义法的方法。 2：学会描述公式的形成过程。
3：理解解释的含义，领会公式分类的要点。
4：使学生了解并学会应用真值表的构成方法。
5：复习并进一步理解命题逻辑的基本概念。 [教学准备]
[教学方法]讲述法 [课时安排]二课时。 [教学过程] 讲述： 复习并示例：判断是否式命题，如果是，则符号化。
1) 922+97+1； 2) x + 5 > 6
3) 理发师只给所有那些不给自己理发的人理发；（罗素悖论） 4) 李兰现在在宿舍或在图书馆里； 5) 蓝色和黄色可以调配成绿色；
6) 如果晚上小王做完了做业并且没有其他事情，他就看电视或看电影。 问题： 在6)中获得一个长串的字符串，这里当然表示了一个命题，但是不是任何一个字符串能表示一个命题呢？或者称为命题公式呢？
抽象地说，命题公式是由命题常项、命题变项、联结词、括号等组成的符号串，但并不是由这些符号任意组成的符号串都是命题公式。 板书 1.2合式公式及其解释 讲述： 首先自然先要了解什么公式。 板书：
一 合式公式
1) 合式公式：
(1) p, q, r, … ,1 , 0 是合式公式；
(2) 如果A是合式公式，则?A也是；
(3) 如果A和B是合式公式，则?p、p ? q、p ? q、p ? q、p ? q也是； (4) 有限次应用(1)-(3)构成的符号串才是合式公式。 讲述： 上述定义方法称为递归定义法（递归就是一个过程直接或间接地调用自己），递归法定义是离散数学中常用的方法。其中，（1）是递归定义的基础，直接规定简单的内容；（2）, （3）是递归定义的归纳，规定了是由简单到复杂的过程；（4）是递归定义的界限，规定了满足前述（1）~（3）条件的最小范围。（递归算法在计算机中容易实现，如C语言中的汉诺塔、n的阶乘、求两个数的最小公约数就是用递归的方法实现的）
板书：
递归定义法：递归基础、递归归纳、递归界限 讲述
在一个复杂的公式中，为了避免歧义需要引进许多的括号，但如果括号太多会使人眼花缭乱，如((p?(q?r))?((p?q)?(r?s)))，共有6对括号，书写简单，可以省略括号 板书：
省略括号的约定：
(1) 公式最外层的括号可以省略；
(2) 规定联结词的运算优先级别由高到低是：?、?、?、?、?，若无括号，优先级高的先运算；
(3) 若同一个联结词连续多次出现且无括号，则按从左到右的顺序运算。 讲述：
按照上述约定，((p?(q?r))?((p?q)?(r?s)))省略了三对括号简化为p?(q?r) ?(p?q)?(r?s)。省略括号只是让公式书写简便，但并不能改变其复杂性。 示例
(1) (((p?q)∧(q?r)) ?(p∨r)) p、q是公式，(p?q)是公式；q、r是公式，(q?r)是公式；((p?q)∧(q?r))是公式；p、r是公式，(p∨r )是公式；(((p?q)∧(q?r)) ?(p∨r))是公式。 这样一个命题公式的形成过程简单表述为： p，q，(p?q)；q，r，(q?r)；((p?q)∧(q?r))；p，r，(p∨r)；(((p?q)∧(q?r)) ?(p∨r))。 (2) ((p∧q)?qr) p，q，(p∧q)；q，r，qr不是；((p∧q)?qr)不是。 讲述： 显然，有些公式的字符串很长，有些很短，甚至只有单个字母，这样公式的复杂性必然有所不同，为了描述这种复杂性，引入公式层次来描述。 板书：
二 合式公式的层次：
(1) 如果A是单个命题常项或命题变项p,q,r,s,…,0,1，则称A是0层公式； (2) 称A是n+1(n?0)层公式，是指A符合下列情况之一： (a) A=?B，B是n层公式；
(b) A=(B?C)，其中B、C分别是i层和j层公式，且n=max(i,j)； (c) A=(B?C)，其中B、C的层次同(b)； (d) A=(B?C) ，其中B、C的层次同(b)； (e) A=(B?C)，其中B、C的层次同(b)； 示例：
(1) (p?q)∨(r∧(p∨s)) (2) ?q?(p∨s)
(1) p, s是0层公式，p∨s是1层公式; r是0层公式, r∧(p∨s)是2层公式；p,q是0层公式，但p?q是1层公式；(p?q)∨(r∧(p∨s)) 是3层公式。公式层次是3。
(2) q是0层公式, ?q是1层公式；p, s是0层公式，p∨s是1层公式; ?(p∨s) 是2层公式；但?q?(p∨s)不是公式。 讲述：
一般来说，一个含有命题变项的命题公式，其真值是不确定的。只有给其每个命题变项都指定确定的真值，命题公式才会有确定的真值。
给定一个真值，就是给命题变项一个赋值，相当于给定一个日常语言中某个具体的句子，即给定一个解释。 板书：
三 真值赋值
令A是一命题公式，p1,p2,…pn是出现在A中的所有命题变项，给p1,p2,…pn指定一组真值，称为对A的一个赋值或解释。
成真赋值：若指定的一组值使得A的值为真，称这组值为A的成真赋值； 成假赋值：若指定的一组值使得A的值为假，称这组值为A的成假赋值。 一个含有n个命题变项的命题公式，共有2n个赋值。 示例
例 已知A是含命题变项p,q,r的命题公式，其成真赋值为000,010,101，求?A的成真赋值和成假赋值。
?A的成真赋值为：001,011,100,110,111；成假赋值为：000,010,101。
例 已知A、B是含命题变项p,q,r的命题公式，A成真赋值为000, 011, 111，B成真赋值为000, 010, 100，求A?B、A?B的成真赋值。
A?B：000,001,010, 100,101,110,111 A?B：000,001,101,110 讲述： 上面是用具体的真值来指定，如果用另外的命题公式来指定，这时再不能称为赋值了，这称为替换。 板书：
替换实例：用命题形式B1,B2,…Bn分别替换命题形式A中的命题变项p1, p2,…pn得到的新的命题形式。 示例：
例如，p?(?p?q)，以p?q替换p，以r替换q，则得到原式的一个替换实例为(p?q)?(? (p?q )?r)。 讲述：
我们知道一个公式有多个赋值，一般来说既有成真赋值，又有成假赋值，但完全可能只有成真赋值，或全是成假赋值，
根据这种不同，我们将公式分成不同类型。 板书：
命题公式的分类：
① 重言式：值总是为真的命题公式。 讲述：
如果一个蕴涵式A?B是重言式，则记作A?B，表示由A可推导出B；同样如果一个等价式A?B是重言式，则记作A?B，表示A和B等值。
注意：?和?不是逻辑联结词，它们表示的分别是逻辑推理和逻辑等值运算，下面的章节将分别讨论。 板书：
② 矛盾式：值总是为假的命题公式。
③ 可满足式：至少存在一组赋值是成真赋值的命题公式。 讲述：
从定义看来，重言式也是可满足式，不过还是将命题公式分成三类：重言式、矛盾式、可满足式。这种分类主要是为了体现重言式的重要性，实际上在命题逻辑中公理、定理都
是重言式，在自然推理的过程中，一个正确的推理也必须是重言式。 板书：
设A是命题公式，则
(1) 若A是重言式，则A的任何替换实例都是重言式； (2) 若A是矛盾式，则A的任何替换实例都是矛盾式； 示例： 例 合式公式(p∧q)∨?(p∧q)、(p∧q?r)∨?(p∧q?r)都是p∨?p的一个替换实例，而p∨?p是重言式，所以它们也是重言式。 板书：
四 真值表
1) 定义：将命题公式A在所有赋值之下取值的情况列成表，称为A的真值表 讲述：
所有命题变项取一组值，即是命题公式的一个赋值，所以真值表包含了所有赋值情况下的公式所取得的值。
而一个赋值使得公式为真，就称为成真赋值，为假就是成假赋值，所以从真值表可以直接获得一个命题公式的成真赋值、成假赋值。 板书：
2) 构造方法：
①找出给定命题公式中的所有命题变项，列出所有可能的取值：
p q T F T F r T T T T F F F F T F ②由低到高列出命题公式的各层次；
③计算各层次的的值，直至最后计算命题公式的值。
示例
例 1.16 构造合式公式(p∨ (p∧q)) ?? (p∨q)的真值表： 真值表： p q p∧q p∨ (p∧q) p∨q ?(p∨q) (p∨(p∧q)) ??(p∨q) 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 0 0
讲述：上述真值表的构成方法中，如果公式层次比较高，则表的宽度将变得很宽，甚至无法写下，因此可采用另一种形式， 板书：
② 按照公式形成过程，标出各层对应的联结词所对应的真值； ③ 直至最后计算命题公式的值。 示例：
p q 0 0 0 1 1 0 1 1 步骤 (p ∨ (p∧q)) 0 0 0 0 1 0 1 1 ② ① ? ? 1 1 1 0 0 0 0 0 ③ ② (p∨q) 0 1 1 1 ①
讲述：
最后，复习一下本节所讲述的内容。 作业：
