Число функций n аргументов?

[Gamover jr]

почему число разных f(x, y) = 16 а не 8 ?

x y f
1 1 1
1 1 0

1 0 1
1 0 0

0 1 1
0 1 0

0 0 1
0 0 0

Какие тут ещё варианты?

[BlackEric]

Вопрос не ясен, если честно :)

Что за функция то хоть? Или это таблица истинности булевых функций? Тогда возможно вы забыли функции NOT,XOR

[Gamover jr]

Сколько разных функций может быть с n аргументов.
Теория говорит 2^2^n, если n=2 , тогда 16 разных функций.
каждый аргумент может принимать значения 1 или 0, и фунция для каждой комбинации значений аргументов может принимат значение 1 или 0. Вот у меня и получается 8 разных функций, которые я перечислил.
Откуда ещё 8?

[BlackEric]

y=x^2+a - сколько у нее может быть значений? Бесконечность.
Про такую теорию слышу 1 раз. Где вы ее нашли?

[Gamover jr]

http://www.intuit.ru/department/hardware/archsys/2/2.html:

Очевидно, что количество различных X1,X2,...........Xn n-разрядных чисел в позиционной двоичной системе есть 2n.

Допустим, что некоторая функция F(X1,X2,....Xn) задана на этих наборах и на каждом из них она принимает либо '0'-ое, либо '1'-ое значение.

Такую функцию называют функцией алгебры логики или переключательной функцией.

Чему равно число различных переключательных функций 'n' аргументов?

Т.к. функция на каждом наборе может принять значение '0' или '1', а всего различных наборов 2^n, то общее число различных функций 'n' аргументов есть: 2^2^n.


или "art of assembly language" ch2:

If you fix the number of input variables,
there are a finite number of unique boolean functions possible. For example, there
are only 16 unique boolean functions with two inputs

[BlackEric]

1. a+b
2. a-b
3. a*b
4. a/b
5. a xor b
6. a or b
7. a and b
8. not a
9. (not a)+b
10.(not a)-b
11.(not a)*b
12.(not a)/b
13.(not a) xor b
14.(not a) or b
15.(not a) and b
16.(not a) not b
Возможно так, но я не уверен.

[ivank]

BlackEric, не существует "битовой" операции деления, так же как и битовый + это то же самое, что xor. А функция not имеет 1 аргумент, а не 2. В общем, неправильная таблица. И вообще, тут разговор про функции алгебры логики, а не произвольной алгебры.

Gamover jr
Во-первых, вы перечислили в первом посте совсем не 8 функций. В принципе, в процитированном вами отрезке вся теория есть. Могу просто привести небольшой пример "совсем на пальцах" для облегчения понимания.
функция 1.
a b f
0 0 0
0 1 0
1 0 0
1 1 0

функция 2
a b f
0 0 1
0 1 0
1 0 0
1 1 0

функция 3
a b f
0 0 0
0 1 1
1 0 0
0 0 0

и так далее до функции 15
a b f
0 0 1
0 1 1
1 0 1
1 1 1

Функцию можно задать просто перечислив все её значения на всех возможных входных аргументах, в определённом порядке. (например 00, 01, 10, 11). Тогда функция (от 2х аргументов) характеризуется последовательностью из 4-х чисел. В моём примере f1=0000, f2=0100, f16=1111. Очевидно, что таких последовательностей может быть 2^4=16.

Далее, общим на функцию n аргументов. У неё может быть 2^n различных наборов на входе. Значит она характеризуется 2^n "выходами". Если в двух последовательностях хотя бы один выход отличается, то это уже разные функции. Соответственно вариантов выходных последовательностей 2^(длина последовательности) = 2^2^n.

[BlackEric]

ivank, вы правы. А я ошибся. Сорри...

[ivank]

со мной можно на ты :)

[Coutty]

Я-то уж подумал, что мировоззрение должно порушиться. Ан нет=) Спасибо за разъяснения;)

[kim-aa]

BlackEric,
Ищем "прикладная теория цифровых автоматов"
выбираем книжку какая глянется, сдуваем пыль (издавались где-то с конца семидесятых по конец восьмидесятых) - и в бой.

[ivank]

kim-aa, зачем так сложно?
Курс алгебры логики входит в любой приличный курс образования математиков и/или инженеров-схемотехников. Причём входит до сих пор, ибо одна из фундаментальных дисциплин (без неё нельзя переходить к дискретной математике вообще, так же как и к проектированию цифровых устройств).

[Coutty]

без неё нельзя переходить к дискретной математике вообще »
Подумать только! Нам сначала дискретную математику преподавали, а уж потом алгебру-логику. =(

[kim-aa]

kim-aa, зачем так сложно? »
Небыло у нас явно такого предмета. Просто он читался семестр, как часть "Основ прикладной теории цифровых автоматов" которая в свою очередь читалась три семестра.