11

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
  • 1
    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
6

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

You then need to check their truth values for all possible combinations of a..f. 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 should be 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.

0

The question is how one can check in general whether two propositional logic formulas are equivalent. There are multiple ways to do this. I will outline four methods: truth table, tree proof, natural deduction and equivalence relations.

  1. Truth Table

To use a truth table generator connect both formulas with a biconditional and see if the column under the biconditional is always true. The following input, with added parentheses, should generate a truth table showing the biconditional is a tautology implying the two formulas are equivalent:

((A v (B v C)) & (D v (E v F)))<>((A & D) v ((A & E) v ((A & F) v ((B & D) v ((B & E) v (( B & F) v ((C & D) v ((C & E) v (C & F)))))))))

  1. Tree Proof

The tree proof approach is to negate the desired conclusion, which would be the entire biconditional, and then attempt to find a branch of the tree that does not lead to a contradiction. If no branch remains open, that is, in every branch a contradiction was found, then the negated conclusion is rejected and the biconditional is valid.

This tree proof generator provides a proof of equivalence of the two formulas.

  1. Natural Deduction

A proof checker makes sure one is using well-formed formula with the permitted inference rules. This provides confidence that any proof one provides is correct. For this proof checker enter the biconditional into the "Conclusion:" box and then attempt to derive that conclusion. One can check the proof along the way. When finished the proof checker will confirm that the proof is correct.

  1. Logical Equivalences

Wikipedia lists logical equivalences. Rather than a biconditional one uses an equivalence symbol between the formulas. If the two formulas are equivalent, one should be able to start with one formula, perhaps the most complicated one, and transform it into the other using these rules.


These are only four ways. The rules for any complete formal system should be able to show that a biconditional is valid, if it is. Also any proof assistant or proof checker should be able to help one provide a proof.

0

Would you be able to do it if I rewrote the problem in arithmetic language? De Morgan's Laws are just the distributive property.

  1. (a+b+c)(d+e+f)
  2. a(d+e+f)+b(d+e+f)+c(d+e+f)
  3. ad+ae+af+bd+be+bf+cd+ce+cf ∎

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.