离散数学2：基本概念
公式层次：单个的命题变项A是0层公式。
如果A是n层公式，B是m层公式，那么￢A是n+1层公式；C=A∧B,C=A∨B,C=A→B,C=A↔B的层次是：max(n,m)+1。
比如（￢(p→￢q) ∧((r∨s) ↔￢q)的层次计算就是：
0 1 0 0 1
2 1 1
3 2
4
4层公式
设p1,p2,p3…pn是公式A中的全部与命题变项，那么给它们各指定一个真值，这就是A的一个赋值/解释。若使A=1，则是成真赋值，否则就是成假赋值。
所以含有n（n≥1）个命题变项的公式有2n个不同赋值。
真值表：把命题公式A在所有赋值下取值情况列成的表。
例：写出（￢p∧q）→￢r的真值表，并求它的成真赋值和成假赋值。
扩展资料：
学科内容
1．集合论部分：集合及其运算、二元关系与函数、自然数及自然数集、集合的基数
2．图论部分：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用
3．代数结构部分：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数
4．组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理
5．数理逻辑部分：命题逻辑、一阶谓词演算、消解原理
离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。
离散数学也可以说是计算机科学的基础核心学科，在离散数学中的有一个著名的典型例子-四色定理又称四色猜想，这是世界近代三大数学难题之一。
它是在1852年，由英国的一名绘图员弗南西斯·格思里提出的，他在进行地图着色时，发现了一个现象，“每幅地图都可以仅用四种颜色着色，并且共同边界的国家都可以被着上不同的颜色”。
那么这能否从数学上进行证明呢？100多年后的1976年，肯尼斯·阿佩尔（Kenneth Appel）和沃尔夫冈·哈肯（Wolfgang Haken）使用计算机辅助计算，用了1200个小时和100亿次的判断，终于证明了四色定理，轰动世界，这就是离散数学与计算机科学相互协作的结果。
离散数学可以看成是构筑在数学和计算机科学之间的桥梁，因为离散数学既离不开集合论、图论等数学知识，又和计算机科学中的数据库理论、数据结构等相关，它可以引导人们进入计算机科学的思维领域，促进了计算机科学的发展。
参考资料：百度百科--离散数学
公式层次：单个的命题变项A是0层公式。
如果A是n层公式，B是m层公式，那么￢A是n+1层公式；C=A∧B,C=A∨B,C=A→B,C=A↔B的层次是：max(n,m)+1。
比如（￢(p→￢q) ∧((r∨s) ↔￢q)的层次计算就是：
0 1 0 0 1
2 1 1
3 2
4
4层公式
设p1,p2,p3…pn是公式A中的全部与命题变项，那么给它们各指定一个真值，这就是A的一个赋值/解释。若使A=1，则是成真赋值，否则就是成假赋值。
所以含有n（n≥1）个命题变项的公式有2n个不同赋值。
真值表：把命题公式A在所有赋值下取值情况列成的表。
例：写出（￢p∧q）→￢r的真值表，并求它的成真赋值和成假赋值。
p q r
￢p
￢p∧q
￢r
(￢p∧q) →￢r
0 0 0
1
0
1
1
0 0 1
1
0
0
1
0 1 0
1
1
1
1
0 1 1
1
1
0
0
1 0 0
0
0
1
1
1 0 1
0
0
0
1
1 1 0
0
0
1
1
1 1 1
0
0
0
1
所以成假赋值为011。000,001,010,100,101,110,111为成真赋值。
如果A在所有赋值下均为真，则A是重言式或永真式，如果所有赋值下均为假，则为矛盾式或永假式。如果A不是矛盾式，那A就是可满足式。
如果A是可满足式，那么A至少有一个成真赋值。如果A是可满足式，而且有至少一个成假赋值，则A是非重言式的可满足式。
（真值表最后一列全1则为重言式，全0则为矛盾式，至少有1个1，则为可满足式）
命题逻辑等值演算
如果A和B构成的A→B是重言式，那么A与B是等值的，记作A⇔B。可以用真值表确定A↔B是不是重言式，来判断A是否与B等值，也可以判断A与B的真值表是否相同来确定A⇔B还是A⇎B。
16组常用的重要等值式模式：
1、A⇔￢￢A
2、A⇔A∨A，A⇔A∧A
3、A∨B⇔B∨A，A∧B⇔B∧A
4、(A∨B) ∨C⇔A∨(B∨C)，(A∧B) ∧C⇔A∧(B∧C)
5、A∨(B∧C)⇔(A∨B) ∧(A∨C)，A∧(B∨C)⇔(A∧B) ∨(A∧C) 分配率
6、￢（A∨B）⇔￢A∧￢B，￢(A∧B)⇔ ￢A∨￢B
7、A∨(A∧B)⇔A，A∧(A∨B)⇔A 吸收率
8、A∨1⇔1，A∧0⇔0
9、A∨0⇔A，A∧1⇔A
10、A∨￢A⇔1
11、A∧￢A⇔0
12、A→B⇔￢A∨B
13、A→B⇔(A→B) ∨(B→A)
14、A→B⇔￢B→￢A
15、A↔B⇔￢A↔￢B
16、(A→B) ∧(A→￢B)⇔ ￢A
分类: 数学本回答被提问者和网友采纳
p为0层，非p由定义知为1层；非p且q选之中较大的层数，q为0层，得整体非p且q为2层；非p且q——>非r，取较大一个然后加1得3层。你可以试着推一下后面的四层，说白了就是每次加一