Discrete Math

Overview of Formal Systems

  • The lesson focuses on numbers and formal systems, leading into Boolean algebra.

Historical Context of Number Systems

  • Review of previously discussed ideas related to number systems.

  • Historical uses of decimal and octal number systems in computing.

  • Computers historically used bits and switches for programming.

  • Early programming example involved flipping switches to input binary data mechanically.

Number System Conversions

  • Converting between bases can be challenging, especially base 10 to base 2 and vice versa.

  • Octal (base 8) is easier because it uses 3 bits to represent numbers:

    • 3 bits can represent numbers from 0 to 7.

Representation of Number Systems in Programming

  • Use of prefixes to denote number bases:

    • Octal: 0 (zero), Hexadecimal: 0x (x marked for hexadecimal), Decimal: typically no prefix.

  • Discussion on how the representations help to avoid confusion (0 versus 'o').

Development of Number Concepts

  • Understanding of zero and negative numbers took time to develop historically.

  • Concepts that may seem natural (like zero) are not obvious or easy to discover.

  • Example of mathematical difficulties is dividing 3 by 2, leading to the creation of new concepts in mathematics.

Examples of Mathematical Systems

  • Brief mention of clock arithmetic displayed as z_12; cycles back after reaching 12.

  • Groups, rings, and fields were defined:

    • A ring allows addition and multiplication but not guaranteed division.

    • Fields allow all arithmetic operations, meaning division is possible.

Introduction to Boolean Algebra

  • Transition from earlier topics to Boolean algebra, which represents truth and falsehood concepts.

  • Example provided regarding logical statements:

    • "It is cold outside and I am a millionaire" - If one part is false, the statement is false.

    • "It is cold outside or I am a millionaire" - If either is true, the overall statement is true.

Logical Operations in Boolean Algebra

  • Logical operations accepted in Boolean algebra: AND, OR, NOT.

  • Symbols used:

    • OR = +

    • AND = ×

    • NOT = bar over the variable (or sometimes a tilde).

Truth Tables in Boolean Algebra

  • Truth table explained for OR operation:

    • 0 + 0 = 0;

    • 0 + 1 = 1;

    • 1 + 0 = 1;

    • 1 + 1 = 1.

  • Truth table for AND operation:

    • 0 × 0 = 0;

    • 0 × 1 = 0;

    • 1 × 0 = 0;

    • 1 × 1 = 1.

Understanding Complement

  • Definition of NOT operation explored:

    • NOT 0 = 1;

    • NOT 1 = 0.

Distinction Between Boolean Algebra and Regular Algebra

  • Highlighted that operations in Boolean algebra are constrained to 0s and 1s, not producing the same flexibility as integers in regular algebra.

  • Example on properties of finite fields that simplify outcomes, e.g., functions in f_2.

Connection with Programming Languages

  • Discussion on representation of Boolean operators in programming, e.g., Python uses True/False, logical keywords for AND, OR, NOT, etc.

  • Emphasis on the idea that Boolean algebra can represent logical expressions effectively even in languages lacking explicit Boolean operations.

Concluding Thoughts on Functional Completeness

  • Concept of functional completeness indicates that combinations of AND, OR, and NOT operations can represent any Boolean function.

  • Recognizing isomorphism: different systems can function similarly under specific constraints (e.g., NASCA cars can turn left despite their structure).

Prepped for Further Learning

  • Intended goal to setup future exploration into formal systems like f_2 and beyond, emphasizing understanding over memorization.