В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 19
Текст из файла (страница 19)
Пусть А означает высказывание: «Х всегда говорит правду», а В означает высказывание: «Дорога, идущая налево, ведет в столицу». Построим такое составное высказывание из высказываний А и В, чтобы ответ местного жителя на вопрос, истинно ли оно, гласил «да» тогда и только тогда, когда истинно высказывание В независимо от того, говорит местный житель всегда правду или всегда лжет.
Путешественнику достаточно спросить: «Верно ли, что Х всегда говорит правду и дорога, идущая налево, ведет в столицу или что М всегда говорит неправду и дорога, идущая налево, не ведет в столицу?», т.е. «Истинно ли высказывание (А л В) ч (-зА л -зВ)?» Проверим, что из ответа «да» вне зависимости от того, говорит ли Н правду или нет, следует, что дорога, идущая налево, ведет в столицу, а из ответа «нет» следует, что эта дорога не ведет в столицу. Здесь возможны четыре случая: а) ответ «да», Х говорит правду; б) ответ «да», 1ч' лжет; в) ответ «нет», )ч говорит правду; г) ответ «нет», Х лжет.
Рассмотрим, например, последний случай. Тогда Л((А л В) ч ч (-зА л -зВ)) = 1, Л(А) = О. Так как Л(А) = О, то Л(А л В) = О и, следовательно, Л(-чА л -з В) = 1. Далее, так как Л(А) = О, то Л(-зА) = = 1, и значит, Л(-зВ) = 1. Следовательно, Л(В) = О. Итак, при ответе «нет» мы заключаем, что дорога, идущая налево, не ведет в столицу.
Оставшиеся три случая предлагается рассмотреть аналогичным образом самостоятельно. Глава П БУЛЕВЫ ФУНКЦИИ Теории булевых функций посвящены четыре параграфа, объединенных в настоящую главу. В З 4 собраны задачи о числе булевых функций, о соотношениях и формальных свойствах булевых функций, я 5 посвящен специальным классам булевых функций, играющим существенную роль в формулировке теоремы Поста о полноте систем булевых функций, т.е. классам линейных, самодвойственных, монотонных, сохраняющих О и сохраняющих 1 булевых функций. В этих двух параграфах помимо заданного материала содержится большое количество новых понятий и фактов, не нашедших места на страницах Учебника и существенно развивающих теорию булевых функций.
В 5 6 рассматриваются полные системы булевых функций и вопросы применения теоремы Поста к их анализу. Релейно-контактные (переключательные) схемы являются ярким примером применения булевых функций в прикладных областях, связанных с автоматикой, телеметрией, компьютерной техникой. Им посвящен 9 7. и 4. Понятие булевой функции и свойства булевых функций Булевой функцией от одного аргумента называется функцияг'от одного аргумента, заданная на множестве из двух элементов (О, Ц и принимающая значения в том же двухэлементном множестве.
Булевой функцией от и аргументов называется функция 7'от п аргументов, заданная на двухэлементном множестве (О, Ц и принимающая значения в двухэлементном множестве (О, Ц. Другими словами, булева функция от и аргументов сопоставляет каждому упорядоченному набору, составленному из элементов О и 1, либо О либо 1. Булева функция 1'от н аргументов х„х„..., х„обозначается так: 7'(хп хъ ..., х„).
В первой из приведенных ниже таблиц указаны значения булевой функции от одного аргумента, называемой отрицанием и обозначаемой х', а во второй — обозначения и значения основных булевых функций от двух аргументов. 92 Функции от двух аргументов называются соответственно: коньюнкция, диэъюнкция, импликация, эквивалентность, штрих Шеффера, стрелка Пирса, сложение по модулю два (сумма Жегалкина). Число булевых функций. Решить задачи 4.1 — 4.7. 4.1. Сколько существует различных булевых функций от одного аргумента? Составьте таблицы значений каждой из них. 4.2.
Сколько существует различных булевых функций от двух аргументов? Составьте таблицы значений каждой из них. Выразите эти функции через отрицание и основные булевы функции от двух аргументов. 4.3. Сколько имеется различных двоичных наборов (т.е. наборов, составленных из нулей и единиц) длины и? 4.4. Докажите, что существует точно 2' различных булевых функций от и аргументов. 4.5. Каково число булевых функций от п аргументов, принимающих на противоположных наборах одинаковые значения? (Противоположными называются два двоичных набора вида (ао ам ..., а„) и (а,', а5, ..., а„').) Р е ш е н и е. Целесообразно начинать решение подобных задач с рассмотрения случаев и = 1, 2, 3.
Рассмотрим, например, последний из них и начнем составлять таблицу значений для искомых функций: 93 Следует заметить, что при выбранной нами системе записи наборов значений аргументов х, у, ~ противоположные наборы располагаются точно симметрично друг другу относительно выделенной средней линии таблицы.
Это означает, что у требуемой функции г" значения на первой половине наборов могут быть заданы произвольно: у„у,, у„у4, но в то же время значения на второй половине наборов, состоящей из наборов, противоположных наборам из первой половины, должны быть уже жестко определены: у4, у,, у,, уь Таким образом, требуемых функций будет столько, сколькими способами мы сумеем означить половину двоичных наборов длины и. Всего двоичных наборов длины л, как мы знаем, имеется 2" штук, половина их 2" '.
Означить их мы сможем числом способов 2'" (это есть число двоичных наборов длины 2" '). Это и есть искомое число функций. 4.6. Найдите число булевых функций от и аргументов, которые на любой паре соседних наборов принимают противоположные значения.
( Соседними называются два таких двоичных набора одинаковой длины, которые отличаются друг от друга значениями лишь в одном месте.) 4.7. На скольких наборах значений аргументов принимает значение 1 следующая булева функция от и аргументов: а) х,х3 ... х„+1; ж)(х, ... х4)+(х4,, ... х„); б) ХЗХ3 ... Х„+ Х~', 3) ХЗХЗХ3 + (Х4Х3 ... Хд); в) х, + х3х3 ... х„; и) 1+х, + х,х3+х,х3х3+ ...
+х,х3 ... х„; Г) 1 + Х~ + ХЗХ3 ". Хп К) Х~ + ХЗХ3 + Х~ХЗХ3 + .. ° + ХЗХ3 ... Х41 Д) Х~Х3 ... Х4 ~ + ХД', Л) (Х~ Ч ... *4 Х4) + (Х4~ ~ Ч ... '4 Х4); е) х~х3+ х3х4 ... х„+ 1; м) (х3 ... Х4) ч (х„,3 ... х„). Решение. а) Данная функция равна 1 тогда и только тогда, когда х,х, ... х„= О.
Последнее выполняется на всех наборах, кроме одного — единичного. Значит„искомое число наборов равно 2" — 1. б) Сумма Жегалкина двух слагаемых равна 1 тогда и только тогда, когда одно из этих слагаемых равно 1, а другое — О. Случай х, = О, х,х, ... х„= 1 реализовать невозможно. Пусть х, = 1, а х,х,... х„= = О. Этот случай осуществляется для всех таких наборов (1, аь ..., 43„), которые не являются полностью единичными. Ясно, что таких наборов имеется 2" ' — 1 штук.
в) Случаю х, = О, х3 ... х„= 1 отвечает только один набор (О, 1, ..., 1). Случаю х, = 1, х, ... х„= О отвечают 2"-' — 1 наборов. Всего наборов будет 2" '. г) Случаю х, = 1, х, ... х„= 1 отвечает только единичный набор: (1, 1, ..., 1). Случаю х, = О, х3 ... х„= О отвечают 2" ' — 1 наборов. Всего 2"-' наборов.
д) Аналогично решению задачи в). е) Сумма Жегалкина трех слагаемых равна 1 тогда и только тогда, когда нечетное число слагаемых равно 1. Следовательно, данная функция примет значение 1, если и только если два 94 первых слагаемых примут значение 0 либо оба этих слагаемых примут значение 1. Последняя ситуация возможна лишь для одного набора (единичного) длины»н (1, 1, ..., 1). Равенство же нулю обоих первых слагаемых достигается на таких двоичных наборах (а„а3, а3, ..., ал), в которых среди элементов а1, а3 есть хотя бы один 0 и среди элементов а3, ..., а„ есть хотя бы один О. Чтобы сосчитать общее число таких наборов, раэделим их на три группы: наборы вида (О, О, а3, ..., а„); наборы вида (О, 1, а3, ..., а„); наборы вида (1, О, а3, ..., а„). Ясно, что в каждой из этих групп одинаковое число наборов.
Поэтому подсчитаем их число в одной из групп. Поскольку среди элементов а3, ..., а„имеется по меньшей мере один О, то наборов вида (О, О, а3, ..., а„) будет столько же, сколько наборов (а„..., а„) длины л— 2, не все элементы которых равны 1. А таких наборов имеется 2" ' — 1. Столько же наборов вида (О, 1, а„..., ал) и еще столько же наборов вида (1, О, а3, ..., ал). Итак, ровно 3(2л ' — 1) наборов превращают каждое из первых двух слагаемых в сумме Жегалкина, задающей данную функцию, в О. Прибавим к ним один набор, превращающий эти слагаемые в 1.
Получим всего 3(2л ' — 1)+1=3 2" ' — 2 наборов. ж) Наборы, для которых х, ... х» = 1, х», ... хл = О, имеют вид (1, ..., 1, а»„, ..., а„). Таких наборов 2" » — 1 штук. Наборы, для которых х, ... х» = О, х»„, ... хл = 1, имеют вид: (ап ..., ан 1, ..., 1). Таких наборов 2» — 1 штук. Итого (2л» вЂ” 1) + (2" — 1) = 2" + 2" » — 2. и) Случай х, = 0 дает 2л-' наборов. Если х, = 1, то х3 = 1.
Далее, случай х3 = 0 дает 2" ' наборов. Если же х, = 1, то х» = 1. Далее, случайх,=Одает2" 'наборов. Еслих,=1, тох»=1. Итак далее... Конец этого процесса будет различным для четных и нечетных и. Пусть и — четное. Тогда случай хл, ='О дает 2л-1л-'1 наборов. Если хл, = 1, то хл = 1.
Таких наборов один (единичный набор). Итого: л-1 и-3 л-5 3 1 2(2 " — 1~ 2 л 2" '+2" 3+2" 5+...+23+2'+1= ' '+1= — (2л — 1)+1. 23 — 1 3 Пусть и — нечетное. Тогда случай хл, = 0 дает 2л-'" " наборов. Если хл,= 1, то хи, = 1. Наконец случай хл = 0 дает 2" "= 1 наборов. Всего получаем следующее число наборов: 23Ц +1>231 2л-1 2л-3 + 2и-5 + + 22 + 1 (2~и 1) 23 — 1 3 л) Наборы,для которыхх, 1~ ... 1~х»=1,х»„~ ... 1 х„=О, имеют вид (а„..., а», О, ..., 0), причем не все а равны О.
Таких наборов ВСЕГО 2»-1. НабОрЫ,дЛяКОтОрЫХХ1 Ч ... ЧХ„=О, Х»,1Ч ... ЧХл=1, имеют вид (О, ..., О, ав „„..., а„), причем не все а равны О. Таких наборов имеется 2" в — 1 штук. Всего: 2в+ 2" в — 2. Равенство булевых функций. Решить задачи 4. 8 — 4.9. Две булевы функции от л аргументов Дхн хн ..., х„) и 8(хн хн ..., х„) называются равными, если любым одинаковым наборам значений аргументов х„х„..., х„обе эти функции сопоставляют одинаковые элементы из множества (О, Ц, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
