Пусть имеется некоторое устройство, внутренняя структура которого нас не интересует, а известно лишь, что оно имеет п упорядоченных входов (занумерованных числами от 1 до п) и один “выход”. На каждый из входов может подаваться один из двух сигналов: 0 или 1 (“отсутствие тока” или “наличие его”) и при каждом наборе сигналов на входе возникает один из двух сигналов 0 или 1 на выходе. Такое устройство называется функциональным элементом (ФЭ). ФЭ, соответствующий функции j от нескольких переменных, может быть изображен следующим образом:
Ясно, что каждому ФЭ соответствует некоторая булева функция f (x 1, x 2,…, xn). Некоторые входы могут быть фиктивными (т. е. при любом наборе сигналов на остальных входах сигнал на выходе не зависит от сигнала на этом входе, и соответствующая булева функция зависит от меньшего числа переменных). Если имеется несколько ФЭ, то из них можно получать новые сложные ФЭ (например, один из входов ФЭ можно соединить с выходом другого. В этом случае полученное соединение соответствует суперпозиции двух функций. Можно также соединять некоторые входы, что означает отождествление некоторых переменных).
|
|
Следующие соединения, очевидно, являются логическими функциями: (x + y) | (y ~ z) и (x | y) ~ (x× y).
Более точно: будем называть соединение нескольких ФЭ схемой, если выполнены следующие естественные требования:
а) всякий ФЭ является схемой;
б) если S 0 – схема и два ее входа соединены вместе, то получившаяся в результате конструкция S также является схемой;
в) если S 1и S 2 – схемы, то схемой будет также конструкция S, полученная соединением какого-либо входа S 1с выходом S 2;
г) всякая схема может быть построена из ФЭ за конечное число шагов при помощи конструкций, описанных в б, в.
Ясно, что не всякое соединение ФЭ является схемой.
Соединение S конечного числа функциональных элементов является схемой тогда и только тогда, когда выполнены 3 условия:
среди ФЭ есть один и только один свободный выход (т.е. выход, не соединенный ни с каким входом);
каждый вход любого ФЭ может быть соединен не более чем с одним выходом другого ФЭ;
в соединении S нет циклов (т.е. нет такого упорядоченного набора ФЭ, когда вход следующего соединен с выходом предыдущего и вход первого соединен с выходом последнего. Цикл в соединении иначе называют обратной связью).
Теперь посмотрим, как на языке схем перефразируется задача о полноте системы функций. Пусть имеется некоторый набор функциональных элементов j 1, j 2,…,j п (точнее, типов ФЭ, т. е. считаем, что имеется неограниченное число элементов, реализующих каждую из функций j k). Спрашивается, при каких условиях любую булеву функцию можно реализовать при помощи схемы, состоящей из данных ФЭ. Из предыдущего ясно что ответ на этот вопрос дается теоремой Поста.
|
|
Замечание. Ясно, что при реализации описанных выше устройств необходимо учитывать, что для работы конкретных ФЭ требуется некоторое время, что влияет на фактор полноты ФЭ. Подробнее об этом можно узнать в [3].
Заметим, что на практике часто используются функции “конъюнкция” и “дизъюнкция”. Для них часто схемы изображаются несколько иначе. Дадим более точное определение. Релейно-контактной схемой или РКС будем называть некоторое соединение, состоящее из следующих элементов:
переключателей (это могут быть как механические устройства, так и лампы, электромагнитные реле и т. д.) Каждый переключатель может принимать значение 1 (через него пройдет ток) или 0 (через него ток не проходит). Будем считать, что любой переключатель соответствует либо логической переменной x,либо ;
проводников, могущих соединять переключатели либо последовательно, либо параллельно (это соответствует замене ФЭ, определяющих конъюнкцию или дизъюнкцию);
входа и выхода из системы (вход и выход называются полюсами системы).
Иначе РКС называют переключательной схемой (П-схемой).
Будем говорить, что конкретная РКС принимает значение 1 при данных значениях переключателей, если через нее проходит ток, в противном случае мы считаем, что она принимает значение 0.
Две РКС считаются равносильными,если они принимают одинаковые значения при одних и тех же значениях переключателей.
Очевидно, что любая суперпозиция функций конъюнкции, дизъюнкции и отрицания может быть изображена в виде РКС. Например, функции соответствует следующая РКС.
Следующая РКС соответствует функции (в ней 12 переключателей).
После сокращения СДНФ по правилу Блейка можно получить равносильную формулу: L = xz Úyz Ú xz, для которой РКС будет иметь 6 переключателей. Если ставить целью уменьшение числа переключателей, то последнее выражение можно преобразовать к виду L = (x Úy) z Úxy (РКС будет иметь 5 переключателей).
8.2. Решение логических задач с помощью теории булевых функци й
Суть применения методов теории булевых функций к решению логических задач состоит в том, что, имея конкретные условия логической задачи, стараются записать их в виде логической функции. При этом учитывается, что каждое высказывание может быть либо истинным, либо ложным и, значит, его можно обозначить логической переменной. В дальнейшем путем равносильных преобразований упрощают полученную формулу, что, как правило, приводит к ответу на все вопросы задачи, но иногда все-таки требуется применять логические рассуждения.
Покажем на ряде конкретных примеров, как использовать возможности теории булевых функций для решения элементарных логических задач.
Пример 1. Пытаясьвспомнитьпобедителей прошлогоднего турнира, 5 бывших зрителей турнира заявили:
1) Антон был вторым, а Борис пятым.
2) Виктор был вторым, а Денис третьим.
3) Григорий был первым, а Борис третьим.
4) Антон был третьим, а Евгений шестым.
5) Виктор был третьим, а Евгений четвертым.
Впоследствии выяснилось, что каждый мог ошибиться, не более чем в одном высказывании. Каково было истинное распределение мест в турнире?
Решение. Будем обозначать высказывания зрителей Х k, где Х – первая буква имени участника турнира, а k – номер места, которое он занял в турнире. В высказываниях зрителей одно высказывание может быть ложным, поэтому будут истинными дизъюнкции этих высказываний А2Ú Б5, В2 Ú Д3, Г1Ú Б3 , А3 Ú Е6 , В3Ú Е4. Но тогда истинной будет конъюнкция: K = (А2 ÚБ5)(В2Ú Д3)(Г1 ÚБ3 )(А3 Ú Е6)(В3Ú Е4 ) = 1.
Учитывая, что Х k Х п = 0 при k ¹ п и Х k Y k = 0 при X¹ Y, получаем путем последовательного раскрытия скобок в К:
|
|
К = (А2Д3 ÚБ5В2 ÚБ5Д3)(Г1А3Ú Г1Е6 ÚБ3Е6)(В3Ú Е4) =
= (А2Д3Г1Е6 ÚБ5В2Г1А3 Ú Б5В2Г1Е6 Ú Б5Д3Г1Е6)(В3Ú Е4) = А3Б5В2Г1Е4 = 1
Полученное соотношение дает распределение первых 5 мест и автоматически получаем, что Денис был шестым т. е. Д6 = 1.
Пример 2. По подозрению в совершении преступления задержали Брауна, Джонса и Смита. Вот что они показали:
Браун: Я совершил это. Джонс не виноват.
Джонс: Браун не виноват. Преступление совершил Смит.
Смит: Я не виноват. Виновен Браун.
В процессе следствия выяснилось, что у одного из них оба утверждения ложны, у другого одно ложно, одно истинно, а у третьего оба истинны, а также, что преступник только один. Требуется определить имя преступника, кто из них говорил правду, а кто нет.
Решение. Обозначимбуквами B, D, C высказывания: виноват Браун, виноват Джонс, виноват Смит соответственно. Тогда утверждения, высказанные задержанными, можно записать в виде конъюнкций , из которых по условию задачи, две ложны, а одна истинна. Истинной будет формула, но из этой формулы решение получится только дополнительным рассуждением: пусть B = 1, тогда по условию C = 0 и D = 0. Но тогда из трех конъюнкций, составляющих К две будут верны: , а это противоречит условию. Значит В= 0. Видно, что C= 1удовлетворяетусловиюзадачи, и это решение единственно, так как если предположить, что D = 1, то это будет означать, что , а значит, что либо В, либо С равно 1, но это противоречит тому, что преступник только один.
Таким образом, преступник – Смит, оба его высказывания ложны, у Брауна одно высказывание ложно, одно нет, а Джонс сказал правду.
Все эти рассуждения используются не только для решения логических задач (которые действительно приходится решать следователям), но и для составления игровых программ (компьютерная игра ШЕРЛОК, содержащая больше 60 тыс. логических задач, составлена с использованием тех же самых конъюнкций, дизъюнкций и отрицаний).