Aristotles "To mathematically model intellingent thought"
First model: Propositional， or Sequential Logic.
Def Proposition - a statement that is either true or false.
usually， "I am tall" is not a proposition， because it is objective.
However， what happen if we define "tall"?
Most basic structuer : Assumption + Assumption implies Conclusion
Language of Propositional Calculus
- variables
A，B， ... ， P， Q or even A_1， A_2， ...
- Logical Connectives
⇒， ∨，∧，¬，⇔ 面倒くさいので以下、記号は適当に。
Now build expressions
yet， for that， we need ( ， ) (paranthesis)
(A implies B) makes sense， but
(A conjunction B not) makes no sense.
Distinguish what makes sense and doens’t by defining the "Well-Formed-Formula" (Wff’s) inductively as follows.
1) All proposition variables are wff’s.
2) If alpha and beta are wff’s， then (alpha conjunction beta)， (alpha disjunction beta)， .....(trivial 5 of them) are also wff’s
3)A wff must be build with finitely many applications of the above step.
** Advantage of inductive definition lies in the ability to prove things inductively.
Ex. Any proper initial segment of wff with atleast one connective has more left paranthesis than right prenthesis
PROOF/ By induction on the complexity of wff’s
Base case: Prop. variables (check)
One connective (there are 5 choices)
cleary， any proper initial segment has one left， no right paranthesis.
2nd Step: Asuume alpha and beta are wff’s that meet the condition.
Now show this is still true for all 5.
By easy computation， Q.E.D
Propositions are repeated by sentence symbols (aso called propositional variables) have connective and paranthesis to build expression， ome of which are wffs.
Def A truth assignment is a function U:{A_i}， i∈N implies {T，F}
i.e. U(A_i) = T or F for all i∈N
Extend U to V{B} B is a wff implies {T，F} as follows.
V(A_i) = U(A_i)
V((a conjunction b))= {T if V(a) = T and V(b)=T， F otherwise.
similarly for disjunction and negation.
The proof that this V is unique relies on the Recursion Theorem
Def Let a be a wff. We say that
1. a is tautology if V(a)=T for all truth assignments of V
2. a is a contracition if (not a) is a tautology.
3. a is satisfiable if there is a truth assignment such that V(a) = T
Asuume we already know how to omit extra paranthesis and know order of procedure
Note， we can omit paranthesis because we establish order of procedure. not vice versa.
Implication associates from right to left.
Def A set Σ of wff’s logically implies a wff b， in symbols Σ logically implication （記号の出し方が分からない） b， if for all truth assignments U， whnere U’(a)=T for all a∈Σ，then U’(b)=T
We say that wff’s a and b are logically equivalent if a logically implies a and b≠a. we write a double logically implication b.
(this simply mean a and b become T/F exactly same time)
Theorem Σlogically implies a implies b IFF ΣU(a)logically implies b.
証明するには，文字数制限が………次回に続く。
First model: Propositional， or Sequential Logic.
Def Proposition - a statement that is either true or false.
usually， "I am tall" is not a proposition， because it is objective.
However， what happen if we define "tall"?
Most basic structuer : Assumption + Assumption implies Conclusion
Language of Propositional Calculus
- variables
A，B， ... ， P， Q or even A_1， A_2， ...
- Logical Connectives
⇒， ∨，∧，¬，⇔ 面倒くさいので以下、記号は適当に。
Now build expressions
yet， for that， we need ( ， ) (paranthesis)
(A implies B) makes sense， but
(A conjunction B not) makes no sense.
Distinguish what makes sense and doens’t by defining the "Well-Formed-Formula" (Wff’s) inductively as follows.
1) All proposition variables are wff’s.
2) If alpha and beta are wff’s， then (alpha conjunction beta)， (alpha disjunction beta)， .....(trivial 5 of them) are also wff’s
3)A wff must be build with finitely many applications of the above step.
** Advantage of inductive definition lies in the ability to prove things inductively.
Ex. Any proper initial segment of wff with atleast one connective has more left paranthesis than right prenthesis
PROOF/ By induction on the complexity of wff’s
Base case: Prop. variables (check)
One connective (there are 5 choices)
cleary， any proper initial segment has one left， no right paranthesis.
2nd Step: Asuume alpha and beta are wff’s that meet the condition.
Now show this is still true for all 5.
By easy computation， Q.E.D
Propositions are repeated by sentence symbols (aso called propositional variables) have connective and paranthesis to build expression， ome of which are wffs.
Def A truth assignment is a function U:{A_i}， i∈N implies {T，F}
i.e. U(A_i) = T or F for all i∈N
Extend U to V{B} B is a wff implies {T，F} as follows.
V(A_i) = U(A_i)
V((a conjunction b))= {T if V(a) = T and V(b)=T， F otherwise.
similarly for disjunction and negation.
The proof that this V is unique relies on the Recursion Theorem
Def Let a be a wff. We say that
1. a is tautology if V(a)=T for all truth assignments of V
2. a is a contracition if (not a) is a tautology.
3. a is satisfiable if there is a truth assignment such that V(a) = T
Asuume we already know how to omit extra paranthesis and know order of procedure
Note， we can omit paranthesis because we establish order of procedure. not vice versa.
Implication associates from right to left.
Def A set Σ of wff’s logically implies a wff b， in symbols Σ logically implication （記号の出し方が分からない） b， if for all truth assignments U， whnere U’(a)=T for all a∈Σ，then U’(b)=T
We say that wff’s a and b are logically equivalent if a logically implies a and b≠a. we write a double logically implication b.
(this simply mean a and b become T/F exactly same time)
Theorem Σlogically implies a implies b IFF ΣU(a)logically implies b.
証明するには，文字数制限が………次回に続く。
コメント