Special Connectives and Functional Completeness

In discrete mathematics and computer engineering, propositional logic serves as the mathematical foundation for digital circuit design, automated reasoning, and compiler optimization. This module explores how complex logical expressions can be simplified, transformed, and represented using minimal sets of operators, culminating in the concepts of functional completeness, duality, and alternative syntax notations.

1. Propositional Logic and Logical Equivalence

A proposition is a declarative sentence that is either true ( $T$ or $1$ ) or false ( $F$ or $0$ ), but not both. Compound propositions are constructed by joining propositional variables using logical operators.

Tautologies, Contradictions, and Contingencies

When evaluating compound propositions, we classify them based on their truth values across all possible interpretations:

Tautology: A statement formula that is always true, regardless of the truth values of its individual propositional variables (e.g., $P \vee \neg P$ ).
Contradiction: A statement formula that is always false, regardless of the truth values of its constituent variables (e.g., $P \wedge \neg P$ ).
Contingency: A statement formula that can be either true or false depending on its variables' values (e.g., $(P \vee \neg Q) \to (P \wedge Q)$ ).

Establishing Logical Equivalence

Two compound propositions $A$ and $B$ are logically equivalent (denoted $A \equiv B$ or $A \Leftrightarrow B$ ) if they have identical truth values in every row of a truth table. This is equivalent to stating that the biconditional $A \leftrightarrow B$ is a tautology.

Consider the logical equivalence between the negation of an implication and a conjunction:

$\neg(P \to Q) \equiv P \wedge \neg Q$

We can prove this equivalence using a truth table:

| $P$ | $Q$ | $P \to Q$ | $\neg(P \to Q)$ | $\neg Q$ | $P \land \neg$ | | :---: | :---: | :---: | :---: | :---: | :---: | | | | | | | | | | | | | | | | | | | | | | | | | | | | |

Because the column for $\neg(P \to Q)$ matches the column for $P \wedge \neg Q$ row-by-row, the equivalence is verified.

2. The Duality Principle

The Duality Principle is an algebraic property of propositional logic that allows us to derive new logical equivalences from known ones without re-evaluating truth tables.

Definition of a Dual

Let $A$ be a formula containing only the logical operators $\wedge$ , $\vee$ , and $\neg$ (where negations only apply directly to variables). The dual of $A$ , denoted $A^*$ , is obtained by:

Replacing every occurrence of $\wedge$ with $\vee$ .
Replacing every occurrence of $\vee$ with $\wedge$ .
Replacing every occurrence of the logical constant $T$ (or $1$ ) with $F$ (or $0$ ).

Note: Negation operators ( $\neg$ ) remain unchanged.

Example of Dual Derivation

Let $A$ be the formula:

$A = (P \vee Q) \wedge (R \vee T)$

To find its dual $A^*$ :

$A^* = (P \wedge Q) \vee (R \wedge T)$

The Duality Theorem

The power of duality lies in the Duality Theorem, which states:

$\text{If } A \equiv B, \text{ then } A^* \equiv B^*$

This allows us to immediately assert dual equivalences. For instance, knowing the distributive law:

$P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)$

By applying the Duality Theorem, we obtain the second distributive law automatically:

$P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)$

3. Special Connectives: NAND and NOR

While standard propositional logic relies heavily on $\{\neg, \wedge, \vee, \to, \leftrightarrow\}$ , practical hardware design benefits from simpler, highly efficient universal gates. Two special connectives are central to this optimization: NAND (Sheffer stroke) and NOR (Peirce arrow).

The NAND Operator (Sheffer Stroke)

The NAND operator is denoted by the Sheffer stroke symbol $\uparrow$ or $|$ . It represents the negation of a conjunction:

$P \uparrow Q \equiv \neg(P \wedge Q)$

It produces a value of False if and only if both of its operands are True.

| $P$ | $Q$ | $P \uparrow Q$ | | :---: | :---: | :---: | | $T$ | $T$ | $F$ | | $T$ | | | | | | | | | | |

The NOR Operator (Peirce Arrow)

The NOR operator is denoted by the Peirce arrow symbol $\downarrow$ . It represents the negation of a disjunction:

$P \downarrow Q \equiv \neg(P \vee Q)$

It produces a value of True if and only if both of its operands are False.

| $P$ | $Q$ | $P \downarrow Q$ | | :---: | :---: | :---: | | $T$ | $T$ | $F$ | | $T$ | | | | | | | | | | |

4. Functional Completeness

A set of logical connectives is functionally complete if any possible truth function (or Boolean function) can be expressed using an equivalent formula containing only the connectives from that set.

Proving Completeness of $\{\neg, \wedge, \vee\}$

Every truth table defines a boolean function. We can construct an equivalent formula for any truth table using its rows that evaluate to True. This technique is known as expressing the function in Disjunctive Normal Form (DNF). Since DNF uses only negations ( $\neg$ ), conjunctions ( $\wedge$ ), and disjunctions ( $\vee$ ), the set $\{\neg, \wedge, \vee\}$ is functionally complete.

Reducing the Set of Connectives

Using De Morgan’s Laws, we can reduce this set even further:

Eliminating Disjunction: Since $P \vee Q \equiv \neg(\neg P \wedge \neg Q)$ , the set $\{\neg, \wedge\}$ is functionally complete.
Eliminating Conjunction: Since $P \wedge Q \equiv \neg(\neg P \vee \neg Q)$ , the set is functionally complete.

Singleton Universality: Completeness of NAND and NOR

Can we achieve functional completeness using a set containing only one connective? Yes. Both $\{\uparrow\}$ and $\{\downarrow\}$ are individually functionally complete.

1. NAND as a Universal Operator

To prove $\{\uparrow\}$ is functionally complete, we must show we can define both negation ( $\neg$ ) and conjunction ( $\wedge$ ) using only the NAND operator:

Negation: $\neg P \equiv P \uparrow P$ Proof: $P \uparrow P \equiv \neg(P \wedge P) \equiv \neg P$ .

2. NOR as a Universal Operator

To prove $\{\downarrow\}$ is functionally complete, we express negation ( $\neg$ ) and disjunction ( $\vee$ ) using only the NOR operator:

Negation: $\neg P \equiv P \downarrow P$ Proof: $P \downarrow P \equiv \neg(P \vee P) \equiv \neg P$ .

Summary Matrix of Connective Transformations

The following matrix displays how the primary operations are mapped to NAND and NOR:

5. Polish Notations and Syntax Trees

In standard logic expressions, we write operators between their operands (e.g., $P \vee Q$ ). This is known as Infix Notation. To resolve ambiguity in complex expressions, we rely on parenthetical scoping and operator precedence.

Alternatively, we can express logical formulas without parentheses using prefix and postfix notations, often termed Polish Notations.

Precedence of Logical Operators

When parentheses are omitted, the order of evaluation is dictated by the standard operator hierarchy:

$\text{Highest} \quad \neg \quad \longrightarrow \quad \wedge \quad \longrightarrow \quad \vee \quad \longrightarrow \quad \to \quad \longrightarrow \quad \leftrightarrow \quad \text{Lowest}$

For example, $P \wedge \neg Q \vee R$ is implicitly parsed as $((P \wedge (\neg Q)) \vee R)$ .

Syntax Representation Formats

Infix Notation: The operator is placed between its arguments: $P \vee Q$ .
Prefix Notation (Polish): The operator precedes its arguments: $\vee P Q$ .
Postfix Notation (Reverse Polish): The operator follows its arguments: $P Q \vee$ .

Parsing via Abstract Syntax Trees (AST)

An Abstract Syntax Tree is a binary tree representing the syntactic structure of an expression. Leaf nodes represent propositional variables, while internal nodes represent operators.

For the infix expression:

$(P \vee \neg Q) \to (R \wedge S)$

We construct the syntax tree below:

text

         [ -> ]
        /      \
     [ v ]    [ ^ ]
     /   \    /   \
    P    [~] R     S
          |
          Q

Using this tree, we can generate all three notations:

Infix (In-order traversal): $(P \vee (\neg Q)) \to (R \wedge S)$
Prefix (Pre-order traversal): $\to \vee P \neg Q \wedge R S$
Postfix (Post-order traversal):

6. Engineering Implementation: Logic Gate Evaluator

The following Python code demonstrates the execution of functionally complete systems. It defines a baseline nand_gate and builds the standard operators (not, and, or, implies) exclusively from it, evaluating a compound proposition.

python

"""
Logic Gate Simulator using Functionally Complete Operators.
This module demonstrates how any logical operation can be constructed 
using ONLY the primitive NAND operation.
"""
 
def nand_gate(p: bool, q: bool) -> bool:
    """The universal Sheffer Stroke (NAND) gate."""
    return not (p and q)
 
# --- Constructing basic gates from NAND ---
 
def logical_not(p: bool) -> bool:
    """Negation: NOT P = P NAND P"""
    return nand_gate(p, p)
 
def logical_and(p: bool, q: bool) -> bool:
    """Conjunction: P AND Q = (P NAND Q) NAND (P NAND Q)"""
    temp = nand_gate(p, q)
    return nand_gate(temp, temp)
 
def logical_or(p: bool, q:

Summary

Tautologies are always True; Contradictions are always False. Understanding these classifications allows for rigorous correctness checks of logical arguments.
The Duality Principle transforms any valid logical equivalence containing $\{\neg, \wedge, \vee\}$ into another valid statement by swapping $\wedge \leftrightarrow \vee$ and $T \leftrightarrow F$ .
Functional Completeness guarantees that any Boolean operation can be written using a small set of base operations. $\{\neg, \wedge, \vee\}$ , , and are typical examples.

Assessed progress

Special Connectives and Functional Completeness

Special Connectives and Functional Completeness

1. Propositional Logic and Logical Equivalence

Tautologies, Contradictions, and Contingencies

Establishing Logical Equivalence

2. The Duality Principle

Definition of a Dual

Example of Dual Derivation

The Duality Theorem

3. Special Connectives: NAND and NOR

The NAND Operator (Sheffer Stroke)

The NOR Operator (Peirce Arrow)

4. Functional Completeness

Proving Completeness of $\{\neg, \wedge, \vee\}$

Reducing the Set of Connectives

Singleton Universality: Completeness of NAND and NOR

1. NAND as a Universal Operator

2. NOR as a Universal Operator

Summary Matrix of Connective Transformations

5. Polish Notations and Syntax Trees

Precedence of Logical Operators

Syntax Representation Formats

Parsing via Abstract Syntax Trees (AST)

6. Engineering Implementation: Logic Gate Evaluator

Summary

Key Concepts

Functional Completeness

Sheffer Stroke (NAND)

Peirce Arrow (NOR)

Duality Law

Polish Notation

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures