3 Практическая часть

Задача 3.1 Построить СДНФ и СКНФ для функции, таблица истинности которой имеет следующий вид:

х	y	z	f(x,y,z)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

Решение.

Построение СДНФ. Функция принимает значение 1 на кортежах (001), (010), (101). Кортежу (001) соответствует элементарная конъюнкция . Кортежу (010) соответствует элементарная конъюнкция . Кортежу (101) соответствует элементарная конъюнкция . Получаем СДНФ f(x,y,z)= .

Построение СКНФ. Функция принимает значение 0 на кортежах (000), (011), (100), (110), (111). Кортежу (000) соответствует элементарная дизъюнкция . Кортежу (011) - , кортежу (100) - , кортежу (110) - , кортежу (111) - .

Получаем СКНФ f(x,y,z)=( )( )( )( )( ).

4 Практические задания

4.1 Построить СДНФ и СКНФ.

Вариант 1 а) ; б) ; в) .	Вариант 2 а) ; б) ; в) .
Вариант 3 а) б) в)	Вариант 4 . а) б) в) .

5 Контрольные вопросы

1) Дайте определение ДНФ и КНФ.

2) Дайте определение СДНФ и СКНФ.

3) Каков алгоритм построения СДНФ?

4) Каков алгоритм построения СКНФ?

Практическая работа № 6. Минимизация алгебраических преобразований.

1 Цель работы

Научиться минимизировать формулы алгебры высказываний.

2 Теоретическая часть

Очень часто СДНФ и СКНФ, которые строятся по таблице истинности, оказываются весьма сложными. Поэтому возникает проблема построения минимальных форм для данной функции.

Импликант булевой функции f - булева функция g, такая, что для любых наборов значений аргументов этих функций из равенства g=1 следует, что f=1. Если отбрасывание любой переменной импликанта приводит к тому, что полученная функция перестает быть импликантом, то такой импликант называется простым.

Сокращенная ДНФ функции f есть дизъюнкция всех простых импликантов функции f. Всякая функция реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.

Алгоритм построения сокращенной ДНФ с помощью СКНФ.

1. По таблице истинности строим СКНФ функции f.

2. В СКНФ раскрываем скобки, удаляем дублирующие элементы ( А˄А=А, А˅А=А) и элементы, которые содержат переменную с её отрицание ( А˄Ā=0)

3. Проводим поглощение (А˅АВ=А) и удаляем дублирующие элементы. Получаем сокращенную ДНФ для функции f.

3 Практическая часть

Задача 3.1 Построить сокращенную ДНФ для функции, таблица истинности которой имеет следующий вид:

x	y	z	f(x,y,z)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

Решение.

Построение СДНФ. Функция принимает значение 1 на кортежах (001), (010), (101). Кортежу (001) соответствует элементарная конъюнкция . Кортежу (010) соответствует элементарная конъюнкция . Кортежу (101) соответствует элементарная конъюнкция . Получаем СДНФ f(x,y,z)= ˅ ˅ .

Построение СКНФ. Функция принимает значение 0 на кортежах (000), (011), (110), (111). Кортежу (000) соответствует элементарная дизъюнкция x˅y˅z. Кортежу (011) - x˅ ˅ , кортежу (100) - ˅y˅z, кортежу (110) - ˅ ˅z, кортежу (111) - ˅ ˅ .

Получаем СКНФ f(x,y,z) =( x˅y˅z)( x˅ ˅ )( ˅y˅z)( ˅ ˅z)( ˅ ˅ ). Далее проводим упрощение по алгоритму. Перемножение лучше начинать со скобок, которые отличаются всего одной переменной (например, z и ). Поэтому поменяем местами 2-ую и 3-ю скобки. Получаем сокращенную ДНФ y ˅ z.