下载文档原格式
第二节 命题公式及其真值表在上节中，用,,p q r L 表示确定的简单命题。
简单命题又称为命题常项或命题常元。
命题常项有确定的真值。
在数理逻辑中，不仅要研究具体的逻辑关系，还要研究抽象的逻辑关系，因而不仅要有命题常项，还要有命题变项。
称真值可以变化的简单陈述句为命题变项或命题变元，仍然用,,p q r L 表示命题的变项。
命题常项、命题变项及联结词可按下述定义合式的公式。
定义2.1 （1）单个的命题变项（或常项）是合式公式；（2）若A 是合式公式，则（¬A ）也是合式公式；（3）若A ，B 是合式公式，则（A ∧B ），（A ∨B ），（A →B ），（A ↔B ）也是合式公式；（4）有限次地应用（1）～（3）形成的符号串都是合式公式。
这样定义的合式公式也称为命题公式，简称公式。
单独使用（¬A ），（A ∧B ），（A ∨B ），（A →B ），（A ↔B ）时，外层括号可以省去，即可写成¬A ，A ∧B ，A ∨B ，A →B ，A ↔B 。
在定义 2.1.中出现的A ，B L 是用来表示任意的合式公式的。
在以下的论述中出现的A ，B ，C 等也同样是用来表示任意公式的。
定义2.2 设1p ，2p L ，n p 是出现在公式A 中的全部的命题变项，给1p ，2p L ，np 各指定一个真值，称为A 的一个赋值或解释。
若指定的一组真值使A 的真值为1，则称这组真值为A 的成真赋值（或成真解释）。
若指定的一组真值使A 的真值为0，则称这组真值为A 的成假赋值（或成假解释）。
本书中对含n 个命题变项的公式的赋值形式做如下规定：（1）设A 中含的命题变项为1p ，2p L ，n p ，赋值12n a a a L （i a 为0或1）是指11p a =，22p a =，L ，n n p a =。
（2）若出现在A 中的命题变项为p ，q ，r ，L ，赋值12n a a a L 是指1p a =，2q a =，L ，即按字典顺序赋值。
离散数学命题公式和真值表第2讲命题常项犹如数学中常量（a,b,c ）命题变项犹如数学中变量（x,y,z ）确指的或具体的命题。
命题常项命题变项不确指的或抽象的命题。
命题常项与命题变项都用p,q,r…等表示。
对命题变项p而言，p只是一个标识，可以用任何一个具体的命题替代。
命题公式将命题常项（即1，0）和命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。
(1)(2)单个命题常项和命题变项是命题公式，称为原子公式。
若A是命题公式，则(⎤A)也是命题公式。
(3)若A，B是命题公式，则(A∧B)，(A∨B)，(A→B)，(A↔B)也是命题公式。
(4)由有限次地应用(2)~(3)形成的符号串是命题公式。
定义2.1（命题公式）注意1设A是公式，B为A中连续的一部分，若B也是公式，则称B为A的子公式。
2公式最外层的括号可以去掉。
注意3优先级规定（1）各联结词运算的优先级为：⎤，∧，∨，→，↔。
（2）对于同一级者一目，从右向左二目，从左到右（3）括号优先，从里到外。
注意根据运算优先级的规定不必要的括号也可以去掉。
如:（p∨q)∨(⎤r)可写为p∨q∨⎤r真值表公式的解释和赋值将公式中的每个命题变项都指定一个具体的命题，抽象的公式就具有了实际的意义，成了命题，具有了真值，这称为公式的解释。
对公式的解释相当于是将指定为真（假）命题的命题变项赋值1（0）。
真命题假命题赋值1赋值0命题变项定义2.2（公式的赋值）设p1 ，p2 ，…，p n是出现在公式A中的全部的命题变项，给p1，p2，…，p n各指定一个真值，称为对A的一个赋值。
定义2.2（公式的赋值）将n个命题变项按下标顺序或字典顺序排列后，赋值就相当于一长为n的0，1字符串。
思考含有n个命题变项的公式共有多少个不同的赋值？SAT（适定性问题）给一个命题公式，它是否存在一个成真赋值？1971年Cook证明：SAT问题是（第一个）NPC问题。
定义2.3（真值表）将命题公式A在所有赋值下取值情况列成表，称做A的真值表。
合式公式的定义合式公式是逻辑学中的一个重要概念，指用逻辑符号和命题变元构造而成的公式。
这些公式可以通过逻辑推理得到真或假的结果。
在逻辑学中，合式公式的定义基础是命题逻辑的语义，即命题的真假。
合式公式的定义首先，我们需要知道什么是命题变元。
命题变元是可以代表一个确定命题的符号，代表具有不同意义的不同字母，如P、Q、R、S等。
合式公式由命题变元和逻辑符号组成，逻辑符号包括否定、合取、析取、蕴含和双重蕴含等符号。
符合一定语法规则的合式公式也叫做公式，不符合语法规则的则是非法的。
例如，P∧Q是一个合式公式，表示“P和Q都为真时，命题为真。
”P∨Q也是一个合式公式，表示“P或Q 为真时，命题为真。
”同样，~P是一个合式公式，表示“P 为假时，命题为真。
”用逻辑符号构造出来的符号串如果符合语法定义规则，则有语义定义：它表示的是命题。
这个命题的真假是与符号串所包含的命题变元和逻辑符号有关，这些符号串的不同组合方式构成了不同的命题，从而形成了不同的合式公式。
以P、Q、R为命题变元，构造一些公式：P∧Q Q∨R (P∧Q)∨R ~(P∨Q) P→Q在逻辑学中，这些公式可以通过逻辑推理得到真或假的结果。
例如，当P为真，Q为假，R为真时，第三个公式为真，其他都为假。
这种逻辑推理的结果也被称为该公式的语义值。
Formal Deduction System的定义为了进一步理解合式公式的定义，我们需要了解形式演绎系统（Formal Deduction System），它是一种系统，可以用来推导命题公式的真假。
形式演绎系统包括符号集合、公理、推理规则。
符号集合由命题变元和逻辑符号组成，公理是前提，它可以由逻辑公理、定义、假设等构成；推理规则规定了如何从前提中推出结论。
严格执行公理和推理规则，我们可以通过形式演绎系统来证明合式公式的真假。
总结合式公式是一个重要的概念。
其定义基于逻辑符号和命题变元构造出来的公式，这些公式可以通过逻辑推理得到真或假的结果。
