Mathematical Logic
Some digital systems content, sentinal logic, prediate logic, graph theory
Read: Discrete Mathematics and Its Applications by Kenneth H. Rosen
Notes:
-
We studied sentential logic as part of the course, but it is often referred to as Propositional logic/calculus
-
We also used a system called L arrow which exists in sentential logic (sometimes called language PC)
-
I advise reading the Rosen Discrete Math Book, in the first few hundred pages… it covers most of what the course does.
-
Functionally complete sets that are good to know for exams and homeworks, here is a non exhaustive list of some basic ones
Graphs:
-
In the course, we usually substitute F = number of faces, n = number of vertices, m = number of edges
-
Graph is bipartite iff it only has cycles of even length
-
Any complete graph (a graph in which each vertex is connected to every other vertex) with > 5 vertices is not planar: homeomorph of K5 or K3,3
-
Any complete graph has a hamilton cycle
-
Graph with m >= n-1 edges, n >= 3 vertices will have a cycle
-
Non-Planar Graphs:
K5 - Graph with 5 vertices all realized (complete)
K3,3 - Graph that has 3 vertices on left, 3 on right that is bipartite and complete
Useful Links
Wikipedia Articles relevant to subject
https://en.wikipedia.org/wiki/Propositional_calculus (Sentential Logic, L-> and L2)
https://en.wikipedia.org/wiki/Hilbert_system
https://en.wikipedia.org/wiki/Formal_system#Logical_system
https://en.wikipedia.org/wiki/First-order_logic (For all, There exists, predicate logic)
Calculators and tools
Python and programming aren’t required for the course but its a good way to check your work! and view my sample program for testing logic * here using the SymPy library