Week 1: Logic Flashcards
1
Q
proposition
A
- a declarative sentence that is either true or false
2
Q
examples of propositions and not propositions
A
- prop: Purdue was founded in 1874, 1869 + 0 = 1869
- not prop: what time is it? x + 1 = 2
3
Q
negation
A
- ¬ symbol
- makes the result the opposite (ex. p is True, ¬p is False)
4
Q
conjunction
A
- ^ 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
5
Q
disjunction
A
- 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
6
Q
implication
A
- 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
7
Q
biconditional
A
- <-> symbol
- means p if and ONLY if q
- either both are true OR false for it to be true
8
Q
meaning of or in discrete
A
- 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
9
Q
exclusive or
A
-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
10
Q
implication is not…
A
- commutative
- p isn’t always true when q is false
11
Q
converse
A
- the opposite of the implication
- original: p -> q (if x=2, x^2=4)
- converse: q -> p (if x^2=4, then x=2)
12
Q
inverse
A
- 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)
13
Q
contrapositive
A
- 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)
14
Q
biconditional
A
- 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
15
Q
how to construct truth tables for compound propositions
A
- 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
16
Q
equivalent propositions
A
- two propositions are equivalent if they always have the same truth value
17
Q
precedence of logical operators (highest to lowest, 5 things)
A
- ¬
- ∨
- →
- <->
18
Q
application of logic
A
- logic gates w/computers
- 1 represents true, 0 is false
19
Q
tautologies
A
- a proposition which is always true
- ex. p ∨¬p
20
Q
contradictions
A
- a proposition which is always false
- p ∧¬p
21
Q
identity law (with T/F)
A
- p ∧ T ≡ p
- p ∨ F ≡ p
22
Q
domination laws (with T/F)
A
-p ∧ F ≡ F
- p ∨ T ≡ T
23
Q
idempotent law
A
-p ∧ p ≡ p
- p ∨ p ≡ p
24
Q
double negation law
A
¬(¬p) ≡ p
25
negation law
- p ∨ ¬p ≡ T
- p ^ ¬p ≡ F
26
commutative law
- p ∨ q ≡ q ∨ p
- p ^ q ≡ q ^ p
27
associative laws
- (p ^ q) ^ r ≡ p ^ (q ^ r)
- (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
28
distributive laws
- p ∨ (q ^ r) ≡ (p ∨ q) ^ (p ∨ r)
- (p ^ (q ∨ r)) ≡ (p ^ q) ∨ (p ^ r)
29
absorption laws
- p ∨ (p ^ q) ≡ p
- p ^ ( p ∨ q) ≡ p
30
De Morgan's first law
¬ (p ^ q) ≡ ¬p ∨ ¬q
31
De Morgan's second law
¬ (p ∨ q) ≡ ¬p ^ ¬q
32
propositional satisfiability
- proposition is satisfiable if you can make the proposition true
- unsatisfiable if there's no way to make the proposition true
33
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
34
what p <-> q is equivalent to
- (p -> q) ^ (q ->p)
35
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
36
universal quantifier
- "for all", symbol ∀
- ∀x P(x) asserts P(x) is true for every x in the domain
37
existential quantifier
- "there exists", symbol ∃
- ∃xP(x) asserts P(x) is true for some x in the domain
38
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
39
compound expressions
- connectives from propositional logic carry over to predicate logic
- expressions with variables are not propositions
- ex. P(3) -0> P(1), etc.
40
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)
41
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
42
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
43
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
44
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)
45
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
46
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
