离散数学（3）——谓词逻辑 个体 将可以独立存在的客体（具体事务或抽象概）称为个体或个体词，并用a,b,c,…表示个体常元，用x,y,z,…表示个体变元。（个体的函数还是个体） 将个体变元的取值范围称为个体域，个体域可以是有穷或无穷集合。人们称由宇宙间一切事物组成的个体域为全总个体域 谓词 将表示个体性质或彼此之间关系的词称为谓词，常用F,G,H,…表示谓词常元或谓词变元，用F(x)表示“x具有性质F”，用F(x,y)表示“x和y具有关系F” 量词、全称量词 称表示数量的词为量词 全称量词是在自然语言中的“所有的”、“一切的”、“任意的”、“每一个”、“都”等的统称 用符号“∀”表示 用∀x表示个体域里的所有x 用∀xF(x)表示个体域里所有x都有性质F 存在量词 存在量词是自然语言中的“有一个”、“至少有一个”、“存在着”、“有的”等的统称 用符号“∃”表示 用∃x表示存在个体域里的x 用∃xF(x)表示个体域里存在x具有性质F 命题符号化 一阶逻辑中命题符号化的两个基本公式 个体域中所有有性质F的个体都有性质G，应符号化为∀x(F(x)→G(x)) 个体域中存在有性质F同时有性质G的个体，应符号化为∃x(F(x)∧G(x)) 一阶谓词逻辑公式及其分类
简称公式，它的形成规则类似于命题逻辑公式 在公式∀xA和∃xA中，称x为指导变元，称A为相应量词的辖域。在∀x和∃x的辖域中，x的所有出现都称为是约束出现，A中不是约束出现的变元称为自由出现 解释 对于给定的公式A，如果指定A的个体域为已知的D，并用特定的个体常元取代A中的个体变元，用特定函数取代A中的函数变元，用特定的谓词取代A中的谓词变元，就构成了A的一个解释 给定的一个公式A可以有多种解释 若A在任何解释下都为真，则称A为永真式 若A在任何解释下都为假，则称A为永假式 若A至少存在一个成真的解释，则称A为可满足式 若A↔B是永真式，则称A与B是等值的，记为A<=>B，并称A<=>B为等值式 基本等值式
在有限个体域D={a1,a2,…,an}中消去量词等值式 ∀xA(x)<=>A(a1)∧A(a2)∧…∧A(an) ∃xA(x)<=>A(a1)∨A(a2)∨…∨A(an) 量词否定等值式 ┐∀xA(x)<=>∃x┐A(x) ┐∃xA(x)<=>∀x┐A(x) 量词辖域收缩与扩张等值式（B中不含x) ∀x(A(x)∨B)<=>∀xA(x)∨B ∀x(A(x)∧B)<=>∀xA(x)∧B ∀x(A(x)→B)<=>∃xA(x)→B ∀x(B→A(x))<=>B→∀xA(x) ∃x(A(x)∨B)<=>∃xA(x)∨B ∃x(A(x)∧B)<=>∃xA(x)∧B ∃x(A(x)→B)<=>∀xA(x)→B ∃x(B→A(x))<=>B→∃xA(x) 两次分配等值式 ∀x(A(x)∧B(x))<=>∀xA(x)∧∀xB(x) 全称量词对“∧”有分配律，但对“∨”不适合分配律 ∃x(A(x)∨B(x))<=>∃xA(x)∨∃xB(x) 存在量词对“∨”有分配律，但对“∧”不适合分配律
