If the first domino falls and each domino knocks over the next, they all fall. That is the logic of the Principle of Mathematical Induction. We will see the structure of the proof (base case, hypothesis and step) in sums, divisibility and inequalities, and the false proof that all horses are the same color.
Union, intersection, difference, and complement are the basic operations on sets, and they show up in SQL as UNION, INTERSECT, and EXCEPT. We see each one in Venn diagrams, along with De Morgan’s laws, distributivity, and the difference between a Venn diagram and an Euler diagram.
The collection of tall people is not a set: there is no criterion that decides, for any person, whether they belong or not. We define set, membership, roster and set-builder descriptions, equality, inclusion, and the power set.
In how many ways can you choose a valid password? What is the shortest path between two cities? These are questions of discrete mathematics. This roadmap introduces the site’s four series on the topic: sets, induction and recurrence, combinatorics, and graphs, with 28 articles.
How do we go from a truth table to the leanest Boolean expression? We show three paths: the canonical forms with minterms and maxterms, algebraic simplification, and the Karnaugh map, with worked exercises and a check in Python with SymPy.
Every operation of a processor can be described with three logical operations: AND, OR and NOT. We go from gates and truth tables to theorems, De Morgan’s laws and the simplification of expressions, with the half adder as the first circuit and examples in Python.
Why doesn’t 0.1 plus 0.2 give 0.3? Because 0.1 is a repeating fraction in binary. We convert fractions between bases by successive multiplications, look at the bits of a float with struct, and see two practical ways out: integers for money and math.isclose for comparisons.
In Python, 5 and 6 returns 6, and 5 & 6 returns 4. We explain the difference and the bitwise operators AND, OR, XOR, NOT and the shifts, used in masks that check, set, clear and toggle bits. In the end, we see where the 755 in chmod comes from.
The addition and subtraction rules of base 10 hold in any base: only the value that triggers the carry changes. We do arithmetic in binary, octal, and hexadecimal, see why with three addends the carry can be worth 2, and implement both algorithms in Python.
In any base, the value of the base itself is written 10. We start from positional notation to convert integers between decimal, binary, octal, and hexadecimal, using expansion, successive divisions, bit grouping, and Python’s bin, oct, hex, and int functions.
In programming, the word “logic” can refer to the process of designing an algorithm, to the conditional structures of the language, or to logical operators such as AND and OR. In the last two cases, we are within what is called mathematical logic.
The and and or operators are short-circuit operators, meaning that the second operand is only evaluated if the result cannot be determined from the value of the first operand alone. Confusing? Let’s look at some examples in this article.
