8

For example:

Is (A ∨ B ∨ C) ∧ (D ∨ E ∨ F) the same as
(A ∧ D) ∨ (A ∧ E) ∨ (A ∧ F) ∨ (B ∧ D) ∨ (B ∧ E) ∨ ( B ∧ F) ∨ (C ∧ D) ∨ (C ∧ E) ∨ (C ∧ F)?

How would I check equivalence in general?

  • 2
    Yes, both formulas are equivalent. Apply the distributive law. – Jo Wehler Dec 1 '15 at 23:23
  • Well... Using discrete math methods? In fact equivalence is NP-hard problem, so there is no known practical way to do it. This means not every pair of formulas you can read can be checked by you for equivalence. But this is more a CS approach than philosophy. – rus9384 Aug 3 '18 at 1:34
5

In logic, equivalency means that two (or more expressions) are such that whenever one is true the other is and whenever one is false, the other is false.

In general, there are two ways to show that two things are equivalent. You could use logical reasoning, or a truth table.

Method 1: logical reasoning

For example, you could say (for a smaller case):

If (A ∨ B) ∧ (C ∨ D) is true, then we know (1) either A or B (or both) is true; (2) either C or D (or both) is true. Therefore, there are four cases: (1) A and C are true, (2) A and D are true, (3) B and C are true, (4) B and D are true.
So if (A ∨ B) ∧ (C ∨ D), then also (A ∧ C) ∨ (A ∧ D) ∨ (B ∧ C) ∨ (B ∧ D).

Furthermore, if (A ∧ C) ∨ (A ∧ D) ∨ (B ∧ C) ∨ (B ∧ D) is true we have to consider four cases:
(1) A ∧ C is true; then also (A ∨ B) ∧ (C ∨ D).
(2) A ∧ D is true; then also (A ∨ B) ∧ (C ∨ D).
(3) B ∧ C is true; then also (A ∨ B) ∧ (C ∨ D).
(4) B ∧ D is true; then also (A ∨ B) ∧ (C ∨ D).
So in all cases we see that (A ∨ B) ∧ (C ∨ D), so this follows from (A ∧ C) ∨ (A ∧ D) ∨ (B ∧ C) ∨ (B ∧ D).

Since we proved both directions we can now say that (A ∨ B) ∧ (C ∨ D) and (A ∧ C) ∨ (A ∧ D) ∨ (B ∧ C) ∨ (B ∧ D) are equivalent.

We often do this intuitively.

Method 2: truth table

This is (at least in this case) a bit similar, but you don't need to make up something clever. You basically try all possibilities for A, B, C, ... and see if the two expressions are equivalent in all cases.

There are many tools online that can make truth tables for you. I use CleanLogic (disclaimer: I wrote it). For example, you may input:

(a | b | c) & (d | e | f)
(a & d) | (a & e) | (a & f) | (b & d) | (b & e) | (b & f) | (c & d) | (c & e) | (c & f)

Note that the two columns on the right are always the same. Since the two expressions are the same in all cases, they are equivalent.

You can also put them into one expression, with an equivalence:

((a | b | c) & (d | e | f)) <-> ((a & d) | (a & e) | (a & f) | (b & d) | (b & e) | (b & f) | (c & d) | (c & e) | (c & f))

And then the corresponding column in the truth table shows all "True". Since the equivalence is true in all cases, it is true in general.

2

One can also proceed as follows: to show two formulas P and Q are equivalent, show that they each entail the other. To check whether P entails Q, check whether (P ∧ ¬Q) is satisfiable -- if so, then P does not entail Q. Similarly check whether (¬P ∧ Q) is satisfiable. If neither is satisfiable, then the formulas are equivalent. There are good algorithms for checking satisfiability. See also Resolution.

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.