Transcript The Boolean Connectives

Language, Proof and
Logic
The Boolean Connectives
Chapter 3
3.0
Truth-functional connectives
The Boolean connectives are used to form compound sentences from
atomic ones.
They are called truth-functional connectives because the truth value
of a compound sentence is fully determined by the truth values of
its components.
Truth tables are the most straightforward way to define Boolean
connectives.
Another way is through Henkin-Hintikka games.
3.1
Negation 
P
Truth table:
TRUE
FALSE
P
FALSE
TRUE
Game:
Committing to the truth of  P means committing to the falsity
of P.
Committing to the falsity of P means committing to the truth
of P.
Atomic sentences and their negations are called literals.
“You try it” on page 69.
3.2
Truth table:
Conjunction 
P
Q
TRUE
TRUE
FALSE
FALSE
TRUE
FALSE
TRUE
FALSE
PQ
TRUE
FALSE
FALSE
FALSE
Game:
If you commit to the truth, then your opponent chooses P or Q, and the
game continues as if you had committed to the truth of that simpler
component.
If you commit to the falsity, then you have to choose either P or Q and,
and the game continues as if you had committed to the falsity of that
component.
“You try it” on page 72.
3.3
Truth table:
Disjunction 
P
Q
TRUE
TRUE
FALSE
FALSE
TRUE
FALSE
TRUE
FALSE
PQ
TRUE
TRUE
TRUE
FALSE
Game:
If you commit to the truth, then have to choose either P or Q, and the
game continues as if you had committed to the truth of that simpler
component.
If you commit to the falsity, then your opponent chooses either P or Q,
and the game continues as if you had committed to the falsity of that
component.
“You try it” on page 76.
3.4
Ambiguity and parentheses
Parentheses must be used whenever ambiguity would result from their
omission. In practice, this means that conjunctions and disjunctions
should be “wrapped” in parentheses whenever combined by means of
some other connective.
P  Q  R is ambiguous,
should be either P  (Q  R) or (P  Q)  R
3.5
Equivalent ways of saying things
PQ  QP
PQ  QP
PP  P
PP  P
Double negation: P  P
DeMorgan 1:
(PQ)  PQ
DeMorgan 2:
(PQ)  PQ
3.6.a
Translation
In order for a FOL sentence to be a good translation of an English
sentence, it is sufficient that the two sentences have the same truth
values in all possible circumstances.
It is not sufficient that they have the same truth value in some particular
world.
3.6.b
Translation
1. The English expression “and” sometimes suggest temporal ordering;
the FOL expression  never does.
Bob went home and ate
2. The English expressions “but”, “however”, “yet”, “nonetheless”,
“moreover” are all stylistic variants of “and”.
Bob was sleepy but he did the homework
3. The English expressions “either” and “both” are often used like
parentheses to clarify an otherwise ambiguous sentence.
Either Bob is home and Jane is home or Max is happy
Max is happy or both Bob is home and Jane is home