Формулы
Как мы видели, табличное представление булевых функций подходит лишь для функций с небольшим числом аргументов. Формулы позволяют удобно представлять многие функции от большего числа аргументов и оперировать различными представлениями одной и той же функции.
Мы будем рассматривать формулы, построенные над множеством элементарных функций

Зафиксируем некоторое счетное множество переменных





Определение 1.2.
а) Базис индукции. 0, 1 и каждая переменная


б) Шаг индукции. Пусть





являются формулами. При этом









Каждой формуле

Базис индукции. Пусть



В первом случае



Шаг индукции. Пусть



или

для некоторой булевой связки







задает функцию


задает функцию

Для определения функции, задаваемой небольшой формулой, удобно использовать таблицу, строки которой сответствуют наборам значений переменных, а в столбце под знаком каждой логической связки стоят значения функции, задаваемой соответствующей подформулой.
Пример 1.1. Например, для формулы



![]() ![]() ![]() | ![]() ![]() ![]() ![]() ![]() | ![]() |
![]() ![]() ![]() ![]() ![]() ![]() | ||||
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 0 1 |
1 1 0 1 1 0 0 1 |
0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 1 1 1 0 0 0 1 0 0 1 1 1 1 0 0 1 |
Каждая строка этой таблицы задает процесс вычисления функции

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий