Theory

Theory: equivalent formulas and negating statements

Published · by

Open PDF The PDF is in Romanian.

Summary

Two formulas are equivalent when they have the same truth values on every row of the table, and a tautology is true on all rows. De Morgan's laws show how to negate a compound statement: “and” turns into “or”, and the negation of “if $p$, then $q$” is “$p$ and not $q$”. An implication and its contrapositive always share the same value.

1. Propositional formulas

They are built from propositions $p,\ q,\ r,\ \ldots$, logical operators and brackets. Order of the operators: not, $\land$, $\vee$, $\rightarrow$, $\leftrightarrow$. For $n$ variables, the truth table has $2^{n}$ rows.

2. Tautologies. Equivalent formulas

Definitions

Tautology = a formula that is true for all values of its variables. Examples: $p \vee \overline{p}$, $p \rightarrow p$.

$A \equiv B$ (“$A$ is equivalent to $B$”): $A$ and $B$ have the same truth values on every row.

Example: $p \rightarrow q \equiv \overline{p} \vee q$.

3. Negation rules

Rule Formula
double negation $\overline{\overline{p}} \equiv p$
De Morgan's laws

$\overline{p \land q} \equiv \overline{p} \vee \overline{q}$

$\overline{p \vee q} \equiv \overline{p} \land \overline{q}$
negation of an implication $\overline{p \rightarrow q} \equiv p \land \overline{q}$

Check for $\overline{p \land q} \equiv \overline{p} \vee \overline{q}$:

$p$ $q$ $p \land q$ $\overline{p \land q}$ $\overline{p}$ $\overline{q}$ $\overline{p} \vee \overline{q}$
$1$ $1$ $1$ $0$ $0$ $0$ $0$
$1$ $0$ $0$ $1$ $0$ $1$ $1$
$0$ $1$ $0$ $1$ $1$ $0$ $1$
$0$ $0$ $0$ $1$ $1$ $1$ $1$

Negating relations: $=$ becomes $\neq$; $<$ becomes $\geq$; $>$ becomes $\leq$; $\in$ becomes $\notin$.

4. Negating statements – examples

  • “$x > 0$ and $y > 0$” → “$x \leq 0$ or $y \leq 0$”.
  • “$x = 1$ or $x = 2$” → “$x \neq 1$ and $x \neq 2$”.
  • “If it rains, I take my umbrella” → “It rains and I do not take my umbrella”.

5. The converse and the inverse of an implication

Definitions

For the implication $p \rightarrow q$: the converse $q \rightarrow p$; the inverse $\overline{p} \rightarrow \overline{q}$; the contrapositive $\overline{q} \rightarrow \overline{p}$.

$p$ $q$ $p \rightarrow q$ $q \rightarrow p$ $\overline{p} \rightarrow \overline{q}$ $\overline{q} \rightarrow \overline{p}$
$1$ $1$ $1$ $1$ $1$ $1$
$1$ $0$ $0$ $1$ $1$ $0$
$0$ $1$ $1$ $0$ $0$ $1$
$0$ $0$ $1$ $1$ $1$ $1$

Remember

$p \rightarrow q \equiv \overline{q} \rightarrow \overline{p}$ and $q \rightarrow p \equiv \overline{p} \rightarrow \overline{q}$. An implication and its converse may have different values.

Example

“If $n \vdots 4$, then $n \vdots 2$” – true; the converse “If $n \vdots 2$, then $n \vdots 4$” – false ($n = 6$); the contrapositive “If $n$ is not divisible by $2$, then it is not divisible by $4$” – true.

Frequently asked questions

What is the negation of an implication?

The negation of “if $p$, then $q$” is “$p$ and not $q$”: $\overline{p \rightarrow q} \equiv p \land \overline{q}$. The implication is false only when the hypothesis is true and the conclusion is false, and the negation states exactly that. A common mistake is to write “if not $p$, then not $q$”: that is the inverse, not the negation.

What do De Morgan's laws say?

The negation of a conjunction is the disjunction of the negations, and the negation of a disjunction is the conjunction of the negations: $\overline{p \land q} \equiv \overline{p} \vee \overline{q}$ and $\overline{p \vee q} \equiv \overline{p} \land \overline{q}$. When you negate a statement, “and” turns into “or”, and “or” turns into “and”.

What is the difference between the converse and the contrapositive?

For $p \rightarrow q$, the converse is $q \rightarrow p$ and the contrapositive is $\overline{q} \rightarrow \overline{p}$. The contrapositive always has the same truth value as the original implication; the converse may have a different one. Proof by contradiction rests on this equivalence.

How do I check whether two formulas are equivalent?

You build the truth table of both formulas, with all $2^{n}$ combinations of values of the $n$ variables. If the two columns agree on every row, the formulas are equivalent and you write $A \equiv B$. A single different row is enough to show that they are not equivalent.