Tautology And Contradiction

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'

Recommended Video Based on Tautology and Contradiction

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.