Основные положения теории булевых функций

ВВЕДЕНИЕ Теория автоматов наиболее тесно связана с теорией алгоритмов. Это объясняется тем, что автомат преобразует дискретную информацию по шагам в дискретные моменты времени. На входе и выходе автомата могут быть символы, слова или выражения какого-либо языка, представляющие собой элемент дискретной информации. Преобразование элементов входной информации в элементы выходной информации выполняется по заданному алгоритму. Эти преобразования возможны с помощью технических и/или программных средств. С помощью средств вычислительной техники создаются сложные программно-технические комплексы для автоматизации рабочих мест на производстве и в управлении, для автоматизации деятельности в организациях и на предприятиях, для автоматизации научных исследований и конструирования. Единый подход в описании технических и программных средств определил понятие "автомат", как математическую модель системы, обеспечивающей прием, хранение и обработку информации. Ограничение числа параметров математической модели определило новое понятие - "конечный автомат". Раздел науки, посвященный изучению таких математических моделей, называют теорией автоматов. Большинство задач теории конечных автоматов включает в себя задачи анализа поведения автомата при обработке информации и синтеза его структуры для заданного алгоритма. При анализе автомата важным является исследование способов описания математической модели. На этом этапе изучают поведение автомата при различных возмущающих воздействиях со стороны окружающей среды и минимизируют число состояний автомата для работы по заданному алгоритму. Этот этап называют также макроподходом, а автомат – абстрактным. Для точной постановки задач анализа автомата и диагностирования его поведения используют алгебру автоматных языков. При синтезе автоматов важным является исследование способов построения сложных автоматов. На этом этапе создают сеть из элементарных автоматов, эквивалентную абстрактному автомату. Этот этап называют микроподходом, а автомат – структурным. Для точной постановки задач синтеза структуры автомата широко используют алгебру логики . Лекция №1. Основные положения теории булевых функций Из идей математической логики возникла теория булевых функций, являющаяся теоретической базой современных ЭВМ, возникло понятие алгоритма, что позволило решать многие неразрешимые проблемы. Именно через математическую логику, теорию булевых функций и теорию алгоритмов происходит сейчас проникновение математических методов в биологию, лингвистику, экономику, вплоть до философии естествознания. Система элементов с определенными в ней операциями конъюнкции (  или логического «И»-умножения), дизъюнкции ( V или логического «ИЛИ»-сложения), эквивалентности (=) и отрицания ( инверсия, НЕ ) – образует алгебру Буля. В алгебре Буля «ИСТИНА» обозначается как 1, а «ЛОЖЬ» – как 0. Функция называется булевой, если она принимает только два значения: 0 или 1, как и все переменные . Следовательно, областью определения булевой или логической функции является множество векторов , каждая координата которого принимает значения из множества {0,1}. Очевидно, что область определения X функции содержит различных векторов ( логических комбинаций из 0 и 1). Каждый конкретный вектор из 0 и 1 будем называть двоичным набором или просто набором. Булева функция, зависящая от n аргументов, называется n-местной и является полностью заданной, если указаны ее значения для всех наборов значений аргументов.Так как число различных наборов для любой функции равно , т. е. конечно, то любую булеву функцию можно задать таблицей с строками. Например: при n=2 xy = 00, 01, 10, 11. Для каждой комбинации переменных логическая функция F может принимать значение 0 или 1, следовательно для n переменных существует различных логических функций. Например: если n=2, то L2 =16; если n=4, то L4 =65536. Функции одной и двух логических переменных называются элементарными. x1 x2 xn-1 xn f (x1 , x2 ... , xn) x f ( 0 0 ... 0 0 ) 1 f ( 0 0 ... 0 1 ) 1 1 f ( 0 0 ... 1 0 ) 2 1 1 f ( 0 0 ... 1 1 ) 3 ... ... ... ... ... ... 1 1 1 f ( 1 1 ... 1 0 ) -1 1 1 1 1 f ( 1 1 ... 1 1 ) Так как наборы значений переменных записываются в стандартном порядке, то две различные булевы функции от n переменных будут отличаться только столбцом значений функции. Если же две логические функции и принимают на всех возможных наборах одинаковые значения, то они считаются равными: Функция существенно зависит от элемента , если В противном случае говорят, что от функция зависит несущественно и является фиктивным аргументом. Функция не изменится, если к ее аргументам приписать любое число фиктивных аргументов или зачеркнуть те аргументы, которые являются фиктивными. Пример имеет фиктивный аргумент . 1 1 1 1 1 1 Значения функции могут быть заданы не на всех наборах аргументов. На некоторых наборах значения функции могут быть не определены. Такие функции мы будем называть неполностью определенными или недоопределенными. В таблице задания функции против наборов, на которых функция не определена, ставится * . Пример. 1 * 1 1 1 1 1 1 * 1 1 1 1 * 1 1 1 1 Здесь функция не определены на трех наборах. Если ее доопределить, то существует способов доопределения. Вообще, если функция не определена на m наборах, то путем произвольного доопределения из нее можно получить различных полностью определенных функций. Элементарные булевы функции Логические функции одной переменной. Для одной переменной число функций равно 4. Все эти функции F1, F2, F3, F4 представлены в таблице 1, которая называется таблицей истинности логических функций. Значение функций F1 и F2 не зависят от значения аргумента X . Это константы F1=1 и F2=0. Значение функции F3 повторяют значения аргумента X, F3 = X. Наконец, значения функции F4 противоположны значениям аргумента. Функции F1, F2, F3 являются тривиальными и практического интереса не представляют. Функция F4 называется отрицанием или инверсией и обозначается. Рассмотрим полный набор логических функций двух переменных, состоящий из 16-ти различных функций, каждая из которых определена на 4-х наборах. Из таблицы видно, что восемь функций могут быть поучены из других восьми путем применения операции отрицания. Некоторые логические функции обладают определенными свойствами, получившими название “замечательные” свойства. Всего различают пять “ замечательных”свойств. В табл.2 эти свойства отмечены номерами: 1- свойство сохранять нуль, 2-свойство сохранять единицу, 3- самодвойственность, 4-монотонность, 5-линейность. Более подробно об этих свойствах сказано дальше. 3.2. Принцип суперпозиции. Законы и тождества алгебры логики Выражения, построенные из конечного числа логических переменных, знаков логических функций, а также констант 0 и 1 называют булевыми формулами. Каждая булева формула может рассматриваться как некоторая булева функция от логических переменных, значение которой на каждом наборе переменных можно получить, если подставить значения переменных (0 или 1) на этом наборе в формулу и произвести указанные логические операции. В логическую формулу вместо любой ее буквы можно подставить как независимую переменную, так и переменную, являющуюся функцией других переменных. Вэтом заключается принцип суперпозиции, т.е. подстановки булевых функций вместо аргументов в другую булеву функцию. С помощью принципа суперпозиции любая булева функция может быть представлена как некоторая комбинация функций двух переменных, полный набор которых представлен в табл.2. Могут быть построены различные логические функции A(X,Y,Z,...) и B(X,Y,Z,...) от одних и тех же логических переменных X,Y,Z,... которые имеют одни и те же значения на всех одинаковых наборах переменных, т.е. A(X,Y,Z,...) = B(X,Y,Z,...) Такое соотношение называется логическим тождеством. Для проверки тождества можно строить таблицы истинности для левой и для правой частей и сравнивать значения функций на всех наборах переменных. Например, рассмотрим тождество . Построим таблицу истинности для левой и для правой частей выражения и сравним их значения на всех наборах переменных X и Y. Из таблицы видно, что это выражение представляет собой тождество. Рассмотрим важнейшие тождества алгебры логики. Если некоторая логическая функция тождественно равна единице, то она называется тавтологией. Если нулю - противоречием. 3.3. Способы задания логической функции Существует ряд способов задания логической функции. Рассмотрим важнейшие из них. 1. Формула, указывающая последовательность логических операций, которые нужно произвести над высказываниями - аргументами, чтобы получить значение функции. Например, F(X1, X2, X3) = X1∙X2 →X3. 2. Таблица истинности. В таблице указываются значения функции в зависимости от значений истинности аргументов. Если функция зависит от n аргументов, то число всех наборов аргументов равно 2n. В таблице истинности указываются все наборы и значение функции на каждом наборе. 3. Числовой способ задания функции. Каждой независимой переменной- аргументу функции ставится в соответствие число 2k (k = 0, 1, 2,...). Аргументы функции записываются в виде упорядоченного множества, например, F(X1, X2, X3). При этом переменная, записанная крайней справа, получает коэффициент 20= 1, переменная, стоящая рядом слева, получает коэффициент 21=2 и т. д. Так, для функции F(X1, X2,X3) независимые переменные получают следующие коэффициенты: X3=1, X2=2, X1=4. Для каждого набора независимых переменных определяется число номер N по формуле N = 4 ∙ X1 + 2 ∙ X2 + 1 ∙ X3. При задании функции указывают номера тех наборов, на которых функция равна единице, и перед списком номеров единичных наборов ставят знак дизъюнкции. Можно также указать те номера наборов, на которых функция равна нулю, но при этом перед списком нулевых наборов ставят знак конъюнкции. Например, функция, заданная таблицей истинности (табл.4) может быть записана следующим образом: F(X,Y,Z) =∨(0,1,4,7) = ∧(2,3,5,6). 4. Геометрический способ задания логической функции. Для функции n - независимых логических переменных рассматривается единичный n- мерный куб. Вершины куба соответствуют наборам независимых переменных. Каждой вершине приписывают значение функции на соответствующем наборе. На рисунке единичные наборы помечают, например, кружками. 5. Логическая схема, представляющая собой условное графическое обозначение логических функций. На рисунке показаны графические обозначения некоторых элементарных логических функций . На рисунке показан пример логической схемы. Логические сети Пусть имеется конечное множество А: а . Пусть – множество логических функций. Тогда совокупность множеств А, В совместно с однозначным отображением множества А на F называется логической сетью. Логическую сеть можно представить в виде графа, вершины которого имеют номера из множества А и соответствуют логическим функциям из F, а дуги определяются элементами из . Пример Т. о., можно сказать, что логическая сеть представляется орграфом с перенумерованными вершинами, которые соответствуют логическим функциям из заданного множества. Рассмотрим теперь множество элементы которого назовем входами логической сети и зададим отображение некоторых подмножеств из X на некоторые элементы из А, т. е. . Геометрической интерпретацией этого отображения являются дуги, входы сети и вершины графа. Например, для рассматриваемой логической сети можно определить Потребуем, чтобы соответствующий граф не содержал циклов и являлся бы упорядоченным, т. е. для любой дуги ( i, j ) выполнялось бы i