命题逻辑
? (论域)定义：论域是一个数学系统，记为D。它由三部分组成：
? (1)一个非空对象集合S，每个对象也称为个体； ? (2) 一个关于D的函数集合F； ? (3)一个关于D的关系集合R。 ? （逻辑连接词）定义
? 设n>0,称为{0,1}n到{0,1}的函数为n元函数，真值函数也称为联结词。 ? 若n =0，则称为0元函数。 ? （命题合式公式）定义：
? (1).常元0和1是合式公式； ? (2).命题变元是合式公式；
? (3).若Q,R是合式公式，则(?Q)、(Q?R) 、(Q?R) 、(Q?R) 、(Q?R) 、
(Q?R)是合式公式；
? (4).只有有限次应用(1)—(3)构成的公式是合式公式。
? （生成公式）定义1.5 设S是联结词的集合。由S生成的公式定义如下：
? ⑴若c是S中的0元联结词，则c是由S生成的公式。 ? ⑴原子公式是由S生成的公式。 ? ⑴若n≥1，F是S中的n元联结词，A1,…,An是由S生成的公式，则FA1…An
是由S生成的公式。
? （复杂度）公式A的复杂度表示为FC(A)
? 常元复杂度为0。
? 命题变元复杂度为0，如果P是命题变元，则 FC (P)=0。 ? 如果公式A=?B，则FC (A)=FC(B)+1。 ? 如果公式A=B1 ? B2，或
A=B1 ? B2，或 A=B1?B2，或 A=B1? B2，或 A=B1 ? B2，或
则FC (A)=max{FC(B1), FC(B2)}+1。
? 命题合式公式语义
? 论域：研究对象的集合。
? 解释：用论域的对象对应变元。 ? 结构：论域和解释称为结构。
? 语义：符号指称的对象。公式所指称对象。合式公式的语义是其对应的逻
辑真值。
? （合式公式语义）设S是联结词的集合是{?，?，?，? ，?，?}。由S生成
的合式公式Q在真值赋值v下的真值指派v(Q)定义如下： ? ⑴v(0)=0, v(1)=1。
? ⑴若Q是命题变元p，则v(A)= pv。 ? ⑴若Q1,Q2是合式公式
? 若Q= ? Q1，则v(Q)= ? v(Q1) ? 若Q=Q1 ? Q2，则v(Q)=v(Q1)? v(Q2)
?
?
?
?
?
?
若Q=Q1⑴Q2，则v(Q)=v(Q1)⑴v(Q2) ? 若Q=Q1? Q2，则v(Q)=v(Q1)? v(Q2) ? 若Q=Q1 ? Q2，则v(Q)=v(Q1)? v(Q2) ? 若Q=Q1? Q2，则v(Q)=v(Q1)? v(Q2)
（真值赋值）由S生成的公式Q在真值赋值v下的真值v(Q)定义如下： ? ⑴若Q是S中的0元联结词c，则v(Q)=c。 ? ⑴若Q是命题变元p，则v(Q)= pv。
? ⑴若Q是FQ1…,Qn，其中n≥1， F是S中的n元联结词， Qi是公式，
则v(Q)=v(FQ1…Qn)=Fv(Q1)…v(Qn)。 （可满足与有效）定义1.7 设Q是公式。
? ⑴如果真值赋值v使得v(Q)=1，则称v满足Q。
? ⑴如果每个真值赋值都满足Q，则称Q为有效式，或称为永真式，也称为
重言式。
? ⑴如果每个真值赋值都不满足Q，则称Q为永假式，也称为矛盾式，不可
满足式。
? ⑴如果至少有一个真值赋值满足Q，则称Q为可满足式。 定理1.5（对偶定理）
? 设A,B是由{0,1,?,⑴,⑴}生成的公式，A*与A互为对偶式，B*与B互为
对偶式。如果A ? B，则A* ? B*。 （完全集）定义：
? 定义1.12设F是n元联结词，p1,p2,…,pn是不同的命题变元。如果公式
A中不出现除p1,p2,…,pn之外的命题变元，并且A?Fp1,p2,…,pn，则称A定义F。
? 设S是联结词集合。如果每个n(n>0)元的联结词都可由S定义，则称S
为完全集。
? 如果完全集S1中的每个联结词都可由联结词集合S2定义，则S2也是完
全集。
? 如果从完全集S中去掉任何一个联结词就成为不完全的了，就称S为极
小完全集。 (范式)定义：
? 原子公式和原子公式的否定统称为文字。如果一个文字恰为另一个文字的
否定，则称它们为相反文字。
? 设n是正整数，A1,……,An都是文字，称A1⑴…⑴An为简单析取式，称
A1⑴…⑴ An为简单合取式。
? 定义⑴１６ 设n是正整数。若B1,……,Bn都是简单合取式，则称
B1⑴…⑴Bn为析取范式。若B1,……,Bn都是简单析取式，则称B1 ⑴… ⑴Bn为合取范式。 （逻辑推论）定义：
? 若真值赋值v满足公式集合Γ中的每个公式，则称v满足Γ。若有真值赋
值满足Γ，则称Γ是可满足的，否则称Γ是不可满足的。
? 设Γ是公式的集合，A是公式。如果每个满足Γ的真值赋值都满足A，则
称A是Γ的逻辑推论， 记为Γ|=A。若Γ|=A不成立，记为Γ|≠A。
?
谓词逻辑
? （论域）定义：论域是一个数学系统，记为D。它由三部分组成：
? (1)一个非空对象集合D；
? (2) 一个关于D的函数集合,也称运算； ? (3)一个关于D的关系集合。
? （一阶谓词逻辑语言）简称一阶逻辑语言
? 逻辑符号：包括变元、联接词、量词； ? 非逻辑符号：包括常元、函词、谓词； ? 仅有个体变元；
? 按形成规则构成的合式公式集合 ? （字符集）定义：
? 逻辑符号，包括变元、联接词、量词、逗号以及括号等，表示如
下：
? 变元：x1, x2, …
? 联接词：?,?,?,?,?,?； ? 量 词：?, ?； ? 逗 号：, ; ? 括 号：(, )
? 非逻辑符号，包括常元、函词、谓词等，表示如下：
? 常 元：c1, c2 , …
? 函 词：f11, f21,......；f12, f22,......； ? 谓 词：P11,P 21,......； P 12, P 22,....。
? （项）定义：
? (1).个体常元是项； ? (2).个体变元是项；
? (3).若是t1,…,tn项，f in是n元函词，则是f i (t1,…,tn)项。 ? （合式公式）定义：合式公式是按如下规则构成的有穷长符号串。
? (1).若是t1,…,tn项，Qin是n元谓词，则Qin(t1,…,tn)是合式公式。 ? (2).若Q是合式公式，则(?Q)是合式公式；
? (3).若Q和R是合式公式，则(Q?R)、(Q?R)、(Q?R) 、(Q?R)及(Q?R)
是合式公式；
? (4).若Q是合式公式，x是变元，则(?xQ)及(?xQ)是合式公式。 ? (5).只有有限次应用(1)—(4)构成的公式是合式公式。 ? （约束变元）定义：
? 若(?xQ)(或?xQ)是公式，则称变元x在公式(?xQ) (或?xQ)中为约束出现，
称x是约束变元，并称 x出现的辖域为Q。
? （自由变元）定义：
? 如果变元x在公式Q中的出现不是约束出现，则称x在Q中为自由出现。
在公式Q中有自由出现的变元称为Q的自由变元，将Q中自由变元的集合记为Var(Q)。
? 定义：不出现变元的项称为基项。 ? 定义：没有自由变元的公式称为语句。 ? 解释（定义）：设D是论域，一个解释I 由以下四部分组成：
数理逻辑定义(必须背)
