Построение таблиц истинности для логических функций
Логическая
функция – это функция, в которой
переменные принимают только два
значения: логическая единица или
логический ноль. Истинность или ложность
сложных суждений представляет собой
функцию истинности или ложности простых.
Эту функцию называют булевой функцией
суждений
.
Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записывается набор аргументов, а в правой – соответствующие значения логической функции.
При построении таблицы истинности необходимо учитывать порядок выполнения логических операций. Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке: инверсия; конъюнкция; дизъюнкция; импликация и эквивалентность.
Для изменения указанного порядка выполнения логических операций используются круглые скобки.
Алгоритм построения таблицы истинности
1.Определить
количество наборов входных переменных
– всевозможных сочетаний значений
переменных, входящих в выражения, по
формуле:
,
где
–
количество входных переменных. Оно
определяет количество строк таблицы.
2.Внести в таблицу все наборы входных переменных.
3.Определить количество логических операций и последовательность их выполнения.
4.Определить количество столбцов таблицы, равное сумме количества переменных и количества операций.
5.Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности.
Пример.
Построить таблицу истинности для
логической функции
.
Количество входных
переменных в заданном выражении равно
трем (А, В, С). Значит, количество
входных наборов
.
Столбцы таблицы
истинности соответствуют значениям
исходных выражений А, В, С, промежуточных
результатов
и
,
а также искомого окончательного
значения сложного арифметического
выражения
.
Таблица 9 |
|||||
|
|
|
|
|
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: 1 и 0.
Электронные схемы, которые преобразовывают сигналы только двух фиксированных напряжений электрического тока, стали называть логическими элементами.
Логические элементы имеют один или несколько входов и один выход, через которые проходят электрические сигналы, обозначаемые условно 0, если «отсутствует» электрический сигнал, и 1, если «имеется» электрический сигнал.
Простейшим логическим элементом является инвертор, выполняющий функцию отрицания. Если на вход поступает сигнал, соответствующий 1, то на выходе будет 0. И наоборот. У этого элемента один вход и один выход (рис. 1).
Рис. 1. Инвертор. |
Рис. 2. Дизъюнктор. |
Рис. 3. Конъюнктор. |
Логический элемент, выполняющий логическое сложение, называется дизъюнктор. Он имеет, как минимум, два входа (рис. 2).
Логический элемент, выполняющий логическое умножение, называется конъюнктор. Он имеет, как минимум, два входа (рис. 3).
В логических системах применяются универсальные логические операции, реализуемые базовыми элементами. Они включают две следующие разновидности:
1. Функция Шеффера. Отражает операцию И-НЕ, обозначается символически вертикальной черточкой – штрих Шеффера (рис. 4).
Рис. 4. Операция И-НЕ. |
Рис. 5. Операция ИЛИ-НЕ. |
Для простейшей функции двух переменных
и
получают:
Таблица 10 |
||
|
|
|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
2. Функция Пирса. Отражает операцию ИЛИ-НЕ, обозначается символически вертикальной стрелкой – стрелка Пирса (рис. 5).
Для простейшей функции двух переменных и получают:
Таблица 11 |
||
|
|
|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
