๐ Negation of Logical Expressions
Negating logical expressions requires understanding the independent roles of:
- Quantifiers: $\forall$, $\exists$
- Logical operators: $\land$, $\lor$, $\Rightarrow$, $\neg$
These components are syntactically nested but semantically independentโnegation applies to each layer separately, not interactively. This modularity is crucial for audit logic, predicate analysis, and proof construction.
๐ง Structural Principle
Quantifiers and logical operators do not cancel or interfere with each other. When negating a compound expression, each layer must be negated according to its own transformation rule.
๐ Core Negation Rules
1. Quantifier Negation
| Original Expression | Negated Form |
|---|---|
| $\forall x \in A,\;P(x)$ | $\exists x \in A,\;\neg P(x)$ |
| $\exists x \in A,\;P(x)$ | $\forall x \in A,\;\neg P(x)$ |
๐ Negating a quantifier flips its type and negates the inner predicate.
2. Logical Connective Negation (De Morganโs Laws)
| Original Expression | Negated Form | Semantic Flag |
|---|---|---|
| $\neg(P \lor Q)$ | $\neg P \land \neg Q$ | <code>#de-morgan</code> |
| $\neg(P \land Q)$ | $\neg P \lor \neg Q$ | <code>#de-morgan</code> |
๐ Negation distributes across logical operators by flipping the connective.
๐งฉ Compound Example
Original
$\exists x \in A,\;P(x) \lor Q(x)$
Negation
$\forall x \in A,\;\neg P(x) \land \neg Q(x)$
Breakdown
- Quantifier flip: $\exists \rightarrow \forall$
- Connective flip: $\lor \rightarrow \land$
- Predicate negation: $P(x), Q(x) \rightarrow \neg P(x), \neg Q(x)$
Visual Anchor
Original: โx โ A, [P(x) โจ Q(x)]
Negation: โx โ A, [ยฌP(x) โง ยฌQ(x)]๐งช Audit Counterexamples
| Expression | Truth Value | Reason |
|---|---|---|
| $\exists x \in \{1,2,3\},\;x > 2$ | โ | $x = 3$ satisfies |
| Negation: $\forall x,\;x \leq 2$ | โ | $x = 3$ violates it |
| Expression | Truth Value | Reason |
|---|---|---|
| $\forall x \in \{1,2,3\},\;x < 5$ | โ | All $x$ satisfy |
| Negation: $\exists x,\;x \geq 5$ | โ | No $x$ satisfies |
๐ง Semantic Clarifier
| Layer | Original | Negated | Notes |
|---|---|---|---|
| Quantifier | $\exists x$ | $\forall x$ | Flip scope |
| Logical Connective | $P(x) \lor Q(x)$ | $\neg P(x) \land \neg Q(x)$ | Apply De Morgan |
| Predicate | $P(x)$ | $\neg P(x)$ | Negate truth condition |
โ Each layer transforms independentlyโno cancellation or interference.