Np Or q is the same as p implies q
Precedence of order of operations:
N, And, Or, implies, bi-conditional.
Contradiction is a statement that is always false.
Tautology is a statement that is always true.
Make flash cards of the following:
EquivalenceS:
P and T is congruent to p, which is the identity law
P and F is congruent to F, which is the domination law.
P or p is congruent to p is the idempotent law.
P or q is congruent to q or p is the communatative law
NnP is the double negation law.
P or (q and r) is congruent to (p or q) and (p or r) is the distributive law.
P and (q or r) is congruent to (p and q) or (p and r) is the 2nd distributive law
P or (p and q is congruent to p is the absorption law.
P and (p or q) is congruent to p is the second aborption law
P or (q or r) is congruent to (p or q) or r is the associative law.
De Morgan's law: n(p or q) is congruent to np and nq.
N(p and q) is congruent to np or nq
Difference between predicates and propositional logic is that predicates involve variables,
and statements in any language that do not have clear propositional operands.
Universal and existential quantifies are both used to limit the variables of a proposition.
Universal uses an upside down "A" symbol to say "for all" x for example and then the universe is
usually defined. For example, If x is the universe of students who have studied abroad.
Existential is used to say that there is at least one one student who has satisfied the
function p(x), which could be "has brought with them their text book." The symbol for
existential is a mirrored "E" or a a reversed "E".
An equivalent way to say N(for all x)p(x) holds is there exists a value x such that Np(x).
The order of quantifies matters.
Direct proofs are the kind of proofs that can be done rather easily.
Indirect proofs use propositional logic and operands to manipulate what you are trying to
prove into something that can more easily be proved.
Proof by contradiction works by showing that the statement is false by something rather
absurd.
A Is a subset of b is a subset if and only if every element in a also belongs in b.
CarDinality is expressed like this: |a|. Cardinality is the amount of elements in a set.
SuRjective Is synonymous with onto. This term means all members of the codomain are
used.
One-to-one means all members of the domain map to a unique member of the codomain.
BiJective A function that is one to one and surjective.
Harmonic Series is written as H subscript n, which is 1 + 1/2 + 1/3 + 1/4 + 1/5 +1/6... 1/n.
The series is divergent. On a Cartesian plane, 1/(x + 1) is equal to the y value.
Stirling's formula isn't required to solve some of these problems, however, it can be useful.
Countable set - A set is countable if it's finite or it has the same cardinality as the set of positive
integers.
If a set is countable, one uses an aleph null symbol to describe its cardinality, which looks like
this:
Power set - The power set of {a,b,c} = {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}, {null}. It can be
calculated by 2^e where e is the amount of elements, or cardinality of a set.
Rational number - A rational number is a number that can be written as a fraction of an integer
over an integer.
Big O notation : Programmers use bigO notation to find the lowest amount of steps needed to
finish an algorithm by being conservative. However, bigO is a "ceiling estimate," and you're
supposed to find an estimate that satisfies a number of some value n that is larger or smaller
than a constant that the G(n) is greater than F(n).
Binary search works by finding the midpoint of a list or set. It works by comparing the value that is
sorted from the list to the midpoint, then it halves the list/set. The algorithm then looks at either
the left or right sight, if it's one side then it creates another midpoint and goes again. BigO
runtime is (log(n)), or expected run time.
Bubble sort is when there is swapping between elements that are right next to each other. It does
this throughout the list/set in one pass, then it does the pass again n - 1 times, where n is the
cardinality of the set. BigO of the algorithm is n^2.
Big omega notation works exactly like Big O notation except it is an estimate that is the lower
bound of a function.
Theta notation can only be used when big O and big Omega have to have the same polynomials
but different constants before it.
Divide and conquer - is what linear search uses. The complexity is log(n). Log in computer
science is base 2. Divides a set/list in half, then does a comparison test, then spits out a smaller
list, etc. (Creates a midpoint every time).
Invertible vs. not-invertible functions - The requirement for there to be an invertible function is
that both the domain and codomain have to be functions when in original relationship and
switched. So, if a function starts out as one-to-one, but not onto, it can't be invertible because all
elements of the domain, when inverted, have to be pointed at an element in the co-domain. For
all x in the set of R, f(x) = xsquared, for instance, is not a one-to-one function, yet the inverse is
the squareroot of abs(y) with a plus/minus next to it., which is not one-to-one. Each element of
the original R set is now limited to being 0 or above for it to make any sense.
Tractable - A problem that has polynomial worst-case complexity,
Intractable - Problems that don't fit under that category.
