Given statements $A$ and $B$, are the formulae $(\lnot A) \land (\lnot B)$ and $(\lnot A) \lor (\lnot B)$ equivalent?

Question

If I have 2 statements, say $A$ and $B$, from which I formed 2 formulae:

1. $f_1: (\lnot A) \land (\lnot B)$

2. $f_2: (\lnot A) \lor (\lnot B)$

Are $f_1$ and $f_2$ equivalent?

Answer 1

One way of verifying whether two boolean expressions are equivalent is to assign all possibilities to all variables, and comparing all results.

A	B	f1	f2
T	T	F	F
T	F	F	T
F	T	F	T
F	F	T	T

We can see (F, F, F, T) does not equal (F, T, T, T), for example for the assignment (A, B) = (T, F) we get result (f1, f2) = (F, T) , meaning f1 $\ne$ f2.

Answer 2

$f_1 \vdash f_2$, if and only if $f_2$ must be true if we assume $f_1$ to be true.

Similarly, $f_2 \vdash f_1$, if and only if $f_1$ must be true if we assume $f_2$ to be true.

Logically, by taking any value for $A$ or $B$, from the domain $\{1, 0 \}$, one could verify that $f_1 \vdash f_2$, because $f_2$ is true whenever $f_1$ is true (for example, when both $A = 0$ and $B = 0$).

However, $f_2 \vdash f_1$ is not true. As, in two cases, $f_2$ is true (e.g. $A = 0$ and $B=1$, or vice-versa), but $f_1$ is not true.

Answer 3

I find it easy to get a quick intuition of the truth value of logical statements involving negations by converting them wherever possible.

So assume by way of contradiction that $\textit{f}_1 \iff \textit{f}_2$, then the two-way contrapositive $\neg \textit{f}_1 \iff \neg \textit{f}_2$ also holds, hence $A \lor B \iff A \land B$ (De Morgan's law). Since $A \lor B \implies A \land B$ is easily confirmed false (by plugging in A=True and B=False) this is a contradiction. $\Box$