Построение таблицы истинности по булевскому выражению
Построим таблицу истинности для следующей функции:
Так как п=3, то всего может быть 23 различных комбинаций значений аргументов.
Вычислим значение F
для каждого набора (
):
и т.д.
Таким образом, получим соответствующую таблицу истинности:
-
х1
х2
х3
F
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
Из приведенного примера видно, что построение таблицы истинности по логическому выражению сводится к вычислению значений этого выражения при всех возможных значениях аргументов.
Получение булевского выражения по таблице истинности
Правила построения булева выражения:
Для каждой строки таблицы истинности с единичным значением функции построить минтерм. Минтермом называется терм-произведение, в котором каждая переменная встречается только один раз – либо с отрицанием, либо без него. Переменные, имеющие нулевые значения в строке, входят в минтерм с отрицанием, а переменные со значением 1 – без отрицания.
Объединить все минтермы операцией дизъюнкции, что даст стандартную сумму произведений для заданной таблицы истинности.
Пример.
Дана таблица истинности:
-
х1
х2
х3
F
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
0
Построим булево выражение для F.
Найдем строки, в которых F=1. Это вторая, третья и шестая.
Для второй строки х1=0, х2=0,
х3=1. Эту строку описывает минтерм
.
Для третьей строки х1=0, х2=1,
х3=0. Эту строку описывает минтерм
.
Для шестой строки х1=1, х2=0,
х3=1. Эту строку описывает минтерм
.
Объединяя термы, получим булево выражение для F:
В это выражение вошли термы-произведения для строк с единичным значением функции F, а вся сумма соответствует совокупности из трех строк. Для остальных пяти наборов значений входных переменных это выражение равно нулю.
Таким образом, мы построили булево выражение по таблице истинности. В данном случае оно называется стандартной суммой произведений (канонической суммой минтермов, СДНФ).
Полученное таким образом выражение, как правило, можно упростить, пользуясь теоремами алгебры логики.