[DM] Lecture 1

Question 1

The study of mathematical structures that are fundamentally discrete rather than continuous.

Answer 1

Discrete Math

Question 2

Those which are separated from (not connected to/distinct from) each other.

Answer 2

Discrete Objects

Question 3

a declarative statement that’s either TRUE or FALSE (but not both).

Answer 3

Proposition

Question 4

corresponds to English “and.”

Answer 4

Conjunction (∧)

Question 5

corresponds to English “or.”

Answer 5

Disjunction (V)

Question 6

It means either p or q, but not both

Answer 6

Exclusive-or (⊕)

Question 7

the hypothesis (or antecedent).

Answer 7

p

Question 8

the conclusion (or consequent).

Answer 8

q

Question 9

corresponds to English “if p then q,” or “p implies q”, “p is sufficient for q”, “q when p”,”p only if q”, “a necessary condition for p is q”

Answer 9

Implication

Question 10

it means “required”

Answer 10

Necessary

Question 11

it means “enough”

Answer 11

Sufficient

Question 12

corresponds to English “p if and only if q,”.

Answer 12

Double Implication

Question 13

p → q and ¬q → ¬p

Answer 13

Contrapositive

Question 14

p → q and q → p

Answer 14

Converse

Question 15

p → q and ¬p → ¬q

Answer 15

Inverse

Question 16

a proposition that’s always TRUE.

Answer 16

Tautology

Question 17

a proposition that’s always FALSE.

Answer 17

Contradiction

Question 18

The statement is true if P(x) is true for every x in D, and the statement is false if P(x) is false for at least one x in D.

Answer 18

Universally Quantified Statement

Question 19

The statement is true if P(x) is true for at least one x in D, and the statement is false if P(x) is false for all values in D.

Answer 19

Existentially Quantified Statement

Question 20

x in P(x) is called a ____

Answer 20

Free Variable

Question 21

-set of two or more propositions related to each other in such a way that all but one of them (the premises) are supposed to provide support for the remaining one (the conclusion)

Answer 21

Argument

Question 22

-transition from premises to conclusion upon which the argument relies.

Answer 22

Inference

Question 23

All but final proposition in the argument

Answer 23

Premise

Question 24

final proposition

Answer 24

Conclusion

Question 25

if the truth of all of its premises implies that the conclusion is true

Answer 25

Valid

Question 26

Steps to test an argument for validity

Answer 26

1) Identify the premises and the conclusion of the argument.
2) Construct a truth table including the premises and the conclusion.
3) Find rows in which all premises are true.
4) In each row of step 3, if the conclusion is true, then the argument is valid, otherwise the argument is invalid

Question 27

the basis of the rule of inference called modus ponens , or the law of detachment.

Answer 27

(p∧(p → q))→ q

Question 28

Modus Tollens

Answer 28

(-q ∧ (p → q)) → -p

Question 29

Hypothetical Syllogism

Answer 29

((p → q) ∧ (q → r)) → (p → r)

Question 30

Disjunctive Syllogism

Answer 30

((p v q) ∧ -p) → q

Question 31

Addition

Answer 31

p → (p v q)

Question 32

Simplification

Answer 32

(p ∧ q) → p

Question 33

conjunction

Answer 33

((p) ∧ (q)) → (p ∧ q)

Question 34

Resolution

Answer 34

((p v q) ∧ (-p v r)) → (q v r)

Question 35

rule of inference used to conclude that P(c) is true, where c is a particular member of the domain, given the premise ∀xP(x)

Answer 35

Universal Instantiation

Question 36

rule of inference that states ∀xP(x) is true, given that P(c) is true for all elements c in the domain

Answer 36

Universal Generalization

Question 37

Used when ∀xP(x) is true by taking an arbitrary element c from the domain and showing that P(c) is true

Answer 37

Universal Generalization

Question 38

Rule of inference for Universal instantiation

Answer 38

∀xP(x) → P(c)

Question 39

rule that allows us to conclude that there is an element c in the domain for which P(c) is true if we know that ∃xP(x) is true

Answer 39

Existential Instantiation

Question 40

rule of inference used to conclude that ∃xP(x) is true when a particular element c with P(c) true is known

Answer 40

Existential Generalization

Question 41

Rule of inference for Universal Generalization

Answer 41

P(c) for an arbitrary c → ∀xP(x)

Question 42

Rule of inference for Existential Generalization

Answer 42

P(c) for some element c → ∃xP(x)

Question 43

Rule of inference for Existential Instantiation

Answer 43

∃xP(x) → P(c) for some element c

Question 44

consists of axioms, definitions and undefined terms

Answer 44

Mathematical System

Question 45

a proposition that has been proved to be true

Answer 45

Theorem

Question 46

theorem that is usually not too interesting in its own right but is useful in proving another theorem.

Answer 46

Lemma

Question 47

theorem that follows quickly from another theorem

Answer 47

Corollary

Question 48

an argument that establishes the truth of a theorem

Answer 48

Proof

Question 49

What are the 3 methods of proving

Answer 49

Direct Proof
Proof by Contraposition
Proof by Contradiction

Question 50

Steps in Direct Proof

Answer 50

1. Assume p is true
2. use axioms, definitions, theorems, etc. to prove q is also true

Question 51

Steps in Proof by Contraposition

Answer 51

1. Make the statement -q → -p
2. Assume -q is true
3. use axioms, definitions, theorems, etc. to prove -p is also true

Question 52

Steps in Proof by Contradiction

Answer 52

For 1 proposition only
- assume -p is true
- find a contradiction that shows -p is false, so that p is true

For implication p → q
- Assume p and -q are true
- Find a contradiction that shows p → q or -q → -p