🤖 Artificial Intelligence Week 1 of 14 BSc · Y1 ⏱ ~50 min

Week 1: Logic, Proofs & Formal Reasoning

Master the mathematical foundations of AI: propositional logic, predicate logic, set theory, graph theory, combinatorics, and formal proof techniques.

University of America

MATH101_AI — Lecture 1 · BSc Y1

🎬 CC Licensed Lecture

0:00 / —:—— 📺 MIT OpenCourseWare (CC BY-NC-SA)

🎯 Learning Objectives

Write formal proofs by induction, contradiction, and contrapositive
Analyze problems using set theory and Boolean logic
Model problems as graphs and apply graph algorithms
Apply combinatorics to algorithm analysis

Topics Covered This Lecture

Propositional & Predicate Logic

Proof Techniques: Induction & Contradiction

Graph Theory: Paths, Cycles, Trees

Combinatorics & Counting

📖 Lecture Overview

This first lecture establishes the foundational framework for Discrete Mathematics. By the end of this session, you will have the conceptual grounding and practical starting point needed for the rest of the course.

        Why this matters
        Master the mathematical foundations of AI: propositional logic, predicate logic, set theory, graph theory, combinatorics, and formal proof techniques. This lecture sets up everything that follows — make sure you understand the core concepts before proceeding to Week 2.
      

Key Concepts

The lecture introduces the four main pillars of this course: Propositional & Predicate Logic, Proof Techniques: Induction & Contradiction, Graph Theory: Paths, Cycles, Trees, Combinatorics & Counting. Each will be explored in depth over the 14-week curriculum, with hands-on projects reinforcing theory at every stage.

# Quick Start: verify your environment is ready for MATH101_AI
import sys
print(f"Python {sys.version}")

# Check key libraries are installed
try:
    import numpy, pandas, matplotlib
    print("✅ Core libraries ready")
except ImportError as e:
    print(f"❌ Missing: {e} — run: pip install numpy pandas matplotlib")

This Week's Focus

Focus on mastering: Propositional & Predicate Logic and Proof Techniques: Induction & Contradiction. These are the prerequisites for everything in Week 2. The concepts build on each other — do not skip the practice exercises.

📋 Project 1 of 3 50% of Final Grade

MATH101 Project 1: Graph Algorithm Implementation

Implement BFS, DFS, Dijkstra's algorithm, and Kruskal's MST algorithm. Prove the correctness of your BFS implementation using formal induction. Analyze complexity for each.

Python implementations of 4 graph algorithms
Formal correctness proof for BFS (induction)
Complexity analysis with empirical validation
Real-world application writeup (social networks, maps)

50%

3 Projects

20%

Midterm Exam

30%

Final Exam

📝 Sample Exam Questions

These represent the style and difficulty of questions you'll see on the midterm and final. Start thinking about them now.

Conceptual Short Answer

Prove by induction that the sum 1+2+...+n = n(n+1)/2.

Analysis Short Answer

Define a complete bipartite graph K(m,n). How many edges does it have? Prove it.

Applied Code / Proof

How many distinct binary strings of length 8 have exactly 3 ones? Show your work.