If I start with this: $$(\neg p \vee \neg q) \vee (r \vee q)$$ are the following logical deductions correct:

$$(\neg p \vee \neg q) \vee (q \vee r) \text{Commutative Property}$$ Property $$(\neg p \vee r) \vee (q \vee \neg q) \text{Associative Property}$$

I just want to make sure I'm using the commutative and associate property correctly.



Your use of the commutative property of $\lor$ is fine enough, though you are also implicitly using a substitutability property as well. Commutativity says $\varphi\lor\psi\equiv\psi\lor\varphi$ but that doesn't necessarily immediately imply that $\Phi(\varphi\lor\psi)\equiv\Phi(\psi\lor\varphi)$ where $\Phi$ is some expression parameterized by a formula, for example, we need substitutability to say that $\chi\lor(\varphi\lor\psi)\equiv\chi\lor(\psi\lor\varphi)$.

Your use of the associative property of $\lor$ is incorrect. Associativity means you can change where the parentheses are in a formula (when all operators are the same and it is associative, here $\lor$). Changing where you place the parentheses will not change the order in which the subformulas occur. Your second example can be arrived at from the the earlier formulas via multiple uses of associativity, but since the order of the subformulas change, you'll also need to use commutativity. Regardless, going from either of the earlier formulas to the third would involve multiple steps and equivalences other than associativity, so it doesn't make sense to call it an application of associativity.

  • $\begingroup$ Every equivalence implies a substitutability property. $\endgroup$ Sep 22 '19 at 23:56
  • $\begingroup$ Hmm okay, so how could I prove this correctly? $\endgroup$
    – Evan
    Sep 22 '19 at 23:57
  • $\begingroup$ @DougSpoonwood Yes, this is a (meta-)theorem though sometimes equivalence is defined as a congruence. You still need to cite it in a complete proof. It is rarely cited in informal proofs though. $\endgroup$ Sep 23 '19 at 0:12
  • 1
    $\begingroup$ @Evan Do it step by step. Associativity of $\lor$ says $(A\lor B)\lor C\equiv A\lor(B\lor C)$ for given formulas $A$, $B$, and $C$. Similarly for commutativity. At each step, say which equivalence you're using and what subformulas you substituting into the equivalence. In your example, it's straightforward to see that there is no choice of formulas $A$, $B$, and $C$ such that one side of the resulting equivalence is your third formula and the other is one of the earlier formulas (or some corresponding subformulas of each). $\endgroup$ Sep 23 '19 at 0:18
  • $\begingroup$ Okay, makes sense, thanks! $\endgroup$
    – Evan
    Sep 23 '19 at 1:09

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.