12
Formal Logic
Finally, the truth tables for conjunction, disjunction, and negation are implemented
by electronic devices called “gates” (AND gate, OR gate, inverter, respectively)
that are fundamental building blocks in computer circuitry. We’ll see in Chapter
8 (Boolean Algebra and Computer Logic) how to combine these gates into more
complex logic networks to carry out specific tasks.
an algorithm
To test whether a wff is a tautology, we can always write its truth table. For n
statement letters, 2
n
rows will be needed for the truth table. Suppose, however,
that the wff has implication as its main connective, so that it has the form P S Q
where P and Q are themselves wffs. Then we can use a quicker procedure than
constructing a truth table to determine whether P S Q is a tautology. We assume
that P S Q is not a tautology, and we see whether this leads to some impossible
situation. If it does, then the assumption that P S Q is not a tautology is also impossible, and P S Q must be a tautology after all.
To assume that P S Q is not a tautology is to say that it can take on false
values, and, by the truth table for implication, P S Q is false only when P is
true and Q false. By assigning P true and Q false, we determine possible truth
values for the wffs making up P and Q. We continue assigning the truth values so
determined until all occurrences of statement letters have a truth value. If some
statement letter is assigned both true and false values by this process, we have an
impossible situation, so the wff P S Q must be a tautology. Otherwise, we have
found a way to make P S Q false, and it is not a tautology.
What we have described is a set of instructions—a procedure—for carrying out the task of determining whether P S Q is a tautology. This procedure
can be executed by mechanically following the instructions; in a finite amount
of time, we will have the answer. In computer science terms, the procedure is an
algorithm.
defInItIon aLgoriThM
An algorithm is a set of instructions that can be mechanically executed in a finite
amount of time in order to solve some problem.
Algorithms constitute the very heart of computer science, and we will have
much to say about them throughout this book. You are probably already aware that
the major task in writing a computer program for solving a problem consists of
devising an algorithm (a procedure) to produce the problem solution.
Algorithms are often described in a form that is a middle ground between
a purely verbal description in paragraph form (as we gave for deciding whether
P S Q is a tautology) and a computer program (that, if executed, would actually carry out the steps of the algorithm) written in a programming language.
This compromise form to describe algorithms is called pseudocode. An algorithm
written in pseudocode should not be hard to understand even if you know nothing
about computer programming. The only thing to note about the pseudocode used
in this book is that lines preceded by double slashes (//) are explanatory comments, not part of the algorithm itself.
Following is a pseudocode form of the algorithm to determine whether P S Q
is a tautology.
Formal Logic
Finally, the truth tables for conjunction, disjunction, and negation are implemented
by electronic devices called “gates” (AND gate, OR gate, inverter, respectively)
that are fundamental building blocks in computer circuitry. We’ll see in Chapter
8 (Boolean Algebra and Computer Logic) how to combine these gates into more
complex logic networks to carry out specific tasks.
an algorithm
To test whether a wff is a tautology, we can always write its truth table. For n
statement letters, 2
n
rows will be needed for the truth table. Suppose, however,
that the wff has implication as its main connective, so that it has the form P S Q
where P and Q are themselves wffs. Then we can use a quicker procedure than
constructing a truth table to determine whether P S Q is a tautology. We assume
that P S Q is not a tautology, and we see whether this leads to some impossible
situation. If it does, then the assumption that P S Q is not a tautology is also impossible, and P S Q must be a tautology after all.
To assume that P S Q is not a tautology is to say that it can take on false
values, and, by the truth table for implication, P S Q is false only when P is
true and Q false. By assigning P true and Q false, we determine possible truth
values for the wffs making up P and Q. We continue assigning the truth values so
determined until all occurrences of statement letters have a truth value. If some
statement letter is assigned both true and false values by this process, we have an
impossible situation, so the wff P S Q must be a tautology. Otherwise, we have
found a way to make P S Q false, and it is not a tautology.
What we have described is a set of instructions—a procedure—for carrying out the task of determining whether P S Q is a tautology. This procedure
can be executed by mechanically following the instructions; in a finite amount
of time, we will have the answer. In computer science terms, the procedure is an
algorithm.
defInItIon aLgoriThM
An algorithm is a set of instructions that can be mechanically executed in a finite
amount of time in order to solve some problem.
Algorithms constitute the very heart of computer science, and we will have
much to say about them throughout this book. You are probably already aware that
the major task in writing a computer program for solving a problem consists of
devising an algorithm (a procedure) to produce the problem solution.
Algorithms are often described in a form that is a middle ground between
a purely verbal description in paragraph form (as we gave for deciding whether
P S Q is a tautology) and a computer program (that, if executed, would actually carry out the steps of the algorithm) written in a programming language.
This compromise form to describe algorithms is called pseudocode. An algorithm
written in pseudocode should not be hard to understand even if you know nothing
about computer programming. The only thing to note about the pseudocode used
in this book is that lines preceded by double slashes (//) are explanatory comments, not part of the algorithm itself.
Following is a pseudocode form of the algorithm to determine whether P S Q
is a tautology.