2

So I have a statement that goes like this:

$$ ( \lnot A \lor B) \land(\lnot A \lor \lnot B) $$

I think it is equivalent to

$$ \lnot A $$

Am I right or not?

Asaf Karagila
  • 393,674
GawronDev
  • 23
  • 3
    Please explain your reasoning for why you think it is right. – vvg Nov 07 '22 at 18:38
  • 2
    It cannot be $B \land \lnot B$ at the same time while that is an error, so only think that is left is $\lnot A$ – GawronDev Nov 07 '22 at 18:40
  • 1
    Yes. Whether $B$ is true or false has no bearing on the output. So we can eliminate the variable $B$ from all clauses. We are left with only $\neg A \land \neg A$ which is equivalent to $\neg A$. – vvg Nov 07 '22 at 18:57

2 Answers2

5

Although it's a bit overkill for this problem, since there are only two variables, you can easily solve this with a truth table:

A B $\lnot A$ $( \lnot A \lor B) \land(\lnot A \lor \lnot B)$
True True False False
True False False False
False True True True
False False True True

As you fill in the last column, you can quickly realize that the truth value of B has no impact on the truth value of the expression $( \lnot A \lor B) \land(\lnot A \lor \lnot B)$.

M Turgeon
  • 10,419
3

  1. We have $(¬A∨B)∧(¬A∨¬B)$

  2. Realize that, by using the distributive law that is $p∨(q∧r)≡(p∨q)∧(p∨r)$, $-A∨(B∧¬B)$ is logically equivalent to$(¬A∨B)∧(¬A∨¬B)$. Let's have the simpler equivalent: $¬A∧(B∨¬B)$

  3. Using negation law yields $¬A∧⊤$

  4. Using identity law yields $¬A$

So, yes, you're right: $(¬A∨B)∧(¬A∨¬B)≡¬A$

Umar Siregar
  • 31