CS Resources

Computer Science Resources and Links from Avi Parshan

View project on GitHub

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

Functionally complete sets

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)

K5 graph

K3,3 - Graph that has 3 vertices on left, 3 on right that is bipartite and complete

K3,3 graph

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

Updated on March 14, 2024