discrete maths

Question 1

propositional logic

Answer 1

a sentence declaring a fact that is either true or false

Question 2

compound proposition

Answer 2

compound propositions are formed for other propositions using logical operators

Question 3

negation (¬)

Answer 3

it is not the case that

Question 4

conjunction (n)

Answer 4

the proposition that two propositions are both true else false

Question 5

disjunction (v)

Answer 5

the proposition that either or both propositions are true

Question 6

truth tables

Answer 6

gives the truth values of a compound proposition for all combinations of inputs

Question 7

short circuit evaluation

Answer 7

in python some boolean operators will only execute the second condition if the first does not determine the value of the expression

Question 8

exclusive or (⊕)

Answer 8

the proposition that either of the propositions are true not both

Question 9

implication (=>)

Answer 9

the proposition of if a hypothesis then conclusion, only false if hyp true and con false

Question 10

contrapositive

Answer 10

p => q is the logical equivalent of ¬q => ¬p

Question 11

converse

Answer 11

p => q is not the logical equivalent of q => p

Question 12

biconditional (<=>)

Answer 12

the proposition that both propositions have equivalent values

Question 13

truthologies

Answer 13

a compound proposition that is always true ie p v ¬p

Question 14

contraditions

Answer 14

a compound proposition that is always false ie p n ¬p

Question 15

logical equivalence (≡)

Answer 15

compound statements are logically equivalent if they share identical truth tables

Question 16

known logical equivalence rules

Answer 16

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, ¬(¬𝑝) ≡ 𝑝

Question 17

ℕ, ℤ, ℚ, ℝ,

Answer 17

ℕ = 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))

Question 18

set notation - enumeration

Answer 18

listing all members of the set ie. A ∈ {1,2,3,4,…,n}

Question 19

set notation - set builder

Answer 19

set is defined using variables and logical statements ie A ∈ {x: x > 0} where x is an integer

Question 20

𝕌

Answer 20

a set containing all the related values without any repititions

Question 21

compliment

Answer 21

𝐴 = 𝕌 − 𝐴

Question 22

power set - 𝒫(𝑆)

Answer 22

a set containing all possible combinations of the elements of s from cardinality of 0 to |s|

Question 23

Cartesian product

Answer 23

A * B, { 𝑎, 𝑏 : 𝑎 ∈ 𝐴 𝑎𝑛𝑑 𝑏 ∈ 𝐵}

Question 24

partition of a set

Answer 24

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)

Question 25

functions

Answer 25

mapping a to b such that each member of a is matched to a single member of b

Question 26

injective function

Answer 26

|A| <= |B|, not all elements of B will necessarily be mapped to a member of A

Question 27

surjective function

Answer 27

|A| >=|B|, Elements of B may map to more than one element of A

Question 28

bijective function

Answer 28

|A| =|B|, both injective and surjective

Question 29

א

Answer 29

smallest cardinality of an infinate set

Question 30

permutations

Answer 30

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

Question 31

combinations

Answer 31

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)

Question 32

Permutations with indistinguishable objects

Answer 32

when a set contains members that appear the same the permutations is n! / (n1! * n2! * ... * nk!)

Question 33

product rule

Answer 33

|A1 * A2 * ... * An| = |A1| * |A2| * ... * |An| 𝑃 (𝐴 ∩ 𝐵) = 𝑃( 𝐴| 𝐵) 𝑃( 𝐵) = 𝑃( 𝐵|𝐴) 𝑃(𝐴)

Question 34

sum rule

Answer 34

for S {s1, s2, ..., sn}, |S| = |s1| + |s2| + ... + |sn| 𝑃 (𝐴 ∪ 𝐵) = 𝑃( 𝐴) + 𝑃 (𝐵) − 𝑃( 𝐴 ∩ 𝐵)

Question 35

probability with equally likely outcomes

Answer 35

P(E) = |E| / |S| where S is the sample space (all possible outcomes) and E is a subset of S

Question 36

probability of compliment

Answer 36

p(¬E) = 1-p(E)

Question 37

independent

Answer 37

P(A and B) = P(A) * P(B)

Question 38

disjointed(mutualy exclusive)

Answer 38

p(A or B) = P(A) + P(B)

Question 39

conditional probability

Answer 39

P(A|B) = P(A and B) / P(B)

Question 40

pigeon-hole principle

Answer 40

to put n+1 items in n boxes, at least one box must have more than one items in it

Question 41

fisher yates shuffel

Answer 41

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

Question 42

direct proof

Answer 42

hypothesis -> deduction -> conclusion

Question 43

proof by case

Answer 43

case1: hypothesis _> deduction -> conclusion case2: hypothesis -> deduction -> conclusion ect

Question 44

proof by counter example

Answer 44

one counter example -> disproof of universal statement

Question 45

proof by contradiction

Answer 45

suppose not: ¬p derive contradiction conclude: ¬p is false therefore p is true

Question 46

proof by contraposition

Answer 46

write statement into p=> q suppose ¬q derive ¬p conclude: ¬q=>¬p and it is equivalent to p=>q

Question 47

proof by induction

Answer 47

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

Question 48

alternative shuffle

Answer 48

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|