Associative laws with negation

Question

Is it possible to simplify a statement like the one below with the associative law despite the negation? I can't seem to find a law that outlines this. The associative law is the closest I could find.

\begin{align} \ (\lnot p \land \lnot q) \ \lor \ q \end{align}

If the above is possible, is it also possible if only one variable in the brackets were to be negated like the below?

\begin{align} \ (p \land \lnot s) \ \lor \ s \end{align}

Thanks.

Answer 1

Associative low holds only when three formulas are put together by two occurrences of the same connective $\land$ or $\lor$. For instance:

\begin{align} (\lnot p \land \lnot q) \land q &\equiv \lnot p \land (\lnot q \land q) &&\text{or} & (\lnot p \lor \lnot q) \lor q &\equiv \lnot p \lor (\lnot q \lor q) \end{align}

So, you cannot use associative law in your formula $(\lnot p \land \lnot q) \lor q$. Indeed, you can easily check that the the truth table of your formula $(\lnot p \land \lnot q) \lor q$ is different from the one of $\lnot p \land (\lnot q \lor q)$.

However, you can simplify your formula $(\lnot p \land \lnot q) \lor q$, but using other logical equivalences instead of associative law (I refer to the ones listed here): \begin{align} (\lnot p \land \lnot q) \lor q &\equiv (\lnot p \lor q) \land (\lnot q \lor q) &&\text{distributivity} \\ &\equiv \lnot p \lor q &&\text{identity} \end{align} where in the last equivalence the identity law can be applied since $\lnot q \lor q$ is a tautology (i.e. it is true under any valuation).

Note that in the simplification above the fact that there is a negation $\lnot$ in front of $p$ does not play any role, so you can simplify in the same way also your second formula: \begin{align} (p \land \lnot s) \lor s &\equiv (p \lor s) \land (\lnot s \lor s) &&\text{distributivity} \\ &\equiv p \lor s &&\text{identity.} \end{align}

Answer 2

When applying the rules, the negation play no role.

Your expression is

$$(a\land b)\lor c,$$ and can be rewritten

$$(a\lor c)\land(b\lor c)$$ by virtue of distributivity (not associativity).

Now plugging the actual arguments,

$$(\lnot p\land \lnot q)\lor q=(\lnot p\lor q)\land(\lnot q\lor q)$$ which can be simplified.

You second expression can be handled the same way.

Answer 3

This is such a common pattern that it has its own name:

Reduction

$$p \land (\neg p \lor q) \Leftrightarrow p \land q$$

(together with all its variants, like $\neg p \land (p \lor q) \Leftrightarrow \neg p \land q$; $(\neg p \lor q) \land p \Leftrightarrow q \land p$; and its dual $p \lor (\neg p \land q) \Leftrightarrow p \lor q$ )

Note that in all cases the $q$ can be any statement, so yes, sure, that can be a negation

The equivalence can also be seen as a specific instance of Resolution