Discrete test 1 study Flashcards

1
Q

conjunction of p and q

A

p ^ q p and q

true when both p and q are true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

disjunction of p and q

A

p v q, p or q

true when at least p or q is true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

exclusive or of p and q

A

true when p and q are different signals

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

if p then q

A

p -> q,

true in all cases except true implies false.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

bi-conditional statement of p and q

A

pq, p if and only if q.

true when p and q have the same value. true or false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Converse of p -> q

A

q -> p

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

contrapositive of p -> q

A

~q -> ~p

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

inverse of p -> q

A

~p -> ~q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

the converse is equivalent to

A

the inverse

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

the original is equivalent to the

A

contrapositive

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

how to tell if something is logically equivalent in 2 ways

A

use truth tables and match columns or use the table of logical equivalences to get to what you need

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

tautology

A

all is true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

contradiciton

A

all is false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

contingancy

A

neither always true nor always false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Axpx

A

for all x in px

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Expx

A

there exists an x that satisfies px

17
Q

E!xpx

A

there exists exactly one x that satisfys p(x)

18
Q

how to negate A and E

A

flip them and move it in

19
Q

even

A

The integer n is even if there exists an integer k such that n = 2k.

20
Q

odd

A

The integer n is odd if there exists an integer k such that n = 2k +1.

21
Q

rational number

A

A rational number p has the form 𝑎
𝑏
, where a and b are
integers and b ≠0.

22
Q

Direct proof

A

To prove 𝑝 → 𝑞 using a direct proof, you assume

that p is true and show that q must also be true

23
Q

Indirect proof

A

(proof by contraposition). To prove 𝑝 → 𝑞 using an

indirect proof, you prove ¬𝑞 → ¬𝑝 (the contrapositive) directly.

24
Q

Proof by contradiction

A

To prove that a proposition p is true, we
assume that it is false and attain a logical contradiction, such as
𝑟 ⋀ ¬𝑟. Then it must be the case that p was true

25
Q

Proof of 𝒑 ↔ 𝒒.contradiction

A

To prove 𝑝 ↔ 𝑞, we may prove both 𝑝 → 𝑞

and 𝑞 → 𝑝

26
Q

Vacuous proof.

A

We know that when p is false, 𝑝 → 𝑞 is true. For
example, if P(n) (n is an integer) is the statement “if n is odd, then
n
2
is odd,” then the proposition P(2) is vacuously true since ‘2 is
odd’ is false.

27
Q

Trivial proof

A

We know that when q is true, 𝑝 → 𝑞 is true. For
example, if P(n) (n is an integer) is the statement “if n is even, then
n + 1 > n,” then it P(n) is trivially true since n + 1 > n is true for all
integers, regardless of whether or not n is even.

28
Q

Proof by cases.

A

. To prove (𝑝1⋁𝑝2⋁ … ⋁𝑝𝑛) → 𝑞, we show that

𝑝𝑖 → 𝑞 for i = 1, 2, …, n.

29
Q

Existence Proofs

A

To prove ∃𝑥𝑃(𝑥) we may either construct an x
for which P(x) is true (constructive existence proof), or we may
demonstrate that P(x) is true for at least one x without actually
finding a specific x (nonconstructive existence proof).

30
Q

Unique Existence Proof

A

To prove ∃! 𝑥𝑃(𝑥) we must show:
∃𝑥(𝑃(𝑥) ∧ ∀𝑦(𝑃(𝑦) → 𝑦 = 𝑥)) [Existence and Uniqueness]
Outline: We can use either a constructive or nonconstructive
existence proof to existence To prove uniqueness, suppose P(x)
and P(y) are both true and show that we must have x = y.