2.1命题及其表示1、【单选题】下列语句中不是命题的是（ ）
a、3是奇数
b、请勿吸烟!
c、我是中学生
d、4 3>5
2、【单选题】下列语句中为命题的是（ ）
a、今天是阴天；
b、你身体好吗？
c、我真快乐；
d、请不要走。
2.2命题联结词1、【单选题】设p：天下大雨，q：他在室内运动，将命题“除非天下大雨，否则他不在室内运动”符号化为（ ）
a、p→q
b、p∧q
c、┐p→┐q
d、┐p∨q
2、【单选题】下面联结词不具有交换律的是（ ）。
a、→
b、∧
c、∨
d、↔
3、【填空题】将几个命题联结起来，形成一个复合命题的逻辑联结词主要有____ 、____ 、____ 、____和____ 。
4、【填空题】命题公式g=（p∧q）→r，则g共有____个不同的解释；把g在其所有解释下所取真值列成一个表，称为g的 ____ ；p，q，r解释依次是（0，1，0）则g的真值为 ____ 。
5、【判断题】命题联结词次序规定为：˥，⋀，⋁，→，↔。⋀，⋁两者之间以出现先后为序。
2.3命题公式1、【单选题】下列公式中为永假式的是（ ）
a、(p∧┐p) ←→q
b、p→(p∨q∨r)
c、(p→┐p)→┐p
d、┐(q→p)∧p
2、【单选题】下列公式中为永真式的是（ ）
a、p→(p∨q∨r)
b、┐(q→p)∧p
c、(p→q)→(q→┐p)
d、(p∧┐p) ←→q
3、【单选题】下列各式中不是重言式的是（ ）
a、q→(p∨q)
b、p∧q→p
c、┐(p∧┐q)∧(┐p∨q)
d、(p→q) ←→(┐p∨q)
4、【单选题】设p, q的真值是0，r, s的真值是1，下列公式中真值为1的是（ ）
a、r→p
b、q∧s
c、p←→s
d、q∨r
5、【单选题】重言式的否定为（ ）。
a、重言式
b、矛盾式
c、可满足式
d、蕴涵式
6、【单选题】下面语句是真命题的为（ ）。
a、我正在说谎
b、如果1＋1＝2，则雪是黑色的
c、如果1＋1＝3，则雪是黑色的
d、吃饭了吗？
2.4命题公式等价1、【判断题】设a，b为两个命题公式a〈═〉b，当且仅当a↔b为一个重言式。
2、【判断题】设a和b是两个命题公式，对a和b的任一赋值，a和b的真值都相同，则称a和b是等价。
2.5命题公式蕴含1、【判断题】当且仅当p→q是一个重言式时，我们称“p蕴含q”记作p＝〉q。
2、【判断题】设a，b为两个命题公式，a等价b，当且仅当a蕴含b及b蕴含a。
2.6命题公式的范式1、【判断题】同一个命题公式有多个等价式，也有多个合取范式和析取范式。
2、【判断题】任何命题公式都可以化成与其等价的析取范式或合取范式，但是其析取范式和合取范式不唯一。
2.7主析取范式1、【单选题】一个公式在等价意义下，下面哪个写法是唯一的（ ）。
a、析取范式
b、合取范式
c、主析取范式
d、以上答案都不对
2、【单选题】┐(p∨q) ←→(p∧q)的主析取范式是（ ）
a、(q∧┐p)∨(p∧＞q)
b、(q∧p)∨(p∧┐q)
c、(┐p∧┐q)∨(p∧q)
d、(┐p∨q)∧(q∧┐p)
3、【判断题】一般地说，n个命题变元共有2n个极小项。
4、【判断题】一个命题公式的真值表中，所有真值为真赋值对应极小项的析取就是此公式的主析取范式。
2.8主合取范式1、【判断题】一个命题公式有唯一的主范式，且当命题变元的顺序约定以后，主析取范式和主合取范式是唯一确定的。
2、【判断题】矛盾式无成真赋值，因而主析取范式不含任何极小项，其主析取范式记为f(或者0)，而主合取范式含(n为公式中命题变元的个数)个极大项。
3、【判断题】重言式无成假赋值，因而主析取范式含(n为公式中命题变元的个数)个极小项；主合取范式记为t(或者1)。
4、【判断题】可满足式的主析取范式就是成真赋值对应小项的析取；主合取范式就是成假赋值对应极大项的合取；且主析取范式中小项m的下标和主合取范式中大项m的下标是互补的。
5、【判断题】如果a、b的任意一个主范式等价，则必有a等价b。
6、【判断题】命题公式(p∧q)∨(¬p∧r)∨(q∧r)的主析取范式是∑1，3，6，7，那么它的主合取范式就是∏0，2，4，5。
7、【判断题】命题公式a的主析取范式是∑1，3，那么它的主合取范式就是∏0，2。
2.9推理理论1、【判断题】所谓推理是指从前提出发，应用推理规则推出结论的思维过程。
2、【判断题】要证明c是一组前提a1，a2，…，an 的有效结论，只需证明a1∧a2∧…∧an→c为重言式。
3、【判断题】命题推理的p规则是指前提在推导过程中的任何时候都可以引入使用。而t规则是推理中如果一个或多个公式蕴含了公式s，则公式s可以引入到以后的推理之中。
2.10直接推理1、【判断题】判断证明(p→q)∧(q→r)∧¬r=﹥¬p 的过程是否正确。 证明：⑴ p→q p规则 ⑵ q→r p规则 ⑶ p→r t⑴⑵i ⑷ ¬r→¬p t⑶e ⑸ ¬r p规则 ⑹ ¬p t⑷ ⑸i 所以¬p是前提p→q，q→r，¬r的有效结论。
2.11间接推理1、【判断题】要证明h1∧h2∧…∧hn 蕴含(a→b)，只需证明h1∧h2∧…∧hn∧a蕴含b，其中a叫做附加前提，这种间接推理方法称为cp规则。
2、【判断题】证明: (p∧q)→r，¬r∨s，¬s，p蕴含¬q 过程如下： 证明： ⑴ q p(附加前提) ⑵ ¬r∨s p ⑶ ¬s p ⑷ ¬r t⑵⑶i ⑸ (p∧q)→r p ⑹ ¬(p∧q) t⑷⑸i ⑺ ¬p∨¬q t⑹e ⑻ p p ⑼ ¬q t⑺⑻i ⑽ q∧¬q(矛盾) t⑴⑼i 以上证明方法是用归谬法，证明过程是正确的。
3.1谓词与量词1、【判断题】客体亦称个体，它是指可以独立存在的对象，它可以是一个具体事物，也可以是一个抽象的概念。
2、【判断题】一般来说指明客体性质或指明客体之间关系的是谓词。
3、【判断题】个体变项的取值范围称为个体域，将一切事物组成的个体域称为全总个体域。
3.2谓词公式1、【多选题】在含有量词的命题进行符号化时，应该注意（）
a、如果事先没有给出个体域，应以全总个体域作为个体域。
b、即使不是选取全总个体域，也要考虑是否需要加入特性谓词。
c、当需要加入特性谓词时，要根据其前面的量词选取适当加入形式。
2、【判断题】通常把命题、命题变元、谓词填式和命题函数叫做谓词演算的原子公式。
3、【判断题】“好人自有好报”可用谓词公式表示如下：设f(x)：x是好人；g(x)：x会有好报，则命题符号化为：∀x(f(x)→g(x))。
4、【判断题】“没有免费的午餐”可用谓词公式表示如下：设m(x)：x是午餐；f(x)： x是免费的，则命题符号化为：┐∃x(m(x)∧f(x))。也可以表示为：∀x(m(x)→┐f(x))。
3.3约束变元与自由变元1、【多选题】我们希望一个个体变元在同一个公式中只以一种身份出现，应用下面（）规则可以做到这一点。
a、约束变元的换名规则
b、自由变元的代入规则
c、约束变元的代入规则
d、自由变元的换名规则
2、【判断题】在谓词公式中，紧接量词以后的最小子公式叫做该量词的辖域或作用域。
3、【判断题】在一个谓词公式中，同一个变元既可以是约束的，又可以是自由的。
4、【判断题】∀x p(x)∧∃yq(x,y）整个谓词公式中只有一个量词。∀x的辖域为p(x)，p(x)中的x和q(x,y) 中的y是约束变元，q(x,y)中的x是自由变元。
5、【判断题】对(∀x)(p(y)∧r(x,y))→(∃y)q(y) 中的自由变元进行代入，则表示为： (∀x)(p(z)∧r(x,y))→(∃y)q(y)。
3.4等价与蕴含ⅰ1、【多选题】当个体域为有限集时，如d={a1，a2，…，an}，对任意谓词a(x)都有( )。
a、∀xa(x)⇔a(a1)∧a(a2)∧…∧a(an)
b、∃xa(x)⇔a(a1)∧a(a2)∧…∧a(an)
c、∀xa(x)⇔a(a1)∨a(a2)∨…∨a(an)
d、∃xa(x)⇔a(a1)∨a(a2)∨…∨a(an)
2、【判断题】谓词公式如同命题公式，根据真值可分为永真式、矛盾式和可满足式。
3、【判断题】设a、b是任意两个谓词公式，对a、b的任何赋值，若其真值相同，则称a与b是等价的，记作a ⇔b；若a→b是有效的，则称a蕴含b，记作a=>b。
4、【判断题】谓词公式中，量词之前的否定联结词，不是否定该量词，而是否定该量词及其辖域 。
5、【判断题】一般情况下，一个谓词公式不是命题，只有当将谓词公式中的各种变元用指定的特殊的常元去代替，才能构成一个命题。这种代替就是对公式的一个解释。
3.5等价与蕴含ⅱ1、【多选题】以下谓词蕴含式正确的是（）。
a、(∀x)a(x)∨(∀x)b(x)=>( ∀x) (a(x)∨b(x))
b、(∃x) (a(x)∧b(x))=>(∃x)a(x)∧(∃x)b(x)
c、(∀x) (a(x)→b(x))=>( ∀x)a(x)→(∀x)b(x)
d、(∀x) (a(x)↔b(x))=>( ∀x)a(x)↔(∀x)b(x)
2、【多选题】以下谓词等价式正确的是（）。
a、∀x(a(x)∧b(x))⇔∀xa(x)∧∀xb(x)
b、∀x(a(x)∨b(x))⇔∀xa(x)∨∀xb(x)
c、∃x(a(x)∨b(x))⇔∃xa(x)∨∃xb(x)
d、∃x(a(x)∧b(x))⇔∃xa(x)∧∃xb(x)
3、【多选题】下列谓词公式是等价的有（）。
a、┐∀xa(x)⇔∃x┐a(x)
b、┐∃xa(x)⇔∀x┐a(x)
c、┐∃x(m(x)∧┐f(x))⇔∀x(m(x)→f(x))
d、┐∀x(f(x)→g(x))⇔∃x(f(x)∧┐g(x))
4、【判断题】任何谓词公式,都可以化成与其等价的前束范式。而前束范式分为前束合取范式和前束析取范式。
5、【判断题】证明 ∀x(a(x)→b)⇔∃xa(x)→b。以下过程是正确的。 证明 ∀x(a(x)→b)⇔∀x(┐a(x)∨b) ⇔∀x┐a(x)∨b⇔┐∃xa(x)∨b ⇔∃xa(x)→b。
3.6谓词推理ⅰ1、【多选题】全称指定规则(us规则)： (∀x)a(x)=>a(c)则（）。
a、c是个体域中任一个体。
b、用c取代a(x)中x时，一定在x出现的所有地方进行取代。
c、若个体域中的所有个体都满足谓词a，则个体域中任一个体c也满足谓词a。
d、体现了在逻辑推理中由一般到特殊的推导方法。
2、【判断题】存在推广规则说明：对于个体域中的某个个体c满足谓词a，当然有(∃x)a(x)。
3、【判断题】存在指定规则说明：若个体域中存在一些个体满足谓词a，则至少有某个确定的个体c满足谓词a。
3.7谓词推理ⅱ1、【判断题】“苏格拉底三段论”以下命题符号化过程是正确的。 设： h(x)：x是人； m(x)：x是要死的； s：苏格拉底。 则推理形式结构为：(∀x)(h(x)→m(x))∧h(s)蕴含m(s)。
2、【判断题】用谓词逻辑推理证明：有理数都是实数，有的有理数是整数，因此有的实数是整数。 证明：设q（x）：x为有理数；r（x）：x为实数；z（x）：x为整数； 前提：∀x(q(x)→r(x))，∃x(q(x)∧z(x))； 结论：∃x(r(x)∧z(x))。 （1）∃x(q(x)∧z(x)) p （2）q(c)∧z(c) es（1） （3）∀x(q(x)→r(x)) p （4）q(c)→r(c) us（3） （5）q(c) t（2）i （6）r(c) t（2）（4）i （7）z(c) t（2）i （8）r(c)∧z(c) t（6）（7）i （9）∃x(r(x)∧z(x)) eg（8） 本例中一定要把⑴,⑵写在⑶,⑷的前面，因为存在指定以后一定满足全称指定，否则不一定满足。也就是说同一个体变元存在指定一定要先于全称指定。
4.1集合的基本概念1、【单选题】下列集合关系表示不正确的是（）。
a、{x} ⊆{x}
b、{x} ∈{x}
c、{x} ∈{x，{x}}
d、{x} ⊆{x，{x}}
2、【多选题】设a={1,2,4}，b={1,3，{2}}，下列各式正确的是（）。
a、{2}∈a
b、{2}∈b
c、{2} ⊆a
d、{2} ⊆b
e、∅∈a
f、∅⊆a
3、【判断题】全集是相对的，不同的问题有不同的全集。即使是同一问题也可以取不同的全集。
4、【判断题】一般地说，任意集合a至少有两个子集，一个是空集∅，另一个是它本身a。
4.2集合的运算1、【单选题】某个集合的元数为10，可以构成（ ）个子集。
a、10
b、20
c、100
d、2的10次方
2、【单选题】设a，b，c是任意集，则下列等式不正确的是（）。
a、(a∪b)-c=(a-c)∪(b-c)
b、a-(b∪c)=(a-b)∩(a-c)
c、(a-b)∪(a-c)=a,当a∩(b∪c)=∅成立
d、a∪(b⊕c)=(a∪b)⊕(a∪c)
3、【多选题】设a={∅}，b=ρ(ρ(a))，问下列各题正确的是（）。
a、∅∈b
b、∅⊆b
c、{∅}∈b
d、{{∅}}∈b
e、{{∅}}⊆b
4、【填空题】设a，b是两个集合，a={1，2，3，4}，b={2，3，5}，则a-b= （） ，b∩a=（）， b∪a=（） 。
5、【判断题】设a为有限集合，则|ρ (a)|=2的|a|次方。
4.3序偶与笛卡尔积1、【多选题】设a，b，c是集合，则有（）
a、a×(b∪c) =(a×b)∪(a×c)
b、a×(b∩c) =(a×b)∩(a×c)
c、(a∪b)×c =(a×c)∪(b×c)
d、(a∩b)×c =(a×c)∩(b×c)
2、【判断题】逻辑的方法表示序偶：（x,y）=（a,b）当且仅当(x=a)∧(y=b)。
3、【判断题】如果a，b都是有限集，|a|= n，|b|= m，则|a×b|=nm=|a||b|。
4、【判断题】设a，b，c，d是非空集合，则 a×b⊆c×d的充分必要条件是a⊆c且b⊆d。
5、【判断题】若x×y=x×z，且x不是空集，则y=z。
6、【判断题】设a={0,1}，b={1,2}，则a×b=b×a。
4.4覆盖与划分1、【判断题】集合的划分必然是其覆盖，但是覆盖不一定是划分。
2、【判断题】设 a={a,b,c}，则f={{a},{a,c}}是a 的一个覆盖。
5.1二元关系及其表示1、【单选题】设a＝{0,a},b={1,a,3},则a∪b的恒等关系是( )
a、{<0,0><1,1>,<3,3>,
}
b、{<0,0>,<1,1>,<3,3>}
c、{<1,1>,,<3,3>}
d、{<0,1>,<1,a>,,<3,0>}
2、【单选题】设集合a＝{1,2}，b={a,b,c},c={c,d}, 则a×（b∩c)＝( )。
a、{(c,1),(2,c)}
b、{(1,c),(2,c)}
c、{(c,1),(c,2)}
d、{(1,c),(c,2)}
3、【填空题】设a={1,2,3,4}，定义a上二元关系r：（a,b）属于r,当且仅当（a-b）/2是整数，称r为模2同余关系，则r=（），domr=（），ranr=（）。
4、【判断题】设a={x, y, z}，则全关系的∣ea∣=∣a×a∣=9。
5.2二元关系的运算
1、【多选题】设r，s，t是a上的二元关系, 则不正确的是（）。
a、r∘(s∪t)=r∘s∪r∘t
b、(r∪s)∘t=r∘t∪s∘t
c、r∘(s∩t)=r∘s∩r∘t
d、(r∩s)∘t=r∘t∩s∘t
2、【判断题】二元关系的复合运算满足交换律。
3、【判断题】设r是a上的二元关系，r∘ia=ia∘r=r。
4、【判断题】设a上的二元关系r和s，则m（r ∘ s）=mr ∘ ms。
5.3关系的性质ⅰ
1、【判断题】设r是集合a上的二元关系，r是自反的当且仅当ia⊆r。
2、【判断题】关系r是自反的，当且仅当在关系矩阵中，对角线上的所有元素都是1，在关系图上每个结点都有自回路。
3、【判断题】若关系r是反自反的，当且仅当关系矩阵对角线的元素皆为零，关系图上每个结点都没有自回路。
4、【判断题】设r是集合a上的二元关系, r是反自反的当且仅当r∩ia=∅。
5.4关系的性质ⅱ
1、【判断题】若关系r是对称的，当且仅当关系矩阵是对称的，且在关系图上，任两个结点间若有定向弧线，必是成对出现。
2、【判断题】若关系r是反对称的，当且仅当关系矩阵以主对角线为对称的元素不能同时为1，在关系图上两个不同结点间的定向弧线不能成对出现。
3、【判断题】设r⊆x×x， (∀x)(∀y)(∀z)(x∈x∧y∈x∧z∈x∧（x,y）∈r∧（y,z）∈r→（x,z）∈r)，则称r在x上是传递的。
4、【判断题】设r⊆x×x，如（x,y）∈r∧（y,z）∈r，则有结果（x,z）∈r，其就具有传递性；否则就不具有传递性。
5、【判断题】设r⊆x×x，如（x,y）∈r∧（y,z）∈r不成立，则不再讨论结果（x,z）∈r是否成立，直接确定r具有传递性。
6、【判断题】设r是x上的二元关系，r是传递的当且仅当r∘r⊆r。
5.5关系的闭包
1、【单选题】设r⊆x×x，则不正确的是（）。
a、rs(r)=sr(r)
b、rt(r)=tr(r)
c、st(r)⊆ts(r)
d、st(r)=ts(r)
2、【单选题】设r1，r2是集合a={a，b，c，d}上的两个关系，其中r1={（a，a），（b，b），（b，c），（d，d）}，r2={（a，a），（b，b），（b，c），（c，b），（d，d）}， 则r2是r1的（ ）闭包。
a、自反
b、对称
c、传递
d、既是对称闭包也是传递闭包
3、【多选题】设r⊆ x×x，则（）。
a、r是自反的当且仅当r(r)=r
b、r是对称的当且仅当s(r)=r
c、r是传递的当且仅当t(r)=r
d、r(r)=r∪ix
4、【判断题】包含r 的最小自反(对称，传递)关系是r 的自反(对称，传递)闭包。
5.6等价关系
1、【多选题】以下关系不是等价关系的有（）。
a、三角形的全等
b、同学关系
c、数的小于等于关系
d、老乡关系
2、【多选题】下列关于等价关系的说法正确的有（）。
a、关系矩阵主对角线全为1且是对称矩阵
b、关系图每一个结点上都有自回路且每两个结点间如果有边，一定有方向相反的两条边
c、关系图被分为互不连通的几部分，每一部分中的所有结点构成一个等价类。
d、如果r是x上的等价关系，则一定可以生成唯一且确定的等价类。
3、【判断题】设r是x上的等价关系，对于x的任意元素a和b，arb 的充分必要条件是[a]r=[b]r。
4、【判断题】设 r是x上的等价关系，x关于r的商集x/r是x的一个划分。
5、【判断题】设r，s集合x上的等价关系，则r=s 当且仅当 x/r=x/s。
6、【判断题】集合x上的任意一个划分，确定了x上的一个等价关系。
5.7相容关系
1、【多选题】设r和s是a上相容关系，则（）。
a、复合关系rºs是a上的相容关系
b、r∪s是a上的相容关系
c、r∩s是a上的相容关系
d、r-s是a上的相容关系
2、【判断题】给定集合a上的关系r，若r是自反、对称的，则称r是a上的相容关系。
3、【判断题】r是相容关系，则其关系矩阵主对角线上的元素都是1，且矩阵是对称的。
4、【判断题】相容类不一定是最大相容类，由不同最大相容类组成的集合为完全覆盖。
5、【判断题】设集合a={1,2,3,4}中的一个覆盖为b={{1,2}，{2,3,4}}，则由b确定的相容关系为：{1,2}×{1,2}∪{2,3,4}×{2,3,4}。
5.8偏序关系
1、【判断题】任意集合a上的恒等关系ia是自反的，反对称的和传递的，所以ia是a上偏序关系。
2、【判断题】设（x,≼）是偏序集，则其哈斯图与其盖住关系cov x是一一对应的且cov x是惟一的。
3、【判断题】在偏序集〈a，≤〉中，如果x，y∈a，有x≤y，且x≠y且没有其他元素z，满足x≤z，z≤y，则称元素y盖住元素x，记作cova={〈x，y〉∣x，y∈a，且y盖住x}。
4、【判断题】设a是集合，ρ (a)是a的幂集合，ρ (a)上的包含关系⊆ 就是其上的一个偏序关系，即< ρ (a) ,⊆ >是偏序集。
5.9极元与最元
5.10上下界及其确界
6.1映射及其分类
7.1代数系统及性质
7.2特殊元素
7.3半群及群
7.4阿贝尔群与循环群
7.5同态与同构
7.6环及其性质
7.7整环及域
8.1格及其性质
8.2分配格及有界格
8.3有补格及布尔格
8.4布尔代数
9.1图的基本概念
9.2结点的度
9.3子图、补图及同构
9.4路与回路
9.5点割集与边割集
9.6图的矩阵表示
9.7欧拉图
9.8欧拉图的应用
9.9哈密尔顿图
9.10平面图
9.11对偶图
9.12树及其最小生成树
9.13有向树及根树
9.14最优树及前缀码
猜你喜欢
- 2022-12-05 21:35
- 2022-12-05 21:33
- 2022-12-05 21:28
- 2022-12-05 21:23
- 2022-12-05 21:14
- 2022-12-05 21:08
- 2022-12-05 20:33
- 2022-12-05 20:27
- 2022-12-05 20:26
- 2022-12-05 19:35