First-Order Predicate Logic Flashcards
What is the language of first-order logic?
What are the primitive symbols?
(1) An infinite sequence of individual variables: x0, x1, x2, . . . , xn, …
(2) For each natural number n , a set of n -ary function symbols: f0, f1, f2, . . .
0-ary function symbols, which take no argument, are called individual constants.
(3) For each natural number n , a set of n -ary predicate symbols (at least one of which must be non-empty): P0, P1, P2, …
(4) A first-order language with equality also contains the binary predicate symbol = .
(5) The usual propositional connectives: ∧ , ∨ , ⊃ , and ∼ .
(6) The universal and existential quantifiers, written as ∀ and ∃.
(7) Finally, parentheses: (, ).
What are logical systems made up of?
Propositional Logic:
(1) Alphabet
(2) wff
(3) Sematic: TT, entailment
(4) Proof systems
First order logic is more complex but has the same structure
Both are sound and complete
What are logical symbols?
Variables, connectives, quantifiers, and equility
What are extra-logical symbols?
Functions, predicate symbols.
Meaning extra-logic symbols determined by interpretation
Compare first order logic and propositional logic
Same structure
Difference between terms and formulas:
a) Terms are like names, consisting of variables and function symbols.
In the standard interpretation (see below) they stand for numbers.
b) Formulas are like statements. They consist of predicate symbols, connectives, quantifiers.
They can be true or false
Recursive definition for terms:
- A single occurrence of a variable is a term.
- If f is an n -ary function symbol, and t1, . . . ,tn are terms, then the string f(t1, . . . ,tn) is
a term. The ti are called the arguments of the term.
This includes the particular case where n = 0 ; a constant is also a term. - Nothing else is a term.
We will often use infix notation for binary (i. e., 2-ary) function symbols, and write t1f t2
instead of f(t1,t2); for example, we will write x1 + x2 for +(x1, x2) .
Recursive definition for formulas:
What is an atomic formula?
When there is an 0-ary relationship. Logical constant or expression of the form (t1, …, tn)
Ex. wff in FOA t=u and A in PL
What is the universal and existential formulas?
Universal Formula: (∀x: A)
Existential Formula: (∃x: A)
How can the quantifiers be defined in terms of each other?
Homework 03
Give two structures and interpretations of the formulas such that (a) is false and (b) is true:
∀x : (x = 0)
Homework 03
If σ is an interpretation of first-order arithmetic in hIN, 1; s, +, ×i, i. e., the structure whose domain are the natural numbers, and where 0^σ = 1, S^σ = s (successor), +^σ = +, and ×^σ = ×, what are (SS0 + SSS0 = SSSSS0)^σ and (∀x : ∼(Sx = 0))^σ?
How do we have to change the interpretation (in the same structure or a different one) so that the formulas become true?
Both are false. The formula SS0 + SSS0 = SSSSS0 is interpreted as “3 + 4 = 6”, which is clearly false. The formula ∀x : ∼(Sx = 0) is false because, according to (F4) of the Basic Semantic Defintion (p. 5 of Handout 3), the x can be interpreted as any element from the universe of dicsourse, i. e., N; when x σ = 0, ∼(Sx = 0) gets interpreted as successor (0) 6= 1, i. e., 1 6= 1, which is false.
Both are true under the standard interpretation.
Homework 03
Say in English what the conclusion of the deduction below means.
Say which inference rules appear to have been used in the following Natural Deduction proof.
If some inference rule was used incorrectly, explain why.
‘If zero is equal to zero, then every number is equal to zero’.
The rules used are the following (top to bottom): ∀-Intro, ⊃-Intro, ∀-Intro, and ∀-Elim.
The first use of the ∀-Introduction is illegal. Here the eigenvariable a is x and it occurs free in x = 0, which, at that point, is an uncancelled hypothesis in the derivation
