SashaMercuryPS. Уже прошёл день. Неужели ни у кого нет мыслей ? Это ведь интересно !

эммм. нет :) Это не интересно. Сорри :)

Не... возможно это интересно конечно, но в данном случае теорема настолько вырвана из контекста, что мне например не понятно о чём речь.

1. "отображающая слова в слова" - не понятен термин "отображающая"
2. "когда каждый бит результата зависит только от битов исходных операндов в той же позиции и правее нее." - это математика... какой класс не помню )) второй наверное :). Мы складываем и отнимаем числа справа-налево (от меньшего разряда к большему). операция же побитового отрицания вообще считается бит в бит (ну то есть на значение определённого бита влияет только бит операнда в той же позиции).


Потому даже не знаю :) Это не теорема... это просто правило счёта. Аксиома... Если бы наша система счёта была другой, она могла бы предусматривать совсем другие правила (например возьмём римские числа... к ним почти ни одно правило греческого счёта не применимо)

SashaMercury...

Не уверен что это аксиома, да и автор говорит о том что доказательство существует. Видимо нужно копать либо в теории чисел, либо в булевой алгебре

Так, с определением скудненько конечно, но разобрались. отображение - это применение (вычисление) некой функции к заданному значению (аргументу).

по поводу теоремы. Как я говорил всё зависит от системы счёта (точнее от системы записи числа). А давайте записывать числа справа-налево (то есть меньший разряд находится левее... как например числа представлены у интеловцов (intel) в оперативке).
Теперь Ваша теорема побитового сложения и вычитания работает? )) Нет... потому что теперь бит зависит наоборот от битов находящихся левее данного :).

Потому это не теорема... это просто правило ведения счёта и записи чисел (слева-направо)... изменения этих правил рушит данную "теорему". Потому это аксиома (общепринятое правило, определение).

SashaMercuryУорренТеорема. Функция, отображающая слова в слова, может быть реализована посредством операций побитового сложения, вычитания, и, или, отрицания тогда и только тогда, когда каждый бит результата зависит только от битов исходных операндов в той же позиции и правее нее.

У нас есть некий оператор над байтом. Мы "действуем оператором P" на слово x, ( в математике пишут Px). Неизвестно как именно мы подействовали. Ну вот вам пример:
x-старый байт
y-получившийся байт
оператор P:
y0=x0;
y1=x0&x1;
y2=x0&x1&x2;
.
.
.
y7=x0&x1&x2...&x7.

Обратите внимание, при получении каждого бита y c индексом j, мы используем только байты x с индексами i<=j.
Согласно теореме, я могу представить оператор P в виде комбинации операций побитового сложения, и, или, отрицания. Подумаю завтра какая формула будет для этого случая.



Теперь, пусть некий оператор K, будет задан таким образом:
y0=x0;
y1=x0&x7;
...
y7=x7;

Как вы заметили, второй бит байта y, считается через 8 бит байта x. Это противоречит условию теоремы, и потому оператор K, мы не сможем записать в виде комбинаций побитового сложения, и, или, отрицания.


Согласен с вами, Дмитрий, формулировка не совсем хорошая, на мой взгляд.

Програмёр, мне понятно почему вы настаиваете на том, что это аксиома.
Возможно, вы поняли теоремутак:
Над байтом можно делать операций побитовой суммы, разности, побитовых и, или, не, в том случае, когда каждый бит результата зависит от предыдущих.
это неправильно, смысл, с большой долей вероятности другой. А именно, как я описал выше

Я ни в коем случае не настаиваю. Даже больше, я изначально признался что не совсем понимаю что именно означает данная формулировка. В моём понимании, это просто констатация факта, что мы не можем выразить число с помощью комбинации функций суммы, разницы или побитовых логических операций, в случае если на значение какого либо бита результата влияет бит операнда стоящий на "высшей" позиции.

Это вполне логично... но математическому обоснованию (я так думаю по крайней мере) не подлежит. На уровне восприятия это объясняется тем, что мы при вычислении простых математических и логических операций (кроме умножения и деления, которые, кстати, тут не вспоминаются по указанным причинам) переносим десятки, а не десятые... потому каждый разряд операнда может влиять на тот же разряд результата, или же на более значимые (стоящие левее).


А вообще, в читаемой Вами книжке изложены какие-то теоремы, заставляющие Вас задуматься об их обоснованности, при чём я не вижу для них явного практического применения. А Вы? Просто если и Вы не видите, так зачем тогда на таких "теоремах" зацикливаться? Даже больше... я бы задумался о правильности выбора книги :)

P.S. Под "слово" в данном случае подразумевается беззнаковое число (ну то есть аналог word в asm?). Просто только в этом случае представленное в первом посте умозаключение будет верным.... Иначе же, как только числа становятся знаковыми (signed), есть большая разница в операциях 0x0001+0x0001 и 0x0001+0x1001.

Ещё раз повторю, практическое применение теоремы спорно, и учитывая что чаще приходится работать со знаковыми величинами, данная теорема может ввести в заблуждение.