Propositional Equivalences and Tautologies

Evaluating compound logical statements allows computer scientists and mathematicians to prove system invariants, optimize digital hardware logic gates, and verify the correctness of software algorithms. This guide explores the core properties of propositional logic, detailing how logical expressions are classified, transformed, and simplified using algebra and truth tables.

1. Propositions, Truth Values, and Connectives

A proposition (or statement) is a declarative sentence that is either strictly true ( $T$ ) or false ( $F$ ), but not both. Upper-case letters (e.g., $P, Q, R$ ) denote propositional variables, while their truth behavior is evaluated using logical operators.

1.1 Truth Tables and Basic Connectives

We define truth tables for the five core logical operators that construct compound expressions:

Negation ( $\neg P$ or $\sim P$ ): Inverts the truth value of a proposition.
Conjunction ( $P \wedge Q$ ): True only if both $P$ and $Q$ are true.
Disjunction ( $P \vee Q$ ): True if at least one of or is true (inclusive OR).

The following master truth table synthesizes these core behaviors:

| $P$ | $Q$ | $\neg P$ | $P \wedge Q$ | $P \vee Q$ | $P \rightarrow Q$ | | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |

1.2 Variations of Conditional Statements

For any given conditional statement $P \rightarrow Q$ , we define three related logical structures:

Converse: $Q \rightarrow P$
Inverse: $\neg P \rightarrow \neg Q$
Contrapositive: $\neg Q \rightarrow \neg P$

An implication and its contrapositive are always logically equivalent ( $P \rightarrow Q \equiv \neg Q \rightarrow \neg P$ ).

1.3 Translating English to Logic

Converting natural language to propositional logic is crucial for modeling system specifications. Consider this safety constraint:

"You cannot ride the roller coaster ( $q$ ) if you are under 4 feet tall ( $r$ ) unless you are older than 16 years old ( $s$ )."

The term "unless" acts as a conditional modifier meaning "if not". We represent this sentence formally as: $(r \wedge \neg s) \rightarrow \neg q$

Alternatively, we can express this as: $\neg s \rightarrow (r \rightarrow \neg q)$

2. Classification of Compound Propositions

We categorize compound propositions into three distinct classes based on their final truth columns in a truth table:

text

               [Compound Propositions]
                          |
        +-----------------+-----------------+
        |                 |                 |
  [ Tautology ]    [ Contradiction ]  [ Contingency ]
   Always True       Always False      Mixed Values
  (e.g., P v ~P)    (e.g., P ^ ~P)    (e.g., P -> Q)

Tautology: A compound proposition that evaluates to True ( $T$ ) across all rows of its truth table, regardless of the truth values assigned to its variables. For example, $P \vee \neg P$ is a basic tautology.
Contradiction: A compound proposition that evaluates to False ( $F$ ) across all rows of its truth table. For example, $P \wedge \neg P$ is a basic contradiction.
Contingency: A compound proposition that can be either True or False depending on the evaluation of its constituent variables (e.g., $P \to Q$ ).

2.1 Substitution Instances

If a compound proposition $B$ is a tautology, we can generate infinitely many other tautologies from it using substitution.

A formula $A$ is a substitution instance of $B$ if $A$ is obtained by replacing variables in $B$ with other logical expressions. The primary condition is that the same expression must replace the same variable each time it occurs.

Example: Let $B$ be the known tautology $P \rightarrow (Q \rightarrow P)$ .
We can substitute the compound formula $(R \rightarrow S)$ for all occurrences of $P$ .
The resulting substitution instance is: Because the structural skeleton of is preserved, this new formula is guaranteed to be a tautology without constructing a -row truth table.

3. Logical Equivalence and Tautological Implication

Establishing relationships between different propositions allows us to replace complex code routines or hardware logic with simplified expressions.

3.1 Logical Equivalence ( $\equiv$ or $\Leftrightarrow$ )

Two propositions $A$ and $B$ are logically equivalent if their truth values are identical in all possible cases. Formally, $A \equiv B$ (or $A \Leftrightarrow B$ ) if and only if the biconditional statement $A \leftrightarrow B$ is a tautology.

To prove that $\neg(P \rightarrow Q)$ is logically equivalent to $P \wedge \neg Q$ , we construct their joint truth table:

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

Because the column for $\neg(P \rightarrow Q)$ is identical to the column for $P \wedge \neg Q$ , we prove that: $\neg(P \rightarrow Q) \equiv P \wedge \neg Q$

3.2 Tautological Implication ( $\Rightarrow$ )

A proposition $A$ is said to logically imply (or tautologically imply) a proposition $B$ if $A \rightarrow B$ is a tautology. We denote this as: $A \Rightarrow B$

4. The Algebra of Propositions and Duality

Rather than writing out large truth tables, we can simplify logic expressions algebraically using equivalence laws.

4.1 Key Laws of Propositional Logic

Identity Laws: $P \wedge T \equiv P \quad\quad P \vee F \equiv P$
Domination Laws: $P \vee T \equiv T \quad\quad P \wedge F \equiv F$

4.2 The Duality Law

For any compound proposition $A$ containing only the operators $\wedge, \vee$ , and $\neg$ , its dual $A^*$ is obtained by swapping:

All $\wedge$ operators with $\vee$ operators.
All $\vee$ operators with $\wedge$ operators.
All $T$ (True) values with $F$ (False) values.
All $F$ (False) values with $T$ (True) values.

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

Example: Find the dual of the formula $A: (P \vee Q) \wedge R$ . We swap the $\vee$ with $\wedge$ , and the $\wedge$ with $\vee$ :

5. Functionally Complete Connectives

A set of logical connectives is functionally complete if every possible compound proposition can be expressed using only the connectives in that set.

The set $\{\neg, \wedge, \vee\}$ is functionally complete.
By applying De Morgan's laws, we can show that $\{\neg, \wedge\}$ and $\{\neg, \vee\}$ are also functionally complete. For example: $P \vee Q \equiv \neg(\neg P \wedge \neg Q)$

5.1 NAND and NOR Operators

We can construct single-operator systems that are functionally complete using NAND or NOR.

Logical NAND ( $\uparrow$ , Sheffer Stroke): Evaluates to false only when both operands are true. $P \uparrow Q \equiv \neg(P \wedge Q)$
Logical NOR ( $\downarrow$ , Peirce Arrow): Evaluates to true only when both operands are false. $P \downarrow Q \equiv \neg(P \vee Q)$

| $P$ | $Q$ | $P \uparrow Q$ (NAND) | $P \downarrow Q$ (NOR) | | :---: | :---: | :---: | :---: | | $T$ | $T$ | | | | | | | | | | | | | | | | | |

5.2 Expressing Connectives using NAND

Because $\{\uparrow\}$ is functionally complete on its own, we can build negation, conjunction, and disjunction using only NAND operations:

Negation: $\neg P \equiv P \uparrow P$
Conjunction: $P \wedge Q \equiv (P \uparrow Q) \uparrow (P \uparrow Q)$

6. Digital Computing, Bitwise Logic, and Syntax Representations

Modern computer architectures represent logical values using binary digits (bits): $1$ represents True ( $T$ ) and $0$ represents False ( $F$ ).

6.1 Bitwise Operations

A bit string is a sequence of zero or more bits. Bitwise operations apply logical operators to each matching position of two bit strings of equal length:

text

String A:     0 1  1 0  1 1  0 1  1 0
String B:     1 1  0 0  0 1  1 1  0 1
--------------------------------------
Bitwise OR:   1 1  1 0  1 1  1 1  1 1
Bitwise AND:  0 1  0 0  0 1  0 1  0 0
Bitwise XOR:  1 0  1 0  1 0  1 0  1 1

Here is a short Python script demonstrating how to calculate these logical bitwise operations:

python

# Bitwise representation in Python
string_a = 0b0110110110
string_b = 0b1100011101
 
# Calculate bitwise results
bitwise_or  = string_a | string_b
bitwise_and = string_a & string_b
bitwise_xor = string_a ^ string_b
 
# Print formatted binary strings padded to 10 bits
print(f"Bitwise OR:  {bitwise_or:010b}")
print(f"Bitwise AND: {bitwise_and:010b}")
print(f"Bitwise XOR: {bitwise_xor:010b}")

6.2 Precedence of Logical Operators

To limit the number of parentheses needed in complex expressions, we define a standard precedence hierarchy:

Negation ( $\neg$ ) — Highest Precedence
Conjunction ( $\wedge$ )
Disjunction ( $\vee$ )
Implication ( $\rightarrow$ )
Biconditional ( $\leftrightarrow$ ) — Lowest Precedence

When an expression is fully parenthesized, every operator is explicitly bound by parenthesis pairs matching its hierarchical level: $\left(P \vee \left(\left(Q \wedge R\right) \wedge \left(\neg S\right)\right)\right)$

       Prefix Tree Structure:
               [^]
              /   \
            [v]   [~]
            / \    |
           P   Q   R

C. Postfix Notation (Reverse Polish Notation)

The operator is placed after its operands. This notation is widely used in stack-based compiler design and interpreter architectures: $P Q \vee R \neg \wedge$

Summary

Compound Propositions are classified as tautologies (always true), contradictions (always false), or contingencies (variable truth values).
Logical equivalence ( $A \equiv B$ ) holds if and only if $A \leftrightarrow B$ is a tautology, allowing us to rewrite complex statements using standard algebraic rules like De Morgan's Laws.
The Duality Law lets us construct dual formulas by swapping operations ( $\wedge \leftrightarrow \vee$ ) and identity values ( $T \leftrightarrow F$ ).

Assessed progress

Propositional Equivalences and Tautologies

Propositional Equivalences and Tautologies

1. Propositions, Truth Values, and Connectives

1.1 Truth Tables and Basic Connectives

1.2 Variations of Conditional Statements

1.3 Translating English to Logic

2. Classification of Compound Propositions

2.1 Substitution Instances

3. Logical Equivalence and Tautological Implication

3.1 Logical Equivalence ( $\equiv$ or $\Leftrightarrow$ )

3.2 Tautological Implication ( $\Rightarrow$ )

4. The Algebra of Propositions and Duality

4.1 Key Laws of Propositional Logic

4.2 The Duality Law

5. Functionally Complete Connectives

5.1 NAND and NOR Operators

5.2 Expressing Connectives using NAND

6. Digital Computing, Bitwise Logic, and Syntax Representations

6.1 Bitwise Operations

6.2 Precedence of Logical Operators

6.3 Syntax Notations: Polish Notation

A. Infix Notation

B. Prefix Notation (Polish Notation)

C. Postfix Notation (Reverse Polish Notation)

Summary

Key Concepts

Tautology, Contradiction, and Contingency

Logical Equivalence

Substitution Instance

Functional Completeness

Duality Law

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures