CSCI 2011 Study Guide - Spring 2018, Comprehensive Midterm Notes - Without Loss Of Generality, Wireless Access Point, Volkswagen Beetle
CSCI 2011
MIDTERM EXAM
STUDY GUIDE
Fall 2018
Discrete Structures
● CSCI 2011 at U of M
Propositional Logic/Boolean Algebra
● Connectives are the word for the operators
● ¬ is not
● is or
● is and
● → is implies
●
↔ is equivalent
● ≡ is identical to
● is exclusive or⊗
Truth Table with Connective Definitions
P, Q
¬P
PQ
PQ
P Q⊗
P→Q
P↔Q
F F
T
F
F
F
T
T
F T
T
F
T
T
T
F
T F
F
F
T
T
F
F
T T
F
T
T
F
T
T
P→Q≡¬PQ
● A tautology is a statement which is true for every combination of T and F for its
arguments (every cell of its truth table)
○ Tautologies are useful to find because then a portion of a complicated logical
expression simplifies to T
● A contradiction is the opposite of a tautology
● ‘not’ , ‘or’, and ‘and’ are a set of connectives which are functionally complete, meaning
they can represent any boolean function
● distributes over and vise-versa
○ ex. ¬p q) (p p)p q))p(¬q≡ ( ¬(¬q
Identities/Logical Equivalences
● De Morgan’s Laws (basically ‘not’ distributes and reverses ‘or’ and ‘and’)
○(P... ) P P ... P¬1P2Pn≡ ¬ 1¬2¬n
○(P... ) P P ... P¬1P2Pn≡ ¬ 1¬2¬n
●, are associative, commutative, and distributive
● Idempotent Laws
find more resources at oneclass.com
find more resources at oneclass.com
○PP≡P
○PP≡P
● Identity Laws
○PT≡P
○PF≡P
● Negation Laws
○PP ¬ ≡ T
○PP ¬ ≡ F
● Domination Laws
○PT≡T
○PF≡F
● Absorption Laws
○P)P(Q≡P
○P)P(Q≡P
● Double Negation Law
○¬P¬ ≡ P
● Distributive Laws
○Q)P)P)P(R≡ ( Q(R
○Q)P)P)P(R≡ ( Q(R
● Definition of Implication
○PP →Q≡ ¬ Q
● (Contrapositive is equivalent)Q PP →Q≡ ¬ → ¬
●PP Q≡ ¬ → Q
● m(P Q)PQ≡ ¬ → ¬
●P)P)Q)( → Q( → R≡P→ ( R
●P)Q)P)( → R( → R≡ ( Q→R
●P)P)Q)( → Q( → R≡P→ ( R
●P)Q)P)( → R( → R≡ ( Q→R
● Use identities for proofs
Predicate Logic/Predicate Calculus/First-order logic
● A predicate is a boolean function whose arguments can be anything but other predicates
(that would be higher-order logic).
○ Ex. parent(x, y) returns true if x is the parent of y
● Quantifiers
○ (Universal/“for all”)∀
■ Ex. means P(x) is true for all xxP (x)∀
○ (Existential/“there exists”)∃
■ Ex. means there exists an (at least one) x such that P(x) is truexP (x)∃
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Connectives are the word for the operators. Is identical to is exclusive or. A tautology is a statement which is true for every combination of t and f for its arguments (every cell of its truth table) Tautologies are useful to find because then a portion of a complicated logical expression simplifies to t. A contradiction is the opposite of a tautology. Not" , or", and and" are a set of connectives which are functionally complete, meaning they can represent any boolean function (cid:1318) distributes over. Ex. p (cid:1319) ( (cid:1319) (cid:1318) (cid:1319) q ( and vise-versa q) p) (p (cid:1319) (cid:1318) ( (cid:1319) p q)) (cid:1319) q. De morgan"s laws (basically not" distributes and reverses or" and and") 1 (cid:1319) p 2 (cid:1318) p n 1 (cid:1319) 2 (cid:1319) p n 1 (cid:1318) 2. (cid:1166), (cid:1165) are associative, commutative, and distributive. P (cid:1319) ( (cid:1318) r ( (cid:1319) q (cid:1318) ( (cid:1319) r.
