3
$\begingroup$

For instance,

Is $\neg (((p \land q) \lor r) \land s)$ equivalent to $((\neg p \lor \neg q) \land \neg r) \lor \neg s$?

  • 0
    I think you can factorize it in the brackets first, and use the easy DeMorgan's Law a few times.2012-04-28
  • 3
    $p\land q\lor r\land s$ is ambiguous. Does it mean $(p\land q)\lor(r\land s)$, or does it mean $((p\land q)\lor r)\land s$, or some other combination? (Note the two are not equivalent; $(p\land q)\lor (r\land s)$ is true if $p$ and $q$ are true and $r$ and $s$ are false, but $((p\land q)\lor r)\land s$ is false if $s$ is false). Express it clearly first, and figure out which connective is at the "top level".2012-04-28
  • 0
    In short: what precedence rules are you using?2012-04-28
  • 2
    @JohnHoffman: With the parenthesization that I *think* you had in mind, your calculation is correct. However, the reader should not be put into the position of having to guess where the missing parentheses are intended to be, unless there are long-established conventions.2012-04-28
  • 0
    Without brackets it may mean that it follows the order of your typing? At least Maple would take this~lol~2012-04-28
  • 0
    Thanks - sorry, I should have clarified.2012-04-28
  • 0
    @JohnHoffman: The calculation is correct. Amusingly, your choice of parentheses is not the one that I thought you intended, and under my previous guess, the calculation was also correct, though the truth tables of the expressions were different. An interesting invariance principle! But easily explained by duality.2012-04-28
  • 2
    The short answer: Yes, you can use DeMorgan's law to expand a long sequence; this is easy to verify if they are all $\land$s or all $\lor$s. For other combinations, you have to be a bit careful on how you associate on either side (making sure the associations are compatible).2012-04-28

1 Answers 1

0

Yes. I think you could prove this by induction. You might also note that once your fully parenthesize the intended formula, if you do things step by step, the negation moves to the parentheses first if any exist, and then moves to the letters and switches just one operation from AND to OR or the other way around. You could also note that negation consists of an isomorphism between ({T, F}, AND) and ({T, F}, AND') where " AND' " indicates OR, which implies that as long as you switch all values for the variables accordingly, and switch the first operation with its correlate OR, any given formula will behave exactly the same once the first operation has gotten rewritten as the second. Negation ensures that you've switched all values accordingly, so you can use De Morgan's laws this way.