15.2 命题公式及其赋值
本章目录 · 1 节
本章导读
【15.2 命题公式及其赋值】命题常项表示一个真值固定的命题;命题变项是在0、1中取值的形式符号。它们与数学中的常量、变量类似。本节用p,q,r等作变项,A、B、C作任意公式的元语言名称。
【定义15.2.1 合式公式】递归定义:(1)单个命题变项或命题常项是原子公式;(2)若A是公式,则(¬A)为公式;(3)若A、B为公式,则(A∧B)、(A∨B)、(A→B)、(A↔B)都是公式;(4)只有经有限次应用这些规则得到的符号串才是公式。合式公式也称命题公式或命题形式。
由一个公式的构造过程得到的内部公式,称其子公式。例如(p∧q)→¬r包含p、q、r、p∧q、¬r及其自身;任取字符串片段未必为子公式。
【注15.2.1】A、B等用于谈论公式,是元语言;p∧q等具体表达式属于对象语言。不要把“公式名称A”理解为一定又有一个新变项A参与赋值。
外层括号和不影响运算次序的括号可省略,省略后只是严格递归公式的缩写。pq→r缺少p、q之间的联结词,不合式;p→r→q若按完全括号化的严格语法也不是原始公式,但采用上节省括号约定时可明确写成((p→r)→q)的缩写。原书一面给同级左结合约定、一面把这种串直接列为不合式,这里将严格语法与缩写分开,以免矛盾。教学及练习统一建议补全连续箭头的括号。
常数0、1可直接纳入语法,也可分别作为p∧¬p、p∨¬p的缩写;此处0、1不是新的自由变项。相同变项在同一次赋值下必须取相同值。
【定义15.2.2 公式层次】原子公式深度0;depth(¬A)=depth(A)+1;二元联结词◇满足depth(A◇B)=1+max(depth(A),depth(B))。若写成n+1层,必须允许n≥0,原书n≥1会漏掉¬p、p∧q等第一层公式,现予修正。层次是语法树深度,不是联结词总数,也不因冗余括号增加。
例如(¬p∧q)→r依次经历否定、合取、蕴涵,深度3;¬(p→¬q)∧((r∨s)↔¬p)深度4。命题常项若纳入原子语法,同样按深度0处理。
【解释与赋值】把变项解释成具体命题,可将公式变成确定的命题。例如(p∨q)→r中取p:2是素数,q:3是偶数,r:√2是无理数,得真命题;若r改成“√2是有理数”,其余不变,得假命题。为求值,只需知道这些命题的0、1值,不必保留自然语言内容。
【定义15.2.3】对公式涉及的每个变项指定0或1,称一个赋值。结果1称成真赋值,结果0称成假赋值。按p₁,…,pₙ或按p,q,r,…固定次序,用二进制串记赋值;必须先说明次序,例如011表示p=0,q=1,r=1,而不是按公式出现位置临时调换。
含n个不同变项共有2ⁿ个赋值。n=0时有一个空赋值,纯常量公式也能求值。含变项的公式不一定随赋值改变:p∨¬p一直为1,p∧¬p一直为0;因此不能说“有变项就必然真值不确定”。
例如(¬p₁∧¬p₂∧¬p₃)∨(p₁∧p₂)在000、110为1,在001、011为0;(p∧¬q)→r在011为1,在100为0。
【定义15.2.4 真值表】将公式在所有赋值下的值完整列出。构造步骤:列全体不同变项;按二进制从全0到全1列出2ⁿ行;按子公式从内到外计算;最后一列为完整公式。两个公式的中间列可以不同,只要在同一组变项、同一赋值下最后值全相同,就说真值表相同。
【例15.2.1】(1)F=(¬p∧q)→¬r,深度3,成假赋值仅011,其余七个成真。表中先列¬p、¬r、¬p∧q,再列F。
(2)G=(p∧¬p)↔(q∧¬q),深度3,左右恒为0,所有00、01、10、11均成真,无成假赋值。
(3)H=¬(p→q)∧q∧r,按左结合深度4。¬(p→q)要求p=1、q=0,却又与q合取,故八个赋值全假。
表中的F、G、H仅是列标题的公式名称,完整公式已在正文写出,不增加变项。(例完)
【定义15.2.5 公式类型】全部赋值均真为重言式或永真式;全部均假为矛盾式或永假式;至少一个赋值真为可满足式。重言式也属于可满足式;既有成真又有成假赋值,称非重言式的可满足式(偶然式)。互斥三分类应写“重言式、矛盾式、偶然式”,不能将有包含关系的“重言式与可满足式”当作互斥类别。
例15.2.1的F为偶然式,G为重言式,H为矛盾式。判断某个公式不是重言式,只需找一个成假赋值;断言它是重言式则必须覆盖所有赋值或给有效证明,不能只挑几个真例。
给定n个变项,语法上公式无穷多,真值函数却只有 种:输入有2ⁿ行,每行输出二选一。每个这样的布尔函数均可用基本联结词表达,后面的主析取范式给出系统构造。n=1时4种,n=2时16种;不要误写成2n或2²ⁿ。
【例15.2.2】比较五公式:F₁=p→q;F₂=p↔q;F₃=¬(p∧¬q);F₄=(p→q)∧(q→p);F₅=¬q∨p。
F₁、F₃的值向量均(1,1,0,1);F₂、F₄均(1,0,0,1);F₅为(1,0,1,1),不属于前两组。F₅是q→p的写法,不能因两边都有p、q就当作p→q。(例完)
【哑元】比较A、B时,取两者全部变项的并集作共同输入。某变项若根本没在A出现,给A的扩展真值表多加这一列只会重复结果,称其为A的哑元。更一般地,出现了却不影响函数值的变项也可叫非本质变项,例如p∨¬p中的p;须区别语法出现与语义相关。
【例15.2.3】以p,q,r为共同次序:F₁=p→q;F₂=¬q∨r;F₃=(¬p∨q)∧((p∧r)→p);F₄=(q→r)∧(p→p)。F₁不含r,F₂不含p。
因为(p∧r)→p及p→p均恒真,F₁与F₃相同,F₂与F₄相同。两组并不相同,例如100时前组0、后组1。与不同变项集合比较时,不能仅把两张四行表不对应地拼起来。(例完)
