Transcript IM_FA16-02-SL_Transcription_Inferencingx

INF 385T: Information Modeling — Class 02
Unit 1: First Order Logic
Sentence Logic:
Transcription and Inferencing
Slides for August 31
Karen Wickett, [email protected]
School of Information
University of Texas at Austin
Fall 2016
1
Unit 1: First Order Logic
• Class 00: Basic Concepts
• Class 01: Sentence Logic: Syntax and Semantics
• Class 02: Sentence Logic: Inference (Truth Tables, ND and TT)
• Class 03: Predicate Logic: Syntax and Semantics
• Class 04: Predicate Logic: Inference (Truth Trees)
• Class 05: Metatheory
2
 Syntax of SL
Vocabulary
•
A, B, C, …
these are atomic sentences
•
&, V, , , ~
•
these are sentence connectives, the first four dyadic (binary), the last monadic
Grammar
[In what follows we use "X" and "Y" as metalinguistic variables that stand in for,
or “range over”, sentences (atomic or compound) in the language SL]
1) A, B, C, … are sentences of SL
2) If X is a (atomic or compound) sentence of SL, then so is (~X), “… the sentence
formed by taking X, writing a “~” in front of it, and surrounding the whole by
parentheses “(Teller).
3) If X and Y are sentences of SL, then so is (X & Y), “that is …“
4) If X and Y are sentences of SL, then so is (X v Y), “… ”
5) If X and Y are sentences of SL, then so is (X  Y), “that is…”
6) If X and Y are sentences of SL, then so is (X  Y)
7) Nothing else is a sentence of SL
3
Semantics of SL (informal summary)
 Syntax tells you what a correctly formed sentence is;
 Semantics tells you under what conditions a correctly formed sentence is
true.
 The semantics for SL has two components, one for atomic sentences and
one for compound sentences.
 Atomic sentences: In any possible situation each atomic sentence has exactly
one of two “truth values”, True ("T") or False ("F").
 Compound sentences: In every possible situation a compound sentence is
assigned a truth value (T or F, but not both) that is determined by the values
(in that situation) of its “immediate constituents”, in the following way…
4
 Valuation Rules for SL (Semantics)
•
Negation: ~X is true if and only if X is false
•
Conjunction: (X & Y) is true if and only if both X is true and Y is true,
•
Disjunction: (X v Y) is true if and only if either (or both) X is true or Y is true
•
Conditional: (X  Y) is true if and only if either (or both) X is false or Y is true
•
Biconditional: (X  Y) is true if and only if X and Y have the same truth value
•
In SL if a sentence is not true it is false.
5
Defining Semantics of SL Connectives
Using a Sentence-Variable -based truth table
X
Y
~X
XvY
X&Y
XY
XY
T
T
F
T
T
T
T
T
F
F
T
F
F
F
F
T
T
T
F
T
F
F
F
T
F
F
T
T
Where the italicized letters X and Y are “metalinguistic” variables
ranging over sentences (either simple or compound) of SL.
6
Transcription
We have our syntax and our semantics for SL, and truth tables will give us a way
to determine the validity of arguments.
•But, first we’ll need to get our arguments into SL.
•Strictly speaking, the translation of ordinary sentences into SL-sentences is not
part of the formal theory of Sentence Logic per se; but it is necessary in order to
apply formal logic to the world.
•In translation we often rely on intuition, and look for the underlying
propositional content amidst varying natural language forms
7
 Translation guidelines [Teller: “transcription”]
•
For the most part we try to provide a logically equivalent expression in SL.
•
i.e. an SL expression that is true if, and only if the natural language
expression is true.
—Only this is of course different than comparing the logical
equivalence of two sentences both in SL!
•
And one that is coordinated with other relevant translations.
—Don’t translate “Bill is home” as “B”in one place and “H” in
another!
•
We often leave logically relevant features unformalized.
•
e.g. Representing “Bill is at home” as “B” and “Mike is at home” as “M”
doesn’t formalize and make logically available the interesting fact that
they are both at home!
•
This is a complex area for logicians, but Teller’s two “Transcription Tests”
are a good place to start from a practical viewpoint.
8
Some Translation Problems
• Not all features can be captured with truth-functional connectives.
• Susan went home but Bill went fishing" is almost always treated the same as
"Susan went home and Bill went fishing”, even though it seems to say
something more. (but what?)
• "Mike got into bed and took off his shoes" is often treated the same as "Mike
took off his shoes and got into bed”, even though it clearly says something
different.
• Some natural language expression are ambiguous without context:
• Ordering a la carte: “You can have pie or cake for dessert”.
—That means: PvC
•
(With the daily special): “You can have pie or cake for dessert”.
—That means: (PvC) & ~(P&C)
9
Translating “If…then …” as “…….” with the truth table TFTT.
• This can be a puzzling thing about elementary sentence logic.
• Why is the truth table for “ ” TFTT
• And if it is, then can we really correctly translate all English conditionals
(“If … then…”) as “X  Y” ?
• The simple answer is that “X  Y” represents part of the meaning of every
corresponding natural language conditional
• even though it is not usually equivalent to those conditionals.
• So it at least captures some of the meaning we are translating.
• Not satisfied? There are more detailed explanations on the web; search for
"material conditional".
• See, for example:
http://personal.bellevuecollege.edu/wpayne/material_conditional.htm
10
Logical Equivalences
•
When two compound sentences have the same truth value for every distribution of
truth values to their atomic sentences we say they are logically equivalent.
•
note that the biconditional of two such sentences is a tautology
•
Because they have the same truth conditions logical equivalents are identical in many
ways:
•
they follow (deductively) from the same sentences.
•
the same sentences follow from them.
•
they may be substituted one for another in any context in any sentence of SL
without changing the truth value or the truth conditions of the sentences in which
these substitutions are made.
—
•
i.e. Teller’s Law of Substitution of Logical Equivalents (SLE) (p. 34)
To indicate that two sentences X and Y are logically equivalent (their biconditional is a
tautology) we write: “X  Y”, for instance: ~~A  A
•
Note that strictly speaking “ “ is not sentence connective in SL; it is a device
used to say something about two SL sentences.
11
Substitution of Logical Equivalents
•
Logically equivalent expressions may be freely substituted one for another within larger
compound sentences. The resulting sentence will have the same truth conditions as the
first.
•
or, more exactly (Teller p.34)…
•
Let X and Y be logically equivalent sentences and U and V be compound
sentences exactly like each other except that
where U has X as a component, V has Y.
•
Then U and V are logically equivalent.
•
It is fairly easy to see intuitively that this is true given truth functional connectives;
it can also be explicitly proved, by mathematical induction.
•
Substitution of logical equivalents is of enormous practical value in logical
manipulations and inferencing.
12
Important Logical Equivalences
It is extremely useful to be able to easily recognize some pairs of logical equivalents and
substitute one for another, often within larger expressions. Here are some very important
ones. Study them carefully and internalize their equivalence. Use truth tables to verify them.
De Morgan’s Laws
i) ~(P  Q)  (~P & ~Q)
ii) ~ (P & Q)  (~P  ~Q)
Distributive Laws
i) P  (Q & R)  (P  Q) & (P  R)
ii) P & (Q v R)  (P & Q)  (P & R)
Implication Equivalences
(P  Q) 
(~P  Q)  ~(P & ~ Q)
 (~Q  ~P)
Biconditional Equivalences
(i) (P  Q)  [(P  Q) & (Q  P)]
(ii) (P  Q)  [(P&Q) v (~Q&~P)]
Exportation / Importation
(P & Q)  R  P  (Q  R)
Double Negation: ~(~P)  P
13
More Logical Equivalences
(So obvious it is usually not necessary to make a special effort to learn them. )
Idempotent Laws (aka Law of Redundancy)
(i) (P  P)  P
(ii) (P & P)  P
Commutative Laws
(i) P  Q  Q  P
(ii) P & Q  Q & P
Associative Laws
(i) (P  Q)  R  P  (Q  R)
(ii) (P & Q) & R  P & (Q & R)
14
 Tautologies and Contradictions
• A tautology (logical truth) is a compound sentence which is such that no
distribution of truth values to its atomic sentences, consistent with the
meaning of its truth functional connectives, will make it false.
•
For instance: Av~A,
P  P,
(AvB)v(~A&~B)
• A contradiction (logical falsehood) is a compound sentence which is such
that no distribution of truth values to its atomic sentences, consistent with the
meaning of its truth functional connectives, will make it true.
• For instance: A&~A, (AvB)&(~A&~B)
•
note that neither P  ~P nor ~P  P is a contradiction.
(look at the truth tables)
• A sentence which is neither a tautology nor a contradiction is contingent.
• i.e. the truth value of the compound is contingent upon the truth values of
the atomic sentences that appear
15
Proving Tautologies and Contradictions
• By truth table
A sentence is…
… a tautology iff there are only Ts in its truth table column.
… a contradiction iff there are only Fs in its truth table column.
… contingent iff there is at least one T and at least one F.
16
The Corresponding Conditional
• The “corresponding conditional” for an argument is the conditional whose
antecedent is a conjunction of the argument’s premises, and whose
consequent is the argument’s conclusion.
• It is easy to see (and may be proved) that an argument is valid if and only if
its corresponding conditional is a tautology.
• Just as “” is used when the biconditional of two sentences are a tautology,
“” is used to say that the conditional formed by two expressions is a
tautology.
• And similary “” is not a sentence connective in sentence logic, but a
symbol in the metalanguage.
• So “X, Y, therefore Z” is a valid argument iff (X & Y)  Z.
17
Truth-Functional Validity
• Provisional account of validity in general: it is impossible for the premises to be
true and the conclusion false.
• Initial intuition for truth-functional validity:
The meanings of the various sentence connectives will not allow a assignment
of Truth to the premises and False to the conclusion.
• Mature definition of truth-functional validity:
There is no assignment of truth values to simple sentences that, given the truthfunctional definitions of sentence connectives (as given in their truth tables)
will make the premises true and the conclusion false.
Or, alternatively: an assignment of true to the premises and false to the
conclusion is inconsistent with the definition of the truth functional
connectives
• A counterexample (or sometimes “countermodel”) is an assignment of truth
values to atomic sentences that makes the premises true and the conclusion false.
18
Truth Table Determination of Validity
• Consider these arguments…
AB
A,
B;
AvB
~A,
B
A&B
A
We can determine that there is no counterexample by examining
every possible distribution of truth values.
• We build a truth table that represents the truth values of the
premises and conclusion for every possible case.
• We then examine it to see whether there is any case where the
premises are true and the conclusion false.
19
Sentence-based Truth Tables (see ex. 1-6)
• Sentence-based truth tables have sentences (e.g., “A”, “B”, “B&C”) in the
column headings.
• Whereas sentence-variable truth tables have sentence variables (e.g., “X”,
“Y”) in the column headings.
• A sentence-based truth tables is a graphic representation of all possible
assignments of truth values to some set of relevant atomic sentences.
• They are used to calculate the truth value of various compound sentences for
each of these assignments.
• And to test for argument validity.
• Each individual row represents a possible assignment of truth values to
atomic sentences.
• Collectively the rows represent all possible assignments of truth values to
atomic sentences.
• For n atomic sentences 2n rows are needed (by the Fundamental Principle of
Counting); the pattern is a standard convention for getting them all.
• Initial “guide” columns are for atomic sentences, subsequent columns for
compound sentences.
20
Truth Table Principle
• By definition we know that the truth value of a compound sentence depends
only on the truth values of its immediate constituents.
• Some reflection suggests that as a consequence, the truth value of any
compound sentence depends only on the truth-values of its atomic sentences
• Informal proof
The truth value of any (SL) compound sentence depends only on the truth
value of its immediate constituents, by definition of the connectives.
• But those immediate constituents are themselves either atomic or
compound, by definition of “sentence in SL” (the SL syntax) —
• and when an immediate constituent is compound then its truth value in
turn depends only upon the truth value of its immediate constituents (again
by definition of the semantics of the connectives)
•
… and so on until we reach only atomic constituents, as we will, by
recursive nature of the SL syntax.
— recall the parse tree we looked at last time
Thus, given an assignment of truth values to atomic sentences, it is possible to use
a truth table to determine the truth value of any sentence in SL.
21
Truth Table Evaluation of Compound Sentence
(~A&B)  (Cv~B)
Simple
Constituents
Compound
Sentences
Row
A
B
C
~A
~B
~A&B
Cv~B
(~A&B)  (Cv~B)
1
T
T
T
F
F
F
T
T
2
T
T
F
F
F
F
F
T
3
T
F
T
F
T
F
T
T
4
T
F
F
F
T
F
T
T
5
F
T
T
T
F
T
T
T
6
F
T
F
T
F
T
F
F
7
F
F
T
T
T
F
T
T
8
F
F
F
T
T
F
T
T
No.
• For only one assignment (namely, in row 6) is the compound false; for all
others it is true. Therefore the sentence is contingent.
22
Constructing Truth Tables
• Truth tables make explicit and vivid:
• the set of all possible assignments (combinations) of truth values to any
selection of atomic sentences
• the meanings of the logical connectives, and the truth value of those
connectives for any specific assignments to atomic sentences.
• the truth conditions of compound propositions, and their truth values in
particular assignments.
• whether or not an argument is valid or invalid
• whether a sentence is a tautology, a contradiction, or contingent
• See the final slide in this slide set for a detailed method for constructing truth
tables.
(Which is useful, but makes it look a bit harder than it is).
23
Truth Table Evaluation of Validity
Simple
Constituents
Premise 1
Premise 2
Conclusion
A B C
~A
~A v B
Bv C
~ CvA
1
T T T
F
T
T
T
2
T T F
F
T
F
T
3
T F T
F
F
T
T
4
T F
F
F
F
F
T
5
F T T
T
T
T
F
6
F T F
T
T
T
T
7
F F T
T
T
T
F
8
F F
T
T
F
T
Sentences
Row
No.
F
• Four assignments will make both premises true (rows 1, 5, 6, 7);
because one of those assignments (row 7) that makes both premises
true also makes the conclusion false the argument is invalid.
24
Truth Tables test for validity.
• It is intuitively obvious that truth tables can determine, for any argument in
SL, whether or not it is truth-functionally valid.
• and that truth tables will do this (i) mechanically, ii) without any mistakes,
and (iii) without missing any cases.
—In the metatheoretical terminology we will learn later, the truth table test for
SL validity is (i)decidable, (ii) sound, and (iii) complete.
—But unfortunately it is not efficient. (… it is so not efficient…)
• The truth table method for determining validity is “combinatorially explosive”
in the sense that the number of steps grows exponentially with the number of
atomic sentences.
• Forty atomic sentences means a trillion rows. Just ten means ... ?
• Computer scientists refer to such algorithms as “intractable”, meaning that
they are not useful, even supercomputers can’t make intractable algorithms
practical.
• Moreover, the truth table technique is not natural, it does not correspond well
with how we actually reason about the world.
25
Natural Deduction Proofs
• A argument form is a structure of metalinguistic variables and
connectives such that any "substitution instance" of that form is a valid
argument
• A substitution instance of an argument form is an argument that can be
generated from that argument form by consistently substituting
sentences for metalinguistic variables.
• The form modus ponens: X  Y; X; Y
Substitution instances of modus ponens
• substituting A for X and B for Y
1) A  B
2) A
-------3) B
•
substituting (MvN) for X; (KvL) for Y
1) (MvN)  (KvL)
2) (MvN)
--------3) (KvL)
26
ND Argument Forms / Traditional Rules
• MP, Modus Ponens:
X  Y, X;
Y
• MT, Modus Tollens:
X Y, ~ Y;
~X
• HS, Hypothetical Syllogism:
X Y, YZ;
X Z
• DS, Disjunctive Syllogism:
XvY, ~ X;
Y
• CD, Constructive Dilemma:
X Y, Z W, Xv Z;
 YvW
• DD, Destructive Dilemma:
X Y, Z W, ~Yv~W;  ~Xv~Z
• Simp, Simplification:
X&Y;
X
• Conj, Conjunction:
X, Y;
X&Y
• Add, Addition:
X;
XvY
See Teller p. 69-70
27
Using ND to prove an argument valid
1. If Bill went to the market (B) and Susan went to the movies (S),
then the house is empty (E).
2. If the is house empty (E), then it is haunted (H).
3. The house is not haunted.
4. Susan went to the movies.
5. Therefore, Bill did not go to the market.
28
Using ND to prove an argument valid
[ alternatively: “derive an inference”]
1)
2)
3)
4)
(B&S)  E
E H
~H
S
5) ~E
6) ~(B&S)
7) ~B v ~S
8) ~S v ~B
9) ~~S
10) ~B
Results
Premises
Desired conclusion
/ ~B
2,3, MT
1,5, MT
6, DeMorgan’s
7, v Commutation
4, Double Negation
8,9, DS QED
Sequential Steps in the proof
Justification, lines and applied argument form
29
Truth Trees — some historical remarks
•
aka proof trees, trees, tableaux, semantic tableaux, analytic tableaux, beth tableaux
•
Roots in classical and medieval argument technique of reductio ad absurdum.
•
Current apparatus developed in the mid 20th century.
•
Classic systematic exposition in First Order Logic (1968), Raymond M. Smullyan.
•
[This is the Smullyan of the knights and knaves puzzle books.]
•
Influential textbook: Formal Logic: Its Scope and Limits (4th ed. 1990), Richard
Jeffrey.
30
Examples of Reductio style reasoning
• Truth trees are based on a particular style of reasoning, where you assume the
premises and the negation of the conclusion and demonstrate a contradiction.
• Reductio ad absurdum.
• I argue that Z follows from P, Q, R by showing that if we suppose Z false and P,
Q, R true then we get some absurdity (such as a contradiction) and so we see that
Z can’t be false (when P,Q,R are true) and so it must be true.
• There is milk in the fridge, therefore Bill caught up with Sue.
• How do I know? Well there was no milk in there this morning, and there was
no milk on the shopping list we gave Sue, and so Bill took off on his bike to
let her know we needed milk before she got to the IGA.
• Now suppose Bill hadn’t caught up with Sue, then she wouldn’t have known
we needed milk, and their would still be no milk in the fridge. But there is
milk in the fridge, as I said. So therefore Bill caught up with Sue.
31
A classic example of Reductio style reasoning
Euclid’s proof that 2 cannot be expressed as the ratio of two integers
1)
Assume the opposite: that 2 can be expressed as the ratio of two integers
2)
If 2 can be expressed as the ratio of two integers, it can be expressed as a ratio “in lowest terms”;
let the integers of this ratio be x/y.
3)
x and y are not both even
4)
(x/y) = 2
5)
So a) (x/y)2 = 2
6)
Therefore x2 is even
(because it is equal to 2 times an integer)
7)
Therefore x is even
(because only even numbers give even squares)
8)
If x is even then x=2z for some integer z.
9)
(2z)2 = 2y2
(or else x/y would not be in lowest terms;
they’d both be divisible by an integer, namely 2).
(from the assumption)
b) x 2/y2 = 2
c) x2 = 2y 2
(a little algebra, on 4) )
(putting Z for X in 5) c.)
10) So a) 4z2 = 2y2 and b) 2z2 = y2.
(more algebra, on 9) )
11) So y2 is even, and therefore y is even.
(because only even numbers give even squares)
12) So x and y are both even
(from 7) and 11) )
13) But x and y cannot both be even as x/y is in lowest terms!
(as per 3) )
14) Therefore the assumption that 2 can be expressed as the ratio of two integers is false
15) Therefore the proposition that 2 cannot be expressed as the ratio of two integers is true
16) QED
32
The basic idea behind truth trees
•
An argument is valid iff it is impossible for (the premises to be true and the conclusion false).
•
And the conclusion is false iff the negation of the conclusion is true.
•
So if an argument is valid iff it is impossible for (the premises to be true and the negation of
the conclusion true);
•
So start with a set of sentences which contains exactly
(i) all the premises, and
(ii) the negation of the conclusion.
•
Try to discover a situation in which all sentences in the set are true
•
In SL such a situation corresponds to a truth table row, or a case which makes all the
sentences true
•
If you can find such a situation, the argument is invalid, because you found a way for the
premises to be true and the conclusion false
•
You found a counterexample.
In SL, an assignment of truth values to some atomic sentences that …
•
But if your search is exhaustive, exploring all possibilities, and ends without finding a
counterexample, then the argument is valid.
33
The Basic Idea One More Time:
• As with truth tables, systematically search for a counterexample to the
argument -- an assignment that makes the premises true and the conclusion
false.
• If you find a counterexample you’ve shown the argument is NOT valid.
• If you complete your search without finding a counterexample then there
is no counterexample and the argument is valid.
• Conduct this search by exploring ways that would make the premises and the
negation of the conclusion, all true.
• This is the same as exploring ways to make the premises true and the
conclusion false, since the conclusion is false iff its negation is true.
• Abandon whole classes of assignments as soon as it is clear they won’t
provide one.
34
Truth tree rules, organized by connective/negation pairs
Read horizontally in first two columns to compare connectives with their negations
always ask yourself: what would make this sentence true? One thing? Two things?
Rules for binary
connectives
Rules for negations of binary
connectives
•
Rule v
XvY

X Y
•
•
Rule &
X&Y

X
Y
•
Rule ~&
~( X & Y)

~X ~Y
•
Rule 
XY

~X Y
•
Rule ~ 
~( X  Y)

X
~Y
•
Rule 
•
Rule ~ 
~( X  Y)

X ~X
~Y Y
XY

X ~X
Y ~Y
Rule ~v
~(X v Y)

~X
~Y
Rule for double negation
•
Rule ~~ X
~~X

X
35
Truth tree rules, organized by order of application
In general: apply ~~ first, then other nonbranching rules, then branching rules;
Rule for double negation
•
Rule ~~ X
~~X

X
Rules for other nonbranching
sentences
•
•
•
Rule &
X&Y

X
Y
Rule ~v
~(X v Y)

~X
~Y
Rule ~ 
~( X  Y)

X
~Y
Rules for branching sentences
•
Rule v
•
Rule ~&
~( X & Y)

~X ~Y
•
Rule 
XY

~X Y
•
Rule ~ 
~( X  Y)

X ~X
~Y Y
•
Rule 
XvY

X Y
XY

X ~X
Y ~Y
36
Teller’s Truth Tree Method:
Steps:
1) Starting with a tree's initial sentences, you may apply the rules in any order.
2) After applying a rule to a sentence, write a check-mark next to the sentence,
to remind yourself that you do not need to work on that sentence again.
3) After working on a sentence, look to see if any paths have closed.
Mark any closed paths with an ’X’.
4) Continue working on unchecked sentences until the tree has been
completed, which happens when either:
a) All paths have closed, or
b) No unchecked sentences are left to which you can apply a rule.
37
Teller’s Truth Tree Method:
Definitions:
“… a branch is closed when a sentence, X, and its negation, ~X, both appear
on the branch.
We mark a branch as closed by writing an ' × ’ at the bottom of the branch.
Do not write anything further on a branch once it has been marked as
closed.”
Any branch that is not closed is open.
A tree is completed (aka “finished”) when all sentences other than literals and
negations of literals have been checked; no more rules may be applied.
38
Teller’s Truth Tree Method
Determinations:
If a completed tree has all closed branches then the set of initial sentences is
inconsistent and the original argument valid.
If a completed tree has at least one open branch the set of initial sentences
consistent and the argument is invalid.
The conjunction of the atomic sentences or negations of atomic sentences
along that path is a counterexample, a truth table row, for which the premises
are true and the conclusion false.
39
Vital heuristics
• For a quicker solution, and a less “bushy” tree (i.e. much less
repetitive writing), start with lines whose diagrams don’t branch.
• Apply the rule of double negation immediately and frequently to
reveal paths with a latent X and ~X so you can close them.
• (i) may reveal a completed tree
• (ii) will reduce the number of branches you need to keep going.
40
What the tree shows, again
• We are exploring assignments of truth values, looking for one that
makes the premises true and the conclusion false.
• We do this by trying to make a set of sentences, consisting of the
premises and the negation of the conclusion, all true. If we can do this
we have found our counterexample.
• A counterexample is represented by an open path through a finished
tree: that is an assignment of truth values that will make the sentences
in the “initial set” all true; i.e. make the premises of the argument true
and the conclusion false.
• If the tree finishes with all branches are closed, then there is no way to
assign values making all sentences in the set true, and therefore no way
to assign values making the premises true and the conclusion false …
and therefore the argument is valid.
41
Is Teller’s Method an Algorithm?
• Teller does not present the tree method as an algorithm as he still asks you to make a
choice as to which which rule to apply first, or what amounts to the same thing,
which unchecked compound sentence to apply a rule to
•
So in Teller's version of the tree method "which rule do I apply first?" is a little like
asking "which piece do I move first" in chess. The rules of chess tell you how you
can move pieces, as well as what it is to win a game, but they don't tell you what
pieces to move or in what sequence in order to win a game.
• Teller does give advice on strategy: double negation right away, nonbranching
before branching. But these don’t completely constrain you choices.
• For a slight more step-by-step version see Suber:
http://www.earlham.edu/~peters/courses/log/treeprop.htm
• And for an even more mechanical version see the next side….
42
An Algorithm for the Tree Method (modifying Teller’s “steps”)
The Tree Method, as an algorithm of steps, some conditional, which are performed over and over until one of the two exit
conditions are reached. Here goes...
Preparation: Form the initial set of sentences by adding to the premises the negation of the conclusion.
Method…
1a)
If ~~ applies to an uncheck(mark)ed sentence, apply it, check(mark) the sentence and go to 2).
1b)
If a nonbranching rule applies to an unchecked sentence, apply it, check the sentence and go to 2).
1c)
If a branching rule applies to an unchecked sentence, apply it, check the sentence, and go to 2).
2)
Has the path you just added a sentence to “closed”? If so, mark it closed, with an X.
3)
Have all paths closed? If yes, then stop. The argument is valid.
At this point there may be unchecked sentences, that is ok as you have shown that the ones you have checked cannot
all be true, and so the set is inconsistent, and so the argument valid.
4)
Are all compound or doubly neg sentences checked? If so, then stop, the argument is invalid
You will only be stopping here if there are no unchecked sentences and at least one open path, which means that the
sentences are consistent (and all be made simultaneously true), which means the argument is invalid and each open
path represents a counterexample, a truth table row which makes all sentences in the initial set true. (If there were no
open paths you will have stopped at 3), above.)
5)
Return to 1a) and execute the steps 1a) through 5) again. (lather, rinse, repeat)
Notes
*) Steps 1a) through 1c) can be collapsed into simply “If a rule applies, apply it, check the sentence; then go to 2), allowing you apply the rules in any order. However
the practical consequences of not doing them in the order given are rather unpleasant.
*) This procedure should look a little more mechanical than Teller or Suber. However it still doesn’t tell you exactly how to find an unchecked sentence (intuitively:
look) and exactly which of the rules that apply to it should be applied, to it (intuitively: any). But if those intuitive steps are articulated at the purely mechanical level
the method will look far more complicated than it is.
43
Constructing a Truth Table to Determine Validity
1)
Make a column for each atomic sentence in the argument, with a double vertical line after the last
column. Label columns at top with the simple sentences represented.
2)
Starting after the rightmost atomic sentence column (the double line) and moving left to right make a
column for every compound “predecessor” (component) sentence in the premises and conclusion.
Order from simpler to more complex so the predecessors of any compound sentence are found
somewhere to the left of the column for that sentnece. Do not repeat columns for predecessors used
more than once. Label columns; make another double line after the rightmost column.
3)
Make a column for each premise and then for the conclusion. Label each with the sentence
represented, and then, above that, with “Premise no. #)” or “Conclusion”.
4)
Make 2n rows under these columns, where n is the number of atomic sentences.
5)
To represent all possible assignments to atomic sentences place truth values in the cells under the
simple sentences this way: in the right-most atomic sentence column alternate single(20) T’s and F’s;
in the column 2nd from the right alternate groups of two (21) Ts and two Fs; in the third column from
the right alternative groups of 4 (22) T’s and 4 Fs, in the fourth column alternate groups of 8 (23) T’s
and 4 Fs and so on until you finish the leftmost column, which should consist of one group 2 n/2 (or 2n1) Ts followed by 2n/2 Fs.
6)
Now use the established truth table definitions of the connectives to calculate the values for every
remaining compound sentence column (predecessors, premises, and conclusions) moving left to right
and exploiting previous calculations of immediate predecessors whenever you need to. Each cell
represents the truth value of its compound sentence (column) given an assignment to its simple
sentences (row).
7)
Inspect the truth table for a row that represents all the premises of the argument as true and the
conclusion as false. If there is one then the argument is invalid, if not it is valid.
44