This little file is meant to ensure that you know enough to do Assignment 1 properly. It's also meant to save some class time. We defined states in class. At first, we said that their domains are the set of all atomic Boolean wffs, i.e., the infinite set consisting of the Boolean constants "top" and "bottom" and the (infinitely many) Boolean variables. Then we indicated how one extends, inductively, any given state v to a function defined on the entire set WFF. Time expired then, but next I would have noted, as GT does, that only finitely many Bool. variables appear in any given wff A, and would have said that a "finite state appropriate to A" is just a function whose codomain is the set {f, t} and whose domain is the set of variables appearing in A together with top and bottom, and whose value at top is t and whose value at bottom is f. (And of course one extends such a "finite state" to a function with a bigger domain, namely, the set of all wffs which contain no Boolean variables other than the ones with appear in A. (That domain includes A! :-) ) The truth table for A with which everyone should be familiar from a previous course (MATH 1019 or MATH 1190, e.g.) then has 2^n (2 to the power n) lines, where n is the number of Boolean variables appearing in A. I gave an example in class. Another example is the upper diagram on page 33 of our text, except that I would write this wff as (p --> (q --> p)), i.e., with brackets. When you give truth tables on this assignment, you may use the symbols f, t without making them bold and without underlining them. Just lower-case, as above, is ok. Upper-case (as in the text by Rosen) is not recommended, for at least two reasons: One, T looks dangerously like the symbol for "top" ("verum") in our alphabet V. Two, we said in the first class that upper-case Latin letters from A through Z would stand for wffs, and if we now use F, T for truth values then we are saying that truth values are wffs, which is ridiculous (the former are semantic creatures; the latter are syntactic; "truth values" are not gotten inductively (as all wffs are!) from atomic wffs, as discussed in our first Tuesday meeting). Note again, also, that for us lexicographic order is f first, then t. (For Rosen it is the reverse.) Thus the values of p, q, r in a truth table featuring only those variables are f f f, t t t, t f f in lines 1, 8, 5, respectively. The grader should not have to spend oceans of time deciding whether a truth table is correctly filled out, if the person who wrote it down did not have the basic consideration for his reader to list the n-tuples of fs and ts lexicographically; I will instruct the grader to grade such tables as harshly as he wants. We gave an official definition in class of "tautology". On test or exam, you must give that definition if asked to define "tautology". But for this assignment you may use this fact (without even mentioning that you are using it): A is a tautology iff it has value t on every line of its truth table. (I.e., iff its value under every finite state appropriate to it is t. This is made visible by there being 2^n ts in the column under the main connective of A (if A is not atomic). We began defining terminology like "satisfies" and "satisfiable" and "tautologically implies" at the end of our time Tuesday, and ran out of time. Here are some definitions, which I'll give here to save time next week (and also so that you can do this assignment). Given two or more wffs A, B, ..., their "joint truth table" has 2^n lines, where n is the number of variables which appear in one or more of the wffs. E.g., if A is p /\ (q == p) and B is (q --> r) \/ q (I left off the outer overcoat in each of A and B here), then the joint truth table of A and B looks like this: p q r A B There should be a vertical line to separate the r column from the part f f f of the table to the right of it, and horizontal lines separating rows from .............. one another, as in the top table on p. 33 of our text. Note that in the t t t joint truth table we regard both of A and B as involving all three variables p, q, r, or at least we treat them as if they do (even though they don't). Following our text, we will use certain upper-case Greek letters to denote sets of wffs: Our favourites (with pronunciations in brackets) will be Γ ("gamma"), Δ ("delta"), Σ ("sigma"), Θ ("theta"), listed in that order on line 4 of page 34 of GT. Often Γ is enough. Here are some official definitions (compare these with 1.3.11 on page 34 -- the term being defined is in bold face below): Let A be a wff, and let Γ be a set of wffs. (0) A state v "satisfies Γ" iff for all wffs B in Γ, v(B) = t. (There is no special notation for this, just the English.) Γ "is satisfiable" iff some state satisfies Γ. ("Some" in mathematics always means "at least one".) Γ "is unsatisfiable" iff it is not satisfiable, i.e., iff every state v fails to satisfy at least one wff in Γ. (1) A is satisfiable iff there is some state v such that v(A) = t. And one expresses this last equation in mathglish by saying that "v satisfies A". (1') A is unsatisfiable, or a contradiction, iff for ALL states v, v(A) = f. (2) Γ tautologically implies A iff for each state v satisfying Γ, v satisfies A. We then write Γ |= A, or (my preference) Γ |= A. taut Unravelling this from earlier definitions, one easily sees that Γ |= A iff EVERY state v which satisfies all of the wffs in Γ also satisfies A. I may get tired of all the verbiage and just say "Γ entails A" in this case. [end of that list of definitions/terminology] Convince yourself of these facts (all are easy): Let A be any wff. Then: ___ |= A iff { | } |= A. (A is a tautology iff the set {top} entails A.) Given the question of whether a set Γ of wffs does or does not tautologically imply a given wff D, we call Γ the set of hypotheses, or premises, and D the conclusion, and we ask whether the hypotheses entail the conclusion. I suggest using notation I don't think is in GT, namely: Let's write v |= A, to mean that the state v satisfies A. Then this double turnstile is pronounced "satisfies", whereas in Γ |= E, it is pronounced "tautologically implies", or "entails". Notice also that (as I said in class), if a double turnstile appears in a phrase like |= C, i.e., with nothing to the left of it, then it is pronounced "is a tautology", and the wff to the right of it is pronounced first ("C is a tautology"). Finally, note (right after 1.3.11 in our text) that in the case of a finite set Γ, we may at times drop the set braces when the set is given by listing its elements, even though it is not proper to do so (we pretend that the set braces are still there). In your answers to problems 1-4 in Assignment 1, you must write enough correct, clear English to convince the grader that you KNOW why your answer is correct. (This can include circling appropriate columns or parts of a truth table, with accompanying English.) OK, enough! |