Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
В алгебре используются три основных закона: переместительный, сочетательный и распределительный. В алгебре логики кроме трех перечисленных законов используется четвертый — закон отрицания. Кроме того, распределительный закон алгебры логики имеет две модификации. Можно также считать, что в алгебре логики используется два распределительных закона (первый и второй). Рассмотрим законы алгебры логики.
Формулировка: логические переменные можно менять местами. Возможные варианты записи:
и
Формулировка: логические переменные в конъюнкциях и дизъюнкциях можно объединять в группы. Возможные варианты записи:
Формулировка: одинаковые переменные в конъюнкциях и дизъюнкциях можно выносить за скобки. Закон имеет две модификации. Первая модификация называется распределением конъюнкции по дизъюнкции. Форма записи закона в первой модификации:
Вторая модификация закона называется распределением дизъюнкции по конъюнкции. Форма записи закона во второй модификации:
Распределительный закон в первой модификации аналогичен распределительному закону обычной алгебры. Вторая модификация закона применима только к логическим функциям.
Закон отрицания имеет две формулировки. Первая: отрицание от конъюнкции равно дизъюнкции отрицаний переменных. Форма записи:
Вторая формулировка: отрицание от дизъюнкции равно конъюнкции отрицаний переменных. Формы записи:
Следует обратить внимание на то, что отрицание от отрицания переменной равно самой переменной. Законы алгебры логики и следствия из них используются для преобразования и упрощения логических функций. Для этих же целей применяются так называемые тождественные соотношения. Рассмотрим тождественные соотношения, а затем следствия из законов алгебры логики.
Тождественные соотношения проверяются подстановкой возможных значений логических переменных. Основные тождественные соотношения:
1)
2)
3)
4)
5)
6)
7)
8)
В тождествах 6, 7, 8 символом F обозначена любая логическая функция или переменная.
Следствия из законов алгебры логики применяются в качестве правил для упрощения логических функций. Упрощение логических функций называется также минимизацией, а упрощенная функция — минимальной. Минимальная функция обычно записывается в ДНФ. Она содержит наименьшее количество конъюнкций минимально возможного ранга. Минимальная логическая функция не поддается дальнейшему упрощению. Для минимизации логических функций используются следующие правила: поглощения, свертки, расширения и склеивания. Рассмотрим эти правила.
Данное правило является следствием из распределительного закона. Оно может быть записано в следующем виде:
Правило доказывается следующим образом. Переменная x1 общая для всех конъюнкций, выносится за скобки, т. е.
При получаем
Выражение равно единице и, следовательно, правило доказано. Вид правила может быть различным. Важным является то, что одна конъюнкция должна быть общей группой для всех других конъюнкций. Например:
Правило является следствием второго распределительного закона. Запись правила:
а)
б)
Доказательство. К левой части выражения применяется второй распределительный закон, т. е.
Первая скобка правой части равна единице, поэтому . Также доказывается равенство .
Правило записывается в следующем виде:
Понятие расширения объясняется возможностью добавления к правой части конъюнкции x2x3. Справедливость правила доказывается искусственным приемом. Конъюнкция x2x3 умножается на дизъюнкцию , а затем делаются простые преобразования, т. е.
Правило склеивания базируется на понятии соседних конъюнкций. Соседними называются конъюнкции, отличающиеся представлением одной переменной. Например, конъюнкции являются попарно соседними. В первой паре конъюнкции отличаются представлением x2, а во второй — представлением x1. По этим переменным конъюнкции склеиваются.
Формулировка правила: две соседние конъюнкции склеиваются с образованием одной конъюнкции меньшего ранга; исчезает та переменная, по которой конъюнкции склеиваются.
Пример: Задана логическая функция в СДНФ .
Необходимо упростить функцию. Так как конъюнкции функции соседние и отличаются представлением x1 то путем их склеивания получаем . Справедливость преобразования (склеивания) доказывается вынесением общих переменных в конъюнкциях за скобку, т. е.
При решении логических задач следует строго соблюдать порядок выполнения логических операций, согласно их приоритету:
1. инверсия
2. конъюнкция
3. дизъюнкция
4. равнозначность.
Задачи по преобразованию логических функций весьма разнообразны. Однако их можно подразделить на следующие типовые группы:
• упрощение логических функций, заданных различным образом;
• построение таблиц истинности функций;
• вычисление значения логического выражения для заданного набора значений переменных;
• определение тождественности логических функций.
Пример 1. Упростить логическую функцию, заданную выражением
а) Приведение функции к ДНФ путем использования законов и правил, т. е.
б) Вычеркивание конъюнкций, равных нулю.
Конъюнкция , конъюнкции равны нулю, поэтому получаем упрощенную функцию
Пример 2. Упростить логическую функцию, заданную выражением
а) Применение закона отрицания с целью последующего перехода к ДНФ, т. е.
б) Анализ промежуточного результата. Устанавливаем, что первая скобка равна единице, так как и , где .
Окончательно получаем .
Пример 3. Упростить логическую функцию, заданную выражением
а) Упрощение функции путем использования закона отрицания и перемножения скобок
б) Применение правила расширения:
Окончательно получаем:
Покажем, что если применять другую последовательность исключения лишних конъюнкций, можно получить другой вид функции, которая не поддается дальнейшему упрощению.
Применяем правило расширения в следующей последовательности:
В результате получаем . Эта функция по рассмотренным правилам и законам упрощению не поддается.
Заметим, что если имеется несколько форм одной функции, не поддающихся дальнейшим упрощениям, то они называются тупиковыми. Одна из них является минимальной.
Пример 4. Упростить функцию , равную единице на наборах 3, 5, 6, 7 (011, 101, 110, 111).
а) Построение таблицы истинности (схема 1а).
В первых трех столбцах записываются возможные наборы. В столбце F на наборах 011, 101, 110 и 111 проставляются единицы; на остальных наборах проставляются нули.
б) Запись функции в СДНФ (см. правило записи).
Наборам 011,101,110,111 соответствуют конъюнкции
поэтому функция будет записана в следующем виде:
в) Упрощение функции. Функции, записанные в СДНФ, первоначально упрощаются по правилу склеивания. Затем применяются другие правила и тождественные соотношения.
В данной функции первые три конъюнкции являются соседними с четвертой. Функция не изменится, если к ней подписать еще две конъюнкции , т. е.
После склеивания пар соседних конъюнкций окончательно получим
Можно было не подписывать конъюнкцию , а просто склеить поочередно три первые конъюнкции с четвертой конъюнкцией.
Пример 5. Построить таблицу истинности функции: .
а) Запись заданной функции в СДНФ.
Данная функция зависит от трех переменных и записана в ДНФ. Для записи функции в СДНФ первая конъюнкция умножается на выражение , а вторая – на выражение . В скобках используются те переменные и их отрицания, которые отсутствуют в конъюнкциях:
б) Определение наборов, на которых функция принимает единичное значение.
Так как по правилу записи конъюнкций в СДНФ единице в наборе соответствует переменная, а нулю — ее отрицание, то конъюнкциям соответствуют наборы 111, 110, 011, 001, т. е. 7, 6, 3, 1.
в) Непосредственное построение таблицы.
В столбце F таблицы (см. схему 1б) на наборах 111, 110, 011, 001 проставляются единицы, а на остальных наборах ставятся нули.
Для вычисления значения логического выражения на заданном наборе значений переменных можно применять два способа: использование СДНФ и способ подстановки. Рассмотрим первый из них.
Пример 6. Вычислить значение логического выражения при х=1, у=1, z=0, т. е. на наборе 6, или 110.
а) Получение СДНФ заданной функции (см. выше пример 4):
После исключения повторяющейся конъюнкции получаем
б) Определение значения выражения.
Выражение V принимает единичное значение только на наборах 100, 000 и 101, или 4, 0, 5 так как задан набор 6, то логическое выражение принимает нулевое значение (V=0).
Второй способ не нуждается в особых пояснениях. При заданных значениях х=1, у=1 и z=0 имеем . Подставляем эти значения в выражение и получаем
В случае вычисления значений сложных логических выражений второй способ не исключает ошибок.
Тождественными являются те логические функции, которые имеют одинаковые СДНФ, т. е. одинаковые таблицы истинности. Поэтому при определении тождественности для логических функций должны быть построены таблицы истинности или получены СДНФ. Таблицы или СДНФ сравниваются и делается вывод о тождественности функций.
Пример 7. Проверить тождественность логических функций:
а) Упрощение функции F.
Применяем закон отрицания и перемножаем скобки, т. е.
Во второй скобке конъюнкции склеиваются, поэтому получаем
Переменная поглощает конъюнкцию , что дает
или
Функция F оказалась записанной в СДНФ, так как содержит конъюнкции одинакового ранга и в них входят все переменные, от которых она зависит.
б) Преобразование функции f.
Функция f также записана в СДНФ. Так как СДНФ функций F и f не совпадают, то они не являются тождественными.
в) Преобразование функции Р.
Получена СДНФ функции Р. Функции F и Р являются тождественными, так как имеют одинаковые СДНФ.
Пример 8. Проверить тождественность логических функций
которая принимает единичные значения на наборах 2, 3.
а) Упрощение функции F. Применяется закон отрицания
Во второй скобке переменная поглощает конъюнкцию , что приводит к следующему результату:
Во второй скобке используется правило свертки и затем скобки перемножаются:
б) Получение СДНФ функции F.
в) Получение СДНФ функции f.
Так как функция f принимает единичные значения на наборах 2 и 3, то ее СДНФ будет иметь вид
Функции F и f имеют одинаковые СДНФ, следовательно, они тождественны.
Пример 9. Проверить тождественность логических функций:
Функция f имеет следующую минимальную форму .
а) Упрощение функции F.
Перемножение скобок:
Исключение лишней конъюнкции из группы :
Исключение лишней конъюнкции yz из группы :
В результате получаем
Упрощенная форма функции F и минимальная форма функции f не совпадают. Однако это не значит что функции не тождественны. Для окончательного вывода нужно получить СДНФ обеих функций.
б) Получение СДНФ функции F.
После удаления повторяющихся конъюнкций получаем
в) Получение СДНФ функции f:
Функции F и f имеют одинаковые СДНФ и принимают единичные значения на одних и тех же наборах 0, 1, 3, 4, 6, 7. Эти функции тождественны. Так как минимальные формы функций не совпадают, то можно сделать вывод, что для функции F была получена тупиковая форма.
Задача. Построить таблицу истинности логической функции трех переменных и определить номера наборов, на которых функция равна 0.
Задача. Получить кратчайшую форму записи логической функции трех переменных