Unit I: Propositional Logic and

Proof Theory
This unit explores the fundamental concepts of propositional logic and proof theory,
laying the groundwork for mathematical reasoning and formal proofs. We will cover the
essentials of sets, set operations, and logical connectivity, highlighting their crucial
importance in computer science and advanced mathematics.
Sets and Set Operations
A set is formally defined as a well-defined collection of distinct objects, called elements. The order of elements within a set does not matter, and each
element appears only once.

Key operations allow us to manipulate and combine sets:

Union (∪): Combines all elements from two or more sets.

Intersection (∩): Contains only the elements common to all sets involved.

Difference (−): Includes elements present in one set but not in another.

Complement: Elements not in a given set, but within a universal set.

Sets can be classified as finite (with a countable number of elements) or infinite (such as the set of natural numbers).

Example: If Set A = {1, 2, 3} and Set B = {2, 3, 4}, then A ∪ B = {1, 2, 3, 4}.
Finite and Infinite Sets
Understanding the distinction between finite and infinite sets is crucial in set theory:

Finite Sets: These sets have a countable number of elements. For instance, the set of days in a week ({Monday, Tuesday, ..., Sunday}) is a finite set with a
cardinality of seven.

Infinite Sets: These sets contain an endless number of elements. They can be categorised into two types:

Countably Infinite Sets: Elements can be put into a one-to-one correspondence with the natural numbers (e.g., the set of all integers, ℤ).

Uncountable Sets: Elements cannot be put into a one-to-one correspondence with the natural numbers (e.g., the set of real numbers, ℝ, between 0 and
1).

The cardinality of a set measures its size, even for infinite sets where it denotes the "number" of elements.

Example: The set of natural numbers (ℕ) is countably infinite, while the set of real numbers ( ℝ) is uncountable.
Venn Diagrams and Set Visualization
Venn diagrams provide a powerful graphical representation for understanding the relationships between sets. These diagrams typically use overlapping
circles, where each circle represents a set, and the overlapping regions denote common elements or intersections.

They are indispensable tools for illustrating various set operations:

Union: The entire area covered by all circles represents the union.

Intersection: The overlapping area between circles depicts the intersection.

Complement: The area outside a specific circle but within the universal set boundary shows the complement.

Difference: The part of one circle that does not overlap with another illustrates the difference.

For example, in a Venn diagram with two sets A and B, the area where the circles overlap signifies A ∩ B.
Principle of Inclusion and Exclusion
The Principle of Inclusion and Exclusion (PIE) is a counting technique used to determine the size of the union of multiple sets, especially when there are
overlaps. It ensures that elements belonging to multiple sets are counted precisely once, preventing over-counting.

Formula for Two Sets:

• This formula calculates the total number of unique elements by summing the sizes of individual sets and then subtracting the size of their intersection
(to correct for elements counted twice).
• The principle can be extended to three or more sets, becoming more complex as the number of sets increases, requiring the addition and subtraction
of intersections of various combinations.

Example: To count students enrolled in either the Drama Club (D) or the Debate Society (B), or both: |D ∪ B| = |D| + |B| − |D ∩ B|. This accounts
for students who are members of both clubs.
Multisets
A multiset is a generalisation of a set that allows elements to appear multiple times. Unlike a standard set, where each element is unique, a multiset
records the multiplicity of each element.

Multisets are particularly useful in fields such as combinatorics, where the frequency of items is significant, and in computer science, for data structures
and algorithms that handle repeated occurrences.

Key Differences from Sets: Operations on Multisets:

• In a set, {a, a, b} simplifies to {a, b}. Operations like union, intersection, and difference can also be applied to
• In a multiset, {a, a, b} is distinct from {a, b} due to the repeated 'a'. multisets, but they must consider the multiplicities of the elements:

• The multiplicity of an element is the number of times it occurs in the • Multiset union involves taking the maximum multiplicity of each
multiset. element.
• Multiset intersection involves taking the minimum multiplicity of
each element.
Propositions and Propositional Logic
In propositional logic, a proposition is a declarative statement that is definitively either true or false, but not both. It forms the basic building block of
logical reasoning.

We distinguish between two types of propositions:

Atomic Propositions: These are the simplest, indivisible statements that cannot be broken down further without losing their truth value. For example,
"The sun is hot" or "2 + 2 = 4".

Compound Propositions: These are formed by combining two or more atomic propositions using logical connectives (also known as logical operators).
For instance, "It is raining AND the sky is grey".

To simplify logical expressions, we use propositional variables (typically p, q, r, etc.) to represent atomic propositions. This allows us to abstract and
analyse complex logical structures more effectively.

Question: Is "What time is it?" a proposition? No, because it is a question and does not have a truth value.
Logical Connectives and Truth Tables
Logical connectives are symbols or words used to combine propositions, forming more complex statements. Each connective has a specific truth value defined by a
truth table.

Common Logical Connectives:

Conjunction (∧): "and" Disjunction (∨): "or" Negation (¬): "not"

p ∧ q is true only if both p and q are true. p ∨ q is true if p is true, or q is true, or both are true. ¬p is true if p is false, and vice versa.

Implication (⇒): "if...then..." Biconditional (⇔): "if and only if"

p ⇒ q is false only if p is true and q is false. p ⇔ q is true if p and q have the same truth value.

Truth tables systematically list all possible truth value combinations for atomic propositions and the resulting truth values for the compound proposition. For
instance, the implication p ⇒ q is logically equivalent to ¬p ∨ q.
Conditional Propositions and Reasoning
A conditional proposition, often expressed as "If p then q" (symbolised as p ⇒ q), is a cornerstone of logical reasoning. Here, 'p' is the hypothesis (or
antecedent), and 'q' is the conclusion (or consequent).

Its truth value is only false when the hypothesis 'p' is true, and the conclusion 'q' is false. In all other scenarios (true hypothesis and true conclusion, false
hypothesis and any conclusion), the conditional is considered true.

One of the most fundamental rules of inference based on conditional propositions is Modus Ponens:

If p is true, and "if p then q" is true, then q must also be true.

This rule forms the basis for valid deductive arguments and is widely applied in formal proofs, automated reasoning systems, and the design of logical
circuits. Understanding conditional propositions is essential for constructing and evaluating logical arguments in proof theory.
Summary and Connections
The concepts introduced in Unit I—sets, set operations, propositions, and logical connectives—form the bedrock of discrete mathematics and provide
foundational tools for advanced reasoning in various disciplines.

Foundational Synergy: Applications in Computer Science:

Set theory and propositional logic are deeply intertwined, sharing the These principles have extensive real-world applications:
underlying algebraic structure of Boolean algebra.
Algorithms: Designing efficient algorithms relies heavily on logical
• This connection allows for the application of logical operations to sets
structures and set manipulations.
and vice versa, enabling powerful problem-solving techniques.
Digital Circuits: The design and analysis of computer hardware circuits are
Proof Theory: based on propositional logic and Boolean algebra.

• Artificial Intelligence (AI): Logic programming, knowledge representation,

Proof theory formalises the process of deductive reasoning using
and automated reasoning in AI systems are built upon these foundational
propositions.
concepts.
• It establishes rules of inference (like Modus Ponens) and logical
Database Systems: Set theory underpins relational databases, while logical
equivalences to construct valid arguments and ascertain the truth of
queries are crucial for data retrieval.
complex statements.

These concepts are indispensable for anyone pursuing studies or careers in computer science, mathematics, and related logical fields.