# Logic, Information and Computation (LGIC)

**LGIC 010 Formal Logic I**

This course provides an introduction to some of the fundamental ideas of logic. Topics will include truth functional logic, quantificational logic, and logical decision problems.

Taught by: Singer

One-term course offered either term

Also Offered As: PHIL 005, PHIL 505

Activity: Lecture

1.0 Course Unit

**LGIC 210 Discrete Mathmatics I**

Topics will be drawn from some subjects in combinatorial analysis with applications to many other branches of math and science: graphs and networks, generating functions, permutationsm posets, asymptotics.

Course not offered every year

Also Offered As: MATH 340

Prerequisite: MATH 114 OR MATH 115

Activity: Lecture

1.0 Course Unit

**LGIC 220 Discrete Mathematics II**

Topics will be drawn from some subjects useful in the analysis of information and computation: logic, set theory, theory of computation, number theory, probability, and basic cryptography.

Also Offered As: MATH 341

Prerequisites: MATH 340, LGIC 210

Activity: Lecture

1.0 Course Unit

**LGIC 310 Logic I**

Propositional logic: semantics, formal deductions, resolution method. First order logic: validity, models, formal deductions; Godel's completeness theorem, Lowenheim-Skolem theorem: cut-elimination, Herbrand's theorem, resolution method. Computability: finite automata, Turing machines, Godel's incompleteness theorems. Algorithmically unsolvable problems in mathematics.

Taught by: Scedrov, Towsner, Weinstein

Course not offered every year

Also Offered As: MATH 570, PHIL 410

Prerequisite: MATH 371 OR MATH 503

Activity: Lecture

1.0 Course Unit

**LGIC 320 Logic II**

The second semester of a two-semester course on the fundamental results and techniques of mathematical logic. Topics will be drawn from model theory, proof theory, recursion theory, and set theory. Connections between logic and algebra, analysis, combinatorics, computer science, and the foundations of mathematics will be emphasized.

Taught by: Scedrov, Towsner, Weinstein

Course not offered every year

Also Offered As: MATH 571, PHIL 413

Prerequisite: MATH 570

Activity: Seminar

1.0 Course Unit