Formal Logic
It is an old dream to write a formal, mathematical description of the laws of human thought.
The goals are to identify what it is that makes certain arguments correct and to identify
correct arguments only from their logical form. Work toward these goals is ancient. It
began with the early Greeks and was extensively developed by Aristotle (384-322 BC). The
study was again actively pursued in the Middle Ages. During the nineteenth and twentieth
centuries, the field developed rapidly, with explosive growth starting around 1930. The
understanding of formalized reasoning is one of the major topics of formal logic, and it
has been extensively applied to studying mathematical proofs. In computer science, formal
logic has many applications in areas such as database theory, artificial intelligence, program
language design, and automated verification of software and hardware. In database theory,
logic is used to formalize the definitions of queries. In artificial intelligence, logic is used
to formalize human inference. Proving a program to be correct can use logic-based notions
such as loop invariants and both pre- and postconditions. Formal logic also plays a major
role during many phases in the design of electronic computers, including the design of
efficient combinatorial networks or circuits.
This chapter provides an introduction to formal logic. First, we give the basic defini-
tions of propositional logic. These cover the usual material expected of a discrete math-
ematics course-propositional logic and logical truth. Next, we introduce normal forms
in propositional logic, particularly simple ways to write formulas, a topic that is now of
special interest in computer science. One application of normal forms is in combinatorial
network design. Examples of the relationship between normal forms and combinatorial
networks will be explained as well. Finally, we discuss an extension of propositional logic
involving predicates and quantifiers. These are key ideas in an extension of propositional
logic to predicate logic. An important part of predicate or first-order logic is to express, in
a single statement, how elements in a set of values can make the statement true.
Introduction to Propositional Logic
The simplest variant of formal logic is propositional logic. Its basic object is a sim-
ple, declarative sentence, called a proposition. Propositional logic is concerned with
combining sentences, such as "The world is round" and "Columbus was right" to form
"If the world is round, then Columbus was right."
89