Даны две функции
.
Требуется:
а) для функции f1(x,y) составить таблицу истинности и найти по ней полином Жегалкина, СДНФ и СКНФ. Упростить, если возможно, СДНФ.
б) для функции f2(x,y,z) составить таблицу истинности и найти по ней полином Жегалкина, СДНФ и СКНФ. По карте Карно получить минимальную ДНФ, нарисовать эквивалентную РКС.
в) составить таблицу Поста для системы функций f1(x,y), f2(x,y,z), проверить полноту системы и выбрать базисы, если она полная.
Решение
А) Составим для функции таблицу истинности.
x y
0 0 0 1 1
0 1 0 1 1
1 0 0 0 1
1 1 1 0 0
Построим полином Жегалкина.
Воспользуемся методом неопределенных коэффициентов.
Многочлен Жегалкина булевой функции двух переменных имеет вид:
.
Составляем четыре уравнения:
,.
,,.
,,.
, , .
Полином Жегалкина имеет вид:
.
Алгоритм построения СДНФ по таблице истинности функции состоит из трех шагов.
В таблице истинности выбираются наборы, на которых функция принимает значение 1 (единицы).
Для наборов, выбранных на первом шаге, составляются конституенты единицы, в которые переменная входит с инверсией, если в соответствующем наборе она принимает значение 0 (ноль), и без инверсии, если в соответствующем наборе она принимает значение 1 (единицы).
Составляется дизъюнкция построенных на втором шаге конституент единицы.
Согласно алгоритму получаем СДНФ:
.
Упростим СДНФ, используя склеивание по у и закон Блейка-Порецкого:
.
Алгоритм построения СКНФ по таблице истинности функции содержит три шага.
В таблице истинности функции выбираются наборы, на которых функция принимает значение 0 (нуля).
Для этих наборов составляются конституенты нуля, в которые переменная входит с инверсией, если в наборе она принимает значение единицы, и без инверсии, если в наборе она принимает значение нуля.
Составляется конъюнкция построенных на предыдущем шаге конституент нуля.
Согласно алгоритму получаем СКНФ:
.
б) Составим для функции таблицу истинности.
x y z
0 0 0 1 1 1 1
0 0 1 1 0 0 0
0 1 0 0 1 1 0
0 1 1 0 0 0 1
1 0 0 0 1 0 1
1 0 1 0 0 1 0
1 1 0 0 1 0 1
1 1 1 0 0 1 0
Построим полином Жегалкина.
Воспользуемся методом неопределенных коэффициентов
.
Полином Жегалкина булевой функции трех переменных имеет вид:
.
Составляем восемь уравнений:
,.
,,.
,,.
, ,.
,,.
, , .
, , .
,
,.
Полином Жегалкина имеет вид:
.
Составим СДНФ:
.
Составим СКНФ:
.
Минимизируем функцию в базисе СДНФ, т.е. найдем МДНФ. Составим диаграмму (карту) Вейча (Карно), записав единицы в клетки диаграммы, которые соответствуют конституентам единицы, входящим в данную функцию, а в остальных клетках записываем нули (или можно и не писать их, оставив клетки пустыми).
Покажем вначале на диаграмме Вейча для функции трех переменных наборы.
y
x 111 110 100 101
011 010 000 001
z z
Для нашей функции
y
x
1 1
1
1
z z
Сама минимизация производится по следующим правилам:
1
Задать вопрос
на новый заказ в Автор24.
