双语离散计算ch2

格式：pdf
大小：108.99 KB
文档页数：35

下载文档原格式

离散数学ch2.二元关系(5、6、7节)

VS
详细描述
关系的对称差运算可以用符号表示为 R△S，其中 R 和 S 是两个关系。它包括属于 R 但不属于 S，以及属于 S 但不属于 R 的所有有序对。如果 (a, b) 在 R△S 中，那么 (a, b) 或者只属于 R，或者只属于 S。
04
CATALOGUE
关系的闭包
闭包的定义
1 2
关系的交运算可以用符号表示为 R ∩ S，其中 R 和 S 是两个关系。它包括同时属于 R 和 S 的所有有序对。如果 (a, b) 在 R ∩ S 中，那么 (a, b) 同时是 R 和 S 的差是一种集合差集操作，它从第一个关系中去除与第二个关系共有的元素。
中可以推导出的新事实。
数据完整性
03
在数据库设计中，闭包的概念用于确保数据的完整性和准确性
，防止出现冗余和不一致的情况。
05
CATALOGUE
关系的类型
函数关系
总结词
函数关系是一种特殊的二元关系，它满足每个自变量都有唯一的因变量与之对应。
详细描述
在函数关系中，对于定义域中的每一个元素，在值域中都有唯一一个元素与之对应。这种关系具有明确性、确定性和无重复性。常见的函数关系有数学函数、映射函数等。
离散数学ch2.二元关系(5、6、7节)
contents
目录
• 引言 • 二元关系的性质 • 关系的运算 • 关系的闭包 • 关系的类型 • 关系在数据库中的应用 • 关系在人工智能中的应用
01
CATALOGUE
引言
定义与概念
定义
二元关系是集合论中的一个基本概念，它描述了两个元素之间的联系。
在设计关系型数据库时，需要考虑数据结构、数据完整性、数据冗余和数据安全性等方面。

ch2_3离散系统的系统函数

H ( z) = z ( z − 0.2 j)( z + 0.2 j) ( z − 0.8)( z − 0.4 j)( z + 0.4 j)
例：试求下面系统函数的零极点形式二阶因子形式。试求下面系统函数的零极点形式二阶因子形式。 z 3 + 0.04 z H ( z) = 3 2 z − 0.8 z + 0.16 z − 0.128
系统函数
系统函数H 系统函数H(z)的表示方式
(1) z−1的有理函数表示
b0 +b z +L+bM z 1 H(z) = − 1 −N a0 + a1z +L+ aN z
(2) z的有理函数表示
−1
−M
H(z) = z
( N−M)
b0z +b z +L+bM 1 N N−1 a0z + a1z +L+ aN
1 Imaginary part 0.5 0 -0.5 -1 -1 -0.5 0 0.5 Real part 1 2
系统函数与系统稳定性
LTI系统稳定的充要条件： LTI系统稳定的充要条件：系统稳定的充要条件
n = −∞
∑
∞
h[n] < ∞
H(z)的收敛域的收敛域ROC包含单位圆的收敛域包含单位圆
%Determination of the factored form and %the second order section form of a % rational z-transform b =[1 0 0.04 0]; a =[1 -0.8 0.16 -0.128]; [z,p,k]=tf2zp(b,a); disp('Zeros are at'); disp(z); disp('Poles are at'); disp(p); disp('Gain constant');disp(k); sos=zp2sos(z,p,k); disp('Second-order sections'); disp(real(sos));

08级离散期末a答案

e
PGe ( x) = x 2 ( x − 1)( x − 2)
PG e ( x) = x( x − 1)( x − 2)
……4 points ……8 points ……10 points
PG ( x) = PGe ( x) − PG e ( x) = x( x − 1) 2 ( x − 2)
6. (10 points) Let A={0，1}.
2.
Write your answers in space provided (5×4=20 points). × 2 3 4 5 6 7 1 2 3 4 5 6 7 −1 1 1) Let p = 6 3 2 1 5 4 7 , then p = 4 3 2 6 5 1 7 =(146)(23).
1 3 1+ 5 n 1 3 1− 5 n cn = ( + )( ) +( − )( ) 2 2 5 2 2 2 5 2
7. (7 points) Let R beat R ∞ is transitive. Proof. Recal that aR b if and only if there is a path in R from a to b. If aR b and bR c , then composition of the paths from a to b and from b to c forms a path from a to c in R. Thus aR ∞ c and R ∞ is transitive. …..7 points
1 0 0 0 1 0 , 0 0 1 0 0 0
Solution. Since M R ∞
1 1 = 0 0

ch2_example

例4 已知某电话交换台每分钟接到的呼唤次数X服从 4 的泊松分布，分别求（1）每分钟内恰好接到3次呼唤的概率；（2）每分钟不超过4次的概率. 解:
P( X k )
3
k
k!
e
4, k 3
4 4 P( X 3) e 0.19563 3!
P( X 4) P( X 0) P( X 1) P( X 2) P( X 3) P( X 4) 0.628838
1 1 a arcsin( ) 0 2 π 2a
1 1 π 2 . 2 π 6 3
( 3) 随机变量 X 的概率密度为
1 a 2 x 2 , a x a , f ( x ) F ( x ) 其它. 0,
均匀分布
f ( x)
a F( x)
由 F ( x)
x

f ( x)d x 得
0, x 0, xx d x , 0 x 3, 0 6 F ( x) 3x x x 0 6 d x 3 (2 2 ) d x , 3 x 4, 1, x 4.
x 0, 0, 2 x , 0 x 3, 12 即 F ( x) 2 3 2 x x , 3 x 4, 4 1, x 4.
实例2 电脑寿命可用一个连续变量 T 来描述.
这种对应关系在数学上理解为定义了一种实值函数.
.
X( )

这种实值函数与在高等数学中大家接触到的函数一样吗？
R
§2.2 离散型随机变量及其概率分布
例1 设随机变量X的分布律为
试确定常数b. 解由分布律的性质有：

自动控制原理ch2

第二章控制系统的数学模型
2-1 控制系统的时域数学模型二非线性微分方程的线性化 1 非线性问题的提出这种将非线性微分方程在一定条件下近似转化为线性微分方程的方法，称为非线性微分方程线性化。尽管经过线性化得到的线性微分方程只是有条件、近似的描述系统的动态特性，但却能使系统动态特性的分析工作大为简化。
数值亦增大同样的倍数。因此可以采用单位典型外作用(例如 1-单位阶跃函数2-单位脉冲函数)对系统进行分析研究，既简化了问题又不影响结果的正确性。
第二章控制系统的数学模型
2-1 控制系统的时域数学模型二非线性微分方程的线性化
1 2
非线性问题的提出非线性线性化方法
第二章控制系统的数学模型
平衡点附近展开泰勒级数。
2 dy 1d y ( x − x0 ) +L y = f ( x ) = y0 + x0 ( x − x0 )+ 2 x0 dx 2! dx 2
忽略二次以上的各项，上式可写成：
dy y = f ( x ) = y0 + x0 ( x − x0 ) dx
Δy
y
y0
y
Δy
A
Δx
第二章控制系统的数学模型 2-0 引言
输入量
θr
输出量
工作机械
ur
uc
放大
θc
Ri
Li
θm
us
器
ur
ia
自动控制系统加上输入信号以后，输出量的运动方程可以用联系输入量和输出量的微分方程加以描述。因为它既能定性又能定量地描述整个系统的运动方程，所以微分方程是系统的一种数学模型。
第二章控制系统的数学模型 2-0 引言

离散数学双语专业词汇表set集合subset子集elementmember

《离散数学》双语专业词汇表set：集合subset：子集element, member：成员，元素well-defined：良定，完全确定brace：花括号representation：表示sensible：有意义的rational number：有理数empty set：空集Venn diagram：文氏图contain(in)：包含（于）universal set：全集finite (infinite) set：有限（无限）集cardinality：基数，势power set：幂集operation on sets：集合运算disjoint sets：不相交集intersection：交union：并complement of B with respect to A：A与B的差集symmetric difference：对称差commutative：可交换的associative：可结合的distributive：可分配的idempotent：等幂的de Morgan’s laws：德摩根律inclusion-exclusion principle：容斥原理sequence：序列subscript：下标recursive：递归explicit：显式的string：串，字符串set corresponding to a sequence：对应于序列的集合linear array(list)：线性表characteristic function：特征函数countable(uncountable)：可数（不可数）alphabet：字母表word：词empty sequence(string)：空串catenation：合并，拼接regular expression：正则表达式division：除法multiple：倍数prime：素（数）algorithm：算法common divisor：公因子GCD(greatest common divisor)：最大公因子LCM(least common multiple)：最小公倍数Euclidian algorithm：欧几里得算法，辗转相除法pseudocode：伪码（拟码）matrix：矩阵square matrix：方阵row：行column：列entry(element)：元素diagonal matrix：对角阵Boolean matrix：布尔矩阵join：并meet：交Boolean product：布尔乘积mathematical structure(system)：数学结构（系统）closed with respect to：对…是封闭的binary operation：二元运算unary operation：一元运算identity：么元，单位元inverse：逆元statement, proposition：命题logical connective：命题联结词compound statement：复合命题propositional variable：命题变元negation：否定（式）truth table：真值表conjunction：合取disjunction：析取quantifier：量词universal quantification：全称量词化propositional function：命题公式predicate：谓词existential quantification：存在量词化converse：逆命题conditional statement, implication：条件式，蕴涵式consequent, conclusion：结论，后件contrapositive：逆否命题hypothesis：假设，前提，前件biconditional, equivalence：双条件式，等价logically equivalent：（逻辑）等价的contingency：可满足式tautology：永真(重言)式contradiction, absurdity：永假(矛盾)式logically follow：是…的逻辑结论rules of reference：推理规则modus ponens：肯定律m odus tollens：否定律indirect method：间接证明法proof by contradiction：反证法counterexample；反例basic step：基础步principle of mathematical induction：（第一）数学归纳法induction step：归纳步strong induction：第二数学归纳法relation：关系digraph：有向图ordered pair：有序对，序偶product set, Caretesian set：叉积，笛partition, quotient set：划分，商集block, cell：划分块，单元domain：定义域range：值域R-relative set：R相关集vertex(vertices)：结点，顶点edge：边in-degree：入度out-degree：出度path：通路，路径cycle：回路connectivity relation：连通性关系reachability relation：可达性关系composition：复合reflexive：自反的irreflexive：反自反的empty relation：空关系symmetric：对称的asymmetric：非对称的antisymmetric：反对称的graph：无向图undirected edge：无向边adjacent vertices：邻接结点connected：连通的transitive：传递的equivalent relation：等价关系congruent to：与…同余modulus：模equivalence class：等价类linked list：链表storage cell：存储单元pointer：指针complementary relation：补关系inverse：逆关系closure：闭包symmetric closure：对称闭包reflexive closure：自反闭包composition：关系的复合transitive closure：传递闭包Warshal’s algorithm：Warshall算法function, mapping, transformation：函数，映射，变换argument：自变量value, image：值，像，应变量labeled digraph：标记有向图identity function on A：A上的恒等函数everywhere defined：处处有定义的onto：到上函数，满射one to one：单射，一对一函数bijection, one-to-one correspondence：双射，一一对应invertible function：可逆函数floor function：下取整函数ceiling function：上取整函数Boolean function：布尔函数base 2 exponential function：以2为底的指数函数logarithm function to the base n：以n为底的对数hashing function：杂凑函数key：键growth of function：函数增长same order：同阶lower order：低阶running time：运行时间permutation：置换，排列cyclic permutation：循环置换，轮换transposition：对换odd(even) permutation：奇（偶）置换order relation：序关系partial order：偏序关系partially ordered set, poset：偏序集dual：对偶comparable：可比较的linear order(total order)：线序，全序linearly ordered set, chain：线（全）序集，链product partial order：积偏序lexicographic order：字典序Hasse diagram：哈斯图topological sorting：拓扑排序isomorphism：同构maximal(minimal) element：极大(小)元extremal element：极值元素greatest(least) element：最大(小)元unit element：么(单位)元zero element：零元upper(lower) bound：上(下)界least upper(greatest lower) bound：上(下)确界lattice：格join：，保联，并meet：保交，交sublattice：子格absorption property：吸收律bounded lattice：有界格distributive lattice：分配格complement：补元modular lattice：模格Boolean algebra：布尔代数involution property：对合律Boolean polynomial, Boolean expression：布尔多项式（表达式）or(and, not) gate：或(与，非)门inverter：反向器circuit design：线路设计minterm：极小项Karnaugh map：卡诺图tree：树root：根，根结点rooted tree：（有）根树level：层，parent：父结点offspring：子女结点siblings：兄弟结点height：树高leaf(leave)：叶结点ordered tree：有序树n-tree：n-元树complete n-tree：完全n-元树(complete) binary tree：(完全)二元(叉)树descendant：后代subtree：子树positional tree：位置树positional binary tree：位置二元(叉)树doubly linked list：双向链表tree searching：树的搜索（遍历）traverse：遍历，周游preorder search：前序遍历Polish form：（表达式的）波兰表示inorder search：中序遍历postorder search：后序遍历reverse Polish form：（表达式的）逆波兰表示linked-list representation：链表表示undirected tree：无向树undirected edge：无向边adjacent vertices：邻接结点simple path：简单路径（通路）simple cycle：简单回路acyclic：无（简单）回路的spanning tree：生成树，支撑树Prim’s algorithm：Prim算法minimal spanning tree：最小生成树weighted graph：（赋）权图weight：树distance：距离nearest neighbor：最邻近结点greedy algorithm：贪婪算法optimal solution：最佳方法Kruskal’s algorithm：Kruskal算法graph：(无向)图vertex(vertices)：结点edge：边end point：端点relationship：关系connection：连接degree of a vertex：结点的度loop：自回路path：路径isolated vertex：孤立结点adjacent vertices：邻接结点circuit：回路simple path(circuit)：基本路径(回路) connected：连通的disconnected：不连通的component：分图discrete graph(null graph)：零图complete graph：完全图regular graph：正规图，正则图linear graph：线性图subgraph：子图Euler path(circuit)：欧拉路径(回路) Konisberg Bridge problem：哥尼斯堡七桥问题ordinance：法规recycle：回收，再循环bridge：桥，割边Hamiltonian path(circuit)：哈密尔顿路径(回路)dodecahedron：正十二面体weight：权TSP(traveling salesperson problem)：货郎担问题transport network：运输网络capacity：容量maximum flow：最大流source：源sink：汇conversation of flow：流的守恒value of a flow：流的值excess capacity：增值容量cut：割the capacity of a cut：割的容量matching problems：匹配问题matching function：匹配函数compatible with：与…相容maximal match：最大匹配complete match：完全匹配coloring graphs：图的着色proper coloring：正规着色chromatic number of G：G的色数map-coloring problem：地图着色问题conjecture：猜想planar graph：(可)平面图bland meats：未加调料的肉chromatic polynomial：着色多项式binary operation on a set A：集合A上的二元运算closed under the operation：运算对…是封闭的commutative：可交换的associative：可结合的idempotent：幂等的distributive：可分配的semigroup：半群product：积free semigroup generated by A：由A生成的自由半群identity(element)：么（单位）元monoid：含么半群，独异点subsemigroup：子半群submonoid：子含么半群isomorphism：同构homomorphism：同态homomorphic image：同态像Kernel：同态核congruence relation：同余关系natural homomorphism：自然同态group：群inverse：逆元quotient group：商群Abelian group：交换（阿贝尔）群cancellation property：消去律multiplication table：运算表finite group：有限（阶）群order of a group：群的阶symmetric group：对称群subgroup：子群alternating group：交替群Klein 4 group：Klein四元群coset：陪集(left) right coset：(左)右陪集normal subgroup：正规(不变)子群prerequisite：预备知识virtually：几乎informal brand：不严格的那种notation：标记sensible：有意义的logician：逻辑学家extensively：广泛地，全面地commuter：经常往来于两地的人by convention：按常规，按惯例dimension：维(数) compatible：相容的discipline：学科reasoning：推理declarative sentence：陈述句n-tuple：n-元组component sentence：分句tacitly：默认generic element：任一元素algorithm verification：算法证明counting：计数factorial：阶乘combination：组合pigeonhole principle：鸽巢原理existence proof：存在性证明constructive proof：构造性证明category：类别，分类factor：因子consecutively：相继地probability(theory)：概率(论) die：骰子probabilistic：概率性的sample space：样本空间event：事件certain event：必然事件impossible event：不可能事件mutually exclusive：互斥的，不相交的likelihood：可能性frequency of occurrence：出现次数(频率) summarize：总结，概括plausible：似乎可能的equally likely：等可能的，等概率的random selection(choose an object at random)：随机选择terminology：术语expected value：期望值backtracking：回溯characteristic equation：特征方程linear homogeneous relation of degree k：k阶线性齐次关系binary relation：二元关系prescribe：命令，规定coordinate：坐标criteria：标准，准则gender：性别graduate school：研究生院generalize：推广notion：概念intuitively：直觉地verbally：用言语approach：方法，方式conversely：相反地pictorially：以图形方式restriction：限制direct flight：直飞航班tedious：冗长乏味的main diagonal：主对角线remainder：余数random access：随机访问sequential access：顺序访问custom：惯例polynomial：多项式substitution：替换multi-valued function：多值函数collision：冲突analysis of algorithm：算法分析sophisticated：复杂的set inclusion(containment)：集合包含distinguish：区分analogous：类似的ordered triple：有序三元组recreational area：游乐场所multigraph：多重图pumping station：抽水站depot：货站，仓库relay station：转送站。

计算方法与数值计算(2-1插值与逼近)

800 1:42.58 罗达尔
1000
1500 3:32.07 恩格尼
是否能建立竞赛距离与纪录时间之间的函数关系，并测算男子1000米纪录。
4
200
150
100
400
600
800
1000
1200
1400
散点图
5
引例2 设f ( x) ln x，并假定已给出下列三点处的函数值，试近似计算 ln11.75的值。
30
f ( n1) ( ) n Rn ( x) (x x j ) (n 1)! j 0
不能确定，实际计算时，
在[a, b]上，若有 f ( n1) ( x) M，则
n f ( n1) ( ) n M Rn ( x) ( x x j ) (n 1)! ( x x j ) (n 1)! j 0 j 0
已知函数f(x)在n+1个互异节点ax0<x1 <……< xn b
处的函数值yi = f(xi) (i=0,1,2,……，n)，
则存在唯一一个次数不超过n次的多项式： Pn(x)=a0+a1x+……+anxn 满足条件Pn (xi) = yi = f(xi) 。
11
证明：设所要构造的插值多项式为：
y1 y=P1(x)
y0
x0
线性插值
18
x1
x
L1(x)= l0(x)y0 + l1(x)y1
其中
x x1 l0 ( x ) x0 x1
x x0 , l1 ( x) x1 x0
l0(x)：点x0的一次插值基函数， l1(x)：点x1的一次插值基函数。

常用离散数学名词中英文对照

常用离散数学名词中英文对照集合：set元素：element严格定义:well defined成员:member外延原理:principle of extension泛集(全集):universal set空集:empty set(null set)子集:subset文氏图:venn diagram并:union交:intersection相对补集:relative complement绝对补集:absolute complement补集:complement对偶性:duality幂等律:idempotent laws组合律:associative laws交换律:commutative laws分配律:distributive laws同一律:identity laws对合律:involution laws求补律:complement laws对偶原理:principle of duality有限集:finite set计算原理:counting principle类:class幂集:power set子类:subclass子集合:subcollection命题:proposition命题计算:proposition calculus语句:statement复合:compound子语句:substatement合取:conjunction析取:disjuction否定:negation真值表:truth table重言式:tautology矛盾:contradiction逻辑等价:logical equivalence命题代数:algebra of propositions 逻辑蕴涵:logicalimplication关系:relation有序对:ordered pair划分:parti-on偏序:partial order整除性:divisibility常规序:usual order上确界:supremum下确界:infimum上(下)界:upper(lower) bound乘积集:product set笛卡儿积:cartesian product笛卡儿平面:cartesian plane二元关系:binary relation定义域:domain值域:range相等:equality恒等关系:identity relation全关系:universal ralation空关系:empty ralation图解:graph坐标图:coordinate diagram关系矩阵:matrix of the relation 连矢图:arrow diagram有向图:directed graph逆关系:inverse relation转置:transpose复合:composition自反:reflexive对称的:symmetric反对称的:anti-symmetric可递的:transitive等价关系:equivalence relation半序关系:partial ordering relation 函数:function映射:mapping变换:transformation像点:image象:image自变量:independent variable因变量:dependent variable函数图象:graph of a function合成函数:composition function可逆函数:invertible function一一对应:one to one correspondence 内射:injective满射:surjective双射:bijective基数度:cardinality基数:cardinal number图论:graph theory多重图:multigraphy顶点:vertix(point,node)无序对:unordered pair边:edge相邻的adjacent端点:endpoint多重边:multiple edge环:loop子图:subgraph生成子图:generated subgraph平凡图:trivial graph入射:incident孤立点:isolated vertex连通性:connectivity通路:walk长度:length简单通路:chain(trail)圈:path回路:cycle连通的:connected连通分支:connected component距离:distance欧拉图:eulerian graph欧拉链路:eulerian trail哈密顿图:hamilton graph哈密顿回路:hamilton cycle货郎行程问题:traveling salesman完全图:complete graph正则图:regular graph偶图:bipartive graph树图:tree graph加权图:labeled graph同构图:isomorphic graph同构:isomorphism同胚的:homeomorphic平面图:planar graph着色问题:colortion区域:region地图:map非平面图:nonplanargraph着色图:colored graphs顶点着色:vertex coloring色散:chromatic number四色原理:four color theorem对偶地图:dual map退化树:degenerate tree生成树:spanning tree有根树:rooted tree根:root水平(深度):level(depth)叶子:leaf分支:branch有序有根树:ordered rooted tree二元运算符:binary operational symbol半群:semigroup单位元素:identity element右(左)单位元素:right(left) identity左(右)消去律:left(right) cancellation law) 逆:inverse并列:juxtaposition有限群:finite group正规子群:normal subgroup非平凡子群:nontrivial subgroup循环群:cyclic group环:ring整环:integral domain域:field交换环:commutative ring加性环:additive group汇合:meet格:lattice有界格:bounded lattice分配格:distributeve lattice补格:complemented lattice表示定理:representation theorem。

ch2-信息论与编码技术(MATLAB实现)-朱春华-清华大学出版社

2.1 离散信源的数学模型与分类
信源的主要问题：
1．如何描述信源（信源的数学建模问题） 2．怎样计算
2.1 离散信源的数学模型与分类
信源是发出消息的源，信源输出以符号形式出现的具体消息。
按照信源发出的消息在时间上和幅度上的分布情况：
先验概率。
离散有记忆信源
所发出的各个符号的概率是有关联的。
2.1 离散信源的数学模型与分类
有记忆信源符号间的概率关联性可用两种方式：
一种是用信源发出的一个符号序列的整体概率（即联合概率）反映有记忆信源的特征．
一种限制记忆长度，即某一个符号出现的概率只与前面一个或有限个符号有关，而不依赖更前面的那些符号，这样的信源可以用信源发出符号序列内各个符号之间的条件概率来反映记忆特征，这就是发出符号序列的马尔可夫信源．
解：设消息x1：摸出红球；消息x2：摸出白球；若放回，该单符号信源为无记忆信源，其数学模型
为：
若不放回，该单符号信源为有记忆信源，每个符号出现的概率与之前出现的符号有关，用条件概率描述。
2.1.2 离散序列无记忆信源
最简单的序列信源是N=2的情况
2
X =X 1 X 2
信源的概率空间为
若每次取两个球，每次均放回。则该信源每次输出两个符号作为一个消息，称为符号序列信源。
设消息x1 x1 ：先后摸出红球；
消息x1x2：先摸出红球，后摸出白球；
消息x2 x1 :先摸出白球，后摸出红球；符号序列
消息x2 x2 :先后摸出白球。
无记忆信源
长度为2的符号序列信源的数学模型其中
2.1.3 离散序列有记忆信源
发出单个符号的信源发出符号序列的信源
指信源每次发出一组含二个以上符号的符号序列代表一个消息．

离散数学（1）复习笔记

离散数学（1）复习笔记Ch1 命题逻辑的基本概念1.1 命题命题：能判断真假且⾮真即假的陈述句。

命题的真值，真命题，假命题。

* 真值待定 *简单命题 | 原⼦命题，复合命题。

1.2 常⽤的5个命题联结词否定，合取，析取，蕴涵，双蕴涵。

* 异或 | 排斥或 | 不可兼或 * 注意语义判断。

* p→q = ﹁ p∨q ** 必要条件 * 只有……才……；仅当……，……；……，仅当……。

注意命题符号化的蕴涵⽅向。

* domain * A horse is white. （×）联结词集，⼀元联结词，⼆元联结词。

* 优先顺序 * （），﹁，∧，∨，→，↔1.3 合式公式及其赋值命题常项 | 命题常元（值是确定的），命题变项 | 命题变元（真值可以变化的陈述句）。

合式公式 | 命题公式 | 命题形式 | 公式（wff）（well formed formulas），原⼦命题公式（单个命题变项），⼦公式。

* 单个命题变项是合式公式，没说命题常项。

*赋值 | 解释，成真赋值，成假赋值。

真值表。

* 真值表要点：赋值从00…0开始，按照⼆进制加法，直到11…1为⽌；按照运算的优先次序写出各⼦公式。

*命题公式的分类：重⾔式 | 永真式，⽭盾式 | 永假式，可满⾜式。

1.4 重⾔式与代⼊规则代⼊规则。

* 1. 公式中被代换的只能是命题变项（原⼦命题），⽽不能是复合命题。

2.对公式中某命题变项施以代⼊，必须对该公式中出现的所有同⼀命题变项施以相同的代换。

* 1.5 命题形式化命题形式化 | 符号化。

Ch2 命题逻辑的等值和推理演算2.1 等值定理等值 | 等价，等值定理：设A，B为两个命题公式，A = B的充分必要条件是 A↔B为⼀个重⾔式。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

OR:

show that the contrapositive (~q)(~p) is true.
Since (~q) (~p) is logically equivalent to p q, then the theorem is proved.
Proof by contrapositive

20:41:24
2
1.1 Mathematical Systems, Direct Proofs, and Counterexamples

A mathematical system consists of

Undefined terms Definitions Axioms
Undefined terms

20:41:24 11

Example 2.1.11(13): Given a direct proof of the following statement: For all X, Y, and Z (1) XÇ(Y-Z)=(XÇY)-(XÇZ); (2) XÈ(Y-X)=XÈY.
Discussion: Proof: (1)Let X,Y, Z be arbitrary sets. We prove XÇ(Y-Z)=(XÇY)-(XÇZ) by proving (i) if xÎ XÇ(Y-Z), then xÎ (XÇY)-(XÇZ) and (ii) if xÎ (XÇY)-(XÇZ) , then xÎXÇ(Y-Z)
Theorems

A theorem is a proposition of the form p q which must be shown to be true by a sequence of logical steps that assume that p is true, and use definitions, axioms and previously proven theorems.

Theorem are often of the form For all x1,x2,…,xn , if p(x1,x2,…,xn) then q(x1,x2,…,xn) A direct proof assumes that p(x1,x2,…,xn) is true and then using p(x1,x2,…,xn) as well as other axioms, definitions, previously derived theorems, and rules of inference, shows directly that p(x1,x2,…,xn) is true Definition 2.1.7 An integer n is even if there exists an integer k such that n=2k. An integer n is odd if there exists an integer k such that n=2k+1

Two triangles are congruent if their vertices can be paired so that the corresponding sides are equal and so are the corresponding angles. he sum of their measures is 180 degrees.

….
20:41:24 12
Disproving a Universally Quantified Statement

Recall: to disprove "xP(x)
we need to find one member x makes P(x) is false. Such a value for x is called a counterexample.
Point Line

Definitions
A definition is a proposition constructed from undefined terms and previously accepted concepts in order to create a new concept. Example. In Euclidean geometry the following are definitions:

20:41:24 14
Indirect proof
The
method of proof by contradiction of a theorem p q consists of the following steps:
1. Assume p is true and q is false 2. Show that ~p is also true. 3. Then we have that p ^ (~p) is true. 4. But this is impossible, since the statement p ^ (~p) is always false. There is a contradiction! 5. So, q cannot be false and therefore it is true.
Lemmas and corollaries
A lemma is a small theorem which is used to prove a bigger theorem. A corollary is a theorem that can be proven to be a logical consequence of another theorem. Example from Euclidean geometry: "If the three sides of a triangle have equal length, then its angles also have equal measure."

Given two distinct points, there is exactly one line that contains them. Given a line and a point not on the line, there is exactly one line through the point which is parallel to the line.

The method of proof by contrapositive of a theorem p q is to show that (~q)(~p) is true.

Since (~q) (~p) is logically equivalent to p q, then the theorem is proved.
Proof by Contradiction A proof by contraction establishes pq by assuming that the hypothesis p is true and that the conclusion q is false and then, using p and q as well as other axioms, definitions, previously derived theorems, and rules of inference, derives a contradiction. A proof by contradiction is sometimes called an indirect proof
10

20:41:24

Example 2.1.8: The integer n=12 is even because there exists an integer k=6 such that n=12=2k=2´6
Example 2.1.10: Given a direct proof of the following statement: For all integers m and n, if m is odd and n is even, then m+n is odd. Discussion: Proof: Let m and n be arbitrary integers, suppose that m is odd and n is even. Then, by definition, there exists two integers k1 and k2 such that m=2k1+1, n=2k2 . Then, the sum is m+n= (2k1+1)+2k2 =2(k1+k2 )+1. Thus, there exists an integer k=k1+k2 such that m+n=2k+1. Therefore m+n is odd.
Axioms
An axiom is a proposition accepted as true without proof within the mathematical system. There are many examples of axioms in mathematics: Example: In Euclidean geometry the following are axioms

Types of proof

A proof is a logical argument that consists of a series of steps using propositions in such a way that the truth of the theorem is established. Direct proof: p q