discrete math 1 midterm Flashcards
proposition
A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. All the following declarative sentences are propositions. 1. Washington, D.C., is the capital of the United States of America. 2. Toronto is the capital of Canada. 3. 1 + 1 = 2. 4. 2 + 2 = 3.
propositional variables
variables that represent propositions, just as letters are used to denote numerical variables. The conventional letters used for propositional variables are p, q, r, s, . . . . The truth value of a proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, denoted by F, if it is a false proposition.
propositional calculus
The area of logic that deals with propositions The area of logic that deals with propositions is called the propositional calculus or propositional logic. It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago.
compound propositions
formed from existing propositions using logical operators
truth table
a diagram in rows and columns showing how the truth or falsity of a proposition varies with that of its components.
negation operator
¬p
conjunction operator
ᐱ
disjunction operator
ᐯ
p ∧ q
conjunction “and”
p ∨ q
disjunction “or”
¬p
negation “not”
inclusive or
p ∨ q “disjunction” p or q (but not both)”
conditional operator
→ The conditional statement p → q is false when p is true and q is false, and true otherwise
→
conditional statement
implication
→ A conditional statement is also called an implication
“If I am elected, then I will lower taxes.”
conditional statement
if 2 + 2 = 4 then x := x + 1
conditional statement
CONVERSE
one of three related conditional statements that occur so often that they have special names q → p is called the converse of p → q
CONTRAPOSITIVE
one of three related conditional statements that occur so often that they have special names p → q is the proposition ¬q →¬p
INVERSE
one of three related conditional statements that occur so often that they have special names ¬p →¬q is called the inverse of p → q
equivalent
When two compound propositions always have the same truth value. conditional statement and its contrapositive are equivalent: p → q = ¬q →¬p “If it is raining, then the home team wins.” “If the home team does not win, then it is not raining.”
biconditional statement
p ↔ q proposition “p if and only if q.” also called bi-implications
p ↔ q
biconditional proposition “p if and only if q.”
bi-implications
p ↔ q proposition “p if and only if q.” also called biconditional statement
“if and only if”
biconditional statement p ↔ q
“q whenever p”
→ conditional statement
“not”
negation operator ¬p
p → q “p only if q” Is Same As ?
“if p, then q,”
¬p →¬q
inverse
q → p is considered what of p → q
converse
p → q is considered what of ¬q →¬p
contrapositive
¬p →¬q is considered what of p → q
inverse
What are the contrapositive, the converse, and the inverse of the conditional statement “The home team wins whenever it is raining?”
Consequently, the contrapositive of this conditional statement is “If the home team does not win, then it is not raining.” The converse is “If the home team wins, then it is raining.” The inverse is “If it is not raining, then the home team does not win.” Only the contrapositive is equivalent to the original statement.
“iff”
“if and only if.” biconditional statement p ↔ q
(p → q) ∧ (q → p).
Note that p ↔ q has exactly the same truth value as (p → q) ∧ (q → p). **** biconditional statement ****
What is the Precedence of Logical Operator →
¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5
What is the Precedence of Logical Operator ¬
¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5
What is the Precedence of Logical Operator ↔
¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5
What is the Precedence of Logical Operator ∨
¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5
What is the Precedence of Logical Operator ∧
¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5
What logic gate is this?
Inverter
What logic gate is this?
OR gate
what logic gate is this?
AND gate
What is a A combinatorial circuit?
Complicated digital circuits can be constructed from three basic circuits, called gates, shown
in Figure 1. The inverter, or NOT gate, takes an input bit p, and produces as output °˛p. The
OR gate takes two input signals p and q, each a bit, and produces as output the signal p ∨ q.
Finally, the AND gate takes two input signals p and q, each a bit, and produces as output the
signal p ∧ q.
tautology
A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology
contradiction.
A compound proposition that is always false is called a contradiction.
contingency.
A compound proposition that is neither a tautology nor a
contradiction is called a contingency
logically equivalent
Compound propositions that have the same truth values in all possible cases are called logically equivalent.
≡
≡
Compound propositions that have the same truth values in all possible cases are called logically equivalent
p ≡ q
is the statement that p ↔ q is a tautology
De Morgan’s Laws.
named after the English mathematician Augustus De Morgan, of the mid-nineteenth century
¬(p ∧ q) ≡ ¬p ∨¬q
¬(p ∨ q) ≡ ¬p ∧¬q
Identity laws
Domination laws
Idempotent laws
Double negation law
Commutative laws
Associative laws
Distributive laws
De Morgan’s laws
Absorption laws
Negation laws
De Morgan’s laws are particularly important because?
They tell us how to negate conjunctions and how to negate disjunctions.
In particular, the equivalence ¬(p ∨ q) ≡ ¬p ∧¬q tells us that the negation of a disjunction is formed by taking the conjunction of the negations of the component propositions. Similarly, the equivalence ¬(p ∧ q) ≡ ¬p ∨¬q tells us that the negation of a conjunction is formed by taking the disjunction of the negations of the component propositions
Propositional Satisfiability
A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true
Propositional unsatisfiable.
when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable.
to show that a compound proposition is unsatisfiable, we need to show that every assignment of truth values to its variables makes it false.
Propositional solution
When we find a particular assignment of truth values that makes a compound proposition true, we have shown that it is satisfiable; such an assignment is called a solution of this particular satisfiability problem
predicate
refers to a property that the subject of the statement can have
propositional function
The statement P(x) is also said to be the value of the propositional function P at x.
Let P(x) denote the statement “x > 3.”
preconditions
The statements that describe valid input are known
as preconditions
postconditions.
the conditions that the output should satisfy when the program has run are known as postconditions.
quantification
Quantification expresses the extent to which a predicate is true over a range of elements. In English, the words all, some, many, none, and few are used in quantifications.
universal quantification
tells us that a predicate is true for every element under
consideration,
existential quantification
tells us that there is one or more element under consideration for which the predicate is true
predicate calculus
The area of logic that deals with predicates and quantifiers
domain of discourse
Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain
Ref: THE UNIVERSAL QUANTIFIER
∀
universal quantifier “EVERY”
“P(x) for all values of x in the domain.”
The notation ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the universal quantifier.We read ∀xP(x) as “for all xP(x)” or “for every xP(x).” An element for which P(x) is false is called a counterexample of ∀xP(x).
∃
existential quantification
universal quantifier “Exists”
“There exists an element x in the domain such that P(x).”
We use the notation ∃xP(x) for the existential quantification of P(x). Here ∃ is called the existential quantifier.
“there is exactly one” and
“there is one and only one.”
uniqueness quantifier, denoted by ∃! or ∃1.
∃!x(x − 1 = 0),
uniqueness quantifier
∃! or ∃1
What are the Precedence of Quantifiers?
The quantifiers ∀ and ∃ have higher precedence than all logical operators from propositional calculus. For example, ∀xP(x) ∨ Q(x) is the disjunction of ∀xP(x) and Q(x). In other words, it means (∀xP(x)) ∨ Q(x) rather than ∀x(P(x) ∨ Q(x)).
bound variable
When a quantifier is used on the variable x, we say that this occurrence of the variable is bound.
free variable
An 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 is called the scope of this quantifier.
Statements involving predicates and quantifiers are logically equivalent….
S ≡ T
if and only if they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions.
We use the notation S ≡ T to indicate that two statements S and T involving predicates and quantifiers are logically equivalent.
De Morgan’s Laws for Quantifiers.
The rules for negations for quantifiers
When the domain of a predicate P(x) consists of n elements, where n is a positive integer greater than one, the rules for negating quantified statements are exactly the same as De Morgan’s laws discussed in Section 1.3. This is why these rules are called De Morgan’s laws for quantifiers.
Prolog facts
Prolog facts define predicates by specifying the elements that satisfy these predicates.
Prolog rules
Prolog rules are used to define new predicates using those already defined by Prolog facts.
nested quantifiers
where one quantifier is within the scope of another, such as
∀x∃y(x + y = 0).
it is sometimes helpful to think of me in terms of nested loops… What am I?
Nested Quantifiers
Logical Equivalences and biconditional Statements
