next up previous
Next: Wednesday, January 19 Up: Lecture Notes Previous: Lecture Notes

Tuesday, January 18

Today's lecture is about propositional logic.  It should be review for
anyone who took Math 187.

Main points (some to be covered later -- we got to point 2):

1.  definition of the propositional connectives; similarities and contrasts
with standard English usage.

2.  The method of truth tables; definition of the notion of "tautology".

3.  Definitions of the notions of "entailment" and "equivalence"; these are
not propositional connectives, and in particular are not the same as
implication and biconditional.

4.  Issues of syntax: precedence and grouping; relationships with
associative and commutative laws.

5.  Algebraic laws for propositional connectives in general.

Point 1 (definition of the propositional connectives; similarities and
contrasts with standard English usage.)

The notation I use here will not be the same as that in the book; it
will correspond to the notation in the theorem prover, though (so it
won't be useless to learn it :-)

All these operations are "truth functional":  they are operations
on "sentences" or "propositions" which depend only on whether the
sentences are true or false.

Negation:

~true = false

~false = true

or in table format

P | ~P
------
T | F
F | T

Conjunction:

true & true = true
true & false = false
false & true = false
false & false = false

or in table format

P | Q | P & Q
-------------
T | T |   T
T | F |   F
F | T |   F
F | F |   F

Notice that the meanings of English "not" and "and" are very similar
to the mwanings of the logical operators.  We say that "Snow is white
and grass is green" exactly when it is true that snow is white and it
is true that grass is green.

With "not", the meaning is the same as in English but the grammar is
not the same.  We don't say "Not grass is green".  The circuitous
formulation "It is false that grass is green" has the same grammar as
the negation operator.

In English, sentences like

Tom and Mary love ice cream

expand to

Tom loves ice cream and Mary loves ice cream

or even

Tom loves ice cream & Mary loves ice cream

but there is a non-truth-functional use of "and" one should be careful
of:

Tom and Mary carried the half-ton safe

probably is not equivalent to 

Tom carried the half-ton safe and Mary carried the half-ton safe.

In general, one should be careful about the English habit of linking
subjects and predicates with what appear to be propositional connectives;
this could be formalized in a logical language, but historically no
one has chosen to do this.

Disjunction:

true | true = true
true | false = true
false | true = true
false | false = false

or in table format

P | Q |  P|Q
-------------
T | T |   T
T | F |   T
F | T |   T
F | F |   F

The meaning of "or" shown above (called "inclusive or" and written and/or
in legal documents) is the usual mathematical meaning of "or".  This contrasts
with English usage, in which "or" often has the meaning found in

Each child may have cheese cake or carrot cake

in which context we suspect that they need to choose one of these
delectable alternatives.  We call this "exclusive or" or "xor" for short.

true <+> true = false
true <+> false = true
false <+> true = true
false <+> false = false

or in table format 

P | Q | P <+> Q
---------------
T | T |    F
T | F |    T
F | T |    T
F | F |    F

This connective occurs much less often than the connective | of
inclusive disjunction, but it does have interesting properties.  We do
need to bear in mind that the meaning of "or" in mathematical text may
be assumed to be "inclusive or" unless we are specifically told that
it cannot; the ambiguity or context dependence in standard English is
to be eliminated from formal mathematical usage.

Implication:

true -> true = true
true -> false = false
false -> true = true
false -> false = true

or in table format:

P | Q | P -> Q
--------------
T | T |   T
T | F |   F
F | T |   T
F | F |   T

We admit the notation P <- Q equivalent in meaning to Q -> P;
we could provide tables for this, but we choose not to.

The English sentence "if P then Q" or "Q if P" does not usually have
this truth functional interpretation (called the "material
conditional").  The merit of the mathematical usage is that it makes
cases of "if P then Q" which are vague in English usage (what is the
truth value of "if 2+2=5 then Napoleon conquered China"?  What about
"If General Washington crossed the Delaware then 2+2=4"?  Something
confuses us about sentences like these) have precise truth values.
The actual meaning of the conditional in English is a topic of
philosophical debate, and we cannot pretend to analyze it here.  What
we do say is that in our apparently English usage as well as our
symbolic usage we mean by "if P then Q" nothing more than "either P is
false or Q is true or both" (you can check that this is the meaning
expressed by the tables above.  There are other forms of "implication"
which we will use in mathematics (one of them appears in tomorrow's
notes); all of them are precisely defined and rather different from
colloquial English usage.  The merit of this definition is that it is
truth functional (so precisely definable) and meets certain natural
expectations as to how it can be used in logical arguments (this will
be most easily seen in our later notes on "natural deduction").

Biconditional:

In English text, P if and only if Q is abbreviated P iff Q.

true <-> true = true
true <-> false = false
false <-> true = false
false <-> false = true

or in tabular format

P | Q | P <-> Q
--------------
T | T |   T
T | F |   F
F | T |   F
F | F |   T

The sentence P <-> Q is to be true just in case P and Q have the same
truth value.  The same kinds of comments about the relationship
between English usage of "if and only if" and mathematical usage apply
as in the case of the conditional, though it is harder to imagine
colloquial usage of this phrase.

I won't discuss the "nand" and "nor" connectives given in the book
here, except to say that the principal interest of these two
connectives is that either of them may be used to define _all_
propositional connectives, and that we will write "nand" as ~&
and "nor" as ~| in the notes and on the prover (if we need to).

Point 2.  (The method of truth tables; definition of the notion of
"tautology".)

All possible behavior of any expression in propositional letters and
propositional connectives can be analyzed by constructing a "truth
table".

For example, we analyze the expression P <-> (P & Q):

P | Q | P&Q | P<->(P&Q)
----------------------
T | T |  T  |  T
T | F |  F  |  F
F | T |  F  |  T
F | F |  F  |  T

We see that P<->(P&Q) has the same truth table as P->Q (which turns out to
be a useful fact).x

The method of truth tables is of limited practical usefulness, since an
expression with n propositional variables requires a truth table with 2^n
rows.  A related counting problem is to determine how many truth functions
with n arguments there are:  an expression with n propositional variables
has a truth table with 2^n rows, in each row of which we can insert T or
F:  there are 2^(2^n) different n-argument truth functions.  In particular,
there are 2^(2^2) = 2^4 = 16 different binary truth functions.

Exercise:  list the 16 different truth functions.  Are any of the functions
we have not listed likely to be useful?

Are any of these functions commutative but not associative?  Are any
of these functions associative but not commutative?



Randall Holmes
2000-05-05