Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS 225 - Discrete Structures In Computer Science > Module 1 > Flashcards

Module 1 Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

What is a proposition?

A

It is a declarative statement that must be EITHER true or false, not both.

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

What is the negation operator and what does it do?

A

~, it turns a statement into it’s inverse. Ex: p = Tom is human. ~p = Tom is not human.

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

What is the conjunction operator and what does it do?

A

And (^). p^q is true if, and only if, p and q are both true.

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

What is the disjunction operator and what does it do?

A

Or, V, pVq is true if, and only if, p or q are true.

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

What is the implication operator and what does it do?

A

Arrow, p implies q. If p is true then q must be true. If p is false then q could be either true or false.

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

What does p but q mean?

A

p and q, p^q

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

What does neither p nor q mean?

A

Not p and not q, ~p^~q

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

What is XOR derived from?

A

P or q and not p and q, (pVq) ^ ~(p^q)

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

What is the definition of a logical equivalence?

A

When two statements have logically equivalent forms when identical component statement variables are used to replace identical component statements.

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

What is De Morgan’s law of conjunction?

A

The negation of the conjunction of two statements is logically equivalent to the disjunction of their negations.

~(p^q) = ~p V ~q

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

What is De Morgan’s law of disjunction?

A

The negation of the disjunction of two statements is logically equivalent to the conjunction of their negations.

~(pVq) = ~p ^ ~q

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

What is a tautology?

A

A statement form that is always true regardless of the truth values of the individual statements substituted for its statement variables.

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

What is a contradiction?

A

A statement form that is always false regardless of the truth values of the individual statements substituted for its statement variables.

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

What is the commutative law of conjunction?

A

p^q = q^p

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

What is the commutative law of disjunction?

A

pVq = qVp

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

What is the associative law of conjunction?

A

(p^q)^r = p^(q^r)

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

What is the associative law of disjunction?

A

(pVq)Vr = pV(qVr)

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

What is the distributive law of conjunction?

A

p^(qVr) = (p^q)V(p^r)

19
Q

What is the distributive law of disjunction?

A

pV(q^r) = (pVq)^(pVr)

20
Q

What is the identity law of conjunction?

A

p^t = p

21
Q

What is identity law of disjunction?

A

pVc = p

22
Q

What is the negation law of disjunction?

A

pV~p = t

23
Q

What is the negation law of conjunction?

A

pVc = p

24
Q

What is the definition of the double negative law?

A

~(~p) = p

25
Q

What is the definition of the idempotent law of conjunction?

A

p^p = p

26
Q

What is the idempotent law of disjunction?

A

pVp = p

27
Q

What is the universal bound law of disjunction?

A

pVt = t

28
Q

What is the universal bound law of conjunction?

A

p^c = c

29
Q

What is the absorption law of conjunction?

A

pV(p^q) = p

30
Q

What is the absorption law of disjunction?

A

p^(pVq) = p

31
Q

What is the negation of t?

A

c

32
Q

What is the negation of c?

A

t

33
Q

What is the definition of a conditional statement?

A

If p and q are statement variables, the conditional of q by p is “if p then q” or “p implies q.”

34
Q

What are p and q called in a conditional statement?

A 
p = the hypothesis (or antecedent)
q = the conclusion (or consequent)
35
Q

What does it mean to be vacuously true or true by default?

A

When a conditional statement is true by virtue of the fact that its hypothesis is false

36
Q

What is the negation of a conditional statement?

A

If p then q is logically equivalent to p and not q

37
Q

What is the contrapositive of a conditional statement?

A

If not q then not p

38
Q

What is the converse of a conditional statement?

A

If q then p

39
Q

What is the inverse of a conditional statement?

A

If not p then not q

40
Q

What is logically equivalent to a normal conditional statement?

A

The contrapositive, or, not p or q

41
Q

What is logically equivalent to the converse of a conditional statement?

A

The inverse

42
Q

What is a biconditional statement?

A

It means p if, and only if, q. True when both p and q are true or they are both false.

43
Q

What is a sufficient condition?

A

If p then q

44
Q

What is a necessary condition?

A

If not p then not q, or, if q then p

CS 225 - Discrete Structures In Computer Science (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions