4.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 |
Предыдущая | Главная | Глава 4 | Следующая