Решение. Представление функций алгебры логики

Представление функций алгебры логики

Цель работы: изучение форм представления функций алгебры логики (ФАЛ) и получение навыков преобразования одной формы представления ФАЛ в другую.

Введение

Основная форма представления функций алгебры логики – таблица истинности (ТИ), которая определяет значение функции на всех наборах переменных.

Помимо таблицы истинности возможны и другие виды представления ФАЛ, наиболее распрост­раненными из которых являются совершенная дизъюнктивная нормальная форма, описывающая все наборы переменных, на которых функция принимает значение, равное 1, и совершенная конъюнктивная нормальная форма, описывающая все наборы переменных, на которых функция принимает значение, равное 0.

В данной работе изучаются способы перехода от одной формы представления ФАЛ к другим формам.

Рассмотрим способы перехода от одного вида представления ФАЛ к другому.

Пример 1

Пусть ФАЛ задана в виде таблицы истинности:

Получить СДНФ и СКНФ этой функции.

Решение

Получение СДНФ.

Для представления сокращенной записи СДНФ этой функции необходимо под знаком обобщенной дизъюнкции (å или V) перечислить через запятую номера всех наборов, на которых функция принимает значение, равное 1:

f (x, y, z)_СДНФ = å(0,3,4,5,7)

Примечания: данный вид представления функции является сокращенной записью СДНФ, а не записью со­кращенной дизъюнктивной нормальной формы.

Получение развернутой записи СДНФ включает следующие этапы.

Этап 1.

Записать дизъюнкцию k конъюнктивных термов, содержащих все переменные, от которых зависит функция, где k – количество наборов, на которых функция принимает значение, равное 1, то есть количество наборов, перечисленное в сокращенной записи СДНФ:

f (x, y, z) = xyz V xyz V xyz V xyz V xyz

Этап 2.

Записать под каждым термом двоичный эквивалент одного из наборов, на которых функция принимает значение, равное 1:

f (x, y, z) = xyz V xyz V xyz V xyz V xyz

000 011 100 101 111

Этап 3.

Расставить знаки отрицания над теми переменными, которым в двоичном эквиваленте соответствует 0:

f (x, y, z)_СДНФ =` x ` y ` z V ` x y z V x ` y ` z V x ` y z V x y z

0 0 0 0 1 1 1 0 0 1 0 1 1 1 1

Полученная запись представляет собой совершенную дизъюнктивную нормальную форму для функции, заданной исходной таблицей истинности.

Получение СКНФ

Для представления сокращенной записи СКНФ этой функции необходимо под знаком обобщенной конъюнкции (Õ или Λ) перечислить через запятую номера всех наборов, на которых функция принимает значение, равное 0:

f (x, y, z)_СКНФ = Õ (1,2,6)

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

Получение развернутой записи СКНФ включает следующие этапы.

Этап 1.

Записать конъюнкцию m дизъюнктивных термов, содержащих все переменные, от которых зависит функция, где m – количество наборов, на которых функция принимает значение, равное 0, то есть ко­ли­чест­во наборов, перечисленное в сокращенной записи СКНФ:

f (x, y, z) = (x V y V z) & (x V y V z) & (x V y V z)

Этап 2.

Записать под каждым термом двоичный эквивалент одного из наборов, на которых функция принимает значение, равное 0:

f (x, y, z) = (x V y V z) & (x V y V z) & (x V y V z)

0 0 1 0 1 0 1 1 0

Этап 3.

Расставить знаки отрицания над теми переменными, которым в двоичном эквиваленте соответствует 1:

f (x, y, z)_СКНФ = (x V y V` z) & (x V` y V z) & (` x V` y V z)

0 0 1 0 1 0 1 1 0

Полученная запись представляет собой совершенную конъюнктивную нормальную форму для функции, заданной исходной таблицей истинности.