2.4 Реализация функций формулами.
Пусть
— множество
булевых функций. Формулой над F
называется
выражение
вида
где
и
либо переменная, либо формула над F.
Множество F называется базисом, функция f называется главной (внешней) операцией (функцией), а называются подформулами.
Обычно для
элементарных булевых функций используется
инфиксная форма записи,
устанавливается
приоритет
и лишние скобки опускаются.
Зная таблицы истинности для функций базиса, можно вычислить таблицу истинности той функции, которую реализует данная формула.
Примеры:
1.
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
Таким образом, формула реализует дизъюнкцию.
2.
|
|
|
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
Таким образом, формула реализует константу 1.
3.
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
Таким образом, формула F3 также реализует дизъюнкцию.
3 Логические исчисления
3.1 Основные понятия.
С древнейших времен человечеству известна логика, или искусство правильно рассуждать. Вообще, способность к рассуждениям — это именно искусство. Имея какие-то утверждения (посылки), истинность которых проверена, скажем на опыте, логик путем умозрительных построений приходит к другому утверждению (заключению), которое также оказывается истинным (в некоторых случаях). Опыт древних (чисто наблюдательный) был систематизирован Аристотелем. Он рассмотрел конкретные виды рассуждений, которые назвал силлогизмами А, именно, Аристотель рассмотрел так называемые категорические утверждения четырех видов:
все А обладают свойством В (все А суть В);
некоторые А обладают свойством В (некоторые А суть В);
все А не обладают свойством В (все А суть не В);
некоторые А не обладают свойством В (некоторые А суть не В)
и зафиксировал все случаи, когда из посылок такого вида выводятся заключения одного из этих же видов.
Пример:
1. Все люди смертны. Сократ — человек. Следовательно, Сократ смертен. Это рассуждение правильно, потому что подходит под один из образцов силлогизмов Аристотеля.
2. Все дикари раскрашивают свои лица. Некоторые современные женщины раскрашивают свои лица. Следовательно, некоторые современные женщины — дикари. Это рассуждение неправильно, хотя, видимо, все входящие в него утверждения истинны.