MATH 110- Quiz 1

MATH 110- Introduction to Mathematical Proofs. UCR

statement

a declarative sentence that must be true or false. NOT both

(section 1.1)

conditional statement

a statement that can be written in the form “If P, then Q”. Where P and Q are used.

*denoted as P⇒Q

(section 1.1)

Takeaway on conditionals

To prove a conditional is true, you must show that when P is true, Q is also true. Q is true when p is false.

To prove a conditional false, you must find an instance when P is true and Q is false.

(section 1.1)

In this class, natural numbers begin at…

1

(section 1.1)

0 is even or odd in this course

even

(section 1.1)

logical operator or connective

a word (or combination of) that combines multiple statements to make a new one

(section 2.1)

compound statement

a statement containing more than operator

(section 2.1)

negation

not P

• denoted as ~p or ¬P 

(section 2.1)

biconditional

statement in the form of (P⇒Q)∧ (Q⇒P)

• “P if and only if Q” can be P⟺Q

(section 2.1)

when are two statements logically equivalent?

• if they have the same truth tables for all combinations of truth values of the components

  • denoted P≡Q

(section 2.2)

converse of a conditional

Q⇒P

(section 2.2)

contrapositive

¬Q ⇒ ¬P
ex) statement: If it rains, then I carry an umbrella.

contrapositive: If I do not carry an umbrella, then it does not rain. 

(section 2.2)

Theorem 2.6 (Making conditionals into an ‘and’ or into an ‘or’)

• (P ⇒ Q) ≡ (¬P ∨ Q)

• ¬ (P ⇒ Q) ≡ (P ∧ ¬Q)

• (P ⇒ Q) ≡ (¬Q ⇒ ¬P)

(section 2.2)

How is P ⇒ Q expressed with a logical disjunction? (“or” operator)

¬P ∨ Q

(section 2.2)

How is ¬ (P ⇒ Q) written with a logical conjunction? (“and” operator)

P ∧ ¬Q

(section 2.2)

Is P ⇒ Q logically equivalent to its contrapositive?

yes

(section 2.2)

DeMorgan’s Laws

• ¬ (P ∧ Q) ≡ [(¬P) ∨ (¬Q)]

• ¬ (P ∨ Q) ≡ [(¬P) ∧ (¬Q)]

(section 2.2)

(DeMorgan’s Laws) What is the statement:

¬ (P ∧ Q)

logically equivalent to?

(¬P) ∨ (¬Q)

(section 2.2)

(DeMorgan’s Laws) What is the statement:

¬ (P ∨ Q)

logically equivalent to?

(¬P) ∧ (¬Q)

(section 2.2)

Is proving a conditional with more hypotheses easier or harder?

easier

(section 2.2)

set

a well defined collection of objects (section 2.3)

roster method

list the elements (section 2.3)

variable

a symbol representing an unspecified object that can be chosen from a given set (called the universal set for the variable)

ex: x, y, θ,.. etc

(section 2.3)

universal set

the set of specified objects from which objects may be chosen to substitute for the variable

(section 2.3)

constant

a specific member of the universal set

ex) All integers with x<3= subset B= {…,-2,-1,0,1,2}. This tells me U= 𝑍 ⊇ B

(section 2.3)

when are two sets equal?

when they contain the same elements.

(section 2.3)

Set A is a subset of B if…

each element of A is an element of B.

(section 2.3)

Given sets A= {1,2,3} and D= {3,3,2,1}, are sets A and D equal?

Yes. Even though D contains some numbers, the elements themselves are still contained within A. The elements of A are also contained within the elements of D. Their elements are identical.

(section 2.3)

open sentence/predicate

a sentence P(x₁, x₂,…,x_n) involving variables x₁, x₂,…, x_n with the property that when specific values from the universal set are substituted for x₁,x₂,…,x_n, the resulting sentence is either true or false (a statement).

(section 2.3)

an element

members of sets (section 2.3)

truth set of an open sentence with one variable

the subset of the universal set that can be substituted for the variable to make the predicate a true statement

(section 2.3)

set builder notation

{ x ∈ U | P(x) } the set of all elements x in the universal set U for which P(x) is true. Can also be written as { f(n) | n ∈ U }.

ex. { x ∈ 𝑍 | x² < 4 } = { x ∈ 𝑍 | -2 < x < 2 } = {-1,0,1} 

(section 2.3)

empty set

set with no elements

(section 2.3)

Does the phrase “for all” correlate to the universal or existential quantifier? How is it denoted?

for all = universal quantifier

denoted by ∀

(section 2.4)

Does the phrase “there exists” correlate to the universal or existential quantifier? How is it denoted?

there exists= existential quantifier

denoted by ∃

(section 2.4)

(∀x∈ U) (P(x)) is true provided that…

the truth set of P(x) is equal to the universal set

(section 2.4)

(∃x∈ U) (P(x)) is true provided that…

there is at least ONE value of x in the universal set that makes P(x) true.

(section 2.4)

the phrase “of a” is ∀ or ∃ ?

like in: “The square of a real number is greater than 3”

“of a”= ∀

 “The square of a real number is greater than 3” = ∀x ∈ R, x² > 3.

(section 2.4)

Provide two ways with quantifiers to write: “There exists an integer x such that x² >3” 

• (∃x ∈ 𝑍) (x² >3)

• ∃x ∈ 𝑍 such that x² >3

(section 2.4)

negation of the universal quantifier

(theorem 2.16)

Negation of (∀x ∈ U) (P(x)) is:

¬[(∀x ∈ U) (P(x))]

(∃x ∈ U) [¬P(x)]

*This asserts the original statement as false, so the truth set of P(x) is not U. There is an element of x of U such that P(x) is false. 

(section 2.4)

negation of the existential quantifier

(theorem 2.16)

negation of (∃x ∈ U) (P(x)) is

(∀x ∈ U) [¬P(x)]

(section 2.4)

counterexample for a ∀

an element x of the universal set U for which P(x) is false. It also shows the corresponding conditional (if x ∈ U, then P(x)) is false by making the hypothesis true and the conclusion false.

(section 2.4)

If a predicate contains more than one quantifier, how many variables need to be quantified to get a statement?

all of them

(section 2.4)

What happens if you quantify only one variable in an open sentence that contains 2 variables?

it becomes an open sentence with 1 variable. (the variable that was not quantified).

(section 2.4)

tautology

Always true.

ex: P∧ ¬P