Выражения, переменные и формы 3 страница

7. ( х)[ (х)→ (x)] º ( х) (х)→( х) (x)

8. ( х)[ (х) (x)] º ( х) (х) ( х) (x) ■

 

Задание 5. Написать отрицания следующих высказываний

1. У каждой собаки есть свой день

2. На равнинах Испании сегодня нет дождей

3. Некоторые книги длиннее, чем эта книга

4. Ни один мастер по ремонту компьютеров не умеет играть в «блэкджек»

5. Некоторым людям всегда везёт

6. Каждый иногда любит кого-то

7. Все любят победителя

8. Все мужчины созданы равными

9. Некоторые ученики из нашего класса ездили на загородную экскурсию ■

 

Задание 6. Для изображений из примера 15 отметить одной (или несколькими) буквами группу или группы картинок, удовлетворяющих условиям:

1. Ни одна картинка не имеет рамки

2. По меньшей мере одна картинка не имеет рамки

3. Не каждая картинка имеет рамку

4. По меньшей мере одна картинка имеет рамку

5. Нет картинок, которые не имеют рамки

6. Все картинки не имеют рамки

7. Не каждая картинка не имеет рамки ■

 

Предметный указатель

Выражение

Квантор,

общности,

по переменной

существования,

по переменной

Квантора навешивания операция

Константа

Констан­тыравносильные

Переменная,

высказывательная

несущественная

свободная

связанная

фиктивная

числовая

Переменной,

значения допустимые

область значений

Форм,

равносильность

неравносильность

Форма,

высказывательная

одноместная,

всюду определённая

нигде не определённая

равносильная константе

функциональная

числовая

s-местная,

всюду определённая

нигде не определённая

Формы, равносильные

высказывательной область истинности

функциональной область прибытия

 

Глава 5. Булева алгебра

1. Понятие булевой функции

2. Функции и формулы

3. Формальный анализ высказываний

4. Булевы функции для описания систем голосования

5. Код Хемминга

6. Задания

7. Предметный указатель

Понятие булевой функции

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

Обозначим через В двухэлементное множество {0,1}, состоящее из двух символов 0 и 1. Тогда В^п = В×В×... ×В (n сомножителей) – это множество всех кортежей длины n, компоненты которых равны 0 или 1. По определению, В ¹= В = {0,1}. Обратим особое внимание на тот факт, что 0 и 1 – это, вообще говоря, не числа ноль и один, а формальные символы, некоторые опера-ции над которыми действительно напоминают обычные арифметические операции сложения и умножения, однако другие операции над ними совсем не похожи на арифметические.

Определим булевы функции, используя общую конструкцию функции из раздела 4-1.1. Булевой функцией называется функция с областью отправления В^п и областью прибытия В. Число n может быть произвольным натуральным числом: 1, 2, …. Возвращаясь к привычным обозначениям, можно сказать, что булева функция является функцией от n переменных, прини-мающих значения из множества В = {0,1}; значения булевой функции принадлежат тому же са-мому двухэлементному множеству В. Если не указано противное, булевы функции будем счи-тать определёнными на всех наборах из В^п. Это значит, что область определения булевой функ-ции совпадает с её областью отправления.

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

1.1. Табличное представление. Булевы функции от небольшого числа переменных удоб-но представлять с помощью таблиц. Таблица для функции f (x ₁, …, x_n) имеет п + 1 столбец. В первых n столбцах указываются значения переменных x ₁, …, x_n, а в (n + 1)-ом столбце – значе-ние f (x ₁, …, x_n) функции f на этом наборе значений.

Таблица.1. Табличное представление функции f (x ₁, …, x_n)

x 1	......	xn –1	xn	f (x 1, …, xn –1, xn)
	......			f (0, …, 0, 0)
	......			f (0, …, 0, 1)
	......			f (0, …, 1, 0)
	......			.....
	......			f (1, …, 1, 1)

Наборы переменных в строках обычно располагаются в лексикографическом порядке:

(α ₁, …, α_n) (β ₁, …, β_n) ↔ i {1, …, n }, такое, что при всех j < i α_j = β_j и α_i < β_i. (1)

Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1-ая строка является записью числа 0, 2-ая – числа 1, 3-я – числа 2,..., а последняя – числа 2 ⁿ –1. Типичное представление булевой функции от трёх переменных даётся в таблице 2. В этой таблице, как и во всех последующих таблицах, задающих булевы функции, наборы переменных расположены в лексикографическом порядке. Обратим особое внимание на удобство такого расположения. Его не надо запоминать. Просто в последнем (самом правом) столбце значения меняются, начиная с нуля, через одну позицию; в предпоследнем столбце, начиная с двух нулей, через две позиции, и т.д., вплоть до первого столбца, в котором в первой половине позиций стоят нули, а во второй половине – единицы. Другие важные свойства наборов, расположенных именно в таком порядке, будут рассмотрены в разделе 5.

Таблица 2. Функция от трёх переменных

x 1	x 2	x 3	f (x 1, x 2, x 3)

При больших п табличное представление становится громоздким. Например, для функции от 10 переменных потребуется таблица с 1024 строками. Но для малых п (п = 2, 3, 4) оно достаточ-но наглядно.

1.2. Булевы функции от одной и двух переменных. Прежде чем двигаться дальше и гово-рить о других представлениях булевых функций, необходимо детально рассмотреть булевы функ-ции от одной и двух переменных. Функции от одной переменной записаны в таблице 3. Этих функций – четыре:

Таблица 3. Булевы функции от 1-ой переменной

x	φ 0	φ 1	φ 2	φ 3

Левый столбец содержит два значения переменной x. Следующие 4 столбца определяют все 4 фун-кции от одной переменной. Функции φ ₀ и φ ₃ – константы 0 и 1; их значения не зависят от значения переменной x. В конце раздела 4-1.1 такие переменные названы несущественными. Функция φ ₁ «повторяет» x: φ ₁(x) = x. Функция φ ₂(x) называется отрицанием x. Для отрицания будет использо-ваться тот же знак Ø, который использовался в таблицах 1-1 и 1-2 для отрицания высказываний. Иногда для отрицания используются также обозначения , x ⁰, ~ x.

Отличие от введённой в разделе 1-2 операции отрицания состоит в том, что там отрицание относилось только к высказываниям и их истинностным значениям. Здесь отрицание относится к формальным символам 0 и 1, для которых интерпретация их как истинностных значений F и T является хотя и часто используемой, но далеко не единственной. То же самое относится и к булевым функциям от любого числа переменных.

Рассмотрим теперь логические функции от двух переменных. Их число равно 16. Все они записаны в таблице 4.

Таблица 4. Булевы функции от 2-ух переменных

x 1

x 2

ψ 0

ψ 1

ψ 2

ψ 3

ψ 4

ψ 5

ψ 6

ψ 7

ψ 8

ψ 9

ψ 10

ψ 11

ψ 12

ψ 13

ψ 14

ψ 15

Два левых столбца содержат все четыре набора переменных: (0, 0), (0, 1), (1, 0), (1, 1), расположен-ные в лексикографическом порядке. Следующие 16 столбцов определяют все 16 различных функ-ций от двух переменных: в столбце под символом ψ_i находятся 4 значения функции ψ_i на этих 4-ёх наборах. Эти столбцы также расположены в лексикографическом порядке, но не сверху-вниз, как в таблицах 1 и 2, а слева направо.

Многие из этих 16-и функций часто используются в качестве «элементарных» и имеют собствен-ные названия и обозначения. Часть этих названий уже использовалась в главе 1 для описания операций над высказываниями и их истинностными значениями. При замене F и T на 0 и 1 все 6 рассмотренных в разделе 1-2.1 операций перейдут в 6 функций, представленных в таблице 4. Естественно, что используются те же названия.

1. ψ ₀(x ₁, x ₂) = 0 – константа 0;

2. ψ ₁₅(x ₁, x ₂) = 1– константа 1;

3. ψ ₃(x ₁, x ₂) = x ₁ – функция, равная 1-му аргументу;

4. ψ ₁₂(x ₁, x ₂) = Ø x ₁ – отрицание x ₁;

5. ψ ₅(x ₁, x ₂) = x ₂ – функция, равная 2-му аргументу;

6. ψ ₁₀(x ₁, x ₂) = Ø x ₂ – отрицание x ₂;

7. ψ ₁(x ₁, x ₂) = x ₁Ù x ₂ – конъюнкция x ₁ и x ₂ (обозначается также через x ₁& x ₂ и x ₁ x ₂);

8. ψ ₇(x ₁, x ₂) = x ₁Ú x ₂ – дизъюнкция x ₁ и x ₂;

9. ψ ₁₃(x ₁, x ₂) = x ₁ → x ₂ – импликация x ₁ и x ₂ (читается «х ₁ влечёт х ₂» или «из х ₁ следет х ₂»;

10. ψ ₆(x ₁, x ₂) = x ₁ Å x ₂ – сложение по модулю 2или разделительная дизъюнкция (исполь-зуется также обозначение x ₁ + x ₂);

11. ψ ₉(x ₁, x ₂) = x ₁ x ₂ – эквивалентность x ₁ и x ₂ (читается как «x ₁ эквивалентно x ₂» или «x ₂ = 1 тогда и только тогда, когда x ₁ = 1»);

12. ψ ₁₄(x ₁, x ₂) = x ₁ | x ₂ – штрих Шеффера(отрицание конъюнкции –«антиконъюнкция»);

13. ψ ₈(x ₁, x ₂) = x ₁ ↓ x ₂ – стрелка Пирса(отрицание дизъюнкции –«антидизъюнкция»).

Заметим, что для 2-местных функций из этого списка в правых частях равенств использованы не только собственные имена, но и инфиксная запись,в которой значок операции помещается между 1-ым и 2-ым аргументами (запись вида ψ (x ₁, x ₂) называется префиксной). Функции ψ ₂(x ₁, x ₂), ψ ₄(x ₁, x ₂), ψ ₁₁(x ₁, x ₂) не имеют специальных названий.

Пример 1. Таблица 4 задаёт все функции от двух переменных. Приведём в качестве примера использования этой таблицы несколько тождеств для булевых функций, в верности которых легко убедиться проверкой значений функций на всех четырёх наборах – 00, 01, 10 и 11 – значений двух переменных. Под тождествами здесь и далее понимаются равенства функций при всех наборах значений их переменных.

a → b º Ø a Ú b (2)

a Å b º (Ø a Ù b) Ú (a Ù Ø b) (3)

a Å 1 º Ø a (4)

a b º (a Ù b) Ú (Ø a Ù Ø b) (5)

a | b º Ø(a Ù b) (6)

a ↓ b º Ø(a Ú b). (7)

Использование других имён переменных вместо x ₁, x ₂ и x подчёркивает независимость свойств функций и связей между ними от этих имён, что, впрочем, совершенно естественно для всех разделов математики ■

Отметим, что функции ψ ₃(x ₁, x ₂), ψ ₁₂(x ₁, x ₂), ψ ₅(x ₁, x ₂), ψ ₁₀(x ₁, x ₂) зависят только от одной переменной, так что в ψ ₃(x ₁, x ₂) и ψ ₁₂(x ₁, x ₂) несущественной является переменная x ₂, в ψ ₅(x ₁, x ₂) и ψ ₁(x ₁, x ₂) несущественной является переменная x ₁. Функции ψ ₀(x ₁, x ₂) и ψ ₁₅(x ₁, x ₂) являются константами 0 и 1, т.е. в них обе переменные несущественны. Конъюнкция называется также логическим умножением, а дизъюнкция – логическим сложением.

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

Таблица 5. Булевы функции от 2-ух переменных со значками функций

x 1

x 2

x 1Ù x 2

ψ 2

x 1

ψ 4

x 2

x 1Å x 2

x 1Ú x 2

x 1 ↓ x 2

x 1 x 2

Ø x 2

ψ 11

Ø x 1

x 1→ x 2

x 1 | x 2

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

Разумеется, эти понятия относятся не только к булевым, но и к произвольным функциям. Хорошо известным примером является равенство sin² x + cos² x = 1, означающее, что переменная x в функции f (x) = sin² x + cos² x несущественна.

Функции и формулы

Табличное представления булевых функций подходят лишь для функций с небольшим числом аргументов. Формулы позволяют удобно представлять многие функции от бóльшего числа аргументов и оперировать различными представлениями одной и той же функции. Пусть B– некоторое (конечное или бесконечное) множество булевых функций. Зафиксируем некото-рое счётное множество переменных V = { x ₁, x ₂, …}. Определим по индукции множество формул над B с переменными из V. Одновременно будем определять числовую характеристику dep (Ф) формулы Ф, называемую её глубиной, и множество её подформул.

а) Базис индукции. Каждая переменная x_i V и каждая константа c B является форму-лой гл-бины0,т.е. dep (x_i) = dep (c)= 0. Множество её подформул состоит из неё самой. Напом-ним, что константа является функцией, все переменные которой несущественны, и c {0, 1}.

б) Шаг индукции. Пусть f (x ₁, …, x_m) B, Ф ₁, …, Ф_т – формулы, и = k. Тогда выражение Ф = f (Ф ₁, …, Ф_m) является формулой, её глубина dep (Ф) равна k + 1, амножество подформул Ф включает саму формулу Ф и все подформулы формул Ф ₁, …, Ф_т.

Понятие «доказательства по индукции», может быть, встречалось читателю. Но вот «опре-деления по индукции», чаще называемые индуктивными или рекурсивными определениями, для большинства читателей являются новыми. Остановимся на этом подробнее.

Речь идёт о задании, построении или описании множеств – в данном случае множества формул – некоторым процессом, который обычно называется порождающей процедурой (см. раздел 2-1). Идея такой процедуры состоит в определении некоторого достаточно простого исходного множества (это и есть базис индукции) и затем в последовательном добавлении в рассматриваемое множество новых элементов, полученных из уже имеющихся элементов, либо из каких-либо других объектов. Точная формулировка этих понятий далеко выходит за рамки настоящего пособия. Здесь мы просто проиллюстрируем «работу» порождающей процедуры на примере.

Пример 2. Определение множества формул над множеством функций B, состоящем из четырёх функций: константы 0, константы 1, Ø (отрицания) и Ú (дизъюнкции).

Сначала определяется исходное множество формул: {0, 1, x ₁, x ₂, …}. В соответствии с описанием базиса индукции, это множество объявляется множеством всех формул глубины 0. Далее, форму-лами глубины 1 являются все формулы вида Ø x ₁, Ø x ₂, …, а также формулы вида x_i Ú x_j (i, j = 1, 2, …) и вида c Ú x_i, x_i Ú c (i = 1, 2, …, c = 0, 1). Далее, формулами глубины 2 являются все формулы вида Ø x_i Ú x_j, x_i ÚØ x_j, Ø x_i ÚØ x_j, Ø(Ø x_i), (x_i Ú x_j)Ú x_k, и т.д.

Убедимся, например, что формулы Ø x_i Ú x_j и (x_i Ú x_j)Ú x_k имеют глубину 2. По построению, подформулами формулы Ø x_i Ú x_j являются формулы Ф ₁ = Ø x_i и Ф ₂ = x_j. Формула Ф ₁ имеет глубину 1, формула Ф ₂ имеет глубину 0, максимальное из этих чисел равно 1 и по описанию шага индукции глу-бина формулы Ф = Ø x_i Ú x_j равна 1 + 1 = 2. В формуле (x_i Ú x_j)Ú x_k Ф ₁ = x_i Ú x_j, Ф ₁ = x_k, их глубина равна 1 и 0 и, значит, глубина Ф = (x_i Ú x_j)Ú x_k равна 2. Заметим, что глубина формулы Ø x_i ÚØ x_j также равна 2 ■

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

Базис индукции. Пусть dep (Ф) = 0. Тогда Ф = x_i V или Ф = c B. В 1-ом случае Ф опре-деляет функцию f_Ф (x_i) = x_i, во 2-ом – функцию, тождественно равную константе c.

Шаг индукции. Предположим (по индукции), что всем формулам над B глубины не бо-лее k булевы функции уже сопоставлены. Пусть Ф (x ₁, …, x_n) – произвольная формула глубины k + 1. По процедуре построения формул это означает, что Ф = f (Ф ₁, …, Ф_m), где f (x ₁, …, x_m) B и при этом = k. По предположению индукции, всем формулам глубины не более k уже сопоставлены булевы функции g ₁(x ₁, …, x_n), …, g_m (x ₁, …, x_n). Тогда формула Ф определяет функцию f_Ф (x ₁, …, x_n) = f (g ₁, …, g_m). Для полной аккуратности конструкции надо включить в индуктивное предположение очевидное условие, что формулы с переменными x ₁, …, x_n определяют функции от этих же переменных.