dmlab-lawchain

About dmlab-lawchain

Source code

MIT License

Laboratory works

Step-by-step solutions: truth tables, laws of logic, predicates, sets, relations, functions, Boolean functions and the Hamming code

Propositional and predicate logic

  1. 1.1Truth table and simplificationBuild the table, reduce to ¬ ∧ ∨
  2. 1.2Counterexample methodTautology check with a counterexample
  3. 1.3Equivalence of formulasTables, laws, combined method
  4. 1.4Predicates and quantifiersQuantifiers on the domain {a, b}

Computer representation of sets

  1. 2.1Vectors, sets, diagram, power setMembership table, diagram, power set
  2. 2.2Simplifying an expression by lawsShorten an expression step by step
  3. 2.3Inclusion–exclusionCounting with overlapping sets

Properties of relations and functions Coming soon

  1. 3.1Properties and type of a relationMatrix, properties, equivalence, order, tolerance
  2. 3.2Operations on relationsInverse, complement, set operations, composition
  3. 3.3Properties of a functionInjective, surjective, bijective; fixing a function

Boolean algebra Coming soon

  1. 4.1Truth table, PDNF and PCNFA function given by the numbers of its assignments
  2. 4.2Karnaugh mapsMinimal DNF and CNF
  3. 4.3The McCluskey methodPrime implicants and the reduced DNF
  4. 4.4The implicant tableDead-end and minimal DNFs: exhaustive search and Petrick's method
  5. 4.5The Hamming codeEncoding, correcting one error, detecting more

Graph theory Coming soon

  1. 5.1Traversals, connectivity, Euler cyclesDFS and BFS, vertex and edge connectivity, an Euler cycle or walk
  2. 5.2The nearest-neighbour algorithmA Hamiltonian cycle in a weighted graph
  3. 5.3A digraphMatrices and lists, connectivity, Euler and Hamilton contours and paths
  4. 5.4The reachability matrixPowers of the adjacency matrix and Warshall's algorithm
  5. 5.5Dijkstra's algorithmShortest paths and the shortest-path tree

Applications of trees Coming soon

  1. 6.1Kruskal's algorithmA minimum spanning tree of a weighted graph
  2. 6.2A tree from its Pruefer codeDecoding a Pruefer code step by step
  3. 6.3An expression treeThe binary tree of an expression, Polish and reverse Polish notation, evaluation
  4. 6.4BacktrackingHamiltonian cycles and walks, a colouring with the fewest colours, search trees