Учебное пособие: Дискретная математика
На этом рисунке представлен пример синтаксической структуры формулы – графическое представление формулы.
Рис. 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, нет.
Если формула построена из логических переменных, лежащих в множестве {x 1 , x 2 ,…, xn }, то будем писать {x 1 , x 2 ,…, xn }.
Таблицы истинности также называются интерпретациями логических операций и составляют семантику формул (т. е. придание смысла формулам) в отличие от синтаксиса формул (т. е. формальных законов их построения, данных в определении формулы).
На множестве 
вводится транзитивное отношение < «быть более сильным» и отношение ~ «быть равносильным» по правилам, представленным на рис. 2. Для равносильных связок расстановка скобок выполняется слева направо.
Рис. 2. Приоритетность логических операций
Все формулы алгебры логики можно разделить на 3 класса:
1) нейтральные, или выполнимые – принимающие как истинное, так и ложное значения;
2) тождественно истинные формулы (или тавтологии) – принимающие истинные значения при любых значениях переменных;
3) тождественно ложные формулы – принимающие ложные значения при любых оценках переменных.
Существует два способа определения истинного значения формулы. Первый – с помощью таблиц истинности, а второй – путём приведения формул к нормальной форме. Формула имеет нормальную форму, если в ней отсутствуют знаки эквиваленции, импликации, двойного отрицания и др., при этом знаки отрицания находятся только при переменных.
Табличный способ определения истинного значения формул имеет ограниченное применение, поскольку при увеличении количества переменных приходится рассматривать слишком много вариантов (2N ).
Равносильными называются два высказывания, у которых таблицы истинности совпадают.
Пример. Составим таблицу истинности функции f=(A 
B )~(
):
Таблица 3
| A | B | AB |  | | | (AB)~() |
|
0 К-во Просмотров: 523
Бесплатно скачать Учебное пособие: Дискретная математика
|