# Logic, Information and Computation (LGIC)

**LGIC 010 Ideas in Logic and Computation**

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

Taught by: Weinstein

Course usually offered in spring term

Also Offered As: PHIL 005

Activity: Lecture

1 Course Unit

Notes: This is a Formal Reasoning course.

**LGIC 210 Applied Mathematics of Information and Computation I**

The first semester of a two-semester course designed to intoduce students to a range of mathematical subjects useful in the analysis of information and computation. This course will treat topics chosen from set theory, combinatorics, graph theory, and number theory.

Taught by: Scedrov, Towsner

Course usually offered in fall term

Also Offered As: MATH 340

Prerequisite: MATH 114 or MATH 115 or permission of the instructor

Activity: Lecture

1 Course Unit

**LGIC 220 Applied Mathematics of Information and Computation II**

The second semester of a two-semester course devoted to mathematical subjects useful in the analysis of information and computation. Topics will be drawn from automata theory, formal languages, computability and complexity, and information theory.

Taught by: Scedrov, Towsner

Course not offered every year

Also Offered As: MATH 341

Prerequisite: LGIC 210 or permission of the instructor

Activity: Lecture

1 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

One-term course offered either term

Also Offered As: MATH 570, PHIL 410

Prerequisite: Math 371 or Math 503

Activity: Lecture

1 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

One-term course offered either term

Also Offered As: MATH 571, PHIL 412

Prerequisite: LGIC 310 or permission of the instructor

Activity: Seminar

1 Course Unit