121 Week 5 - Predicate Logic

Question 1

Why is predicate logic needed

Answer 1

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.

Question 2

What are the 2 parts of predicate logic

Answer 2

Syntax and semantics

Question 3

Syntax

Answer 3

notations for concepts and operators used to create formulae

Question 4

Semantics

Answer 4

The meanings behind the formulas

Question 5

Predicates

Answer 5

A verb describing a property or relation of a term

Question 6

Terms

Answer 6

Subjects expressed through nouns or pronouns

Question 7

Atomic formula

Answer 7

Smallest element of predicate logic
Consists of 1 predicate and 1 or more terms

Question 8

Predicates for properties

Answer 8

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

Question 9

Predicates for relations

Answer 9

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.

Question 10

Constant terms

Answer 10

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

Question 11

Predicate logic notation

Answer 11

Predicates - upper case first letter of the verb
Term - lower case first letter

Question 12

Atomic formula

Answer 12

Combines terms and predicates to make a formula
e.g., Bob is a man -> M(a)

Question 13

Arity of an atomic formulae

Answer 13

the number of variables it takes as arguments

Question 14

Variable

Answer 14

Represents general terms - unspecified individuals of the same type.
Abstracts away from specific objects such as constants.

Question 15

Conventions for variables

Answer 15

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”.

Question 16

Truth values

Answer 16

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.

Question 17

Closed/ground formulae

Answer 17

Predicates where the arguments are only constants
They are propositions and have truth values

Question 18

Open/unground formula

Answer 18

Predicates where at least 1 argument is a variable
They are not propositions and don’t have truth values

Question 19

Universe of discourse

Answer 19

All entities that can replace a variable in an atomic formula.

Question 20

Compound formulae

Answer 20

Formulae obtained by applying logical connectives to atomic formulae
E.g., “Jay and Kay are SCC121 students” = S(j) AND S(k)

Question 21

Quantifiers

Answer 21

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.

Question 22

Universal quantifier

Answer 22

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.

Question 23

Existential Quantifier

Answer 23

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.

Question 24

Negation of universal quantifier

Answer 24

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)

Question 25

Negation of existential quantifier

Answer 25

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)

Question 26

De Morgan’s Laws for Quantifiers

Answer 26

~∀x P(x) ≡ Ǝx ~P(x)
~Ǝx P(x) ≡ ∀x ~P(x).

Question 27

Unrestricted quantifiers

Answer 27

all elements in the Universe of Discourse

Question 28

Restricted quantifiers

Answer 28

some elements in the Universe of Discourse (a subset)

Question 29

Universal instantiation

Answer 29

∀x M(x) ∴ M(c)
e.g., Every man is mortal therefore any specific man is mortal

Question 30

Universal generalization

Answer 30

M(a) for any arbitrary a ∴ ∀x M(x)
e.g., Any arbitrary man is mortal therefore every man is mortal

Question 31

Existential instantiation

Answer 31

Ǝ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

Question 32

Existential generalization

Answer 32

P(c) for some element c ∴ Ǝx P(x)
e.g., Aristotle is mortal therefore there is someone who is mortal

Question 33

Precedence

Answer 33

Quantifiers have the highest precedence over all binary connectives
Order:
∀, Ǝ
¬
∧
∨
→
↔

Question 34

Nested quantifiers

Answer 34

May need more than 1 quantifier for a formula
Order only matters if quantifiers are of different types

Question 35

Assignment of variables

Answer 35

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.