This website houses notes from my studies at the University of Liverpool. If you see any errors or issues, please do open an issue on this site's GitHub.
Extended Pigeonhole Principle Consider a function $f:A\rightarrow B$ where $A$ and $B$ are finite sets and $\vert A\vert >k\vert B\vert$ for some natural number $k$. Then, there is a value of $f$ which occurs at least $k+1$ times. graph TD subgraph A a b c d e f g end...
Cardinality of Finite Sets and Functions The cardinality of a finite set $S$ is the number of elements in $S$. A bijection $f:S\rightarrow\{1,\ldots,n\}$. This means that there are as many elements in the set that $S$ maps to as there are in $S$. For finite sets $A$ and $B$: $\vert...
How to Describe Data The ER model describes data in terms of: Entities A thing which can be distinctly identified Attributes A property of an entity. Relationships An association among entities. erDiagram CUSTOMER ||--o{ ORDER : places ORDER ||--|{ LINE-ITEM : contains CUSTOMER }|..|{ DELIVERY-ADDRESS : uses Attempt a data...
The meeting takes place if all members have been informed in advance, and it is quorate. It is quorate provided that there are at least 15 people present. Member will have been informed in advance if there is not a postal strike. Consequence: If the meeting does not take place,...
A propositional formula is satisfiable if there exist an interpretation under which it is true. Example 1 The formula $(p\wedge\neg p)$ is not satisfiable, because: \[I(p\wedge\neg p)=0\] for all interpretations $I$: $p$ $\neg p$ $(p\wedge\neg p)$ 1 0 0 0 1 0 As you can see from the table there...
An interpretations $I$ assigns to every atomic proposition $p$ a truth value: \(I(p)\in\{0,1\}\) This means: If $I(p)=1$, then $p$ is called true under the interpretation $I$. If $I(p)=1$, then $p$ is called false under the interpretation $I$. Given an assignment $I$ we can computer the truth value of compound formulas...
for many purposes, rules are not expressive enough. for example: You cannot express that something is not the case: $\text{not FrenchFootballClub(LiverpoolFC)}$ You cannot connect sentences using or: $\text{Today, I will do the AI exercise or}$ $\text{I will play football.}$ A proposition is a statement that can be true or false,...
filter filterkeeps only the elements for which f returns True. filter' :: (a -> Bool) -> [a] -> [a] filter' _ [] = [] filter' f (x:xs) | f x = x : rest | otherwise = rest where rest = filter' f xs filter' even [1..10] > [2,4,6,8,10] In...
map map applies a funciton f to every element in a list. map' :: (a -> b) -> [a] -> [b] map' _ [] = [] map' f (x:xs) = f x : map' f xs This saves you from writing out the generic code for applying a function to...
Injective (one-to-one) Functions Let $f:A\rightarrow B$ be a function. We call $f$ and injective, or one-to-one, function if: \[f(a_1)=f(a_2)\Rightarrow a_1 = a_2 \text{ for all } a_1,a_2\in A\] This is logically equivalent to $a_1\neq a_2 \Rightarrow f(a_1) \neq f(a_2)$ and so injective functions never repeat values. In other words: Different...