Полные системы булевых функций

СОДЕРЖАНИЕ

1. Полные системы булевых функций

2. Сокращенные и тупиковые дизъюнктивные нормальные формы

3. Алгоритм Квайна и Мак-Класки минимизации булевой функции

4. Геометрическое представление логических функций

5. Геометрический метод минимизации булевых функций

6. Минимизация булевой функции с помощью карты Карно

7. Построение оптимальных контактно-релейных схем

Упражнения

Библиографический список

1. Полные системы булевых функций

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

Таблица 1

№	X1 = 0 X2 = 0	0 1	1 0	1 1	fk (X1 , X2 )
1	0	0	0	0	f1 = 0
2	0	0	0	1
3	0	0	1	0
4	0	0	1	1
5	0	1	0	0
6	0	1	0	1
7	0	1	1	0
8	0	1	1	1
9	1	0	0	0
10	1	0	0	1
11	1	0	1	0
12	1	0	1	1
13	1	1	0	0
14	1	1	0	1
15	1	1	1	0
16	1	1	1	1

Функция f₁ называется нулевой; f₁₆ – единичной; f₂ – конъюнкцией; f₈ – дизъюнкцией; f₁₁ и f₁₃ – отрицаниями Х₁ и Х₂ соответственно; f₁₂ и f₁₄ – импликациями; f₃ и f₅ – коимпликациями; f₁₀ – эквиваленцией; f₇ – сложением по модулю два или разделительной дизъюнкцией; f₉ – стрелкой Пирса (функцией Вебба); f₁₅ – штрихом (функцией) Шеффера.

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

является суперпозицией элементарных функций: отрицания, дизъюнкции, конъюнкции и импликации.

Система булевых функций называется полной, если любая булева функция является суперпозицией этих функций.

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

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

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

Полная система булевых функций называется базисом, если она перестает быть полной при удалении хотя бы одной из этих функций.

Согласно этому определению система булевых функций не является базисом. Действительно, применяя законы де-Моргана

, ,

конъюнкцию в булевой функции можно заменить на дизъюнкцию и отрицани

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать