Булева функция может быть представлена суперпозицией (совокупности) некоторого набора функций {f1, f2, ... fn}.
Система элементарных логических функций f1 … fm называется полной, если любую ФАЛ можно изобразить в виде суперпозиции функций f1 . . . fn.
Теорема. Пусть даны две системы логических функций:
$$F={f_{1}, f_{2},…,f_{n}}$$и
$$G={g_{1}, g_{2},…,g_{n}}$$Если система (4.1) полна и каждая её функция может быть выражена как суперпозиция функций системы (4.2), тогда система (4.2) является полной.
Пример 4.1. Известно, система функций {И, ИЛИ, НЕ} является функционально полной (например, именно в этой системе логических функций можно представить её совершенные дизъюнктивную и конъюнктивную нормальные формы СДНФ, СКНФ). Отсюда следует, что система ФАЛ, состоящая из одной функции "Штрих Шеффера", также функционально полна, так как:
$$\overline{x} = x / x$$ $$x \vee y =\overline{\overline{ x \vee y}}=\overline{\overline{x} \And \overline{y}}=(x/x)/(y/y)$$ $$x \And y = \overline{\overline{x \And y}}=(x/x)/(y/y)$$Правила перехода от представления ФАЛ в виде ДНФ к функции, представленной в базисе "Штрих Шеффера"
Правила перехода от представления ФАЛ в виде КНФ к функции, представленной в базисе "Стрелка Пирса"
Рассмотрим основные свойства логических функций, которые позволят определить их состав, составляющий функционально полный набор.
Переключательной (логической) функцией, сохраняющей нуль, называется функция, которая на нулевом наборе аргументов, т.е. на наборе (0,0, ..., 0,0), равна нулю. Для переключательных функций, сохраняющих нуль, выполняется условие: f( 0,0, ..., 0,0 ) = 0.
Очевидно, что логических функций от n аргументов, сохраняющих ноль, будет ровно половина от всех возможных функций, то есть $$2^{2^{n-1}}$$.
Переключательной функцией, сохраняющей единицу, называется функция, которая на единичном наборе аргументов, т.е. на наборе (1,1, ..., 1,1), равна единице. Для переключательных функций, сохраняющих единицу, выполняется условие:f (1,1, ..., 1,1) = 1. Функций, обладающих этим свойством, будет также ровно половина:$$2^{2^{n-1}}$$.
К одному из основных свойств логической функции относится ее принадлежность к классу самодвойственных функций. Чтобы рассмотреть это свойство разберем вначале несколько сопутствующих понятий.
Два набора аргументов называются противоположными, если все значения аргументов одного набора противоположны значениям аргументов другого набора. Чтобы получить противоположный набор, достаточно заменить в данном наборе нули единицами, а единицы нулями.
Для функции трех аргументов следующие пары наборов являются противоположными:
000 и 111; 001 и 110; 010 и 101; 011 и 100.
В общем виде два противоположных набора записываются в виде (x1, x2, ..., xn) и ($$\overline{x_{1}}, \overline{x_{2}}, ..., \overline{x_{n}).$$
Переключательная функция n переменных f* (x1, x2, ..., xn) называется двойственной к функции f(x1, x2, ..., xn) , если имеет место равенство:
$$f^{*}(x_{1}, x_{2},. . . , x_{n}) = \overline{f}(\overline{x_{1}},\overline{x_{2}},. . ., \overline{x_{n}})$$Например, для функции дизъюнкции f (x1, x2) = x1 v x2 двойственной будет функция конъюнкции f* (x1, x2) = x1 x2.
Переключательная функция называется самодвойственной, если на каждой паре противоположных наборов она принимает противоположные значения, т. е. если выполняется условие:
$$f(x_{1}, x_{2},. . . , x_{n}) = f^{*}(x_{1},x_{2}, . . . , x_{n}) = \overline{f}(\overline{x_{1}},\overline{x_{2}}, . . . , \overline{x_{n}})$$Пример самодвойственной функции: F(x1,x2,x3) = ∑(1,2,3,7)
| Набор | x1 | x2 | x3 | F(x1,x2,x3) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 | 0 |
| 6 | 1 | 1 | 0 | 0 |
| 7 | 1 | 1 | 1 | 1 |
При определении свойства монотонности переключательной функции используется понятие сравнимости двух наборов аргументов.
Примем условие, что 0 < 1 (на самом деле, для логической функции корректнее было бы писать: false < true, но это смотрится у совсем несерьезно и в свете дальнейших рассуждений оставим все-таки исходный вариант). Два набора аргументов X = (x1, x2, ..., xn) и Z = ( z1, z2, ..., zn ) называются сравнимыми, если для всех аргументов выполняется условие xi =< zi (говорят, что X =< Z). Иными словами, если значение каждого аргумента одного набора меньше или равно значению того же аргумента второго набора, то говорят, что первый набор меньше или равен второму (не больше второго). И наоборот. Если значение каждого аргумента одного набора больше или равно значению того же аргумента второго набора, то говорят, что первый набор больше или равен второму (не меньше второго).
Например, если X = (0000) и Z = (0001), то наборы сравнимы, и X < Z.
Если же некоторые из значений аргументов первого набора больше или равны, а другие меньше значений тех же аргументов второго набора, то такие наборы называются несравнимыми.
Например, если X = (1010) и Z = (0110), то эти наборы являются несравнимыми (x1 > z1, но x2 < z2).
Переключательная функция называется монотонной, если для всех пар сравнимых наборов при любом возрастании набора значение этой функции не убывает, т.е. сохраняет свое значение или изменяется с 0 на 1. Здесь, аналогично обычной математике, можно рассматривать монотонно возрастающие и монотонно убывающие функции, но для наших дальнейших рассуждений это не будет иметь какого-либо значения.
Т.е. для монотонной логической функции должно выполняться условие: если для сравнимых наборов X =< Z , то F(X) =< F(Z).
Примеры: монотонная функция: F1(x1, x2) = x2,
немонотонная функция: $$F2(x_1, x_2) = x_1 \oplus x_2$$
x1 | x2 | F1(x1,x2) | F2(x1,x2) |
| 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Для упрощения анализа данной таблицы отметим, что наборы (0,1) и (1,0) являются несравнимыми. Поэтому значения функции для определения ее монотонности на этих наборах делать не следует.
Переключательная функция называется линейной, если она может быть представлена полиномом Жегалкина
$$f(x_1,x_2, …, x_n) = c_0 \oplus c_1 x_1 \oplus c_2 x_2 \oplus … \oplus c_n x_n$$, где
$$\oplus$$ – символ операции "сумма по mod2";
с0, с1, ..., сn – коэффициенты, равные 0 или 1.
Для того чтобы система переключательных функций была функционально полной, необходимо и достаточно, чтобы эта система включала:
Рассмотрим все функции от двух переменных f(x0, x1) с точки зрения удовлетворения ими рассмотренным выше свойствам (Табл. 4.1).
| Свойства функций двух переменных | |||||
|---|---|---|---|---|---|
| Функция | Сохранение "0" | Сохранение "1" | Самодвойственная | Монотонная | Линейная |
| $$f_0 = 0$$ | + | + | + | ||
| $$f_1 = \overline{x_{1}\vee x_{0}}$$ | |||||
| $$f_2 = \overline{x_{1}}x_{0}$$ | + | ||||
| $$f_3 = \overline{x_1}$$ | + | + | |||
| $$f_4 = x_{1}\overline{x_{0}}$$ | + | ||||
| $$f_5 = \overline{x_{0}}$$ | + | + | |||
| $$f_6 = x_1 oplus x_0$$ | + | + | |||
| $$f_7 = \overline{x_1 x_0}$$ | |||||
| $$f_8 = x_1 x_0$$ | + | + | + | ||
| $$f_9 = \overline{x_{1}\oplus x_{0}}$$ | + | + | |||
| $$f_{10} = x_0$$ | + | + | + | + | + |
| $$f_{11} = \overline{x_{1}}$$ | + | ||||
| $$f_{12} = x_1$$ | + | + | + | + | + |
| $$f_{13} = x_{1}\vee\overline{x_0}$$ | + | ||||
| $$f_{14} = x_1 \vee x_0$$ | + | + | + | ||
| $$f_{15} = 1$$ | + | + | + | ||
Мы видим, что как, собственно, и следовало ожидать, если включить в состав функционально полного набора все функции от данного числа переменных, то с его помощью мы, даже не прибегая к суперпозиции каких-либо функций, сможем выразить любую ФАЛ.
Выделение всех функционально полных наборов ФАЛ даже для функций двух переменных с относительно небольшим количеством функций является весьма трудоемкой задачей, которая может решаться либо перебором, либо какими-то эвристическими методами. А для функций от трёх переменных (общее количество таких функций$$2^{2^{3}}=256$$) это становится непосильной задачей.
На практике используются несколько наиболее известных таких наборов:
F1 = {, V , ˉ } – "И, ИЛИ, НЕ"
F2 = {/} – "штрих Шеффера"
F3 = {->} – "стрелка Пирса"
F4 = {"Сумма по mod2", "И", "Константа 1"} – "базис Жегалкина".
Как видим из Табл. 4.1, все они удовлетворяют теореме Поста – Яблонского, поэтому являются функционально полными.
На первом этапе вопрос ставится так, чтобы в функционально полный набор функций входило их ограниченное количество.
Уже на примере анализа функций, входящих в набор F1, можно сделать вывод, что данный набор является избыточным: удаление из него функции "И" или функции "ИЛИ" всё равно приводит к тому, что остающиеся две функции удовлетворяют требованиям теоремы Поста – Яблонского, а, следовательно, наборы из функций {"И", "НЕ"} и {"ИЛИ", "НЕ"} тоже функционально полны. Из этих наборов ни одну функцию убрать уже нельзя без того, чтобы они не перестали быть функционально полными.
В то же время наборы F2 и F3 состоят всего лишь из одной функции. Поэтому нет смысла их каким-либо образом сокращать.
В связи с этим помимо понятия "функционально полный набор логических функций" используется также понятие "логический базис".
Второй этап призван дать ответ на вопрос: "Все ли ФАЛ входящие в эти или какие-либо другие наборы являются необходимыми для обеспечения функциональной полноты набора?".
Система функций F={f1, f2,…,fn} называется базисом, если она полна, но всякая её собственная подсистема не является полной.
Дать ответ на вопрос о включении той или иной функции в состав функционально полного набора, а тем более, базиса не представляется возможным. Можно дать лишь верхнее ограничение на количество логических функций, входящих в базис, на основе следующей теоремы.
Теорема Яблонского
Из всякой полной системы логических функций можно выделить полную подсистему, содержащую не более четырех логических функций.
Таким образом, любой базис логических функций содержит не более четырех ФАЛ.
В лекции дано определение полноты системы логических функций. Описаны основные свойства ФАЛ. На основании свойств логических функций от двух переменных согласно теореме Поста-Яблонского представлены примеры наиболее часто используемых в вычислительной технике функционально-полных наборов логических функций. Определено понятие базиса логических функций.
Булева функция может быть представлена суперпозицией (совокупности) некоторого набора функций {f1, f2, ... fn}.
Система элементарных логических функций f1 … fm называется полной, если любую ФАЛ можно изобразить в виде суперпозиции функций f1 . . . fn.
Теорема. Пусть даны две системы логических функций:
$$F={f_{1}, f_{2},…,f_{n}}$$и
$$G={g_{1}, g_{2},…,g_{n}}$$Если система (4.1) полна и каждая её функция может быть выражена как суперпозиция функций системы (4.2), тогда система (4.2) является полной.
Пример 4.1. Известно, система функций {И, ИЛИ, НЕ} является функционально полной (например, именно в этой системе логических функций можно представить её совершенные дизъюнктивную и конъюнктивную нормальные формы СДНФ, СКНФ). Отсюда следует, что система ФАЛ, состоящая из одной функции "Штрих Шеффера", также функционально полна, так как:
$$\overline{x} = x / x$$ $$x \vee y =\overline{\overline{ x \vee y}}=\overline{\overline{x} \And \overline{y}}=(x/x)/(y/y)$$ $$x \And y = \overline{\overline{x \And y}}=(x/x)/(y/y)$$Правила перехода от представления ФАЛ в виде ДНФ к функции, представленной в базисе "Штрих Шеффера"
Правила перехода от представления ФАЛ в виде КНФ к функции, представленной в базисе "Стрелка Пирса"
Рассмотрим основные свойства логических функций, которые позволят определить их состав, составляющий функционально полный набор.
Переключательной (логической) функцией, сохраняющей нуль, называется функция, которая на нулевом наборе аргументов, т.е. на наборе (0,0, ..., 0,0), равна нулю. Для переключательных функций, сохраняющих нуль, выполняется условие: f( 0,0, ..., 0,0 ) = 0.
Очевидно, что логических функций от n аргументов, сохраняющих ноль, будет ровно половина от всех возможных функций, то есть $$2^{2^{n-1}}$$.
Переключательной функцией, сохраняющей единицу, называется функция, которая на единичном наборе аргументов, т.е. на наборе (1,1, ..., 1,1), равна единице. Для переключательных функций, сохраняющих единицу, выполняется условие:f (1,1, ..., 1,1) = 1. Функций, обладающих этим свойством, будет также ровно половина:$$2^{2^{n-1}}$$.
К одному из основных свойств логической функции относится ее принадлежность к классу самодвойственных функций. Чтобы рассмотреть это свойство разберем вначале несколько сопутствующих понятий.
Два набора аргументов называются противоположными, если все значения аргументов одного набора противоположны значениям аргументов другого набора. Чтобы получить противоположный набор, достаточно заменить в данном наборе нули единицами, а единицы нулями.
Для функции трех аргументов следующие пары наборов являются противоположными:
000 и 111; 001 и 110; 010 и 101; 011 и 100.
В общем виде два противоположных набора записываются в виде (x1, x2, ..., xn) и ($$\overline{x_{1}}, \overline{x_{2}}, ..., \overline{x_{n}).$$
Переключательная функция n переменных f* (x1, x2, ..., xn) называется двойственной к функции f(x1, x2, ..., xn) , если имеет место равенство:
$$f^{*}(x_{1}, x_{2},. . . , x_{n}) = \overline{f}(\overline{x_{1}},\overline{x_{2}},. . ., \overline{x_{n}})$$Например, для функции дизъюнкции f (x1, x2) = x1 v x2 двойственной будет функция конъюнкции f* (x1, x2) = x1 x2.
Переключательная функция называется самодвойственной, если на каждой паре противоположных наборов она принимает противоположные значения, т. е. если выполняется условие:
$$f(x_{1}, x_{2},. . . , x_{n}) = f^{*}(x_{1},x_{2}, . . . , x_{n}) = \overline{f}(\overline{x_{1}},\overline{x_{2}}, . . . , \overline{x_{n}})$$Пример самодвойственной функции: F(x1,x2,x3) = ∑(1,2,3,7)
| Набор | x1 | x2 | x3 | F(x1,x2,x3) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 | 0 |
| 6 | 1 | 1 | 0 | 0 |
| 7 | 1 | 1 | 1 | 1 |
При определении свойства монотонности переключательной функции используется понятие сравнимости двух наборов аргументов.
Примем условие, что 0 < 1 (на самом деле, для логической функции корректнее было бы писать: false < true, но это смотрится у совсем несерьезно и в свете дальнейших рассуждений оставим все-таки исходный вариант). Два набора аргументов X = (x1, x2, ..., xn) и Z = ( z1, z2, ..., zn ) называются сравнимыми, если для всех аргументов выполняется условие xi =< zi (говорят, что X =< Z). Иными словами, если значение каждого аргумента одного набора меньше или равно значению того же аргумента второго набора, то говорят, что первый набор меньше или равен второму (не больше второго). И наоборот. Если значение каждого аргумента одного набора больше или равно значению того же аргумента второго набора, то говорят, что первый набор больше или равен второму (не меньше второго).
Например, если X = (0000) и Z = (0001), то наборы сравнимы, и X < Z.
Если же некоторые из значений аргументов первого набора больше или равны, а другие меньше значений тех же аргументов второго набора, то такие наборы называются несравнимыми.
Например, если X = (1010) и Z = (0110), то эти наборы являются несравнимыми (x1 > z1, но x2 < z2).
Переключательная функция называется монотонной, если для всех пар сравнимых наборов при любом возрастании набора значение этой функции не убывает, т.е. сохраняет свое значение или изменяется с 0 на 1. Здесь, аналогично обычной математике, можно рассматривать монотонно возрастающие и монотонно убывающие функции, но для наших дальнейших рассуждений это не будет иметь какого-либо значения.
Т.е. для монотонной логической функции должно выполняться условие: если для сравнимых наборов X =< Z , то F(X) =< F(Z).
Примеры: монотонная функция: F1(x1, x2) = x2,
немонотонная функция: $$F2(x_1, x_2) = x_1 \oplus x_2$$
x1 | x2 | F1(x1,x2) | F2(x1,x2) |
| 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Для упрощения анализа данной таблицы отметим, что наборы (0,1) и (1,0) являются несравнимыми. Поэтому значения функции для определения ее монотонности на этих наборах делать не следует.
Переключательная функция называется линейной, если она может быть представлена полиномом Жегалкина
$$f(x_1,x_2, …, x_n) = c_0 \oplus c_1 x_1 \oplus c_2 x_2 \oplus … \oplus c_n x_n$$, где
$$\oplus$$ – символ операции "сумма по mod2";
с0, с1, ..., сn – коэффициенты, равные 0 или 1.
Для того чтобы система переключательных функций была функционально полной, необходимо и достаточно, чтобы эта система включала:
Рассмотрим все функции от двух переменных f(x0, x1) с точки зрения удовлетворения ими рассмотренным выше свойствам (Табл. 4.1).
| Свойства функций двух переменных | |||||
|---|---|---|---|---|---|
| Функция | Сохранение "0" | Сохранение "1" | Самодвойственная | Монотонная | Линейная |
| $$f_0 = 0$$ | + | + | + | ||
| $$f_1 = \overline{x_{1}\vee x_{0}}$$ | |||||
| $$f_2 = \overline{x_{1}}x_{0}$$ | + | ||||
| $$f_3 = \overline{x_1}$$ | + | + | |||
| $$f_4 = x_{1}\overline{x_{0}}$$ | + | ||||
| $$f_5 = \overline{x_{0}}$$ | + | + | |||
| $$f_6 = x_1 oplus x_0$$ | + | + | |||
| $$f_7 = \overline{x_1 x_0}$$ | |||||
| $$f_8 = x_1 x_0$$ | + | + | + | ||
| $$f_9 = \overline{x_{1}\oplus x_{0}}$$ | + | + | |||
| $$f_{10} = x_0$$ | + | + | + | + | + |
| $$f_{11} = \overline{x_{1}}$$ | + | ||||
| $$f_{12} = x_1$$ | + | + | + | + | + |
| $$f_{13} = x_{1}\vee\overline{x_0}$$ | + | ||||
| $$f_{14} = x_1 \vee x_0$$ | + | + | + | ||
| $$f_{15} = 1$$ | + | + | + | ||
Мы видим, что как, собственно, и следовало ожидать, если включить в состав функционально полного набора все функции от данного числа переменных, то с его помощью мы, даже не прибегая к суперпозиции каких-либо функций, сможем выразить любую ФАЛ.
Выделение всех функционально полных наборов ФАЛ даже для функций двух переменных с относительно небольшим количеством функций является весьма трудоемкой задачей, которая может решаться либо перебором, либо какими-то эвристическими методами. А для функций от трёх переменных (общее количество таких функций$$2^{2^{3}}=256$$) это становится непосильной задачей.
На практике используются несколько наиболее известных таких наборов:
F1 = {, V , ˉ } – "И, ИЛИ, НЕ"
F2 = {/} – "штрих Шеффера"
F3 = {->} – "стрелка Пирса"
F4 = {"Сумма по mod2", "И", "Константа 1"} – "базис Жегалкина".
Как видим из Табл. 4.1, все они удовлетворяют теореме Поста – Яблонского, поэтому являются функционально полными.
На первом этапе вопрос ставится так, чтобы в функционально полный набор функций входило их ограниченное количество.
Уже на примере анализа функций, входящих в набор F1, можно сделать вывод, что данный набор является избыточным: удаление из него функции "И" или функции "ИЛИ" всё равно приводит к тому, что остающиеся две функции удовлетворяют требованиям теоремы Поста – Яблонского, а, следовательно, наборы из функций {"И", "НЕ"} и {"ИЛИ", "НЕ"} тоже функционально полны. Из этих наборов ни одну функцию убрать уже нельзя без того, чтобы они не перестали быть функционально полными.
В то же время наборы F2 и F3 состоят всего лишь из одной функции. Поэтому нет смысла их каким-либо образом сокращать.
В связи с этим помимо понятия "функционально полный набор логических функций" используется также понятие "логический базис".
Второй этап призван дать ответ на вопрос: "Все ли ФАЛ входящие в эти или какие-либо другие наборы являются необходимыми для обеспечения функциональной полноты набора?".
Система функций F={f1, f2,…,fn} называется базисом, если она полна, но всякая её собственная подсистема не является полной.
Дать ответ на вопрос о включении той или иной функции в состав функционально полного набора, а тем более, базиса не представляется возможным. Можно дать лишь верхнее ограничение на количество логических функций, входящих в базис, на основе следующей теоремы.
Теорема Яблонского
Из всякой полной системы логических функций можно выделить полную подсистему, содержащую не более четырех логических функций.
Таким образом, любой базис логических функций содержит не более четырех ФАЛ.
В лекции дано определение полноты системы логических функций. Описаны основные свойства ФАЛ. На основании свойств логических функций от двух переменных согласно теореме Поста-Яблонского представлены примеры наиболее часто используемых в вычислительной технике функционально-полных наборов логических функций. Определено понятие базиса логических функций.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.