Lecture 1 (2.11.97)
Overview ,
Course home page ,
Introductory example: Polynomials
Polynomials are expressions defined inductively.
With a polynomial p we can associate a function
F(p): Reals --> Reals
F is a meaning function for polynomials.
It is defined inductively.
Instead of the reals we can take any ring R.
Then $F_R(p)$ is function R --> R.
Representation of structures
We recall the geenral definition of $\tau$-structures.
We looked at different representations of
graphs as relational structures.
-
A graph with the vertices as universe and a binary relation R_E
for the edges.
(=standard representation of graphs)
-
A graph with set of vertices and edges as universe,
and tow binary predicate for vertices beginning and ending an edge,
respectively
-
Exercise: find other representations for graphs.
-
Second Order Logic
We gave the definition of Second Order Logic $SOL(\tau)$,
and repeated the definition of First Order Logic
$FOL(\tau)$, both syntax and meaning function.
We also defined $MSOL(\tau)$, Monadic Second Order Logic,
and $ESOL(\tau)$, Existential Second Order Logic.
We discussed graph properties (in both presentations).
- Regularity of fixed in-(out)-degree is $FOL$-definable.
- Non-Connectivity, definable in Monadic ESOL.
We shall see that it is not definable in $FOL$.
- graphs having a cycle definable in $ESOL$ (but not
in $FOL$).
- 3-colorabilty, definable in $ESOL$ (but not in $FOL$).
- Find definitions for Eulerian graphs, Hamiltonian graphs,
planar graphs.......
Next lecture:
Lecture 2