Propositional Logic

Instructor

Li Hui

Propositions and Logical Connectives

Mathematical logic studies logic using mathematical methods (introducing a symbolic system), also known as symbolic logic.

Mathematical logic is widely applied in automated theorem proving, artificial intelligence, programming, and other fields.

Artificial intelligence is an emerging discipline that arose after the invention of computers. Building on mathematical logic and statistics, its goal is to enable machines to approximate human thinking and logical reasoning.

Applications of Mathematical Logic in Computer Science

Foundation of Computer Hardware System Design

Computer arithmetic is implemented through digital logic technology; Boolean algebra and normal forms are the foundational theory of digital logic.
The design of switching circuits in computer science also uses Boolean algebra and normal forms from mathematical logic.

Example: A bank vault is equipped with an automatic alarm system. It can only be activated when a manual control switch in the general manager’s office is closed. If this manual switch is closed, an alarm will sound if the vault door is forced open, or if a staff member has not cut the power supply and someone is in the passage leading to the vault. Design this control circuit.

Let $p$: The manual switch is closed. $q$: The vault door is forced open. $r$: A staff member has not cut the power supply. $s$: Someone is in the passage leading to the vault. $F$: The automatic alarm system sounds. \[F{\Leftrightarrow}P{\wedge}(Q{\vee}(R{\wedge}S)).\]

Foundation of Artificial Intelligence

Artificial intelligence is a science grounded in computational mathematics and the Turing machine, which reasons about and solves problems to enable machines to perform intelligent tasks.

Logical reasoning is one of the most enduring subfields of artificial intelligence research.

Logic is the foundation of all mathematical reasoning.

Alan Turing (1912.6.23 - 1954.6.7)

British mathematician and logician.
Turing enrolled as an undergraduate at King’s College, Cambridge in 1931 and received his PhD from Princeton University. During World War II he returned to Cambridge and assisted the military in breaking the German Enigma cipher, helping the Allies achieve victory.
In the field of artificial intelligence, Turing proposed the Turing Test, a method for determining whether a machine exhibits intelligence.
Furthermore, the Turing machine model proposed by Turing is the theoretical prototype of modern computers.

Applications of Mathematical Logic in Everyday Life

Personnel Assignment Problems

Example: Among four people $A$, $B$, $C$, and $D$, two are to be sent on a business trip. How should they be selected based on the following three conditions?

If $A$ goes, then exactly one of $C$ or $D$ must go.
$B$ and $C$ cannot both go.
If $C$ goes, then $D$ must stay.

Mathematical logic in discrete mathematics mainly covers propositional logic and predicate logic (first-order logic).

The central problem of study: reasoning.

The basic element of reasoning (premises ${\rightarrow}$ conclusion) is the proposition.

Propositions

Proposition: A declarative sentence that has a truth value or can be judged as true or false.

Two conditions: (1) It is a declarative sentence; (2) It can be judged as true or false.

Truth value: The value assigned to a proposition.

Every proposition has a unique truth value.

True proposition: truth value is true ($T$, 1)
False proposition: truth value is false ($F$, 0)

Example: Determine whether each of the following sentences is a proposition.

How are you?
No smoking!
$x+y>5$.
Taiwan is a part of China.

Solution:

and (2) are not declarative sentences, so they are not propositions.
Although it is a declarative sentence, its truth value varies with $x$ and $y$ and is indeterminate, so it is not a proposition.
is a true proposition.

Humans can live to a thousand years old.
There are living organisms on the Moon.
The barber shaves all and only those who do not shave themselves.

Solution: (5) is a false proposition.

As for (6), no one can currently determine its truth value, but the proposition “there are living organisms on the Moon” definitely has a unique answer (organisms exist or they do not, i.e., the proposition is either true or false), so it is a proposition.

is a declarative sentence, but its truth value cannot be determined. This is a paradox.

The Barber Paradox:

The barber does not shave himself ${\Rightarrow}$ the barber should shave himself
The barber shaves himself ${\Rightarrow}$ the barber should not shave himself

Propositions are classified into simple propositions and compound propositions.

Simple proposition: A proposition formed by a simple sentence (also called an atomic proposition).

A simple proposition cannot be further divided. Simple propositions are generally denoted by lowercase letters $p, q, r{\cdots}$ and their subscripted forms $p_i, q_i, r_i, {\cdots}$. These symbols representing simple propositions are called propositional variables (or propositional identifiers).

Example:

$p$: Hainan is a beautiful island
$q$: Today is sunny

Compound proposition: A proposition formed by combining several atomic propositions with connectives (also called a molecular proposition).

Example:

If I had a pair of wings, then I could fly in the blue sky.
It will snow tomorrow or it will rain tomorrow.

The representation and truth value of a compound proposition depend on the atomic propositions it contains and the connectives used; these connectives are also called logical connectives.

Logical Connectives

Definition: Let $p$ be a proposition. The negation of $p$ is called the negation of proposition $p$, denoted ${\lnot}p$ (or ${\sim}p$).

The symbol ${\lnot}$ is called the negation connective.

In natural language, expressions such as “not”, “it is not the case that”, “does not hold”, “there is no”, and “is incorrect” can all be symbolized as ${\lnot}$.

The truth value of compound proposition ${\lnot}P$ is given by the following table; ${\lnot}P$ is true if and only if $P$ is false.

\[ \begin{array}{cc} p & {\lnot}p \\ 0 & 1 \\ 1 & 0 \\ \end{array} \]

Let $p$: Hangzhou is a city

Then ${\lnot}p$: Hangzhou is not a city

Let $q$: Every real number can be expressed as a fraction

Then ${\lnot}q$: Not every real number can be expressed as a fraction

Definition: Let $p$, $q$ be propositions. The compound proposition “$p$ and $q$” is called the conjunction of $p$ and $q$, denoted $p{\wedge}q$.

The symbol ${\wedge}$ is called the conjunction connective.

In natural language, connectives expressing “and”, such as: “both ${\cdots}$ and ${\cdots}$”,

“not only ${\cdots}$ but also ${\cdots}$”,

“at the same time ${\cdots}$ and ${\cdots}$”,

“${\cdots}$ and ${\cdots}$”,

“${\cdots}$ together with ${\cdots}$”

can all be symbolized as ${\wedge}$.

The truth value of compound proposition $p{\wedge}q$ is given by the following table.

\[ \begin{array}{ccc} p & q & p{\wedge}q \\ 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \end{array} \]

The truth value of $p{\wedge}q$ is true if and only if both $p$ and $q$ are true.

Let $p$: Li Ming is watching a movie, $q$: Zhang Hua is watching a movie.

Then $p{\wedge}q$: Both Li Ming and Zhang Hua are watching movies.

Definition: Let $p$, $q$ be propositions. The compound proposition “$p$ or $q$” is called the disjunction of $p$ and $q$, denoted $p{\vee}q$.

The symbol ${\vee}$ is called the disjunction connective.

The truth value of compound proposition $p{\vee}q$ is given by the following table. $p{\vee}q$ is true if and only if at least one of $p$, $q$ is true.

\[ \begin{array}{ccc} p & q & p{\vee}q \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \\ \end{array} \]

In natural language, “$\cdots$ or $\cdots$” and “either $\cdots$ or $\cdots$” can all be symbolized as “$p{\vee}q$”.

Let $p$: He is now in Shanghai; $q$: He is now in Guangzhou.

Then $p{\vee}q$: He is now in Shanghai or in Guangzhou.

Let $r$: We have Discrete Mathematics in the first class; $s$: We have Advanced Mathematics in the first class.

Then $r{\vee}s$: We have Discrete Mathematics or Advanced Mathematics in the first class.

Definition: Let $p$, $q$ be propositions. The compound proposition “if $p$ then $q$” is called the conditional (implication) of $p$ and $q$, denoted $p{\rightarrow}q$.

The symbol ${\rightarrow}$ is called the implication connective (conditional connective).

Here $p$ is called the antecedent and $q$ is called the consequent of the conditional.

The truth value of compound proposition $p{\rightarrow}q$ is given by the following table.

\[ \begin{array}{ccc} p & q & p{\rightarrow}q \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \end{array} \]

Let $p$: He has time, $q$: He will help you.

Then $p{\rightarrow}q$: If he has time, then he will help you.

Let $p$: Sharks can fly, $q$: The Great Wall is in northern China.

Then $p{\rightarrow}q$: If sharks can fly, then the Great Wall is in northern China.

Since proposition $p$ is false and proposition $q$ is true, proposition $p{\rightarrow}q$ is true.

In natural language, there is usually some intrinsic connection between “if $\cdots$” and “then $\cdots$”.

In mathematical logic, for $p{\rightarrow}q$, as long as $p$ and $q$ are propositions, $p{\rightarrow}q$ is meaningful, without requiring any particular relationship between $p$ and $q$.

The logical relationship of $p{\rightarrow}q$ is that $q$ is a necessary condition for $p$, or equivalently, $p$ is a sufficient condition for $q$.

In natural language, especially in mathematics, the statement that $q$ is a necessary condition for $p$ can be expressed in many different ways:

“Whenever $p$, then $q$”
“Only if $q$, then $p$”
“If $p$, then $q$”
“Unless $q$, then not $p$”
“Because $p$, therefore $q$”

All of the above expressions appear different on the surface but all convey that $q$ is a necessary condition for $p$; therefore, the connective used should be symbolized as $p{\rightarrow}q$

Example:

If it rains, then I will ride my bicycle to school.
Whenever it rains, I will ride my bicycle to school.
It is raining, so I ride my bicycle to school.

Let $p$: It is raining, $q$: I ride my bicycle to school. The above proposition can be symbolized as: $p{\rightarrow}q$.

Definition: Let $p$ and $q$ be propositions. The compound proposition “$p$ if and only if $q$” is called the biconditional (equivalence) of $p$ and $q$, denoted $p{\leftrightarrow}q$.

The symbol ${\leftrightarrow}$ is called the biconditional connective (equivalence connective).

The truth value of compound proposition $p{\leftrightarrow}q$ is given by the following table.

\[ \begin{array}{ccc} p & q & p{\leftrightarrow}q \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \end{array} \]

In natural language, “if and only if”, “is equivalent to”, “is the same as $\cdots$”, etc. can all be symbolized as ${\leftrightarrow}$.

The basic logical relationship expressed by the biconditional is that $p$ and $q$ are each other’s necessary and sufficient condition.

Let $p$: Two circles have equal areas, $q$: Two circles have equal radii.

Then $p{\leftrightarrow}q$: Two circles have equal areas if and only if they have equal radii.

The truth value of a compound proposition depends only on the truth values of its atomic propositions, not on their content.

Summary

\[ \begin{array}{ccccccc} p & q & {\lnot}p & p{\wedge}q & p{\vee}q & p{\rightarrow}q &p{\leftrightarrow}q \\ 0 & 0 & 1&0&0&1&1 \\ 0 & 1 & 1&0&1&1&0 \\ 1 & 0 & 0&0&1&0&0 \\ 1 & 1 & 0&1&1&1&1 \\ \end{array} \]

Where: 0 represents $F$ (false) and 1 represents $T$ (true)

Propositional Formulas and Truth Tables

In propositional logic, there is a distinction between propositional constants and propositional variables.

A propositional constant represents a specific proposition; a propositional variable represents an arbitrary proposition.

A propositional constant represents a specific proposition, so it has a definite truth value.

A propositional variable has no definite truth value; it is not a proposition. Its truth value is determined only when replaced by a specific proposition.

This substitution operation is called a truth assignment, valuation, or interpretation for the propositional variable.

A propositional formula (well-formed formula, WFF) is defined recursively as follows:

Propositional constants and propositional variables (such as $p, q, r, {\cdots}, T, F$) are propositional formulas;
If $A$ is a propositional formula, then (${\lnot}A$) is also a propositional formula;
If $A, B$ are propositional formulas, then $(A{\wedge}B)$, $(A{\vee}B)$, $(A{\rightarrow}B)$, and $(A{\leftrightarrow}B)$ are also propositional formulas;
Any string of symbols consisting of propositional constants, propositional variables, logical connectives, and parentheses obtained by finitely applying rules (1)-(3) is also a propositional formula.

When a propositional formula is complex, many parentheses are used. To reduce their use, the following conventions apply:

The precedence of connectives from high to low is: ${\lnot}{\wedge}{\vee}{\rightarrow}{\leftrightarrow}.$
For the same connective evaluated left to right, parentheses may be omitted.
The parentheses around (${\lnot}A$) and the outermost parentheses of any propositional formula may be omitted.
Symbols like $A, B$ introduced in definitions denote arbitrary propositional formulas, not specific ones.

Example: \[p{\wedge}q\] \[(p{\rightarrow}(q{\rightarrow}r)){\vee}r\] \[(p{\rightarrow}q{\rightarrow}r){\vee}r\] \[(p{\wedge}q{\wedge}r){\rightarrow}(p{\vee}(q{\wedge}s))\] is a propositional formula.

However, the following

\[(p{\wedge}q){\rightarrow}({\rightarrow}r){\wedge}r{\vee}p\] \[(p{\vee}q){\rightarrow}r)\] is not a propositional formula.

If $A_{1}$ is a part of propositional formula $A$, and $A_{1}$ itself is also a propositional formula, then $A_{1}$ is called a subformula of $A$.

For the propositional formula \[(p{\wedge}q){\rightarrow}(r{\vee}(q{\wedge}s))\],

\[p{\wedge}q, q{\wedge}s, r{\vee}(q{\wedge}s)\] are all its subformulas.

Symbolization of Propositions

Expressing a proposition described in natural language as a propositional formula is called symbolization of propositions.

Steps for symbolizing propositions:

Identify each atomic proposition in the proposition and symbolize it.
Identify each connective in the proposition and symbolize it.
Combine the symbolized atomic propositions and connectives.

Symbolize the following propositions:

Either Xiao Wang or Xiao Li is sent on a business trip.

Let $p$: Xiao Wang is sent on a business trip; $q$: Xiao Li is sent on a business trip. The proposition is symbolized as: $p{\vee}q$.

We cannot both row and jog.

Let $p$: We row; $q$: We jog. The proposition is symbolized as: ${\lnot}(p{\wedge}q)$.

If you come, then whether he sings depends on whether you accompany him.

Let $p$: You come; $q$: He sings; $r$: You accompany him. The proposition is symbolized as: $p{\rightarrow}(q{\leftrightarrow}r)$.

If it does not rain in the morning, I will go to the movies; otherwise I will stay home and read.

Let $p$: It rains in the morning; $q$: I go to the movies; $r$: I stay home and read. The proposition is symbolized as: $({\lnot}p{\rightarrow}q){\wedge}(p{\rightarrow}r)$.

In the formula $(p{\wedge}{\lnot}q){\rightarrow}{\lnot}r$:

Let $p$: Li Qiang is a sports enthusiast; $q$: Li Qiang is an arts enthusiast; $r$: Li Qiang is a sports-and-arts enthusiast,

then the formula $(p{\wedge}{\lnot}q){\rightarrow}{\lnot}r$ expresses:

If Li Ming is a sports enthusiast but not an arts enthusiast, then Li Ming is not a sports-and-arts enthusiast.

The following points should be noted when symbolizing propositions:

Determine whether the sentence is a proposition; if not, it cannot be symbolized.
Determine which logical connective corresponds to the connective in the sentence.
Correctly represent atomic propositions and choose logical connectives.
Symbolize propositions according to logical relationships, not literal translation.

Let $p$: Lin Fen does homework; $q$: Lin Fang does homework. Then “Lin Fen and Lin Fang are both doing homework” can be symbolized as $p{\wedge}q.$

However, “Lin Fen and Lin Fang are sisters” cannot be symbolized as $p{\wedge}q$; it is an atomic proposition.

Truth Tables

Let $A$ be a propositional formula and $p_{1}, p_{2}, {\cdots}, p_{n}$ all propositional variables appearing in $A$ (we may write $A(p_{1}, p_{2}, {\cdots}, p_{n})$ for a formula $A$ with $n$ propositional variables $p_{1}, p_{2}, {\cdots}, p_{n}$). Assigning a set of truth values to $p_{1}, p_{2}, {\cdots}, p_{n}$ is called a truth assignment, valuation, or interpretation of $A$.

\[ \begin{array}{ccccc} p_1 & p_2 & {\cdots} & p_n & A(p_{1}, p_{2}, {\cdots}, p_{n}) \\ 0&0&{\cdots}&0& v_1 \\ 0&0&{\cdots}&1& v_2 \\ {\vdots}&{\vdots}&{\cdots}&{\vdots}&{\vdots}\\ 1&1&{\cdots}&1&v_{2^n} \\ \end{array} \]

A propositional formula with $n$ variables has $2^{n}$ different interpretations, each corresponding to a definite truth value.

For a propositional formula $A$, the table listing all possible interpretations of $A$ together with the corresponding truth values of $A$ is called the truth table of $A$.

A truth table of a propositional formula consists of two parts:

The left part lists every interpretation of the propositional formula. For a formula with $n$ propositional variables, there are $2^{n}$ different interpretations.
The right part lists the truth value of the propositional formula corresponding to each interpretation.

Compute the truth table of the propositional formula $({\lnot}p{\wedge}q){\vee}p$.

Solution:

\[ \begin{array}{ccccc} p & q & {\lnot}p & {\lnot}p{\wedge}q & ({\lnot}p{\wedge}q){\vee}p \\ 0 & 0 & 1&0&0 \\ 0 & 1 & 1&1&1 \\ 1 & 0 & 0&0&1 \\ 1 & 1 & 0&0&1 \\ \end{array} \]

Compute the truth table of the propositional formula $(p{\rightarrow}q){\rightarrow}r$.

Solution:

\[ \begin{array}{ccccc} p & q & r & p{\rightarrow}q & (p{\rightarrow}q){\rightarrow}r \\ 0&0&0&1&0 \\ 0&0&1&1&1 \\ 0&1&0&1&0 \\ 0&1&1&1&1 \\ 1&0&0&0&1 \\ 1&0&1&0&1 \\ 1&1&0&1&0 \\ 1&1&1&1&1 \\ \end{array} \]

Given a propositional formula $A$. If every interpretation of $A$ makes $A$ true, then $A$ is called a tautology;

if every interpretation of $A$ makes $A$ false, then $A$ is called a contradiction;

if at least one interpretation makes $A$ true, then $A$ is called a satisfiable formula.

The problem of determining the type (tautology, contradiction, or satisfiable formula) of a given propositional formula is called the decision problem for propositional formulas.

Use a truth table to determine the type of the propositional formula $(p{\wedge}(p{\vee}q)){\leftrightarrow}{\lnot}p$.

Solution: \[ \begin{array}{ccccccc} p & q & p{\vee}q & p{\wedge}(p{\vee}q) & {\lnot}p & p{\wedge}(p{\vee}q){\leftrightarrow}{\lnot}p\\ 0 & 0 & 0&0&1&0 \\ 0 & 1 & 1&0&1&0 \\ 1 & 0 & 1&1&0&0 \\ 1 & 1 & 1&1&0&0 \\ \end{array} \]

It follows that $(p{\wedge}(p{\vee}q)){\rightarrow}{\lnot}p$ is a contradiction.

Use a truth table to determine the type of the propositional formula $p{\wedge}{\lnot}p$.

Solution:

\[ \begin{array}{ccc} p & {\lnot}p & p{\wedge}{\lnot}p\\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ \end{array} \]

It follows that $p{\wedge}{\lnot}p$ is a contradiction.

Use a truth table to determine the type of the propositional formula $p{\vee}{\lnot}p$.

Solution:

\[ \begin{array}{ccc} p & {\lnot}p & p{\vee}{\lnot}p\\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ \end{array} \]

It follows that $p{\vee}{\lnot}p$ is a tautology.

Use a truth table to determine the type of the propositional formula $(p{\rightarrow}q){\rightarrow}r$.

Solution: \[ \begin{array}{ccccc} p & q & r & p{\rightarrow}q & (p{\rightarrow}q){\rightarrow}r \\ 0&0&0&1&0 \\ 0&0&1&1&1 \\ 0&1&0&1&0 \\ 0&1&1&1&1 \\ 1&0&0&0&1 \\ 1&0&1&0&1 \\ 1&1&0&1&0 \\ 1&1&1&1&1 \\ \end{array} \]

It follows that $(p{\rightarrow}q){\rightarrow}r$ is a satisfiable formula.

Equivalences

Laws of Propositions

Let $A$ and $B$ be propositional formulas. If for every interpretation $A$ and $B$ always have the same truth value, then $A$ and $B$ are called logically equivalent (or equivalent), denoted $A{\Leftrightarrow}B$. $A{\Leftrightarrow}B$ is called an equivalence.

Distinction and connection between the symbols “${{\Leftrightarrow}}$” and “${{\leftrightarrow}}$”:

“${\Leftrightarrow}$” is not a connective; $A{\Leftrightarrow}B$ is not a formula but expresses the logical equivalence relation between two formulas.

“${\leftrightarrow}$” is a connective; $A{\leftrightarrow}B$ is a formula.

$A{\Leftrightarrow}B$ if and only if $A{\leftrightarrow}B$ is a tautology.

Whether two propositional formulas are equivalent can be determined by:

Truth tables: if the truth tables of $A$ and $B$ are identical, then $A$ and $B$ are equivalent;
Formula derivation method (equational calculus).

Prove: $p{\wedge}q{\Leftrightarrow}q{\wedge}p$.

Proof: Construct the truth table for $p{\wedge}q$ and $q{\wedge}p$ as follows:

\[ \begin{array}{cccc} p & q & p{\wedge}q & q{\wedge}p\\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ \end{array} \]

Since the truth tables of $p{\wedge}q$ and $q{\wedge}p$ are identical, the two propositional formulas are equivalent.

One can also prove this by showing $(p{\wedge}q){\leftrightarrow}(q{\wedge}p)$ is a tautology.

$p{\wedge}q{\Leftrightarrow}q{\wedge}p$. The truth table for $(p{\wedge}q){\leftrightarrow}(q{\wedge}p)$ is:

\[ \begin{array}{ccccc} p & q & p{\wedge}q & q{\wedge}p&(p{\wedge}q){\leftrightarrow}(q{\wedge}p) \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} \]

Since $(p{\wedge}q){\leftrightarrow}(q{\wedge}p)$ is a tautology, we have $p{\wedge}q{\Leftrightarrow}q{\wedge}p.$

Prove: $(p{\vee}q){\rightarrow}r{\Leftrightarrow}({\lnot}p{\vee}r){\wedge}({\lnot}q{\vee}r).$

Proof: Construct the truth tables for $(p{\vee}q){\rightarrow}r$ and $({\lnot}p{\vee}r){\wedge}({\lnot}q{\vee}r)$ as follows.

\[ \begin{array}{ccccc} p & q & r & (p{\vee}q){\rightarrow}r & ({\lnot}p{\vee}r){\wedge}({\lnot}q{\vee}r) \\ 0&0&0&1&1 \\ 0&0&1&1&1 \\ 0&1&0&0&0 \\ 0&1&1&1&1 \\ 1&0&0&0&0 \\ 1&0&1&1&1 \\ 1&1&0&0&0 \\ 1&1&1&1&1 \\ \end{array} \]

The two truth tables are identical, so the two propositional formulas are equivalent.

Properties of Equivalences

Reflexivity: For any propositional formula $A$, we have $A{\Leftrightarrow}A.$

Symmetry: For any propositional formulas $A$ and $B$, if $A{\Leftrightarrow}B$ then $B{\Leftrightarrow}A.$

Transitivity: For any propositional formulas $A$, $B$, and $C$, if $A{\Leftrightarrow}B$ and $B{\Leftrightarrow}C$, then $A{\Leftrightarrow}C$.

When determining whether formulas are equivalent, one can refer to some commonly used equivalences. These common equivalences are called laws of propositional logic.

Double Negation Law

\[{\lnot}{\lnot}A{\Leftrightarrow}A\]

Idempotent Laws

\[A{\vee}A{\Leftrightarrow}A\] \[A{\wedge}A{\Leftrightarrow}A\]

Associative Laws

\[(A{\vee}B){\vee}C{\Leftrightarrow}A{\vee}(B{\vee}C)\] \[(A{\wedge}B){\wedge}C{\Leftrightarrow}A{\wedge}(B{\wedge}C)\]

Commutative Laws

\[A{\vee}B{\Leftrightarrow}B{\vee}A\] \[A{\wedge}B{\Leftrightarrow}B{\wedge}A\]

Distributive Laws

\[A{\vee}(B{\wedge}C){\Leftrightarrow}(A{\vee}B){\wedge}(A{\vee}C)\] \[A{\wedge}(B{\vee}C){\Leftrightarrow}(A{\wedge}B){\vee}(A{\wedge}C)\]

Absorption Laws

\[A{\vee}(A{\wedge}B){\Leftrightarrow}A\] \[A{\wedge}(A{\vee}B){\Leftrightarrow}A\]

De Morgan’s Laws

\[{\lnot}(A{\wedge}B){\Leftrightarrow}{\lnot}A{\vee}{\lnot}B\] \[{\lnot}(A{\vee}B){\Leftrightarrow}{\lnot}A{\wedge}{\lnot}B\]

Identity Laws

\[A{\vee}F{\Leftrightarrow}A\] \[A{\wedge}T{\Leftrightarrow}A\]

Domination Laws

\[A{\vee}T{\Leftrightarrow}T\] \[A{\wedge}F{\Leftrightarrow}F\]

Negation Laws

\[A{\vee}{\lnot}A{\Leftrightarrow}T\] \[A{\wedge}{\lnot}A{\Leftrightarrow}F\]

Conditional Laws (Material Implication)

\[A{\rightarrow}B{\Leftrightarrow}{\lnot}A{\vee}B\] \[A{\rightarrow}B{\Leftrightarrow}{\lnot}B{\rightarrow}{\lnot}A\] \[{\lnot}(A{\rightarrow}B){\Leftrightarrow}A{\wedge}{\lnot}B\]

Reductio ad Absurdum

\[(A{\rightarrow}B){\wedge}(A{\rightarrow}{\lnot}B){\Leftrightarrow}{\lnot}A\]

Exportation/Importation Laws

\[(A{\wedge}B){\rightarrow}C{\Leftrightarrow}A{\rightarrow}(B{\rightarrow}C)\]

Biconditional Laws (Material Equivalence)

\[A{\leftrightarrow}B{\Leftrightarrow}(A{\rightarrow}B){\wedge}(B{\rightarrow}A)\] \[A{\leftrightarrow}B{\Leftrightarrow}(A{\wedge}B){\vee}({\lnot}A{\wedge}{\lnot}B)\] The 14 groups of equivalences above include 24 important equivalences in total.

Since $A$, $B$, $C$ can represent any propositional formula, these equivalences are called equivalence schemas.

Each basic equivalence can generate infinitely many equivalences of the same type.

Example: In the conditional law $A{\rightarrow}B{\Leftrightarrow}{\lnot}A{\vee}B$, taking $A=p, B=q$ gives the equivalence \[p{\rightarrow}q{\Leftrightarrow}{\lnot}p{\vee}q.\] Taking $A=p{\vee}q$, $B=r$ gives the equivalence \[(p{\vee}q){\rightarrow}r{\Leftrightarrow}{\lnot}(p{\vee}q){\vee}r.\]

All propositional laws can be proved using truth tables.

Prove De Morgan’s law: ${\lnot}(p{\wedge}q){\Leftrightarrow}{\lnot}p{\vee}{\lnot}q$.

Proof:

\[ \begin{array}{ccccccc} p & q & p{\wedge}q & {\lnot}p & {\lnot}q & {\lnot}(p{\wedge}q) & {\lnot}p{\vee}{\lnot}q\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ \end{array} \]

Since the truth tables of ${\lnot}(p{\wedge}q)$ and ${\lnot}p{\vee}{\lnot}q$ are identical, the two propositional formulas are equivalent.

Formula Derivation Method

Let $A(p_{1}, p_{2}, {\cdots}, p_{n})$ be a propositional formula, and $p_i$ a propositional variable in $A(p_{1}, p_{2}, {\cdots}, p_{n})$.

Replacing every occurrence of $p_i$ in $A$ with some propositional formula yields formula $B$. $B$ is called a substitution instance of $A$.

For the propositional formula: \[A(p, q)=(p{\vee}q){\rightarrow}q\]

replacing $q$ with $r{\wedge}s$ gives the substitution instance: \[B(p, r, s)=(p{\vee}(r{\wedge}s)){\rightarrow}(r{\wedge}s).\]

Theorem (Substitution Rule): Let propositional formula $A$ be a tautology. If $B$ is a substitution instance of $A$, then $B$ is also a tautology.

For the tautology: \[(p{\rightarrow}q){\leftrightarrow}({\lnot}q{\rightarrow}{\lnot}p)\]

replacing propositional variable $p$ with the formula $r{\wedge}s$ gives: \[((r{\wedge}s){\rightarrow}q){\leftrightarrow}({\lnot}q{\rightarrow}{\lnot}(r{\wedge}s))\] which is still a tautology.

Theorem (Replacement Rule): Let $A_{1}$ be a subformula of propositional formula $A$, and $B_{1}$ another propositional formula.

Replace $A_{1}$ in $A$ with $B_{1}$ to obtain formula $B$. If $A_{1}{\Leftrightarrow}B_{1}$, then $A{\Leftrightarrow}B$.

For the propositional formula: \[(p{\rightarrow}q){\wedge}r\]

replacing the formula $p{\rightarrow}q$ with ${\lnot}p{\vee}q$ gives \[({\lnot}p{\vee}q){\wedge}r.\] Because: \[(p{\rightarrow}q){\Leftrightarrow}({\lnot}p{\vee}q)\] Therefore: $(p{\rightarrow}q){\wedge}r{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}r.$

With the substitution rule and replacement rule, one can derive more complex equivalences from known ones.

This method of deriving complex equivalences using known equivalences, the substitution rule, and the replacement rule is called the formula derivation method (equational calculus).

Prove: $r{\rightarrow}(p{\rightarrow}q){\Leftrightarrow}r{\rightarrow}{\lnot}(p{\wedge}{\lnot}q).$

Proof: \[r{\rightarrow}(p{\rightarrow}q){\Leftrightarrow}r{\rightarrow}({\lnot}p{\vee}q)\] \[{\Leftrightarrow}r{\rightarrow}{\lnot}({\lnot}{\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}r{\rightarrow}{\lnot}(p{\wedge}{\lnot}q)\] Therefore $r{\rightarrow}(p{\rightarrow}q){\Leftrightarrow}r{\rightarrow}{\lnot}(p{\wedge}{\lnot}q)$.

Prove: $(p{\rightarrow}q){\wedge}(r{\rightarrow}q){\Leftrightarrow}(p{\vee}r){\rightarrow}q$.

Proof: \[(p{\rightarrow}q){\wedge}(r{\rightarrow}q)\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}({\lnot}r{\vee}q)\] \[{\Leftrightarrow}({\lnot}p{\wedge}{\lnot}r){\vee}q\] \[{\Leftrightarrow}{\lnot}(p{\vee}r){\vee}q\] \[{\Leftrightarrow}(p{\vee}r){\rightarrow}q\] Therefore $(p{\rightarrow}q){\wedge}(r{\rightarrow}q){\Leftrightarrow}(p{\vee}r){\rightarrow}q$.

Prove: $(p{\wedge}q){\vee}({\lnot}p{\vee}({\lnot}p{\vee}q)){\Leftrightarrow}{\lnot}p{\vee}q$.

Proof: \[(p{\wedge}q){\vee}({\lnot}p{\vee}({\lnot}p{\vee}q))\] \[{\Leftrightarrow}(p{\wedge}q){\vee}(({\lnot}p{\vee}{\lnot}p){\vee}q)\] \[{\Leftrightarrow}(p{\wedge}q){\vee}({\lnot}p{\vee}q)\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\vee}(p{\wedge}q)\] \[{\Leftrightarrow}{\lnot}p{\vee}(q{\vee}(p{\wedge}q))\] \[{\Leftrightarrow}{\lnot}p{\vee}q\]

Prove: $((p{\vee}q){\wedge}{\lnot}({\lnot}p{\wedge}({\lnot}q{\vee}{\lnot}r))){\vee}(({\lnot}p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}{\lnot}r)){\Leftrightarrow}T$.

Proof: \[((p{\vee}q){\wedge}{\lnot}({\lnot}p{\wedge}({\lnot}q{\vee}{\lnot}r))){\vee}(({\lnot}p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}{\lnot}r))\] \[{\Leftrightarrow}((p{\vee}q){\wedge}{\lnot}({\lnot}p{\wedge}({\lnot}q{\vee}{\lnot}r))){\vee}({\lnot}(p{\vee}q){\vee}{\lnot}(p{\vee}r))\] \[{\Leftrightarrow}((p{\vee}q){\wedge}(p{\vee}(q{\wedge}r))){\vee}({\lnot}(p{\vee}q){\vee}{\lnot}(p{\vee}r))\]

\[{\Leftrightarrow}((p{\vee}q){\wedge}((p{\vee}q){\wedge}(p{\vee}r))){\vee}({\lnot}(p{\vee}q){\vee}{\lnot}(p{\vee}r))\] \[{\Leftrightarrow}((p{\vee}q){\wedge}((p{\vee}q){\wedge}(p{\vee}r))){\vee}{\lnot}((p{\vee}q){\wedge}(p{\vee}r))\] \[{\Leftrightarrow}(((p{\vee}q){\wedge}(p{\vee}q)){\wedge}(p{\vee}r)){\vee}{\lnot}((p{\vee}q){\wedge}(p{\vee}r))\] \[{\Leftrightarrow}((p{\vee}q){\wedge}(p{\vee}r)){\vee}{\lnot}((p{\vee}q){\wedge}(p{\vee}r))\] \[{\Leftrightarrow}T\]

After an exam, an elementary school student told his father, mother, and aunt: “My scores in today’s math and Chinese exams both ranked in the top three in the class.” He asked the three of them to guess his exact rankings. Their guesses were as follows:

Father: Math 1st, Chinese 3rd;
Mother: Math 2nd, Chinese 3rd;
Aunt: Math 1st, Chinese 2nd.

After hearing the guesses, the student calmly said: “One of you is completely correct, and the other two each got one right.” Use the formula derivation method to determine the student’s rankings in the two subjects.

Solution: Let the propositions be

$p$: Math ranked 1st;
$q$: Math ranked 2nd;
$r$: Chinese ranked 2nd;
$s$: Chinese ranked 3rd.

Exactly two of $p, q, r, s$ are true and two are false. Let:

Father’s judgment: $A_{1}=p{\wedge}s$
Mother’s judgment: $A_{2}=q{\wedge}s$
Aunt’s judgment: $A_{3}=p{\wedge}r$

Father is completely correct: $B_{1}=p{\wedge}s$

Father got exactly one right: $B_{2}=(p{\wedge}{\lnot}s){\vee}({\lnot}p{\wedge}s)$

Mother is completely correct: $C_{1}=q{\wedge}s$

Mother got exactly one right: $C_{2}=(q{\wedge}{\lnot}s){\vee}({\lnot}q{\wedge}s)$

Aunt is completely correct: $D_{1}=p{\wedge}r$

Aunt got exactly one right: $D_{2}=(p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r)$

Thus,

\[Z=(B_{1}{\wedge}C_{2}{\wedge}D_{2}){\vee}(C_{1}{\wedge}B_{2}{\wedge}D_{2}){\vee}(D_{1}{\wedge}B_{2}{\wedge}C_{2})\] is a true proposition.

while: \[B_{1}{\wedge}C_{2}{\wedge}D_{2}\] \[{\Leftrightarrow}(p{\wedge}s){\wedge}((q{\wedge}{\lnot}s){\vee}({\lnot}q{\wedge}s)){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}((p{\wedge}s{\wedge}q{\wedge}{\lnot}s){\vee}(p{\wedge}s{\wedge}{\lnot}q{\wedge}s)){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}(F{\vee}(p{\wedge}{\lnot}q{\wedge}s)){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}(p{\wedge}{\lnot}q{\wedge}s){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}(p{\wedge}{\lnot}q{\wedge}s{\wedge}p{\wedge}{\lnot}r){\vee}(p{\wedge}{\lnot}q{\wedge}s{\wedge}{\lnot}p{\wedge}r)\] \[{\Leftrightarrow}(p{\wedge}{\lnot}q{\wedge}s{\wedge}{\lnot}r){\vee}F\] \[{\Leftrightarrow}p{\wedge}{\lnot}q{\wedge}s{\wedge}{\lnot}r\]

\[C_1{\wedge}B_2{\wedge}D_2\] \[{\Leftrightarrow}(q{\wedge}s){\wedge}((p{\wedge}{\lnot}s){\vee}({\lnot}p{\wedge}s)){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}((q{\wedge}s{\wedge}p{\wedge}{\lnot}s){\vee}(q{\wedge}s{\wedge}{\lnot}p{\wedge}s)){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}(F{\vee}(q{\wedge}s{\wedge}{\lnot}p)){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}(q{\wedge}s{\wedge}{\lnot}p){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\]

\[{\Leftrightarrow}(q{\wedge}s{\wedge}{\lnot}p{\wedge}p{\wedge}{\lnot}r){\vee}(q{\wedge}s{\wedge}{\lnot}p{\wedge}{\lnot}p{\wedge}r)\] \[{\Leftrightarrow}F{\vee}(q{\wedge}s{\wedge}{\lnot}p{\wedge}r)\] \[{\Leftrightarrow}q{\wedge}s{\wedge}{\lnot}p{\wedge}r\]

The Chinese ranking cannot be both 2nd and 3rd; therefore, exactly one of $r, s$ must be false, i.e.:

\[q{\wedge}s{\wedge}{\lnot}p{\wedge}r{\Leftrightarrow}F.\]

\[D_{1}{\wedge}B_{2}{\wedge}C_{2}\] \[{\Leftrightarrow}(p{\wedge}r){\wedge}((p{\wedge}{\lnot}s){\vee}({\lnot}p{\wedge}s)){\wedge}((q{\wedge}{\lnot}s){\vee}({\lnot}q{\wedge}s))\] \[{\Leftrightarrow}((p{\wedge}r{\wedge}p{\wedge}{\lnot}s){\vee}(p{\wedge}r{\wedge}{\lnot}p{\wedge}s)){\wedge}((q{\wedge}{\lnot}s){\vee}({\lnot}q{\wedge}s))\] \[{\Leftrightarrow}((p{\wedge}r{\wedge}{\lnot}s){\vee}F){\wedge}((q{\wedge}{\lnot}s){\vee}({\lnot}q{\wedge}s))\]

\[{\Leftrightarrow}(p{\wedge}r{\wedge}{\lnot}s){\wedge}((q{\wedge}{\lnot}s){\vee}({\lnot}q{\wedge}s))\] \[{\Leftrightarrow}(p{\wedge}r{\wedge}{\lnot}s{\wedge}q{\wedge}{\lnot}s){\vee}(p{\wedge}r{\wedge}{\lnot}s{\wedge}{\lnot}q{\wedge}s)\] \[{\Leftrightarrow}(p{\wedge}r{\wedge}{\lnot}s{\wedge}q){\vee}F\] \[{\Leftrightarrow}p{\wedge}r{\wedge}{\lnot}s{\wedge}q\]

The math ranking cannot be both 1st and 2nd, so exactly one of $p, q$ is false, i.e.,

\[p{\wedge}r{\wedge}{\lnot}s{\wedge}q{\Leftrightarrow}F.\]

Therefore \[Z=(B_{1}{\wedge}C_{2}{\wedge}D_{2}){\vee}(C_{1}{\wedge}B_{2}{\wedge}D_{2}){\vee}(D_{1}{\wedge}B_{2}{\wedge}C_{2})\] \[{\Leftrightarrow}(p{\wedge}{\lnot}q{\wedge}s{\wedge}{\lnot}r){\vee}F{\vee}F\] \[{\Leftrightarrow}p{\wedge}{\lnot}q{\wedge}s{\wedge}{\lnot}r\]

is a true proposition, i.e., the student ranked 1st in math and 3rd in Chinese.

Tautological Implications

Given propositional formula $A{\rightarrow}B$,

the formula $B{\rightarrow}A$ is called its converse.

The formula ${\lnot}A{\rightarrow}{\lnot}B$ is called its inverse.

The formula ${\lnot}B{\rightarrow}{\lnot}A$ is called its contrapositive.

These four propositional formulas have the following relationships: \[A{\rightarrow}B{\Leftrightarrow}{\lnot}B{\rightarrow}{\lnot}A, \]

\[B{\rightarrow}A{\Leftrightarrow}{\lnot}A{\rightarrow}{\lnot}B\]

Let $A, B$ be propositional formulas. If $A{\rightarrow}B$ is a tautology, i.e., $A{\rightarrow}B{\Leftrightarrow}T$, then $A{\rightarrow}B$ is called a tautological implication. We also say $A$ tautologically implies $B$, denoted $A{\Rightarrow}B.$

Distinction and connection between “${\Rightarrow}$” and “${\rightarrow}$”:

“${\Rightarrow}$” is not a connective; “$A{\Rightarrow}B$” is not a formula but expresses the tautological implication relation between $A$ and $B$.
“${\rightarrow}$” is a connective; $A{\rightarrow}B$ is a formula.
$A{\Rightarrow}B$ if and only if $A{\rightarrow}B$ is a tautology.

The following methods can be used to prove $A{\Rightarrow}B$:

Truth table method: show $A{\rightarrow}B$ is a tautology via a truth table.
Assume the antecedent is true and derive the consequent: Assume $A$ is true; if one can derive $B$ is $T$, then $A{\rightarrow}B$ is a tautology, i.e., $A{\Rightarrow}B$.
Assume the consequent is false and derive the antecedent is false: Assume $B$ is $F$; if one can derive $A$ is $F$, then $A{\rightarrow}B$ is a tautology, i.e., $A{\Rightarrow}B$.
Formula derivation method.

Prove: ${\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p$.

Proof: (Truth table method)

To prove ${\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p$, it suffices to show $({\lnot}q{\wedge}(p{\rightarrow}q)){\rightarrow}{\lnot}p$ is a tautology.

Compute the truth table of $({\lnot}q{\wedge}(p{\rightarrow}q)){\rightarrow}{\lnot}p$:

\[ \begin{array}{cccccc} p & q & {\lnot}q & p{\rightarrow}q & {\lnot}q{\wedge}(p{\rightarrow}q) & {\lnot}q{\wedge}(p{\rightarrow}q){\rightarrow}{\lnot}p \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ \end{array} \]

Since $({{\lnot}}q{{\wedge}}(p{{\rightarrow}}q)){{\rightarrow}}{{\lnot}}p$ is a tautology, we have ${{\lnot}}q{{\wedge}}(p{{\rightarrow}}q){{\Rightarrow}}{{\lnot}}p.$

(Antecedent-true method) \[({\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p)\]

Assume the antecedent ${\lnot}q{\wedge}(p{\rightarrow}q)$ is $T$; then ${\lnot}q$ and $p{\rightarrow}q$ are both $T$,

From the above, $q$ is $F$. Since $p{{\rightarrow}}q$ is $T$, $p$ must be $F$, so ${{\lnot}}p$ is $T$.

Therefore\[{\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p.\]

(Consequent-false method) \[({\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p)\]

Assume the consequent ${\lnot}p$ is $F$; then $p$ is $T$.

If $q$ is $T$, then ${{\lnot}}q$ is $F$, so ${{\lnot}}q{{\wedge}}(p{{\rightarrow}}q)$ is $F$; if $q$ is $F$, since $p$ is $T$, $p{\rightarrow}q$ is $F$.

Thus, ${{\lnot}}q{{\wedge}}(p{{\rightarrow}}q)$ is $F$. Therefore \[{{\lnot}}q{{\wedge}}(p{{\rightarrow}}q){{\Rightarrow}}{{\lnot}}p.\]

Prove: ${\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q$.

Proof: (Truth table method)

To prove ${\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q$, it suffices to show $({\lnot}p{\wedge}(p{\vee}q)){\rightarrow}q$ is a tautology.

Compute the truth table of $({\lnot}p{\wedge}(p{\vee}q)){\rightarrow}q$.

\[ \begin{array}{cccccc} p & q & {\lnot}p & p{\vee}q & {\lnot}p{\wedge}(p{\vee}q) & {\lnot}p{\wedge}(p{\vee}q){\rightarrow}q \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 \\ \end{array} \]

Since ${{\lnot}}p{{\wedge}}(p{{\vee}}q){{\rightarrow}}q$ is a tautology, we have ${{\lnot}}p{{\wedge}}(p{{\vee}}q){{\Rightarrow}}q.$

(Antecedent-true method) \[({\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q)\] Assume the antecedent ${\lnot}p{\wedge}(p{\vee}q)$ is $T$; then ${\lnot}p$ and $p{\vee}q$ are both $T$.

From the above, $p$ is $F$, so $q$ is $T$.

Therefore\[{\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q.\]

(Consequent-false method) \[({\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q)\] Assume the consequent $q$ is $F$.

If $p$ is $T$, then ${\lnot}p$ is $F$, so ${\lnot}p{\wedge}(p{\vee}q)$ is $F$;
if $p$ is $F$, then $p{\vee}q$ is $F$, so ${\lnot}p{\wedge}(p{\vee}q)$ is $F$.

Therefore \[{{\lnot}}p{{\wedge}}(p{{\vee}}q){{\Rightarrow}}q\]

Let $A$, $B$, $C$, and $D$ be propositional formulas. The following 9 groups of basic implications are given.

These implications can all be proved using the above methods. They can also be used via the formula derivation method to prove more complex implications.

Simplification

\[A{\wedge}B{\Rightarrow}A\] \[A{\wedge}B{\Rightarrow}B\]

Addition

\[A{\Rightarrow}A{\vee}B\] \[B{\Rightarrow}A{\vee}B\]

Modus Ponens

\[A{\wedge}(A{\rightarrow}B){\Rightarrow}B\]

Modus Tollens

\[{\lnot}B{\wedge}(A{\rightarrow}B){\Rightarrow}{\lnot}A\]

Disjunctive Syllogism

\[{\lnot}A{\wedge}(A{\vee}B){\Rightarrow}B\]

Hypothetical Syllogism

\[(A{\rightarrow}B){\wedge}(B{\rightarrow}C){\Rightarrow}(A{\rightarrow}C)\]

Biconditional Syllogism

\[(A{\leftrightarrow}B){\wedge}(B{\leftrightarrow}C){\Rightarrow}(A{\leftrightarrow}C)\]

Constructive Dilemma

\[(A{\rightarrow}B){\wedge}(C{\rightarrow}D){\wedge}(A{\wedge}C){\Rightarrow}B{\wedge}D\] \[(A{\rightarrow}B){\wedge}(C{\rightarrow}D){\wedge}(A{\vee}C){\Rightarrow}B{\vee}D\]

Disjunction Elimination

\[(A{\rightarrow}B){\wedge}(C{\rightarrow}B){\wedge}(A{\wedge}C){\Rightarrow}B\] \[(A{\rightarrow}B){\wedge}(C{\rightarrow}B){\wedge}(A{\vee}C){\Rightarrow}B\]

The 9 groups of basic implications above include 13 important implications. Since $A$, $B$, $C$, and $D$ can represent any propositional formula, these are called tautological implication schemas. Each basic implication can generate infinitely many implications of the same type.

In the Modus Ponens $A{\wedge}(A{\rightarrow}B){\Rightarrow}B$, taking $A=p, B=q$ gives $p{\wedge}(p{\rightarrow}q){\Rightarrow}q;$ taking $A=p{\rightarrow}q$, $B=r$ gives $(p{\rightarrow}q){\wedge}((p{\rightarrow}q){\rightarrow}r){\Rightarrow}r$.

Prove: ${\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p$.

Proof: (Method 1) \[{\lnot}q{\wedge}(p{\rightarrow}q)\] \[{\Leftrightarrow}{\lnot}q{\wedge}({\lnot}p{\vee}q)\] \[{\Leftrightarrow}({\lnot}q{\wedge}{\lnot}p){\vee}({\lnot}q{\wedge}q)\] \[{\Leftrightarrow}({\lnot}q{\wedge}{\lnot}p){\vee}F\] \[{\Leftrightarrow}{\lnot}q{\wedge}{\lnot}p\] \[{\Rightarrow}{\lnot}p\] Therefore \[{\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p.\]

(Method 2) For ${\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p$, it suffices to show $({\lnot}q{\wedge}(p{\rightarrow}q)){\rightarrow}{\lnot}p$ is a tautological implication.

\[({\lnot}q{\wedge}(p{\rightarrow}q)){\rightarrow}{\lnot}p\] \[{\Leftrightarrow}({\lnot}q{\wedge}({\lnot}p{\vee}q)){\rightarrow}{\lnot}p\] \[{\Leftrightarrow}(({\lnot}q{\wedge}{\lnot}p){\vee}({\lnot}q{\wedge}q)){\rightarrow}{\lnot}p\] \[{\Leftrightarrow}(({\lnot}q{\wedge}{\lnot}p){\vee}F){\rightarrow}{\lnot}p\] \[{\Leftrightarrow}({\lnot}q{\wedge}{\lnot}p){\rightarrow}{\lnot}p\] \[{\Leftrightarrow}{\lnot}({\lnot}q{\wedge}{\lnot}p){\vee}{\lnot}p\] \[{\Leftrightarrow}(q{\vee}p){\vee}{\lnot}p\] \[{\Leftrightarrow}T\] Therefore, ${\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p.$

Prove: ${\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q$.

Proof: \[{\lnot}p{\wedge}(p{\vee}q)\] \[{\Leftrightarrow}({\lnot}p{\wedge}p){\vee}({\lnot}p{\wedge}q)\] \[{\Leftrightarrow}F{\vee}({\lnot}p{\wedge}q)\] \[{\Leftrightarrow}{\lnot}p{\wedge}q\] \[{\Rightarrow}q\] Therefore, ${\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q$.

Prove: $p{{\wedge}}q{{\Rightarrow}}p{{\rightarrow}}q$.

Proof: \[p{\wedge}q\] \[{\Rightarrow}q\] \[{\Rightarrow}{\lnot}p{\vee}q\] \[{\Leftrightarrow}p{\rightarrow}q\] Therefore, $p{\wedge}q{\Rightarrow}p{\rightarrow}q$.

Theorem: Let $A$ and $B$ be propositional formulas. $A{\Leftrightarrow}B$ if and only if $A{\Rightarrow}B$ and $B{\Rightarrow}A.$

Proof:

(Necessity) Assume $A{\Leftrightarrow}B$; then $A{\leftrightarrow}B$ is a tautology.

Since $A{\leftrightarrow}B{\Leftrightarrow}(A{\rightarrow}B){\wedge}(B{\rightarrow}A)$, $A{\rightarrow}B$ is a tautology and $B{\rightarrow}A$ is a tautology, i.e., $A{\Rightarrow}B$ and $B{\Rightarrow}A$.

(Sufficiency) Assume $A{\Rightarrow}B$ and $B{\Rightarrow}A$; then $A{\rightarrow}B$ and $B{\rightarrow}A$ are both tautologies.

Since $A{{\leftrightarrow}}B{{\Leftrightarrow}}(A{{\rightarrow}}B){{\wedge}}(B{{\rightarrow}}A)$, $A{{\leftrightarrow}}B$ is a tautology, i.e., $A{{\Leftrightarrow}}B.$

Tautological implications have the following properties:

Let $A$, $B$ be any two propositional formulas. If $A{\Rightarrow}B$ and $A$ is a tautology, then $B$ is also a tautology.
Reflexivity. For any propositional formula $A$, $A{\Rightarrow}A$.
Transitivity. For any propositional formulas $A$, $B$, $C$: if $A{\Rightarrow}B$ and $B{\Rightarrow}C$, then $A{\Rightarrow}C$.
For any propositional formulas $A$, $B$, $C$: if $A{\Rightarrow}B$ and $A{\Rightarrow}C$, then $A{\Rightarrow}(B{\wedge}C)$.
For any propositional formulas $A$, $B$, $C$: if $A{\Rightarrow}C$ and $B{\Rightarrow}C$, then $(A{\vee}B){\Rightarrow}C$.

Complete Sets of Connectives

Although the connectives ${\lnot}$, ${\wedge}$, ${\vee}$, ${\rightarrow}$, and ${\leftrightarrow}$ can express any relationship between propositions and represent any propositional formula, they are sometimes not concise enough. To remedy this, four additional connectives are defined.

Exclusive Or Connective

Let $p$ and $q$ be propositions. The compound proposition “exactly one of $p$ or $q$ holds” is called the exclusive or (XOR) of $p$ and $q$, denoted $p{{\oplus}}q$ (or ${{\nleftrightarrow}}$). The symbol ${{\oplus}}$ is called the exclusive or connective (non-inclusive disjunction connective).

The truth value of $p{\oplus}q$ is given by the following table. $p{\oplus}q$ is true if and only if exactly one of $p$, $q$ is true.

\[ \begin{array}{ccc} p & q & p{\oplus}q \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} \]

Example:

He will go to the department store tomorrow or the day after tomorrow (but not both).

Let $p$: He goes to the department store tomorrow; $q$: He goes the day after tomorrow. Then (1) is symbolized as $p{\oplus}q$.

He is now either in Shanghai or in Hangzhou (but not both).

Let $p$: He is now in Shanghai; $q$: He is now in Hangzhou. Then (2) is symbolized as $p{\oplus}q$.

From the definition of the exclusive or connective: \[p{\oplus}q{\Leftrightarrow}{\lnot}(p{\leftrightarrow}q).\]

The exclusive or connective has the following properties:

$p{\oplus}q{\Leftrightarrow}q{\oplus}p$
$(p{\oplus}q){\oplus}r{\Leftrightarrow}p{\oplus}(q{\oplus}r)$
$p{\wedge}(q{\oplus}r){\Leftrightarrow}(p{\wedge}q){\oplus}(p{\wedge}r)$
$p{\oplus}q{\Leftrightarrow}(p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}q)$
$(p{\oplus}q){\Leftrightarrow}{\lnot}(p{\leftrightarrow}q)$

Conditional Negation Connective

Let $p$ and $q$ be propositions. The compound proposition “the negation of if $p$ then $q$” is called the conditional negation of $p$ and $q$, denoted $p{{\nrightarrow}}q$. The symbol ${{\nrightarrow}}$ is called the conditional negation connective.

The truth value of $p{\nrightarrow}q$ is given by the following table. $p{\nrightarrow}q$ is true if and only if $p$ is true and $q$ is false.

\[ \begin{array}{ccc} p & q & p{\nrightarrow}q \\ 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} \]

From the definition of the conditional negation connective: \[p{\nrightarrow}q{\Leftrightarrow}{\lnot}(p{\rightarrow}q).\]

NAND Connective

Let $p$ and $q$ be propositions. The compound proposition “negation of $p$ and $q$” is called the NAND of $p$ and $q$, denoted $p{{\uparrow}}q$. The symbol ${{\uparrow}}$ is called the NAND connective.

The truth value of $p{\uparrow}q$ is given by the following table. $p{\uparrow}q$ is true if and only if $p$ and $q$ are not both true.

\[ \begin{array}{ccc} p & q & p{\uparrow}q \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} \]

From the definition of the NAND connective: \[p{\uparrow}q{\Leftrightarrow}{\lnot}(p{\wedge}q).\]

The NAND connective has the following properties:

$p{\uparrow}p{\Leftrightarrow}{\lnot}(p{\wedge}p){\Leftrightarrow}{\lnot}p$
$p{\uparrow}q{\Leftrightarrow}q{\uparrow}p$
$(p{\uparrow}q){\uparrow}(p{\uparrow}q){\Leftrightarrow}{\lnot}(p{\uparrow}q){\Leftrightarrow}p{\wedge}q$
$(p{\uparrow}p){\uparrow}(q{\uparrow}q){\Leftrightarrow}{\lnot}p{\uparrow}{\lnot}q{\Leftrightarrow}p{\vee}q$

NOR Connective

Let $p$ and $q$ be propositions. The compound proposition “neither $p$ nor $q$” is called the NOR of $p$ and $q$, denoted $p{\downarrow}q$. The symbol ${\downarrow}$ is called the NOR connective.

The truth value of $p{\downarrow}q$ is given by the following table. $p{\downarrow}q$ is true if and only if both $p$ and $q$ are false.

\[ \begin{array}{ccc} p & q & p{\downarrow}q \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \\ \end{array} \]

From the definition of the NOR connective: \[p{\downarrow}q{\Leftrightarrow}{\lnot}(p{\vee}q).\]

The NOR connective has the following properties:

$p{\downarrow}p{\Leftrightarrow}{\lnot}(p{\vee}p){\Leftrightarrow}{\lnot}p$
$p{\downarrow}q{\Leftrightarrow}q{\downarrow}p$
$(p{\downarrow}q){\downarrow}(p{\downarrow}q){\Leftrightarrow}{\lnot}(p{\downarrow}q){\Leftrightarrow}p{\vee}q$
$(p{\downarrow}p){\downarrow}(q{\downarrow}q){\Leftrightarrow}{\lnot}p{\downarrow}{\lnot}q{\Leftrightarrow}p{\wedge}q$

At this point, nine connectives have been introduced.

Functionally Complete Sets of Connectives

Let $S$ be a set of connectives. If propositional formulas built from connectives in $S$ can express any propositional formula, then $S$ is called a functionally complete set of connectives.

Example: $\{{\lnot}$, ${{\wedge}}$, ${{\vee}}$, ${{\rightarrow}}$, ${{\leftrightarrow}}$, ${{\oplus}}$, ${{\uparrow}}$, ${{\downarrow}}$, ${{\nrightarrow}}\}$ is a functionally complete set of connectives.

To determine whether a set of connectives is functionally complete, one only needs to check whether the connectives in the set can replace all connectives in a known functionally complete set.

Prove: {${\lnot}$, ${\wedge}$, ${\vee}$, ${\rightarrow}$, ${\leftrightarrow}$} is a functionally complete set.

Proof: Since $\{{\lnot}$, ${{\wedge}}$, ${{\vee}}$, ${{\rightarrow}}$, ${{\leftrightarrow}}$, ${{\oplus}}$, ${{\uparrow}}$, ${{\downarrow}}$, ${{\nrightarrow}}\}$ is a functionally complete set of connectives, and: \[p{\oplus}q{\Leftrightarrow}{\lnot}(p{\leftrightarrow}q)\] \[p{\uparrow}q{\Leftrightarrow}{\lnot}(p{\wedge}q)\] \[p{\downarrow}q{\Leftrightarrow}{\lnot}(p{\vee}q)\] \[p{\nrightarrow}q{\Leftrightarrow}{\lnot}(p{\rightarrow}q)\] ${\oplus}, {\uparrow}, {\downarrow}$, and ${\nrightarrow}$ can be completely replaced by ${\lnot}, {\wedge}, {\vee}, {\rightarrow}$, and ${\leftrightarrow}$.

Therefore, {${\lnot}, {\wedge}, {\vee}, {\rightarrow}, {\leftrightarrow}$} is a functionally complete set.

$\{{\lnot}, {{\wedge}}, {{\vee}}\}$, $\{{\lnot}, {{\wedge}}\}$, ${{}},

Prove: $\{{\lnot}, {{\wedge}}, {{\vee}}\}$ is a functionally complete set of connectives.

Proof: Since $\{{\lnot}, {{\wedge}}, {{\vee}}, {{\rightarrow}}, {{\leftrightarrow}}\}$ is a functionally complete set of connectives, and: \[p{\rightarrow}q{\Leftrightarrow}{\lnot}p{\vee}q\] \[p{\leftrightarrow}q{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}(p{\vee}{\lnot}q)\] So ${{\rightarrow}}$ and ${{\leftrightarrow}}$ can each be replaced by ${{\lnot}}$, ${{\wedge}}$, and ${{\vee}}$.

Thus, $\{{\lnot}$, ${{\wedge}}$, ${{\vee}}\}$ is also a functionally complete set of connectives.

In a set of connectives, if one connective can be defined using other connectives in the set, it is called a redundant connective. Otherwise it is called an independent connective.

In the connective set $\{{\lnot}$, ${{\wedge}}$, ${{\vee}}\}$, ${{\vee}}$ is a redundant connective, because: \[p{\vee}q{\Leftrightarrow}{\lnot}({\lnot}p{\wedge}{\lnot}q).\]

Given a functionally complete set $S$, if $S$ contains no redundant connectives, then $S$ is called a minimal functionally complete set.

Prove: $\{{\lnot}, {{\vee}}\}$ is a minimal functionally complete set.

Proof: Since $\{{\lnot}, {{\wedge}}, {{\vee}}\}$ is a functionally complete set, and: \[p{\wedge}q{\Leftrightarrow}{\lnot}({\lnot}p{\vee}{\lnot}q)\] Therefore, $\{{\lnot}, {{\vee}}\}$ is a functionally complete set.

From the laws of propositions, a propositional formula containing a binary connective cannot be equivalently replaced by one containing only unary connectives. Since ${{\vee}}$ is binary and ${{\lnot}}$ is unary, they cannot replace each other. Therefore $\{{\lnot}, {{\vee}}\}$ is a minimal functionally complete set.

$\{{\lnot}, {{\wedge}}\}$, $\{{\lnot}, {{\rightarrow}}\}$, $\{{\uparrow}\}$, and $\{{\downarrow}\}$ are also all minimal functionally complete sets.

Prove: $\{{\uparrow}\}$ is a minimal functionally complete set.

Proof: Since $\{{\lnot}, {{\vee}}\}$ is a minimal functionally complete set, and: \[{\lnot}p{\Leftrightarrow}{\lnot}(p{\wedge}p){\Leftrightarrow}(p{\uparrow}p)\] \[p{\vee}q{\Leftrightarrow}{\lnot}({\lnot}p{\wedge}{\lnot}q){\Leftrightarrow}{\lnot}p{\uparrow}{\lnot}q{\Leftrightarrow}(p{\uparrow}p){\uparrow}(q{\uparrow}q)\] Therefore, $\{{\uparrow}\}$ is also a minimal functionally complete set.

\[{\lnot}p{\Leftrightarrow}{\lnot}(p{\wedge}p){\Leftrightarrow}p{\uparrow}p\] \[p{\wedge}q{\Leftrightarrow}{\lnot}(p{\uparrow}q){\Leftrightarrow}(p{\uparrow}q){\uparrow}(p{\uparrow}q)\] \[p{\vee}q{\Leftrightarrow}{\lnot}({\lnot}p{\wedge}{\lnot}q){\Leftrightarrow}({\lnot}p){\uparrow}({\lnot}q){\Leftrightarrow}(p{\uparrow}p){\uparrow}(q{\uparrow}q)\] \[p{\rightarrow}q{\Leftrightarrow}((p{\uparrow}p){\uparrow}(p{\uparrow}p)){\uparrow}(q{\uparrow}q)\] \[p{\leftrightarrow}q{\Leftrightarrow}((((p{\uparrow}p){\uparrow}(p{\uparrow}p)){\uparrow}(q{\uparrow}q))\] \[{\uparrow}(((q{\uparrow}q){\uparrow}(q{\uparrow}q)){\uparrow}(p{\uparrow}p))){\uparrow}\] \[((((p{\uparrow}p){\uparrow}(p{\uparrow}p)){\uparrow}(q{\uparrow}q))\] \[{\uparrow}(((q{\uparrow}q){\uparrow}(q{\uparrow}q)){\uparrow}(p{\uparrow}p)))\]

Express the propositional formula ${{\lnot}}p{{\vee}}(q{{\rightarrow}}r)$ using an equivalent formula that contains only the connectives ${{\lnot}}$ and ${{\wedge}}$.

Solution: \[{\lnot}p{\vee}(q{\rightarrow}r){\Leftrightarrow}{\lnot}p{\vee}({\lnot}q{\vee}r)\] \[{\Leftrightarrow}{\lnot}p{\vee}{\lnot}(q{\wedge}{\lnot}r)\] \[{\Leftrightarrow}{\lnot}(p{\wedge}(q{\wedge}{\lnot}r))\]

Dual Formulas

Given a propositional formula $A$ containing only connectives ${{\lnot}}$, ${{\wedge}}$, and ${{\vee}}$, replace ${{\vee}}$ with ${{\wedge}}$, ${{\wedge}}$ with ${{\vee}}$, the special constant $T$ with $F$, and $F$ with $T$. The resulting propositional formula $A^*$ is called the dual formula of $A$.

From the definition it is easy to see that $A$ is also the dual of $A^*$, i.e., duality is mutual: $(A^*)^*=A$.

Find the dual formulas of the following propositional formulas:

$p{\wedge}q$
${\lnot}(p{\vee}q){\wedge}T$

Solution:

The dual formula is $p{{\vee}}q$.
The dual formula is ${{\lnot}}(p{{\wedge}}q){{\vee}}F$.

If propositional formula $A$ contains, besides ${{\lnot}}, {{\wedge}}, {{\vee}}$, connectives such as ${{\rightarrow}}, {{\leftrightarrow}}, {{\uparrow}}, {{\downarrow}}$, first convert $A$ to a formula containing only ${{\lnot}}, {{\wedge}}, {{\vee}}$, then find its dual $A^*$.

Find the dual of the propositional formula $A=r{{\rightarrow}}(p{{\wedge}}(p{{\leftrightarrow}}q))$.

Solution: \[A{\Leftrightarrow}r{\rightarrow}(p{\wedge}(p{\rightarrow}q){\wedge}(q{\rightarrow}p))\] \[{\Leftrightarrow}r{\rightarrow}(p{\wedge}({\lnot}p{\vee}q){\wedge}({\lnot}q{\vee}p))\] \[{\Leftrightarrow}{\lnot}r{\vee}(p{\wedge}({\lnot}p{\vee}q){\wedge}({\lnot}q{\vee}p)\] Therefore\[A^*={\lnot}r{\wedge}(p{\vee}({\lnot}p{\wedge}q){\vee}({\lnot}q{\wedge}p).\]

Find the dual formulas of $p{{\uparrow}}q$ and $p{{\downarrow}}q$.

Solution: \[p{\uparrow}q{\Leftrightarrow}{\lnot}(p{\wedge}q)\]

Since the dual of ${{\lnot}}(p{{\wedge}}q)$ is ${{\lnot}}(p{{\vee}}q)$, the dual of $p{{\uparrow}}q$ is ${{\lnot}}(p{{\vee}}q)$.

Also \[{{\lnot}}(p{{\vee}}q){{\Leftrightarrow}}p{{\downarrow}}q\]

so the dual of $p{{\uparrow}}q$ is $p{{\downarrow}}q$,

that is, $p{{\downarrow}}q$ and $p{{\uparrow}}q$ are dual to each other.

Theorem: Let $A$ and $A^*$ be dual formulas, and $p_1, p_2, {{\cdots}}, p_n$ be all the propositional variables appearing in $A$ and $A^*$. Then:

${\lnot}A(p_{1}, p_{2}, {\cdots}, p_{n}){\Leftrightarrow}A^*({\lnot}p_{1}, {\lnot}p_{2}, {\cdots}, {\lnot}p_{n})$
$A({\lnot}p_{1}, {\lnot}p_{2}, {\cdots}, {\lnot}p_{n}){\Leftrightarrow}{\lnot}A^*(p_{1}, p_{2}, {\cdots}, p_{n})$

Let $A(p, q, r)={{\lnot}}p{{\vee}}({{\lnot}}q{{\wedge}}r)$. Prove: \[{{\lnot}}A(p, q, r){{\Leftrightarrow}}A^*({{\lnot}}p, {{\lnot}}q, {{\lnot}}r),\, \, \, \, \, \, \, A({{\lnot}}p, {{\lnot}}q, {{\lnot}}r){{\Leftrightarrow}}{{\lnot}}A^*(p, q, r).\]

Proof: \[A^*({\lnot}p, {\lnot}q, {\lnot}r)={\lnot}{\lnot}p{\wedge}({\lnot}{\lnot}q{\vee}{\lnot}r) \, {\Leftrightarrow}\, p{\wedge}(q{\vee}{\lnot}r)\] \[{\lnot}A(p, q, r)={\lnot}({\lnot}p{\vee}({\lnot}q{\wedge}r))\, {\Leftrightarrow}\, {\lnot}{\lnot}p{\wedge}{\lnot}({\lnot}q{\wedge}r)\, {\Leftrightarrow}\, p{\wedge}(q{\vee}{\lnot}r)\] Therefore, ${\lnot}A(p, q, r){\Leftrightarrow}A^*({\lnot}p, {\lnot}q, {\lnot}r)$.

Similarly, \[A({\lnot}p, {\lnot}q, {\lnot}r)={\lnot}{\lnot}p{\vee}({\lnot}{\lnot}q{\wedge}{\lnot}r)\, {\Leftrightarrow}\, p{\vee}(q{\wedge}{\lnot}r)\] \[{\lnot}A^*(p, q, r)={\lnot}({\lnot}p{\wedge}({\lnot}q{\vee}r))\, {\Leftrightarrow}\, p{\vee}(q{\wedge}{\lnot}r)\] Therefore, $A({\lnot}p, {\lnot}q, {\lnot}r){\Leftrightarrow}{\lnot}A^*(p, q, r).$

Theorem (Duality Principle): Let $p_1, p_2, {{\cdots}}, p_n$ be all the propositional variables in formulas $A$ and $B$. If $A{{\Leftrightarrow}}B$, then $A^*{{\Leftrightarrow}}B^*$.

From the duality principle:

If $A$ is a tautology, then $A^*$ is a contradiction;
For propositional formulas $A$ and $B$, if $A{{\Rightarrow}}B$, then $B^*{{\Rightarrow}}A^*$;
Given $A{{\Leftrightarrow}}B$ where $B$ is simpler than $A$, by the duality principle one can directly obtain $B^*$ (which is equivalent to $A^*$).

Let $A=p{{\vee}}({{\lnot}}p{{\vee}}(q{{\wedge}}{{\lnot}}q))$, then $A^*=p{{\wedge}}({{\lnot}}p{{\wedge}}(q{{\vee}}{{\lnot}}q))$

Because \[A{{\Leftrightarrow}}p{{\vee}}({{\lnot}}p{{\vee}}F){{\Leftrightarrow}}p{{\vee}}{{\lnot}}p{{\Leftrightarrow}}T\]

Therefore\[A^*{\Leftrightarrow}F\]

(In fact, $A^*=p{{\wedge}}({{\lnot}}p{{\wedge}}T){{\Leftrightarrow}}p{{\wedge}}{{\lnot}}p{{\Leftrightarrow}}F$)

Let $A=p{{\wedge}}q$, $B=p$, then $A^*=p{{\vee}}q, B^*=p$.

Because \[p{{\wedge}}q{{\Rightarrow}}p\, (A{{\Rightarrow}}B)\] \[p{\Rightarrow}p{\vee}q\, (B^*{\Rightarrow}A^*)\]

Thus: \[A{{\Rightarrow}}B, \, \, \, \, B^*{{\Rightarrow}}A^*\]

Prove:

$(p{\wedge}q){\vee}({\lnot}p{\vee}q){\Leftrightarrow}{\lnot}p{\vee}q$
$(p{\vee}q){\wedge}({\lnot}p{\wedge}q){\Leftrightarrow}{\lnot}p{\wedge}q$

Proof: (1)

\[(p{\wedge}q){\vee}({\lnot}p{\vee}q){\Leftrightarrow}(p{\vee}({\lnot}p{\vee}q)){\wedge}(q{\vee}({\lnot}p{\vee}q))\] \[{\Leftrightarrow}(p{\vee}{\lnot}p{\vee}q){\wedge}(q{\vee}{\lnot}p{\vee}q){\Leftrightarrow}T{\wedge}({\lnot}p{\vee}q){\Leftrightarrow}{\lnot}p{\vee}q\]

The dual of $(p{{\wedge}}q){{\vee}}({{\lnot}}p{{\vee}}q)$ is $(p{{\vee}}q){{\wedge}}({{\lnot}}p{{\wedge}}q)$, the dual of ${{\lnot}}p{{\vee}}q$ is ${{\lnot}}p{{\wedge}}q.$

From (1): $(p{\wedge}q){\vee}({\lnot}p{\vee}q){\Leftrightarrow}{\lnot}p{\vee}q$, we can prove (2): $(p{{\vee}}q){{\wedge}}({{\lnot}}p{{\wedge}}q){{\Leftrightarrow}}{{\lnot}}p{{\wedge}}q$.

Normal Forms

Definition: An conjunction of finitely many propositional variables or their negations is called a simple conjunction (elementary product); each propositional variable or its negation is called a conjunct.

Example: $p$, ${{\lnot}}p$, $q$, ${{\lnot}}q$, $p{{\wedge}}q$, $p{{\wedge}}{{\lnot}}q$, ${{\lnot}}p{{\wedge}}q$, ${{\lnot}}p{{\wedge}}{{\lnot}}q$, $p{{\wedge}}q{{\wedge}}r$, $p{{\wedge}}q{{\wedge}}{{\lnot}}r$ etc. are all elementary products.

Definition: A disjunction of finitely many propositional variables or their negations is called a simple disjunction (elementary sum); each propositional variable or its negation is called a disjunct.

Example: $p$, ${{\lnot}}p$, $q$, ${{\lnot}}q$, $p{{\vee}}q$, $p{{\vee}}{{\lnot}}q$, ${{\lnot}}p{{\vee}}q$, ${{\lnot}}p{{\vee}}{{\lnot}}q$, $p{{\vee}}q{{\vee}}r$, $p{{\vee}}q{{\vee}}{{\lnot}}r$ etc. are all elementary sums.

Note: A single propositional variable or its negation can be regarded as either an elementary product or an elementary sum.

Example: $p$, ${{\lnot}}p$, $q$, ${{\lnot}}q$ are elementary products and also elementary sums.

Theorem: A necessary and sufficient condition for an elementary product to be a contradiction is that it contains some propositional variable together with its negation.

Example: The elementary product $p{{\wedge}}q{{\wedge}}{{\lnot}}q$ is a contradiction, because it contains propositional variable $q$ and its negation ${{\lnot}}q$.

Theorem: A necessary and sufficient condition for an elementary sum to be a tautology is that it contains some propositional variable together with its negation.

Example: The elementary sum $p{{\vee}}q{{\vee}}{{\lnot}}p$ is a tautology, because it contains propositional variable $p$ and its negation ${{\lnot}}p$.

Definition: A propositional formula consisting of a disjunction of elementary products is called a disjunctive normal form (DNF), i.e., it has the form: \[A_{1}{\vee}A_{2}{\vee}{\cdots}{\vee}A_n\] where $A_1, A_2, {{\cdots}}, A_n$ are all elementary products.

Example: The propositional formula ${{\lnot}}p{{\vee}}(p{{\wedge}}q){{\vee}}(p{{\wedge}}{{\lnot}}q{{\wedge}}r)$ is a DNF.

Definition: A propositional formula consisting of a conjunction of elementary sums is called a conjunctive normal form (CNF), i.e., it has the form: \[B_{1}{\wedge}B_{2}{\wedge}{\cdots}{\wedge}B_n\] where $B_1, B_2, {{\cdots}}, B_n$ are all elementary sums.

Example: The propositional formula $q{{\wedge}}(p{{\vee}}q){{\wedge}}({{\lnot}}q{{\vee}}r)$ is a CNF.

The dual of any DNF is a CNF; the dual of any CNF is a DNF.

Theorem (Normal Form Existence Theorem): Every propositional formula has an equivalent DNF and an equivalent CNF.

The steps to find the DNF and CNF of a propositional formula are:

Eliminate all connectives outside $\{{\lnot}, {{\wedge}}, {{\vee}}\}$;
Use De Morgan’s laws to move the negation connective ${{\lnot}}$ inward to immediately precede propositional variables, and eliminate double negations;
Use distribution laws to convert to DNF or CNF.

The DNF and CNF of a propositional formula are not necessarily unique.

Find the CNF and DNF of the following propositional formula: \[((p{\vee}q){\rightarrow}r){\rightarrow}p\]

Solution: (1) Find the CNF \[((p{\vee}q){\rightarrow}r){\rightarrow}p\] \[{\Leftrightarrow}({\lnot}(p{\vee}q){\vee}r){\rightarrow}p\] \[{\Leftrightarrow}{\lnot}({\lnot}(p{\vee}q){\vee}r){\vee}p\] \[{\Leftrightarrow}((p{\vee}q){\wedge}{\lnot}r){\vee}p\] \[{\Leftrightarrow}(p{\vee}q{\vee}p){\wedge}({\lnot}r{\vee}p)\] \[{\Leftrightarrow}(p{\vee}q){\wedge}({\lnot}r{\vee}p)\]

Find the DNF

\[((p{\vee}q){\rightarrow}r){\rightarrow}p\] \[{\Leftrightarrow}({\lnot}(p{\vee}q){\vee}r){\rightarrow}p\] \[{\Leftrightarrow}{\lnot}({\lnot}(p{\vee}q){\vee}r){\vee}p\] \[{\Leftrightarrow}((p{\vee}q){\wedge}{\lnot}r){\vee}p\] \[{\Leftrightarrow}(p{\wedge}{\lnot}r){\vee}(q{\wedge}{\lnot}r){\vee}p\] \[{\Leftrightarrow}p{\vee}(q{\wedge}{\lnot}r)\]

One can also find the DNF from the CNF, or vice versa.

\[((p{\vee}q){\rightarrow}r){\rightarrow}p\] \[{\Leftrightarrow}(p{\vee}q){\wedge}({\lnot}r{\vee}p)\] \[{\Leftrightarrow}(p{\wedge}{\lnot}r){\vee}(p{\wedge}p){\vee}(q{\wedge}{\lnot}r){\vee}(q{\wedge}p)\] \[{\Leftrightarrow}(p{\wedge}{\lnot}r){\vee}p{\vee}(q{\wedge}{\lnot}r){\vee}(q{\wedge}p)\] \[{\Leftrightarrow}p{\vee}(q{\wedge}{\lnot}r){\vee}(q{\wedge}p)\] \[{\Leftrightarrow}p{\vee}(q{\wedge}{\lnot}r)\]

DNF and CNF can be used to determine the type of a propositional formula.

A DNF is a contradiction if and only if each of its elementary products is a contradiction; $(A_1{{\vee}}A_2{{\vee}}{{\cdots}}{{\vee}}A_n$, $A_i$ is a contradiction)
A CNF is a tautology if and only if each of its elementary sums is a tautology; $(B_1{{\wedge}}B_2{{\wedge}}{{\cdots}}{{\wedge}}B_n$, $B_i$ is a tautology)
A propositional formula is a contradiction if and only if every elementary product in its DNF contains at least one propositional variable together with its negation;
A propositional formula is a tautology if and only if every elementary sum in its CNF contains at least one propositional variable together with its negation.

Determine the type of the following propositional formula using normal forms:

\[p{\wedge}({\lnot}p{\vee}q){\wedge}({\lnot}p{\vee}{\lnot}q).\] Solution: \[p{\wedge}({\lnot}p{\vee}q){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}((p{\wedge}{\lnot}p){\vee}(p{\wedge}q)){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}(F{\vee}(p{\wedge}q)){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}(p{\wedge}q){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}(p{\wedge}q{\wedge}{\lnot}p){\vee}(p{\wedge}q{\wedge}{\lnot}q)\] Since the first elementary product contains both $p$ and ${{\lnot}}p$, and the second contains both $q$ and ${{\lnot}}q$.

Therefore the propositional formula is a contradiction.

Determine the type of the following propositional formula using normal forms: \[p{\rightarrow}(q{\rightarrow}(p{\wedge}q))\]

Solution: \[p{\rightarrow}(q{\rightarrow}(p{\wedge}q))\] \[{\Leftrightarrow}{\lnot}p{\vee}({\lnot}q{\vee}(p{\wedge}q))\] \[{\Leftrightarrow}{\lnot}p{\vee}(({\lnot}q{\vee}p){\wedge}({\lnot}q{\vee}q))\] \[{\Leftrightarrow}({\lnot}p{\vee}{\lnot}q{\vee}p){\wedge}({\lnot}p{\vee}{\lnot}q{\vee}q)\] Since the first elementary sum contains both $p$ and ${{\lnot}}p$, and the second contains both $q$ and ${{\lnot}}q$.

Therefore, this propositional formula is a tautology.

Determine the type of the following propositional formula using normal forms:

\[(p{\vee}q){\rightarrow}(p{\wedge}q)\] Solution: \[(p{\vee}q){\rightarrow}(p{\wedge}q)\] \[{\Leftrightarrow}{\lnot}(p{\vee}q){\vee}(p{\wedge}q)\] \[{\Leftrightarrow}({\lnot}p{\wedge}{\lnot}q){\vee}(p{\wedge}q)\] \[{\Leftrightarrow}(p{\vee}{\lnot}q){\wedge}({\lnot}p{\vee}q)\] From the DNF and CNF of this propositional formula: it is neither a tautology nor a contradiction, so it is a satisfiable formula.

Determine whether the following formula is a tautology: \[q{\vee}(p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}{\lnot}q).\] Solution: Convert to CNF \[q{\vee}(p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}((q{\vee}p){\wedge}(q{\vee}{\lnot}q)){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}((q{\vee}p){\wedge}T){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}(q{\vee}p){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}(q{\vee}p{\vee}{\lnot}p){\wedge}(q{\vee}p{\vee}{\lnot}q)\] Therefore, this propositional formula is a tautology.

Principal Disjunctive Normal Form and Principal Conjunctive Normal Form

In an elementary product containing $n$ propositional variables, if each variable and its negation do not both appear, but exactly one of them must appear exactly once, then such an elementary product is called a minterm.

The minterms formed by two propositional variables are: \[p{\wedge}q, p{\wedge}{\lnot}q, {\lnot}p{\wedge}q, {\lnot}p{\wedge}{\lnot}q\] The minterms formed by three propositional variables are: \[p{\wedge}q{\wedge}r, p{\wedge}q{\wedge}{\lnot}r, p{\wedge}{\lnot}q{\wedge}r, p{\wedge}{\lnot}q{\wedge}{\lnot}r, {\lnot}p{\wedge}q{\wedge}r, {\lnot}p{\wedge}q{\wedge}{\lnot}r, \] \[{\lnot}p{\wedge}{\lnot}q{\wedge}r, {\lnot}p{\wedge}{\lnot}q{\wedge}{\lnot}r\] In general, $n$ propositional variables produce $2^n$ distinct minterms, denoted $m_0, m_1, \cdots, m_{2^n-1}$, where $m_i$ denotes the $i$-th minterm.

Definition: In an elementary sum containing $n$ propositional variables, if each variable and its negation do not both appear, but exactly one of them must appear exactly once, then such an elementary sum is called a maxterm.

The maxterms formed by two propositional variables are: \[p{\vee}q, p{\vee}{\lnot}q, {\lnot}p{\vee}q, {\lnot}p{\vee}{\lnot}q\] The maxterms formed by three propositional variables are: \[p{\vee}q{\vee}r, p{\vee}q{\vee}{\lnot}r, p{\vee}{\lnot}q{\vee}r, p{\vee}{\lnot}q{\vee}{\lnot}r, {\lnot}p{\vee}q{\vee}r, {\lnot}p{\vee}q{\vee}{\lnot}r, \] \[{\lnot}p{\vee}{\lnot}q{\vee}r, {\lnot}p{\vee}{\lnot}q{\vee}{\lnot}r\] In general, $n$ propositional variables produce $2^n$ distinct maxterms, denoted $M_0, M_1, \cdots, M_{2^n-1}$, where $M_i$ denotes the $i$-th maxterm.

For a propositional formula containing $n$ propositional variables, if every elementary product in its DNF is a minterm of those $n$ variables, then the DNF is called the principal disjunctive normal form (PDNF) of the formula.

Basic form: \[A_{1}{\vee}A_{2}{\vee}{\cdots}{\vee}A_n\] For a propositional formula containing $n$ propositional variables, if every elementary sum in its CNF is a maxterm of those $n$ variables, then the CNF is called the principal conjunctive normal form (PCNF) of the formula.

Basic form: \[B_{1}{\wedge}B_{2}{\wedge}{\cdots}{\wedge}B_n\]

Theorem (Uniqueness of PDNF): Every propositional formula that is not a contradiction has an equivalent PDNF, and it is unique.

Theorem (Uniqueness of PCNF): Every propositional formula that is not a tautology has an equivalent PCNF, and it is unique.

Two methods can be used to find the principal normal form:

Truth table method
Formula derivation method (equational calculus)

The principal normal form of a propositional formula can be obtained by constructing its truth table.

In the truth table, the disjunction of minterms corresponding to interpretations where the formula is $T$ gives the PDNF.

In the truth table, the conjunction of maxterms corresponding to interpretations where the formula is $F$ gives the PCNF.

Example: Find the PDNF of $p{{\rightarrow}}q$.

Solution: The PDNF of $p{{\rightarrow}}q$ is the disjunction of some of the four minterms $p{{\wedge}}q$, $p{{\wedge}}{{\lnot}}q$, ${{\lnot}}p{{\wedge}}q$, ${{\lnot}}p{{\wedge}}{{\lnot}}q$.

The truth table of the propositional formula and the two-variable minterms is as follows:

\[ \begin{array}{ccccccc} p & q & p{\rightarrow}q & {\lnot}p{\wedge}{\lnot}q & {\lnot}p{\wedge}q & p{\wedge}{\lnot}q & p{\wedge}q\\ 0 & 0 & 1&1&0&0&0 \\ 0 & 1 & 1&0&1&0&0 \\ 1 & 0 & 0&0&0&1&0 \\ 1 & 1 & 1&0&0&0&1 \\ \end{array} \]

Therefore, the PDNF of $p{{\rightarrow}}q$ is:

\[p{\rightarrow}q{\leftrightarrow}({\lnot}p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}q){\vee}(p{\wedge}q).\]

Find the PCNF of ${{\lnot}}p{{\wedge}}{{\lnot}}q$.

Solution: The PCNF of ${{\lnot}}p{{\wedge}}{{\lnot}}q$ is the conjunction of some of the four maxterms $p{{\vee}}q, p{{\vee}}{{\lnot}}q, {{\lnot}}p{{\vee}}q, {{\lnot}}p{{\vee}}{{\lnot}}q$.

\[ \begin{array}{ccccccc} p & q & {\lnot}p{\wedge}{\lnot}q & p{\vee}q & p{\vee}{\lnot}q & {\lnot}p{\vee}q & {\lnot}p{\vee}{\lnot}q\\ 0 & 0 & 1&0&1&1&1 \\ 0 & 1 & 0&1&0&1&1 \\ 1 & 0 & 0&1&1&0&1 \\ 1 & 1 & 0&1&1&1&0 \\ \end{array} \]

Therefore, the PCNF of ${{\lnot}}p{{\wedge}}{{\lnot}}q$: \[{\lnot}p{\wedge}{\lnot}q{\Leftrightarrow}(p{\vee}{\lnot}q){\wedge}({\lnot}p{\vee}q){\wedge}({\lnot}p{\vee}{\lnot}q).\]

Find the principal normal forms (PDNF and PCNF) of $p{{\rightarrow}}{{\lnot}}q$.

Solution:

\[ \begin{array}{ccccccc} p & q & p{\rightarrow}{\lnot}q & {\lnot}p{\wedge}{\lnot}q & {\lnot}p{\wedge}q & p{\wedge}{\lnot}q & p{\wedge}q\\ 0 & 0 & 1&1&0&0&0 \\ 0 & 1 & 1&0&1&0&0 \\ 1 & 0 & 1&0&0&1&0 \\ 1 & 1 & 0&0&0&0&1 \\ \end{array} \]

Therefore, the PDNF of $p{{\rightarrow}}{{\lnot}}q$ is $p{\rightarrow}{\lnot}q{\Leftrightarrow}({\lnot}p{\wedge}{\lnot}q)$ ${\vee}({\lnot}p{\wedge}q){\vee}(p{\wedge}{\lnot}q).$

Next, find the PCNF of $p{{\rightarrow}}{{\lnot}}q$.

\[ \begin{array}{ccccccc} p & q & p{\rightarrow}{\lnot}q & p{\vee}q & p{\vee}{\lnot}q & {\lnot}p{\vee}q & {\lnot}p{\vee}{\lnot}q\\ 0 & 0 & 1&0&1&1&1 \\ 0 & 1 & 1&1&0&1&1 \\ 1 & 0 & 1&1&1&0&1 \\ 1 & 1 & 0&1&1&1&0 \\ \end{array} \]

Therefore, the PCNF of $p{{\rightarrow}}{{\lnot}}q$ is \[p{\rightarrow}{\lnot}q{\Leftrightarrow}({\lnot}p{\vee}{\lnot}q).\]

The formula derivation method (equational calculus) can be used to construct the PDNF, with the following steps:

Convert the propositional formula to a DNF.
Remove all contradictory elementary products from the DNF.
Use the idempotent law to merge repeated elementary products and repeated variables within elementary products.
Use the identity law to add missing propositional variables to each elementary product (e.g., $p{{\vee}}{{\lnot}}p$), then apply the distribution law to expand.
Use the idempotent law again to merge repeated minterms.

Find the PDNF of ${{\lnot}}p{{\vee}}{{\lnot}}q$.

Solution: \[{\lnot}p{\vee}{\lnot}q\] \[{\Leftrightarrow}({\lnot}p{\wedge}(q{\vee}{\lnot}q)){\vee}((p{\vee}{\lnot}p){\wedge}{\lnot}q)\] \[{\Leftrightarrow}({\lnot}p{\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q){\vee}(p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}({\lnot}p{\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q){\vee}(p{\wedge}{\lnot}q)\]

Find the PDNF of $p{{\rightarrow}}((p{{\rightarrow}}q){{\wedge}}{{\lnot}}({{\lnot}}q{{\vee}}{{\lnot}}p))$.

Solution: \[p{\rightarrow}((p{\rightarrow}q){\wedge}{\lnot}({\lnot}q{\vee}{\lnot}p))\] \[{\Leftrightarrow}{\lnot}p{\vee}(({\lnot}p{\vee}q){\wedge}(q{\wedge}p))\] \[{\Leftrightarrow}{\lnot}p{\vee}(({\lnot}p{\wedge}q{\wedge}p){\vee}(q{\wedge}q{\wedge}p))\] \[{\Leftrightarrow}{\lnot}p{\vee}F{\vee}(q{\wedge}p)\] \[{\Leftrightarrow}{\lnot}p{\vee}(q{\wedge}p)\] \[{\Leftrightarrow}({\lnot}p{\wedge}(q{\vee}{\lnot}q)){\vee}(p{\wedge}q)\] \[{\Leftrightarrow}({\lnot}p{\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q){\vee}(p{\wedge}q)\]

Similarly, the formula derivation method can be used to construct the PCNF.

Convert the propositional formula to a CNF.
Remove all tautological elementary sums from the CNF.
Use the idempotent law to merge repeated elementary sums and repeated variables within elementary sums.
Use the identity law to add missing propositional variables to each elementary sum (e.g., $p{{\wedge}}{{\lnot}}p$), then apply the distribution law to expand.
Use the idempotent law again to merge repeated maxterms.

Find the PCNF of ${{\lnot}}p{{\wedge}}{{\lnot}}q$.

Solution: \[{\lnot}p{\wedge}{\lnot}q\] \[{\Leftrightarrow}({\lnot}p{\vee}(q{\wedge}{\lnot}q)){\wedge}((p{\wedge}{\lnot}p){\vee}{\lnot}q)\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}({\lnot}p{\vee}{\lnot}q){\wedge}(p{\vee}{\lnot}q){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}({\lnot}p{\vee}{\lnot}q){\wedge}(p{\vee}{\lnot}q)\]

Find the PCNF of $p{{\rightarrow}}((p{{\rightarrow}}q){{\wedge}}{{\lnot}}({{\lnot}}q{{\vee}}{{\lnot}}p))$.

Solution: \[p{\rightarrow}((p{\rightarrow}q){\wedge}{\lnot}({\lnot}q{\vee}{\lnot}p))\] \[{\Leftrightarrow}{\lnot}p{\vee}(({\lnot}p{\vee}q){\wedge}(q{\wedge}p))\] \[{\Leftrightarrow}{\lnot}p{\vee}(({\lnot}p{\wedge}q{\wedge}p){\vee}(q{\wedge}q{\wedge}p))\] \[{\Leftrightarrow}{\lnot}p{\vee}F{\vee}(q{\wedge}p)\] \[{\Leftrightarrow}{\lnot}p{\vee}(q{\wedge}p)\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}({\lnot}p{\vee}p)\] \[{\Leftrightarrow}{\lnot}p{\vee}q\]

Find the principal normal forms of $(p{{\wedge}}q){{\vee}}(p{{\wedge}}r)$.

Solution: \[(p{\wedge}q){\vee}(p{\wedge}r){\Leftrightarrow}p{\wedge}(q{\vee}r)\] \[{\Leftrightarrow}(p{\vee}(q{\wedge}{\lnot}q){\vee}(r{\wedge}{\lnot}r)){\wedge}((p{\wedge}{\lnot}p){\vee}q{\vee}r)\] \[{\Leftrightarrow}(p{\vee}q{\vee}r){\wedge}(p{\vee}q{\vee}{\lnot}r){\wedge}(p{\vee}{\lnot}q{\vee}r){\wedge}(p{\vee}{\lnot}q{\vee}{\lnot}r){\wedge}(p{\vee}q{\vee}r){\wedge}({\lnot}p{\vee}q{\vee}r)\]

\[{\Leftrightarrow}(p{\vee}q{\vee}r){\wedge}(p{\vee}q{\vee}{\lnot}r){\wedge}(p{\vee}{\lnot}q{\vee}r){\wedge}(p{\vee}{\lnot}q{\vee}{\lnot}r){\wedge}({\lnot}p{\vee}q{\vee}r)\] Also, \[(p{{\wedge}}q){{\vee}}(p{{\wedge}}r)\] \[{\Leftrightarrow}(p{\wedge}q{\wedge}(r{\vee}{\lnot}r)){\vee}(p{\wedge}(q{\vee}{\lnot}q){\wedge}r)\] \[{\Leftrightarrow}(p{\wedge}q{\wedge}r){\vee}(p{\wedge}q{\wedge}{\lnot}r){\vee}(p{\wedge}q{\wedge}r){\vee}(p{\wedge}{\lnot}q{\wedge}r)\] \[{\Leftrightarrow}(p{\wedge}q{\wedge}r){\vee}(p{\wedge}q{\wedge}{\lnot}r){\vee}(p{\wedge}{\lnot}q{\wedge}r)\]

The total number of minterms in PDNF and maxterms in PCNF is: $8=2^3$.

Simplified Truth Table Method for Principal Normal Forms

In general, $n$ propositional variables produce $2^{n}$ distinct minterms, denoted $m_{0}, m_{1}, \cdots, m_{2^n-1}$; $m_{i}$ denotes the $i$-th minterm.

Representation of minterm subscripts: The $i$-th minterm $m_{i}$ of $2^{n}$ minterms formed by $n$ propositional variables has its subscript $i$ encoded in $n$-bit binary.

When a position is a propositional variable, the corresponding binary bit is 1; when it is the negation of a propositional variable, the corresponding binary bit is 0.

Truth table of the 4 distinct minterms of two propositional variables

\[ \begin{array}{ccccccc} p & q & {\lnot}p{\wedge}{\lnot}q & {\lnot}p{\wedge}q & p{\wedge}{\lnot}q & p{\wedge}q&\\ && m_0(m_{00})& m_1(m_{01})& m_2(m_{10})& m_3(m_{11})&\\ 0 & 0 & 1&0&0&0 & m_0\\ 0 & 1 & 0&1&0&0 & m_1 \\ 1 & 0 & 0&0&1&0 & m_2 \\ 1 & 1 & 0&0&0&1 & m_3 \\ \end{array} \]

Decimal and binary subscript encodings of minterms.

Properties of minterms:

Each minterm has truth value $T$ when its interpretation matches its encoding; for all other $2^{n}-1$ interpretations its truth value is $F$.
The conjunction of any two distinct minterms is a contradiction, i.e. $m_{i}{\wedge}m_{j}{\Leftrightarrow}F(i{\neq}j).$
The disjunction of all minterms is a tautology, i.e. $m_{0}{\vee}m_{1}{\vee}{\cdots}{\vee}m_{2^{n}-1}{\Leftrightarrow}T.$

In general, $n$ propositional variables produce $2^{n}$ distinct maxterms, denoted $M_{0}, M_{1}, \cdots, M_{2^{n}-1}$; $M_{i}$ denotes the $i$-th maxterm.

Representation of maxterm subscripts: The $i$-th maxterm $M_{i}$ of $2^{n}$ distinct maxterms formed by $n$ propositional variables has its subscript $i$ encoded in $n$-bit binary.

When a position of the maxterm is a propositional variable, the corresponding binary bit is 0; when it is the negation, the corresponding binary bit is 1.

Truth table of the 4 distinct maxterms of two propositional variables

\[ \begin{array}{ccccccc} p & q & {\lnot}p{\vee}{\lnot}q & {\lnot}p{\vee}q & p{\vee}{\lnot}q & p{\vee}q&\\ && M_3(M_{11})& M_2(M_{10})& M_1(M_{01})& M_0(M_{00})&\\ 1 & 1 & 0&1&1&1 & M_3\\ 1 & 0 & 1&0&1&1 & M_2\\ 0 & 1 & 1&1&0&1 & M_1\\ 0 & 0 & 1&1&1&0 & M_0\\ \end{array} \]

Properties of maxterms:

Each maxterm has truth value $F$ when its interpretation matches its encoding; for all other $2^{n}-1$ interpretations its truth value is $T$.
The disjunction of any two distinct maxterms is a tautology, i.e. $M_{i}{\vee}M_j{\Leftrightarrow}T(i{\neq}j).$
The conjunction of all maxterms is a contradiction, i.e. $M_{0}{\wedge}M_{1}{\wedge}{\cdots}{\wedge}M_{2^{n}-1}{\Leftrightarrow}F.$

Find the principal disjunctive and conjunctive normal forms of the following propositional formula: \[q{\wedge}(p{\vee}{\lnot}q)\] Solution: Construct the PDNF \[ \begin{array}{cccc} p & q & q{\wedge}(p{\vee}{\lnot}q) &\\ 0 & 0 & 0 & m_0\\ 0 & 1 & 0 & m_1\\ 1 & 0 & 0 & m_2\\ 1 & 1 & 1 & m_3\\ \end{array} \] So the principal disjunctive normal form of $q{\wedge}(p{\vee}{\lnot}q)$ is: \[q{\wedge}(p{\vee}{\lnot}q){\Leftrightarrow}m_{3}{\Leftrightarrow}m_{11}{\Leftrightarrow}p{\wedge}q.\]

Construct the PCNF

\[ \begin{array}{cccc} p & q & q{\wedge}(p{\vee}{\lnot}q) &\\ 1 & 1 & 1 & M_3\\ 1 & 0 & 0 & M_2\\ 0 & 1 & 0 & M_1\\ 0 & 0 & 0 & M_0\\ \end{array} \] So the principal conjunctive normal form of $q{\wedge}(p{\vee}{\lnot}q)$ is: \[q{\wedge}(p{\vee}{\lnot}q)\] \[{\Leftrightarrow}M_{0}{\wedge}M_{1}{\wedge}M_{2}\] \[{\Leftrightarrow}M_{00}{\wedge}M_{01}{\wedge}M_{10}\] \[{\Leftrightarrow}(p{\vee}q){\wedge}(p{\vee}{\lnot}q){\wedge}({\lnot}p{\vee}q)\]

Truth table of the 8 distinct minterms of three propositional variables

\[ \begin{array}{ccccccccc} &&&m_0&m_1&m_2&m_3&m_4&m_5&m_6&m_7\\ p & q & r & \bar{p}\bar{q}\bar{r} & \bar{p}\bar{q}{r} & \bar{p}{q}\bar{r} &\bar{p}{q}{r} & {p}\bar{q}\bar{r} & {p}\bar{q}{r} & {p}{q}\bar{r} & {p}{q}{r}\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & m_0\\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & m_1\\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & m_2\\ 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & m_3\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & m_4\\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & m_5\\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & m_6\\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & m_7\\ \end{array} \]

Truth table of the 8 distinct maxterms of three propositional variables

\[ \begin{array}{ccccccccc} p & q & r & M_7&M_6&M_5&M_4&M_3&M_2&M_1&M_0\\ 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & M_7\\ 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & M_6\\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & M_5\\ 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & M_4\\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & M_3\\ 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & M_2\\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & M_1\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & M_0\\ \end{array} \]

Note: Here $M_7$ corresponds to $\lnot{p}{\lor}\lnot{q}{\lor}\lnot{r}$.

Find the principal normal forms of $(p{\wedge}q){\vee}r$.

\[ \begin{array}{cccccc} p & q & r & (p{\wedge}q){\vee}r&&\\ 0 & 0 & 0 & 0 & m_0 & \boxed{M_0}\\ 0 & 0 & 1 & 1 & \boxed{m_1} & M_1\\ 0 & 1 & 0 & 0 & m_2 & \boxed{M_2}\\ 0 & 1 & 1 & 1 & \boxed{m_3} & M_3\\ 1 & 0 & 0 & 0 & m_4 & \boxed{M_4}\\ 1 & 0 & 1 & 1 & \boxed{m_5} & M_5\\ 1 & 1 & 0 & 1 & \boxed{m_6} & M_6\\ 1 & 1 & 1 & 1 & \boxed{m_7} & M_7\\ \end{array} \]

Principal disjunctive normal form: \[(p{\wedge}q){\vee}r{\Leftrightarrow}m_{1}{\vee}m_{3}{\vee}m_{5}{\vee}m_{6}{\vee}m_{7}\] \[{\Leftrightarrow}({\lnot}p{\wedge}{\lnot}q{\wedge}r){\vee}({\lnot}p{\wedge}q{\wedge}r){\vee}(p{\wedge}{\lnot}q{\wedge}r)\] \[{\vee}(p{\wedge}q{\wedge}{\lnot}r){\vee}(p{\wedge}q{\wedge}r)\] \[{\Leftrightarrow}m_{001}{\vee}m_{011}{\vee}m_{101}{\vee}m_{110}{\vee}m_{111}\]

Principal conjunctive normal form: \[(p{\wedge}q){\vee}r{\Leftrightarrow}M_{0}{\wedge}M_{2}{\wedge}M_{4}\] \[{\Leftrightarrow}(p{\vee}q{\vee}r){\wedge}(p{\vee}{\lnot}q{\vee}r){\wedge}({\lnot}p{\vee}q{\vee}r)\] \[{\Leftrightarrow}M_{000}{\wedge}M_{010}{\wedge}M_{100}\]

Find the principal normal forms of $({\lnot}p{\rightarrow}r){\wedge}(q{\leftrightarrow}p)$.

\[ \begin{array}{cccccc} p & q & r & ({\lnot}p{\rightarrow}r){\wedge}(q{\leftrightarrow}p)&&\\ 0 & 0 & 0 & 0 & m_0 & \boxed{M_0}\\ 0 & 0 & 1 & 1 & \boxed{m_1} & M_1\\ 0 & 1 & 0 & 0 & m_2 & \boxed{M_2}\\ 0 & 1 & 1 & 1 & m_3 & \boxed{M_3}\\ 1 & 0 & 0 & 0 & m_4 & \boxed{M_4}\\ 1 & 0 & 1 & 1 & m_5 & \boxed{M_5}\\ 1 & 1 & 0 & 1 & \boxed{m_6} & M_6\\ 1 & 1 & 1 & 1 & \boxed{m_7} & M_7\\ \end{array} \]

Principal disjunctive normal form: \[({\lnot}p{\rightarrow}r){\wedge}(q{\leftrightarrow}p)\] \[{\Leftrightarrow}m_{1}{\vee}m_{6}{\vee}m_{7}\] \[{\Leftrightarrow}m_{001}{\vee}m_{110}{\vee}m_{111}\] \[{\Leftrightarrow}({\lnot}p{\wedge}{\lnot}q{\wedge}r){\vee}(p{\wedge}q{\wedge}{\lnot}r){\vee}(p{\wedge}q{\wedge}r)\] Principal conjunctive normal form: \[({\lnot}p{\rightarrow}r){\wedge}(q{\leftrightarrow}p)\] \[{\Leftrightarrow}M_{0}{\wedge}M_{2}{\wedge}M_{3}{\wedge}M_{4}{\wedge}M_{5}\] \[{\Leftrightarrow}M_{000}{\wedge}M_{010}{\wedge}M_{011}{\wedge}M_{100}{\wedge}M_{101}\] \[{\Leftrightarrow}(p{\vee}q{\vee}r){\wedge}(p{\vee}{\lnot}q{\vee}r){\wedge}(p{\vee}{\lnot}q{\vee}{\lnot}r){\wedge}({\lnot}p{\vee}q{\vee}r){\wedge}({\lnot}p{\vee}q{\vee}{\lnot}r)\]

Relationship between minterms and maxterms: \[{\lnot}m_{i}{\Leftrightarrow}M_{i}, \, \, {\lnot}M_{i}{\Leftrightarrow}m_{i}\] Let propositional formula $A$ contain $n$ propositional variables. The PDNF of $A{\vee}{\lnot}A$ (tautology) should contain all $2^{n}$ minterms of $n$ propositional variables.

Conversely, the PCNF of $A{\wedge}{\lnot}A$ (contradiction) should contain all $2^{n}$ maxterms of $n$ propositional variables.

Steps to find the PCNF from the known PDNF of $A$:

Find the PDNF of ${\lnot}A$, i.e., the disjunction of minterms not appearing in the PDNF of $A$;
${\lnot}{\lnot}A$ gives the PCNF of $A$.

Steps to find the PDNF from the known PCNF of $A$:

Find the PCNF of ${\lnot}A$, i.e., the conjunction of maxterms not appearing in the PCNF of $A$;
${\lnot}{\lnot}A$ gives the PDNF of $A$.

Find the principal normal forms of the propositional formula: \[A=(p{\rightarrow}q){\wedge}q\] Solution: \[A=(p{\rightarrow}q){\wedge}q\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}q\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}(p{\vee}q){\wedge}({\lnot}p{\vee}q)\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}(p{\vee}q)\] \[{\Leftrightarrow}M_{10}{\wedge}M_{00}\]

\[{\lnot}A{\Leftrightarrow}M_{01}{\wedge}M_{11}\] \[{\lnot}{\lnot}A{\Leftrightarrow}{\lnot}(M_{01}{\wedge}M_{11}){\Leftrightarrow}m_{01}{\vee}m_{11}\] \[{\Leftrightarrow}({\lnot}p{\wedge}q){\vee}(p{\wedge}q)\]

Find the principal normal forms of the propositional formula: \[A=p{\vee}(q{\wedge}{\lnot}r)\] Solution: \[A=p{\vee}(q{\wedge}{\lnot}r)\] \[{\Leftrightarrow}(p{\wedge}({\lnot}q{\vee}q){\wedge}({\lnot}r{\vee}r)){\vee}(({\lnot}p{\vee}p){\wedge}(q{\wedge}{\lnot}r))\] \[{\Leftrightarrow}(p{\wedge}{\lnot}q{\wedge}{\lnot}r){\vee}(p{\wedge}{\lnot}q{\wedge}r){\vee}(p{\wedge}q{\wedge}{\lnot}r){\vee}(p{\wedge}q{\wedge}r){\vee}({\lnot}p{\wedge}q{\wedge}{\lnot}r)\]

\[{\Leftrightarrow}m_{100}{\vee}m_{101}{\vee}m_{110}{\vee}m_{111}{\vee}m_{010}\]

\[{\lnot}A{\Leftrightarrow}m_{000}{\vee}m_{001}{\vee}m_{011}\] \[{\lnot}{\lnot}A{\Leftrightarrow}{\lnot}(m_{000}{\vee}m_{001}{\vee}m_{011}){\Leftrightarrow}M_{000}{\wedge}M_{001}{\wedge}M_{011}\] \[{\Leftrightarrow}(p{\vee}q{\vee}r){\wedge}(p{\vee}q{\vee}{\lnot}r){\wedge}(p{\vee}{\lnot}q{\vee}{\lnot}r)\]

Applications of principal normal forms:

Determine whether two propositional formulas are equivalent;
Determine the type of a propositional formula.

To prove an equivalence, find the PDNF or PCNF of each propositional formula separately. If they are identical, the two formulas are equivalent; otherwise they are not.

Prove: $(p{\rightarrow}q){\wedge}q{\Leftrightarrow}(p{\vee}{\lnot}q){\rightarrow}q.$

Proof: \[(p{\rightarrow}q){\wedge}q\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}q\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}(p{\vee}q){\wedge}({\lnot}p{\vee}q)\] \[{\Leftrightarrow}(p{\vee}q){\wedge}({\lnot}p{\vee}q)\] \[(p{\vee}{\lnot}q){\rightarrow}q\] \[{\Leftrightarrow}{\lnot}(p{\vee}{\lnot}q){\vee}q{\Leftrightarrow}({\lnot}p{\wedge}q){\vee}q\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}q{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}(p{\vee}q){\wedge}({\lnot}p{\vee}q)\] \[{\Leftrightarrow}(p{\vee}q){\wedge}({\lnot}p{\vee}q)\]

Using principal normal forms to determine the type of a formula:

If $A$ is equivalent to $T$, or the PDNF of $A$ contains all $2^{n}$ minterms, then $A$ is a tautology;
If $A$ is equivalent to $F$, or the PCNF of $A$ contains all $2^{n}$ maxterms, then $A$ is a contradiction;
If $A$ is neither equivalent to $T$ nor to $F$, and its PDNF has fewer than $2^{n}$ minterms and its PCNF has fewer than $2^{n}$ maxterms, then $A$ is satisfiable.

Determine the type of the following propositional formulas.

$p{\vee}((p{\vee}q){\rightarrow}q)$

Solution: \[p{\vee}((p{\vee}q){\rightarrow}q)\] \[{\Leftrightarrow}p{\vee}({\lnot}(p{\vee}q){\vee}q)\] \[{\Leftrightarrow}p{\vee}q{\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}(p{\wedge}(q{\vee}{\lnot}q)){\vee}((p{\vee}{\lnot}p){\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}(p{\wedge}q){\vee}(p{\wedge}{\lnot}q){\vee}(p{\wedge}q){\vee}({\lnot}p{\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}(p{\wedge}q){\vee}(p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q)\] The PDNF contains 4 minterms, therefore it is a tautology.

$q{\wedge}(q{\rightarrow}p){\wedge}(p{\rightarrow}{\lnot}q)$

Solution: \[q{\wedge}(q{\rightarrow}p){\wedge}(p{\rightarrow}{\lnot}q)\] \[{\Leftrightarrow}q{\wedge}({\lnot}q{\vee}p){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}((p{\wedge}{\lnot}p){\vee}q){\wedge}({\lnot}q{\vee}p){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}(p{\vee}q){\wedge}({\lnot}p{\vee}q){\wedge}({\lnot}q{\vee}p){\wedge}({\lnot}p{\vee}{\lnot}q)\] The PCNF contains 4 maxterms, therefore it is a contradiction.

$p{\vee}(q{\wedge}{\lnot}({\lnot}p{\wedge}q)).$

Solution: \[p{\vee}(q{\wedge}{\lnot}({\lnot}p{\wedge}q))\] \[{\Leftrightarrow}p{\vee}(q{\wedge}(p{\vee}{\lnot}q))\] \[{\Leftrightarrow}p{\vee}(q{\wedge}p){\vee}(q{\wedge}{\lnot}q)\] \[{\Leftrightarrow}p{\vee}(p{\wedge}q)\] \[{\Leftrightarrow}(p{\wedge}(q{\vee}{\lnot}q)){\vee}(p{\wedge}q)\] \[{\Leftrightarrow}(p{\wedge}{\lnot}q){\vee}(p{\wedge}q)\] The PDNF contains 2 minterms, so it is a satisfiable formula.

Propositional Logic Reasoning Theory

Reasoning is the thought process of deriving new propositions from known ones.

The known propositions are called the premises or hypotheses of the reasoning; the new proposition is called the conclusion; the theory related to reasoning is called reasoning theory.

The premises of reasoning can be one or more propositional formulas; the conclusion is a propositional formula.

Let $A$, $B$ be propositional formulas. If $A{\rightarrow}B$ is a tautology, i.e., $A{\Rightarrow}B$, then the reasoning from $A$ to $B$ is called a valid argument. $B$ is also called a valid conclusion of $A$, or $B$ can be derived from premise $A$.

Let $A_{1}, A_{2}, {\cdots}, A_n$ and $B$ be propositional formulas. If: \[(A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n){\rightarrow}B\] is a tautology, i.e.: \[A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n{\Rightarrow}B\] then the reasoning from $A_{1}, A_{2}, {\cdots}, A_n$ to $B$ is called a valid argument; $B$ is called a valid conclusion of the set of premises $A_{1}, A_{2}, {\cdots}, A_n$, or $B$ can be derived from the set of premises $A_{1}, A_{2}, {\cdots}, A_n$.

This form of reasoning from premises to conclusion can be written as: \[{A_{1}, A_{2}, {\cdots}, A_n}{\vdash}B\] where ${\vdash}$ means “derives”; ${A_{1}, A_{2}, {\cdots}, A_n}{\vdash}B$ is called the formal structure of the argument.

If the argument is valid, we write: \[{A_{1}, A_{2}, {\cdots}, A_n}{\vDash}B\] that is, $A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n{\Rightarrow}B$.

Methods of Reasoning

The process of identifying valid conclusions is called reasoning or argumentation.

Common argumentation methods include:

Simple proof method
Formal proof method (constructive proof method)

Simple Proof Method

Let $A_{1}, A_{2}, {\cdots}, A_n$ and $B$ be propositional formulas. To prove: \[{A_{1}, A_{2}, {\cdots}, A_n}{\vDash}B\] one can prove that \[(A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n){\rightarrow}B\] is a tautology, i.e., \[(A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n){\rightarrow}B\] in the truth table, under every interpretation, \[(A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n){\rightarrow}B\] the truth value is always true.

Determine whether ${\lnot}p$ is a valid conclusion of the premises $p{\rightarrow}q$, ${\lnot}q$.

Solution: First construct the truth table of $((p{\rightarrow}q){\wedge}{\lnot}q){\rightarrow}{\lnot}p$

\[ \begin{array}{ccccccc} p & q & {\lnot}p & {\lnot}q & p{\rightarrow}q & (p{\rightarrow}q){\wedge}{\lnot}q & ((p{\rightarrow}q){\wedge}{\lnot}q){\rightarrow}{\lnot}p \\ 0 & 0 & 1&1&1&1&1 \\ 0 & 1 & 1&0&1&0&1 \\ 1 & 0 & 0&1&0&0&1 \\ 1 & 1 & 0&0&1&0&1 \\ \end{array} \]

From the truth table, $((p{\rightarrow}q){\wedge}{\lnot}q){\rightarrow}{\lnot}p$ is a tautology, so $((p{\rightarrow}q){\wedge}{\lnot}q){\vdash}{\lnot}p$ is valid.

That is: ${\lnot}p$ is a valid conclusion of the premises $p{\rightarrow}q, {\lnot}q$.

Formal Proof Method

A formal proof (constructive proof) is a sequence of propositional formulas describing the reasoning process; each formula in the sequence is either a known premise or a conclusion derived from some premises.

Inference rules include:

P-rule (premise introduction rule)
T-rule (conclusion introduction rule)
Substitution rule
CP-rule

as well as basic equivalences and basic tautological implications.

$P$-rule (Premise Introduction Rule): A premise may be introduced at any step in the derivation.

$T$-rule (Conclusion Introduction Rule) During a derivation, if one or more previously established propositional formulas imply conclusion $B$, then $B$ may be used as a premise in subsequent steps.

$CP$-rule: If the valid conclusion has the form $R{\rightarrow}C$, then $R$ may be added as an additional premise, and it suffices to derive $C$.

In a formal proof, to obtain a valid conclusion from given premises, two basic methods are commonly used: direct proof and indirect proof.

Both methods require constructing three sequences:

The first sequence is step numbers; the second is the sequence of derived propositional formulas; the third is the annotation sequence, including the inference rules applied and the reasoning laws used, i.e., the justification for each step.

Direct proof method

The direct proof method derives the valid conclusion from a set of known premises using inference rules, basic equivalences, and basic tautological implications.

The following proves that ${\lnot}p$ is a valid conclusion of the premises $p{\rightarrow}{\lnot}q, q{\vee}{\lnot}r, r$.

$r, \qquad$ $P$-rule
$q{\vee}{\lnot}r, \qquad$ $P$-rule
$q, \qquad$ $T$-rule (disjunctive syllogism), (1)(2)
$p{\rightarrow}{\lnot}q, \quad$ $P$-rule
$q{\rightarrow}{\lnot}p, \quad$ $T$-rule (contrapositive), (4)
${\lnot}p, \quad$ $T$-rule (modus ponens), (3)(5)

So ${\lnot}p$ is a valid conclusion of the premises $p{\rightarrow}{\lnot}q, q{\vee}{\lnot}r$, $r$.

Prove: $\{(p{\vee}q){\rightarrow}r, r{\rightarrow}s, {\lnot}s\}{\vDash}({\lnot}p{\vee}{\lnot}q)$

Proof:

$(p{\vee}q){\rightarrow}r\qquad$ $P$-rule
$r{\rightarrow}s\qquad$ $P$-rule
$(p{\vee}q){\rightarrow}s\qquad$ $T$-rule, (1)(2)
${\lnot}s\qquad$ $P$-rule
${\lnot}(p{\vee}q)\qquad$ $T$-rule, (3)(4)
${\lnot}p{\wedge}{\lnot}q\qquad$ $T$-rule, (5)

So $\{(p{\vee}q){\rightarrow}r, r{\rightarrow}s, {\lnot}s\}{\vDash}({\lnot}p{\wedge}{\lnot}q)$ is valid.

Prove: $\{(w{\vee}r){\rightarrow}v, v{\rightarrow}c{\vee}s, s{\rightarrow}u, {\lnot}c{\wedge}{\lnot}u\}{\vDash}{\lnot}w$

Proof:

${\lnot}c{\wedge}{\lnot}u\qquad$ $P$-rule
${\lnot}u\qquad$ $T$-rule, (1)
$s{\rightarrow}u\qquad$ $P$-rule
${\lnot}s\qquad$ $T$-rule, (2)(3)
${\lnot}c\qquad$ $T$-rule, (1)
${\lnot}c{\wedge}{\lnot}s\qquad$ $T$-rule, (4)(5)

${\lnot}(c{\vee}s)\qquad$ $T$-rule, (4)
$(w{\vee}r){\rightarrow}v\qquad$ $P$-rule
$v{\rightarrow}c{\vee}s\qquad$ $P$-rule
$(w{\vee}r){\rightarrow}(c{\vee}s)\qquad$ $T$-rule, (8)(9)
${\lnot}(w{\vee}r)\qquad$ $T$-rule (7)(10)
${\lnot}w{\wedge}{\lnot}r\qquad$ $T$-rule, (11)
${\lnot}w\qquad$ $T$-rule, (12)

Example: A number is a complex number if and only if it is a real or imaginary number. A number is neither real nor imaginary, therefore it is not a complex number.

Proof: First symbolize the premises and conclusion.

$p$: A number is a complex number.

$q$: A number is a real number.

$r$: A number is an imaginary number.

Premise: $p{\leftrightarrow}(q{\vee}r), {\lnot}q{\wedge}{\lnot}r$

Conclusion: ${\lnot}p$

$p{\leftrightarrow}(q{\vee}r)\qquad$ $P$-rule
$(p{\rightarrow}(q{\vee}r)){\wedge}((q{\vee}r){\rightarrow}p)\quad$ $T$-rule, (1)
$p{\rightarrow}(q{\vee}r)\qquad$ $P$-rule
${\lnot}q{\wedge}{\lnot}r\qquad$ $P$-rule
${\lnot}(q{\vee}r)\qquad$ $T$-rule, (4)
${\lnot}p\qquad$ $T$-rule, (3)(5)

Therefore, ${\lnot}p$ is a valid conclusion of the premises $p{\leftrightarrow}(q{\vee}r), {\lnot}q{\wedge}{\lnot}r$.

Indirect Proof Method

Proof by Contradiction

Let $A_{1}, A_{2}, {\cdots}, A_n$ be propositional formulas, and $P_{1}, P_{2}, {\cdots}, P_m$ be all the propositional variables appearing in them.

If there exists at least one interpretation that makes $A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n$ true, then the propositional formulas $A_{1}, A_{2}, {\cdots}, A_n$ are called consistent (compatible).

Otherwise, if for every interpretation at least one $A_i\ (1{\leq}i{\leq}n)$ is false, making $A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n$ false, then the propositional formulas $A_{1}, A_{2}, {\cdots}, A_n$ are called inconsistent (incompatible).

Theorem: $A_{1}, A_{2}, {\cdots}, A_n$ are inconsistent if and only if, for any propositional formula $R$, \[A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n{\Rightarrow}R{\wedge}{\lnot}R.\]

Theorem: Let $A_{1}, A_{2}, {\cdots}, A_n$, $C$ be propositional formulas, with $A_{1}, A_{2}, {\cdots}, A_n$ consistent. If $A_{1}, A_{2}, {\cdots}, A_n, {\lnot}C$ is inconsistent, then $C$ is a valid conclusion of $A_{1}, A_{2}, {\cdots}, A_n$.

To prove \[{A_{1}, A_{2}, {\cdots}, A_n}{\vdash}C\] is valid, it suffices to prove: \[A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n{\wedge}{\lnot}C{\Rightarrow}R{\wedge}{\lnot}R.\]

Prove: ${\lnot}D$ is a valid conclusion of the premises $A{\rightarrow}B, {\lnot}B{\vee}C, {\lnot}C, D{\rightarrow}A$.

Proof: Use proof by contradiction. Add ${\lnot}({\lnot}D){\Leftrightarrow}D$ as an additional premise.

$D\qquad$ $P$ (additional premise)
$D{\rightarrow}A\qquad$ $P$
$A\qquad$ $T$, (1)(2)
$A{\rightarrow}B\qquad$ $P$
$B\qquad$ $T$, (3)(4)
${\lnot}B{\vee}C\qquad$ $P$
$C\qquad$ $T$, (5)(6)
${\lnot}C\qquad$ $P$
$C{\wedge}{\lnot}C\qquad$ $T$, (7)(8)

Prove: ${\lnot}p{\wedge}{\lnot}q{\vDash}{\lnot}(p{\wedge}q).$

Proof: Add ${\lnot}{\lnot}(p{\wedge}q){\Leftrightarrow}p{\wedge}q$ as an additional premise.

$p{\wedge}q\qquad$ $P$ (additional premise)
$p\qquad$ $T$, (1)
${\lnot}p{\wedge}{\lnot}q\qquad$ $P$
${\lnot}p\qquad$ $T$, (3)
$p{\wedge}{\lnot}p\qquad$ $T$, (2)(4)

The conclusion $p{\wedge}{\lnot}p$ is a contradiction, therefore \[{\lnot}p{\wedge}{\lnot}q{\vDash}{\lnot}(p{\wedge}q)\]

Prove: ${\lnot}p{\wedge}{\lnot}q{\vDash}{\lnot}(p{\wedge}q).$

Proof:

${\lnot}p{\wedge}{\lnot}q\qquad$ $P$
${\lnot}p\qquad$ $T$, (1)
${\lnot}p{\vee}{\lnot}q\qquad$ $T$, (2)
${\lnot}(p{\wedge}q)\qquad$ $T$, (3)

Therefore, \[{\lnot}p{\wedge}{\lnot}q{\vDash}{\lnot}(p{\wedge}q).\]

CP-Rule

If the valid conclusion has the form $R{\rightarrow}C$, then $R$ may be added to the premises as an additional premise, and it suffices to derive $C$.

\[{A_{1}, A_{2}, {\cdots}, A_n}{\vDash}R{\rightarrow}C\] This is equivalent to: \[{A_{1}, A_{2}, {\cdots}, A_n, R}{\vDash}C\]

Prove: $\{{\lnot}p{\vee}q, q{\rightarrow}s, {\lnot}p{\rightarrow}{\lnot}r\}{\vDash}r{\rightarrow}s$.

Proof: Since the conclusion $r{\rightarrow}s$ is a conditional, we apply the $CP$-rule: add the antecedent $r$ of the conclusion as an additional premise, i.e.: \[\{{\lnot}p{\vee}q, q{\rightarrow}s, {\lnot}p{\rightarrow}{\lnot}r, r\}{\vDash}s\]

$r\qquad$ $P$ (additional premise)
${\lnot}p{\rightarrow}{\lnot}r\qquad$ $P$
$r{\rightarrow}p\qquad$ $T$, (2)

$p\qquad$ $T$, (1)(3)
${\lnot}p{\vee}q\qquad$ $P$
$q\qquad$ $T$, (4)(5)
$q{\rightarrow}s\qquad$ $P$
$s\qquad$ $T$, (6)(7)
$r{\rightarrow}s\qquad$ $CP$, (1)(8)

Example: Given the following situation, determine whether the argument is valid.

Premises:

If I do not play games, I will have sufficient time.
If I have sufficient time, I will study English diligently.
If I study English diligently, I will not fail my English exam.

Conclusion: I failed my English exam, therefore I must have been playing games.

Proof: First symbolize the premises and conclusion.

$p$: I play games.

$q$: I have sufficient time.

$r$: I study English diligently.

$s$: I pass my English exam.

Premises: ${\lnot}p{\rightarrow}q, q{\rightarrow}r, r{\rightarrow}s$

Conclusion: ${\lnot}s{\rightarrow}p$.

Restate the premises and conclusion:

Premises: ${\lnot}p{\rightarrow}q, q{\rightarrow}r, r{\rightarrow}s$

Conclusion: ${\lnot}s{\rightarrow}p$

Since the conclusion ${\lnot}s{\rightarrow}p$ is a conditional, we can apply the $CP$-rule.

${\lnot}p{\rightarrow}q\qquad$ $P$
$q{\rightarrow}r\qquad$ $P$
${\lnot}p{\rightarrow}r\qquad$ $T$, (1)(2)

$r{\rightarrow}s\qquad$ $P$
${\lnot}p{\rightarrow}s\qquad$ $T$, (3)(4)
$ \$ (additional premise)
$p\qquad$ $T$, (5)(6)
${\lnot}s{\rightarrow}p\qquad$ $CP$, (6)(7)