Главная | Обратная связь

Порядок выполнения работы

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

 

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

 

Введение

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

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

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

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

 

Пример 1

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

 

Номер набора	x	y	z	f(x,y,z)

 

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

Решение

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

Для представления сокращенной записи СДНФ этой функции необходимо под знаком обобщенной дизъюнкции (å или 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

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

 

Пример 2

Пусть ФАЛ задана сокращенной записью СДНФ:

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

Представить таблицу истинности, а также полную и сокращенную записи СКНФ этой функции.

Решение

Получение таблицы истинности

Этап 1.

Подготовить ТИ для логической функции трех переменных:

 

Номер набора	x	y	z	f(x,y,z)

 

Этап 2.

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

 

Номер набора	x	y	z	f(x,y,z)

 

Этап 3.

Записать 0 в качестве значения функции в остальные строки таблицы:

 

Номер набора	x	y	z	f(x,y,z)

 

Таблица истинности получена.

 

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

Получение СКНФ по ТИ описано в примере 1.

Результатом будет:

f(x,y,z)_СКНФ = ∏(3,4,6) = (x V ¯y V`z ) & (`x V y V z ) & (`x V`y V z)

 

Пример 3

Пусть ФАЛ задана сокращенной записью СКНФ:

f(x,y,z)_СКНФ = Õ(2,3,4,5,7)

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

Решение

Так как получение ТИ в данном примере не требуется, то можно использовать следующий подход.

Этап 1.

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

f(x,y,z)_СДНФ = å(0,1,6)

Этап 2.

Получить полную запись СДНФ согласно указаниям примера 1. Результатом будет:

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

 

Пример 4

Пусть ФАЛ задана в виде СДНФ:

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

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

Решение

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

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

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

Затем представим эти наборы в десятичном коде и перечислим их под знаком обобщенной дизъюнкции:

f(x,y,z)_СДНФ = å(4,1,2,7)

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

f(x,y,z)_СКНФ = Õ(0,3,5,6)

По сокращенной записи СКНФ получим ее полную запись согласно методике, изложенной в примере 1:

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

 

Пример 5

Пусть ФАЛ задана в виде СКНФ:

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

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

Решение

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

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

0 1 0 0 1 1 1 0 1

Затем представим эти наборы в десятичном коде и перечислим их под знаком обобщенной конъюнкции:

f(x,y,z)_СКНФ = Õ(2,3,5)

По полученной сокращенной записи СКНФ функции получим сокращенную запись СДНФ, перечислив под знаком обобщенной дизъюнкции å номера наборов, не вошедших в сокращенную запись СКНФ:

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

По сокращенной записи СДНФ получим ее полную запись согласно методике, изложенной в примере 1:

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

Порядок выполнения работы

После запуска программы открывается главное окно (рис. ), позволяющее выбрать режим работы.

 

Рис. Главное окно обучающей программы по формам представления логических функций

 

Если работа выполняется без оценки, то обучаемый должен нажать кнопку «Старт» и перейти к окну тренировочного режима (рис. ).

Рис. Окно тренировочного режима

 

Здесь он может выполнить предложенное ему задание, получить новое задание того же типа (кнопка «Следующее задание»), перейти к выполнению заданий других типов или вернуться на главную форму урока, чтобы перейти к выполнению работы в режиме контрольного тестирования (кнопка «Вернуться»).

При выполнении задания в тренировочном режиме обучаемый по кнопке «Теория» может обратиться к теоретическому материалу по данной теме.

Выполнение каждого задания складывается из выполнения 4 пунктов. Правильность выполнения каждого из пунктов можно проверить, нажав кнопку «ОК» рядом с соответствующим полем. При этом обучающая программа или подтверждает правильность выполнения пункта задания, или сообщает об ошибке и предлагает либо показать правильное значение (кнопка «Показать ответ»), либо попытаться ещё раз самостоятельно выполнить этот же пункт задания (кнопка «Попробовать ещё») (рис. ).

Рис. Окно проверки выполнения пунктов задания в тренировочном режиме

 

Для выполнения урока в контрольном режиме необходимо в главном окне программы поставить флажок «С оценкой» и нажать кнопку «Старт».

В этом режиме задания предлагаются для выполнения последовательно. После выполнения каждого задания необходимо нажать кнопку «ОК». При этом обучающая программа отмечает правильно выполненные пункты задания. Для пунктов, выполненных с ошибками, показывается правильный результат (рис. ). За каждый правильно выполненный пункт задания, начисляется определённое количество баллов. Правильное заполнение таблицы истинности, а также сокращённых записей нормальных форм оценивается в 1 балл. Правильное получение совершенной нормальной формы оценивается в 2 балла.

 

Рис. Окно оценки текущих результатов выполнения контрольного задания

 

Для перехода к выполнению следующего задания необходимо нажать кнопку «ОК» в окне текущих результатов. В любой момент посмотреть текущие результаты выполняемой работы можно, нажав кнопку «Результаты» на главной панели.

После выполнения всех 5 заданий на основании набранного общего количества баллов выставляется оценка.