Transcript Truth Trees

Truth Trees
Intermediate Logic
Truth Table Method
• The truth table method systematically exhausts all
possible truth value combinations of the statements
involved.
• In the truth-table we look for a row that reflects a
certain possibility, and that will tell us the answer to
whatever question we had.
– E.g. If we want to know whether or not a certain statement
is a tautology, we are interested in the possibility of that
statement to be false; the statement is a tautology iff it is
not possible for that statement to be false
– For an argument: Is it possible to have all true premises and
a false conclusion? If so, invalid. If not, valid.
Drawback and Room for Solution
• A drawback of the truth table method is that
the number of rows grows exponentially.
• Fortunately, there is room for a solution to this
problem. Since all we are interested in, is the
existence of a specific combination of truth
values of the statements involved, all we need
to find is one example of such a case. Once we
have found such a case, there is no need to
exhaust all other cases.
Simple Solution: Stopping Early
• One solution to the problem of big truth tables is
therefore to simply stop once you have found a row
that represents the combination of truth values you
are interested in.
• Thus, rather than working out a truth table column by
column, you may want to do it row by row, so that
you can stop as soon as you have found a row of the
kind you are looking for.
• A big drawback of this approach is that if no row of
the kind you are looking for exists, then you have to
complete the whole truth table after all.
A More Focused Search
• Consider the following argument:
P  (Q  R)
R  Q
R
• We are interested in whether all premises can be
true and the conclusion false:
– In order for the conclusion to be false, R must be false.
– In order for the second premise to be true while R is
false, Q must be false.
– In order for the first premise to be true while Q and R
are both false, P must be false.
The Short Truth Table Method
• The Short Truth Table Method assigns truth values to
the involved atomic and complex statements in order
to try and obtain a certain combination of truth
values:
P  (Q  R)
F T F FF
RQ
F TTF
/
R
F
• The Short Truth Table Method thus tries to
generate one row of the truth table that has the
combination of truth values you are interested in.
Short Truth Table Method and
Indirect Proof
• As you assign truth values to certain statements, the
truth values of other statements can be forced.
• If you are forced to make a statement both true and
false, then you know that the combination of truth
values you are looking for does not exist:
P  (Q  P)
TF TF F
 Contradiction, so the
statement is a tautology!
• The short truth table method is therefore often a
kind of proof by contradiction or indirect proof
Drawback of the Short Truth Table
Method
• A drawback of the short truth table method is that you
are not always forced to assign any further truth
values:
R  (Q  P)
T T
(Q  R)  P
T
T
RP
T
Q
T
• At this point, you can choose to assign certain
truth values, but if your choice does not lead to the
row you are looking for, then you need to try a
different option, and the short truth table method
has no tools to do go through all of your options in
a systematic way.
Truth Trees
• The obvious solution to the drawback of the short
truth table method is to incorporate tools to
systematically keep track of multiple options.
• One method that does so is the truth tree method:
– The truth tree method tries to systematically derive a
contradiction from the assumption that a certain set of
statements is true.
– Like the short table method, it infers which other
statements are forced to be true under this assumption.
– When nothing is forced, then the tree branches into the
possible options.
Decomposition Rules for Truth
Trees
P 
P
PQ 
P
Q
PQ 
PQ 
P
Q
P
(PQ) 
P
Q
Q
PQ 
P
Q
P
Q
(PQ) 
P
Q
(PQ) 
P
Q
(PQ) 
P
Q
P
Q
Truth Tree Example
(((PQ)R)  (P(QR))) 
(PQ)R 
(P(QR)) 
P
(QR) 
Q
((PQ)R) 
P(QR) 
PQ 
All branches close
R
 the original
P
statement cannot be
Q
false  tautology!
R
(PQ)  R
×
P Q
×
×
P
×
Q  R 
Q
×
R
×
Further Rules for Truth Trees
• A decomposable statement is any statement that is not
a literal.
• A sentence belongs to every branch below it.
• You can close a branch if an atomic statement and its
negation both belong to that branch.
• Every undecomposed decomposable statements needs
to be decomposed in every open branch it belongs to.
• A branch is finished if there are no undecomposed
decomposable statements that belong to it.
How to Use Truth Trees
• At the ‘root’ of the tree, write down all statements
that you try and make true according to the
combination of truth values you are interested in.
• Decompose according to the rules until you have a
finished open branch or until all branches close.
– If there is a finished open branch, then that means that it is
possible for all statements at the root of the tree to be true.
– If all branches close, then that means that it is not possible
for all statements at the root of the tree to be true.
– It is up to you to draw the appropriate conclusion from this.
Example: Testing for Validity
• To use a tree to test for validity:
– 1. Write down at the root of the tree all premises
and the negation of the conclusion
– 2. Work through the tree until you find an open and
completed branch or all branches are closed
– 3a. If you found an open and completed branch,
then that means that it is possible for all statements
in the root of the tree to be true, which in turn
means that it is possible for all premises to be true
while the conclusion is false. Hence, the argument
is invalid.
– 3b. If all branches closed, the opposite is true, i.e.
the argument is valid.
How to Avoid Bushy Trees
• Since at any point there can be multiple
undecomposed decomposable statements, the tree is
going to look different based on which statement you
choose to decompose.
• Since more branches means more work, you want to
avoid branching as much as possible. So, as a
heuristic:
– Choose statements that don’t branch
– If you have to branch, choose those that you know will
quickly lead to a closed branch.
– If you don’t know which one leads quickly to a closed
branch, choose a large statement (why?)
Truth Trees for
Predicate Logic
Intermediate Logic
Running Examples
Valid Argument (13.24):
x (Cube(x)  Small(x))
x Cube(x)  x Small(x)
Invalid Argument (13.25):
x Cube(x)  x Small(x)
x (Cube(x)  Small(x))
Truth-Functional Expansions
• Suppose that our Universe of Discourse (UD)
contains only the objects a and b.
• Given this UD, the claim x Cube(x) is true iff
Cube(a)  Cube(b) is true.
• Similarly, the claim x Cube(x) is true iff Cube(a)
 Cube(b) is true.
• The truth-functional interpretation of the FO
statements given a fixed UD is called the truthfunctional expansion of the original FO
statement with regard to that UD.
Truth-Functional Expansions
and Proving FO Invalidity
• Truth-Functional expansions can be used
to prove FO invalidity. Example (13.25):
x Cube(x)  x Small(x)
x (Cube(x)  Small(x))
UD = {a,b}
T
T
F
T
F
T T
(Cube(a)  Cube(b))  (Small(a)  Small(b))
(Cube(a)  Small(a))  (Cube(b)  Small(b))
T
F F
F
F
F T
This shows that there is a world in which the premise is
true and the conclusion false. Hence, the original argument
is FO invalid.
Truth-Functional Expansions
and Proving FO Validity
• If the truth-functional expansion of an FO argument in
some UD is truth-functionally invalid, then the original
argument is FO invalid, but if it is truth-functionally valid,
then that does not mean that the original argument is FO
valid.
• For example, with UD = {a}, the expansion of the
argument would be truth-functionally valid. In general, it
is always possible that adding one more object to the UD
makes the expansion invalid.
• Thus, we can’t prove validity using the expansion
method, as we would have to show the expansion to be
valid in every possible UD, and there are infinitely many
UD’s.
• The expansion method is therefore only good for proving
invalidity. Indeed, it searches for countermodels.
The Expansion Method as a
Systematic Procedure
• Still, the expansion method can be made
into a systematic procedure to test for FO
invalidity:
– Step 1: Expand FO argument (which can be
done systematically) in UD = {a}.
– Step 2: Use some systematic procedure (e.g.
truth-table method or truth-tree method) to
test whether the expansion is TF invalid. If it is
TF invalid, then stop: the FO argument is FO
invalid. Otherwise, expand FO argument in
UD = {a,b}, and repeat step 2.
A More Focused Search
• A further drawback of the expansion method is
that the search for a counterexample is very
inefficient.
• A focused search for a counterexample is more
efficient:
– (13.25) I want there to be at least one cube, and at
least one small object, but no small cubes. So, if we
have a cube, a, then a cannot be small, so I need a
second object, b, which is small, but not a cube.
Counterexample, so the argument is invalid.
Advantage of a Focused Search
• The focused search method is like the indirect
truth-table method.
• Indeed, like the indirect truth-table method, the
focused search method can prove validity:
– (13.24) I want there to be at least one small cube. Let
us call this small cube a. How, I don’t want it to be
true that there is at least one cube and at least one
small object. However, a is both a cube and small.
Contradiction, so I can’t generate a counterexample.
Truth-Trees for Predicate Logic
• Like the direct method, the focused search
method needs to be systematized,
especially since the search often involves
making choices.
• Fortunately, the truth-tree method, which
systematized the indirect truth-table
method in truth-functional logic, can be
extended for predicate logic.
Truth-Tree Rules for Quantifiers
x (x)

x (x)
x (x)
x (x) 
x (x)

(c)
with ‘c’ a
new constant
in that branch
x (x)
(c)
with ‘c’ any
constant
Truth-Tree Rules for Identity
(c)
c = d (or d = c)
(d)
(where (d) is the result
of replacing any number
of c’s with d’s in (c))
aa
×
Truth-Tree Example I
x Cube(x)  x Small(x) 
x (Cube(x)  Small(x)) 
x Cube(x)

x Small(x)

x (Cube(x)  Small(x))
Cube(a)
Small(b)
(Cube(a)  Small(a)) 
(Cube(b)  Small(b)) 
Cube(a)
Small(a)
×
Cube(b)
Small(b)
Open branch,
×
so it’s invalid
Truth-Tree Example II
x (Cube(x)  Small(x))

(x Cube(x)  x Small(x)) 
Cube(a)  Small(a) 
Cube(a)
Small(a)
x Cube(x) 
x Cube(x)
x Small(x) 
x Small(x)
Small(a)
Cube(a)
×
×
All branches close,
so it’s valid
Modifications on Tree Method
• Since universal statements never get checked
off, you don’t have to instantiate a universal in
every branch that it belongs to.
• An open branch is finished if every statements in
that branch that has not been decomposed is
either a literal or a universal that has been
instantiated for every constant in that branch.
Rules of KE Calculus
P
P
DN
PQ
P
Q
(P  Q)
P
Q
Alpha


Branch
PQ
P
Q
PQ
P
Q
PQ
P
Q
(P  Q)
P
(P  Q)
P
PQ
Q
P
PQ
P
Q
(P  Q)
P
Q
Q
Beta
(P  Q)
P
Q
Eta
Q
HW 4
• 1. Demonstrate that 8.47 from LPL is invalid
using:
– a. the short truth-table method
– b. the truth tree method
• 2. 4.4.1.c from Bostock
• 3. Use the expansion method to show that (4)
from 3.6.3.b from Bostock is not valid
• 4. 4.4.1.i from Bostock
• 5. Show that KE Calculus can do whatever the
truth tree method can do