Mathematical Logic

Some digital systems content, sentential logic, predicate logic, graph theory

Read: Discrete Mathematics and Its Applications by Kenneth H. Rosen (not required by the course)

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.
This is not my exhaustive list of notes (& proofs), there are topics not covered in the course on this page, so do not use this as your main source of notes

Logic

Logic symbols (refresher)

Here are some stuff worth knowing (on top of the basic gates/symbols)

a ↑ b = ¬(a ∧ b) = nand
a ↓ b = ¬(a ∨ b) = nor
F = constant false
T = constant true
A ⇒ B
- When A is true and B is false, the sentence gets the False truth value, otherwise it will always get the True truth value
- Called If then, implies, or conditional
A ↔ B = A ⊙ B
if and only if = xnor
(A ⇒ B) ∧ (B ⇒ A)

English to Logic

Sentential Logic Sentence	A ↔ B	A → B	~B → A	~(A → B) = A ∧ ~B	A ∧ B	A ∨ B	A ↑ B	A ↓ B	(A → B) & (~A → C)	(~B → A) & (B → C)

English	A if and only if B	A only if B	A unless B	A is not sufficient for B	A but B	A or (else) B	not the case that both A and B	Neither a nor b	if A, then B, and if not A, then C	if not B, then A, and if B then C
	A just when B	If A then B	A if not B	it is not true that if A then B	A who B	Bring A or B or both			if A, then B; otherwise C	A unless B, in which case C
	If A then B and vis-versa	B if A	unless B,A		A and B	Either A or (else) B
	A is equivelent to B	B because A	if not B, then A		Both A and B	A unless B
		A hence B			Although A, B
		A implies B
		B in case A
		in case A,B
		If A,B
		on condition that A, B
		B on condition that A
		not A if not B
		B is necessary for A
		Only if A are/then B
		B provided that A
		B when A

Predicate Logic Sentence	∀x	∃x	¬(∃x…)	¬(∀𝑥 … )	∀𝑥 𝑃 (𝑥) → 𝑄(𝑥)	∃𝑥 𝑃 (𝑥) ∧ 𝑄(𝑥)	(∃x (∃y ((B(x) ∧ B(y)) ∧ x ≠ y)))	(∀x (∀y ((B(x) ∧ B(y)) → (x = y))))	((∃x B(x)) ∧ (∀x (∀y ((B(x) ∧ B(y)) → (x = y)))))
								(¬(∃x (∃y ((B(x) ∧ B(y)) ∧ (x ≠ y)))))	(∃x (B(x) ∧ (∀y (B(y) → (x = y)))))
English	Every x	Exists x	None	Not every x	Every P-ish x has property Q	Some P-ish x has property Q	There are at least two X’s		There are exactly one x
	For all x	At least one x	No x	Not all				There are at most one x
	Each x	Some x
	Any x	There is a x
		Thesere exists a x
		One or more

Functional completeness

Any functionally complete set of logical symbols (gates) can be used to create any other gate
Functionally complete sets that are good to know for exams and homeworks, here is a non exhaustive list of some basic ones
AND, OR, NOT : {∧, ∨, ¬}
NAND : {↑}
NOR : {↓}
AND, NOT : {∧, ¬}
OR, NOT : {∨, ¬}
and here are some additional ones
IMP, NOT : {⇒, ¬}
XOR, IMP : {⊕, ⇒}
AND, BIDIRECTIONAL, FALSE : {∧, ↔, F}
OR, BIDIRECTIONAL, FALSE : {∨, ↔, F}

Graphs:

Word	Definition	Notation
Graph	Set of vertices and set of edges	G=(V,E)
Vertex	Unique node	v ∈ V
Edge	Pair of 2 vertices (linked)	e ∈ E
Adjacent vertices/Neighbors	f there is an edge from one vertex to the other ie v-u or v<->u, so v and u are adjacent to each other … but v->u v is adjacent to u but u isn’t adjacent to v
Degree	Number of edges touching that vertex (in undirected graph)	d(v)
in-degree	number of edges coming into vertex vx… ie v3->vx->v2 , vx has in-degree of 1 (from v3 coming in) (directed graph)	Din(v)
out-degree	number of edges leaving vertex vx (directed graph)	Dout(v)
Connected vertices	In an undirected graph, an unordered pair of vertices {x, y} is called connected if a path leads from x to y. Otherwise, the unordered pair is called disconnected. (path exists between them)
Path	sequence of vertices connected by edges.	{v1,….,v4}
Cycle	A cycle is a path that starts and ends at the same vertex.	{v1,v2,…v1……..vn, v1}
Simple path	path that doesn’t repeat any vertices
Simple Cycle	A simple cycle is a cycle that repeats no vertices except that the first vertex is also the last (in undirected graphs, no edge can be repeated)
Euler path	Path that uses every edge of graph exactly once
Euler cycle	a cycle that uses each edge exactly once (undirected graph)
Hamilton path	path that visits each vertex exactly once - tracable
Hamilton cycle	cycle that visits each vertex exactly once
Depth	# of edges in path from root to that node
Distance	length of shortest path having vertices v,u at the endpoints
Diamater	in connected graph it is maximum length of shortest path - max of distances between pairs of vertices in graph
Path length	# of edges in a path
Component	subset ov vertices Vi ⊆ V
Connected component	subset ov vertices Vi ⊆ V tat is connected

Graph Atttrbutes
Undirected Graph	{v1,v2} = {v2,v1} … if v1 shares an edge with v2 (we draw a line for the edge)
Directed Graph	(v1,v2) means v1 -> v2 … but we cannot go from v2 -> v1 unless another edge exists (v2,v1)
Subgraph	A subgraph of a graph G is a graph whose vertices and edges are subsets of the vertices and edges of G, respectively	H ⊆ G
Induced Subgraph	An induced subgraph of a graph G is a subset of vertices V’ and all edges whose endpoints are both in V’	G[V’].
Simple	a graph that does not contain more than one edge between the pair of vertice
Complete	each pair of vertices is joined by an edge. A complete graph contains all possible edges.
Regular	each vvertex has same degree
K-regular	regular graph where each vertex has degree K
Bipartite	a graph where the vertices can be divided into two disjoint sets such that all edges connect a vertex in one set to a vertex in another set. There are no edges between vertices in the disjoint sets.
Planar	A planar graph is a graph that can be drawn in the plane without any edges crossing.
Complete bipartite	a special bipartite graph where every vertex on one side of the bipartition is connected to every vertex on the other side
Clique	a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. an induced subgraph of G that is complete.
Peterson graph	nonplanar, hamiltonian path, no hamiltonian cycle
Connected	if, for each pair of vertices, there exists at least one single path which joins them
Acyclic	a graph with no cycles
Hamiltonian-connected	if for every pair of vertices there is a Hamiltonian path between the two vertices.
DAG	Directed graph wihtout any directed cycles
Tree	Connected and acyclic or add edge = makes a cycle, or remove edge disconnects graph
K_n	Complete graph on n vertices
Cycle graph	a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain.
C_n	Cycle graph on n vertices (	n	= # ov vertices = # edges in this case)
K_a,b	is a bipartite graph that consists of two disjoint sets of n vertices each, with every vertex in the first set connected to every vertex in the second set. In other words, if we have two sets of vertices U and V, each with n vertices, then _a,b has an edge between every pair of vertices u ∈ U and v ∈ V.
G^c	a graph G’ (complement) on the same set of vertices as of G such that there will be an edge between two vertices (v, e) in G’, if and only if there is no edge in between (v, e) in G	G’(v, e’)
G^T	a graph G^T (transpose) where V is the same set of vertices as in G, but E^T is the set of edges E but with directions reversed (directed graph), if e = (v,u), e^T = (u,v)	G^T = (V, E^T )

More graph properties:

In the course, we usually substitute F = number of faces, n = number of vertices, m = number of edges (important for formula sheet)
Graph is bipartite if and only if all cycles have even length
K₅ - Graph with 5 vertices all realized (complete)

$K5 graph$

K_3,3 - Graph that has 3 vertices on top, 3 on bottom that is bipartite and complete (sometimes split left and right)

$K3,3 graph$

Any complete graph (a graph in which each vertex is connected to every other vertex) with > 5 vertices is not planar: it is homeomorphic of K₅ or K_3,3
Any complete graph has a Hamilton cycle
Graph with m >= n-1 edges, n >= 3 vertices will have a cycle
Regular graph = each vertex has the same degree (same number of edges touching it)
A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path.
Q_n - graph of n-dimensional hypercube
- is bipartite
- Always has 2ⁿ vertices, n2^n-1 edges
  - it is a regular graph, each vertex has degree of n
- for even n, it will have a Euler cycle
- for graph with n > 1
  - has Hamiltonian cycle
  - is planar (iff 1 < n <= 3)
- Q3 is a cube, higher dimensions are harder to visualize

Good to know

Implication: A ⇒ B

A implies B (If A then B)
- A ⇒ B is false when A is true and B is false, but otherwise it’s true

Meta-Deduction: A ⊢ B

A proves B
- B can be proved using A as premise
⊢ A
- A is a tautology (every premise can deduce A)

Meta-implication: A ⊨ B

A entails B
- B is true in every structure where A is true
- In every model, it is not the case that A is true and B is false

Terms you may see elsewhere

First order logic = Predicate logic (For all, There exists)

If A ⊢ B then A ⊨ B (soundness theorem)
If A ⊨ B then A ⊢ B (completeness theorem)

Propositional logic = Sentential Logic (L arrow and L2)

Cycle = Circuit = Tour

Path = Trail

Edge = Arc

Course Links

Useful Links

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 April 2, 2024

CS Resources

Computer Science Resources and Links from Avi Parshan