Автор работы: Пользователь скрыл имя, 01 Августа 2013 в 11:36, контрольная работа
Задание 1
1) Составить таблицу истинности для булевой функции.
2) Составить СДНФ и СКНФ по таблице истинности.
3) Привести функцию с помощью преобразований к СДНФ и СКНФ.
4) Построить полином Жегалкина методом неопределённый коэффициентов.
Задание 2:
1) Выяснить вопрос о равносильности ДНФ функций сведением их к СДНФ.
2) Преобразовать с помощью дистрибутивных законов f_2 к КНФ, упростить логическое выражение.
f_1=x¯y ¯z∨xz∨yz∨x¯y z
f_2=y¯x∨¯y x∨xz
f_3=z¯x∨¯y x∨¯z
Задание 3:
Для данной булевой функции f(x_1,x_2,x_3,x_4 )=1100 0100 0111 0110, заданной векторно, составить:
1) дизъюнктивное разложение по переменным x_2,x_4
2) конъюнктивное разложение по переменным x_1,x_4
Задание 1
1) Составить таблицу истинности для булевой функции.
2) Составить СДНФ и СКНФ по таблице истинности.
3) Привести функцию с помощью преобразований к СДНФ и СКНФ.
4) Построить полином Жегалкина методом неопределённый коэффициентов.
Решение:
1) Таблица истинности:
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
2) СДНФ:
СКНФ:
Добавим в элементарные конъюнкции «недостающие» переменные и применим дистрибутивный закон:
Перейдём от ДНФ к КНФ, используя дистрибутивные законы.
4) Полином Жегалкина булевой функции от трёх переменных x, y, z имеет вид:
Найдём неизвестные
Тогда:
Задание 2:
1) Выяснить вопрос о
равносильности ДНФ функций
2) Преобразовать с помощью дистрибутивных законов к КНФ, упростить логическое выражение.
Решение:
Видим, что среди функций равносильных нет.
Задание 3:
Для данной булевой функции заданной векторно, составить:
1) дизъюнктивное разложение по переменным
2) конъюнктивное разложение по переменным
Решение:
Составим таблицу истинности для функции
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1) Дизъюнктивное разложение по переменным
Из таблицы истинности видно, что:
Тогда:
2) Конъюнктивное разложение по переменным
Из таблицы истинности видно, что:
Тогда:
Задание 4:
Для функций выяснить вопрос об принадлежности к классам
Решение:
Сопоставим функциям таблицу истинности:
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
Проверка функции
Δ Паскаля |
Слагаемые | ||||
0 |
0 |
0 |
0 |
0 1 1 0 1 1 1 0 |
1 |
0 |
0 |
1 |
1 |
1 0 1 1 0 0 1 |
z |
0 |
1 |
0 |
1 |
1 1 0 1 0 1 |
y |
0 |
1 |
1 |
0 |
0 1 1 1 1 |
yz |
1 |
0 |
0 |
1 |
1 0 0 0 |
x |
1 |
0 |
1 |
1 |
1 0 0 |
xz |
1 |
1 |
0 |
1 |
1 0 |
xy |
1 |
1 |
1 |
0 |
1 |
xyz |
Единицам левой стороны соответствуют слагаемые нашего полинома:
Проверка функции
Δ Паскаля |
Слагаемые | ||||
0 |
0 |
0 |
1 |
1 0 0 1 0 0 1 0 |
1 |
0 |
0 |
1 |
0 |
1 0 1 1 0 1 1 |
z |
0 |
1 |
0 |
0 |
1 1 0 1 1 0 |
y |
0 |
1 |
1 |
1 |
0 1 1 0 1 |
yz |
1 |
0 |
0 |
0 |
1 0 1 1 |
x |
1 |
0 |
1 |
0 |
1 1 0 |
xz |
1 |
1 |
0 |
1 |
0 1 |
xy |
1 |
1 |
1 |
0 |
1 |
xyz |
— нелинейный, значит
Задание 5:
Для данной булевой функции:
1) Найти фиктивные переменные.
2) Преобразовать данную
формулу в эквивалентную ей, но
не содержащую фиктивных
Решение:
Первый способ (основан на равносильных преобразованиях).
Второй способ (по таблице истинности).
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
z:
Так как переменная на всех соседних наборах значений переменных принимает одинаковые
значения, то она является фиктивной.
Для восстановления функции, не содержащей фиктивную переменную , возьмём таблицу истинности функции , вычеркнем из нее все строки, в которых , а также вычеркнем столбец переменной . В результате получим таблицу истинности функции
|
|||
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
Чтобы булеву функцию задать формулой, нужно составить СДНФ или СКНФ (с последующим упрощением), а лучше полином Жегалкина (в данном случае), так как выше уже было установлено, что данная функция есть
Задание 6:
Даны функции
Решение:
1) Сопоставим для функций таблицу истинности.
0 |
0 |
0 |
− |
1 |
− |
0 |
0 |
1 |
0 |
− |
0 |
0 |
1 |
0 |
− |
− |
0 |
0 |
1 |
1 |
0 |
− |
− |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
− |
0 |
− |
1 |
1 |
0 |
− |
1 |
− |
1 |
1 |
1 |
− |
− |
1 |
Так как то на всех наборах, предшествующих набору (011), функция тоже должна равняться 0, то есть:
Так как то на всех наборах, которым предшествует набор (100), функция тоже должна равняться 1, то есть:
Получаем:
Если функция линейна, то её полином Жегалкина должен иметь вид:
то есть не содержит знака конъюнкции.
Подставим наборы значений переменных, где функция определена:
Подставим во второе уравнение системы, получим:
Решение системы:
Тогда: . В соответствии с этим полиномом доопределяем функцию на тех наборах, на которых она не определена.
Получаем:
Чтобы , на всех противоположных наборах значений переменных она должна принимать разные значения. Поэтому:
2) Так как