Discrete Mathematics - Lecture 1.4 Predicates and Quantifiers PDF

Preview

Summary

Discrete Mathematics - Lecture 1.4 Predicates and Quantifiers...

Description

Math 3336 Section 1.4 Predicates and Quantifiers Predicates Propositional logic is not enough to express the meaning of all statements in mathematics and natural language. Examples: Is “ 1” True or False?

Is “

i

” True or False?

Predicate Logic • Variables: ฀฀, ฀฀, ฀฀, etc. • Predicates: ฀฀(฀฀), ฀฀(฀฀), etc. • Quantifiers: Universal and Existential • Connectives from propositional logic carry over to predicate logic. A predicate ฀฀(฀฀) is a declarative se ฀฀(฀฀) is also said to be the value of t ฀฀(฀฀) becomes a

n when

Examples (Propositional Functions): 1. Let ฀฀(฀฀) be “ a. ฀฀

2.

1.” Determine the truth value of

)

Let ฀฀(฀฀, ฀฀, ฀฀) be “฀ ฀

b. ฀฀(−2) → ฀฀ ฀฀

฀฀.” Find these truth values:

a. ฀฀(2, −1, 5)

b. ฀฀

Page 1 of 5

, 3,

We need quantifiers to express the meaning of English words including • •

and s

“All students in this class are computer science majors” “There is a math major student in this class”

The two most important quantifiers are: l,” symbol e exists,” sy

• •

We wr ). • ∀฀฀ ฀฀(฀฀) asserts ฀฀(฀฀) is true for If ฀ ฀ = {฀฀1 , ฀฀2 , … , ฀฀฀฀ } , then •

in the

∀฀฀ ฀฀(฀฀) = ฀฀(฀฀1 ) ∧ ฀฀(฀฀2 ) … ∧ ฀฀(฀฀฀฀ ).

∃฀฀ ฀฀(฀฀) asserts ฀฀(฀฀) is true for If ฀ ฀ = {฀฀1 , ฀฀2 , … , ฀฀฀฀ } , then

.

in the

.

∃฀฀ ฀฀(฀฀) = ฀฀(฀฀1 ) ∨ ฀฀(฀฀2 ) … ∨ ฀฀(฀฀฀฀ ).

Examples: 1. Let ฀฀(฀฀): “ ” with the domain of ). Find the truth value of

.

2. Let ฀฀(฀฀): “ ” with the domain of Find the truth value of

•

.

The truth value of ∃฀฀ ฀฀(฀฀) and ∀฀฀ ฀฀(฀฀) depends ฀฀(฀฀) and on the ฀฀.

on the

Quantifiers Statement ∀฀฀ ฀฀(฀฀) ∃฀฀ ฀฀(฀฀)

When True? ฀฀(฀฀) is true for There is

When False? .

which ฀฀(฀฀) is .

Page 2 of 5

There is ฀฀(฀฀ ฀฀(฀฀) is f

Example: Suppose the domain of the propositional function ฀฀(฀฀): ฀฀ consists of . Write out each of the following propositions using conjunction or disjunction and determine its truth value. 1. ∀฀฀ ฀฀(฀฀) 2. ∃฀฀ ฀฀(฀฀)

An element for which ฀฀(฀฀) is false is called a Precedence of Quantifiers The quantifiers

and

have

than

Example: ∀฀฀ ฀฀(฀฀) ∨ ฀฀(฀฀) means (∀฀฀ ฀฀(฀฀)) ∨ ฀฀(฀฀). ∀฀฀ (฀฀(฀฀) ∨ ฀฀(฀฀)) means something different. Negating Quantifiers De Morgan laws for quantifiers (the rules for negating quantifiers) are:

Example: Write the negations of the statements: 1.

an honest politician.”

3. ∀฀฀(฀฀ 2 > ฀฀)

Page 3 of 5

Translating from English into Logical Expressions Examples: Translate the statements into the logical symbols. Let . 1. in your class can speak Hindi. 2. in your class is friendly. 3. a student in your class who was not born in California. ฀฀(฀฀) = “ ฀฀ ฀฀฀฀฀฀฀฀฀฀฀฀ ฀฀฀฀฀฀฀฀฀฀”, ฀฀(฀฀) = “ ฀฀ ฀฀฀฀ ฀฀฀฀฀฀฀฀฀฀฀฀฀฀฀฀, ” ฀฀(฀฀ ) = “ ฀฀ ฀฀฀฀฀฀ ฀฀฀฀฀฀฀฀ ฀฀฀฀ ฀฀฀฀฀

Example: Translate the following sentence into predicate logic and give its negation: “Every student in this class has taken a course in Java.” Solution: First, decide on the domain U! Solution 1: If U is “ Solution 2: But if

define a propositional function ” and translate as , also define a propositional function ” and translate as

Page 4 of 5

) denoting

) denoting “

Example: Translate the following sentence into predicate logic: student in this class has taken a course in Java.” Solution: First, decide on the domain U! Solution 1: If Solution 2: But if

, translate as then translate as

Page 5 of 5...