Discrete Mathematics Flashcards
definition: argument
finite sequence of statements followed by a single statement, the conclusion
definition: premise
sequence of statements
definition: conclusion
follows premise
normally begins with a word or phrase like: therefore, so, thus, hence, it follows that
definition: valid (argument)
if upon assuming that the premises are true it follows that the conclusion is true
Latin: modus pones
“mode that affirms”
Latin: non sequitur
“it does not follow”
Roots: calculus
- a single small bead that was used by the Romans to perform counting tasks*
plural: (calculi)
definition: calculus
- 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
definition: propositional calculus
***
definition: proposition
a sentence that is either true or false
definition: connectives
combining operations
- ¬
- “not,” negation
- logand
- “and,” conjunction
- logor
- “or,” disjunction
- →
- “conditional,” implication
How would you say P → Q?
- “if P then Q”
- “P implies Q”
- “Q if P”
- “P is a sufficient condition for Q”
- “Q is a necessary condition for P”
definition: antecedent
***
definition: consequent
***
Fill out a basic two variable truth table for: A → B
A → B
t
t
f
t
What is the value of:
true → false?
false
definition: well-formed formula (wff)
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
what are the the truth symbols?
- T (or True)
- F (or False)
what are the connectives?
negation, conjunction, disjunction, implication
“not,” “and,” “or,” and “conditional”
what are propositional variables?
uppercase letteres (for example: A, B, P, Q, etc.)
what are the punctuation symbols for propositional calculus?
- (
- ,
- )
In which order do the connectives have precedence?
not
and
or
conditional
NOTE: and, or, and the conditional are left associative (evaluated L to R)
definition: syntax tree
displays hierarchy of the connectives
define: tautology
define: contradition
define: contingency
TT >= (1 true) && TT >= (1 false)
Name two fundamental tautologies.
- T (or True)
- P ∨ ¬P
Name two fundamental contradicitions.
- F (or False)
- P logand nt P
Name a fundamental contingency.
P
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
negation
¬¬A ≡
A
disjunction
A ∨ True ≡
True
disjunction
A ∨ False ≡
A
disjunction
A ∨ A ≡
A
disjunction
A ∨ ¬A ≡
True
conjunction
A ∧ True ≡
A
conjunction
A ∧ False ≡
False
conjunction
A ∧ A ≡
A
conjunction
A ∧ ¬A ≡
False
implication
A → True ≡
True
implication
A → False ≡
¬A
implication
True → A ≡
A
implication
False → A ≡
True
implication
A → A ≡
True
absorption
A ∧ (A ∨ B) ≡
A
absorption
A ∨ (A ∧ B) ≡
A
absorption
A ∧ (¬A ∨ B) ≡
A ∧ B
absorption
A ∨ (¬A ∧ B) ≡
A ∨ B
de morgans
¬ (A ∧ B) ≡
¬A ∨ ¬B
de morgans
¬ (A ∨ B) ≡
¬A ∧ ¬B
A → B ≡
(conversion)
¬A ∨ B
¬ (A → B) ≡
(conversion)
A ∧ ¬B
A → B ≡
(conversion II)
A ∧ ¬B → False
A ∧ (B ∨ C) ≡
(conversion)
(A ∧ B) ∨ (A ∧ C)
A ∨ (B ∧ C) ≡
(conversion)
(A ∨ B) ∧ (A ∨ C)
A ≡ B iff ____ ∧ ____ is a _________ .
A ≡ B iff ____ and ____ are _________ .
- (A → B)
- (B → A)
- tautology
- A → B
- B → A
- tautologies
Give an example of the transitive property.
If W ≡ X
and X ≡ Y,
then W≡ Y.
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.
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.
Substitution Property 1
W is a tautology iff W(A/True) and W(A/False) are tautologies.
Substitution Property 2
W is a contradiction iff W(A/True) and W(A/False) are contradictions.
How do you check the meaning of a wff (or, simply, W)?
Use Quine’s Method to substitute variables with true/false values.
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
definition: literal
a propositional variable or its negation
definition: fundamental conjunction
etither a literal or a conjunction of 2+ literals
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
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
definition: fundamental disjunction
either a literal or the disjunction of two or more literals
definition: conjunctive normal form (CNF)
either a fundamental disjunction or a conjunction of two or more fundamental disjunctions
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.
How do you add a variable to a conjunction?
∧ (R ∨ ¬R)
How do you add a variable to a disjunction?
∨ (R ⋀ ¬R)
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
Name all adequate set of connectives.
{¬, ⋀, ∨}
{¬, ∨}
{¬, ⋀}
{¬, →}
{NAND}
{NOR}
Truth table for NAND:
T, T, T, F
Truth table for NOR:
T, F, F, F
definition: NAND
definition: NOR
NAND: “negation of AND”
NOR: “negation of OR”
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
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
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
proof rule: conjunction (conj)
proof rule: simplification (simp)
proof rule: additon (add)
proof rule: disjunctive syllogism (ds)
proof rule: modus ponens (mp)
proof rule: conditional proof (cp)
proof rule: double negation (dn)
proof rule: contradition (contr)
proof rule: indirect proof (ip)
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
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
derived rules: modus tollens (mt)
Latin: “mode that denies”
derived rules: proof by cases (cases)
derived rule: hypothetical syllogism (hs)
derived rule: constructive dilemma (cd)
definition: theorem
the last wff in a proof for which all premises have been discharged
definition: sound proof system (propositional calculus)
every theorem is a tautology
definition: complete proof system (propositional calculus)
every tautology is a theorem
