Discrete Math and its Applications

connectives

logical operators used to form new propositions from two or more existing propositions

conjunction

"and"; true only when both propositions are true

disjunction

"or"; false only when both propositions are false

exclusive or

true only when exactly one of the propositions is true and false otherwise

implication

conditional statement; "if p, then q" false when p is true and q is false, true otherwise.

converse of p->q

q->p; equivalent to inverse

contrapositive p->q

not q -> not p; has the same truth value as p->q always

inverse of p->q

not p -> not q; equivalent to converse

equivalent

two compound propositions always having the same truth value

biconditionals (bi-implications; biconditional statements)

if and only if; true only when p and q have the same truth values; iff

Precedence of logical operators

negation, conjunction, disjunction, conditional, biconditional

bit

symbol with two possible values, namely 0 and 1

boolean variable

a variable with a value of either true or false

bit string

sequence of zero or more bits; the length of this string is the number of bits in the string

tautology

a compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it (emphasis on always)

contradiction

a compound proposition that is always false

contingency

a compound proposition that is always true

logically equivalent

compound propositions that have the same truth values in all possible cases; when these two propositions, p and q, in the compound proposition p iff q is a tautology. (emphasis on truth values)

distributive law (disjunction over conjunction)

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

De Morgan's Laws

how to negate conjunctions and disjunctions; the negation of a disjunction is the conjunction of the negation of the components; the negation of a conjunction is the disjunction of the negations of the component propositoins

satisfiable

when for a compound proposition there is an assignment of truth values to its variables that makes it trues

unsatisfiable

when the compound proposition is false for all assignments of truth values to its variables

solution

an assignment of truth values that makes a compound proposition true

predicate

refers to a property that the subject of the statement can have

propositional function

the value determined by the statement P(x)

preconditions

the statements that describe valid input

postconditions

the conditions that the output should satisfy when the program has run

quantification

expresses the extent to which a predicate is true over a range of elements

universal quantification

"P(x) for all values of x in the domain"

counterexample

an element for which P(x) is false (for the universal quantification)

existential quantification

"There exists an element x in the domain such that P(x)."

uniqueness quantifier

"there is exactly one", "there is one and only one." (backwards E!)

bound

the occurrence of the variable, when a quantifier is used on the variable

free

the occurrence of a variable that is not bound by a quantifier or set equal to a particular value

scope

the part of a logical expression to which a quantifier is applied

argument

a sequence of propositions.

premises

all propositions but the final proposition in an argument

conclusion

final proposition in an argument

valid

when the truth of all an argument's premises implies that the conclusion is true

modus ponens/law of detachment

the tautology if (p AND (if p then q)) then q

modus tollens

the tautology if (not q and (if p then q)) then not p

hypothetical syllogism

the tautology if ((if p then q) and (if q then r)) then (if p then r)

disjunctive syllogism

the tautology if ((p or q) and not p) then q

addition

the tautology if p then (p or q)

simplification

the tautology if (p and q) then p

conjunction (rule of inference)

the tautology if ((p) and (q)) then (p and q)

Resolution

the tautology if ((p or q) and (not p or r)) then (q or r)

fallacy of affirming the conclusion

treating the proposition "if p then q and q, then p" as a tautology, even though it is not

fallacy of denying the hypothesis

treating the proposition "if p then q and not p, then not q" as a tautology, even though it is not

Universal instantiation

for every x, P(x), therefore P(c)

Universal generalization

P(c) for an arbitrary c, there for every x P(x) (emphasis arbitrary, no assumptions about c)

Existential instantiation

there exists an x P(x), therefor P(c) for some element c (we only know that this c exists)

Existential generalization

P(c) for some element c, therefore there exists an x P(x)

universal modus ponens

if for every x, if P(x) then Q(x) is true, and if P(a) is true for particular a in the domain of the universal quantifier, then Q(a) must also be true