Введение в схемы, автоматы и алгоритмы



Формулы


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

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

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