2.5.
Логические формулы. Таблицы истинности
Применяя введенные логические
операции, можно из простых высказываний составить высказывания сколь угодно
сложного вида. Например,
A ®ВÚС;
(A « 
Ú
) ® Ù ;
B ® Ú (С
Ù B) « (A Ú B) Ù ® С и т.д.
Такие высказывания называются логическими формулами или булевыми функциями, а входящие в них
простые высказывания – логическими
переменными. Символы Ø, Ù, Ú, ®, « называют логическими связками.
Формулы логики
высказываний можно рассматривать двояко.
1. Принимая А, В, С за обозначение простых высказываний, логическая
формула будет представляться как определенное сложное высказывание. Например,
если обозначить А – «Будет дождь», В – «Я возьму зонт», С – «Я надену плащ», то A®ВÚС – запись
сложного высказывания «Если будет дождь,
то я возьму зонт или надену плащ».
2. Если рассматривать буквы А, В,
С
в качестве переменных, принимающих два значения 1 и 0, то в этом случае
логическая формула является булевой функцией.
Для правильного вычисления значения
логических формул необходимо задать порядок выполнения логических операций.
Сначала выполняется операция отрицания Ø, затем конъюнкция Ù
и дизъюнкция Ú (они равноправны), затем импликация ® и,
последней, эквивалентность «. Как и в алгебре, скобки необходимы
для изменения порядка действий, а равноправные операции вычисляются слева
направо.
Таким образом, для вычисления
значения выражения (A « 
Ú) ® Ùнеобходимо
сначала определить и , затем
выполнить дизъюнкцию Ú,
после этого подсчитать значение выражения, стоящего в скобках: A«Ú,
далее выполнить конъюнкцию высказываний Ù и, наконец, соединить вычисленные значения высказываний A «Ú и Ù с помощью импликации: (A « Ú) ® Ù. Порядок выполнения операций будет таков:
.
Пусть простые высказывания А и В
истинны: А=1, В=1. Тогда и являются ложными высказываниями: =0, =0.
Также ложной будет и дизъюнкция Ú=0.
Значение высказывания в скобках A«Ú=0,
так как эквивалентность истина«ложь дает ложь. Конъюнкция ложных высказываний Ùтакже ложна: Ù=0. Результирующее высказывание представляет собой соединение
ложь®ложь, что по определению операции
импликация есть истина. Значит, (A « Ú) ® Ù=1 при А=1 и В=1.
Вычислим значение истинности
рассмотренной логической формулы при всевозможных комбинациях значений логических
переменных, составляющих эту формулу. Делать такие вычисления удобнее с помощью
таблицы, в каждой строке которой анализируется одна комбинация значений простых
высказываний, а в столбцах вычисляются все операции по порядку. Такие таблицы,
построенные для сложных высказываний, называются таблицами истинности или таблицами Куайна.
Таблица истинности – перебор всех возможных комбинаций значений простых высказываний, из
которых состоит сложное, и указание соответствующих значений сложного
высказывания.
Построим таблицу истинности для
приведенного выше сложного высказывания:
(A « Ú) ® Ù.
Так как и А, и В могут принимать два
значения, то различных комбинаций значений А и В будет четыре:
А=1, В=1;
А=1, В=0;
А=0, В=1;
А=0, В=0.
Вычислим значение сложного
высказывания в каждом случае по действиям.
|
А |
В |
|
|
|
A« |
|
(A « |
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
Двойной чертой отделяем значения исходных переменных
от вычисляемых значений по определениям логических операций.
Если логическая формула состоит из
трех переменных А, В и С,
то строк в таблице истинности будет 8. Действительно, для каждого значения
высказывания С, а их два: истина и
ложь, существуют 4 комбинации значений А
и В. Все логические возможности
значений высказываний А, В
и С можно проиллюстрировать с помощью
так называемого дерева логических возможностей:
|
А |
|
|
0 |
1 |
|
0 |
|
|
1 |
|
0 |
1 |
|
0 |
|
В |
|
1 |
|
|
0 |
|
|
|
|
1 |
|
|
0 |
|
|
С |
|
|
|
|
|
1 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Если в сложном высказывании – n простых, то логических возможностей – строк таблицы
истинности будет 
. К примеру, при n=10, число различных комбинаций
значений переменных - число строк
таблицы 
.
Пример 4.1. Построить таблицу истинности
логической формулы:
B ® Ú (С Ù B) « (A Ú B).
Решение.
Сначала определим порядок вычисления логических операций:
.
Вычислим значения сложного
высказывания по действиям для каждого из 8 возможных комбинаций простых.
|
А |
В |
С |
С Ù
B |
A Ú
B |
|
|
B
®
|
B
®
|
|
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |