Переключательные функции

Для n - логических переменных (аргументов) существует 2n их комбинаций или двоичных наборов. На каждом таком наборе может быть определено значение функции 0 или 1. Если значения функции отличаются хотя бы на одном наборе, функции - разные. Общее число переключательных функций (ПФ) от n аргументов равно N=22n. Для n=2, N=16. При n=3, N=256 и далее очень быстро растет. Практическое значение имеют 16 функций от 2-х переменных, т.к. любое сложное выражение можно рассматривать как композицию из простейших. В таблице 1 приведены некоторые из ПФ для n=2. i-номер набора входных переменных x1 и x0.

ЗАПОМНИТЕ СЛЕДУЮЩИЕ ОПРЕДЕЛЕНИЯ. Функция "И" равна единице, если равны единице ВСЕ ее аргументы. Функция "ИЛИ" равна единице, если равен единице ХОТЯ БЫ один аргумент. Функция "ИСКЛЮЧАЮЩЕЕ ИЛИ" (XOR) равна единице, если равен единице ТОЛЬКО один ее аргумент.

38. Зависимость числа различных переключательных функций от числа переменных. Основные законы алгебры логики.

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

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

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

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

По сравнению с аналитической функцией непрерывного аргумента даже для одного аргумента существует множество различных функций.

Число аргументов: 1 2 3 4 5 10

Число различных перекл. ф-ций: 4 16 256 65536 ~4*109 ~10300

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