程序代写 CSI 2101: Discrete Structures

Predicate Logic and Quantifiers
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
January 19, 2022

Copyright By PowCoder代写 加微信 powcoder

Md. Hasan (uOttawa) Discrete Structures 1c MdH W22 January 19, 2022 1 / 13

1 Predicates and Quantifiers
2 Nested Quantifiers
Md. Hasan (uOttawa) Discrete Structures 1c MdH W22 January 19, 2022 2 / 13

Predicates
􏰀 Propositional logic is inadequate in expressing the meaning of a wide range of mathematical statements. Thus, a different type of logic named predicate logic is introduced in mathematics and computer science.
􏰀 Predicates
“x is less than 9” P(x)
(mathematical expression) (natural language) (propositional function)
• x is the subject and also the variable
• P is the predicate
• P(x) is a proposition and has a truth value
Md. Hasan (uOttawa) Discrete Structures 1c MdH W22 January 19, 2022 3 / 13

Predicates (cont.)
• Let P(x) denotes the statement “x < 9”. • P(11) is false. • P(4) is true. 􏰀 A statement can also include multiple variables. In that case, the propositional function is also a multivariable function. • Let Q (x , y , z ) denotes the statement “x + y = z ”. • Q(1, 0, 1) is true. • Q(3, 4, 5) is false. Md. Hasan (uOttawa) Discrete Structures 1c MdH W22 January 19, 2022 4 / 13 Quantifiers 􏰀 Quantifiers are used to express the extent to which a predicate is true over a range of elements. 􏰀 The Universal Quantifier A property is true for all values of a variable in a particular domain. • “P(x) for all values of x in the domain.” • ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the universal quantifier. • An element for which P(x) is false is called a counterexample to ∀xP(x). • We just need one counterexample to establish that ∀xP(x) is false. • ∀x(x2 ≥ x) is false if the domain consists of all real numbers. • ∀x(x2 ≥ x) is true if the domain consists of all integers. Md. Hasan (uOttawa) Discrete Structures 1c MdH W22 January 19, 2022 5 / 13 Quantifiers (cont.) 􏰀 The Existential Quantifier There exists at least one element with a certain property. • “There exists an element x in the domain such that P(x).” • ∃xP(x) denotes the existential quantification of P(x). Here ∃ is called the existential quantifier. 􏰀 Example • “∃x(x > 3)” is true where the domain consists of all real numbers.
• “∃x(x = x + 1)” is false where the domain consists of all real numbers.
∀xP(x) ∃xP(x)
Table: Quantifiers When True?
When False?
P(x) is true for every x. There is an x for which P(x) is true.
There is an x for which P(x) is false. P(x) is false for every x.
Md. Hasan (uOttawa)
Discrete Structures 1c MdH W22 January 19, 2022 6 / 13

Quantifiers (cont.)
􏰀 The Uniqueness Quantifier
∃!xP(x)denotes“There exists a unique x such that P(x) is true.”
􏰀 Quantifiers Over Finite Domains
• When the elements of the domain are x1, x2, …, xn, where n is a positive integer, the universal quantification ∀xP(x) is the same as the conjunction P(x1) ∧ P(x2) ∧ … ∧ P(xn).
• When the elements of the domain are x1, x2, …, xn, where n is a positive integer, the existential quantification ∃xP(x) is the same as the disjunction P(x1) ∨ P(x2) ∨ … ∨ P(xn).
Md. Hasan (uOttawa) Discrete Structures 1c MdH W22 January 19, 2022 7 / 13

Quantifiers (cont.)
􏰀 Precedence of Quantifiers
The quantifiers ∀ and ∃ have higher precedence than all logical operators
from propositional calculus.
∀xP(x) ∨ Q(x) is the disjunction of ∀xP(x) and Q(x). In other words, it
means (∀xP(x)) ∨ Q(x) rather than ∀x(P(x) ∨ Q(x)). 􏰀 Logical Equivalences Involving Quantifiers
Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions.
Md. Hasan (uOttawa) Discrete Structures 1c MdH W22 January 19, 2022 8 / 13

Quantifiers (cont.)
􏰀 Negating Quantified Expressions De Morgan’s Laws for quantifiers:
¬∀xP(x) ≡ ∃x¬P(x) ¬∃xP(x) ≡ ∀x¬P(x)
“Every student in this class has bought the textbook” (∀xP(x))
“It is not the case that every student in this class has bought the textbook” (¬∀xP(x))
“There is a student in this class who has not bought the textbook” (∃x¬P(x))
“There is a student in this class who has bought the textbook” (∃xP(x)) “It is not the case that there is a student in this class who has bought the textbook” (¬∃xP(x))
“Every student in this class has not bought the textbook” (∀x¬P(x))
Md. Hasan (uOttawa) Discrete Structures 1c MdH W22 January 19, 2022 9 / 13

Nested Quantifiers
􏰀 Nested quantifiers commonly occur in mathematics and computer science. They are also necessary to express the meaning of sentences in natural languages.
– The statement ∀x∀y(x + y = y + x) says that x + y = y + x for all real numbers x and y (we assume that the domain for the variables x and y consists all real numbers).
– The statement ∀x∃y(x + y = 0) says that for every real number x there is a real number y such that x + y = 0. This states that every real number has an additive inverse (we assume that the domain for the variables x and y consists all real numbers).
Md. Hasan (uOttawa) Discrete Structures 1c MdH W22 January 19, 2022 10 / 13

Nested Quantifiers (cont.)
􏰀 The order of the quantifiers in a nested statement is important, unless all are universal quantifiers or all are existential quantifiers.
– Let Q (x , y ) denotes “x + y = 0” where the domain for all variables
consists all real numbers.
– The statements ∃y∀xQ(x, y) and ∀x∃yQ(x, y) are not logically equivalent.
• ∃y∀xQ(x,y) denotes “There is a real number y such that for every real number x, Q(x,y).” (False)
• ∀x∃yQ(x,y) denotes “For every real number x there is a real number y such that Q(x,y).” (True)
Md. Hasan (uOttawa) Discrete Structures 1c MdH W22 January 19, 2022 11 / 13

Nested Quantifiers (cont.)
∀x∀yP(x, y) ∀y∀xP(x, y)
∀x∃yP(x, y) ∃x∀yP(x, y)
∃x∃yP(x, y) ∃y∃xP(x, y)
Table: Quantification of Two Variables When True?
When False?
P(x, y) is true for every pair x, y.
For every x there is a y for which P(x, y) is true. There is an x for which P(x, y) is true for every y. There is a pair x, y for which P(x, y) is true.
There is a pair x, y for which P(x, y) is false.
There is an x such that P(x, y) is false for every y. For every x there is a y for which P(x, y) is false. P(x, y) is false for every pair x, y.
Md. Hasan (uOttawa) Discrete Structures 1c MdH W22 January 19, 2022 12 / 13

Thank You!
Questions and Comments?
Md. Hasan (uOttawa) Discrete Structures 1c MdH W22 January 19, 2022 13 / 13

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com