Propositional Logic

The system of propositional logic allows us to express statements mathematically and reason about their truth values.

Language of Propositional Logic

We must first define the syntax we will use to express propositions in propositional logic.

A proposition, in fact, is defined as follows:

Definition 1: Proposition

A proposition is a statement that can be true or false.

Terminology: Synonyms for Proposition

Mathematical papers often use the following terms to more concisely refer to propositions:

A theorem is a significant proposition that has been proven to be true.
A lemma is a proposition used to progress towards proving a larger theorem.
A corollary is a proposition that follows directly from a previously proven theorem.
A proposition, in general, is a statement that can be proven true or false.

“True” and “False” are the two truth values that propositions can take on.

Propositional Variables

Propositional variables are used to abstract propositions into a symbolic form. Since we are interested in the syntax used to express propositions, we cannot associate a propositional variable with a specific proposition. Instead, we treat propositional variables as placeholders that can represent any proposition.

Definition 2: Propositional Variable

A propositional variable $𝑝$ is a variable that can potentially take on a truth value. That is, $𝑝$ can be assigned either true or false.

Remark

Note that a propositional variable $𝑝$ itself is not “either true or false” directly. Rather it is merely “possible” to assign $𝑝$ a truth value of either true or false, and we manipulate $𝑝$ as if we don’t know which truth value it has been assigned.

Example.

The assertion that $𝑥$ is a square can be assigned a propositional variable

𝑝

, since it would hold that

𝑝

is true if

𝑥

is a square, and false otherwise.

Notation: Truth Values

We can denote the truth values as $𝖳$ for true and $𝖥$ for false.

Complex Propositions

Although propositional variables can abstract individual propositions, we can express more complex propositions by combining propositional variables using logical connectives.

Definition 3: Logical Connective

A logical connective is an operator that takes one or more propositions as input and produces a new proposition as output.

Definition 4: Atomic and Compound Propositions

An compound proposition is a proposition that can be formed by combining one or more propositions using logical connectives. A proposition that is not compound is called an atomic proposition.

Resource 1: Semantics of the Standard Logical Connectives

If $𝑃$ and $𝑄$ are propositions, then the following are common logical connectives:

$\neg 𝑃$ , called the negation of $𝑃$ , read “not $𝑃$ .”
$𝑃 \land 𝑄$ , called the conjunction of $𝑃$ and $𝑄$ , read “ $𝑃$ and $𝑄$ .”
$𝑃 \lor 𝑄$ , called the disjunction of $𝑃$ and $𝑄$ , read “ $𝑃$ or $𝑄$ .”
$𝑃 \Rightarrow 𝑄$ , called the implication from $𝑃$ to $𝑄$ , read “if $𝑃$ then $𝑄$ ” or “ $𝑃$ implies $𝑄$ .”
$𝑃 \Leftrightarrow 𝑄$ , called the biconditional between $𝑃$ and $𝑄$ , read “ $𝑃$ if and only if $𝑄$ .”

The above connectives are listed in order of binding precedence. Also, the implication operator $\Rightarrow$ is right-associative, while the other binary connectives are left-associative.

Example.

The compound proposition

𝑝 \land 𝑞 \lor 𝑟

unambigously denotes

(𝑝 \land 𝑞) \lor 𝑟

since

\land

binds more tightly than

\lor

Example.

The compound proposition

𝑝 \Rightarrow 𝑞 \Rightarrow 𝑟

unambiguously denotes

𝑝 \Rightarrow (𝑞 \Rightarrow 𝑟)

since

\Rightarrow

is right-associative.

Terminology: Tautology and Contradiction

A proposition is a tautology, denoted $𝐭$ or $⊤$ , if it is assumed to be true under all circumstances. A proposition is a contradiction, denoted $𝐜$ or $⊥$ , if it is assumed to be false under all circumstances.

Well-Formed Propositional Formulae

Formally, we can define the syntax of compound propositions using the notion of propositional formulae. A propositional formula is an abstract syntactic object that represents a proposition. Propositional formulae are built from propositional variables and logical connectives according to the following rules:

Definition 5: Well-Formed Propositional Formula

Let $Φ$ a set of propositional variables, and let $Ψ$ be a set of logical connectives over $Φ$ . The set of well-formed propositional formulae over $Ψ$ , denoted $𝒲 (Φ, Ψ)$ , is the smallest set such that the following rules hold:

Trivial Formulae. $𝐭 \in 𝒲 (Φ, Ψ)$ and $𝐜 \in 𝒲 (Φ, Ψ)$ .
Atomic Formulae. If $𝑝 \in Φ$ , then $𝑝 \in 𝒲 (Φ, Ψ)$ .
Unary Connectives. For all $𝑃 \in 𝒲 (Φ, Ψ)$ and for all unary connectives $⋆ \in Ψ$ , we have $(⋆ 𝑃) \in 𝒲 (Φ, Ψ)$ .
Binary Connectives. For all $𝑃, 𝑄 \in 𝒲 (Φ, Ψ)$ and for all binary connectives $⋆ \in Ψ$ , we have $(𝑃 ⋆ 𝑄) \in 𝒲 (Φ, Ψ)$ .

This definition of a well-formed propositional formula rigorously defines a syntax under which we can write compound propositions.

Example.

Φ = {△, □, ○}

and

Ψ = {⋆, *}

where

⋆

is a unary connective and

*

is a binary connective, then

𝒲 (Φ, Ψ)

would include formulae such as

(⋆ △)

(□ * ○)

, and

(⋆ (△ * □))

𝒲 (Φ, Ψ)

would not include

(△ □)

, since there is no connective between

△

and

□

Proposition 1: Unique Readability of Propositional Formulae

Let $𝑃 \in 𝒲 (Φ, Ψ)$ . Then exactly one of the following holds:

$𝑃 = 𝐭$ or $𝑃 = 𝐜$ .
$𝑃 \in Φ$ .
$\exists! 𝑄 \in 𝒲 (Φ, Ψ)$ such that $𝑃 = (⋆ 𝑄)$ for some unary connective $⋆ \in Ψ$ .
$\exists! 𝑄, 𝑅 \in 𝒲 (Φ, Ψ)$ such that $𝑃 = (𝑄 ⋆ 𝑅)$ for some binary connective $⋆ \in Ψ$ .

The definition of well-formed formulae is a bit abstract, so it would be useful to restrict it to the set of familiar connectives we want to eventually assign semantics to. Define a set of standard logical connectives $Ψ$ that we will implicitly assume:

Definition 6: Standard Logical Connectives

Let $\neg$ be a unary connective, and let $\land$ , $\lor$ , $\Rightarrow$ , and $\Leftrightarrow$ be binary connectives. Then the set of standard logical connectives is defined as $Ψ = {\neg, \land, \lor, \Rightarrow, \Leftrightarrow}$ .

Notation: Precendence and Associativity

When unambiguous, we will often omit parentheses in propositional formulae, relying on the standard binding precedence and associativity of the logical connectives to disambiguate:

Define the binding strength from tightest to loosest of the standard logical connectives as $(\neg, \land, \lor, \Rightarrow, \Leftrightarrow)$ .
Define $(\neg \neg 𝑃)$ to mean $(\neg (\neg 𝑃))$ .
Define $(𝑃 ⋆ 𝑄 ⋆ 𝑅)$ to mean $((𝑃 ⋆ 𝑄) ⋆ 𝑅)$ for the connectives $\land$ , $\lor$ , and $\Leftrightarrow$ .
Define $(𝑃 \Rightarrow 𝑄 \Rightarrow 𝑅)$ to mean $(𝑃 \Rightarrow (𝑄 \Rightarrow 𝑅))$ .

Notation

Unless specified, assume that the set of propositional formulae is defined under the standard logical connectives from Definition 6. Consequently, let $𝒲 (Φ)$ denote the set of well-formed propositional formulae over $Φ$ under the standard logical connectives.

Definition 7: Subformula

Let $𝑃 \in 𝒲 (Φ, Ψ)$ . A subformula of $𝑃$ is any formula that appears as a part of $𝑃$ . Formally, the set of subformulae of $𝑃$ , denoted $Sub (𝑃)$ , is defined recursively as follows:

If $𝑃 = 𝐭$ , $𝑃 = 𝐜$ , or $𝑃 \in Φ$ , then $Sub (𝑃) = {𝑃}$ .
If $𝑃 = (⋆ 𝑄)$ for some unary connective $⋆ \in Ψ$ , then $Sub (𝑃) = {𝑃} \cup Sub (𝑄)$ .
If $𝑃 = (𝑄 ⋆ 𝑅)$ for some binary connective $⋆ \in Ψ$ , then $Sub (𝑃) = {𝑃} \cup Sub (𝑄) \cup Sub (𝑅)$ .

Example.

Sub (𝑝 \land (𝑞 \lor 𝑟)) = {𝑝, 𝑞, 𝑟, 𝑞 \lor 𝑟, 𝑝 \land (𝑞 \lor 𝑟)}

Definition 8: Complexity and Depth of a Propositional Formula

The complexity of a propositional formula $𝑃$ , denoted $complexity (𝑃)$ , is the total number of logical connectives in $𝑃$ . Formally, if $𝑃 \in 𝒲 (Φ, Ψ)$ , then:

{\begin{matrix} complexity (𝑝) = 0 & if 𝑝 = 𝐭 or 𝑝 = 𝐜 or 𝑝 \in Φ \\ complexity (⋆ 𝑃) = 1 + complexity (𝑃) & if 𝑃 \in 𝒲 (Φ, Ψ) and ⋆ \in Ψ \\ complexity (𝑃 ⋆ 𝑄) = 1 + complexity (𝑃) + complexity (𝑄) & if 𝑃, 𝑄 \in 𝒲 (Φ, Ψ) and ⋆ \in Ψ \end{matrix}

The depth of a propositional formula $𝑃$ , denoted $depth (𝑃)$ , is the length of the longest path from the root of $𝑃$ to any leaf in the parse tree of $𝑃$ . Formally, if $𝑃 \in 𝒲 (Φ, Ψ)$ , then:

{\begin{matrix} depth (𝑝) = 0 & if 𝑝 = 𝐭 or 𝑝 = 𝐜 or 𝑝 \in Φ \\ depth (⋆ 𝑃) = 1 + depth (𝑃) & if 𝑃 \in 𝒲 (Φ, Ψ) and ⋆ \in Ψ \\ depth (𝑃 ⋆ 𝑄) = 1 + \max (depth (𝑃), depth (𝑄)) & if 𝑃, 𝑄 \in 𝒲 (Φ, Ψ) and ⋆ \in Ψ \end{matrix}

Example.

Let

𝑃 = 𝑝 \land (𝑞 \lor 𝑟)

. Then

complexity (𝑃) = 2

since there are two logical connectives in

𝑃

, and

depth (𝑃) = 2

Truth Assignments and Semantics

While propositional formulae are syntactic objects, we can assign them meaning by defining truth assignments that specify the truth value of each propositional variable.

Definition 9: Truth Assignment

A truth assignment $𝜎$ over a set of propositional variables $Φ$ is a function that assigns a truth value to each propositional variable in $Φ$ (and by extension, to all propositional formulae over $Φ$ ).

Formally, a truth assignment $𝜎$ over $Φ$ is a function that satisfies:

\begin{matrix} 𝜎 & : 𝒲 (Φ) \to {𝖳, 𝖥} . \end{matrix}

where $𝒲 (Φ)$ denotes the set of all propositional formulae over $Φ$ .

Example.

By saying

𝜎 (𝑝) = 𝖳

, we are asserting that the propositional variable

𝑝

is true under the truth assignment

𝜎

Example.

Let $Φ = {𝑝, 𝑞}$ be a set of propositional variables. Then a truth assignment $𝜎$ over $Φ$ could be defined as follows:

𝜎 (𝑝) = 𝖳, 𝜎 (𝑞) = 𝖥, 𝜎 (𝑝 \land 𝑞) = 𝖥, 𝜎 (𝑝 \lor 𝑞) = 𝖳, \dots

Another truth assignment over $Φ$ , say $𝜉$ , could be defined differently as:

𝜉 (𝑝) = 𝖥, 𝜉 (𝑞) = 𝖥, 𝜉 (𝑝 \land 𝑞) = 𝖥, 𝜉 (𝑝 \lor 𝑞) = 𝖥, \dots

There are many possible truth assignments over a set of propositional variables. Specifically, if $Φ$ is a set of $𝑛$ propositional variables, then there are $2^{𝑛}$ possible truth assignments over $Φ$ , since each propositional variable can be assigned one of two values ( $𝖳$ or $𝖥$ ) independently.

Corollary 1: Number of Truth Assignments

Let $Φ$ be a set of $𝑛$ propositional variables. Then there are $2^{𝑛}$ possible truth assignments over $Φ$ .

Definition 10: Satisfaction of Propositional Formulae

A propositional formula $𝑃$ is satisfied under a truth assignment $𝜎$ , denoted $𝜎 ⊨ 𝑃$ , if $𝜎 (𝑃) = 𝖳$ . Otherwise, if $𝜎 (𝑃) = 𝖥$ , we say that $𝑃$ is not satisfied under $𝜎$ , denoted $𝜎 ⊭ 𝑃$ .

Terminology: Satisfiability of Propositional Formulae

A propositional formula $𝑃$ is satisfiable if there exists a truth assignment $𝜎$ such that $𝜎 ⊨ 𝑃$ . Otherwise, $𝑃$ is unsatisfiable.

We can now rigorously define tautologies and contradictions in terms of truth assignments:

Definition 11: Tautology and Contradiction

Let $Φ$ be a set of propositional variables. A propositional formula $𝑃$ over $Φ$ is a tautology if $𝜎 ⊨ 𝑃$ for all truth assignments $𝜎$ over $Φ$ .

On the other hand, a propositional formula $𝑃$ is a contradiction if $𝜎 ⊭ 𝑃$ for all truth assignments $𝜎$ over $Φ$ .

Boolean Functions and Truth Tables

Definition 12: Boolean Parameterization

The Boolean parameterization $𝑓 : {𝖳, 𝖥}^{𝑛} \to {𝖳, 𝖥}$ of a propositional formula $𝑃$ over the variables $Φ = {𝑝_{1}, 𝑝_{2}, \dots, 𝑝_{𝑛}}$ is the Boolean function defined by:

𝑓 (𝜎 (𝑝_{1}), 𝜎 (𝑝_{2}), \dots, 𝜎 (𝑝_{𝑛})) = 𝜎 (𝑃) for all truth assignments 𝜎 over Φ .

Example.

Let $𝑃 = 𝑝_{1} \land \neg 𝑝_{2}$ be a propositional formula over the variables $Φ = {𝑝_{1}, 𝑝_{2}}$ . Then the Boolean parameterization of $𝑃$ is the function $𝑓 : {𝖳, 𝖥}^{2} \to {𝖳, 𝖥}$ defined by:

𝑓 (𝖳, 𝖳) = 𝖥, 𝑓 (𝖳, 𝖥) = 𝖳, 𝑓 (𝖥, 𝖳) = 𝖥, 𝑓 (𝖥, 𝖥) = 𝖥 .

Definition 13: Truth Table

The truth table of a propositional formula $𝑃$ over the variables $Φ = {𝑝_{1}, 𝑝_{2}, \dots, 𝑝_{𝑛}}$ is a tabular representation of all possible truth assignments. Specifically, each row corresponds to a possible truth assignment over $Φ$ , and the last column gives the truth value of $𝑃$ under that assignment:

$𝑝_{1}$	$𝑝_{2}$	$\dots$	$𝑝_{𝑛}$	$\dots$	$𝑃$
$𝜎_{1} (𝑝_{1})$	$𝜎_{1} (𝑝_{2})$	$\dots$	$𝜎_{1} (𝑝_{𝑛})$	$\dots$	$𝜎_{1} (𝑃)$
$𝜎_{2} (𝑝_{1})$	$𝜎_{2} (𝑝_{2})$	$\dots$	$𝜎_{2} (𝑝_{𝑛})$	$\dots$	$𝜎_{2} (𝑃)$
$⋮$	$⋮$	$⋱$	$⋮$	$⋱$	$⋮$
$𝜎_{𝑚} (𝑝_{1})$	$𝜎_{𝑚} (𝑝_{2})$	$\dots$	$𝜎_{𝑚} (𝑝_{𝑛})$	$\dots$	$𝜎_{𝑚} (𝑃)$

Where $𝜎_{1}, 𝜎_{2}, \dots, 𝜎_{𝑚}$ are the $2^{𝑛}$ possible truth assignments over $Φ$ . Auxiliary columns of the truth table may be added to show the truth values of subformulae of $𝑃$ under each truth assignment.

Example.

A truth table for the propositional formula $(𝑝 \Rightarrow 𝑞) \Rightarrow 𝑝$ is:

$𝑝$	$𝑞$	$𝑝 \Rightarrow 𝑞$	$(𝑝 \Rightarrow 𝑞) \Rightarrow 𝑝$
$𝖳$	$𝖳$	$𝖳$	$𝖳$
$𝖳$	$𝖥$	$𝖥$	$𝖳$
$𝖥$	$𝖳$	$𝖳$	$𝖥$
$𝖥$	$𝖥$	$𝖳$	$𝖥$

Notice that all rows have the same truth value in the $𝑝$ and $(𝑝 \Rightarrow 𝑞) \Rightarrow 𝑝$ columns. In other words, $𝑝$ and $(𝑝 \Rightarrow 𝑞) \Rightarrow 𝑝$ have the same truth value under every possible truth assignment, so $𝑝 \equiv (𝑝 \Rightarrow 𝑞) \Rightarrow 𝑝$ .

Property

Let $𝑃$ be the propositional formula corresponding to a column of a truth table. $𝑃$ is a tautology iff all entries in the column are $𝖳$ , and $𝑃$ is a contradiction iff all entries in the column are $𝖥$ . $𝑃$ is satisfiable iff at least one entry in the column is $𝖳$ .

Semantics of Logical Connectives

Until now, logical connectives like $\neg$ , $\land$ , and $\lor$ have been treated as syntactic objects that can be used to build propositional formulae, but they have not been given any meaning. Under a truth assignment, we can properly define the semantics of the logical connectives.

Definition 14: Negation

Under a truth assignment $𝜎$ , the negation of a propositional formula $𝑃$ , denoted $\neg 𝑃$ and read “not $𝑃$ ”, is defined by:

𝜎 (\neg 𝑃) = {\begin{matrix} 𝖳 & if 𝜎 ⊭ 𝑃 \\ 𝖥 & otherwise \end{matrix}

Definition 15: Conjunction

Under a truth assignment $𝜎$ , the conjunction of two propositional formulae $𝑃$ and $𝑄$ , denoted $𝑃 \land 𝑄$ and read “ $𝑃$ and $𝑄$ ”, is defined by:

𝜎 (𝑃 \land 𝑄) = {\begin{matrix} 𝜎 (𝑄) & if 𝜎 ⊨ 𝑃 \\ 𝖥 & otherwise \end{matrix}

Definition 16: Disjunction

The disjunction of two propositional formulae $𝑃$ and $𝑄$ , denoted $𝑃 \lor 𝑄$ and read “ $𝑃$ or $𝑄$ ”, is defined by:

𝜎 (𝑃 \lor 𝑄) = {\begin{matrix} 𝜎 (𝑄) & if 𝜎 ⊭ 𝑃 \\ 𝖳 & otherwise \end{matrix}

Definition 17: Implication

The implication from a propositional formula $𝑃$ to a propositional formula $𝑄$ , denoted $𝑃 \Rightarrow 𝑄$ and read “if $𝑃$ then $𝑄$ ”, is defined by:

𝜎 (𝑃 \Rightarrow 𝑄) = {\begin{matrix} 𝖳 & if 𝜎 ⊭ 𝑃 \\ 𝜎 (𝑄) & otherwise \end{matrix}

When $𝜎 (𝑃) = 𝖥$ , the implication $𝑃 \Rightarrow 𝑄$ is true regardless of the truth value of $𝑄$ , in which case we say that $𝑃 \Rightarrow 𝑄$ is vacuously true.

Definition 18: Biconditional

The biconditional between two propositional formulae $𝑃$ and $𝑄$ , denoted $𝑃 \Leftrightarrow 𝑄$ and read “ $𝑃$ if and only if $𝑄$ ”, is defined by:

𝜎 (𝑃 \Leftrightarrow 𝑄) = {\begin{matrix} 𝖳 & if 𝜎 (𝑃) = 𝜎 (𝑄) \\ 𝖥 & otherwise \end{matrix}

Logical Equivalences

Definition 19: Logical Equivalence

Two propositional formulae $𝑃$ and $𝑄$ are logically equivalent, denoted $𝑃 \equiv 𝑄$ , iff $𝑃$ and $𝑄$ have the same truth value under every possible truth assignment. That is,

𝑃 \equiv 𝑄 iff 𝜎 (𝑃) = 𝜎 (𝑄) for all possible truth assignments 𝜎 .

Corollary 2: Logical Equivalence as a Biconditional

Let $𝑃$ and $𝑄$ be propositional formulae. Then $𝑃 \equiv 𝑄$ iff $𝑃 \Leftrightarrow 𝑄$ is a tautology.

Property

Let $𝑃$ and $𝑄$ be propositional formulae corresponding to columns of a truth table. $𝑃 \equiv 𝑄$ iff the entries in the $𝑃$ and $𝑄$ columns are the same for every row.

Definition 20: Propositional Axioms

For all propositional formulae $𝑃$ , $𝑄$ , and $𝑅$ , the following laws hold:

Associativity.
$𝑃 \lor (𝑄 \lor 𝑅) \equiv (𝑃 \lor 𝑄) \lor 𝑅 and 𝑃 \land (𝑄 \land 𝑅) \equiv (𝑃 \land 𝑄) \land 𝑅 .$
Commutativity.
$𝑃 \lor 𝑄 \equiv 𝑄 \lor 𝑃 and 𝑃 \land 𝑄 \equiv 𝑄 \land 𝑃 .$
Distributivity.
$𝑃 \lor (𝑄 \land 𝑅) \equiv (𝑃 \lor 𝑄) \land (𝑃 \lor 𝑅) and 𝑃 \land (𝑄 \lor 𝑅) \equiv (𝑃 \land 𝑄) \lor (𝑃 \land 𝑅) .$
Identity.
$𝑃 \lor 𝐜 \equiv 𝑃 and 𝑃 \land 𝐭 \equiv 𝑃 .$
Existence of Complements.
$𝑃 \lor \neg 𝑃 \equiv 𝐭 and 𝑃 \land \neg 𝑃 \equiv 𝐜 .$

To simplify propositional formulae, we can use logical equivalences to rewrite them in simpler forms.

Theorem 1: Double Negation Law

For all propositional formulae $𝑃$ , it holds that $\neg \neg 𝑃 \equiv 𝑃$ .

Proof: Double Negation Law.

Suppose

𝑃

is a propositional formula. Then:

Theorem 2: De Morgan’s Laws

For all propositional formulae $𝑃$ and $𝑄$ , the following equivalences hold:

\neg (𝑃 \lor 𝑄) \equiv \neg 𝑃 \land \neg 𝑄 and \neg (𝑃 \land 𝑄) \equiv \neg 𝑃 \lor \neg 𝑄 .

Resource 2: Logical Equivalences

	Name	Equivalence
Axioms	Commutativity over $\land$	$𝑃 \land 𝑄 \equiv 𝑄 \land 𝑃$
	Commutativity over $\lor$	$𝑃 \lor 𝑄 \equiv 𝑄 \lor 𝑃$
	Associativity over $\land$	$𝑃 \land (𝑄 \land 𝑅) \equiv (𝑃 \land 𝑄) \land 𝑅$
	Associativity over $\lor$	$𝑃 \lor (𝑄 \lor 𝑅) \equiv (𝑃 \lor 𝑄) \lor 𝑅$
	Distributivity of $\land$ over $\lor$	$𝑃 \land (𝑄 \lor 𝑅) \equiv (𝑃 \land 𝑄) \lor (𝑃 \land 𝑅)$
	Distributivity of $\lor$ over $\land$	$𝑃 \lor (𝑄 \land 𝑅) \equiv (𝑃 \lor 𝑄) \land (𝑃 \lor 𝑅)$
	Identity for $\land$	$𝑃 \land 𝐭 \equiv 𝑃$
	Identity for $\lor$	$𝑃 \lor 𝐜 \equiv 𝑃$
Equivalences over $\neg, \land, \lor$	Law of Excluded Middle	$𝑃 \lor \neg 𝑃 \equiv 𝐭$
	Law of Non-Contradiction	$𝑃 \land \neg 𝑃 \equiv 𝐜$
	Domination of $\lor$	$𝑃 \lor 𝐭 \equiv 𝐭$
	Domination of $\land$	$𝑃 \land 𝐜 \equiv 𝐜$
	Double Negation	$\neg \neg 𝑃 \equiv 𝑃$
	De Morgan’s Law over $\land$	$\neg (𝑃 \land 𝑄) \equiv \neg 𝑃 \lor \neg 𝑄$
	De Morgan’s Law over $\lor$	$\neg (𝑃 \lor 𝑄) \equiv \neg 𝑃 \land \neg 𝑄$
	Absorption Law over $\land$	$𝑃 \land (𝑃 \lor 𝑄) \equiv 𝑃$
	Absorption Law over $\lor$	$𝑃 \lor (𝑃 \land 𝑄) \equiv 𝑃$
	Idempotency of $\land$	$𝑃 \land 𝑃 \equiv 𝑃$
	Idempotency of $\lor$	$𝑃 \lor 𝑃 \equiv 𝑃$
Implication Equivalences	Material Implication	$𝑃 \Rightarrow 𝑄 \equiv \neg 𝑃 \lor 𝑄$
	Contraposition of $\Rightarrow$	$𝑃 \Rightarrow 𝑄 \equiv \neg 𝑄 \Rightarrow \neg 𝑃$
	Exportation of $\Rightarrow$	$(𝑃 \land 𝑄) \Rightarrow 𝑅 \equiv 𝑃 \Rightarrow (𝑄 \Rightarrow 𝑅)$
	Elimination using $\lor$	$𝑃 \lor 𝑄 \equiv \neg 𝑃 \Rightarrow 𝑄$
Biconditional Equivalences	Definition of Biconditional	$𝑃 \Leftrightarrow 𝑄 \equiv (𝑃 \land 𝑄) \lor (\neg 𝑃 \land \neg 𝑄)$
	Material Biconditional	$𝑃 \Leftrightarrow 𝑄 \equiv (𝑃 \Rightarrow 𝑄) \land (𝑄 \Rightarrow 𝑃)$
	Contraposition of $\Leftrightarrow$	$𝑃 \Leftrightarrow 𝑄 \equiv \neg 𝑃 \Leftrightarrow \neg 𝑄$
	Exportation of $\Leftrightarrow$	$(𝑃 \land 𝑄) \Leftrightarrow 𝑅 \equiv 𝑃 \Leftrightarrow (𝑄 \Leftrightarrow 𝑅)$
	Negation of Biconditional	$\neg (𝑃 \Leftrightarrow 𝑄) \equiv 𝑃 \Leftrightarrow \neg 𝑄$

Normal Forms

Definition 21: Literal

A literal over a set of propositional variables $Φ$ is either a propositional variable $𝑝 \in Φ$ or the negation of a propositional variable $\neg 𝑝$ for some $𝑝 \in Φ$ .

Definition 22: Negation Normal Form

A propositional formula is in negation normal form (NNF) if the negation operator $\neg$ only applies to propositional variables, and the only logical connectives are conjunctions and disjunctions.

Definition 23: Disjunctive Normal Form

A propositional formula is in disjunctive normal form (DNF) if it is a disjunction of conjunctions of literals.

Definition 24: Conjunctive Normal Form

A propositional formula is in conjunctive normal form (CNF) if it is a conjunction of disjunctions of literals.

Theorem 3: Existence of Normal Forms

For all propositional formulae $𝑃$ , there exist propositional formulae in NNF, DNF, and CNF that are logically equivalent to $𝑃$ .

Proposition 2: Length Complexity of Normal Forms

The number of symbols needed to express a propositional formula $𝑃$ in CNF or DNF has a length complexity of $𝒪 (2^{𝑛})$ , where $𝑛$ is the number of propositional variables in $𝑃$ .

Counting Formulae

Functional Completeness

Definition 25: Functionally Complete Set of Connectives

A set of logical connectives $Ψ_{1}$ over $Φ$ is functionally complete over $Ψ_{2}$ iff for every propositional formula $𝑃 \in 𝒲 (Φ, Ψ_{2})$ , there exists a propositional formula $𝑄 \in 𝒲 (Φ, Ψ_{1})$ such that $𝑃 \equiv 𝑄$ .

Theorem 4: Alternative Characterization of Functional Completeness

A set of logical connectives $Ψ$ over a set $Φ = {𝑝_{1}, 𝑝_{2}, \dots, 𝑝_{𝑛}}$ iff for every truth assignment $𝜎$ over $Φ$

Theorem 5: Functional Completeness over Standard Logical Connectives

Each of ${\neg, \land}$ , ${\neg, \lor}$ , and ${\neg, \Rightarrow}$ is functionally complete over the set of standard logical connectives.

Definition 26: Sheffer Stroke and Peirce’s Arrow

The Sheffer stroke (also called the NAND operator) is a binary connective denoted by $↑$ and defined by $𝑃 ↑ 𝑄 \equiv \neg (𝑃 \land 𝑄)$ . Peirce’s arrow (also called the NOR operator) is a binary connective denoted by $↓$ and defined by $𝑃 ↓ 𝑄 \equiv \neg (𝑃 \lor 𝑄)$ .

Theorem 6: Functional Completeness of Sheffer Stroke and Peirce’s Arrow

Each of ${↑, ↓}$ is functionally complete over the set of standard logical connectives.

Resolution

Exercises

Exercise 1.

Compute the truth table for the proposition

(𝑝 \Rightarrow 𝑞) \Leftrightarrow (\neg 𝑞 \Rightarrow \neg 𝑝)

Exercise 2.

Convert

\neg (𝑝 \Rightarrow (𝑞 \land \neg 𝑟))

to NNF, DNF, and CNF.

Exercise 3.

Show that

(𝑝 \lor 𝑞) \Rightarrow 𝑟 \equiv (𝑝 \Rightarrow 𝑟) \land (𝑞 \Rightarrow 𝑟)

Exercise 4.

Show that

(𝑝 \Rightarrow 𝑞 \Rightarrow 𝑟) \Rightarrow (𝑝 \Rightarrow 𝑞) \Rightarrow 𝑝 \Rightarrow 𝑟

is a tautology.

Exercise 5.

Show that

{\lor}

is not functionally complete over the set of standard logical connectives.

Exercise 6.