K 系统 和命题逻辑的树形图方法类似。不过在每个命题旁边要标准一个自然数，表示某个可能世界。和命题逻辑相比，多了下面四条规则： 在第四个规则中， irj 的 j 必须在前面没有出现过。 例 1 ：用树形图验证： 例 2 ：用树形图验证 ⊨ ( ◇ p ∧◇﹁ q) → ◇□◇ p 是否成立。 树形图没有封闭，所以 ( ◇ p ∧◇﹁ q) → ◇□◇ p 不是有效式。 从树形图中可以读出反模型： 其他正规系统 在框架上加一些限制条件，比如自返性、对称性、传递性、持续性。 自返性 r ：对任意的 w ， Rww 对称性 s ：如果 Rwu ，则 Ruw 传递性 t ：如果 Rwu 且 Ruv ，则 Rwv 持续性 h ：对任意的 w ，存在 v ， Rwv 在用树形图判定模态命题在这些系统中是否是有效式时，需要添加一些规则： S5 系统 在 K V 中 R 是全通关系，即任意的 u 和 v ， Ruv 。所以它的树形图比较简单， r 无需出现。 所以可以用上述方法验证 S5 系统的有效式。
重言式 如果一个复合命题，不管其原子命题取什么值，它总是为真，则我们称之为重言式。比如 p → p ， (p → q) → ( ﹁ q →﹁ p) 。从定义可知，如果 A 是重言式，则 ⊨A 。 和重言式相对的是矛盾式，即永远为假的命题，比如 p ∧﹁ p ， p ↔ ﹁ p 。 如果要判断 B 是不是 A 的如果后承，即 A ⊨B 是否成立，只需判断 ⊨ A → B 是否成立，即 A → B 是不是重言式。 如果要判断 A 能否推出 B ，根据可靠性定理和完全性定理，也只需判断 A → B 是不是重言式。 真值表方法 要判断一个命题是不是重言式。列真值表，穷尽原子命题的所有可能取值，看看这个命题是不是总取真值，如果总是真则它就是重言式了。 比如判断 (p → q) ∧ p → q 是不是重言式。 最后一列的取值总是为真，所以它是重言式。 归谬赋值法 假设要判定的命题为假，然后逐步推出它的子命题的取值，最后推出它的原子命题的取值，如果它的原子命题出现矛盾的取值，即出现既真又假的情况，则说明原命题是不可能为假的，即它是重言式。 假设 (A → B) → ((C → D) → (A ∧ C → B ∧ D)) 为 0 。则 A → B 取值 1 ， (C → D) → (A ∧ C → B ∧ D) 取值 0 。所以 C → D 取值 1 ， A ∧ C → B ∧ D 。所以 A ∧ C 取值 1 ， B ∧ D 取值 0 。所以 A 和 C 取值 1 。而 A → B 取值 1 ， C → D 取值 1 ，所以 A 、 B 、 C 、 D 的取值都为 1 ，这与 B ∧ D 取值 0 矛盾。 归谬赋值法也可以压缩在一行表示，出现矛盾的取值，则在下面划短横线。 有时情况比较复杂，比如我们知道 p ∨ q 为 1 ，这时我们无法确定 p 和 q 的值，只知道 p 和 q 最少有一个为 1 。这时我们需要分别考虑各种赋值情况，当每种情况都导致矛盾时，原命题才是重言式。 树形图方法 树形图方法和归谬赋值实质上是一样的。当要判断 A 是不是重言式时，将问题转为判断﹁ A 有没有可能为真，如果这是不可能的，则 A 是重言式。 将待判断命题的否命题按下面的规则展开。如果一个分支上同时出现某个命题及其否定，则该分支封闭，在末端打上 X 号。如果所有分支都封闭，则待判断命题是重言式。每个命题都要用这些规则不断展开，直到将其分解为原子命题，除非某分支出现矛盾提前终结。已经展开的命题，在其旁边打上 √ 号，表示后面不需要再考虑这个命题了。 例子：判断 (p → q) ∧ r →﹁ (p ∧ r) ∨ (q ∧ r) 是否是重言式。
我们知道，语句呈现的是线性的字符串，而语句 结构却是二维的。我们之所以能够理解语句的意思，是因为我们的大脑语言处理中枢能够把线性语句解构（decode）成二维的结构：语法学家常常用类似下列的上下颠倒的树形图来表达解构的结果（所谓 parsing）。 上面这个树形图叫作依从关系树形图（dependency tree，常常用来表达词或词组之间的逻辑语义关系，与此对应的还有一种句法树，叫短语结构树 phrase structure tree，更适合表达语句单位之间的边界与层次关系)。直观地说，所谓理解了一句话，其实就是明白了两种意义：（1）节点的意义（词汇意义）；（2）节点之间的关系意义（逻辑语义）。譬如上面这个例子，在我们的自动语句分析中有大小六个节点：【Tonight】 【I】 【am going to enjoy】 【the 【song】 Hero】 【again】，分解为爷爷到孙儿三个层次，其中的逻辑语义是：有一个将来时态的行为【am going to enjoy】，结构上是老爷爷，他有两个亲生儿子，两个远房侄子。长子是其逻辑主语（Actor） 【I】，此子是其逻辑宾语（Undergoer）【the song Hero】，父子三人是语句的主干（主谓宾，叫做 argument structure），构成语句意义的核心。 两个远房侄子，一个是表达时间的状语（adverbial）【Tonight】，另一个表达频次的状语（adverbial）【again】。最后，还有一个孙子辈的节点【song】，他是次子的修饰语（modifier，是同位语修饰语），说明【Hero】的类别。 从句法关系角度来看，依从关系遵从一个原则：老子可以有n（n=0）个儿子（图上用下箭头表示），而儿子只能有一个老子：如果有一个以上的老子，证明有结构歧义，说明语义没有最终确定，语言解构（decoding）没有最终完成。虽然一个老子可以有任意多的下辈传人，其亲生儿子是有数量限制的，一般最多不超过三个，大儿子是主语，次子是宾语，小儿子是补足语。比如在句子 “I gave a book to her” 中，动词 gave 就有三个亲儿子：主语 【I】， 宾语【a book】，补足语 【to her】. 很多动词爷爷只有两个儿子（主语和宾语，譬如 John loves Mary），有的只有一个儿子（主语，譬如 John left）。至于远房侄子，从结构上是可有可无的，在数量上也是没有限量的。他们的存在随机性很强，表达的是伴随一个行为的边缘意义，譬如时间、地点、原因、结果、条件等等。 自然语言理解（Natural Language Understanding）的关键就是要模拟人的理解机制，研制一套解构系统（parser），输入的是语句，输出的是语法结构树。在这样的结构树的基础上，很多语言应用的奇迹可以出现，譬如机器翻译，信息抽取，自动文摘，智能搜索，等等。 在结束本文前，再提供一些比较复杂一些的语句实例。我把今天上网看到的一段英文输入给我们研制的parser，其输出的语法结构树如下（未经任何人工编辑，分析难免有小错）。 说明：细心的读者会发现下列结构树中，有的儿子有两个老子，有的短语之间互为父子，这些都违反了依存关系的原则。其实不然。依存关系的原则针对的是句法关系，而句法后面的逻辑关系有时候与句法关系一致，有时候不一致。不一致的时候就会出现两个老子，一个是与句法关系一致的老子，一个是没有相应的显性句法关系的老子。最典型的情形是所谓的隐性（逻辑）主语或宾语。 譬如第一个图示中的右边那棵结构树中，代词「I」就有两个老子：其句法老子是谓语动词「have learned」，它还有一个非谓语动词（ING形式）的隐性的逻辑老子「(From) reading」，也做它的逻辑主语 (who was reading? I)。再如第二个图示中的语法结构树中，定语从句的代表动词「were demonstrating」的句法老子是其所修饰的名词短语「students」，但逻辑上该名词短语却是定语从句动词「were demonstrating」的主语（actor）。有些纯粹的句法分析器（parser）只输出句法关系树，而我们研制的parser更进一步，深入到真正的逻辑语义层次。这样的深层分析为自然语言理解提供了更为坚实的基础，因为显性和隐性的关系全部解构，语义更为完整。 我们每天面对的就是这些树木构成的语言丛林。在我的眼中，它们形态各异，婀娜多姿，变化多端而不离其宗（“语法”）。如果爱因斯坦在时空万物中看到了造物主的美，如果门捷列夫在千姿百态的物质后面看到了元素表的简洁，语言学家则是在千变万化的语言现象中看到了逻辑结构之美。这种美的体验伴随着我们的汗水，鼓励我们为铲平语言壁垒而愚公移山，造福人类。 后记：When I showed the above trees to my daughter today, she was amazed, pretty! She asked, is this what you made the machine to do in diagramming sentences? Yes. Wow, incredible. I don't think I can diagram the sentences as nice as these. Can some day the machine be smarter than you the creator? Is the machine learning by itself? I said, it is not self-learning at this point and the self-learning system is too research oriented to put into a real life system now. But I do observe from time to time that the machine we made for parsing sometimes generate results of very complicated sentences way beyond our expectation, better than most human learners at times. This is because I encode the linguistics knowledge piece by piece, and machine is super good at memory. Once taught, it remembers every piece of knowledge we programmed into the system. Over the years of the development cycle, the accumulation of the knowledge is incredibly powerful. We humans are easy to forget things and knowledge, but machine has no such problems. In this sense, it is not impossible that a machine can beat his creator in practical performance of a given task. 回答： I don't think tree is the way my mind thinks １窃以为，句法树迄今仍是大脑黑箱作业的最好的模拟和理论 ２ does not really matter 作者: 立委 (*) 日期: 06/03/2011 04:30:20 As long as subtree matching is a handy and generalized way of info extraction. Tree is not the goal but a means to an end. The practical end is to extract knowledge or facts or sentiments from language. In practice, our goal is not to simulate the human comprehension per se , the practical goal is: Quote 在这样的结构树的基础上，很多语言应用的奇迹可以出现，譬如机器翻译，信息抽取，自动文摘，智能搜索，等等。 【相关博文】 《泥沙龙笔记：漫谈自动句法分析和树形图表达》 【 科普小品：文法里的父子原则 】 【立委科普：语法结构树之美（之二）】 《新智元：有了deep parsing，信息抽取就是个玩儿》 泥沙龙笔记：parsing 是引擎的核武器，再论NLP与搜索 乔氏 X 杠杠理论 以及各式树形图表达法 【 立委随笔：创造着是美丽的 】 【 科研笔记：开天辟地的感觉真好 】 【立委科普：美梦成真的通俗版解说】 【征文参赛：美梦成真】 【立委科普：自然语言parsers是揭示语言奥秘的LIGO式探测仪】 【置顶：立委科学网博客NLP博文一览（定期更新版）】
标签: 树形图
