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

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?

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.

$$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.

• This is an old question and answer, but when you use $\vdash$, didn't you want to use $\rightarrow$?
– nbro
Jan 21 at 19:38

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$$