离散数学定义(必须背)概要.docx

命题逻辑 ? (论域)定义：论域是一个数学系统，记为D。它由三部分组成： ? (1)一个非空对象集合S，每个对象也称为个体； ? (2) 一个关于D的函数集合F； ? (3)一个关于D的关系集合R。 ? （逻辑连接词）定义 ? 设n0,称为{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(n0)元的联结词都可由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不成立