Тексты лекций / Текст лекции 3

является формулой, ее глубина ( ) равна +1, а множество подформул включает саму формулу и все подформулы , ,..., .

Используя индукцию по глубине формулы, определим функцию, заданную формулой. Определение. Базис индукции. Пусть ( ) = 0. Тогда имеет вид = , где - переменная из , или = , где - константа из . В первом случае задаеттождествен-

ную функцию , во втором - функцию, тождественно равную константе . Индуктивный переход. По предположению индукции каждой формуле глубины

сопоставлена некоторая функция. Пусть ( , ,..., ) - произвольная формула глубины

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

( , ,..., ),..., ( , ,..., ) .

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

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

Задачи повышенной сложности

2.1.Назовем весом булева вектора число его координат, равных 1. Сколько булевых векторов длины n имеет вес k?

2.2.Булевы векторы часто называют вершинами булева куба. Расстоянием (Хэмминга)

между вершинами и куба называют число , , равное числу координат, в

11

ние между векторами (1,0,0,1,0) и (0,0,0,1,1) равно 2. Расстояние между векторами (0,0,1,0) и (1,0,1,0) равно 1 и, значит, они соседние. Расстояние между векторами (1,0,0,1,0,0) и (0,1,1,0,1,1) равно длине этих векторов, и, следовательно, они противоположные.

Найти число неупорядоченных пар вершин булева куба , удаленных друг от друга на расстояние k (0 ≤ ≤ ).

2.3. Показать, что для любых противоположных наборов и выполняется равенство

() + = 2 − 1.

2.4.Подсчитать число функций от переменных, у которых: а) одна переменная фиктивная, остальные существенные;

б) (1 ≤ ≤ ) переменных фиктивные, остальные - существенные.

2.5.Пусть = { ,, }-подмножествобулевыхфункций,причем (1), (2),

(3) и ни одна из функций не является тождественной константой, = { ,,} - алфавит переменных. Определить, является ли выражение формулой над множеством независимо от вида функций ,,:

Ответы и указания к упражнениям

2.1. 16. Указание. Вектор, одинаково читающийся слева направо и справа налево, однозначно определяется первой половиной своих координат. Первые четыре его координаты можно выбрать 2 2 2 2 = 16 способами. 2.2. (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0),

менные , - существенные. Чтобы удалить фиктивную переменную , нужно вычеркнуть изтаблицыистинностифункции2-ойстолбеци3-,4-,7-,8-юстроки(еслинесчитатьстроку заголовков). В результате получим таблицу истинности функции ( ,) = (0111). б) Переменные ,  - фиктивные, - существенная. После удаления фиктивных переменных по-

лучим функцию ( ) = (01). 2.8. = ), = (00001010), = (00001100). 2.9. ( ,) = ( ).

12

Тема 3 «Булевы функции и способы их задания» Олейник Т.А., 2020

Решение. Чтобы выполнить задание, нужно выявить все фиктивные переменные функции и удалить их. Построим таблицу истинности функции , дополнив ее для наглядности столбцомномеровбулевыхвекторов(табл.1).Сначалавыясним,какиеиз аргументов функции фиктивные. Чтобы выяснить, является переменная фиктивной или существенной, нужно сравнить значения функции на парах векторов, отличающихся лишь значени-

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

Решение. = ( ̄̄̄ ̄̄ ) ( ̄̄ ̄ ) = = ̄̄( ̄ ) ̄( ̄ ) = ̄̄ 1 ̄ 1 = ̄( ̄ ) = ̄.

13