При рассмотрении таблицы можно выделить 44 функционально полных системы булевых функций: 2 – одно функциональных, 16 – двух функциональных, 23 –трех функциональных, 3 – четырех функциональных.
Система функций, которая является функционально полной, называется базисом.
Минимальным базисом называется такой базис, удаление из которого хотя бы одной функции превращает систему в неполную.
В настоящее время используются три базиса - базис Шеффера, базис Пирса и булев базис, в котором содержатся три функции И, ИЛИ, инверсия.

Заметим, что булев базис не является минимальным, т.к. из него можно удалить либо функцию И, либо функцию ИЛИ.

Аналитическая запись булевых функций в базисе Пирса.
Будем использовать следующее обозначение:

.

Вспомним запись булевой функции в совершенной дизъюнктивной нормальной форме: . Символ означает, что дизъюнкция берется только для таких наборов на которых функция равна единице: . Попробуем записать эту функцию таким образом, чтобы оно содержало только функции Пирса и отрицания (отрицание также реализуется функцией Пирса: ). Просуммируем конституенты единицы наборов, где функция равно нулю. Мы получили новую функцию, значения которой противоположны исходной функции, поэтому: . Но последнее выражение есть не что иное, как функция Пирса: . Однако конституенты единицы представляют собой конъюнкции переменных и от конъюнкций нужно также избавиться. Для этого преобразуем конституенты единицы: .

Таким образом, алгоритм перехода от табличного задания функции к аналитической записи в базисе Пирса таков:

1) выбрать в таблице все наборы аргументов

---

, на которых функция равна нулю;

2) аргументы каждого из этих наборов объединяются функцией Пирса. Причем, если аргумент равен 1, то он записывается с отрицанием; если – 0, то без отрицания;

3) все полученные составляющие (термы) объединяются функцией Пирса.
Пример:

	0	0	0	0	1	1	1	1
	0	0	1	1	0	0	1	1
	0	1	0	1	0	1	0	1
	1	1	0	1	1	0	1	0

Выбираем наборы 010, 101, 111;

, , ;

3) .

По аналитической записи функции можно нарисовать схему её реализующую:

---

Запись функций в базисе Шеффера.
Конституента нуля для набора записывается так:

. Действительно, в силу определения конституенты нуля

она равна нулю на этом наборе, следовательно все слагаемые в конституенте должны быть равны нулю. Отсюда следует правило, если в наборе аргумент равен единице, то в конституенту нуля он записывается с отрицанием, если нулю – без отрицания.

Известно, что любую функцию можно записать в совершенной конъюнктивной нормальной форме в виде произведения конституент нуля. Однако ее можно записать и как инверсию функции значения которой противоположны исходной функции:



Символы ( ) обозначают, что конъюнкциями связываются конституенты нуля наборов на которых исходная функция равна нулю (единице). Действительно, если на наборе функция равна единице, то можно указать для этого набора конституенту нуля равную нулю на этом наборе и единице – на остальных наборах. Конъюнкция этих конституент представляет собой новую функцию равную нулю на тех наборах, где функция равна единице, т.е. и . Полученное выражение – это функция Шеффера над конституентами нуля: . Для получения окончательной записи функции преобразуем конституенты нуля:

Окончательное представление функции: . Следовательно, алгоритм перехода от таблицы истинности к аналитической записи в базисе Шеффера

---

таков:

Выбрать в таблице все наборы аргументов на которых функция равна единице;

Аргументы каждого из этих наборов связать операцией Шеффера, причем, если аргумент равен 1, то он записывается без отрицания, если нулю – с отрицанием.

Все полученные выражения также связываются операцией Шеффера.

Пример:

	0	0	0	0	1	1	1	1
	0	0	1	1	0	0	1	1
	0	1	0	1	0	1	0	1
	1	0	1	0	0	0	0	1

000, 010, 111;

, , ;

---

Минимизация булевых функций.
Одну и ту же булеву функцию можно представить в виде различных логических выражений тождественных друг другу. Практический интерес имеют выражения, содержащие наименьшее число букв, т. к. они позволяют упростить устройство, реализующее эту функцию. Такие функции называют минимальными. Поскольку в настоящее время используются три базиса: булев, Пирса и Шеффера, то будем изучать методы минимизации функций в булевом базисе, когда уравнения представляются в минимальных дизъюнктивных нормальных формах (МДНФ); в булевом базисе, когда уравнения записываются в минимальных конъюнктивных нормальных формах (МКНФ); в базисе Пирса и базисе Шеффера.

Проблеме минимизации посвящено огромное число работ, известно большое число различных методов минимизации. При небольшом числе аргументов булевой функции используют диаграммы Вейча (карты Карно). Метод чрезвычайно удобен при числе аргументов не более пяти. Диаграммы Вейча – это графическое представление таблиц истинности, когда таблица размещается на торе, естественно, что при использовании таблицы используют развертку тора. При выполнении заданных формальных правил «автоматически» производится выполнение операций склеивания и поглощения, а результатом будет минимальная форма булевой функции.

В литературе описаны методы получения МДНФ и МКНФ. При необходимости получения минимальных форм в базисе Пирса или Шеффера используют тождественные преобразования МДНФ или МКНФ. Такой подход вряд ли можно считать оправданным, т.к. минимальные формы функции в базисах Пирса и Шеффера можно легко получить по тем же самым диаграммам Вейча.
Получение минимальных дизъюнктивных нормальных

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

---

Смотрите также файлы

• Реконструкция средней школы 18 в г. Белгороде.docx

• Вестник пнипу. Аэрокосмическая техника. 2014. 39 50.pdf

• Расчет параметров бвр.docx

• При проектировании фрагмента занятия следуйте логике методической разработки.docx

• Гормоны гипофиза у плода.docx