2. Propositional Logic Flashcards
Grammatical strings of symbols (i.e., ones that “make sense”) are called _______.
well-formed formulas, or “formulas” or “wffs” for short
Grammatical strings of symbols (i.e., ones that “make sense”) are called well-formed formulas, or “formulas” or “wffs” for short. We define these by ________.
first carefully defining exactly which symbols are allowed to occur in wffs (the “primitive vocabulary”), and second, carefully defining exactly which strings of these symbols count as wffs
Primitive vocabulary: …
· Connectives: →, ∼
· Sentence letters: P, Q, R …, with or without numerical subscripts
· Parentheses: ( , )
Definition of wff (well-formed formulas):
i) Every sentence letter is a PL-wff
ii) If φ and ψ are PL-wffs then (φ→ψ) and ∼φ are also PL-wffs
iii) Only strings that can be shown to be PL-wffs using i) and ii) are PL-wffs
Definition of wff (well-formed formulas):
i) Every sentence letter is a PL-wff
ii) If φ and ψ are PL-wffs then (φ→ψ) and ∼φ are also PL-wffs
iii) Only strings that can be shown to be PL-wffs using i) and ii) are PL-wffs
Here is how the denition works…
Its core is clauses i) and ii) (they’re sometimes called the formation rules). Clause i) says that if you write down a sentence letter on its own, that counts as a wff. So, for example, the sentence letter P, all by itself, is a wff. (So is Q, so is P_147_, and so on. Sentence letters are often called “atomic” wffs, because they’re not made up of smaller wffs.) Next, clause ii) tells us how to build complex wffs from smaller wffs. It tells us that we can do this in two ways. First, it says that if we already have a wff, then we can put a ∼ in front of it to get another wff. (The resulting wff is often called a “negation”.) For example, since P is a wff (we just used clause i) to establish this), then ∼P is also a wff. Second, clause ii) says that if we already have two wffs, then we can put an → between them, enclose the whole thing in parentheses, and we get another wff. (The resulting wff is often called a “conditional”, whose “antecedent” is the wff before the → and whose “consequent” is the wff after the →.) For example, since we know that Q is a wff (clause i)), and that ∼P is a wff (we just showed this a moment ago), we know that (Q→∼P) is also a wff. This process can continue. For example, we could put an → between the wff we just constructed and R (which we know to be a wff from clause i)) to construct another wff:
((Q→∼P)→R). By iterating this procedure, we can demonstrate the wffhood of arbitrarily complex strings.
Some books use __ instead of →, or __ instead of ∼. Other common symbols include __ or __ for conjunction, __ for disjunction, and __ for the biconditional.
⊃; ¬; &; ·; |; ≡
Definition of wff (well-formed formulas):
i) Every sentence letter is a PL-wff
ii) If φ and ψ are PL-wffs then (φ→ψ) and ∼φ are also PL-wffs
iii) Only strings that can be shown to be PL-wffs using i) and ii) are PL-wffs
Why the greek letters in clause ii)?
It wouldn’t be right to phrase it, for example, in the following way: “if P and Q are wffs, then ∼P and (P→Q) are also wffs”. That would be too narrow, for it would apply only in the case of the sentence letters P and Q. It wouldn’t apply to any other sentence letters (it wouldn’t tell us that ∼R is a wff, for example), nor would it allow us to construct negations and conditionals from complex wffs (it wouldn’t tell us that (P→∼Q) is a wff). We want to say that for any wff (not just P), if you put a ∼ in front of it you get another wff; and for any two wffs (not just P and Q), if you put an → between them (and enclose the result in parentheses) you get another wff. That’s why we use the metalinguistic variables “φ” and “ψ”. The practice of using variables to express generality is familiar; we can say, for example, “for any integer n, if n is even, then n + 2 is even as well”. Just as “n” here is a variable for numbers, metalinguistic variables are variables for linguistic items. (We call them metalinguistic because they are variables we use in our metalanguage, in order to talk generally about the object language, which is in this case the formal language of propositional logic.)
Definition of wff (well-formed formulas):
i) Every sentence letter is a PL-wff
ii) If φ and ψ are PL-wffs then (φ→ψ) and ∼φ are also PL-wffs
iii) Only strings that can be shown to be PL-wffs using i) and ii) are PL-wffs
What’s the point of clause iii)?
Clauses i) and ii) provide only sufficient conditions for being a wff, and therefore do not on their own exclude nonsense combinations of primitive vocabulary like P∼Q∼R, or even strings like P ⊕ Q that include disallowed symbols. Clause iii) rules these strings out, since there is no way to build up either of these strings from clauses i) and ii), in the way that we built up the wff (∼P→(P→Q)).
Definition of wff (well-formed formulas):
i) Every sentence letter is a PL-wff
ii) If φ and ψ are PL-wffs then (φ→ψ) and ∼φ are also PL-wffs
iii) Only strings that can be shown to be PL-wffs using i) and ii) are PL-wffs
Notice an interesting feature of this definition: the very expression we are trying to define, ‘wff’, appears on the right hand side of clause ii) of the definition. In a sense, we are using the expression ‘wff’ in its own definition. But this “circularity” is benign, because ______.
the definition is recursive
A recursive (or “inductive”) definition of a concept F contains a circular-seeming clause, often called the _____ clause, which specifies that _____. But a recursive definition also contains a “base clause,” which specifies noncircularly that _____. Even though the inductive clause rests the status of certain objects as being Fs on whether certain other objects are Fs (whose status as Fs might in turn depend on the status of still other objects…), this eventually traces back to the base clause, which secures F-hood all on its own. Thus, recursive definitions are anchored by their ______; that’s what distinguishes them from viciously circular definitions.
“inductive”;
if such-and-such objects are F, then so-and-so objects are also F;
certain objects are F;
base clauses
Definition of wff (well-formed formulas):
i) Every sentence letter is a PL-wff
ii) If φ and ψ are PL-wffs then (φ→ψ) and ∼φ are also PL-wffs
iii) Only strings that can be shown to be PL-wffs using i) and ii) are PL-wffs
In the definition of wffs, clause i) is the ____, and clause ii) is the ____ clause.
base;
inductive;
The wffhood of the string of symbols ((P→Q)→∼R), for example, rests on the wffhood of (P→Q) and of ∼R by clause ii); and the wffhood of these, in turn, rests on the wffhood of P, Q and R, again by clause ii). But the wffhood of P, Q, and R doesn’t rest on the wffhood of anything else; clause i) species directly that all sentence letters are wffs.
Definitions of ∧, ∨, and ↔: …
- “φ∧ψ” is short for “∼(φ→∼ψ)”
- “φ∨ψ” is short for “∼φ→ψ”
- “φ↔ψ” is short for “(φ→ψ) ∧ (ψ→φ)” (which is in turn short for “∼((φ→ψ) → ∼(ψ→φ))”)
So, whenever we subsequently write down an expression that includes one of the defined connectives, we can regard it as being short for an expression that includes only the official connectives, ∼ and →.
____ is short for “∼(φ∧∼ψ)”
“φ→ψ”
____ is short for “∼(∼φ∧∼ψ)”
“φ∨ψ”
____ is short for “(φ→ψ)∧(ψ→φ)”
“φ↔ψ”
