CS计算机代考程序代写 FIT2014 Theory of Computation Lecture 3 Predicate Logic

FIT2014 Theory of Computation Lecture 3 Predicate Logic

FIT2014 Theory of Computation

Lecture 3
Predicate Logic

slides by

COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969

Warning
This material has been reproduced and communicated to you by or on behalf of Monash University

in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.

Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.

1 / 20

Lecture overview

I Statements with variables

I Predicates

I Definitions and terminology

I Existential quantifier

I Universal quantifier

I Doing logic with quantifiers

2 / 20

Statements with variables

Consider these statements:

I W is negative.

I X passed this subject.

I Y = Z .

These do not yet have truth values.

The variables are free, in that no value is (yet) given to them.

You can, if you wish, assign values to them.

Each set of values you give to the variables creates a different specific proposition.

3 / 20

Statements with variables

For example, in the statement W is negative, the variable W is free.
If we assign values to it, we can create specific propositions:


−2 is negative True
−1 is negative True

0 is negative False
1 is negative False
2 is negative False


4 / 20

Predicates
Definitions
A predicate is a statement with variables such that, for any values of the variables, it
is either True or False.

I i.e., it becomes a proposition

We treat each variable as ranging over some domain.

I For the predicate W is negative, we’ve just been using the domain Z.

The variables of a predicate are also called its arguments.

A predicate is called k-ary if it has k arguments. Special cases: unary, binary, ternary, . . .

Some alternative terminology:

# arguments terminology

1 property
≥ 2 relation

5 / 20

Predicates
Definitions
A predicate is a statement with variables such that, for any values of the variables, it
is either True or False.

I i.e., it becomes a proposition

We treat each variable as ranging over some domain.

I For the predicate W is negative, we’ve just been using the domain Z.

The variables of a predicate are also called its arguments.

A predicate is called k-ary if it has k arguments. Special cases: unary, binary, ternary, . . .

Some alternative terminology:

# arguments terminology

1 property
≥ 2 relation

5 / 20

Predicates
Definitions
A predicate is a statement with variables such that, for any values of the variables, it
is either True or False.

I i.e., it becomes a proposition

We treat each variable as ranging over some domain.

I For the predicate W is negative, we’ve just been using the domain Z.

The variables of a predicate are also called its arguments.

A predicate is called k-ary if it has k arguments. Special cases: unary, binary, ternary, . . .

Some alternative terminology:

# arguments terminology

1 property
≥ 2 relation

5 / 20

Predicates: examples

# args. example domain

1 isNegative(X ) N
1 isNegative(X ) Z
2 = [always available] objects
2 X < Y numbers 2 isMotherOf(X ,Y ), meaning “X is the mother of Y ” people 3 gives(X ,Y ,Z ), meaning “X gives Y to Z” X ,Z are people, Y is a gift ... ... ... Predicates may be thought of as truth-valued functions, i.e., functions whose value is always in {True, False}. 6 / 20 Predicates: examples # args. example domain 1 isNegative(X ) N 1 isNegative(X ) Z 2 = [always available] objects 2 X < Y numbers 2 isMotherOf(X ,Y ), meaning “X is the mother of Y ” people 3 gives(X ,Y ,Z ), meaning “X gives Y to Z” X ,Z are people, Y is a gift ... ... ... Predicates may be thought of as truth-valued functions, i.e., functions whose value is always in {True, False}. 6 / 20 Functions We’ll also use functions whose values aren’t necessarily just True or False. # args. example domain codomain 1 √ X nonnegative numbers numbers 1 motherOf(X ) people people 2 X + Y numbers numbers ... ... ... Functions with no arguments are called constants. I Examples: 5, Annie, . . . A function’s arguments can be: constants; variables; functions. 7 / 20 Functions We’ll also use functions whose values aren’t necessarily just True or False. # args. example domain codomain 1 √ X nonnegative numbers numbers 1 motherOf(X ) people people 2 X + Y numbers numbers ... ... ... Functions with no arguments are called constants. I Examples: 5, Annie, . . . A function’s arguments can be: constants; variables; functions. 7 / 20 Existential quantifier There’s a fly in my soup. ∃X : (X is a fly) ∧ (X is in my soup). There exists W : W is negative. ∃W : W < 0 If domain of W is N: it’s False. ∃W ∈ N : W < 0 If domain of W is Z: it’s True. ∃W ∈ Z : W < 0 8 / 20 Existential quantifier There’s a fly in my soup. ∃X : (X is a fly) ∧ (X is in my soup). There exists W : W is negative. ∃W : W < 0 If domain of W is N: it’s False. ∃W ∈ N : W < 0 If domain of W is Z: it’s True. ∃W ∈ Z : W < 0 8 / 20 Existential quantifier Someone did it. ∃X : X did it. It’s sort-of like a disjunction . . . · · · · · ·∨(Annie did it)∨(Edward did it)∨(Henrietta did it)∨(Radhanath did it)∨· · · · · · . . . but: I often the domain of a variable is infinite; I keep the variables, they’re useful. The variables are now bound. You can no longer give specific values to the variables to create specific propositions. The quantifier has turned the statement into a single proposition about the entire domains of the variables. Quantifiers can only be used with variables. Using them with constant objects makes no sense: ∃5, ∃Annie. 9 / 20 Existential quantifier Someone did it. ∃X : X did it. It’s sort-of like a disjunction . . . · · · · · ·∨(Annie did it)∨(Edward did it)∨(Henrietta did it)∨(Radhanath did it)∨· · · · · · . . . but: I often the domain of a variable is infinite; I keep the variables, they’re useful. The variables are now bound. You can no longer give specific values to the variables to create specific propositions. The quantifier has turned the statement into a single proposition about the entire domains of the variables. Quantifiers can only be used with variables. Using them with constant objects makes no sense: ∃5, ∃Annie. 9 / 20 Existential quantifier Some computer is human. i.e., There exists a human computer. If the domain of X is { computers } Predicate: I human(X ): X is human. ∃X : human(X ) But what if the domain of X is { everything on Earth } ? Predicates: I human(X ): X is human. I computer(X ): X is a computer. 10 / 20 Existential quantifier Some computer is human. i.e., There exists a human computer. If the domain of X is { computers } Predicate: I human(X ): X is human. ∃X : human(X ) But what if the domain of X is { everything on Earth } ? Predicates: I human(X ): X is human. I computer(X ): X is a computer. 10 / 20 Existential quantifier Some computer is human. i.e., There exists a human computer. If the domain of X is { everything on Earth } Predicates: I human(X ): X is human. I computer(X ): X is a computer. Correct: Incorrect: ∃X : computer(X ) ∧ human(X ) ∃X : computer(X )⇒ human(X ) I “There exists something that is both computer and human.” I “There exists a human computer.” I “Some computer is human.” I “There exists something which is not a computer or is human.” I “There exists something which is not both a computer and non-human.” I “Not everything is a nonhuman computer.” 11 / 20 Existential quantifier Some computer is human. i.e., There exists a human computer. If the domain of X is { everything on Earth } Predicates: I human(X ): X is human. I computer(X ): X is a computer. Correct: Incorrect: ∃X : computer(X ) ∧ human(X ) ∃X : computer(X )⇒ human(X ) I “There exists something that is both computer and human.” I “There exists a human computer.” I “Some computer is human.” I “There exists something which is not a computer or is human.” I “There exists something which is not both a computer and non-human.” I “Not everything is a nonhuman computer.” 11 / 20 Existential quantifier Some computer is human. i.e., There exists a human computer. If the domain of X is { everything on Earth } Predicates: I human(X ): X is human. I computer(X ): X is a computer. Correct: Incorrect: ∃X : computer(X ) ∧ human(X ) ∃X : computer(X )⇒ human(X ) I “There exists something that is both computer and human.” I “There exists a human computer.” I “Some computer is human.” I “There exists something which is not a computer or is human.” I “There exists something which is not both a computer and non-human.” I “Not everything is a nonhuman computer.” 11 / 20 Universal quantifier Everyone can pass this subject. For every X : X can pass this subject. ∀X : canPass(X ). All numbers are interesting. ∀X : X is interesting. ∀X : isInteresting(X ). I True — and we’ll prove it! For all W : W is negative ∀W : W < 0. False. Again, the variables are now bound. 12 / 20 Universal quantifier Every computer is human. If the domain of X is { computers } Predicate: I human(X ): X is human. ∀X : human(X ) But what if the domain of X is { everything on Earth } ? Predicates: I human(X ): X is human. I computer(X ): X is a computer. 13 / 20 Universal quantifier Every computer is human. If the domain of X is { computers } Predicate: I human(X ): X is human. ∀X : human(X ) But what if the domain of X is { everything on Earth } ? Predicates: I human(X ): X is human. I computer(X ): X is a computer. 13 / 20 Universal quantifier Every computer is human. If the domain of X is { everything on Earth } Predicates: I human(X ): X is human. I computer(X ): X is a computer. Incorrect: Correct: ∀X : computer(X ) ∧ human(X ) ∀X : computer(X )⇒ human(X ) I “Everything is both computer and human.” I “Everything is a human computer.” I “For everything, if it’s a computer, then it’s human.” I “Everything that’s a computer is also human.” I “Every computer is human.” 14 / 20 Universal quantifier Every computer is human. If the domain of X is { everything on Earth } Predicates: I human(X ): X is human. I computer(X ): X is a computer. Incorrect: Correct: ∀X : computer(X ) ∧ human(X ) ∀X : computer(X )⇒ human(X ) I “Everything is both computer and human.” I “Everything is a human computer.” I “For everything, if it’s a computer, then it’s human.” I “Everything that’s a computer is also human.” I “Every computer is human.” 14 / 20 Universal quantifier Every computer is human. If the domain of X is { everything on Earth } Predicates: I human(X ): X is human. I computer(X ): X is a computer. Incorrect: Correct: ∀X : computer(X ) ∧ human(X ) ∀X : computer(X )⇒ human(X ) I “Everything is both computer and human.” I “Everything is a human computer.” I “For everything, if it’s a computer, then it’s human.” I “Everything that’s a computer is also human.” I “Every computer is human.” 14 / 20 Multiple quantifiers Thinking of graphs . . . Suppose we have a predicate adj(X ,Y ) meaning that vertices X and Y are adjacent. Some two vertices are not adjacent. ∃X ∃Y : ¬(X = Y ) ∧ ¬adj(X ,Y ). ∃(X ,Y ) : ¬(X = Y ) ∧ ¬adj(X ,Y ). Every pair of vertices is adjacent. ∀X ∀Y : ¬(X = Y ) ⇒ adj(X ,Y ). ∀(X ,Y ) : ¬(X = Y ) ⇒ adj(X ,Y ). Some vertex is adjacent to all other vertices. ∃X ∀Y : ¬(X = Y ) ⇒ adj(X ,Y ). Every vertex has a neighbour. ∀X ∃Y : adj(X ,Y ). 15 / 20 Multiple quantifiers Thinking of graphs . . . Suppose we have a predicate adj(X ,Y ) meaning that vertices X and Y are adjacent. Some two vertices are not adjacent. ∃X ∃Y : ¬(X = Y ) ∧ ¬adj(X ,Y ). ∃(X ,Y ) : ¬(X = Y ) ∧ ¬adj(X ,Y ). Every pair of vertices is adjacent. ∀X ∀Y : ¬(X = Y ) ⇒ adj(X ,Y ). ∀(X ,Y ) : ¬(X = Y ) ⇒ adj(X ,Y ). Some vertex is adjacent to all other vertices. ∃X ∀Y : ¬(X = Y ) ⇒ adj(X ,Y ). Every vertex has a neighbour. ∀X ∃Y : adj(X ,Y ). 15 / 20 Multiple quantifiers Thinking of graphs . . . Suppose we have a predicate adj(X ,Y ) meaning that vertices X and Y are adjacent. Some two vertices are not adjacent. ∃X ∃Y : ¬(X = Y ) ∧ ¬adj(X ,Y ). ∃(X ,Y ) : ¬(X = Y ) ∧ ¬adj(X ,Y ). Every pair of vertices is adjacent. ∀X ∀Y : ¬(X = Y ) ⇒ adj(X ,Y ). ∀(X ,Y ) : ¬(X = Y ) ⇒ adj(X ,Y ). Some vertex is adjacent to all other vertices. ∃X ∀Y : ¬(X = Y ) ⇒ adj(X ,Y ). Every vertex has a neighbour. ∀X ∃Y : adj(X ,Y ). 15 / 20 Multiple quantifiers Six degrees of separation Suppose we have a predicate knows(X ,Y ) meaning that person X knows person Y . It has been claimed that, in the human social network, the maximum distance between any two people is at most 6. Exercise: write this claim in predicate logic, using just the predicate knows. 16 / 20 Doing logic with quantifiers If we know that ∀X blah(X ) and obj is any specific object (in the domain of X ), then we can deduce that blah(obj) We have: (∀X blah(X )) ⇒ blah(obj) Also: blah(obj) ⇒ (∃X blah(X )) 17 / 20 Doing logic with quantifiers If we know that ∀X blah(X ) and obj is any specific object (in the domain of X ), then we can deduce that blah(obj) We have: (∀X blah(X )) ⇒ blah(obj) Also: blah(obj) ⇒ (∃X blah(X )) 17 / 20 Doing logic with quantifiers ∀X (p(X ) ∧ q(X )) is logically equivalent to (∀X p(X )) ∧ (∀X q(X )) ∃X (p(X ) ∨ q(X )) is logically equivalent to (∃X p(X )) ∨ (∃X q(X )) What about the logical relationship between . . . ∀X (p(X ) ∨ q(X )) and (∀X p(X )) ∨ (∀X q(X )) . . . ? . . . etc 18 / 20 Doing logic with quantifiers ∀X (p(X ) ∧ q(X )) is logically equivalent to (∀X p(X )) ∧ (∀X q(X )) ∃X (p(X ) ∨ q(X )) is logically equivalent to (∃X p(X )) ∨ (∃X q(X )) What about the logical relationship between . . . ∀X (p(X ) ∨ q(X )) and (∀X p(X )) ∨ (∀X q(X )) . . . ? . . . etc 18 / 20 Relationship between quantifiers ¬ ∀Y means the same as ∃Y ¬ “Not all dogs are happy.” is the same as . . . “There exists an unhappy dog.” ¬∀X (dog(X ) ⇒ happy(X )) Not all dogs are happy = ∃X ¬(dog(X ) ⇒ happy(X )) = ∃X ¬(¬dog(X ) ∨ happy(X )) (see last lecture) = ∃X (¬¬dog(X ) ∧ ¬happy(X )) (by De Morgan) = ∃X (dog(X ) ∧ ¬happy(X )) There exists an unhappy dog 19 / 20 Relationship between quantifiers Similarly, ¬ ∃Y means the same as ∀Y ¬ ¬ ∀Y ¬ means the same as ¬ ∃Y ¬ means the same as 20 / 20