Chapter 7

# Boolean Functions & Shattering Demo

Explore all 16 two-input Boolean functions and test VC dimension interactively

A perceptron with two inputs can compute 14 out of 16 Boolean functions — exactly those that are linearly separable. The two exceptions are XOR and XNOR: no single line can separate their positive from negative points. As input dimension grows, the fraction of computable functions collapses to zero. The VC dimension measures a model's capacity: a perceptron in ℝn can shatter any n+1 points in general position.

## All 16 Two-Input Boolean Functions

Click any cell to see details. Green border = linearly separable, red = not.

14 of 16 are linearly separable

### —

x₁ | x₂ | f(x)
--- | --- | ---

## VC Dimension & Shattering

Drag the 3 points below. A perceptron can shatter 3 points in general position (classify all 2³ = 8 labelings). If points become collinear, some labelings fail.

### Labelings (8 total)

Click a labeling to test it. Blue = class 1, Red = class 0. Green highlight = separable, Red = not.

#### What is shattering?

A set of points is shattered by a model if the model can achieve every possible labeling. The VC dimension is the largest set size that can be shattered.

For a perceptron in ℝ²: VCdim = 3