Логические функции.
Таким образом, логика – наука о законах, формах и операциях правильного мышления, зародившаяся еще до нашей эры, находит в настоящее время активное применение в вычислительной технике: как в аппаратной части устройств, так и в программной.
Логика оперирует логическими величинами – понятиями выражаемыми словами ИСТИНА или ЛОЖЬ. Символически записанные логические величины называются логическими переменными.
Логические функции – это функции логических переменных, соответственно принимающие значение ЛОЖЬ или ИСТИНА. Для наглядности логической функции строят таблицу истинности, из которой видно, что при различных значениях входных логических переменных должно быть на выходе функции.
Самые известные логические функции И, ИЛИ, НЕ. Рассмотрим примеры и таблицы истинности данных функций. Начнем с функции И – логическое умножение. Данная функция становится истинной только в том случае, если истинны обе входные переменные.
вход 1 |
вход 2 |
функция И |
|
подал документы |
наличие высокого балла |
зачисление в институт |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
1 |
|
1 |
1 |
1 |
Рисунок 5. Функция И.
Как видно из примера (смотри Error: Reference source not found), чтобы быть зачисленным в институт, надо получить высокий суммарный балл (в данном примере не конкретизируется термин «высокий») и подать документы. Наличие высокого балла без подачи документов не приведет к зачислению. Поданные документы при низком балле также не приводят к зачислению. В данном примере все условия должны быть выполнены. Если обозначить в примере вход 1 как a, а вход 2 как b, то функцию можно записать a*b или a˄b.
Функция И имеет также название конъюнкции.
Задание: привести примеры функции И.
Функция ИЛИ-логическое сложение. Становится истинной в случае, если хотя бы одна из входных переменных истинна (смотри Error: Reference source not found).
вход 1 |
вход 2 |
функция ИЛИ |
|
призер олимпиад |
наличие высокого балла |
зачисление в институт |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
1 |
|
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
Рисунок 6. Функция ИЛИ.
Пример рассматривается при наличии школьного аттестата (предполагающего сданные экзамены) и поданных документов, для зачисления в институт. Поступление возможно при наличии высокого балла. Поступление также возможно, если абитуриент является призером олимпиад. Если абитуриент одновременно и призер, и имеет высокий балл, он также поступит. В данном примере достаточно выполнения хотя бы одного условия. Функция ИЛИ записывается как a+b или a˅b
Задание: привести примеры функции ИЛИ.
Альтернативный вариант названия функции ИЛИ – функция дизъюнкции.
Обе функции (И и ИЛИ) могут иметь на входе более двух переменных (смотри Error: Reference source not found).
вход 1 |
вход 2 |
вход3 |
функция И |
|
вход 1 |
вход 2 |
вход 3 |
функция ИЛИ |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
|
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
Рисунок 7. Функции трех логических переменных.
Функция НЕ – функция отрицание – функция одной переменной (смотри Error: Reference source not found). Функция НЕ записывается как ¬а.
вход 1 |
функция НЕ |
0 |
1 |
1 |
0 |
Рисунок 8. Функция отрицания.
На самом деле логических функций намного больше, чем три перечисленные: если рассмотреть все вероятные функции от двух переменных (а их шестнадцать - 24), то (смотри Error: Reference source not found) можно увидеть:
уже знакомые функции И (f2) ИЛИ (f8),
постоянно ложную (f1) и постоянно истинную (f16) функции,
отрицание И (f15), имеющую название И-НЕ, иначе Штрих Шеффера,
отрицание ИЛИ (f9), имеющую название ИЛИ-НЕ, иначе Стрелка Пирса,
сложение по модулю 2 (f7),
и прочие.
x1 |
x2 |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
f12 |
f13 |
f14 |
f15 |
f16 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
Рисунок 9. Полный перечень функций двух переменных.
В рамках логики доказано, что любую функцию любого количества переменных можно выразить через так называемый базис – набор логических функций, которые позволяют выразить любую функцию. И одним из базисов является набор функций И, ИЛИ ,НЕ.
Задание: написать через базис И, ИЛИ, НЕ функцию, реализующую следующую таблицу истинности (смотри Error: Reference source not found).
подача документов |
призер олимпиад |
наличие высокого балла |
Функция поступление в институт |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
Рисунок 10. Таблица истинности функции поступления в институт от трех логических переменных.
Задание: реализовать функции Стрелка Пирса и Штрих Шеффера через базис И, ИЛИ, НЕ.
Альтернативные варианты базисов – использование так называемой Стрелки Пирса или Штриха Шеффера. Любая из них является базисом и позволяет реализовать функцию любой сложности на своей основе.
Задание: реализовать функции И, ИЛИ, НЕ через стрелку Пирса и через Штрих Шеффера.
Существуют законы алгебры логики, позволяющие преобразовывать сложные логические выражения.
Закон |
Для ИЛИ |
Для И |
|
Переместительный (коммутативности) |
|
|
|
Сочетательный (ассоциативности) |
|
|
|
Распределительный (дистрибутивности) |
|
|
|
Правила де Моргана |
|
|
|
Идемпотенции (рефлексивности) |
|
|
|
Поглощения |
|
|
|
Склеивания |
|
|
|
Операция переменной с ее инверсией |
|
|
|
Операция с константами |
|
|
|
Двойного отрицания |
|
||
Альтернативный
вариант преобразования –составить
таблицу истинности и проанализировать
ее. В качестве наглядной демонстрации
разберем пример преобразования выражения
.
При составлении таблицы истинности определим приоритет действий и выполним преобразования в соответствии с приоритетом. Первое действие a∧b (смотри Error: Reference source not found), далее – инверсия полученного на первом шаге результата (¬(a∧b)). Далее, полученный на втором шаге результат логически умножается на b (¬(a∧b) ∧b). На четвертом (последнем) шаге результат третьего шага логически умножается на b. Полученный на финальном шаге результат анализируется: получается, что значения функции на выходе полностью совпадает со значением логического входа b. Результат упрощения функции ¬(a∧b) ∧b∨b=b.
a |
b |
a∧b |
¬(a∧b) |
¬(a∧b)∧b |
¬(a∧b) ∧b∨b |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
Рисунок 11. Упрощение сложной функции при помощи таблицы истинности.
Те же самые преобразования проведем с использованием законов логики.
¬(a∧b)= ¬a∨¬b по правилу Моргана.
(¬a∨¬b) ∧b =(¬a∧b) ∨(¬b∧b) по закону дистрибутивности.
(¬b∧b) =0 умножение логической переменной на ее отрицание
(¬a∧b) ∨0=(¬a∧b) логическое сложение логической переменной с нулем
(¬a∧b) ∨(¬b∧b) =(¬a∧b)
(¬a∧b) ∨b=b закон поглощения.
Таким образом, путем последовательных преобразований при помощи законов логики приходим к такому же результату: ¬(a∧b) ∧b∨b=b.
Задание: Упростить данную форму:
таблица
истинности функций приводится:
x |
y |
Сложение
по модулю два
|
Импликация
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
Рисунок 12. Таблицы истинности логических функций сложение по модулю два и импликации.
Как было сказано, все перечисленные функции могут быть реализованы в виде логических элементов на транзисторах. Рассмотрим, что такое транзистор.