MTH 309 Study Guide - Final Guide: Existential Quantification, Universal Quantification, Propositional Function
30 Apr 2018
School
Department
Course
Professor
Discrete Final Exam Study Guide
Part 1
Propositional Logic
• Proposition
A proposition is a declarative sentence that is either true or false but not both. The truth value
of a proposition is T if true & F if false
• ,
No-P is tue he P is false
•
P ad Q is tue he oth P & Q ae tue
•
P o Q is tue he at least oe of P & Q is tue
•
P iplies Q is tue he P is false o Q is tue
•
P oiplies Q o P if & ol if Q is tue he oth P & Q are true or both P & Q are false
• Truth Tables
T
T
F
T
T
T
T
T
F
F
F
T
F
F
F
T
T
F
T
T
F
F
F
T
F
F
T
T
• Truth Value of Propositions
Statement
When True?
When False?
Both true
Either false
At least one of true
Both false
Either P is false or Q true (or
both)
Both true & false
• Contrapositive
The contrapositive of is and they are logically equivalent. Thus, to prove an
implication, you may prove the contrapositive.
Eaple: If a it is i FL, its i the U“. Cotapositie: If a it ist i the U“, it ist i FL.
• Converse
The converse of is . These two statements are not logically equivalent.
Propositional Equivalences
• Tautology
Something has tautology if it is always true. For example,
• Logically Equivalent
Two statements are logically equivalent if they have the same truth table, i.e., if is a
tautology. The notation is .
• Laws/Properties of Logical Equivalences
find more resources at oneclass.com
find more resources at oneclass.com
Double Negation Law
Commutative Laws
Associative Laws
De Mogas Las
Distributive Laws
Absorption Laws
• Contradiction
Use the symbol for a statement always true (tautology) & for a statement always false.
This sets the basis for a proof by contradiction. This means if you assume and , then try to
poe its tue, ou get a otaditio. “o it ust e instead of .
Predicates & Quantifiers
• Propositional Functions
The statement is said to be the value of the propositional function at . Once a value
has been assigned to the variable , the statement becomes a proposition & has a truth
value.
Example: Let denote the statement . is true & is false.
We can also have statements that involve more than one variable. In is the predicate
& are the variables.
Example: Let denote the statement . is false & is true.
• Quantification
Quantification expresses the extent to which a predicate is true over a range of elements. In
English, the words all, some, many, none, & few are used in quantifications.
• Domain
The domain (universe) is the values looked at in a quantification. It must be specified. When the
domain changes, the truth value of a quantification changes as well.
find more resources at oneclass.com
find more resources at oneclass.com
•
The uiesal uatifiatio, fo eah. Its said for all o fo ee . A
element for which is false is called a counterexample of
•
The eistetial uatifiatio, thee eists. Its said There exists an element in the domain
such that .
• Truth Value of Quantifiers
Statement
When True?
When False?
is true for every x
There is an for which
is false
There is an for which
is true
is false for every x
• Precedence of Quantifiers
The quantifiers & have higher precedence than all logical operators from propositions.
Example: is the disjunction of & . In other words, it means
rather than
• Logical Equivalence of Quantifiers
To show that statements are logically equivalent, we must show that they always take the same
truth value, no matter what the predicates & are, & no matter what the domain is.
Example:
First, we show that if is true, then is true. Second, we show
that if is true, then is true.
Suppose that is true. This means that if is in the domain, then
is true. Hence, is true & is true. Because is true & is true for every
element in the domain, we can conclude that & are both true. So,
is true.
Next, suppose that is true. It follows that is true & is true.
Hence, if is in the domain, then is true & is true. It follows that for all
is true. So, is true.
We can now conclude that
• Negating Quantifications
To negate a quantified expression, you must negate everything. i.e., both the quantifier & the
proposition.
• Truth Value of Negated Quantifiers
Statement
Equivalent Statement
When True?
When False?
is false for
every x
There is an for
which is true
There is an for
which is false
is true for every
x
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
A proposition is a declarative sentence that is either true or false but not both. F (cid:862)p (cid:272)oi(cid:373)plies q(cid:863) o(cid:396) (cid:862)p if & o(cid:374)l(cid:455) if q(cid:863) is t(cid:396)ue (cid:449)he(cid:374) (cid:271)oth p & q are true or both p & q are false. Either p is false or q true (or both) (cid:1842)(cid:1512)(cid:1843) (cid:1842)(cid:1513)(cid:1843) (cid:1842) (cid:1843) The contrapositive of (cid:1842) (cid:1843) is ~(cid:1843) ~(cid:1842), and they are logically equivalent. Something has tautology if it is always true. Two statements are logically equivalent if they have the same truth table, i. e. , if (cid:1842) (cid:1843) is a tautology. The notation is (cid:1842)(cid:1568)(cid:1843). implication, you may prove the contrapositive. E(cid:454)a(cid:373)ple: if a (cid:272)it(cid:455) is i(cid:374) fl, it(cid:859)s i(cid:374) the u . Co(cid:374)t(cid:396)apositi(cid:448)e: if a (cid:272)it(cid:455) is(cid:374)(cid:859)t i(cid:374) the u , it is(cid:374)(cid:859)t i(cid:374) fl: laws/properties of logical equivalences, logically equivalent. ~(cid:4666)(cid:1842)(cid:1512)(cid:1843)(cid:4667)=(cid:4666)~(cid:1842)(cid:4667)(cid:1513)(cid:4666)~(cid:1843)(cid:4667) (cid:1842)(cid:1512)(cid:4666)(cid:1843)(cid:1513)(cid:1844)(cid:4667)(cid:1568)(cid:4666)(cid:1842)(cid:1512)(cid:1843)(cid:4667)(cid:1513)(cid:4666)(cid:1842)(cid:1512)(cid:1844)(cid:4667) (cid:1842)(cid:1513)(cid:4666)(cid:1843)(cid:1512)(cid:1844)(cid:4667)(cid:1568)(cid:4666)(cid:1842)(cid:1513)(cid:1843)(cid:4667)(cid:1512)(cid:4666)(cid:1842)(cid:1513)(cid:1844)(cid:4667) (cid:1842)(cid:1513)(cid:4666)(cid:1842)(cid:1512)(cid:1843)(cid:4667)(cid:1568)(cid:1842) (cid:1842)(cid:1512)(cid:4666)(cid:1842)(cid:1513)(cid:1843)(cid:4667)(cid:1568)(cid:1842: contradiction value, propositional functions.
