Week 1: Logic Flashcards
proposition
- a declarative sentence that is either true or false
examples of propositions and not propositions
- prop: Purdue was founded in 1874, 1869 + 0 = 1869
- not prop: what time is it? x + 1 = 2
negation
- ¬ symbol
- makes the result the opposite (ex. p is True, ¬p is False)
conjunction
- ^ symbol
- works like and (BOTH have to be true for it to be true)
- ex. the movie is nice = p, I am at home = q, p^q the movie is nice and I’m at home
disjunction
- symbol ∨
- works like and (just ONE needs to be true)
- ex. p: 1+1=2, q: 2+2=5
- p∨ q is p OR q
- disjunction is COMMUTATIVE
implication
- p -> q is a conditional statement of implication
- if p is false, statement is always true (no condition to fulfill)
- if p AND q are true, its true
- if p is true, q is false, its false
biconditional
- <-> symbol
- means p if and ONLY if q
- either both are true OR false for it to be true
meaning of or in discrete
- inclusive or (ex. student who have taken 180 or 161 may take this class)
- disjunction/or means this in discrete
- for p ∨ q, at least one must be true
exclusive or
-symbol ⊕
- ex. comes with soup or salad (don’t expect to get both)
- with p ⊕ q, one of p and q must be true, but not both
implication is not…
- commutative
- p isn’t always true when q is false
converse
- the opposite of the implication
- original: p -> q (if x=2, x^2=4)
- converse: q -> p (if x^2=4, then x=2)
inverse
- the negated version of the original statement
- original: ¬ p → ¬ q (if x=2, x^2=4)
- inverse: p → q (if x ≠ 2, x^2 ≠ 4)
contrapositive
- the negated version and opposite of the original statement
- original: ¬ p → ¬ q (if x=2, x^2=4)
- contrapositive: q → p (if x^2≠ 4, then x ≠ 2)
biconditional
- symbol p <-> q, written as p if and only if q
- only true when both p and q are true OR false
- ex. p = book is good, q = staying at home, p <-> book is interesting iff I’m at home
how to construct truth tables for compound propositions
- need a row for every possible combination of values for atomic propositions (2^n for n variables)
- list all possible combinations
- columns for each individual step
equivalent propositions
- two propositions are equivalent if they always have the same truth value
precedence of logical operators (highest to lowest, 5 things)
- ¬
- ∨
- →
- <->
application of logic
- logic gates w/computers
- 1 represents true, 0 is false
tautologies
- a proposition which is always true
- ex. p ∨¬p
contradictions
- a proposition which is always false
- p ∧¬p
identity law (with T/F)
- p ∧ T ≡ p
- p ∨ F ≡ p
domination laws (with T/F)
-p ∧ F ≡ F
- p ∨ T ≡ T
idempotent law
-p ∧ p ≡ p
- p ∨ p ≡ p
double negation law
¬(¬p) ≡ p
negation law
- p ∨ ¬p ≡ T
- p ^ ¬p ≡ F
commutative law
- p ∨ q ≡ q ∨ p
- p ^ q ≡ q ^ p
associative laws
- (p ^ q) ^ r ≡ p ^ (q ^ r)
- (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
distributive laws
- p ∨ (q ^ r) ≡ (p ∨ q) ^ (p ∨ r)
- (p ^ (q ∨ r)) ≡ (p ^ q) ∨ (p ^ r)
absorption laws
- p ∨ (p ^ q) ≡ p
- p ^ ( p ∨ q) ≡ p
De Morgan’s first law
¬ (p ^ q) ≡ ¬p ∨ ¬q
De Morgan’s second law
¬ (p ∨ q) ≡ ¬p ^ ¬q
propositional satisfiability
- proposition is satisfiable if you can make the proposition true
- unsatisfiable if there’s no way to make the proposition true
ways to express the biconditional in English
- p if and only if q
- p is necessary and sufficient for q
- if p then q, and conversely
- p iff q
what p <-> q is equivalent to
- (p -> q) ^ (q ->p)
predicate logic
- propositional functions are a generalization of proposition
- contain variables and a predicate (P(x))
- variables can be replaced by elements in their domain
universal quantifier
- “for all”, symbol ∀
- ∀x P(x) asserts P(x) is true for every x in the domain
existential quantifier
- “there exists”, symbol ∃
- ∃xP(x) asserts P(x) is true for some x in the domain
propositional functions
- the statement P(x) has the value of the propositional function P at x
- domain needs to be given (often denoted by U)
- ex. P(x) “x > 0” and domain integers, P(-3) is false, P(3) is true
compound expressions
- connectives from propositional logic carry over to predicate logic
- expressions with variables are not propositions
- ex. P(3) -0> P(1), etc.
precedence of quantifiers
- the quantifiers ∃ and ∀ have higher precedence than all logical operators
- ex. ∀x P(x) ^ Q(x) means (∀x P(x)) ^ Q(x)
equivalences in predicate logic
- predicates/quantifiers are logically equivalent iff they have the same truth value
- true for every predicate and every domain used for variables
negating quantified expressions
- if ∃x J(x) means for some, ¬∃x J(x) ALL
- if ∀ x J(x) means all, ¬∀ x J(x) means SOME
De Morgan’s Laws for quantifiers
¬∃x P(x) ≡ ∀ x ¬P(x)
- when true, every x is false
- when false, there is an x where P(x) is true
¬∀ x P(x) ≡ ∃x ¬P(x)
- when true, there is an x where P(x) is false
- when false, every x is true
nested quantifiers
- having multiple quantifiers for multiple variables
- ex. x and y are real nums, “every real number has an additive inverse”
- ∀x ∃y (x + y = 0)
order of quantifiers
- if using nested quantifier, and all variables have a ∀, order doesn’t matter
- if used nested quantifier, and some variables have ∀ and others ∃, order matters
- ex. ∀x∀y P(x, y) can be, ∀x∃y P(x, y) can’t be
can we switch the order of quantifiers?
- if they are all the same type (for all or there exists) yes
- if they are different, no
