2013-06-23

 昨日と同じ時間に起きた。午前中は無かったことになった。喫茶店に行って情報論理の中間の対策。過去問とレポートを見直す。23時くらいに帰ってきて麻婆豆腐の残り食べて少しだらけてから3時まで続き。以下まとめ。

 わかんないことそれなりにあるけど落ち着けば6割くらいはなんとかなりそう。でも不安。それよりも明日終わったらアーキテクチャなり講演の感想文?なりあるんだけど。

 

<Information Logic>

report2

・equivalence relation: if it is reflexive, symmetric and transitive

・partial order: if it is reflexive, antisymmetric and transitive

・preorder: if it is reflexive and transitive

・reflexive: xRx

・symmetric: xRy implies yRx

・antisymmetric: xRy and yRx implies x = y

・transitive: xRy and yRz implies xRz

report4,5

・structural induction

 - 難しく考えずに普通に帰納法だと思えばよい。「結論が成り立つと仮定して、一段拡張されてもその性質が保存すること」を意識する。はじめにbase-caseを与えてしまえば、自由に仮定すなわち目標となる結論を用いて議論してよいことになる、はず。induction-hypothesis <- conclusion

 問題として多いのは「proof treeの一段で成り立つ性質が二段以上になっても成り立つ」「variableとformulaやtermの一つの分解について(表現が難しい)成り立つ性質がすべてのformulaやtermについて成り立つ」というタイプだと思う。帰納法がどうやったら回るかということを考えていけば自ずと示すべきこと/示す際に使っていい条件がわかるはず。

  - report5-1の解説が原理を理解するのにわかりやすい説明。

report7

・tell whether predicate formulas valid/satisfiable/unsatisfiable

 - give a valuation(->{tt, ff}) for formula, and deform the formula

 - or derivation tree

examination in last year

・P⊃Q⊃R means P⊃(Q⊃R)

・algebraic specification, Σ: signature, E: axioms

・an example of a (Σ, E)-algebra = write a set on which the algebra is defined, and interpretations of the operations

・when check whether a propositional formula is valid or not, first write the truth table(s)

・check: in a proof tree in LK, left P∧Q can be devided into P, Q by admissible rule

・if a propositional formula is not valid, give a valuation J, that is,  for example, J(p) = ff

・in derivation rules of predicate LK, all-R and exist-L come with the side condition: Eigenvarible Condition that is the varialbe z does not have any free occurence in the sequent on the bottom

・when check whether a predicate formula is valid or not, firstly interpret it semantically, secondly write its interpretation syntactically

・when present a structure S, write a set U, functional symbol f and predicate symbol P

topics (usually from Wikipedia)

・Variables vs. Meta-Variables

 - variavles: on the object-level

 - meta-variables: on the meta-level, stand for some variables on the object-level

・Syntax vs. Semantics

 - Syntax is anything having to do with formal languages or formal systems without regard to any interpretation or meaning given to them

 - Semantics mathematically defines whether a formula is true or not

・Well-defined

 - is unambiguous and its objects are independent of their representative

 - "「ある概念の定義をする場合、そう決めることによって、何も矛盾なく上手くいく」ということが確認されているということ" (from www004.upp.so-net.ne.jp/s_honma/welldefined/welldefined.htm)

・Soundness vs. Completeness

 - Soundness: syntactic derivability gives(implies?) semantical validity

 - Completeness: semantical validity gives(implies?) syntactic derivability

exam questions in last year

・give an example of a (Σ, E)-algebra

 - write a set on which the algebra is defined, and interpretations of the operations

・capture-avoiding substitution

 - substitution = targets of exchange are not bound variables but free variables

・tell if propositional formulas are valid or not and give a proof

・tell if predicate formulas are valid or not and give a proof

・show specifics of binary relation

・show that LK and LK' has the same deductive power

・give an example of structure

・first order predicate logic

 

では。

広告を非表示にする