4

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?

nbro
  • 39,006
  • 12
  • 98
  • 176
Coder
  • 141
  • 6

3 Answers3

3

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.

Gulzar
  • 729
  • 1
  • 8
  • 23
0

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

Gulzar
  • 729
  • 1
  • 8
  • 23
Coder
  • 141
  • 6
  • This is an old question and answer, but when you use $\vdash$, didn't you want to use $\rightarrow$? – nbro Jan 21 '21 at 19:38
0

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$

Tcfkaj
  • 101