Автор: Пользователь скрыл имя, 19 Февраля 2012 в 14:02, доклад
Функцией алгебры логики (булевой функцией) от переменных называется функция, принимающая значения 1,0 и аргументы которой также принимают значения 1,0.
Всякая булева функция от переменных может быть задана с помощью таблицы истинности
Найдем выражение для и . Для упрощения записей обозначим , , соответственно через , , , а и - через и .
Тогда
,
.
Упростим
данные выражения
Таким
образом
Отсюда получаем схему одноразрядного двоичного сумматора
Задание
к лабораторной работе
№4
I.
Составить контактные и
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
II.
Упростить схемы
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
III.
1) Нужно, чтобы включение света
в комнате осуществлялось с
помощью трех различных
2)
Пусть каждый из пяти членов
комитета голосует «за», нажимая
кнопку. Постройте простейшую цепь,
через которую ток проходил
бы тогда и только тогда,
когда большинство членов
3)
Пусть каждый из пяти членов
комитета голосует «за», нажимая
кнопку. Постройте простейшую цепь,
через которую ток проходил
бы тогда и только тогда,
когда большинство членов
4)
Построить контактные и
5)
Построить контактные и
6)
Построить контактные и
7)
Составьте электронную схему
дешифратора, переводящую
8)
Составить схему-шифратор, переводящую
десятичные цифры в
Контрольные
вопросы
Лабораторная
работа №5. Полнота и
замкнутость
Система булевых функций называется полной, если любую булеву функцию можно представить в виде суперпозиции функций из .
Например,
следующие системы
,
,
являются полными.
Множество булевых функций называется замкнутым классом, если любая суперпозиция функций из снова принадлежит .
Всякая система булевых функций порождает некоторый замкнутый класс. Этот класс состоит из всех булевых функций, которые можно получить суперпозициями из . Такой класс называется замыканием и обозначается . Для замкнутого класса следует, что . Очевидно, что если - полная система, то .
Рассмотрим следующие классы булевых функций.
- класс булевых функций,
- класс булевых функций,
Булева
функция
называется двойственной
к функции
, если
.
Булева функция называется самодвойственной, если она совпадает с двойственной, т.е. .
- класс всех самодвойственных функций.
Булевы функции вида , где , равны нулю или единице, называются линейными.
- класс всех линейных булевых функций.
Для того, чтобы определить, является ли данная булева функция линейной или нет, ее надо представить в виде полинома Жегалкина.
Два набора и называются сравнимыми, если , .
Запись означает, что набор предшествует набору .
Булева функция называется монотонной, если для любых наборов и таких, что , имеет место неравенство . - класс монотонных функций.
Теорема (о функциональной полноте). Для того, чтобы система булевых функций была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти классов , , , , .
В
тех задачах, где требуется выяснить, является
ли данная система булевых функций
полной, мы будем составлять таблицы,
которые называются таблицами
Поста.
В клетках данной таблицы мы будем писать плюс или минус, в зависимости от того, входит функция, стоящая в данной строке в класс, стоящий в данном столбце, или не входит. Используя теорему о полноте, мы получаем, что для полноты данной системы булевых функций необходимо и достаточно, чтобы в каждом столбце стоял хотя бы один минус.
Пример 1. Выяснить, является ли функция линейной.
Найдем
полином Жегалкина для данной
функции.
,
Следовательно, данная функция линейна.
Пример
2. Какие из указанных функций являются
монотонными:
а)
б)
а)
Упростим формулу
.
Эта функция равна нулю на наборах (0,0,0), (0,1,0), (1,0,0). Все оставшиеся наборы, исключая (0,0,1) содержат не менее двух единиц, а значит, они могут быть только больше. Набор (0,0,1) (0,0,0), а с остальными двумя он несравним. Значит, рассматриваемая функция монотонна.
б) Функция немонотонна, т.к. (0,0) (1,0), но .
Пример 3. Является ли функция самодвойственной?
Найдем
двойственную функцию к данной
Следовательно, данная функция самодвойственная.
Пример
4. Выяснить, являются ли данные системы
булевых функций полными
а)
б)
в)
а)
. Ясно, что
,
. Так как
, то
. Найдем полином Жегалкина для
. Следовательно,
. Так как (0,0)
(1,1), но
, то
.
Таблица Поста для системы имеет вид.
- | - | - | - | - |
Итак,
- полная система.
б)
+ | - | - | + | + | |
- | + | - | + | + | |
+ | + | - | - | + | |
+ | + | + | + | - |
Функция
самодвойственна, так как
Функция немонотонная, так как (0,0,1) (0,1,1), но 1=0+0+1>0+1+1=0.
Система
- полная система.
в)
- | - | + | + | - | |
+ | + | + | - | - |
Функция
самодвойственная, так как
Итак, система целиком принадлежит классу . Следовательно, по теореме о полноте не является полной системой.
Задания
к лабораторной работе
№5
I. Какие из указанных систем функций являются замкнутыми классами?
1) Линейная функция;
2) самодвойственные функции;
3) монотонные функции;
4) монотонно убывающие функции;
5) функции, сохраняющие нуль;
6) функции, сохраняющие единицу;
7) функции, сохраняющие и нуль, и единицу;
8) функции, сохраняющие нуль, но не сохраняющие единицу;
9) функции от одной переменной;
10) функции от двух переменных.
II.
Являются ли следующие функции
линейными?
1)
2)
3)
4)
5)
6)
7)
8)