Scribd
Upload
18 views4 pages

Understanding Quantifiers in Logic

Công ty Kiếm thẻ cào chúng tôi chia sẻ đến bạn cách kiếm thẻ cào trên điện thoại Android và IOS giúp bạn dễ dàng kiếm thêm thu nhập mỗi ngày mà không mất bất kỳ chi phí nào từ nhiều hình thức khác nhau: làm khảo sát online, đọc báo hay 24h kiếm tiền. Address: Công Ty Kiếm Thẻ Cào Điện Thoại - Xóm Trung Tiến Diễn Hoàng - Diễn Châu - Nghệ An. Phone: (+84) 37 854 4082 Contact Us: Website: https://kiemthecaofree.com/ Facebook: https://www.facebook.com/kiemthecaocom

Uploaded by

Ngoc Duc
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
18 views4 pages

Understanding Quantifiers in Logic

Công ty Kiếm thẻ cào chúng tôi chia sẻ đến bạn cách kiếm thẻ cào trên điện thoại Android và IOS giúp bạn dễ dàng kiếm thêm thu nhập mỗi ngày mà không mất bất kỳ chi phí nào từ nhiều hình thức khác nhau: làm khảo sát online, đọc báo hay 24h kiếm tiền. Address: Công Ty Kiếm Thẻ Cào Điện Thoại - Xóm Trung Tiến Diễn Hoàng - Diễn Châu - Nghệ An. Phone: (+84) 37 854 4082 Contact Us: Website: https://kiemthecaofree.com/ Facebook: https://www.facebook.com/kiemthecaocom

Uploaded by

Ngoc Duc
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

[INT 1358]: Discrete Mathematics I

1.4 Predicates and Quantifiers


Predicate Logic
Predicate logic have the following features to express propositions:

• Variables: x, y, z, etc. (the subject of a sentence), can be substituted with an element from a
domain.

• Predicates: P, M , etc. (the predicate of a sentence)

• Domain: the collection of values that a variable can take.

Propositions must be definitive (not vague or undefined). So, a Propositional Function is not a
Proposition until all variables are defined (or “bound”).

Example: Let Q(x, y) denote the statement “x + y > 2x”

• Q(x, y) has two unbound variables (x and y), and is not a proposition.

• Q(1, y) = 1 + y > 2 [Not a proposition] one bound variable (x = 1) and one unbound
variable (y).

• Q(1, 2) = 1 + 2 > 2 [Proposition] two bound variables (x = 1 and y = 2)

Quantifiers
Quantifiers provide a notation that allows us to quantify (count) how many objects in the universe
of discourse satisfy the given predicate.

• Universal Quantifier ∀ - For all elements

• Existential Quantifier ∃ - There exists an element

De Morgan’s Law for Quantifiers


• ¬∀xP (x) ≡ ∃x¬P (x)

• ¬∃xP (x) ≡ ∀x¬P (x)

1.4 pg. 53 # 5
Let P (x) be the statement “x spends more than five hours every weekday in class,” where the
domain for x consists of all students. Express each of these quantifications in English.

a) ∃xP (x)
There exists a student who spends more than five hours every weekday in class.

1
[INT 1358]: Discrete Mathematics I

b) ∀xP (x)
Every student spends more than five hours every weekday in class.

c) ∃x¬P (x)
There exists a student who does not spend more than five hours every weekday in class.

d) ∀x¬P (x)
No student spends more than five hours every weekday in class.

1.4 pg. 53 # 11
Let P (x) be the statement “x = x2 .” If the domain consists of all the integers, what are these truth
values?

a) P (0)
True

c P (2)
False

e ∃xP (x)
True

f ∀xP (x)
False

1.4 pg. 54 # 25
Translate each of these statements into logical expressions using predicates, quantifiers, and logical
connectives. The domain of x is all people.

c All your friends are perfect.


Let F (x) be “x is your friend” and P (x) be “x is perfect.”
∀x(F (x) → P (x))

d At least one of your friends is perfect.


Let F (x) be “x is your friend” and P (x) be “x is perfect.”
∃x(F (x) ∧ P (x))

2
[INT 1358]: Discrete Mathematics I

1.4 pg. 55 # 33
Express each of these statements using quantifiers. Then form the negation of the statement, so
that no negation is to the left of a quantifier. Next, express the negation in simple English. (Do not
simply use the phrase “It is not the case that.”)

b No rabbit knows calculus.


C(x) =“x knows calculus”.
Domain for x is all rabbits.
∀x¬C(x)
∃xC(x)
There exists a rabbit that knows calculus.

c Every bird can fly.


F (x) =“x can fly”.
Domain for x is all birds.
∀xF (x)
∃x¬F (x)
There exists a bird who cannot fly.

1.4 pg. 55 # 35
Find a counterexample, if possible, to these universally quantified statements, where the domain
for all variables consists of all integers.

a ∀x(x2 ≥ x)
No counter example. See Example 13 in section 1.4.

b ∀x(x > 0 ∨ x < 0)


0. Since 0 is not less than or greater than 0, 0 is a counter example.

c ∀x(x = 1)
2. Since 2 is not 1, 2 is a counter example.

1.4 pg. 56 # 59
Let P (x), Q(x), and R(x) be the statements “x is a professor,” “x is ignorant,” and “x is vain,”
respectively. Express each of these statements using quantifiers; logical connectives; and P (x),
Q(x), and R(x), where the domain consists of all people.

a No professors are ignorant.


∀x(P (x) → ¬Q(x))

b All ignorant people are vain.


∀x(Q(x) → R(x))

3
[INT 1358]: Discrete Mathematics I

c No professors are vain.


∀x(P (x) → ¬R(x))

d Does (c) follow from (a) and (b)?


No because we can have vain professors.

Common questions

Powered by AI

The logical expression ∀xP(x) describes this situation, where P(x) represents 'x spends more than five hours in class daily.' It implies that every student within the domain fulfills this condition, which means there are no exceptions among students .

The negation of 'Every bird can fly,' expressed as ∀xF(x), is ∃x¬F(x), which means 'There exists a bird who cannot fly.' This implies that at least one bird does not possess the ability to fly .

The statement 'No professors are vain' (∀x(P(x) → ¬R(x))) is not implied by the combination because the possibility remains for professors who are neither ignorant (P(x) → ¬Q(x)) nor vain. The antecedent 'No professors are ignorant' does not affect the consequent that professors can still be vain without being ignorant .

De Morgan's laws allow us to negate a universal quantification like ∀x¬C(x), which states 'No rabbit knows calculus,' by converting it to an existential quantification. The negation is expressed as ∃xC(x), meaning 'There exists a rabbit that knows calculus' .

The expression ∃x(F(x) ∧ P(x)) can be restated in English as 'At least one of your friends is perfect,' reflecting the existence of at least one individual satisfying both conditions — being a friend and being perfect .

The expression ¬∀xP(x) implies that it is not true that every element in the domain satisfies the predicate P(x). This can be restated using existential quantifiers as ∃x¬P(x), which means there exists at least one element in the domain for which P(x) is false .

The statement 'At least one of your friends is perfect' can be expressed using logical expressions as ∃x(F(x) ∧ P(x)), where F(x) denotes 'x is your friend' and P(x) denotes 'x is perfect' .

P(0) is true because for x = 0, the equation 0 = 0² holds true, conforming to the predicate x = x². The broader implication is that zero is a valid solution within the integer domain for this specific predicate, thus evidencing that the predicate holds for some but not all integers .

The logical expression for no person being ignorant in a domain can be given as ∀x¬Q(x), where Q(x) denotes 'x is ignorant.' Applying it with P(x) for professors and R(x) for vain as ∀x(P(x) → ¬Q(x)) shows professors are not ignorant, but this does not logically extend to 'no person is ignorant' as other domain elements may still be ignorant outside being professors .

A counterexample in universal quantifications disproves the statement by providing a specific instance where the predicate is false. For example, the universally quantified statement ∀x(x > 0 ∨ x < 0) is invalidated by 0, as 0 is neither greater than nor less than 0 .

You might also like