Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Методические указания к практической работе № 4
|
|
Определение. Булевой функцией f(x1, x2, …, xn) называется n-местная функция, аргументы которой принимают значения во множестве {0, 1} и сама функция принимает значения в этом же множестве.
Всякую булеву функцию от n переменных можно задать таблицей из 2n строк, в которой в каждой строке записывают одну из оценок списка переменных, принимающих значение 0 или 1.
Пример.
Для n=3 булеву функцию можно задать следующей таблицей.
| № | x1 | x2 | x3 | f(x1, x2, x3) |
| f(0, 0, 0) | ||||
| f(0, 0, 1) | ||||
| f(0, 1, 0) | ||||
| f(0, 1, 1) | ||||
| f(1, 0, 0) | ||||
| f(1, 0, 1) | ||||
| f(1, 1, 0) | ||||
| f(1, 1, 1) |
Используется также задание булевой функции в виде двоичного слова, длина которого зависит от числа переменных.
Пример.
Пусть задана булева функция от трех переменных. Тогда число наборов 
.
| № набора | х1 | х2 | х3 | f |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 0 | 1 | 1 | 0 |
| 4 | 1 | 0 | 0 | 1 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 0 |
| 7 | 1 | 1 | 1 | 1 |
Номера наборов всегда нумеруются, начиная с нуля, в таблице приведено стандартное расположение всех наборов функции трех переменных (обратите внимание, что каждый набор представляет собой двоичный код числа, равный номеру соответствующего набора). Первые четыре столбца одинаковы для всех булевых функций от трех переменных. Столбец значений функции задается или вычисляется.
Эту же функцию можно записать f(х1, х2, х3)=00101101.
Утверждение 1. Существует ровно 
различных булевых функций от n переменных. Константы 0 и 1 считают нуль-местными булевыми функциями.
Утверждение 2. Каждой формуле логики высказываний соответствует некоторая булева функция.
Пример.
Построить все булевы функции, зависящие от двух переменных.
Решение.
n=2, различных булевых функций от двух переменных существует ровно 16.
Таблица 4 – Булевы функции от двух переменных
| № функции | Значение функции | Формула, соответствующая функции |
| 1. | f=0000 | f=0 |
| 2. | f=0001 | f=x1Ù x2 |
| 3. | f=0010 | f= 
|
| 4. | f=0011 | f=x1 |
| 5. | f=0100 | f= 
|
| 6. | f=0101 | f=x2 |
| 7. | f=0110 | f=x1Å x2 |
| 8. | f=0111 | f=x1Ú x2 |
| f=1000 | f= 
| |
| f=1001 | f= 
| |
| f=1010 | f= 
| |
| f=1011 | f= 
| |
| f=1100 | f= 
| |
| f=1101 | f=x1®x2 | |
| f=1110 | f= 
| |
| f=1111 | f=1 |
Теорема 1. Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно нулю, то существует такая формула F, зависящая от списка переменных x1, x2, …, xn и находящаяся в СДНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки дизъюнктивных членов.
Теорема 2. Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно единице, то существует такая формула F, зависящая от списка переменных x1, x2, …, xk и находящаяся в СКНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки конъюнктивных членов.
Поскольку каждая булева функция представима в виде формулы логики высказываний, то принцип построения СДНФ и СКНФ сохраняется такой же как и для формул логики высказываний.
Пример.
Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 00101110.
Решение.
Таблица 5 – Таблица значений булевой функции:
| № | x1 | x2 | x3 | f(x1, x2, x3) |
СКНФ (0): № 0, 1, 3, 7
СДНФ (1): № 2, 4, 5, 6
Определение. Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени: 
, причем на каждом наборе < i1, …, ik> все аij (j = 1, …, k) различны, aj Î {0, 1}.
Теорема. Всякую булеву функцию можно представить единственным полиномом Жегалкина.
Многочлен Жегалкина можно получить различными способами. Остановимся на рассмотрении построения многочлена Жегалкина с помощью треугольника Паскаля. Рассмотрим алгоритм на примере.
Пример.
Построить многочлен Жегалкина для функции f=10011110.
Решение.
Алгоритм построения многочлена Жегалкина:
Шаг 1. Строим таблицу. Первый столбец содержит возможные слагаемые многочлена Жегалкина. Нулевому набору всегда соответствует слагаемое 1. Остальным наборам соответствует слагаемое, представляющее собой конъюнкцию переменных, которые на данном наборе принимают значение 1. Следующие n столбцов – всевозможные наборы из 0 и 1, соответствующие переменным. Далее столбец значений функции f. Функция g является вспомогательной, поэтому изначально этот столбец не заполнен.
Таблица 6 – Многочлен Жигалкина
| Слагаемые многочлена Жегалкина | x1 | x2 | x3 | f | g | Треугольник Паскаля |
| 1 | 0 | 0 | 0 | 1 | ||
| x3 | 0 | 0 | 1 | 0 | ||
| x2 | 0 | 1 | 0 | 0 | ||
| x2x3 | 0 | 1 | 1 | 1 | ||
| x1 | 1 | 0 | 0 | 1 | ||
| x1 x3 | 1 | 0 | 1 | 1 | ||
| x1 x2 | 1 | 1 | 0 | 1 | ||
| x1 x2 x3 | 1 | 1 | 1 | 0 |
Шаг 2. Построение треугольника Паскаля. Верхняя сторона треугольника есть функция f. Любой другой элемент треугольника есть сумма по модулю два двух соседних элементов предыдущей строки. Левая сторона треугольника представляет собой значение вспомогательной функции g.
Таблица 7 – Многочлен Жигалкина
| Слагаемые многочлена Жегалкина | x1 | x2 | x3 | f | g | Треугольник Паскаля |
| 1 | 0 | 0 | 0 | 1 | 1 | f = 1 0 0 1 1 1 1 0 |
| x3 | 0 | 0 | 1 | 0 | 1 | 1 0 1 0 0 0 1 |
| x2 | 0 | 1 | 0 | 0 | 1 | 1 1 1 0 0 1 |
| x2x3 | 0 | 1 | 1 | 1 | 0 | 0 0 1 0 1 |
| x1 | 1 | 0 | 0 | 1 | 0 | 0 1 1 1 |
| x1 x3 | 1 | 0 | 1 | 1 | 1 | 1 0 0 |
| x1 x2 | 1 | 1 | 0 | 1 | 1 | 1 0 |
| x1 x2 x3 | 1 | 1 | 1 | 0 | 1 | 1 |
Шаг 3. Построение многочлена Жегалкина. В многочлен войдут только те слагаемые, которым соответствует единица во вспомогательной функции g.
Для данной функции многочлен Жегалкина имеет вид:
f = 1 + x3 + x2 + x1 x3 + x1 x2 + x1 x2 x3.
Варианты заданий
Вариант 1
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 01101110.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=11011110
b) f=11010110.
Вариант 2
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 00100110.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=01011110
b) f=11000110.
Вариант 3
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 10101110.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=10101110
b) f=11011010.
Вариант 4
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 10101010.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=11011000
b) f=0101110.
Вариант 5
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 10101101.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=11000110
b) f=11010110.
Вариант 6
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 01101110.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=11001100
b) f=10101010.
Вариант 7
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 00100100.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=01001110
b) f=11011010.
Вариант 8
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 0010111.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=11011101
b) f=00011110.
Вариант 9
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 00001110.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=11110010
b) f=01011100.
Вариант 10
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 11110000.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=11011100
b) f=10010110.
Вариант 11
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 00101010.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=10011100
b) f=11011101.
Вариант 12
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 10001110.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=10001111
b) f=10010010.
Вариант 13
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 11101110.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=01011101
b) f=00011110.
Вариант 14
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 10000111.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=00010001
b) f=11101110.
Вариант 15
Задание 1. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 00100101.
Задание 2. Построить многочлен Жегалкина для функции:
a) f=01010101
b) f=10100100.
Вопросы к защите практической работы №4
1. Что называется булевой функции?
2. Как определить количество наборов переменных булевой функции?
3. Сколько существует наборов для функции п переменных?
4. Опишите алгоритм построения СДНФ булевой функции.
5. Опишите алгоритм построения СДНФ булевой функции.
6. Сформулируйте определение многочлена Жегалкина.
7. Опишите алгоритм построения многочлена Жегалкина.
|
|