1
$\begingroup$

there is some kind of priorities for the elements in propositional logic ?

for example : p ∧¬q → r , given this ,we there may be two options

(p ∧¬q) → r OR p ∧ (¬q → r) , which one is the correct ?

$\endgroup$
  • 2
    $\begingroup$ Note how you are missing an alternative: p ∧ (¬(q → r)) $\endgroup$ – Raphael Jun 23 '15 at 12:35
5
$\begingroup$

If you look at formal definitions of the syntax of propositional logic, you will find that

$\qquad p \land \lnot q \to r$

is not a proper sentence; parentheses are needed to avoid exactly the ambiguity you mention.

Operator precedences can be used for implicit parenthesisation. You seem to be asking if there are agreed-upon operator precedences in logic.

I don't think formal logics contains this concept; formal grammars just do not lend themselves to model precedences (or any ambiguity) very well. In practice (by which I mean both blackboard writing and implemented logic parsers), we do use precedences; usual conventions include

  1. $\lnot$,
  2. $\land$,
  3. $\lor$,
  4. $\implies$,
  5. $\iff$

in decreasing order of precedence. Using these, your example is equivalent to

$\qquad (p \land (\lnot q)) \to r$.

David's warning is apt, though: if you want to be clear, don't rely on implicit precedences. Typesetting can help -- you can e.g. group terms with spacings -- but in case of doubt, just put the parentheses. In a larger body of work, you can also state your convention once and safe symbols afterwards, provided you stick to your own rules.

$\endgroup$
  • 1
    $\begingroup$ *pokes Raphael with a stick* $\endgroup$ – David Richerby Jun 23 '15 at 12:37
3
$\begingroup$

It seems to be conventional that $\neg$ binds to the object immediately following it, so $\neg A \land B$ means $(\neg A) \land B$, rather than $\neg(A \land B)$.

Beyond that, the safest option is to treat all other operators as having equal precedence and use enough parentheses to force the reading you intend. In the past, authors frequently asserted or assumed precedence rules because syntax was seen as being more interesting in and of itself. However, such rules are rather arbitrary. For example, one might assert that $\land$ is multiplication modulo 2 and $\lor$ is addition modulo 2 so $\land$ should have higher precedence. But this doesn't help much because $\land$ and $\lor$ have different distributivity properties to $\times$ and $+$, at least in the non-modular setting that we're used to.

Nowadays, except for negation, it seems more common to just disambiguate by bracketing. If you see a modern author asserting or, worse, assuming precedence rules, I suggest poking them with a stick until they stop.

$\endgroup$
  • $\begingroup$ While your last sentence holds humorous value, I have to ask: really? Do you put all the brackets when nesting quantifiers? I'd never assume precedences between $\land$ and $\lor$, or $\implies$ and $\iff$, but I think the basic order of 1. $\lnot$ 2. $\land,\lor$ and 3. $\implies, \iff$ is universally used (without parens). $\endgroup$ – Raphael Jun 23 '15 at 12:37
  • $\begingroup$ "I'd never assume precedences between ∧ and ∨" But your answer does exactly that. No, I wouldn't bracket when nesting quantifiers: I'd assume left-to-right reading. But I would write either $(\forall x\,A)\land B$ or $\forall x\,(A\land B)$. (Technically, the question is about propositional logic so there aren't any quantifiers anyway.) $\endgroup$ – David Richerby Jun 23 '15 at 12:40
  • $\begingroup$ I reference Wikipedia; I make not statement about my personal preferences. Should I? $\endgroup$ – Raphael Jun 23 '15 at 12:41
  • $\begingroup$ By the way, your left-right-reading argument (with all its faults) can be used to argue for a left-associative convention of reading logics. I don't think we want that? Also, $\lnot$ before $\land$ before $\lor$ is just carrying over (unary) $-$ before $\cdot$ before $+$ from arithmetics, and that one we all use. $\endgroup$ – Raphael Jun 23 '15 at 13:17
  • 2
    $\begingroup$ I'm arguing that we don't need brackets for quantifiers because $\forall x \exists y \exists z\, \varphi$ can only mean $\forall x\,(\exists y\,(\exists z\,\varphi))$. Likewise, there's no need to bracket, e.g., $A\lor B\lor C$ because $\lor$ commutes. But, for other cases (e.g., a mix of different operators), it's clearer to use parentheses (or, sometimes, whitespace) than precedence rules. I'd much rather read $A\land (B\lor C)$ or $A\;\land\;B\lor C$ than have to remember somebody's rules for parsing $A\land B\lor C$. $\endgroup$ – David Richerby Jun 23 '15 at 13:46

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.