Lecture #5. Sept. 23
Here is the Basic Truth Table again:
1
xy
F¬ (x)
F∨(x,y)
F∧(x,y)
F→(x,y)
F≡(x,y)
ff
t
f
f
t
t
ft
t
t
f
t
f
tf
f
t
f
f
f
tt
f
t
t
t
t
I repeated above the table that we saw on Friday (Sept. 18) to dis- cuss a bit F→(x, y).
The most “sane” entry in this column is arguably, the one for input (t,f).
Since this function is describing the truth-value of implications, and the x input is the hypothesis and the y input is the conclusion,
Then having F→(t, f) = f can be interpreted as saying that the implication cannot be true if we started with a true hypothesis and ended up with a false conclusion.
We can easily agree with this!
. . . Since our intuition accepts that “→” preserves truth from left to
right.
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
2 BUT STILL: There are unsettling issues about the truth table for “→”,
this table known as the semantics of Classical or Material Implication. For example:
• “If it is cloudy today, then my name is George”
My name IS “George” so the above is true if it is NOT cloudy today (by row two in the
table).
But the hypothesis is irrelevant to the conclusion, which does not FOLLOW, intu-
itively speaking, from the hypothesis.
• “If it is cloudy today, then my name is George”
My name IS “George”. Suppose also that it IS cloudy today! Then the above is true (by row four in the table).
The same comment as above, about the irrelevance between hypothesis and conclusion applies!
What do we do?
Answer. Nothing. This semantics (“this”, not “these”; singular) is
what 99% of the literature uses. If it helps, think of f as 0 and t as 1.
Now if you think of “→” as “≤”(we will have a strong reason to do so; wait for when we introduce our Axioms) then the column under F→ is all right!
It confirms that F→(x, y) has the semantics of “x ≤ y”, which inci- dentally is totally consistent with the semantics of ≡ as “x = y”:
That is, the view that “≡” says “→ and ←”, coincides with the view in the table that it says “=” —in other words, “≤ and ≥”.
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
3
So far, states give meaning (values) to atomic formulas only. Let us extend this meaning-giving to any wff.
0.0.1 Definition. (The value of a wff in some state, v) We extend any state v to be mean- ingful not only with atomic arguments but also with any wff arguments.
We will call such an extension of v by the same letter, but will “cap” it with a “hat”, v, since it is a different function!
What IS an “extension” of v?
It is a function v that on the arguments that v is defined so is v and gives the same output!
But v is defined on more inputs: On all wff found in WFF.
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
You see the significance of the uniqueness of i.p.!!!
v(p) = v(p) v(⊤) = t v(⊥) = f
v(¬A) = F v(A) ¬
v(A∧B)=F v(A),v(B) ∧
v(A∨B)=F v(A),v(B) ∨
v(A → B) = F v(A), v(B) →
v(A≡B)=F v(A),v(B) ≡
4
The definition of v is inductive:
The first three lines below simply say that v agrees with v on the
inputs that the latter is defined on.
The remaining lines trace along the inductive definition of wff, and give the value of a wff using the values —via “recursive calls”— of its UNIQUE i.p.
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
Truth tables are more convenient to understand, AND misunderstand!
For example the 6-th equality in the previous definition can also be depicted as:
5
AB
A∨B
ff
f
ft
t
tf
t
tt
t
At a glance the table says that to compute the value of A ∨ B you just utilise the values of the i.p. A and B as indicated.
The misunderstanding you MUST avoid is this: The two left columns are NOT values you assign to A and B.
You can assign values ONLY to ATOMIC formulas!
What these two columns DO say is that the formulas A and B
have each two possible values.
That is 4 pairs of values, as displayed!
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
We say a variable p occurs in a formula meaning the obvious: It is,
as a string, a substring —a part— of the formula.
0.0.2 Theorem. Given a formula A. Suppose that two states, v and s agree on all the variables of A. Then v(A) = s(A).
Proof. We do induction of the formula A:
1.CasewhereAisatomic. Wellifitis⊤or⊥thenv(A)=s(A)istrue. IfAisp,then
v(A) = s(A) by hypothesis of the theorem.
2. Case where A is (¬B). The value of A —whether under v or under s— is determined by a recursive call to v(B) and s(B). Seeing that all the variables of B are in A, the I.H. yields v(B) = s(B) and hence v(A) = s(A).
3. Case where A is (B ◦ C). The value of A —whether under v or under s— is determined by recursive calls to v(B) and v(C) on one hand and s(B) and s(C) on the other.
Seeing that all the variables of B and C are in A, the I.H. yields v(B) = s(B) and v(C) = s(C) (∗)
Hence no matter which one of the ∧,∨,→,≡ the symbol ◦ stands for, it operating on v(B) and v(C) or on s(B) and s(C) will yield the same result by (∗).
6
That is, v(A) = s(A).
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
7
0.0.3 Remark. (Finite “appropriate” States) A state v is by definition an infinite
table.
By the above theorem, the value of any wff A in a state v is determined only by the values of v ON THE VARIABLES OF A, since any other state that agrees with v on said variables gives the same answer.
Thus, going forward we will be utilising finite appropriate states to compute the truth values of any wff.
0.0.4 Definition. (Tautologies and other things. . . )
1. A Tautology is a formula A which is true in all states. That is, for all v, we have v(A) = t.
We write “|=taut A” for “A is a tautology”.
2. A contradiction is a formula A such that, for all v, we have v(¬A) = t.
Clearly, for all v, we have v(A) = f.
3. A is satisfiable iff for some v, we have v(A) = t.
We say that v satisfies A.
Boolean logic for the user helps to discover tautologies.
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
8 We saw that WFF denotes the set of all (well-formed) formulas.
Capital Greek letters that are different from any Latin capital let- ter are used to denote arbitrary sets of formulas. Such letters are Γ, ∆, Φ, Ψ, Ω, Π, Σ. As always, in the rare circumstance you run out of
such letters you may use primes and/or (natural number) subscripts.
0.0.5 Definition. (Tautological implication —the binary |=taut)
1. Let Γ be a set of wff. We say that v satisfies Γ iff v satisfies every for-
mula in Γ.
2. We say that Γ tautologically implies A —and we write this as Γ |=taut A— iff
every state v that satisfies Γ also satisfies A.
The configuration
Γ |=taut A (1) is called a tautological implication claim.
We call Γ the set of hypotheses or premises of the tautological implication, while A is the
conclusion.
IMPORTANT! The task to verify (1) entails work on our part ONLY if we found a v that satisfies Γ.
If there is NO such v then the claim (1) is valid! YOU cannot contradict
its validity for you will need a v that satisfies Γ but NOT A.
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
0.0.6 Example.
(1) If |=taut A, then for any Σ, we have Σ |=taut A.
The converse is not valid:
(2) We have p |=taut p ∨ q. Indeed, for any v such that v(p) = t we compute v(p ∨ q) = t from the truth table for ∨.
Yet,p∨qisNOTatautology. Justtakev(p)=v(q)=f
Note also the obvious: A |=taut A ∨ B, for any wff A and B. Again use the truth table of
p.5.
In view of 0.0.2 we can check all of satisfiability, tautology status, and tautological implication with finite Γ using a finite truth table.
9
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
Examples. Example 1. ⊥ |=taut A.
Because no v satisfies the lhs of “|=taut” so according to Definition I rest my case.
Example2. LetusbuildatruthtableforA→B∨Aandseewhatweget. I wrote sloppily, according to our priorities agreement.
I mean (A → (B ∨ A)).
We align our part-work under the glue since it is the glue that causes the output.
Here → is the last (applied) glue. Under it we write the final results for this formula.
Since A and B are not necessarily atomic, the values under A and B in the table below are possible values NOT assigned values! So (A → (B ∨ A)) is a
tautology.
Here is another tautology. I will verify this by a shortcut method, WITHOUT building a truth table.
I will show
|=taut ((A → B) → A) → A (1) Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
10
A
B
A
→
B
∨
A
f f t t
f t f t
t t t t
f t t t
Example 3.
I will do so by arguing that it is IMPOSSIBLE TO MAKE (1) FALSE.
• If(1)isfalsethenAisfalseand(A→B)→Aistrue.
• Given the two blue statements above, it must be that A → B is false. IMPOS- SIBLE, since A is false!
11
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
where A and B are formulas and p is any variable means
• As an Action: “Find and replace by B ALL occurrences of p in A”.
• As a Result: The STRING resulting from the action described in the previous bullet.
1. In the METAtheory of Logic where we use the exprssion “[p := B]” we Agree to Give it The Highest priority: Thus, A ∧ B[q := C]
means A ∧ B[q := C] and ¬A[p := B] means ¬A[p := B]
2. Clearly if p does NOT occur in A, then the “action” found noth- ing to replace, so the resulting string —according to (1)— in this case is just A; NO CHANGE.
Lecture #6. Sept. 25.
0.0.7 Definition. (Substitution in Formulas)
The METAnotation
A[p := B] (1)
12
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
13
We observe the following, according to the inductive definition of formulas.
With reference to (1) of the previous page, say
1. A is atomic. In particular, using “=” for equality of strings,
• Aisp. ThenA[p:=B]=B
• A is q —where by q we denote a variable other than the one p stands for. Then A[p := B] = A —no change.
• Ais⊥or⊤. ThenA[p:=B]=A—nochange.
2. A is (¬C). Then all occurrences of p are in C. All Action happens with C.
Thus A[p := B] is effected by doing first S = C[p := B]. Above I named the result S for convenience.
Now A[p := B] is (¬S).
3. Ais(C◦D). ThenalloccurrencesofpareinC orD.
All Action happens with C and also D. Thus A[p := B] is effected by doing
(a) S=C[p:=B]
(b) T =D[p:=B]
Where I named the two above results S and T for convenience.
(c) To conclude, use concatenation —in the order indicated below— to obtain the
string
(S ◦ T )
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
14
0.0.8 Proposition. For every wff A and wff B and any variable p, A[p := B] is*a wff. Proof. Induction on A using the observations 1.–3. of the previous page.
Cases for A:
• A is Atomic. So we are under Case 1 of the previous page. Regardless of subcase (we get as the result of substitution) A or B. This result is a wff.
• CasewhereAis(¬C). TheI.H.oni.p.appliestoC,soS=C[p:=B]isaformula —where we used a new name S for convenience.
But A[p := B] is (¬S). Done.
• Case where A is (C ◦ D). The I.H. on i.p. applies to C and D, so S = C[p := B] and T = D[p := B] are formulas —using the notation of the previous page.
ButA[p:=B]is(S◦T). Done.
*We are purposely sloppy with jargon here —like everybody else in the literature: “IS” means “results into”. Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
15 We are poised to begin describing the proof system of Boolean logic.
To this end we will need the notation that is called formula schemata or formula schemas (if you consider “schema” an English word).
0.0.9 Definition. (Schema, Schemata) Add to the alphabet V the following symbols: 1. “[”, “]”, and “:=”
2. All NAMES of formulas: A,B,C,…, with or without primes and/or subscripts.
3. All metasymbols for variables: p, q, r, with or without primes and/or sub- scripts.
Then a formula schema is a STRING over the augmented alphabet, which becomes a wff whenever all metasymbols of types 2 and 3 above, which occur in the string, are replaced by wff and actual variables respectively.
A formula that we obtain by the process described in the paragraph above
is called an Instance of the Schema.
Three examples of schemata.
(1) A: This Schema stands for a wff! So trivially, if I plug into A an actual wff, I
get that wff as an instance!
(2) (A ≡ B): Well, whatever formulas I substitute into A and B (metavariables) I get a wff by
the inductive definition of wff.
(3) A[p := B]: We know that if I substitute A and B by formulas and p by a Boolean variable
I get a wff (0.0.8).
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
16
Next stop is Proofs!
In proofs we use Axioms and Rules (of Inference). It is the habit in the literature to write Rules as fractions:
P1,P2,…,Pn Q
where allof P1,…,Pn,Q are schemata.
(R)
An Instance of the Rule is a common instance of all P1,…,Pn,Q, that is, a metavariable A is replaced by the same wff throughout, and a metavariable p is also replaced by the same Boolean variable throughout.
We call the schema (if one, or schemata if many) on the numerator the premise(s) but also hypothes(is/es).
The single schema in the denominator we call the conclusion (also “result”).
I note that the fraction (R) above, the RULE, is meant as an input / output
device.
For every instance of (R)
all the Pi and the Q become wff P1′,…,Pn′,Q′ theRule,withinputP1′,…,Pn′ yieldsoutput(result,conclusion)Q′.
We also say that Q′ is the result of the application of (R) to P1′,…,Pn′. Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.
We say
Rule2
A, A ≡ B B
There are NO restrictions in the use of “Leibniz”.
In particular, it is NOT required that p actually occurs in C. If it does not, then the denominator is C ≡ C.
17
0.0.10 Definition. (Rules of Inference of OUR version of Boolean Logic) There are just two:
Rule1
A≡B
C[p := A] ≡ C[p := B]
(Leibniz)
(Eqn)
Lecture Notes (outline) for MATH 1090 A (Fall 2020) © George Tourlakis, 2020.