Prove that a disjunction (in first-order logic) does not depend on the order or grouping of its disjuncts

381 Views Asked by At

For at least four disjuncts. For example, it should follow immediately that any two disjunctions of seven formulas are equivalent. There are 132 cases to check without this general result.

Prove using axioms, rules of inference, theorems of first-order logic. You may assume that disjunction is commutative and associative.

1

There are 1 best solutions below

10
On

Probably the best way of getting at this problem is to prove that disjunction is associative (so that the parentheses no longer matter) and that it is commutative (so that the order no longer matters). If you have those two properties, then you can simply place any of your disjunctions in increasing order by index to check equivalence.

EDIT: The original statement has been edited, so there are no longer indices to order by, but I think the spirit of the solution is clear.

EDIT 2: As per one of my comments, see this post as to why I think this problem is impossible as stated: Why can't we quantify over propositional functions/open formulas in first order languages?