# G51 MCS

## Binary expression

| Name | Formula | |
| :--- | :--: | :--: |
| Tautology | $a \lor \lnot a \Leftrightarrow \top$ |
| Contradiction | $a \land \lnot a \Leftrightarrow \bot$ |
| Absorption | $\top \lor a \Leftrightarrow \top$ | $\bot \land a \Leftrightarrow \bot$ |
| Identity | $\bot \lor a \Leftrightarrow a$ | $\top \land a \Leftrightarrow a$ |
| Associativity | $(a \land b) \land c \Leftrightarrow a \land ( b \land c)$ | $(a \lor b) \lor c \Leftrightarrow a \lor ( b \lor c)$ |
| Distributivity | $(a \lor b) \land c \Leftrightarrow (a \land c) \lor (b \land c)$ | $(a \lor b) \land c \Leftrightarrow (a \land c) \lor (b \land c)$

## Glossary

| Word | Definition |
| :--- | :--- |
| Axiom | A proposition that is either proven to be, or is accepted as true. It can be used to build on proofs |
| Claim | A proposition that is said to be true - e.g. $4 \in \mathbb{N}$ |
| Indirect proof | Proving a claim through proving all of its contradictions (other possibilities) are false |
| Direct proof | Proving a claim through proving that it is true |
| Predicate | a proposition whose value depends one one or more variables |
| Proof | A sequence of logical deductions from axioms and other statements which concludes that a proposition is true |
| Proposition | A statement that is either true or false |
| Set | An unordered collection of numbers |
| Tuple | An ordered collection of values |