Discrete Mathematics Flashcards
1
Q
definition: argument
A
finite sequence of statements followed by a single statement, the conclusion
2
Q
definition: premise
A
sequence of statements
3
Q
definition: conclusion
A
follows premise
normally begins with a word or phrase like: therefore, so, thus, hence, it follows that
4
Q
definition: valid (argument)
A
if upon assuming that the premises are true it follows that the conclusion is true
5
Q
Latin: modus pones
A
“mode that affirms”
6
Q
Latin: non sequitur
A
“it does not follow”
7
Q
Roots: calculus
A
- a single small bead that was used by the Romans to perform counting tasks*
plural: (calculi)
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
9
Q
definition: propositional calculus
A
***
10
Q
definition: proposition
A
a sentence that is either true or false
11
Q
definition: connectives
A
combining operations
- ¬
- “not,” negation
- logand
- “and,” conjunction
- logor
- “or,” disjunction
- →
- “conditional,” implication
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”
13
Q
definition: antecedent
A
***
14
Q
definition: consequent
A
***
15
Q
Fill out a basic two variable truth table for: A → B
A
A → B
t
t
f
t
16
Q
What is the value of:
true → false?
A
false
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
18
Q
what are the the truth symbols?
A
- T (or True)
- F (or False)
19
Q
what are the connectives?
A
negation, conjunction, disjunction, implication
“not,” “and,” “or,” and “conditional”
20
Q
what are propositional variables?
A
uppercase letteres (for example: A, B, P, Q, etc.)
21
Q
what are the punctuation symbols for propositional calculus?
A
- (
- ,
- )
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)
23
Q
definition: syntax tree
A
displays hierarchy of the connectives
24
Q
define: tautology
A
25
define: **contradition**
26
define: **contingency**
TT \>= (1 true) && TT \>= (1 false)
27
Name two fundamental tautologies.
* T (or True)
* P ∨ ¬P
28
Name two fundamental contradicitions.
* F (or False)
* P logand nt P
29
Name a fundamental contingency.
P
30
definition: **logical equivalence**
* 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
31
# negation
**¬¬A ≡**
A
32
# disjunction
A ∨ True ≡
True
33
# disjunction
A ∨ False ≡
A
34
# disjunction
A ∨ A ≡
A
35
# disjunction
A ∨ ¬A ≡
True
36
# conjunction
A ∧ True ≡
A
37
# conjunction
A ∧ False ≡
False
38
# conjunction
A ∧ A ≡
A
39
# conjunction
A ∧ ¬A ≡
False
40
# implication
A → True ≡
True
41
# implication
A → False ≡
¬A
42
# implication
True → A ≡
A
43
# implication
False → A ≡
True
44
# implication
A → A ≡
True
45
# absorption
A ∧ (A ∨ B) ≡
A
46
# absorption
A ∨ (A ∧ B) ≡
A
47
# absorption
A ∧ (¬A ∨ B) ≡
A ∧ B
48
# absorption
A ∨ (¬A ∧ B) ≡
A ∨ B
49
# de morgans
¬ (A ∧ B) ≡
¬A ∨ ¬B
50
# de morgans
¬ (A ∨ B) ≡
¬A ∧ ¬B
51
A → B ≡
| (conversion)
¬A ∨ B
52
¬ (A → B) ≡
| (conversion)
A ∧ ¬B
53
A → B ≡
| (conversion II)
A ∧ ¬B → False
54
A ∧ (B ∨ C) ≡
| (conversion)
(A ∧ B) ∨ (A ∧ C)
55
A ∨ (B ∧ C) ≡
| (conversion)
(A ∨ B) ∧ (A ∨ C)
56
A ≡ B *iff* ____ ∧ ____ is a _________ .
A ≡ B *iff* ____ and ____ are _________ .
* (A → B)
* (B → A)
* tautology
* A → B
* B → A
* tautologies
57
Give an example of the transitive property.
If W ≡ X
and X ≡ Y,
then W≡ Y.
58
definition: replacement rule
"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
definition: **Quine's method**
* 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
**Substitution Property 1**
W is a tautology iff W(A/True) and W(A/False) are tautologies.
61
**Substitution Property 2**
W is a contradiction iff W(A/True) and W(A/False) are contradictions.
62
How do you check the ***meaning*** of a wff (or, simply, W)?
Use Quine's Method to substitute variables with true/false values.
63
definition: **truth function**
* 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
65
definition: **literal**
a propositional variable or its negation
66
definition: **fundamental conjunction**
etither a literal or a conjunction of 2+ literals
67
definition: **disjunctive normal form** (DNF)
either a fundamental conjunction or a disjunction of two or more fundamental conjunctions
note: every wff is equivalent to a DNF
68
definition: **full disjunctive normal form**
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
definition: **fundamental disjunction**
either a literal or the disjunction of two or more literals
70
definition: **conjunctive normal form (CNF)**
either a fundamental disjunction or a conjunction of two or more fundamental disjunctions
71
definition: **full conjunctive normal form**
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
How do you add a variable to a conjunction?
∧ (R ∨ ¬R)
73
How do you add a variable to a disjunction?
∨ (R ⋀ ¬R)
74
definition: **adequate** (functionally complete)
a set of connectives is adequate if every truth function is equivalent to a wff defined in terms of the connectives
75
Name all adequate set of connectives.
{¬, ⋀, ∨}
{¬, ∨}
{¬, ⋀}
{¬, →}
{NAND}
{NOR}
76
Truth table for NAND:
T, T, T, F
77
Truth table for NOR:
T, F, F, F
78
definition: NAND
definition: NOR
NAND: "negation of AND"
NOR: "negation of OR"
79
definitions:
(1) **natural deduction** (formal proof approach)
(2) **axiomatic** (formal proof approach)
(3) **axiom**
(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
definition: **proof** (derivation)
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
definition: **proof (inference) rules**
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
proof rule: **conjunction** (conj)
83
proof rule: **simplification** (simp)
84
proof rule: additon (add)
85
proof rule: **disjunctive syllogism** (ds)
86
proof rule: **modus ponens** (mp)
87
proof rule: **conditional proof** (cp)
88
proof rule: **double negation** (dn)
89
proof rule: **contradition** (contr)
90
proof rule: indirect proof (ip)
91
definition: **subproof**
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
definition: **proof by contradiction** (**reductio ad absurdum**)
* 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
derived rules: **modus tollens** (mt)
Latin: "mode that denies"
94
derived rules: **proof by cases** (cases)
95
derived rule: **hypothetical syllogism** (hs)
96
derived rule: **constructive dilemma** (cd)
97
definition: **theorem**
the last wff in a proof for which all premises have been discharged
98
definition: **sound proof system** (propositional calculus)
every theorem is a tautology
99
definition: **complete proof system** (propositional calculus)
every tautology is a theorem
