Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Для новых пользователей первый месяц бесплатно. Чат-бот для мастеров и специалистов, который упрощает ведение записей: — Сам записывает клиентов и напоминает им о визите;
— Персонализирует скидки, чаевые, кэшбэк и предоплаты;
— Увеличивает доходимость и помогает больше зарабатывать; Начать пользоваться сервисом
Методические указания к практической работе № 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 определена однозначно с точностью до перестановки дизъюнктивных членов.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
Теорема 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. Опишите алгоритм построения многочлена Жегалкина.
|
|