LECTURE: M-W-F: 9-9:50 @ DBH 1500
DISCUSSION: M-W: 8-8:50 @ DBH 1500

INSTRUCTOR: NAM TRANG
OFFICE HOURS: W 2-3, F 2:30-3:30 @ RH 410N FINALS WEEK'S OFFICE HOUR: T: 3-6

COURSE SYLLABUS AND POLICIES     UCI Academic Honesty Policies     UCI Student Resources

HOMEWORK ASSIGNMENTS:     HW1     HW2     HW3     HW3 Solution     HW4 (due Nov 13 now)     HW4 Solution     HW5     HW5 Solution     HW6     HW6 Solution For 1 and 3     HW6 Solution For 2 and 1(b), 1(c)

READING ASSIGNMENT: Section 2.4 and 2.5, Section 2.6 (focusing on applications of compactness, don't worry about enumerability/decidability), and Section 2.8.

QUIZ:     Quiz 4 (Nov 13)     Quiz 5 (Nov 22)     Quiz 6 (Dec 6)

PRACTICE PROBLEMS:     Set 1     FINAL PRACTICE PROBLEMS    FINAL PRACTICE PROBLEMS SOLUTION (note the corrections of typos on problem 11)

COURSE PROGRESS
Week 0
F: Went over class logistics, syllabus, defined sets, tuples, functions, relations, Cartesian products
Week 1
M: Equivalence relations, induction on natural numbers, language, wffs in sentential logic, algorithm for determining whether an expression is a wff (using trees)
W: Truth tables, truth assignments, examples of how to evaluate a formula given a truth assignment on its propositional symbols, definition of tautological implications,
F: defined tautology and tautological equivalence, gave examples of showing tautological implications: {A,-A} |= B, {A, A->B}|= B for all A, B; {A->B} and {-A or B} are tautologically equivalent, gave examples of showing formulas are tautology( with truth table method and with short-cuts), gave conventions for ommiting parentheses.
Week 2
M: Boolean functions, examples of computing Boolean functions of wffs, definition of complete sets of connectives, proved that alpha tautologically implies beta iff B^n_alpha(X) <= B^n_beta(X) for all sequences X of length n with values in {T,F}
W: Boolean functions (cont.), Post's theorem on completeness of the set of connectives, disjunctive normal forms. Showed, as corollaries of Post's theorem, every boolean function can be realized by a formula in disjunctive normal form, and the set {NOT, AND, OR} is complete.
F: Shows {AND, NOT} and {OR, NOT} are complete; gave an example of an incomplete set of connectives: {AND, IMPLIES}, logic gates and electrical devices. Gave examples of constructing logic gates for: (A AND B) OR (NOT A AND NOT B) and the multiplexor
Week 3
M: Depth of a wff and delay of an electrical device, Carnaugh's map method used to reduce the depth of a given wff
W: Carnaugh's map method (cont.): gave more examples/tricks on how to do the Carnaugh map; give the statement of the compactness theorem, prove a corollary of the theorem that if Sigma tautologically implies tau then there is a finite subset of Sigma that tautologically implies tau
F: Defined the Goedel order, showed there are bijections between N and finite sequences of elements in N; started on the proof of the compactness theorem for sentential logic
Week 4
M: Finished the proof of the compactness theorem
W: Introduction to first order logic; defined the language (logical symbols + special symbols); gave examples of first-order languages: language of set theory, language of number theory, language of groups; defined terms and formulas
F: First order-logic (cont.), some examples of converting statements in English to wffs in a first order language; for example, express "there is a set that contains no elements" in L_{ST}; express "every element of a group has a unique inverse" in L_{GT}; express "there is no largest natural number" and "the sum of two odd numbers is an even number" in L_{NT}
Week 5
M: Structures of first-order logic, examples (L_NT and the natural numbers with the usual interpretations of the symbols being the canonical model of L_NT), evaluations of variables/terms: given a function s: V--> M, where M is the domain of our model \script(M), defined t^\script(M)[s]: the evaluation of the term t in the model \script(M) with respect to s.
W: Reviews for midterm
F: Midterm
Week 6
M: (Section 2.2) Returned midterm, went over results, grading rubriks, defined satisfaction relation in first-order logic (for atomic formulas)
W: (Section 2.2) Satisfaction relation in first-order logic (cont.), examples of how to verify satisfaction.
F: Holiday. No class
Week 7
M: (Still in Section 2.2) More examples of how to verify satisfaction; defined free/bound occurrence of a variable in a formula.
W: (Still in Section 2.2) Continued with defining free/bound occurrence of a variable.
F: (Still in Section 2.2) Lemma about satisfaction of a formula only depends on the evaluations of variables with free occurrences in that formula; Theory, models of theories Logical implications, examples of logical implications
Week 8
M: (Still in Section 2.2) Pop quiz on free/bound occurrences of variables; more examples of logical implications; definability, examples of definable sets,
W: Finished Section 2.2 (gave more examples on definable sets); Start section 2.4: defined tautologies in First Order Logic; listed the Axioms of FOL and Rules of Inference.
F: Thanksgiving. No class.
Week 9
M: (Section 2.4) Tautology, axioms of first order logic, rules of inference; defined substitutability, \varphi(v/t); defined a formal proof and the relation "Sigma proves tau".
W: (Section 2.5) Give some examples of formal proofs, statement of the soundness theorem, completeness theorem for first order logic (2 versions each). Characterize deductively inconsistent sets of formulas. State and prove the compactness theorem (from the soundness and completeness theorem).
F:Starts an application of compactness theorem: if a set of sentences has arbitrarily large finite models, then it has an infinite model. This gives: the set of finite models cannot be Mod(Sigma) for any set of sentences Sigma and the set of infinite models cannot be Mod(tau) for any sentence tau. Define elementary equivalence. Construction of a model M elementarily equivalent to the natural numbers but has an "infinite element", namely an element c that is bigger than every natural number.
Week 10
M: Defined elementarily equivalent models; defined elementary embeddings; Construction of a model elementarily equivalent to (N, <) but has an infinite <-descending sequence.
W: Constructed a model elementarily equivalent to the natural numbers but has an element bigger than every natural number; Constructed a nonstandard model of the reals using the compactness theorem: the model contains an element bigger than every real, contains "infinitesimals", i.e. epsilon such that 0 < epsilon < r for every real r.
F: Addendum to the construction of a nonstandard model of the reals; went over details again of constructing a model elementarily equivalent to the natural numbers but has an infinite descending sequence; final reviews.
-->