NLP入门之形式语言与自动机学习(二)
第二篇:逻辑与图论
1:什么是命题? 说起什么是命题,命题是一个能够判断真假的语句,一般可以用一个大写的字母表示为一个命题.举个例子:
A:3是奇数
B:铜是金属
C:1+4=2
结果很显然易见,命题A和命题B的真值均是真命题,命题C的真值是假命题
2:什么是连接词?
连接词是用于把单个命题构成复合命题,连接词包括”非”,”与”,”或”,”蕴含”,通常用符号“┐”表示“非”, 符号“ ∧”表示“ 与”、符 号“ ∨ ”表 示“ 或 ”和 符 号“ → ”表 示“ 蕴 含 ”。
下边有一张真值表,可以看看给出的这些连接词的定义:
把上边的图字符用语言来概括下:
1:当命题P和Q的真值时,当且仅当复合命题P∧Q的真值是真,其他的情况P∧Q的真值均为假
2:当命题P和Q的真值均为假时,当且仅当复合命题P∨Q的真值为假,其他情况P∨Q均为真
3:当命题P为真且命题Q为假时,当且仅当复合命题P→Q的 真值为假。其他情况P→Q均为真。
4:至于连接词“非”可对命题进行否定,当命题P为真,则有┐P为假。
3:命题的演算规律
根据上边的几条规定,对他的命题演算进行证明下:
(1) ┐┐P =P
(2)P∨P P
P∧P P
(3)P∨Q Q∨P
P∧Q Q∧P
(4)P∨(Q∧R) (P∨Q)∧(P∨R)
P∧(Q∨R) (P∧Q)∨(P∧R) (5)P∨(P∧Q)P
P∧(P∨Q)P
(6)┐(P∨Q) ┐P∧┐Q
┐(P∧Q) ┐P∨┐Q
(7)P∨F P
P∧T P
(8)P∨T T
P∧F F
二:图
这一部分将介绍下图论的一些基本概念,先说说什么是图,图的定义如下:
1:什么是图?
一个图是由一个三元组(V,E,ψ)组成的,其中V是非空的节点集合,E是边的集合,ψ是从边集合E到节点无序偶或有序偶集合上的函数。
下面以一个例子说明:
大家发现图中的边总是与两个节点相关联,所以一个图一般表示为二元组,即G = (V,E),若边ek与节点无序偶〈vi,vj>相关联,则称该边为无向边。若边ek与节点有序偶〈vi,vj>相关联,则称该边为有向边,其中vi为 边ek的起始节点,vj为终止节点。
并且如果一个图中的每条边都是没有方向的,这个图就可以称为无向图,就跟例1一样,如果一个图中每条边都是有向边,称该图为有向图,如下图所示:
在第二个图中其实就可以用G = (V, E)来表示:
V= {a,b,c,d}
E= {〈a,b〉,〈a,d〉,〈b,d〉,〈b,c〉,〈c,c〉}
在图中,如果两个节点是由一条有向边或者一条无向边关联,则称这两个节点是邻接点.关联于同一节点的两条边统称为邻接边.关联与同一个节点的一条边称为自闭路,比如上图中的(c,c)就是一条自闭路.
另外在研究图的性质和图的局部结构中,子图的概念是很重要的,下边我想要说说子图的定义:
设图G=(V,E)和图G1=(V1,E1),如果V1 ∈V且E1∈E,则称G1 是G的子图;如果V1 =V且E1=E,则称G1 是G的真子图;如果V1=V且E1∈E,则称G1 是G的生成子图。
下边的这一个例子,(b)和(c)均为(a)的子图,又(b)是(a)的生成子图。
2:图的重构
通常, 一个图的几何图形可有若干个不同的画法, 就是说, 一 个图的几何图并不是惟 一的 , 但它们描述的图却是相同的。如果有两个图 , 它们的节点数和边数相同 , 而且节点和边的关联关系也一样 , 那么这两个图应是相同的 , 或称同构图。
定义如下:
图G1 =(V1,E1)和图G2 =(V2,E2),若存在双射函数f:V1→V2,且e=〈vi,vj〉是G1的一条边,当且仅当e′=〈f(vi),f(vj)〉是G2 的一条边,则称G1 和G2 同构,记为G1 DG2。
举个例子:
下面的两个图是同构图,用\来表示对应
节点的对应:
v1 \a
v2 \b
v3 \c
v4 \d
〈v2,v1〉\〈b,a〉
〈v4 ,v1〉\ 〈d,a〉
〈v3 ,v4〉\ 〈c,d〉
〈v3 ,v2〉\ 〈c,b〉
2:路径和回路
路径的定义:
有向图G=(V,E)的有限条边的序列e1,e2,…,en, 其中任意边ei的终止节点是边ei+ 1 的起始节点 , 则称这样的边
序列是图G的路径。当路径中所有的边都互不相同时 , 称为简单路径 ; 当路径中所
有节点都互不相同时 , 称为基本路径
比如在下图中:
P4 = (〈v1 ,v2〉,〈v2 ,v4〉,〈v4 ,v2〉,〈v2 ,v3〉,〈v3 ,v4〉,〈v4 ,v2〉,
〈v2 ,v5〉,〈v5 ,v1〉)是一条回路;P5 = (〈v1 ,v2〉,〈v2 ,v3〉,〈v3 ,v4〉,〈v4 ,v2〉,〈v2 ,v5〉,〈v5 ,v1〉)
是一条简单回路 ;P6 = (〈v1 ,v2〉,〈v2 ,v3〉,〈v3 ,v4〉,〈v4 ,v5〉,〈v5 ,v1〉) 是 一条 基
本回路。
路径长度:
在一条路径中, 所含边的条数称为该路径的长度。
在一个有向图中, 如果存在从节 点vi到节点vj的路径,则称从vi到vj是可达的。将vi可达的所有节点构成 的集合称为是vi的可达节点集。
在一个有向图中, 如果每对不同 的节点vi和vj之间都是相互可达的, 则称该图是强连图。
3:图的矩阵表示:
定义:
设G= (V,E) 是 有 向 图 ,V= {v1 ,v2,…,vn},定义一个n×n的矩阵A,A的元素是aij, 并且有
称矩阵A是图G的邻接矩阵。
4 .节点度数
在有向图中 , 射入一个节点的边数称为该节点的入度 , 由一个节点射出的边数称为该节点的出度。 节点的入度和出度之和 , 称为该节点的度数。在无向图中 , 一个节点关联的边数就称为该节点的度数。
5:树
树是一种无回路的有向图,无回路的有向图, 是指一个有向图中不存在回路。其中, 入度为 0 的节点 称为根节点,出度为 0 的节点称为叶子。因此, 图中节点a和节 点f是根节点 , 而节 点b、d和g便 是 叶 子 。
定义如下:
如果有向图T中,只存在一个节点v的入度为0,其他所有节点入度均为 1, 从节点v出发可到达T中的每个节 点,则称T是一棵有向树或称根树.T中入度为0的节点v是树的根,T中出度为0的节点是树 的叶子,其他入度为 1 的节点称为树的枝节点(或称内节点)。
例如下图中的所示的树均为根树。一个孤立节点也是一棵有向树。
因为有向树中没有任何回路, 所以树中所有路径都是基本路 径。从根节点到树中某一节点的路径长度, 称为该节点的层数。
在上图(a)所示的树中,根节点1 的层数为0,节点2,5,6 的层 数为 1, 节点 3,4, 7 的层数为 3。同时将树中最长的路径长度称为树的高度。
同时为了方便 , 可以借用家族术语来表达树中节点之间的关系 , 把 从节点v出发可达的每个节点 , 都称是v的子孙 , 其中只经一条边可达的节点,称是v的直接子孙(或称儿子)。
从有向树的结构可以看出,树的每一个节点也都是给定树的 子树的根。如果删除树的根和与它关联的边 , 便得到一些子树 , 这 些子树的根 , 就是第一层上的各节点
在有向树中,如果每个节点的出度小于或等于m, 称该树是m元树; 如果每个节点的出度都等于m或 0, 称该树是完全m元树
当m= 2,m元树和完全m元树分别称为二元树和完全二元 树。对于二元树的每个枝节点或根节点 , 至多有两棵子树 , 分别为 左子树和右子树
举个例子:
用二元树表示一个算术表达式((a-c)/(b1+b2))+b3 *b4
对计算机来说 , 处理二元树是比较方便的 , 所以常把有序树转 化为二元树。用二元树表示有序树的方法是 :
(1) 除保留最左边的枝节点外, 删去所有从每个节点长出的 分枝 , 在一层中的节点之间用从左到右的有向边连接。
(2) 对任何给定的节点, 它的左儿子和右儿子按以下方法选 定:直接处于给定节点之下的节点, 作为左儿子, 对于同一水平线 上与给定节点有邻接的节点 , 作为右儿子 , 依此类推。
好,上述内容已经包含了大部分形式语言和自动机所需的基础知识,接下来我们将会正式开始形式语言和自动机的学习