Дискретная математика (стр. 2 из 10)
Пример.
Логическая формула
задает функцию от трех переменных как суперпозицию функций одной и двух переменных.Для уменьшения числа скобок вводятся приоритеты операций. Наиболее приоритетна функция отрицания. Затем идет конъюнкция, после нее – дизъюнкция. Все другие функции имеют равный приоритет, меньший, чем у дизъюнкции. Очевидно, что скобками можно установить желаемый порядок операций. Вышеприведенная формула может быть эквивалентно записана так:
. Отметим, что используют и другое распределение приоритетов, в частности, полагая импликацию менее приоритетной, чем все другие функции.Логическая формула дает возможность построить соответствующий функциональный преобразователь, если мы имеем «элементарные» или «базисные» преобразователи. Для реализации преобразователя f примера выше необходимо иметь элементы, реализующие отрицание, дизъюнкцию, конъюнкцию и сложение по модулю два (см. рис. 1).
На этом рисунке представлен пример синтаксической структуры формулы – графическое представление формулы.
Рис. 1. Синтаксическая структура формулы
Очевидным образом по формуле можно построить табличное представление функции f.
Таблица 2
| p | q | r |  |  |  |  |  |  |
| 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
Суперпозицией нескольких простых булевых функций можно построить более сложную функцию, в частности, булеву функцию от большего числа переменных. Поставим вопрос: можно ли суперпозицией фиксированного набора функций представить любую булеву функцию от любого числа переменных? Удивительно, но ответ на этот вопрос положителен.
Штрих Шеффера является отрицанием конъюнкции, стрелка Пирса – отрицание дизъюнкции, сумма Жегалкина – отрицание эквивалентности.
М. Жегалкин (1869–1947) – российский математик и логик, один из основоположников современной математической логики.
Чарльз Пирс (1839–1914) – американский логик, математик и естествоиспытатель. Основоположник семиотики, родоначальник прагматизма.
3.3 Формулы алгебры логики
Из логических переменных можно составлять различные конструкции, которые образуют формулы алгебры логики.
Пусть
– некоторое множество логических переменных. По индукции определим понятие формулы алгебры логики:1) любая логическая переменная является формулой (атомарной);
2) если
и 
– формулы, то выражения 
и другие, представленные в табл. 1, являются формулами;3) никаких других формул, кроме построенных в пунктах 1 и 2, нет.
Если формула
построена из логических переменных, лежащих в множестве {x1, x2,…, xn}, то будем писать {x1, x2,…, xn}.Таблицы истинности также называются интерпретациями логических операций и составляют семантику формул (т. е. придание смысла формулам) в отличие от синтаксиса формул (т. е. формальных законов их построения, данных в определении формулы).
На множестве
вводится транзитивное отношение < «быть более сильным» и отношение ~ «быть равносильным» по правилам, представленным на рис. 2. Для равносильных связок расстановка скобок выполняется слева направо. 
Рис. 2. Приоритетность логических операций
Все формулы алгебры логики можно разделить на 3 класса:
1) нейтральные, или выполнимые – принимающие как истинное, так и ложное значения;
2) тождественно истинные формулы (или тавтологии) – принимающие истинные значения при любых значениях переменных;
3) тождественно ложные формулы – принимающие ложные значения при любых оценках переменных.
Существует два способа определения истинного значения формулы. Первый – с помощью таблиц истинности, а второй – путём приведения формул к нормальной форме. Формула имеет нормальную форму, если в ней отсутствуют знаки эквиваленции, импликации, двойного отрицания и др., при этом знаки отрицания находятся только при переменных.
Табличный способ определения истинного значения формул имеет ограниченное применение, поскольку при увеличении количества переменных приходится рассматривать слишком много вариантов (2N).
Равносильными называются два высказывания, у которых таблицы истинности совпадают.
Пример. Составим таблицу истинности функции f=(A
B)~( 
):Таблица 3
| A | B | A B |  | | | (A B)~( ) |
| 0011 | 0101 | 1101 | 1100 | 1010 | 1101 | 1111 |
Полученное высказывание истинно всегда. Такие высказывания называют тождественно истинными и обозначаются J. По аналогии существуют и тождественно ложные высказывания L. Метод заполнения таблицы истинности принят для не очень сложных высказываний. Если выражение содержит N опций, то таблица становится громоздкой. Для этого используются законы алгебры логики. Таблицу истинности можно составить с использованием программы. В большинстве языков высокого уровня имеются логические операции NOT, AND, OR, XOR, реализующие операции
соответственно.Контрольные вопросы
1. Дайте определение высказывания.
2. Перечислите основные символы алгебры высказываний.
3. Перечислите основные функции алгебры логики.
4. Что является основной задачей алгебры логики?
5. Что такое таблицы истинности логических функций?
6. Составьте таблицу истинности функций дизъюнкции и конъюнкции.
7. Составьте таблицу истинности функций импликации и эквивалентности.
8. Составьте таблицу истинности функций отрицания и сложения по модулю 2.
9. Составьте таблицу истинности функций Штрих Шеффера и Стрелка Пирса.
10. Формулы алгебры логики. Приоритет логических операций. Какие отношения имеют место на множестве логических операций?
11. Что такое синтаксическая структура формулы?
12. На какие классы делятся формулы алгебры логики?
3.4 Законы алгебры логики и следствия из них
При решении многих логических задач часто приходится упрощать формулы, полученные при формализации их условий. Упрощение формул в алгебре логики производится на основе эквивалентных преобразований, опирающихся на основные логические законы. Законы алгебры логики – это тавтологии (или теоремы).
1. Закон тождества:
А=А
2. Закон непротиворечия:
3. Закон исключения третьего:
4. Закон двойного отрицания:
