资源描述：
《离散数学定义(必须背).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、命题逻辑§(论域)定义：论域是一个数学系统，记为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)构成的公式是合式公式
2、。§（生成公式）定义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
3、)}+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
4、=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，则称
5、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
6、为完全集。•如果完全集S1中的每个联结词都可由联结词集合S2定义，则S2也是完全集。•如果从完全集S中去掉任何一个联结词就成为不完全的了，就称S为极小完全集。§(范式)定义：•原子公式和原子公式的否定统称为文字。如果一个文字恰为另一个文字的否定，则称它们为相反文字。•设n是正整数，A1,……,An都是文字，称A1∨…∨An为简单析取式，称A1∧…∧An为简单合取式。•定义⒈１６设n是正整数。若B1,……,Bn都是简单合取式，则称B1∨…∨Bn为析取范式。若B1,……,Bn都是简单析取式，则称B1∧…∧Bn为合取范式。§（逻辑推论）定义：•若真值赋值v满足公式
7、集合Γ中的每个公式，则称v满足Γ。若有真值赋值满足Γ，则称Γ是可满足的，否则称Γ是不可满足的。•设Γ是公式的集合，A是公式。如果每个满足Γ的真值赋值都满足A，则称A是Γ的逻辑推论，记为Γ
8、=A。若Γ
9、=A不成立，记为Γ
10、≠A。谓词逻辑§（论域）定义：论域是一个数学系统，记为D。它由三部分组成：•(1)一个非空对象集合D；•(2)一个关于D的函数集合,也称运算；•(3)一个关于D的关系集合。§（一阶谓词逻辑语言）简称一阶逻辑语言•逻辑符号：包括变元、联接词、量词；•非逻辑符号：包括常元、函词、谓词；•仅有个体变元；•按形成规则构成的合式公式集合•（字符集）定义
11、：§逻辑符号，包括变元、联接词、量词、逗号以及括号等
