Boolean conjunctions
A Boolean conjunction maps X = {0, 1}^n to Y = {0, 1}.
From Bits to One Label
A Boolean conjunction starts with an n-component binary input and produces one binary output. In notation, it is a mapping from X = {0, 1}^n to Y = {0, 1}. The input belongs to X, so it contains n components, while the output belongs to Y, so it is a single value.
The Formula’s Building Blocks
The mapping is expressed by a proposition formula. The formula can contain variables that appear positively, variables that appear negated, and conjunction symbols joining the terms. A positive variable appears without the negation symbol. A negated variable appears with ¬ before it. The indices identify which components of the n-component input participate in the formula.
| Formula part | How to identify it | What its index indicates |
|---|---|---|
| x_i | The variable appears without ¬ | Input component i participates positively |
| ¬x_j | The variable appears with ¬ | Input component j participates negated |
| ∧ | The conjunction symbol joins terms | The listed terms belong to one proposition formula |
The visible parts of a Boolean conjunction formula
Tracing a Concrete Assignment
Consider the generated illustration f(x1, x2) = x1 ∧ ¬x2. This formula contains one positive variable, x1, and one negated variable, ¬x2. The indices show that the formula uses the first and second components of the input.
Classifying Inputs with x1 ∧ ¬x2
Use the generated formula f(x1, x2) = x1 ∧ ¬x2 to associate a binary output with several two-component binary inputs.
Identify the terms: x1 is positive, while x2 appears negated as ¬x2.
Read the input: For input (1, 0), the first component is 1 and the second component is 0.
Evaluate the proposition: The positive x1 condition is satisfied by 1, and the negated x2 condition is satisfied because x2 is 0. This generated illustration therefore assigns output 1 to (1, 0).
Compare another input: For input (1, 1), the positive x1 condition is satisfied, but the negated x2 condition is not. This generated illustration therefore assigns output 0 to (1, 1).
The formula maps each two-component binary input to one binary output. In this illustration, (1, 0) maps to 1 and (1, 1) maps to 0.
Definition and Learnability
There are two different statements to keep separate. The definition describes what belongs to the Boolean-conjunction class: a rule maps an input from {0, 1}^n to an output in {0, 1}, and its mapping can be expressed using positive variables, negated variables, and conjunction symbols. The learnability statement is different: Boolean conjunctions are efficiently learnable in the realizable case.
Recognizing a formula as a Boolean conjunction answers a membership question about the class. Saying that Boolean conjunctions are efficiently learnable answers a learning question about recovering a rule from labeled examples under the realizable-case condition.
Realizable-Case Learning
In the realizable case, the labeled examples are generated by some Boolean conjunction. The learnability claim says that the Boolean-conjunction class can be learned efficiently in this setting. At the level supported here, the important conclusion is that an efficient learner can use such realizable labeled examples to recover a Boolean conjunction consistent with the target rule. The source establishes this theorem-level conclusion but does not provide a further implementation trace.
Common Classification Mistakes
Treating the output as another n-component vector.
The input has n binary components, but the output is a single binary value in {0, 1}.
Fix:
Keep the domain and codomain distinct: {0, 1}^n is the input space, and {0, 1} is the output space.Calling every variable in the formula positive.
A variable preceded by ¬ is a negated variable.
Fix:
Inspect each term for the negation symbol before classifying it.Using the learnability claim as the definition.
The mapping and formula structure define the class; efficient learnability is a separate conclusion about the class in the realizable case.
Fix:
State the mapping and formula structure first, then state the separate learnability property.Assuming the source provides a specific learning algorithm.
The source establishes efficient learnability but does not provide a further implementation trace.
Fix:
Report the theorem-level conclusion without adding an unsupported algorithm or runtime.
Check Your Understanding
A proposition formula contains x3, ¬x5, and conjunction symbols joining its terms. Explain which variables are positive, which are negated, what the indices identify, and whether this information describes the class definition or the learnability claim.
Hints
- A variable without ¬ is positive.
- A variable with ¬ is negated.
- The indices refer to components of the n-component input.
- The formula structure addresses the definition; efficient learnability is a separate claim.
Complete this statement: A Boolean conjunction maps an input from ______ to an output in ______. Then explain what changes when the statement is extended with the claim that Boolean conjunctions are efficiently learnable in the realizable case.
Hints
- The input is an n-component binary vector.
- The output is one binary value.
- The added claim concerns learning from realizable labeled examples, not the formula's notation.
Key Takeaways
- A Boolean conjunction is a mapping from {0, 1}^n to {0, 1}.
- Its input is an n-component binary vector, and its output is one binary value.
- Its proposition formula can contain positive variables, negated variables, and conjunction symbols; indices identify input components.
- Efficient learnability in the realizable case is a separate claim stating that the class can be learned efficiently when examples are generated by some Boolean conjunction.
- The class definition and the learnability statement should be reported as two distinct ideas.
Key Takeaways
- Boolean conjunctions map n-bit inputs to one-bit outputs.
- Positive variables appear without negation, while negated variables appear with ¬.
- Variable indices identify the components of the input used in the proposition formula.
- Efficient learnability in the realizable case describes a learning property of the class, not its definition.
- The source establishes efficient learnability but does not specify a further implementation trace.