Foundations of Propositional Logic

Propositional logic is the branch of mathematical logic that studies the truth values of declarative statements and how they form complex systems using logical operators. It serves as the formal foundation for computer circuitry design, software verification algorithms, and rigorous mathematical proofs.

1. Mathematical Logic and Propositions

At its core, mathematical logic provides rules, methodologies, and systematic techniques to determine whether a given mathematical argument is valid. It allows us to prove a theorem—a statement that can be shown to be true under certain specified conditions.

A proposition (or statement) is a declarative sentence that is either strictly True ( $T$ ) or False ( $F$ ), but not both. We typically represent propositions using uppercase letters such as $P, Q, R, S$ or lowercase letters $p, q, r, s$ .

text

                        ┌────────────────────────┐
                        │ Declarative Statement  │
                        └───────────┬────────────┘
                                    │
                    ┌───────────────┴───────────────┐
                    ▼                               ▼
       ┌─────────────────────────┐     ┌─────────────────────────┐
       │ Propositional Statement │     │     Non-Proposition     │
       │ (Has clear truth value) │     │ (Commands/Opinions/etc) │
       └────────────┬────────────┘     └─────────────────────────┘
                    │
            ┌───────┴───────┐
            ▼               ▼
        ┌───────┐       ┌───────┐
        │ True  │       │ False │
        │  (T)  │       │  (F)  │
        └───────┘       └───────┘

Examples of Propositions

$P$ : " $2$ is an even number" (Truth value: $T$ )
$Q$ : " $7$ is an even number" (Truth value: $F$ )
$R$ : "It snowed in Whistler, BC on January 4, 2008" (Truth value: $T$ or )

Non-Propositions

"My cat is beautiful" (Subjective opinion; lacks an objective truth value)
"Turn your homework in on Wednesday" (Command or imperative sentence)
"Why are we taking this class?" (Interrogative question)
"This statement is false" (A self-referential paradox; cannot be consistently assigned a single truth value)

2. Logical Operators and Truth Tables

We construct complex, compound propositions from simpler ones using logical operators (also called connectives).

Negation ( $\neg$ or $\sim$ )

The negation of a proposition $P$ , written as $\neg P$ (read as "not $P$ "), has the opposite truth value of $P$ .

| $P$ | $\neg P$ | | :---: | :---: | | $T$ | $F$ | | $F$ | $T$ |

Conjunction ( $\land$ )

The conjunction of $P$ and $Q$ , written as $P \land Q$ (read as " $P$ and $Q$ "), is true if and only if both $P$ and $Q$ are true. Otherwise, it is false.

| $P$ | $Q$ | $P \land Q$ | | :---: | :---: | :---: | | $T$ | $T$ | $T$ | | $T$ | | | | | | | | | | |

Disjunction ( $\lor$ )

The disjunction of $P$ and $Q$ , written as $P \lor Q$ (read as " $P$ or $Q$ "), is true if at least one of the propositions is true. It is false only when both $P$ and $Q$ are false.

| $P$ | $Q$ | $P \lor Q$ | | :---: | :---: | :---: | | $T$ | $T$ | $T$ | | $T$ | | | | | | | | | | |

Conditional / Implication ( $\rightarrow$ )

An implication $P \rightarrow Q$ (read as "if $P$ , then $Q$ ") expresses a conditional relationship. Here, $P$ is called the hypothesis (or antecedent), and $Q$ is called the conclusion (or consequent). The implication is false only when a true hypothesis leads to a false conclusion ( $T \rightarrow F$ ).

| $P$ | $Q$ | $P \rightarrow Q$ | | :---: | :---: | :---: | | $T$ | $T$ | $T$ | | $T$ | | | | | | | | | | |

Biconditional / Biimplication ( $\leftrightarrow$ or $\rightleftarrows$ )

The biconditional statement $P \leftrightarrow Q$ (read as " $P$ if and only if $Q$ ") is true when both $P$ and $Q$ share the same truth values.

| $P$ | $Q$ | $P \leftrightarrow Q$ | | :---: | :---: | :---: | | $T$ | $T$ | $T$ | | $T$ | | | | | | | | | | |

3. Conditional Variations

Given a conditional statement $P \rightarrow Q$ , we can form three related conditional propositions:

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

Let's illustrate these with an example:

Original Conditional ( $P \rightarrow Q$ ): "If today is Sunday ( $P$ ), then I will wash the car ( $Q$ )."
Converse ( $Q \rightarrow P$ ): "If I wash the car, then today is Sunday."
Inverse ( $\neg P \rightarrow \neg Q$ ): "If today is not Sunday, then I will not wash the car."

Crucial Relationship: A conditional statement is always logically equivalent to its contrapositive ( $P \rightarrow Q \equiv \neg Q \rightarrow \neg P$ ). The converse and inverse are also logically equivalent to each other ( $Q \rightarrow P \equiv \neg P \rightarrow \neg Q$ ).

4. Translating Natural Language to Propositional Logic

Translating ambiguous natural language sentences into precise logical formulas is vital for systems engineering. Consider the following policy:

"You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old."

We begin by identifying the atomic propositional variables:

$q$ : You can ride the roller coaster.
$r$ : You are under 4 feet tall.
$s$ : You are older than 16 years old.

Now we analyze the logic of "unless". The clause "unless you are older than 16 years old" means "if you are not older than 16 years old" ( $\neg s$ ). So, if you are not older than 16 ( $\neg s$ ), then being under 4 feet tall ( $r$ ) implies you cannot ride the roller coaster ( $\neg q$ ).

We write this mathematically as: $\neg s \rightarrow (r \rightarrow \neg q)$

Alternatively, we can group the conditions: "If you are under 4 feet tall AND you are not older than 16 years old, then you cannot ride the roller coaster." $(r \land \neg s) \rightarrow \neg q$

Let us prove that these two formulations are logically equivalent using truth tables:

| $r$ | $s$ | $q$ | $\neg q$ | $\neg s$ | $r \land \neg s$ | $($ | | | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |

The truth values for both formulations are identical across all eight assignments, validating the translation.

5. Tautologies, Contradictions, and Contingencies

Compound propositions are categorized based on their possible valuations:

Tautology: A statement formula that is always true, regardless of the truth values assigned to its component variables.
- Example: $P \lor \neg P$
Contradiction: A statement formula that is always false, regardless of the truth values of its component variables.
- Example: $P \land \neg P$
Contingency: A statement formula that can be either true or false depending on the values of its component variables.
- Example: $(P \lor \neg Q) \rightarrow (P \land Q)$

text

              ┌────────────────────────┐
              │  Compound Proposition  │
              └───────────┬────────────┘
                          │
         ┌────────────────┼────────────────┐
         ▼                ▼                ▼
   ┌───────────┐    ┌───────────┐    ┌───────────┐
   │ Tautology │    │Contingency│    │Contradiction
   │ [Always T]│    │ [T or F]  │    │ [Always F]│
   └───────────┘    └───────────┘    └───────────┘

Substitution Instances

If a formula $B$ is a tautology, we can obtain another tautology $A$ by consistently substituting more complex formulas for the variables in $B$ . This formula $A$ is called a substitution instance of $B$ .

For example, let $B$ be the tautology: $P \rightarrow (Q \rightarrow P)$

If we substitute $P$ with $(R \rightarrow S)$ , the resulting formula $A$ is still a tautology: $(R \rightarrow S) \rightarrow (Q \rightarrow (R \rightarrow S))$

6. Logical Equivalence and Tautological Implication

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

Two compound propositions $A$ and $B$ are logically equivalent if they share the same truth values in all possible scenarios. Symbolically, we write this as $A \equiv B$ , which means that the biconditional statement $A \leftrightarrow B$ is a tautology.

Proving Logical Equivalence Algebraically

Let's show that $\neg(P \rightarrow Q)$ is logically equivalent to $P \land \neg Q$ :

Use the conditional equivalence: $P \rightarrow Q \equiv \neg P \lor Q$ .
Substitute this into the expression: $\neg(P \rightarrow Q) \equiv \neg(\neg P \lor Q)$

Thus, $\neg(P \rightarrow Q) \equiv P \land \neg Q$ .

Tautological Implication ( $\Rightarrow$ )

A statement formula $A$ logically implies (or tautologically implies) $B$ if the conditional statement $A \rightarrow B$ is a tautology. We write this as: $A \Rightarrow B$

7. Duality and Functional Completeness

Duality Law

Two formulas $A$ and $A^*$ are duals of each other if we can obtain one from the other by swapping:

Conjunction ( $\land$ ) and Disjunction ( $\lor$ )
True ( $T$ ) and False ( $F$ ) (or $1$ and $0$ in bit operations)

Note: Negation operators ( $\neg$ ) remain unchanged when finding the dual of an expression.

Example: The dual of $(P \lor Q) \land R$ is $(P \land Q) \lor R$ .

Functionally Complete Set of Connectives

A set of logical connectives is functionally complete if any possible truth function can be expressed solely using the operators in that set.

$\{\neg, \land, \lor\}$ is functionally complete.
$\{\neg, \land\}$ and $\{\neg, \lor\}$ are functionally complete because $P \lor Q \equiv \neg(\neg P \land \neg Q)$ and .

NAND ( $\uparrow$ / Sheffer Stroke)

The NAND operation yields false only when both inputs are true.

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

NOR ( $\downarrow$ / Peirce Arrow)

The NOR operation yields true only when both inputs are false.

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

8. Logic and Bit Operations

In computer science, logical values are represented as binary digits (bits):

$1$ represents True ( $T$ )
$0$ represents False ( $F$ )

A bit string is a sequence of zero or more bits. Bitwise operations apply logical operators to each corresponding pair of bits in two 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   (A v B)
Bitwise AND:  0  1  0  0  0  1  0  1  1  0   (A ^ B)
Bitwise XOR:  1  0  1  0  1  0  1  0  1  1   (A ⊕ B)

Infix Notation: The operator is placed between the operands.
- Example: $P \lor Q$
Prefix Notation (Polish): The operator is placed before the operands.
- Example: $\lor P Q$
Postfix Notation (Reverse Polish): The operator is placed after the operands.
- Example: $P Q \lor$

Summary

Propositions must be declarative sentences that evaluate to a single, constant truth value ( $T$ or $F$ ).
Logical connectives compile simple propositions into compound structures, mapped through truth tables.
Conditionals ( $P \rightarrow Q$ ) generate three variations: converse ( $Q \rightarrow P$ ), inverse ( $\neg P \rightarrow \neg Q$ ), and contrapositive ().

Assessed progress

Foundations of Propositional Logic

Foundations of Propositional Logic

1. Mathematical Logic and Propositions

Examples of Propositions

Non-Propositions

2. Logical Operators and Truth Tables

Negation ( $\neg$ or $\sim$ )

Conjunction ( $\land$ )

Disjunction ( $\lor$ )

Conditional / Implication ( $\rightarrow$ )

Biconditional / Biimplication ( $\leftrightarrow$ or $\rightleftarrows$ )

3. Conditional Variations

4. Translating Natural Language to Propositional Logic

5. Tautologies, Contradictions, and Contingencies

Substitution Instances

6. Logical Equivalence and Tautological Implication

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

Proving Logical Equivalence Algebraically

Tautological Implication ( $\Rightarrow$ )

7. Duality and Functional Completeness

Duality Law

Functionally Complete Set of Connectives

NAND ( $\uparrow$ / Sheffer Stroke)

NOR ( $\downarrow$ / Peirce Arrow)

8. Logic and Bit Operations

9. Operator Precedence and Parenthesization

Order of Precedence

Notation Formats (Polish Notation)

Summary

Key Concepts

Proposition

Logical Connectives

Tautology and Contradiction

Logical Equivalence

Functional Completeness

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures