NOT

NOT (also known as logical negation, logical complement, or inversion) is a fundamental unary operation in logic and mathematics that maps a truth value to its opposite. In classical Boolean algebra, the NOT operator takes a single input proposition \(P\) and outputs \(\neg P\) (also written as \(\sim P\) or \(!P\)), which is true if and only if \(P\) is false, and false if and only if \(P\) is true. The operation is central to propositional logic, digital circuit design, programming languages, and set theory (where it corresponds to complementation). Its truth table is the simplest of all logical gates, with only two rows: 0 → 1 and 1 → 0.

1 Definition and notation

The NOT operation is defined as a unary function that reverses the truth value of its argument. In formal logic, it is an operator of type \(\text{Bool} \to \text{Bool}\). The result of applying NOT to a proposition \(P\) is written in various ways depending on context, but the semantics remain the same: it yields the logical complement of \(P\).

1.1 Symbolic representations

Several symbols are used to denote logical negation across different fields:

• Logical notation: \(\neg P\) (negation sign), \(\sim P\) (tilde), or \(P'\) (prime).
• Programming languages: In C, C++, Java, and many others, the unary operator ! is used for Boolean negation (e.g., !true evaluates to false). In languages like Python, not is a keyword.
• Digital electronics: The overline (e.g., \(\overline{A}\)) or the prime symbol (e.g., \(A'\)) denote the inverted output of a logic gate.
• Mathematics: In set theory, the complement of a set \(A\) is often denoted by \(A^c\) or \(\overline{A}\).

1.2 Truth table

The truth table for the NOT operation enumerates all possible input values and their corresponding outputs.

1.2.1 Classical (two-valued) logic

In classical Boolean logic, where only two truth values (true and false, often represented as 1 and 0) exist, the truth table is:

This table defines the behavior of the NOT gate.

1.2.2 Multi-valued and fuzzy logic variants

In multi-valued logics (e.g., three-valued logic, Łukasiewicz logic, or Kleene logic), the NOT operation is extended to handle additional truth values. For example, in Kleene's strong three-valued logic (values: true, false, unknown), the negation of "unknown" remains "unknown". In fuzzy logic, where truth values range continuously from 0 to 1, the typical negation function is \(1 - x\), although other involutive functions (e.g., \(\sqrt{1 - x^2}\)) are also used.

2 Properties

The NOT operation possesses several algebraic properties that are important in logic and mathematics.

2.1 Involution (double negation)

A key property of classical negation is that applying the operation twice returns the original value: \(\neg(\neg P) = P\). This is known as double negation elimination or the involution property. It holds in classical Boolean algebra and in many non-classical logics (though some, like intuitionistic logic, reject it). In digital circuits, double inversion is used to shape signal propagation delays.

2.2 Relationship with other logical operators

Negation interacts with conjunction (AND), disjunction (OR), and other operators via several standard equivalences.

2.2.1 De Morgan's laws

De Morgan's laws express how negation distributes over conjunction and disjunction: \[ \neg(P \land Q) = \neg P \lor \neg Q \] \[ \neg(P \lor Q) = \neg P \land \neg Q \] These laws are fundamental in Boolean algebra, logic design, and programming (e.g., simplifying conditions). They also hold in set theory for complementation relative to a universal set.

2.2.2 Expressiveness: functional completeness

The NOT operator, together with either AND or OR, forms a functionally complete set of logical connectives—meaning any Boolean function can be expressed using only these operators. For example, the NAND gate (NOT AND) and NOR gate (NOT OR) are each functionally complete by themselves. This is the basis for constructing all digital logic from a single type of gate.

3 Applications

The NOT operation appears in numerous practical and theoretical domains.

3.1 Digital electronics

In digital electronics, the NOT gate (also called an inverter) is one of the three basic logic gates (along with AND and OR). It outputs the logical complement of its input.

3.1.1 Logic gate implementation

A NOT gate can be implemented using a single transistor (e.g., a bipolar junction transistor or CMOS inverter). In integrated circuits, inverters are building blocks for more complex gates, such as NAND and NOR, and for sequential elements like flip-flops. The CMOS inverter consists of a p-type and an n-type MOSFET in series; when the input is high, the n-type transistor conducts and pulls the output low, and vice versa.

3.1.2 Use in flip-flops and memory circuits

Inverters are essential for bistable circuits (e.g., SR latches, D flip-flops). Two cross-coupled inverters form a basic memory cell that can store one bit. This configuration, known as a latch, is the foundation of static random-access memory (SRAM) and registers. The NOT operation is also used in clock conditioning and signal debouncing.

3.2 Computer science

In programming, logical and bitwise NOT operators are common.

3.2.1 Boolean expressions and conditionals

In most programming languages, the logical NOT operator (often ! or not) negates a Boolean expression. For example, if (!isValid) executes the block when isValid is false. It is used to invert conditions, loop termination tests, and to implement tautologies and contradictions.

3.2.2 Bitwise NOT operator

A bitwise NOT (unary operator ~ in C-like languages) flips every bit of its integer operand. For example, ~0 yields all 1s (in two's complement representation, that equals −1). The bitwise NOT is used in low-level operations such as masking, setting, or clearing specific bits. It also appears in image processing (e.g., color inversion) and cryptography.

3.3 Mathematics

Beyond propositional logic, negation finds applications in set theory and predicate logic.

3.3.1 Set complement

In set theory, the complement of a set \(A\) relative to a universe \(U\) is denoted \(A^c\), \(\overline{A}\), or \(\complement A\), and is defined as \(\{x \in U \mid x \notin A\}\). Complementation satisfies De Morgan's laws and the involution property \((A^c)^c = A\). In Boolean algebra of sets, the complement corresponds directly to logical negation.

3.3.2 Negation in predicate logic

In first-order logic, negation is used with quantifiers: \(\neg(\forall x\, P(x))\) is equivalent to \(\exists x\, \neg P(x)\), and \(\neg(\exists x\, P(x))\) is equivalent to \(\forall x\, \neg P(x)\) (the dualities known as De Morgan's laws for quantifiers). Negation also forms the basis of proof by contradiction and contrapositive reasoning.

4 Philosophical and linguistic aspects

The concept of negation extends beyond formal logic into language and philosophy.

4.1 Negation in natural language

In ordinary language, negation is expressed in many ways: using words like "not", "no", "never", "un-", "in-", etc. It can operate on sentences (e.g., "It is not raining") or on phrases (e.g., "unhappy", "nonstandard"). Natural language negation often involves issues of scope, ambiguity, and presupposition (e.g., "John didn't stop smoking" presupposes that John used to smoke). The logical properties of natural language negation continue to be studied in linguistics and philosophy.

4.2 Paradoxes involving negation (e.g., liar paradox)

The liar paradox ("This sentence is false") arises from self-referential negation. If the sentence is true, then it must be false, and vice versa. Such paradoxes reveal limitations of formal systems and have motivated developments in paraconsistent logic and Tarski's hierarchy of languages. In weaker logical systems, attempts to resolve the paradox often involve restricting the use of negation with self-reference.

5 See also

• Boolean algebra
• Logic gate
• Negation (disambiguation)
• De Morgan's laws
• Truth value
• Complement (set theory)