|
Ответить на вопрос об истинности или ложности некоторого
сложного высказывания, иногда бывает удобно и просто,
построив таблицу истинности для имеющегося логического
выражения. Для построения таблицы истинности необходимо
выполнить следующие действия.
- Определить количество переменных, входящих в формулу,
и составить таблицу всевозможных значений переменных
(если количество переменных n,
то количество различных наборов переменных будет 2n).
Конкретные наборы можно рассматривать как числа в
двоичной системе счисления и располагать их в порядке
возрастания от 0 до 2n-1.
- Провести анализ построения формулы алгебры
высказываний с учетом расположения скобок и
приоритетности порядка выполнения логических операций.
Выписать саму формулу, затем ее главные подформулы,
затем под каждой подформулой снова выписываем главные
подформулы и т.д..
- Определяем количество строк и столбцов в таблице.
Количество столбцов в таблице равно сумме количества
простых переменных, и количества выделенных подформул
плюс один столбец на саму формулу. Количество строк
равно 2n+1,
дополнительная строка добавляется для записи переменных,
подформул и самой формулы.
- Поэтапно заполнять таблицу истинности, двигаясь слева
направо, для всех подформул (удобнее по порядку их
выполнения).
Пример 1: Построить таблицу истинности и
определить логическое значение формулы:
((С\/В)→В)/\(А/\В)→В
|
A |
B |
C |
С/\В |
(С\/В)→В |
А/\В |
((С\/В)→В)/\(А/\В) |
F |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
|
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Если в результате заполнения таблицы истинности,
получается высказывание истинное при любом наборе
переменных входящих в это высказывание, то исходное
высказывание называется тождественно-истинным.
Иногда тождественно-истинные формулы называют
тавтологиями.
Если же в результате заполнения таблицы истинности,
получается высказывание ложное при любом наборе входящих
переменных, то исходное высказывание называется
тождественно-ложным или противоречием.
Если высказывание не является ни тождественно истинным,
ни тождественно-ложным, то говорят, что это
высказывание выполнимо или нейтрально.
В построенной таблице истинности, при любом наборе
значений, входящих в нее переменных исходная формула
алгебры высказываний принимает значение – 1, значит, эта
формула является тождественно-истинной.
Пример 2. Построить таблицу истинности для
логической функции:
Воспользовавшись приведенным выше алгоритмом построения
таблиц истинности, определяем:
- количество логических переменных – 2, следовательно,
различных наборов значений переменных – 4, строк в
таблице – 5.
- количество выделенных подформул – 3, следовательно,
количество столбцов в таблице – 6.
- строим по
заданным параметрам таблицу истинности:
Анализируя полученную таблицу истинности, видим, что
истинностные значения заданной формулы
точно
совпадают со значением логической переменной А. Они либо
одновременно ложны, либо одновременно истинны. Такие
формулы называются равносильными или
эквивалентными. Равносильные формулы могут содержать
различное количество логических переменных. Для
установления равносильности важно, чтобы формулы, имели
одинаковые значения при одинаковых наборах значений
переменных. Для обозначения равносильности используется
знак равенства. Таким образом, для рассмотренного
примера мы можем записать:
 .
Кроме понятия равносильности формул, для определения
отношения между различными формулами пользуются также
такими понятиями как:
- противоположность;
- совместимость и несовместимость;
- логическое следование.
Две формулы алгебры высказываний называются
противоположными или инверсными, если при
любом наборе значений переменных они принимают
противоположные значения.
Две формулы алгебры высказываний называются
совместимыми, если хотя бы при одном наборе значений
переменных они одновременно принимают значения «истина»,
в противном случае они являются несовместимыми.
Формула В является логическим следствием формулы А,
если при любых наборах значений переменных, входящих в
формулы, импликация А→В принимает значение «истина».
Что бы выполнить обратную задачу, а именно, по таблице
истинности, при заданном наборе переменных восстановить
исходную формулу алгебры высказываний, или получить
формулу равносильную исходной необходимо выполнить
следующие действия:
- определить контрольные точки (если функция принимает
значение «истина» меньшее число раз, чем значение
«ложь», то в качестве контрольных точек удобнее
использовать наборы значений переменных, при которых
функция принимает значение «истина»);
- записать конъюнкции логических переменных для каждой
контрольной точки, записывая саму переменную, если ее
значение в данном наборе истинно и отрицание переменной,
если ее значение в данном наборе ложно;
- объединить полученные конъюнкции дизъюнкциями;
- если возможно, упростить полученное выражение с
помощью законов алгебры высказываний.
Если функция чаще принимает значение «ложь», то в
качестве контрольных точек удобнее использовать наборы,
при которых функция ложна. В этом случае для каждой
контрольной точки необходимо записывать дизъюнкции и
объединять их конъюнкциями. |
