4
$\begingroup$

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?

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.