September 7, 2004

Section 1.4

• Predicate wffs , predicates, quantifiers, logical connectives & grouping symbols.
• valid arguments rely solely on the internal structure of the argument not on the truth or falsity of the conclusion in any particular interpretation.,
• No equivalent of the truth table exists to easily prove validity.
• We use a formal logic system called predicate logic.
• The equivalence rules and inference rules of propositional logic are still part of predicate logic.
• There are arguments with predicate wffs that are not tautologies but are still valid because of their structure and the meaning of the universal and existential quantifiers.
• Approach to proving arguments is:
• strip off quantifiers
• manipulate unquantified wffs
• put quantifiers back
• Four new rules in table 1.17 – restrictions in column 3 are essential - p.47
• NOTE: P(x) does not imply that P is a unary predicate with x as its only variable. P(x) does imply that x is one of the variables in the predicate which might be (there exists a y) such that (for all z) Q(x,y,z) – bottom of page 46.
• Universal instantiation: p.47
• substitution must not be within the scope of another quantifier
• Existential instantiation: p.48
• requires new constant symbols
• NOTE: need to do existential instantiation before universal instantiation
• Universal generalization: p.49
• variable generalized must not be a free variable in any hypothesis
• ei can’t have been used anywhere in the proof
• Existential generalization: p 50
• variable generalized can’t have already appeared in the wff to which

the existential generalization is applied.

• NOTE: instantiation rules strip off a quantifier from the front (left) of an entire wff that is in the scope of that quantifier (i.e. 2 things to be careful of)
• Typo on page 52 – should refer to Practice 24 and Example 31.

Reminders:

• A free variable is one that occurs somewhere in a wff that is not part of a quantifier and is not within the scope of a quantifier involving that variable. p. 36
• The truth value of a propositional wff depends on the truth values assigned to the statement letters. p. 39
• The truth value of a predicate wff depends on the interpretation.
• There are an infinite number of possible interpretations for a predicate wff.
• There are only 2ⁿ possible rows in the truth table for a propositional wff with n statement letters.
• A tautology is a propositional wff that is true for all rows of the truth table.
• The analogue to tautology for predicate wffs is validity.
• A predicate wff is valid if it is true in all possible interpretations.
• The algorithm to decide whether a propositional wff is a tautology requires examination of all the possible truth assignments. p. 40
• NO algorithm to decide validity exists – but if we can find a single interpretation in which the wff has the truth value false or has no truth value at all, then the wff is not valid.