Формулы

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

Мы будем рассматривать формулы, построенные над множеством элементарных функций

. Все эти функции, кроме констант, называются логическими связками или логическими операциями. При этом для 2-местных функций из этого списка будем использовать инфиксную запись, в которой имя логической связки помещается между 1-ым и 2-ым аргументами.

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

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

Определение 1.2.

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

является формулой глубины 0, т.е. . Множество ее подформул состоит из нее самой.

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

и - формулы, . Тогда выражения и

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

, а . Множество подформул включает саму формулу и для все подформулы формулы , а для все подформулы формул и

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

сопоставим булеву функцию, которую эта формула задает, используя индукцию по глубине формулы.

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

. Тогда или

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

задает функцию , во втором - функцию, тождественно равную константе .

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

- произвольная формула глубины . Тогда

или

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

. Так как то формулам и соответствующие функции и уже сопоставлены. Тогда формула

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

, а формула

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

.

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

Пример 1.1. Например, для формулы

функция задается выделенным столбцом следующей таблицы.

Таблица 1.3. Функция

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
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий

---

---