BUAA 离散数学1 知识点整理

详见 离散数学 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是合式公式，则($\neg Q$)、($Q\land R$) 、($Q \lor R$) 、($Q \oplus R$) 、($Q \rightarrow R$) 、($Q \leftrightarrow 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=\neg 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(Q)= 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。