Logic in Computer Science An Introductory Course for Master Students Wang j iwang@nudt.edu.cn ecture One Preliminaries Logic in Computer Science- p 1/16
Logic in Computer Science An Introductory Course for Master Students Wang Ji jiwang@nudt.edu.cn Lecture One Preliminaries Logic in Computer Science – p.1/16
Theory of equivalence relations (A,R) (E1) For all r: ra (E2 )For all y: If a Ry then y ro (E3)For all 9, z If a Ry and g Rx then Rz Logic in Computer Science- p 2/16
Theory of Equivalence Relations (A, R) (E1) For all x : xRx. (E2) For all x, y : If xRy then yRx. (E3) For all x, y, z : If xRy and yRz then xRz. Logic in Computer Science – p.2/16
Theory of equivalence relations (A,R) (E1) For all r: ra (E2 )For all y: If a Ry then y ro (E3)For all 3, 3, 2: If x Ry and y rx then c Re For all and y, if there is a u such that Ru and Ru, then for all z, o rx if and only if y rx Logic in Computer Science- p 2/16
Theory of Equivalence Relations (A, R) (E1) For all x : xRx. (E2) For all x, y : If xRy then yRx. (E3) For all x, y, z : If xRy and yRz then xRz. For all x and y, if there is a u such that xRu and yRu, then for all z, xRz if and only if yRz. Logic in Computer Science – p.2/16
A Primary Analysis The concept“ Proposition” A formal language formulas The concept“ Follow from” Consequence relation The concept t“ Proof a sequence of formulas, Axioms, rules Logic in Computer Science -p 3/16
A Primary Analysis The concept “Proposition” A formal language, formulas The concept “Follow from” Consequence relation The concept “Proof” A sequence of formulas, Axioms, Rules Logic in Computer Science – p.3/16
Induction Consider an initial set b Cu and a class f of functions containing just two members f and g Where f:U×U→ U and g:U→U Let b=a, b. How to define the set c which contains b,f(b,b),9(a),f((a),f(b,b), Logic in Computer Science- p 4/16
Induction Consider an initial set B ⊆ U and a class F of functions containing just two members f and g, where f : U × U → U and g : U → U Let B = {a, b}. How to define the set C which contains b, f(b, b), g(a), f(g(a), f(b, b)), · · · Logic in Computer Science – p.4/16