Maths Logic

Proposition is a statement that can be true or false

• ¬ not
• ^ and
• v or
• -> if-then (implication)
• <-> if-and-only-if logicaly((a->b)^(b->a))

• Tautology, Where a statement will always be true
• Contradiction, Where a statement will alwaus be false
• Contingency, Where a statement can be true or false, depending on inputs.

Functions

A function is where every input has exactly 1 or 0 outputs

The identity function is where the input = the output.

A total function is where every possible item in the domain can be input in to the function

A partial function is where not every element in the domain can be input in to the function

injective: Where no two inputs to a function give the same output

surjective: where all elements in the co domain can be given by the output of the function

bijective: where a function is both injective and surjective.

Rules

• x E A -> x is an element of set A
• A set can be infinitely long
• Elements of a set have a relationship or follow a rule
• Sets don’t have to be ordered
• Sets don’t contain same element twice
• :,| -> such as
• R -> Set of real numbers
• N -> Set of natural numbers (positive whole inc. 0)
• Z -> Set of integers
• Q -> set of rational numbers (fractions)
• 0/ -> empty set
• Cardinality, |A| -> number of elements in the set
• Subset -> set of number where all elements are found in another set
• Proper subset -> subset but only if both sets are NOT equal
• Intersection -> all elements in both sets
• Disjointed if intersection is a null set
• Union -> all elements in both sets
• Difference -> all elements in one set that aren’t in another

Rules

• Ordered pair -> a set where the order matters
• Cartesian product -> all the possible ordered pair matches of two sets
• Relation -> set of ordered set between A and B based on a rule
• A relation doesn’t need to contain all the possible pairs
• Binary relationship -> where the relation is a subset of Cartesian A B
• Can use nodes to depict relation between the pairs using directed arrows
• Reflexive -> Each element in A is in the relation paired with itself
• Symmetric -> Each pair and its’ reverse are in the relation
• Transitive -> iff (x,y) (y,z) hence (x,z) based on rule defining relation then transitive
• Equivalence -> relation is reflexive, symmetric and transitive
• Equivalence set -> all elements pair with set element in equivalent relation

Orderd Pairs

Cartesian Producut of A and B is the set of all possible orderd pairs (where Elements from A come before B)

You can define a relation between two sets using rules, involving the Cartesian product.

Binary relation "T" from A to B is a list of possible (but not all possible) Orderd pairs that follow a rule

LET "R" BE A BINARY RELATION ON A SET A!!!

Reflexivity

Where for every element in the set A, there is a orderd pair where both values are the same value as the element in A

Symetry

Where for each element in the Relation R, there is a symetric element, where the values in each pair are swapped. eg. (1,4), (4,1)

Transistivity

Where two Orderd Pairs (1,2) (2,3) can be imagined as a path, and the Binary Relation R also contains an element (1,3) that simplifies the path.

Equivelence

Equivelence is where R is Reflexive, Symetrical, and Transitive.

Haskell Basics

Haskell does not have loops, it has if statements, expressions, and functions only. If you need to do loops, you have to use recursion, or ther techniques (learned in following weeks).

Example Function

function1 :: Int -> Int

function1 x = x ^ 2

This function for example will take an Int input, square it, and then give the output as an Int.

There are many different styles of proramming (paradimes)

• Imperitive

• Computation contains statements and program states (varialbles)<

• Procedural

• Normal linear programing using methods and variables

• Object Oriented

• Similar to Procedural, but has objects, which can contain functions and variables

• Declarative

• No statements
• No Program states

  Functional (eg. Haskell)

• No state changes are allowed, no changing variables.

  Logic (eg. Prolog)

• Sets of sentences, containing rules about the problem to be solved.

Discrete Mathematics Rules

• A set is a collection of elements
• Sets have no repeated elements
• The order of elements in a set is irrelevent
• The set A containing the elements 1, 2 and 3 is noted as A={1,2,3}

• Special cases:

• R is the set of Real Numbers (all numbers)
• N is the set of Natural Numbers, (integers greater than and including 0)
• I/Z is the set of Integer Numbers, (all whole numbers, positive and negative)
• Q is the set of Rational numbers, (all fractions, expresed by only integers)

• More Rules

• Only Sets can be Subsets, elements cant be subsets!
• Cardinality is the number of elements in a set
• Partition is a collection of non-empty subsets, where all elements are unique.
• Power Set Z is the collection of all possible subsets of Set Z. Should contain 2^(number of elements in the origional set)
• The Complement of a set is another set containing all elements of the universe that are not present in the origional set.
• The Union of two sets contains all elements that are in both sets.
• The Difference of two sets A and B contains all elements present in set A, that are not present in set B.
• The Intersection of sets contain only the elements that every set contains.