Logic and Set Theory Basics

In the previous chapters, we introduced algebra, functions, and geometry, all of which focus on "numbers" and "figures."

In this chapter, we will deal with something more fundamental:How to describe "conditions"(logic),How to describe "a collection of things"(set theory).

In machine learning, almost all content involving "probability" and "uncertainty" is fundamentally expressed in set theory; all content involving "conditional judgments" and "algorithm flows" is fundamentally expressed in logic.

Basic logical operations: AND, OR, NOT, IMPLIES

Logical AND (AND, symbol ∧)

is true if and only if p and qare both true。

Intuition: the two conditions must be satisfied at the same time; if either one is missing, it won't work—just like "you get wet only if it rains and you don't have an umbrella."

Logical OR (OR, symbol ∨)

is true as long as p and qat least one of them is true。

The "or" in mathematics is an "inclusive or": when both are true, the whole statement is also true. It does not mean "either/or" in everyday speech.

Logical NOT (NOT, symbol ¬)

It simply flips the truth value of p: when p is true,it is false; when p is false,it is true.

Logical implication (IMPLIES, symbol ⇒)

Read as "if p, then q", it is the one most likely to go against intuition:

The two most counterintuitive rows: when p is false, no matter what q is,is judged astrue。

An example to help understand: "If it rains tomorrow (p), I'll bring an umbrella (q)."

If tomorrowdoes not rain(p is false), then no matter whether you bring an umbrella or not, you cannot say the statement is "false"—it simply makes no promise about the "no rain" situation.

Logical equivalence (IFF, symbol ⇔)

Read as "p if and only if q", meaning p and q always have the same truth value (either both true, or both false).

Click the switches below to personally "light up" each combination and observe the results of the four operations.

Why these symbols are important for AI

When reading algorithm pseudocode and conditional judgments in model training (such as the trigger condition for "early stopping"), these are all combinations of logical expressions.

A decision tree model is essentially composed of layers of "if...then..." (implication) judgments.

Many theorems in probability theory make extensive use of logical operations to describe relationships between events during proofs.

Executing the above code yields the following output:

p      q      p∧q    p∨q    ¬p     p⇒q
True True True True False True
True False False True False False
False True False True True True
False False False False True True

The second row is that unique "false": p true, q false, the implication does not hold.

Set concepts: intersection, union, subset

What is a set?

A set is a whole made up of "a bunch of definite things", for examplerepresents the set containing the three elements 1, 2, 3.

Subset

If every element in set A is also an element of set B, then A is B'ssubset, denoted as。

For example, then。

Union, intersection, difference, complement

design：

Correspondence between set operations and logical operations

Set theory and logical operations are actually "two languages for the same thing":

This is also why these two sections are placed in the same chapter: they are two expressions of the same underlying logic.

Click the button to switch set operations and see the highlighted areas in the Venn diagram.

The output after running the above code is:

{1, 2, 3, 4, 5, 6, 7}
{4, 5}
{1, 2, 3}
{1, 2, 3, 6, 7}
{6, 7, 8, 9, 10}

Why probability theory is built on set theory

Events are sets

An "event" in probability theory is essentially a set: the set of all "possible outcomes" that satisfy a certain condition.

For example, when rolling a die, the set corresponding to the event "rolling an even number" is。

Probability operations directly correspond to set operations

Addition formula: inclusion-exclusion principle

The geometric intuition of this formula: the overlapping part of two circles is counted twice, so it needs to be subtracted once.

This can be seen very intuitively using a Venn diagram (a graphical representation of sets).

Conditional probability

It is read as "the probability of A occurring given that B has already occurred."

Intuition: once we know B has occurred, the "universe" under discussion shrinks from the original U to B.

At this point, the probability of A occurring is naturally the proportion of "the intersection of A and B" in the "new universe B".

The prototype of Bayes' theorem

Conditional probability can also be written in reverse:

Rearranging this, we obtain the core formula of Bayes' theorem:

It is the theoretical foundation of many machine learning models (such as the naive Bayes classifier), and its derivation starts precisely from the simple set intuition that "conditional probability is the proportion of a set intersection."

The classic disease detection problem best demonstrates the power of Bayes: a test "accuracy of 95%" is not the same as "a 95% probability of being diseased after a positive test." Drag the slider and calculate it yourself.

The output from running the above code is:

0.059000000000000004
0.16101694915254236

The conclusion is very counterintuitive: the test "accuracy is 95%", but the probability of actually being sick among positive results is only about 16% -- because the prevalence itself is only 1%, a large number of false positives drown out true positives.

This is exactly the value of Bayes' theorem: it tells youhow to use new evidence (test result) to update old beliefs (prevalence), which is also the common intellectual origin of the naive Bayes classifier and Bayesian optimization.

Chapter summary