DISCRETE MATH QUIZ 2

Predicate

• Refers to a property that the subject of the statement can have.

Quantifiers

• Expresses the extent to which a predicate is true over a range of elements

Predicate Calculus

• Area of logic that deals with predicates and quantifiers.

Domain of discourse

• A particular domain where mathematical statements assert that a property is true for all values of a variable.

Universal Quantifier

• Tells us that a predicate is true for every element under consideration

• uses symbol “∀“

Existential Quantifiers

• Tells us that there is one or more element under consideration for which the predicate is true

• Uses symbol “∃“

Bound

• An occurrence of a variable when a quantifier is used on it.

Free

• An occurrence of a variable that is not bound by a quantifier or set equal to a particular value.

∀x(P(x) v Q(x))

Let P (x) be the statement “x can speak Russian” and let Q(x) be the statement “x knows the computer language C++.” Express each of these sentences in terms of P (x), Q(x), quantifiers, and logical connectives

• Every student at your school either can speak Russian or knows C++

∀x(¬P(x) v ¬Q(x)) / ¬∃x(P(x) v Q(x))

 Let P (x) be the statement “x can speak Russian” and let Q(x) be the statement “x knows the computer language C++.” Express each of these sentences in terms of P (x), Q(x), quantifiers, and logical connectives.

• No student at your school can speak Russian or knows C++.

∃x((C(x) ^ D(x))^F(x))

Let C(x) be the statement “x has a cat,” let D(x) be the statement “x has a dog,” and let F (x) be the statement “x has a ferret.” Express each of these statements in terms of C(x), D(x), F (x), quantifiers, and logical connectives.

• A student in your class has a cat, a dog, and a ferret.

∃x((C(x) ^ F(x))^¬D(x))

Let C(x) be the statement “x has a cat,” let D(x) be the statement “x has a dog,” and let F (x) be the statement “x has a ferret.” Express each of these statements in terms of C(x), D(x), F (x), quantifiers, and logical connectives.

• Some student in your class has a cat and a ferret, but not a dog.

Every animal is a rabbit and hops

Translate these statements into English, where R(x) is “x is a rabbit” and H (x) is “x hops” and the domain consists of all animals.

• ∀x(R(x) ∧ H (x))

Every rabbit hops

Translate these statements into English, where R(x) is “x is a rabbit” and H (x) is “x hops” and the domain consists of all animals

•  ∀x(R(x) → H (x))

All people are comedians and funny.

Translate these statements into English, where C(x) is “x is a comedian” and F (x) is “x is funny” and the domain consists of all people.

• ∀x(C(x) ∧ F (x))

Set

• Is an unordered collection of objects called elements.

Roster Method

• Is a way of describing a set where we list all the members or elements of the set.

Set builder notation

• Way of describing a set where we characterize all the elements of the set by stating the property/properties that they must have to be members.

Empty set

• It is a special set that has no elements

• also known as “null set“

• Denoted by symbol “∅“ or { }

Subset

• Are set whose element are contained within another set

Power set

• It is the set of all the subsets of the set.

Union

• it is the set that contains the elements that are either in set A or in B.

Intersect

• A set that contains the elements that are in both set A and set B

Disjoint

• two sets that has an empty set as their intersection

Difference

• Is a set containing those elements that are in set A but not in set B

• A - B

{ x | x is a lowercase English letter, m<=x<=p}

Use set builder notation to give a description of each of these sets.

• {m, n, o, p}

{ x | x ∈ Z , -3<=x<=3}

Use set builder notation to give a description of each of these sets.

• {−3, −2, −1, 0, 1, 2, 3}

Second is a subset of the first

 For each of these pairs of sets, determine whether the first is a subset of the second, the second is a subset of the first, or neither is a subset of the other.

•  the set of airline flights from New York to New Delhi, the set of nonstop airline flights from New York to New Delhi

First is a subset of the second

 For each of these pairs of sets, determine whether the first is a subset of the second, the second is a subset of the first, or neither is a subset of the other.

• the set of flying squirrels, the set of living creatures that can fly

Neither is a subset of the other

 For each of these pairs of sets, determine whether the first is a subset of the second, the second is a subset of the first, or neither is a subset of the other.

• the set of students studying discrete mathematics, the set of students studying data structures

2 is an element of this set

For each of the following sets, determine whether 2 is an element of that set.

• {2,{2}}

2 is not an element of this set

For each of the following sets, determine whether 2 is an element of that set.

• {{2},{2,{2}}}

{2} is an element of this set

For each of the following sets, determine whether {2} is an element of that set.

• {{2},{{2}}}

{2} is not an element of this set

For each of the following sets, determine whether {2} is an element of that set.

• {{{2}}}

FALSE

Determine whether each of these statements is true or false.

• 0 ∈ ∅

FALSE

Determine whether each of these statements is true or false.

• {0}∈{0}

FALSE

Determine whether each of these statements is true or false.

• {0}⊂{0}

TRUE

Determine whether each of these statements is true or false.

• {∅} ⊂ {∅,{∅}}

Set of students who live within one mile of school and walk to classes

Let A be the set of students who live within one mile of school and let B be the set of students who walk to classes. Describe the students in each of these sets.

• A ∩ B

Set of students who live within one mile of school, but do not walk to classes

Let A be the set of students who live within one mile of school and let B be the set of students who walk to classes. Describe the students in each of these sets.

• A − B
  

Set of students who either live within one mile of school or walk to classes

Let A be the set of students who live within one mile of school and let B be the set of students who walk to classes. Describe the students in each of these sets.

• A ∪ B

U-(A∩B)

Suppose that A is the set of sophomores at your school and B is the set of students

in discrete mathematics at your school. Express each of these sets in terms of A and B.

• the set of students at your school who either are not sophomores or are not taking discrete mathematics

B-A

Suppose that A is the set of sophomores at your school and B is the set of students

in discrete mathematics at your school. Express each of these sets in terms of A and B.

• Set of students who are taking discrete mathematics, but not sophomores.

{0,6}

Let A = {1, 2, 3, 4, 5} and B = {0, 3, 6}. Find

• B - A
  

{a,b,c,d,e}

Let A = {a, b, c, d, e} and B = {a, b, c, d, e, f, g, h}. Find

• A ∩ B