Tautology And Contradiction

In logic and mathematics, statements can often be classified based on their truth values under all possible scenarios. Two significant classifications are tautology and contradiction. Additionally, the concept of quantifiers plays a crucial role in expressing mathematical statements that involve generality or existence.

Tautology

A compound statement is called tautology if it is always true for all possible truth values of its component statement.

For example, $p ∨ ~p , ( p ⇒ q ) ∨ ( q ⇒ p ) $

It is denoted by the letter ' $t$ '

Contradiction (fallacy)

A compound statement is called a contradiction if it is always false for all possible truth values of its component statement.

For example, $p ∧ ~p, ∼(( p ⇒ q ) ∨ ( q ⇒ p )) $

It is denoted by letter ' $c$ ' or ' $f$ '

Truth Table

$\begin{array}{|c|c|c|c|c|c|c|c|}\hline \mathrm{\;\;\;\;\;}p\mathrm{\;\;\;\;\;}&\mathrm{\;\;\;}q\mathrm{\;\;\;}&\mathrm{\;\;\;\;\;}p\rightarrow q\mathrm{\;\;\;\;\;}&\mathrm{\;\;\;} q\rightarrow p\mathrm{\;\;\;} &\mathrm{\;\;\;}\left ( p\rightarrow q \right )\vee\left ( q\rightarrow p \right )\mathrm{\;\;}&\mathrm{\;\;\;}\sim\left ( \left ( p\rightarrow q \right )\vee\left ( q\rightarrow p \right ) \right ) \mathrm{\;\;} \\\hline \hline \mathrm{T}&\mathrm{T} & \mathrm{T} &\mathrm{T}&\mathrm{T}&\mathrm{F} \\ \hline \mathrm{T}&\mathrm{F} & \mathrm{F} &\mathrm{T}&\mathrm{T}&\mathrm{F} \\ \hline \mathrm{F}&\mathrm{T} & \mathrm{T} &\mathrm{F}&\mathrm{T}&\mathrm{F} \\ \hline \mathrm{F}&\mathrm{F} & \mathrm{T} &\mathrm{T}&\mathrm{T}&\mathrm{F} \\ \hline\end{array}$

Quantifiers

Quantifiers are phrases like ‘These exist’ and “for every”. We come across many mathematical statements containing these phrases.

For example

$p$ : For every prime number $x, √x$ is an irrational number.

$q$ : There exists a triangle whose all sides are equal.

There are two types of quantifiers

1. Universal: In this words like 'For all', 'All', 'For every', "Every' etc, are used and it denotes that all members of a set has that property.

For example, p : 'For every prime number $x, √x$ is an irrational number' tells us that the property mentioned is applicable to all the prime numbers

2. Existential: In this words like 'There exist a', 'Some', 'There is at least one' etc, are used and it denotes that there is at least one member in the set that has that property.

For example, $q$ : 'There exists a triangle whose all sides are equal' tells us that the property mentioned is applicable to at least one triangle.

Negation of statement containing a quantifier

To find the negation of a statement with a quantifier, apart from adding 'not' at appropriate place (as we usually do for finding negation of a mathematical statements), we also interchange the quantifier from universal to existential and vice versa

For example,

1. Negation of $p$ : 'For every prime number $x, √x$ is an irrational number'

is $\sim p$ : 'There is at least one prime number x such that √x is an not an irrational number'

Notice that apart from adding 'not', we have also changed the type of quantifier

2. Negation of $q$ : 'There exists a triangle whose all sides are equal'

is ' $\sim q$ : 'For every triangle, all sides are not equal'

Solved Examples Based on Tautology And Contradiction

Example 1: Which of the following Boolean expressions is a tautology?

1) $(p \wedge q) \vee(p \rightarrow q)$
2) $(p \wedge q) \vee(p \vee q)$
3) $(p \wedge q) \rightarrow(p \rightarrow q)$
4) $(p \wedge q) \wedge(p \rightarrow q)$

Solution

$(p \wedge q) \rightarrow(p \rightarrow q)$ is tautology

Example 2: If $P$ and $Q$ are two statements, then which of the following compound statement is a tautology?
1) $((P \Rightarrow Q) \wedge \sim Q) \Rightarrow Q$
2) $((P \Rightarrow Q) \wedge \sim Q) \Rightarrow P$
3) $((P \Rightarrow Q) \wedge \sim Q) \Rightarrow \sim P$
4) $((P \Rightarrow Q) \wedge \sim Q) \Rightarrow \Rightarrow(P \wedge Q)$

Solution
LHS of all the option are same

$
\begin{aligned}
((P \rightarrow Q) \wedge \sim Q) & \equiv(\sim P \vee Q) \wedge \sim Q \\
& \equiv(\sim P \wedge \sim Q) \vee(Q \wedge \sim Q) \\
& \equiv \sim P \wedge \sim Q
\end{aligned}
$
$
\begin{aligned}
& \text { (A) } \\
& (\sim P \wedge \sim Q) \rightarrow Q \\
& \quad \equiv \sim(\sim P \wedge \sim Q) \vee Q \\
& \quad \equiv(P \vee Q) \vee Q \neq \text { tautology }
\end{aligned}
$

(B)
$(\sim P \wedge \sim Q) \rightarrow P \equiv(\mathrm{P} \vee \mathrm{Q}) \vee \mathrm{P} \neq$ Tautology
(C)
$
\begin{aligned}
& (\sim P \wedge \sim Q) \rightarrow \sim P \\
& \quad \equiv \sim(\sim P \wedge \sim Q) \vee \sim P \\
& \quad \equiv(P \vee Q) \vee \sim P=\text { tautology }
\end{aligned}
$
(D)
$
\begin{aligned}
& (\sim P \wedge \sim Q) \rightarrow(P \wedge Q) \\
& \quad \equiv(P \vee Q) \vee(P \wedge Q) \neq \text { Tautology }
\end{aligned}
$

Example 3: If the Boolean expression $(p \Rightarrow q) \Leftrightarrow(q *(\sim p))_{\text {is a tautology, }}$ then Boolean expression $p *(\sim q)$ is equivalent to :
1) $\sim q \Rightarrow p$
2) $q \Rightarrow p$
3) $p \Rightarrow \sim q$
4) $p \Rightarrow q$

Solution
$
\begin{aligned}
& (p \Rightarrow q) \Leftrightarrow(q *(\sim p)) \\
& \because p \rightarrow q \equiv-p \vee q
\end{aligned}
$

So, $* \equiv \vee$
Thus, $p *(\sim q) \equiv \mathrm{p} \vee(\sim q) \equiv q \rightarrow p$

Example 4: If the Boolean expression $(p \wedge q) \circledast(p \otimes q)$ is a tautology, then $\circledast$ and $\otimes$ are respectively given by :
1) $\rightarrow, \rightarrow$
2) $\vee, \rightarrow$
3) $\wedge, \rightarrow$
4) $\wedge, \vee$

Solution

$\begin{array}{c|c|c|c|c} \mathrm{p} & \mathrm{q} & \mathrm{p} \wedge \mathrm{q} & \mathrm{p} \rightarrow \mathrm{q} & (\mathrm{p} \wedge \mathrm{q}) \rightarrow(\mathrm{p} \rightarrow \mathrm{q}) \\ \hline \mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{T} & \mathrm{T} \\ \mathrm{T} & \mathrm{F} & \mathrm{F} & \mathrm{F} & \mathrm{T} \\ \mathrm{F} & \mathrm{T} & \mathrm{F} & \mathrm{T} & \mathrm{T} \\ \mathrm{F} & \mathrm{F} & \mathrm{F} & \mathrm{T} & \mathrm{T} \end{array}$

Example 5: Which of these statement is a fallacy?
1) $p \vee q$
2) $p \wedge q$
3) $p \wedge \sim p$
4) $\sim p \wedge q$

Solution
The truth table for $p \wedge \sim p$ is always "$F$". Hence it is a fallacy.

Summary
Understanding the concepts of tautology, contradiction, and quantifiers is crucial in logical reasoning and mathematical proofs. Tautologies are universally true statements, while contradictions are universally false. Quantifiers allow us to express the generality or existence of certain properties across a set. In practical terms, recognizing tautologies and contradictions can help identify valid and invalid arguments, respectively. Moreover, understanding quantifiers and their negations enables one to formulate and understand universal and existential claims accurately.