Module 1 Flashcards Preview

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

Flashcards in Module 1 Deck (44):
1

What is a proposition?

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

2

What is the negation operator and what does it do?

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

3

What is the conjunction operator and what does it do?

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

4

What is the disjunction operator and what does it do?

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

5

What is the implication operator and what does it do?

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.

6

What does p but q mean?

p and q, p^q

7

What does neither p nor q mean?

Not p and not q, ~p^~q

8

What is XOR derived from?

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

9

What is the definition of a logical equivalence?

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

10

What is De Morgan’s law of conjunction?

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

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

11

What is De Morgan’s law of disjunction?

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

~(pVq) = ~p ^ ~q

12

What is a tautology?

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

13

What is a contradiction?

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

14

What is the commutative law of conjunction?

p^q = q^p

15

What is the commutative law of disjunction?

pVq = qVp

16

What is the associative law of conjunction?

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

17

What is the associative law of disjunction?

(pVq)Vr = pV(qVr)

18

What is the distributive law of conjunction?

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

19

What is the distributive law of disjunction?

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

20

What is the identity law of conjunction?

p^t = p

21

What is identity law of disjunction?

pVc = p

22

What is the negation law of disjunction?

pV~p = t

23

What is the negation law of conjunction?

pVc = p

24

What is the definition of the double negative law?

~(~p) = p

25

What is the definition of the idempotent law of conjunction?

p^p = p

26

What is the idempotent law of disjunction?

pVp = p

27

What is the universal bound law of disjunction?

pVt = t

28

What is the universal bound law of conjunction?

p^c = c

29

What is the absorption law of conjunction?

pV(p^q) = p

30

What is the absorption law of disjunction?

p^(pVq) = p

31

What is the negation of t?

c

32

What is the negation of c?

t

33

What is the definition of a conditional statement?

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

34

What are p and q called in a conditional statement?

p = the hypothesis (or antecedent)
q = the conclusion (or consequent)

35

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

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

36

What is the negation of a conditional statement?

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

37

What is the contrapositive of a conditional statement?

If not q then not p

38

What is the converse of a conditional statement?

If q then p

39

What is the inverse of a conditional statement?

If not p then not q

40

What is logically equivalent to a normal conditional statement?

The contrapositive, or, not p or q

41

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

The inverse

42

What is a biconditional statement?

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

43

What is a sufficient condition?

If p then q

44

What is a necessary condition?

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