Информатика и ИКТ подготовка к ЕГЭ
Построение формул по заданным таблицам истинности - Построение алгебры высказываний - Краткий теоретический справочник
Рассмотрим вначале решение этой задачи на примере. Пусть формула F = F(A1, A2, A3) от трёх высказывательных переменных задана таблицей истинности (см. табл. 1.7).
Таблица 1.7. Таблица истинности формулы от трёх высказывательных переменных.
|
A1 |
А2 |
А3 |
F(A1, A2, A3) |
|
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
|
0 |
0 |
0 |
0 |
Понятно, что существует бесконечно много равносильных формул алгебры высказываний, имеющих эту таблицу истинности. Укажем способ нахождения двух таких формул.
Помечаем те строки таблицы, в которых F(A1, A2, A3) принимает значение, равное 1. Это строки 1, 3, 7. Для каждой строки (логической возможности) составим формулу, истинную только в этой логической возможности и ложную во всех остальных логических возможностях
1-я строка — А1 ^ А2 ^ А3
3-я строка — А1 ^ ¬ А2 ^ А3
7-я строка — ¬ А1 ^ ¬ А2 ^ А3.
Если возьмём теперь дизъюнкцию всех этих формул, то это и будет искомой формулой:
Рассмотрим другое решение этой задачи. Помечаем те строки таблицы, в которых F(A1, A2, A3) принимает значение, равное 0. Это строки 2, 4, 5, 6, 8. Для каждой логической возможности составим формулу, ложную только в этой логической возможности и истинную во всех остальных логических возможностях
2-я строка — ¬ А1 v ¬ А2 v А3
4-я строка — ¬ А1 v А2 v А3
5-я строка — А1 v ¬ А2 v ¬ А3
6-я строка — А1 v ¬ А2 v А3
8-я строка — А1 v А2 v А3.
Если теперь возьмём конъюнкцию этих формул, то это также будет искомой, то есть имеющей заданную таблицу истинности, формулой:
Формулы (1) и (2) равносильны, так как имеют одну и ту же таблицу истинности. В данном случае удобнее строить формулу (1).