121 Week 5 - Predicate Logic Flashcards
Why is predicate logic needed
It lets us describe propositions in a more detailed and complex way than propositional logic can. It accounts for parts of and links between parts of propositions and quantifiers.
What are the 2 parts of predicate logic
Syntax and semantics
Syntax
notations for concepts and operators used to create formulae
Semantics
The meanings behind the formulas
Predicates
A verb describing a property or relation of a term
Terms
Subjects expressed through nouns or pronouns
Atomic formula
Smallest element of predicate logic
Consists of 1 predicate and 1 or more terms
Predicates for properties
Predicates can be used to describe the property of a subject - its features/attributes
E.g., the sky is blue or Tom’s car is blue
Predicates for relations
Predicates can be used to describe the relationship between terms - objects and a subjects.
E.g., Jay is the father of Kay or Jay and Kay are neighbours.
Constant terms
Specific objects e.g., Alice or Bob
Conventionally written as the lower case first letter of the term e.g., a and b for Alice and Bob
Predicate logic notation
Predicates - upper case first letter of the verb
Term - lower case first letter
Atomic formula
Combines terms and predicates to make a formula
e.g., Bob is a man -> M(a)
Arity of an atomic formulae
the number of variables it takes as arguments
Variable
Represents general terms - unspecified individuals of the same type.
Abstracts away from specific objects such as constants.
Conventions for variables
Written as a lowercase letter from the end of the alphabet like x or y
E.g., in M(x), variable x represents male humans and predicate M represents “is a man”.
Truth values
A value representing whether an atomic formula is true or false
E.g., M(x) where M is a predicate for “is male” would be true of x is a man.
Closed/ground formulae
Predicates where the arguments are only constants
They are propositions and have truth values
Open/unground formula
Predicates where at least 1 argument is a variable
They are not propositions and don’t have truth values
Universe of discourse
All entities that can replace a variable in an atomic formula.
Compound formulae
Formulae obtained by applying logical connectives to atomic formulae
E.g., “Jay and Kay are SCC121 students” = S(j) AND S(k)
Quantifiers
Operates that state how many values from universe of discourse satisfy an open formula.
Quantified formulae are made when quantifiers are combined with terms in open formulae.
Universal quantifier
Denotes that a statement applies to all elements in the domain.
It has the symbol ∀ which is read as “for all”.
∀x P(x) is true if P(x) is true for every x in the domain.
∀x P(x) is false if there exists at least one x for which P(x) is false.
Existential Quantifier
Denotes that a statement applies to at least one element in the domain.
It has the symbol ∃ which reads “there exists”
∃x P(x) is true if there exists at least one x in the domain for which P(x) is true.
∃x P(x) is false if P(x) is false for all x in the domain.
Negation of universal quantifier
if ∀x B(x) = “all cats are black”, the negation is ~∀x B(x) = “not all cats are black”.
“not all cats are black” is equivalent to “there is at least one cat who is not black” or ~∀x B(x) = Ǝx ~B(x)
Negation of existential quantifier
if ∃x P(x) = “there exists a cat which is purple”, the negation is ~∃x P(x) = “there is no cat which is purple”.
“it is not the case that there is a cat who is purple” is equivalent to: “every cat is not purple” or ~Ǝx P(x) = ∀x ~P(x)
De Morgan’s Laws for Quantifiers
~∀x P(x) ≡ Ǝx ~P(x)
~Ǝx P(x) ≡ ∀x ~P(x).
Unrestricted quantifiers
all elements in the Universe of Discourse
Restricted quantifiers
some elements in the Universe of Discourse (a subset)
Universal instantiation
∀x M(x) ∴ M(c)
e.g., Every man is mortal therefore any specific man is mortal
Universal generalization
M(a) for any arbitrary a ∴ ∀x M(x)
e.g., Any arbitrary man is mortal therefore every man is mortal
Existential instantiation
Ǝx M(x) ∴ M(a) for some element a
e.g., There is someone who is mortal, let’s call them a therefore a is mortal
Existential generalization
P(c) for some element c ∴ Ǝx P(x)
e.g., Aristotle is mortal therefore there is someone who is mortal
Precedence
Quantifiers have the highest precedence over all binary connectives
Order:
∀, Ǝ
¬
∧
∨
→
↔
Nested quantifiers
May need more than 1 quantifier for a formula
Order only matters if quantifiers are of different types
Assignment of variables
A variable will be substituted into a formula for each value in the universe of discourse and assign a truth value to each entity in the universe of discourse.
