0
$\begingroup$

I am reading: How to prove it, A structured approach by Daniel J.Velleman and despite it being a book based on both maths and computer science all logic statements seems to be in the "maths logic" notation like so: $$\lor, \land, \lnot$$ However in all my computer science classes we used "computing logic" notation like so: $$+,\cdot,\overline{A}$$ There is no explanation of when, and which, of these notations are to be used in different scenarios in the book. I personally prefer the "maths logic notation" and my best guess is that the reason it seems to be used more is that it is less ambiguous as it uses its own symbols. If this is the case is there any real reason for the "computing logic notation" to be used, or is it just used due to tradition?

Also as a side note my book stated that in maths $or$ is considered to be iclusive is there therefore a separate sign for exclusive $or$ much like $\oplus$ in computing notation?

$\endgroup$
  • 1
    $\begingroup$ $\veebar$ is used for xor sometimes, IIRC. $\endgroup$ – Chappers Jun 23 '17 at 23:42
  • 1
    $\begingroup$ Sonnym Yes you are correct. in math, (and in logic), "or" is taken to be the inclusive or, just like + is in computing logic. In logic, instead of seeing $\oplus$ (used extensively in computer/boolean logic), we usually simply define the exclusive "or" explicitly: $p\oplus q \equiv$ $$(p \lor q) \land \lnot (p \land q)$$ $\endgroup$ – Namaste Jun 23 '17 at 23:46
  • 1
    $\begingroup$ In general: $a+b$ corresponds to $a\lor b$, $a \cdot b = ab$ corresponds to $a \land b$, $\bar{A} = A' = \lnot A$. $\endgroup$ – Namaste Jun 23 '17 at 23:51
  • 1
    $\begingroup$ It really splits off in terms of strict boolean logic, and the logic used in math and in logic. The equivalences remain, but used for different purposes. I know best from the math/logic perspective. Similarly, in boolean logic, true is represented by $1$ and false by $0$, whereas in logic and math, we are more likely to use true, T, for true, and F or false, for false. $\endgroup$ – Namaste Jun 23 '17 at 23:56
  • 3
    $\begingroup$ Computer science is a big field. Most CS papers I read don't use your "computing logic" notation. Admittedly, I'm primarily interested in programming language theory which is closely related to type theory and mathematical logic. Even then there's a smörgåsbord of notations. Similarly mathematical logic has a smörgåsbord on notations including ones similar to your "computing logic" notation. It's simply not the case that logic notation is standardized even within a subfield. $\endgroup$ – Derek Elkins Jun 24 '17 at 0:05
1
$\begingroup$

If you observe, the computer science notation is similar to regular algebra notation: addition signs and multiplication signs. It becomes convenient to use when 'or' doesn't really represent a logical 'or' but a bitwise 'or', sometimes just called 'addition' (without carries):

  10010101
+ 00100101
= 10110101

'Multiplication' a.k.a. 'and' works similarly. The main difference is that the computer science notation is used more often in the context of performing this special type of arithmetic, or dealing with Boolean algebra expressions like $AB + \bar{A}C$, because it is easier to think of them that way. (E.g. There are digital circuits called 'adders'.)

The mathematical notation of $\land$, $\lor$, $\lnot$ is used exclusively for logical statements like $P(x) \land \lnot(Q(x) \lor R(x))$. I have almost never seen something like $10010101 \lor 00100101$ and it would be unintuitive to write it that way.

This duality is quite interesting when you notice that the two notations are actually talking about the same thing!

$\endgroup$
  • 1
    $\begingroup$ I've pretty much universally seen $\wedge, \vee, \lnot$ used as the operations in a Boolean algebra, which would include examples such as bit strings of a certain length. $\endgroup$ – Daniel Schepler Jun 24 '17 at 0:10
  • $\begingroup$ @DanielSchepler Perhaps that is because I have only dealt with Boolean algebra in a digital electronics context, where it is almost always written like my example. $\endgroup$ – shardulc Jun 24 '17 at 0:15
  • $\begingroup$ Again, dear @DanielSchepler this is a question about logic notation, not of boolean algebra. $\endgroup$ – Namaste Jun 24 '17 at 0:43
  • 1
    $\begingroup$ It really comes down to one thing : Where are the $\lor, \land, \lnot$ keys on your computer keyboard? (v,^ don't cut it.) Information Technology text authors just prefer easily typeable notations over ASC][ or markup text. $\endgroup$ – Graham Kemp Jun 24 '17 at 7:28
  • $\begingroup$ It also helps to know how computer languages deal with it. For example, the C family uses &, |, ^, ! for .and., .or., .xor., .not. (with variations for bitwise vs. boolean). $\endgroup$ – amI Jun 13 '18 at 23: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.