Why Logic is
Important for Computer Science and Mathematics
A Czech translation of this page is available at Scientific
and Technical Translation .
A Swedish translation of this page is available at
Science Blog: https://www.expertoautorecambios.es/science/?p=998 .
An Estonian translation of this page is available at:
A Portuguese translation of this page is available
at:
https://www.homeyou.com/~edu/ciencia-da-computacao-e-matematica
Logic is concerned with forms of reasoning. Since reasoning is involved in most intellectual activities, logic is relevant to a broad range of pursuits. The study of logic is essential for students of computer science. It is also very valuable for mathematics students, and others who make use of mathematical proofs, for instance, linguistics students. In the process of reasoning one makes inferences. In an inference one uses a collection of statements, the premises, in order to justify another statement, the conclusion. The most reliable types of inferences are deductive inferences, in which the conclusion must be true if the premises are. Recall elementary geometry: Assuming that the postulates are true, we prove that other statements, such as the Pythagorean Theorem, must also be true. Geometric proofs, and other mathematical proofs, typically use many deductive inferences.
Most of our logic courses include precise analyses of the characteristics of deductive inference. These courses introduce some special symbols in what are called ``formal languages,'' but logic is not symbol manipulation. The courses teach general concepts and methods that are useful independently of formal languages. Students learn how to construct proofs in English, as well as in a formal language, so the concepts and methods that are learned can be used in a variety of contexts. One even learns how to prove theorems about formal languages; this is especially important for computer science, linguistics, and some branches of mathematics.
The idea of a general purpose computer, the Turing Machine, was invented in the course of research in logic. Computer programs are written in special, symbolic languages, e.g., Fortran, C++, Lisp, Prolog. These languages contain features of logical symbolism, and Lisp and Prolog are derived from formal languages for logic. Through such connections, the study of logic can help one in the design of programs. Other mathematical techniques covered in PHL 313K, e.g., recursive definitions, are widely used in programs. The set theory covered in PHL 313K is used in modern database designs. But computer science is not just programming. It includes the logical and mathematical analysis of programs. With such analyses, one can prove the correctness of procedures and estimate the number of steps required to execute a specified program. Modern logic is used in such work, and it is incorporated into programs that help construct proofs of such results. Logic also has a role in the design of new programming languages, and it is necessary for work in artificial intelligence and cognitive science. Some parts of logic are used by engineers in circuit design.
An understanding of the subjects taught in PHL 313K is required to be a successful computer science major: 1. Just as calculus is used in engineering courses, basic logic and set theory are used in many computer science courses. 2. Upper division CS courses are not programming drills; these courses cover general principles and require mathematical proofs about these principles. PHL 313K teaches the basic principles and methods for constructing and assessing proofs.
Mathematicians reason about abstract concepts, for example, continuous functions, algebraic systems such as ``rings,'' and topological spaces. Most math students learn to write proofs about such things by following examples in their classes. This is part of learning math, but it is slow, and often leads to confusions. Math majors who study logic find that it helps them in their mathematical thinking. It is helpful in avoiding confusions and helpful in constructing clear, convincing proofs. The study of logic is essential for work in the foundations of mathematics, which is largely concerned with the nature of mathematical truth and with justifying proofs about mathematical objects, such as integers, complex numbers, and infinite sets. Math majors at UT are not required to take a logic course, but those who do almost always report that it is interesting and useful.
PHL 313K is an introduction to logic, elementary set theory, the foundations of number theory, and uses of induction and recursion. It requires serious study, but it covers interesting and useful material. Good follow up courses, for students interested in more advanced logic, are PHL 344K (= M 344K) and PHL 358.
Robert L. Causey
Update by RLC: 09/22/17