CPSC 2600: Foundations of Computer Science : 5 credit class
About
Introduction to logic, applications of logic, methods of proof , sets, functions, induction, recurrence relations, graphs, and counting.
Prerequisites
A C- or better in MATH 1335 and a C or better in either CPSC 1230 or CPSC 1430.
Learning Outcomes
• Transform logical statements into English sentences and vice versa.
• Evaluate logical assertions when defined using predicates and quantifiers.
• Construct logical proofs using a variety of rules of inference.
• Distinguish between induction, strong induction and structural induction.
• Construct proofs using an appropriate form of induction.
• Identify key characteristics of a graph (connectivity, density, weights, cycles).
• Traverse graphs.
• Apply graph coloring to scheduling or resource allocation.
• Establish the correspondence between recurrence relations and functions.
• Define and evaluate sequences and summations.
• Recognize the key differences between counting methods (replacement, arrangement vs selection, inclusion/exclusion).
Methods of Proof
Direct Proof
In a direct proof, you start with the given assumptions or premises and use logical deduction to arrive at the conclusion. You build a logical chain of reasoning from the given information to the desired result. Example
To prove that the sum of two even integers is even:
Assume a and b are even integers.
By definition, an even integer can be expressed as 2k where k is an integer.
So, a = 2m and b = 2n for some integers m and n.
Then, a + b = 2m + 2n = 2(m + n), which is also an even integer.
Proof by Contradiction
Also known as reductio ad absurdum, proof by contradiction assumes the negation of what we want to prove and then shows that this assumption leads to a contradiction. If the assumption leads to a contradiction, then the original statement must be true. Example
To prove that the square root of 2 is irrational:
Assume, for contradiction, that sqr(2) is rational.
Then, sqr(2) = p/q, where p and q are coprime integers.
Squaring both sides, 2 = p^2/q^2.
So. p^2 = 2q^2, which implies that p^2 is even
Since the square of an integer is even if and only if the integer is even, p must be even.
If p is even, then p^2 is divisible by 4.
This implies that q^2 is divisible by 2.
If q^2 is divisible by 2, then q must be even.
But if both p and q are even, they are not coprime, which contradicts our assumption.
Therefore, sqr(2) cannot be rational.
Recurrence Relations
A recurrence relation is a mathematical relationship or equation that defines a sequence recursively in terms of its previous terms. It is a way of describing a sequence of numbers where each term depends on one or more preceding terms.
Recurrence relations are commonly used in various areas of mathematics, computer science, and engineering to model processes that evolve over time or to solve problems involving repeated calculations.
Sets
In discrete mathematics, a set is a fundamental concept used to represent a collection of distinct objects or elements. Sets are used to describe and analyze mathematical structures, relationships, and operations.
Set Operations:
Unions: The union of two sets A and B is the set of all elements that are in A or B, or both.
Intersection: The intersection of two sets A and B is the set of all elements that are in both A and B.
Difference: The difference of two sets A and B is the set of all elements that are in A but not in B, or vice versa.
