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) 对任何给定的节点, 它的左儿子和右儿子按以下方法选 定:直接处于给定节点之下的节点, 作为左儿子, 对于同一水平线 上与给定节点有邻接的节点 , 作为右儿子 , 依此类推。

好,上述内容已经包含了大部分形式语言和自动机所需的基础知识,接下来我们将会正式开始形式语言和自动机的学习