Brainscape's Knowledge GenomeTM

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


See full index

Computer Science > Discrete Mathematics > Flashcards

Discrete Mathematics Flashcards

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

definition: argument

A

finite sequence of statements followed by a single statement, the conclusion

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

definition: premise

A

sequence of statements

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

definition: conclusion

A

follows premise

normally begins with a word or phrase like: therefore, so, thus, hence, it follows that

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

definition: valid (argument)

A

if upon assuming that the premises are true it follows that the conclusion is true

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

Latin: modus pones

A

“mode that affirms”

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

Latin: non sequitur

A

“it does not follow”

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

Roots: calculus

A
  • a single small bead that was used by the Romans to perform counting tasks*
    plural: (calculi)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

definition: calculus

A
  • a language
  • made up of expressions
  • has definite rules for forming expressions
  • values (meanings) are associated with the expressions
  • definite rules to transform one expression into another having the same value
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

definition: propositional calculus

A

***

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

definition: proposition

A

a sentence that is either true or false

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

definition: connectives

A

combining operations

  • ¬
    • “not,” negation
  • logand
    • “and,” conjunction
  • logor
    • “or,” disjunction
  • →
    • “conditional,” implication
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

How would you say P → Q?

A
  • “if P then Q”
  • “P implies Q”
  • “Q if P”
  • “P is a sufficient condition for Q”
  • “Q is a necessary condition for P”
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

definition: antecedent

A

***

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

definition: consequent

A

***

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

Fill out a basic two variable truth table for: A → B

A

A → B

t

t

f

t

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

What is the value of:

true → false?

A

false

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

definition: well-formed formula (wff)

A

a grammatically correct expression

  • a wff is either…
    • a truth symbol
    • a propositional variable
    • the negation of a wff
    • the conjunction of two wffs
    • the disjunction of two wffs
    • the implication of one wff from another
    • a wff surrounded by parentheses
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

what are the the truth symbols?

A
  • T (or True)
  • F (or False)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

what are the connectives?

A

negation, conjunction, disjunction, implication

“not,” “and,” “or,” and “conditional”

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

what are propositional variables?

A

uppercase letteres (for example: A, B, P, Q, etc.)

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

what are the punctuation symbols for propositional calculus?

A
  • (
  • ,
  • )
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

In which order do the connectives have precedence?

A

not

and

or

conditional

NOTE: and, or, and the conditional are left associative (evaluated L to R)

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

definition: syntax tree

A

displays hierarchy of the connectives

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

define: tautology

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

define: contradition

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

define: contingency

A

TT >= (1 true) && TT >= (1 false)

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

Name two fundamental tautologies.

A
  • T (or True)
  • P ∨ ¬P
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Name two fundamental contradicitions.

A
  • F (or False)
  • P logand nt P
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Name a fundamental contingency.

A

P

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

definition: logical equivalence

A
  • two wffs A and B are logically equivalent (or equivalent) if they have the same truth value for each assignment of truth values to the set of all propositional variables occurring in the wffs*
    example: A ≡ B
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

negation

¬¬A ≡

A

A

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

disjunction

A ∨ True ≡

A

True

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

disjunction

A ∨ False ≡

A

A

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

disjunction

A ∨ A ≡

A

A

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

disjunction

A ∨ ¬A ≡

A

True

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

conjunction

A ∧ True ≡

A

A

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

conjunction

A ∧ False ≡

A

False

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

conjunction

A ∧ A ≡

A

A

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

conjunction

A ∧ ¬A ≡

A

False

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

implication

A → True ≡

A

True

41
Q

implication

A → False ≡

A

¬A

42
Q

implication

True → A ≡

A

A

43
Q

implication

False → A ≡

A

True

44
Q

implication

A → A ≡

A

True

45
Q

absorption

A ∧ (A ∨ B) ≡

A

A

46
Q

absorption

A ∨ (A ∧ B) ≡

A

A

47
Q

absorption

A ∧ (¬A ∨ B) ≡

A

A ∧ B

48
Q

absorption

A ∨ (¬A ∧ B) ≡

A

A ∨ B

49
Q

de morgans

¬ (A ∧ B) ≡

A

¬A ∨ ¬B

50
Q

de morgans

¬ (A ∨ B) ≡

A

¬A ∧ ¬B

51
Q

A → B ≡

(conversion)

A

¬A ∨ B

52
Q

¬ (A → B) ≡

(conversion)

A

A ∧ ¬B

53
Q

A → B ≡

(conversion II)

A

A ∧ ¬B → False

54
Q

A ∧ (B ∨ C) ≡

(conversion)

A

(A ∧ B) ∨ (A ∧ C)

55
Q

A ∨ (B ∧ C) ≡

(conversion)

A

(A ∨ B) ∧ (A ∨ C)

56
Q

A ≡ B iff ____ ∧ ____ is a _________ .

A ≡ B iff ____ and ____ are _________ .

A
  • (A → B)
  • (B → A)
  • tautology
  • A → B
  • B → A
  • tautologies
57
Q

Give an example of the transitive property.

A

If W ≡ X

and X ≡ Y,

then W≡ Y.

58
Q

definition: replacement rule

A

“You can always replace equals for equals.”

  • If a wff W is changed
  • by replacing a subwff
    • (i.e., a wff that is part of W)
  • by an equivalent wff,
  • then the wff obtained in this way
  • is equivalent to W.
59
Q

definition: Quine’s method

A
  • If A is a variable in the wff W,
  • then the expression W(A/True)
  • denotes the wfff obtained from W
  • by replacing all occurrences of A by True.
  • Similarly, we define W(A/False)
  • to be the wff obtained from W
  • by replacing all occurrences of A by False.
60
Q

Substitution Property 1

A

W is a tautology iff W(A/True) and W(A/False) are tautologies.

61
Q

Substitution Property 2

A

W is a contradiction iff W(A/True) and W(A/False) are contradictions.

62
Q

How do you check the meaning of a wff (or, simply, W)?

A

Use Quine’s Method to substitute variables with true/false values.

63
Q

definition: truth function

A
  • a function with a finite number of arguments,
  • where the argument values and function values
  • are from the set {True, False}
  • every truth function is equivalen to a propositional wff defined in terms of the connectives ¬, ∧, and ∨.
  • also, any wff defines a truth function
64
Q
A
65
Q

definition: literal

A

a propositional variable or its negation

66
Q

definition: fundamental conjunction

A

etither a literal or a conjunction of 2+ literals

67
Q

definition: disjunctive normal form (DNF)

A

either a fundamental conjunction or a disjunction of two or more fundamental conjunctions

note: every wff is equivalent to a DNF

68
Q

definition: full disjunctive normal form

A

a DNF for W is called an FDNF if each fundamental conjunction has exactly n literals, one for each of the n variables appearing in W.

note: every wff that is not a contradiction is equivalent to a full DNF

69
Q

definition: fundamental disjunction

A

either a literal or the disjunction of two or more literals

70
Q

definition: conjunctive normal form (CNF)

A

either a fundamental disjunction or a conjunction of two or more fundamental disjunctions

71
Q

definition: full conjunctive normal form

A

a CNF for W is called an FCNF if each fundamental disjunction has exactly n literals, one for each of the n variables that appear in W.

note: every wff is equivalent to a CNF and every wff that is not a tautology is equivalent to a full CNF.

72
Q

How do you add a variable to a conjunction?

A

∧ (R ∨ ¬R)

73
Q

How do you add a variable to a disjunction?

A

∨ (R ⋀ ¬R)

74
Q

definition: adequate (functionally complete)

A

a set of connectives is adequate if every truth function is equivalent to a wff defined in terms of the connectives

75
Q

Name all adequate set of connectives.

A

{¬, ⋀, ∨}

{¬, ∨}

{¬, ⋀}

{¬, →}

{NAND}

{NOR}

76
Q

Truth table for NAND:

A

T, T, T, F

77
Q

Truth table for NOR:

A

T, F, F, F

78
Q

definition: NAND
definition: NOR

A

NAND: “negation of AND”

NOR: “negation of OR”

79
Q

definitions:

(1) natural deduction (formal proof approach)
(2) axiomatic (formal proof approach)
(3) axiom

A

(1) the rules reflect the informal way that we reason
(2) the premises for arguments are limited to a fixed set of wffs, called axioms, and where there is only one rule, modus ponens
(3) a fixed set of wffs

80
Q

definition: proof (derivation)

A

a finite sequence of wffs, where each wff is either a premise or the result of applying a rule to certain previous wffs in the sequence

81
Q

definition: proof (inference) rules

A

the rules applied in a proof ; gives a condition for which a new wff can be added to a proof

condition / wff

note: we say that the condtion of the rule infers the wff

82
Q

proof rule: conjunction (conj)

A
83
Q

proof rule: simplification (simp)

A
84
Q

proof rule: additon (add)

A
85
Q

proof rule: disjunctive syllogism (ds)

A
86
Q

proof rule: modus ponens (mp)

A
87
Q

proof rule: conditional proof (cp)

A
88
Q

proof rule: double negation (dn)

A
89
Q

proof rule: contradition (contr)

A
90
Q

proof rule: indirect proof (ip)

A
91
Q

definition: subproof

A

a proof that contains another proof

  • proves a statement that is needed for the proof to continue
  • a derivation that always starts with a new premise and always ends by applying CP or IP to the derivatoin
92
Q

definition: proof by contradiction (reductio ad absurdum)

A
  • assume that the statement to be proven is false and argue from there until a contradiction of some kind is reached
  • then conclude that the original statement is true
  • this is based on the folling simple equivalence for any wff W:
    • W ≡ ¬W → False
93
Q

derived rules: modus tollens (mt)

A

Latin: “mode that denies”

94
Q

derived rules: proof by cases (cases)

A
95
Q

derived rule: hypothetical syllogism (hs)

A
96
Q

derived rule: constructive dilemma (cd)

A
97
Q

definition: theorem

A

the last wff in a proof for which all premises have been discharged

98
Q

definition: sound proof system (propositional calculus)

A

every theorem is a tautology

99
Q

definition: complete proof system (propositional calculus)

A

every tautology is a theorem

Computer Science (4 decks)

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