Discrete Math Flashcards
Individually separate and distinct.
discrete
(thetheory of ways things combine; in particular, how to count these ways)
combinatorics
is any declarative sentence which is either true or false.
statement
__________is atomic if it cannot be divided into smaller statements, otherwise it is _________
statement, molecular
You can build more complicated (molecular) statements out of simpler ones using ________
logical connectives.
Logical connectives are called _________ when they connecttwo statements while a ____________ applies to a single statement.
binary connectives, unary connective
(sometimes called sentential variables), usually capital lettersin the middle of the alphabet: P, Q, R, S, . . ..
propositional variables
A composite proposition, in which is composed of sub propositions andvarious connectives is referred to as a __________
compound proposition.
A proposition is said to be ________ if it cannot be broken downinto simpler propositions, that is, if it is not composite.
primitive
P ∧ Q is read “P and Q,” and called a ____________
conjunction.
P ∨ Q is read “P or Q,” and called a ________
disjunction.
P → Q is read “if P then Q,” and called an ________
implication or conditional.
P ↔ Q is read “P if and only if Q,” and called a ________
biconditional.
¬P is read “not P,” and called a
negation
We say that P is the ________ (or antecedent), and Q is the _________ (or consequent).
hypothesis, conclusion
is the study of consequence.
logic
An ________ is a set of statements, one of which is called the_________ and the rest of which are called _________.
argument, conclusion, premises
An argument which is not valid is called a ________
fallacy.
is simply a statement.
proposition
studies the ways statements can interact with eachother.
Propositional logic
The _________ of a compound propositions is referred to as exclusive disjunction.
exclusive or
A variable is called a _____________ if its value is either true or
false.
Boolean variable
is a sequence of zero or more bits.
bit string
is a mathematical expression that has a variable as its subject, and a predicate which is the property the
variable. It is denoted by P(x).
propositional function
is a proposition whose truth depends on the value of one
or more variables.
predicate
expresses the extent to which a predicate is true over a range of elements.
Quantification
of P (x) for a particular domain is the
proposition that asserts that P (x) is true for all values of x in this
domain.
universal quantification
The symbol ∃ which reads “there exists” or “for some” or “for at least
one” is called the
existential quantifier.
we form a proposition that is true if
and only if P (x) is true for at least one value of x in the domain.
existential quantification,
is a statement which is true on the basis of its logical form alone.
tautology
if it is false for any truth values of its variables.
contradiction
A compound proposition that is neither a tautology nor a contradiction is a
contingency.
Two (molecular) statements P and Q are ______________ provided P
is true precisely when Q is true.
logically equivalent
The way to distribute a negation over a disjunction (an or) has a similar rule for distributing over a conjunction (and).
De Morgan’s Law
To write this statement symbolically, we must use
quantifiers.
Better to think of P and O as denoting properties of their input. The technical term for these is _________ and when we study them in logic, we need to use _________.
predicates, predicate logic
