discrete maths Flashcards
propositional logic
a sentence declaring a fact that is either true or false
compound proposition
compound propositions are formed for other propositions using logical operators
negation (¬)
it is not the case that
conjunction (n)
the proposition that two propositions are both true else false
disjunction (v)
the proposition that either or both propositions are true
truth tables
gives the truth values of a compound proposition for all combinations of inputs
short circuit evaluation
in python some boolean operators will only execute the second condition if the first does not determine the value of the expression
exclusive or (⊕)
the proposition that either of the propositions are true not both
implication (=>)
the proposition of if a hypothesis then conclusion, only false if hyp true and con false
contrapositive
p => q is the logical equivalent of ¬q => ¬p
converse
p => q is not the logical equivalent of q => p
biconditional (<=>)
the proposition that both propositions have equivalent values
truthologies
a compound proposition that is always true ie p v ¬p
contraditions
a compound proposition that is always false ie p n ¬p
logical equivalence (≡)
compound statements are logically equivalent if they share identical truth tables
known logical equivalence rules
Commutative, 𝑝 Ʌ 𝑞 ≡ 𝑞 Ʌ 𝑝, 𝑝 V 𝑞 ≡ 𝑞 V 𝑝
Associative, (𝑝 Ʌ 𝑞) Ʌ 𝑟 ≡ 𝑝 Ʌ (𝑞 Ʌ 𝑟), (𝑝 V 𝑞) V 𝑟 ≡ 𝑝 V (𝑞 V 𝑟)
Distributive, 𝑝 V (𝑞 Ʌ 𝑟) ≡ (𝑝 V 𝑞) Ʌ (𝑝 V 𝑟), 𝑝 Ʌ (𝑞 V 𝑟) ≡ (𝑝 Ʌ 𝑞) V (𝑝 Ʌ 𝑟)
Identity, 𝑝 Ʌ T ≡ 𝑝, 𝑝 V F ≡ 𝑝
Negation, 𝑝 V ¬𝑝 ≡ T, 𝑝 Ʌ ¬𝑝 ≡ F
Idempotent, 𝑝 Ʌ 𝑝 ≡ 𝑝, 𝑝 V 𝑝 ≡ 𝑝
De Morgan, ¬(𝑝 V 𝑞) ≡ ¬𝑝 Ʌ ¬𝑞, ¬(𝑝 Ʌ 𝑞) ≡ ¬𝑝 V ¬𝑞
Double negation, ¬(¬𝑝) ≡ 𝑝
ℕ, ℤ, ℚ, ℝ,
ℕ = natural numbers (numbers used for counting)
ℤ = integers (whole numbers)
ℚ = rational numbers (numbers that can be written as p/q)
ℝ = complex numbers ( numbers in the form a +ib where i=sqrt(-1))
set notation - enumeration
listing all members of the set ie. A ∈ {1,2,3,4,…,n}
set notation - set builder
set is defined using variables and logical statements ie A ∈ {x: x > 0} where x is an integer
𝕌
a set containing all the related values without any repititions
compliment
𝐴 = 𝕌 − 𝐴
power set - 𝒫(𝑆)
a set containing all possible combinations of the elements of s from cardinality of 0 to |s|
Cartesian product
A * B, { 𝑎, 𝑏 : 𝑎 ∈ 𝐴 𝑎𝑛𝑑 𝑏 ∈ 𝐵}
partition of a set
a set containing subsets which total to = the original set, there are no empty subsets and each combination of subsets are disjointed (no common member)
functions
mapping a to b such that each member of a is matched to a single member of b
injective function
|A| <= |B|, not all elements of B will necessarily be mapped to a member of A
surjective function
|A| >=|B|, Elements of B may map to more than one element of A
bijective function
|A| =|B|, both injective and surjective
א
smallest cardinality of an infinate set
permutations
a set of objects from a sequence where order maters, a sequence n has n! combinations
to find p(n,r) where n is the length of the whole set and r is the length of the subset to be found there are: 𝑛^𝑟 permutations with repartitions and 𝑛! / (𝑛 − 𝑟 !) without repartitions
combinations
a set of objects from a sequence where order does not matter
to find c(n,r): n! / (r!(n-r)!) combinations without repartitions and c(n+r-1, n-1)
Permutations with indistinguishable objects
when a set contains members that appear the same the permutations is n! / (n1! * n2! * … * nk!)
product rule
|A1 * A2 * … * An| = |A1| * |A2| * … * |An|
𝑃 (𝐴 ∩ 𝐵) = 𝑃( 𝐴| 𝐵) 𝑃( 𝐵) = 𝑃( 𝐵|𝐴) 𝑃(𝐴)
sum rule
for S {s1, s2, …, sn}, |S| = |s1| + |s2| + … + |sn|
𝑃 (𝐴 ∪ 𝐵) = 𝑃( 𝐴) + 𝑃 (𝐵) − 𝑃( 𝐴 ∩ 𝐵)
probability with equally likely outcomes
P(E) = |E| / |S| where S is the sample space (all possible outcomes) and E is a subset of S
probability of compliment
p(¬E) = 1-p(E)
independent
P(A and B) = P(A) * P(B)
disjointed(mutualy exclusive)
p(A or B) = P(A) + P(B)
conditional probability
P(A|B) = P(A and B) / P(B)
pigeon-hole principle
to put n+1 items in n boxes, at least one box must have more than one items in it
fisher yates shuffel
unbiased shuffle that produces a random permutation of the set, runs in o(n), for each item generates a random number from 0<= j< i and swaps the original item and the random index
direct proof
hypothesis -> deduction -> conclusion
proof by case
case1: hypothesis _> deduction -> conclusion
case2: hypothesis -> deduction -> conclusion
ect
proof by counter example
one counter example -> disproof of universal statement
proof by contradiction
suppose not: ¬p
derive contradiction
conclude: ¬p is false therefore p is true
proof by contraposition
write statement into p=> q
suppose ¬q
derive ¬p
conclude: ¬q=>¬p and it is equivalent to p=>q
proof by induction
prove that when the variable is 1 is true
hypothesis variable = k is valid
sub in k + 1 then simplify and substitute n back in for k + 1
alternative shuffle
similar to fisher yates but generates index from 0 < j < len(set), produces an uneven sample space, as |set|^|set| does not devide exactly by |set|
