In this introductory chapter we write one very small program which will produce the truth table for one particular formula. The method is easily adapted to writing similar programs for other, even much larger formulas. Readers familiar with Pascal will want to skip this chapter entirely.
If you have never written a Pascal program on the computer that you are using, then you should write a tiny little program and get it running. Otherwise you will want to skip this section.
To write a program you need an editor to create and edit a file which will remain permanently on your disk area. If the program is a Pascal program, then it has to be processed by the Pascal compiler to produce another file. In most systems this resulting file has to be processed further by a linker which produces another file again. Only this last file is eventually executed by the computer.
To get started it is useful to begin with something entirely trivial. The following is the sort of program that you might use:
HELLO.PAS or something like that.
On a VAX you then compile it with the command
$-prompt again.
If the program contained an error which the Pascal compiler
detected,
then you should not try to link the faulty program
but go back to the editor to correct the error.
If the program when running did not produce the right output,
you should also go back to the editor to correct it.
On a Unix system the commands will be different
but essentially similar.
For most programs it is necessary to go through many cycles
of editing, compiling, linking and running.
Suppose your program is called MYPROG,
then the cycle is quite well described by the following:
HELLO program to write
HELLO
program to work properly, then you should get help from somebody.
In the remainder of this chapter we shall learn how to write a program which will produce the complete truth table for a particular formula of propositional logic. Different, but similar programs are easily written for different formulas. In Chapter 5 we shall write one program which can read any formula of propositional logic and produce its truth table. But such a general purpose program is not entirely trivial, so in this chapter we shall be content with writing special purpose programs for just one formula.
To make matters as easy as possible, we select as a demonstration formula one which only uses those propositional operators for which Pascal has obviously corresponding Boolean operators:
NOT binds more strongly than AND,
which binds more strongly than OR.
It is as if the formula were bracketed like this:
The formula contains three atomic formulas:
p, q and r.
So the full truth table will contain 2^3 = 8 lines.
Each such line should contain the current values
of the atomic formulas, together with the value of the big formula.
The 8 lines should be preceded by a header
line containing the names of the three atoms, then a space
and then the formula.
In the header line and in each of the 8 lines of the table,
the names of the atoms or the values of the atoms
should be separated by a space.
For the 8 values of the formula,
it will look best if they occur immediately below
the main operator of the formula, which is the second OR.
The truth values of the atomic formulas and of the big formula
could be written as 1 and 0, which is easiest on the eyes,
or as T and F which is just marginally easier to program.
This is what the output should look like:
The program has to start by writing the header line
containing the three atoms separated by a space,
then a larger space followed by the formula.
Because in the 8 lines of the table
the value of the formula has to be written directly
underneath the main operator of the formula,
it is useful to define two CONST strings:
one is the formula preceded by a few spaces,
the other is a blank string of spaces as long
as the formula string up to its main operator.
This is an easy way of ensuring the alignment.
Thus, to write the header line,
a string p q r is written out, followed
by the string constant for the formula.
Now the 8 lines of the table have to be written. For each line it is necessary to produce the truth values of the three atoms, to write them out, and then to write the truth value of the formula for these values. However, it is best not to think in terms of 8 lines but in terms of what has to be done for each of the 3 atoms.
Starting with p, then q and then r,
for each atom the values true and false have to be
assigned.
When r has been assigned a value,
the formula itself can be evaluated and the current line written out.
To assign first true and then false to an atom,
a FOR loop is useful.
It may be that you are only familiar with FOR loops
that use integers,
but they work equally well with boolean values.
It may be that you are only familiar with FOR loops
which go upward,
but by saying DOWNTO instead of TO
they can be made to go downwards.
In the case of Boolean values,
downwards means first true then false.
The form of such loops is:
p, q and r,
and to obtain a truth table with all the possible
combinations of values we nest the FOR loops for the three
atomic formulas:
p, q and r have to be declared
as Boolean variables in a VAR section at the beginning of the program.
In our case doing something or other means
writing out a line in the truth table.
So a write statement is called for which will
write the current values of the three atoms
and the current value of the formula.
All four of these are boolean values,
and Pascal would normally write them as TRUE and FALSE.
This would make a correct but unnecessarily wordy table,
it looks nicer if only single characters T and F are used.
These happen to be the first characters of what Pascal
would normally write,
so if we specify that the values are to be written
in a field of just one character,
only T or F will be written.
For example, if b is a Boolean expression,
then
b as just one character, T or F.
Since in the header line
each atom was followed by a space,
to achieve alignment the current value of each
atom has to be followed by a space.
Finally the value of the formula has to be written,
but it has to be preceded by a blank
which is as long as the formula up to its main operator.
This is the CONST string referred to earlier.
The value of the formula,
now given not as a string but as a Boolean expression,
is written next.
Each line in the truth table is written by
one single writeln statement.
The following is the standard Pascal source for the truth table program.
You might think that it is hardly worthwhile to write
a 12 line Pascal program to produce a truth table of 8 lines
plus one header line.
On the other hand, consider a formula with, say, six atomic formulas.
This will require a table of 2^6 = 64 lines,
but how long will the program be?
There are three more atomic formulas than in the program
that we have written,
so there will have to be three more nested FOR loops,
each of one extra line each.
That will make 15 lines in all.
Different constants:
Modify the program so that instead of writing T and F
for the truth values it writes 1 and 0.
A different programming language: If you know another programming language, like perhaps the C language, write the program in that language.
Other connectives:
Assume that the material implication connective is written IMP
and that the material equivalence connective is written IFF.
Write a formula using these connectives,
then write a Pascal program to produce a truth table for
this formula.
Note that IMP and IFF are not Pascal operators,
so you will have to find a way around that.
Summary: It would be useful if the truth table program could say at the end "tautology" if the formula was true in every line, or "contradiction" if the formula was false in every line, or "contingent" otherwise. Modify the program accordingly. Sometimes one does not even want to see the whole truth table but only this one-word summary. Modify the program so that it only writes the summary.
Values of subformulas: For teaching purposes many books show truth tables in which the truth value of each subformula is written under its main operator. This of course is how one does truth tables by hand. Think about how you would modify the program to write the values of subformulas. But do not bother to actually make the program do it --- for a program which only writes the table for a single formula it really is not worth it.
Non-classical logic: There are some logics which use more than two truth values --- three, four, even eight. If you know some of them, write a program to write a table for a single formula with these unconventional truth value.
Reading: If you had problems with understanding the Pascal program, then you should consult any one of the many and often very good introductory books on Pascal. Some of those recommended are: Cooper and Clancy (1985), Leestma and Nyhoff (1990), Peters (1986). If you had problems getting your program into the computer, read the manual for your editor.
A puzzle: The following is taken from "The Mind of the Year" competition in The Weekend Australian, September 8-9 1990, p 10.
At a quadruple marriage ceremony four men Arthur, Bill, Charlie and Don were marrying Erica, Fanny, Georgina and Helen, though not necessarily in that order. Consider the following statements:
If Fanny is not marrying Arthur, then Georgina is not marrying Charlie. If either Georgina or Helen is marrying Bill, then Arthur is marrying Fanny. If Charlie is not marrying Erica, then Bill is marrying Helen. If Georgina is marrying Don, then Bill is not marrying Fanny. If Don is not marrying Fanny, then Fanny is marrying Bill.
Who is marrying whom? Write a Pascal program to solve this puzzle. (Hint: think of the four women as variables, think of the four men as values.)