Talk:Minimal negation operator

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Low Priority  Field: Foundations, logic, and set theory
Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.

Contents

[edit] Notes & Queries

Jon Awbrey 18:20, 20 February 2006 (UTC)

[edit] Minimal Negation Operator — Initial Draft

JA: Copied below, a very rough exposition of mno's from the talk page at boolean algebras canonically defined, to be worked up for the main page here. Jon Awbrey 01:32, 19 August 2006 (UTC)

JA: This is a critter that goes back to Leibniz, I think. In some dialects of graph theory it's called the link operator. It's a discrete analogue of the point-deleted neighborhood in calculus. I used to call it the boundary operator, because that's what it looks like in venn diagrams, and I think that there's an official name for it in co/homology theory, but I've forgotten what little I knew of that.

JA: If you are thinking of a n-cube (incubus) as your favorite graph, then each point of the cube can be represented as a conjunction of n posited or negated variables. So the all 1's node is the product of all positives x_1 x_2 … x_[n-1] x_n and the all 0's node is the product of all negatives (x_1)(x_2) … (x_[n-1])(x_n), here using parentheses for negation a la Peirce. These are called singular propositions (or singular boolean functions) because the fibre of truth under such a function is a single point of the cube. To be continued … Jon Awbrey 17:08, 17 August 2006 (UTC)

JA: Let's say that p is a product of literals, that is, a conjunction of posited or negated basis elements. Then p = e_1 e_2 … e_[n-1] e_n, where e_j = x_j or e_j = (x_j) = ¬x_j, for each j = 1 to n. Then the fibre of 1 under p, that is, (p^(-1))(1) is a single node of the n-cube.

JA: Given p as above, and representing the boundary operator or minimal negation operator (mno) of rank n by a bracket of the form "( , …, )", the proposition (e_1, e_2, …, e_[n-1], e_n) is true on the nodes adjacent to the node where p is true, and false everywhere else on the cube. Jon Awbrey 19:00, 17 August 2006 (UTC)

JA: For example, let's take the case where n = 3. Then the minimal negation opus \nu (p, q, r)\!, which we will eventually get so lax as to write "(p, q, r)" when there is minimal risk of misinterpretation, has the following venn diagram:

o-------------------------------------------------o
|                                                 |
|                                                 |
|                 o-------------o                 |
|                /               \                |
|               /                 \               |
|              /                   \              |
|             /                     \             |
|            o                       o            |
|            |           P           |            |
|            |                       |            |
|            |                       |            |
|        o---o---------o   o---------o---o        |
|       /     \`````````\ /`````````/     \       |
|      /       \`````````o`````````/       \      |
|     /         \```````/ \```````/         \     |
|    /           \`````/   \`````/           \    |
|   o             o---o-----o---o             o   |
|   |                 |`````|                 |   |
|   |                 |`````|                 |   |
|   |        Q        |`````|        R        |   |
|   o                 o`````o                 o   |
|    \                 \```/                 /    |
|     \                 \`/                 /     |
|      \                 o                 /      |
|       \               / \               /       |
|        o-------------o   o-------------o        |
|                                                 |
|                                                 |
o-------------------------------------------------o
Figure 1.  (p, q, r)

JA: Back in a flash ... Jon Awbrey 13:18, 18 August 2006 (UTC)

JA: (Some flashes are slower than others.) For a contrasting example, consider the boolean function expressed by the form ((p),(q),(r))\!, whose venn diagram is as follows:

o-------------------------------------------------o
|                                                 |
|                                                 |
|                 o-------------o                 |
|                /```````````````\                |
|               /`````````````````\               |
|              /```````````````````\              |
|             /`````````````````````\             |
|            o```````````````````````o            |
|            |`````````` P ``````````|            |
|            |```````````````````````|            |
|            |```````````````````````|            |
|        o---o---------o```o---------o---o        |
|       /`````\         \`/         /`````\       |
|      /```````\         o         /```````\      |
|     /`````````\       / \       /`````````\     |
|    /```````````\     /   \     /```````````\    |
|   o`````````````o---o-----o---o`````````````o   |
|   |`````````````````|     |`````````````````|   |
|   |`````````````````|     |`````````````````|   |
|   |``````` Q ```````|     |``````` R ```````|   |
|   o`````````````````o     o`````````````````o   |
|    \`````````````````\   /`````````````````/    |
|     \`````````````````\ /`````````````````/     |
|      \`````````````````o`````````````````/      |
|       \```````````````/ \```````````````/       |
|        o-------------o   o-------------o        |
|                                                 |
|                                                 |
o-------------------------------------------------o
Figure 2.  ((p),(q),(r))

JA: TGIF !!! Jon Awbrey 21:32, 18 August 2006 (UTC)

[edit] Minimal Negation Operator — Working Draft

If you are thinking of a n-cube as your favorite graph, then each point of the cube can be represented as the unique point where a conjunction of n posited or negated variables is true. So the point whose coordinates are all 1 is the unique point where the product of all posited variables x_1\ x_2\ \ldots\ x_{n-1}\ x_n is 1, and the point whose coordinates are all 0 is the unique point where the the product of all negated variables (x_1)(x_2)\ldots(x_{n-1})(x_n) is 1, here using parentheses for negation a la Peirce. These are called singular propositions (or singular boolean functions) because the fiber of 1 under such a function is a single point of the cube.

Let's say that the proposition p is a product of literals, that is, a conjunction of posited or negated basis elements. Then p = e_1\ e_2\ \ldots\ e_{n-1}\ e_n, where e_j = x_j\! or e_j = (x_j) = \lnot x_j, for each j = 1 to n. Then the fiber of 1 under p, that is, p − 1(1) is a single point of the n-cube.

Given p as above, and representing the boundary operator or minimal negation operator of rank n by a bracket of the form (\ ,\ \ldots ,\ ), the proposition (e_1,\ e_2,\ \ldots,\ e_{n-1},\ e_n) is true on the nodes adjacent to the node where p is true, and false everywhere else on the cube.

For example, let's take the case where n = 3. Then the minimal negation opus \nu (p, q, r)\!, which we will eventually get so lax as to write "(p, q, r)\!" when there is minimal risk of misinterpretation, has the following venn diagram:

o-------------------------------------------------o
|                                                 |
|                                                 |
|                 o-------------o                 |
|                /               \                |
|               /                 \               |
|              /                   \              |
|             /                     \             |
|            o                       o            |
|            |           P           |            |
|            |                       |            |
|            |                       |            |
|        o---o---------o   o---------o---o        |
|       /     \`````````\ /`````````/     \       |
|      /       \`````````o`````````/       \      |
|     /         \```````/ \```````/         \     |
|    /           \`````/   \`````/           \    |
|   o             o---o-----o---o             o   |
|   |                 |`````|                 |   |
|   |                 |`````|                 |   |
|   |        Q        |`````|        R        |   |
|   o                 o`````o                 o   |
|    \                 \```/                 /    |
|     \                 \`/                 /     |
|      \                 o                 /      |
|       \               / \               /       |
|        o-------------o   o-------------o        |
|                                                 |
|                                                 |
o-------------------------------------------------o
Figure 1.  (p, q, r)

For a contrasting example, consider the boolean function expressed by the form ((p),(q),(r))\!, whose venn diagram is as follows:

o-------------------------------------------------o
|                                                 |
|                                                 |
|                 o-------------o                 |
|                /```````````````\                |
|               /`````````````````\               |
|              /```````````````````\              |
|             /`````````````````````\             |
|            o```````````````````````o            |
|            |`````````` P ``````````|            |
|            |```````````````````````|            |
|            |```````````````````````|            |
|        o---o---------o```o---------o---o        |
|       /`````\         \`/         /`````\       |
|      /```````\         o         /```````\      |
|     /`````````\       / \       /`````````\     |
|    /```````````\     /   \     /```````````\    |
|   o`````````````o---o-----o---o`````````````o   |
|   |`````````````````|     |`````````````````|   |
|   |`````````````````|     |`````````````````|   |
|   |``````` Q ```````|     |``````` R ```````|   |
|   o`````````````````o     o`````````````````o   |
|    \`````````````````\   /`````````````````/    |
|     \`````````````````\ /`````````````````/     |
|      \`````````````````o`````````````````/      |
|       \```````````````/ \```````````````/       |
|        o-------------o   o-------------o        |
|                                                 |
|                                                 |
o-------------------------------------------------o
Figure 2.  ((p),(q),(r))

[edit] Venn Diagrams

JA: Pretty nifty !!! Jon Awbrey 18:08, 22 August 2006 (UTC)

[edit] New pix

Enjoy the new pix. The ASCII versions probably took as long to make as the pretty ones, which were done with SVG. Unfortunately, the current Wikipedia rendering (using rsvg) is seriously deficient (W3C validation, ASV, Batik, and Inkscape all work fine), so I have also uploaded PNG renderings to use in the article for now.

Compare bad rendering

(p,q,r)
(p,q,r)
((p),(q),(r))
((p),(q),(r))


with good rendering.

(p,q,r)
(p,q,r)
((p),(q),(r))
((p),(q),(r))


Since SVG files are plain text files, and since I created these by typing rather than WYSIWYG, it should be easy to modify them for other uses. --KSmrqT 18:27, 22 August 2006 (UTC)

JA: I'll really have to learn how to do these. I used to do a lot of graphics in my Macintosh days, but when various factors beyond my control turned me out of that garden, the early Windows graphics tools were so primitive that I gave up on graphics altogther. At any rate, I was just thinking that it might be nice to have side-by-side pix of the venn diagrams and the node-painted cubes for the same props or functions. Jon Awbrey 06:08, 24 August 2006 (UTC)