Exam 1: Weeks 1 - 5

What does this symbol mean: ⊕

exclusive or - -true when p OR q is true, but NOT if both are true

In a truth table, if there are 3 variables (p v q ^ r), how many rows will there be?

2^3 = 8 rows

What does this symbol mean: →

conditional - -"if p then q"; -Only false if p is false and q is true

what is the converse of p → q

q → p

what is the contrapositive of p → q

¬q → ¬p

what is the inverse of p → q

¬p → ¬q

What does this symbol mean: ↔

biconditional - - "p if and only if q"-true when p and q have the SAME truth values

What is a tautology?

a proposition that is always true

De Morgan's Law: ¬(p ∨ q)

¬p ∧ ¬q

De Morgan's Law: ¬(p ∧ q)

¬p ∨ ¬q

What is a logical statement whose truth value is a function of one or more variables?

predicate

Is "x is an odd number" a proposition?

no sir - if it contains a variable, it is a predicate

What is a universally quantified statement?

∀x P(x)

What is an existentially quantified statement?

∃x P(x)

T/F: The expression (∃x S(x)) ∨ R(x) is a proposition.

False

T/F: The expression ∃x P(x) is a proposition.

True

T/F: The expression ∀x P(x) ∨ ∃x Q(x) is a proposition.

True

T/F: The expression ∀x Q(x) ∧ ¬P(x) is a proposition

False - ¬P(x) is not bound by a quantifier

¬∀x F(x) is equivalent to what? (using De Morgan's law for quantified statements)

∃x ¬F(x)

¬∃x P(x) is equivalent to what? (using De Morgan's law for quantified statements)

∀x ¬P(x)

Simplify using De Morgan's: ¬∃x (P(x) ∨ Q(x))

∀x (¬P(x) ∧ ¬Q(x))

Simplify using De Morgan's: ¬∃x P(x)

∀x ¬P(x)

A logical expression with more than one quantifier that bind different variables in the same predicate is said to have what?

nested quantifiers

Is the variable y bound in the expression ∀x Q(x, y)?

NOPE - there is no quantifier that binds y

Is the following logical expression a proposition: ∀z ∃y Q(x, y, z)?

NOPE - The variable x is not bound

∀x ∀y P(x, y) ≡ ?(using De Morgan's)

∃x ∃y ¬P(x, y)

¬∀x ∃y P(x, y) ≡ ?(using De Morgan's)

∃x ∀y ¬P(x, y)

¬∃x ∀y P(x, y) ≡ ?(using De Morgan's)

∀x ∃y ¬P(x, y)

¬∃x ∃y P(x, y) ≡ ?(using De Morgan's)

∀x ∀y ¬P(x, y)

Write a logically equivalent statement: "Everyone sent an email to someone else

∀x ∃y ((x ≠ y) ∧ M(x, y))

Express: "Exactly one person was late to the meeting"(L(x): x was late to meeting)

∃x (L(x) ∧ ∀y ((y ≠ x) → ¬L(y))

Express: "Every adult is married to someone at the party."M(x, y): x is married to y. A(x): x is an adult.

∀x ∃y(A(x) → M(x, y))

Express: "Every adult is married to exactly one adult"M(x, y): x is married to y. A(x): x is an adult.

∀x ∃y ∀z ((A(x) → M(x, y)) ∧ (z≠y → ¬M(x,z))

Express: There is no smallest number

¬∃x ∀y (x <= y)

Express: Every number besides 0 has a multiplicative inverse

∀x ∃y (x ≠ 0 → xy = 1)

Express: Exactly one new employee missed the deadlineP(x, y): x knows y's phone number. D(x): x missed the deadline.N(x): x is a new employee.

∃x ∀y (N(x) ∧ D(x) ∧ (y ≠ x) ∧ (N(y) → ¬D(y)))

Express: Everyone besides Sam has taken at least two different math classes.The predicate T(x, y) indicates that student x has taken class y.

∀x ∃y ∃z ((x≠Sam) → ((y≠z) ∧ T(x,y) ∧ T(x,z))

Express: Sam has taken exactly two math classes.The predicate T(x, y) indicates that student x has taken class y.

∃y ∃z ∀w ( (z≠y) ∧ T(Sam, y) ∧ T(Sam, z) ∧ ((w≠y ∧ w≠z) → ¬T(Sam, w)))

Write the negation of the logical expression so that all negations immediately precede predicates:∃x ∃y P(x, y) ∧ ∀x ∀y Q(x, y)

∀x ∀y ¬P(x, y) v ∃x ∃y ¬Q(x,y)

Convert to decimal representation:(10011011) base 2

155

What are the first 9 numbers in Base 2?

0, 1, 10, 11, 100, 101, 110, 111, 1000

First 16 numbers in base 16

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f

Count to 13 to base 5

1, 2, 3, 4, 10, 11, 12, 13, 14, 20, 21, 22, 23

Count to 13 in base 8

1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15

Convert to decimal representation:(456) base 7

237

Convert to decimal representation:(38A) base 16

906

Convert to decimal representation:(2214) base 5

309

Convert to binary representation:(69) base 10

(1000101) base 2

Convert to binary representation:(485) base 10

(111100101) base 2

Convert to base 16:(708) base 10

(2C4) base 16

7566 (base 8) + 4515 (base 8) =

(14303) base 8

101100112 (base 2) + 11012 (base 2) =

(11000000) base 2

7A66 (base 16) + 45C5 (base 16) =

(C02B) base 16

3022 (base 5) - 2433 (base 5) =

(34) base 5

Convert to 8-bits two's complement representation:(124) base 10

(01111100) 8-bit two's complement

Convert to 8-bits two's complement representation:(-124) base 10

(10000100) 8-bits two's complement

Convert to 8-bits two's complement representation:(109) base 10

(01101101) 8-bits two's complement

Convert to 8-bits two's complement representation:(-79) base 10

(10110001) 8-bits two's complement

Convert the 8-bit two's complement to its decimal representation:(00011110)

30

Convert the 8-bit two's complement to its decimal representation:(11100110)

-26

Convert the 8-bit two's complement to its decimal representation:(00101101)

45

Convert the 8-bit two's complement to its decimal representation:(10011110)

-98

An argument is valid if the conclusion is _____ whenever the hypotheses are all ______, otherwise the argument is invalid.

true, true

Two arguments are considered to be ________ if the hypotheses appear in a different order.

the same

An argument can be shown to be invalid by showing an assignment of truth values to its variables that makes all the hypotheses ____ and the conclusion _____.

True, False

In a logical proof, if the proposition in a step is a hypothesis, the justification is ________

hypothesis

In a logical proof, the proposition in the last step in the proof must be the ___________ of the argument being proven.

conclusion

In order to apply the rules of inference to quantified expressions, such as ∀x ¬(P(x) ∧ Q(x)), we need to ____________________ by plugging in a value from the domain to replace the variable x.

remove the quantifier

An ________ element of a domain has no special properties other than those shared by all the elements of the domain.

arbitrary

A __________ element of the domain may have properties that are not shared by all the elements of the domain.

particular

If the element is defined in a hypothesis, it is always a _________ element and the definition of that element in the proof is labeled "Hypothesis".

particular

f an element is introduced for the first time in the proof, the definition is labeled _____________ and must specify whether the element is arbitrary or particular.

Element Definition

The rules existential instantiation and universal instantiation replace a __________ with an ________________________.

quantified variable; element of the domain

The rules existential generalization and universal generalization replace an ___________________ with a ___________________.

element of the domain; quantified variable

The proof of a theorem may make use of ________, which are statements assumed to be true.

axioms

How is a direct proof expressed?

p → cp is a proposition that is a conjunction of all the hypotheses and c is the conclusion.

In a _________ of a conditional statement, the hypothesis p is assumed to be true and the conclusion c is proven as a direct result of the assumption.

direct proof

A proof by contrapositive proves a conditional theorem of the form p → c by showing that the contrapositive _______ is true.

¬c → ¬p

what can an even integer be expressed as?

2k

what can an odd integer be expressed as?

2k + 1

A proof by _________ starts by assuming that the theorem is false and then shows that some logical inconsistency arises as a result of this assumption.

contradiction

Unlike direct proofs and proofs by contrapositive, a proof by contradiction can be used to prove theorems that are not _______

conditional statements

A __________ of a universal statement such as ∀x P(x) breaks the domain for the variable x into different classes and gives a different proof for each class.

proof by cases

Give an example of roster notation of set A with the elements 2, 4, 6, and 10

A = {2, 4, 6, 10}

The symbol ∈ is used to indicate that ___________

an element is in a set

The symbol ∉ indicates that ________________

an element is not in a set

The set with no elements is called the ________ and is denoted by the symbol ∅

empty set

For any element a, a ∉ ∅ is _______

TRUE

The cardinality of a finite set A, denoted by _____, is the number of elements in A.

|A|

The cardinality of the empty set |∅| is _________

zero

N is the set of _________, which includes ______________

natural numbers; all integers greater than or equal to zero

Z is the set of _______.

all integers (negative and positive)

Q is the set of __________, which includes _________________

rational numbers; all real numbers that can be expressed as a/b, where a and b are integers and b does not equal 0

R is the set of

real numbers

A = { x ∈ S : P(x) } is an example of what kind of notation?

set builder notation

If every element in A is also an element of B, then A is ______

a subset of B

If A ⊆ B and there is an element of B that is not an element of A (i.e., A ≠ B), then A is a ________ of B

proper subset

T/F: The empty set ∅ is the same as { ∅ }.

FALSE

What is the cardinality of { ∅ }

one

Since |A| = 3, the cardinality of the power set of A is ______?

2^3 = 8

T/F: ∅ ⊆ X for any X

TRUE

T/F: The empty set is a subset of every set

TRUE

The intersection of A and B : A ∩ B

the set of all elements that are elements of BOTH A and B

the union of A and B: A ∪ B

the set of all elements that are elements of A OR B

the difference between A and B: A - B

the set of elements that are in A but NOT in B

the symmetric difference between A and B: A ⊕ B

the set of elements that are a member of one of A and B, but not both

the complement of set A: __ A

the set of all elements in U that are not elements of A

An ordered pair of items is written _______

(x, y)

The use of parentheses ( ) for an ordered pair indicates that the order of entries is ________, unlike sets which use curly braces { }, indicating that the order in which the elements are listed ________.

significant; does not matter

The Cartesian product of A and B: A x B

the set of all ordered pairs in which the first entry is in A and the second entry is in B

|A x B| = ________?

|A| * |B|

The Cartesian product of a set A with itself can be denoted _____?

A^k

if A = {x, y}, what is the set A^2 ??

{xx, xy, yy, yx}

The empty string is the unique string whose length is __ and is usually denoted by the symbol λ

0

{0, 1}^0 = _____ ?

{λ}

f: X → Y: x is called_____, y is called _____

the domain, the target

For function f: X → Y, an element y is in the ______ of f if and only if there is an x ∈ X such that (x, y) ∈ f.

range

if f maps different elements in X to different elements in Y, a function is ______

one-to-one

if the range of f is equal to the target Y, a function is _______

onto

Let X = { u, v, w, x }. Define a function g: X → X to be: g = { (u, v), (v, w), (w, x), (x, u) }. What is g-1(x)?

w

f: R → R, where f(x) = -x + 3. What is f-1

f^-1(x) = -x + 3

If x is a real number, then |x| is the _______ of x. If A is a finite set, then |A| refers to the _______ of the set A.

absolute value;cardinality

What is (f ο f-1)(17) ?

17

Give an example of a function from the set of integers to the set of positive integers that is : one-to-one but not onto

f(n) { n^2 n <= 0 {n^2 + 1 n > 0

Give an example of a function from the set of integers to the set of positive integers that is : onto but not one to one

f(n) = |n| + 1

Give an example of a function from the set of integers to the set of positive integers that is : one-to-one and onto

f(n) {2 * |n| n < 0 {2*n + 1 n >= 0

Give an example of a function from the set of integers to the set of positive integers that is : neither one-to-one or onto

f(n) = 1

When is a conditional q→p ?

q if pq is a necessary for p