Лекция № 8. Логические функции.

Ниже будет подробно рассматриваться двухэлементное множество и двоичные переменные, принимающие значения из этого множества. Его элементы часто обозначают 0 и 1, однако они, вообще говоря, не являются числами в обычном смысле (хотя и похожи на них по некоторым свойствам). Наиболее распространённая интерпретация двоичных переменных – логическая: “да” – “нет”, “истинно” – “ложно”. В контексте, содержащем одновременно двоичные и арифметические величины, а также функции, эта интерпретация обычно фиксируется явно. Например, в языках программирования (Pascal и др.) вводится специальный тип переменной – логическая переменная, значения которой обозначаются true и false. В данной лекции логическая интерпретация двоичных переменных не везде является обязательной, поэтому будем считать, что , рассматривая 0 и 1 как формальные символы, не имеющие арифметического смысла.

 

1. Функции алгебры логики.

 

Определение. Алгебра, образованная множеством вместе со всеми возможными операциями на нём, называется алгеброй логики.

Определение. Функцией алгебры логики (логической функцией) называется арная операция на множестве .

Первый термин является более точным, однако второй более распространён, особенно в приложениях. Он и будет использоваться в дальнейшем. Итак, логическая функция - это функция, принимающая значения 0 или 1. Множество всех логических функций будем обозначать , множество всех логических функций переменных - .

Определение. Алгебра, образованная элементным множеством вместе со всеми операциями на нём, называется алгеброй значной логики, а арная операция на элементном множестве называется значной логической функцией.

Множество всех значных логических функций обозначается . Мы в дальнейшем будем рассматривать логические функции только из .

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

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

Таблица 1.

Заметим, что наборы в таблице расположены в определённом порядке – лексикографическом, который совпадает с возрастанием наборов, если рассматривать их как двоичные числа. Этим упорядочением будем пользоваться в дальнейшем. При любом фиксированном упорядочении наборов логическая функция переменных полностью определяется вектор-столбцом значений функции, то есть . Поэтому число различных функций переменных равно числу различных двоичных векторов длины .

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

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

Практический смысл удаления фиктивных переменных очевиден, поскольку они не влияют на значение функции и являются с этой точки зрения лишними. Однако иногда бывает полезно вводить фиктивные переменные. Благодаря такому введению можно всякую функцию переменных сделать функцией любого большего числа переменных. Поэтому любую конечную совокупность функций можно считать зависящей от одного и того же множества переменных (которое является объединением множеств переменных всех взятых функций).

1. Примеры логических функций.

 

Логических функций одной переменной четыре; они приведены в таблице 2.

 

Таблица 2.

Здесь функции и - константы 0 и 1 соответственно, значения которых не зависят от значения переменной, и, следовательно, переменная для них несущественна. Значения функции совпадают со значениями переменной . Наконец, функция , значения которой противоположны значениям переменной, есть ни что иное, как отрицание (функция НЕ). Различные способы обозначения этой функции: .

Логических функций двух переменных – шестнадцать; они приведены в таблице 3.

0 0
0 1
1 0
1 1

Таблица 3.

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

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

Функция является конъюнкцией переменных и (функцией И). Она равна 1 тогда и только тогда, когда обе переменные равны 1. Обозначается: , . Её также называют логическим умножением, поскольку таблица её действительно совпадает с таблицей обычного умножения для чисел 0 и 1. Поэтому, кстати, по аналогии с обычным умножением, знак операции между переменными часто опускают: .

Операцию будем называть умножением по модулю 2 (см. ниже). Она реализует произведение остатков от деления чисел 0 и 1 на число 2.

Функция называется дизъюнкцией переменных и (функцией ИЛИ). Она равна 1, если значения или равны 1. Союз “или” понимается здесь в неразделительном смысле “хотя бы один из двух”. Обозначается: .

Функция называется неравнозначностью переменных и . Она равна 1, когда значения аргументов различны, и равна 0, когда значения аргументов одинаковы. Обозначается: .

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

Два целых числа и называются сравнимыми по модулю , если при делении на это число они дают одинаковые остатки.

Обозначается: . Например, , . Так вот, функцию можно рассматривать, как сложение по модулю 2. Действительно, сумма остатков от деления чисел 0 и 1 на число 2 равна 1, а сумма остатков от деления чисел 0 и 0, либо 1 и 1 на 2 равна 0.

Функция называется импликацией или логическим следованием. Обозначается: .

Функция называется эквивалентностью или равнозначностью. Она равна 1, если значения переменных одинаковы и 0, если они различны. Обозначается: .

Есть ещё две функции двух переменных, имеющие специальные названия. Функция называется стрелкой Пирса и обозначается . Функция называется штрихом Шеффера и обозначается . Остальные функции специальных названий не имеют и, как можно показать, легко выражаются через перечисленные выше функции.

В функциях и переменная фиктивна. Из таблицы 3 видно, что , а . Аналогично, в функциях и переменная фиктивна: , а .

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

 

1. Суперпозиции и формулы.

 

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

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

Определение. Говорят, что формула имеет глубину , если она имеет вид , где , а формулы, максимальная из глубин которых равна . При этом называются подформулами формулы , а называется внешней, или главной операцией формулы .

Соответственно, формулы также могут иметь подформулы, которые являются в этом случае и подформулами формулы . Например, выражение в наших обозначениях – это формула глубины 1. Выражение является формулой глубины 3, содержащей одну подформулу глубины 2 и две подформулы глубины 1.

В дальнейшем конкретные формулы будем записывать в более привычном виде, при котором условные знаки функций стоят между аргументами (такую запись называют инфиксной). Например, если является конъюнкцией, дизъюнкцией, а импликацией, то приведённая выше формула примет вид .

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

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

Всякая формула, выражающая данную функцию, как суперпозицию других функций, задаёт способ её вычисления (при условии, что известно, как вычислять исходные функции). Этот способ определяется следующим очевидным правилом: формулу можно вычислить, только если уже вычислены значения всех её подформул. Применим, например формулу к набору . Получим: . Далее получим . Наконец, .

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

В отличие от табличного задания представление данной функции формулой не единственно. Например, если в качестве исходного множества функций зафиксировать функции из предыдущего пункта (то есть функции И, ИЛИ, НЕ), то функцию - штрих Шеффера – можно представить формулами и . Функцию - стрелка Пирса – можно представить формулами и .

Определение. Формулы, представляющие одну и ту же функцию называются эквивалентными или равносильными.

Эквивалентность формул принято обозначать знаком равенства, поэтому можно записать: .

Существует стандартный метод для выяснения эквивалентности двух формул. По каждой формуле восстанавливается таблица функции, а затем две полученные таблицы сравниваются. Таким способом в предыдущеё лекции мы устанавливали равносильность высказываний. Он весьма громоздок, так как требует вычислений, если считать, что обе формулы зависят от переменных. Более простыми методами, позволяющими устанавливать эквивалентность данных формул, а также получать новые формулы, эквивалентные исходной, являются эквивалентные преобразования, которые будут рассмотрены в дальнейшем.

Назад, в начало конспекта.

 

 

Лекция № 9. Булевы алгебры.

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

 

1. Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.

Введём обозначения: . Пусть параметр, равный 0 или 1. Тогда , если , и , если .

Теорема 8.1. Всякая логическая функция может быть представлена в следующем виде:

,

где , а дизъюнкция берётся по всем наборам значений переменных .

Равенство (1) называется разложением по переменным . Формула (1) достаточно громоздка на вид, однако её несложно использовать при небольших значениях и . Например, при значениях , разложение (1) имеет вид:

.

Практический смысл такого разложения очевиден: оно позволяет заменять функцию нескольких переменных суперпозицией конечного числа функций с меньшим количеством переменных. Особенно важен частный случай , когда разложение производится по всем переменным. При этом все переменные в правой части равенства (1) получают фиксированные значения, и функции в конъюнкциях правой части становятся равными 0 или 1, что даёт:

,

где дизъюнкция берётся по всем наборам , на которых . Такое разложение называется совершенной дизъюнктивной нормальной формой (СДНФ) функции . СДНФ содержит ровно только конъюнкций, сколько единиц в таблице функции ; каждому единичному набору соответствует дизъюнкция всех переменных, в которых взято с отрицанием, если и без отрицания, если . Таким образом, существует взаимно однозначное соответствие между таблицей функции и её СДНФ. Следовательно, для каждой логической функции СДНФ является единственной (с точностью до порядка переменных и конъюнкций).

Пример 1. Составить СДНФ для функции, заданной таблицей:

 

Поскольку данная таблица (уже встречавшаяся ранее) содержит три единичных набора, СДНФ будет конъюнкцией трёх дизъюнкций. В свою очередь, каждая дизъюнкция включает три переменных – по числу их в функции .

Получим: .

Напомним, что, подобно знаку умножения, знак дизъюнкции в логических формулах часто опускают. Тогда полученное выражение примет более компактный вид:

.

Единственная функция, которая не имеет СДНФ – это константа .

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

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

 

1. Булева алгебра функций.

Выше мы обозначили множество всех логических операций на двухэлементном множестве , как .

Определение. Булевой алгеброй логических функций называется алгебра вида , основным множеством которой является всё множество логических функций, а операциями – дизъюнкция, конъюнкция и отрицание.

Замечание. На практике мы имеем дело не самими функциями, а с представляющими их формулами, то есть с алгеброй формул, которая значительно шире, поскольку каждую функцию представляет бесконечное множество формул. Чтобы “синхронизировать” их алгебре формул придаётся следующий вид. Элементами алгебры формул объявляются не сами формулы, а классы эквивалентности формул, то есть классы формул, представляющих одну и ту же функцию. Определённая таким образом, алгебра формул называется алгеброй Линденбаума - Тарского. Она изоморфна булевой алгебре функций.

Теперь рассмотрим основные свойства булевых операций (частично уже знакомые по теме “Элементы математической логики”).

1. Ассоциативность: а) ; б) .

2. Коммутативность: а) ; б) .

3. Дистрибутивность конъюнкции относительно дизъюнкции: .

4. Дистрибутивность дизъюнкции относительно конъюнкции:

.

5. Идемпотентность: а) ; б) .

6. Двойное отрицание: .

7. Свойства констант: а) ; б) ; в) ; г) ; д) ; е) .

8. Правила де Моргана: а) ; б) . Очень важные соотношения, которые часто будут использоваться в дальнейшем. С их помощью (а также с помощью соотношения 6) дизъюнкция заменяется конъюнкцией и наоборот.

9. Закон противоречия: .

10. Закон “исключённого третьего”: .

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

При подстановке формулы вместо переменной все вхождения данной переменной в исходное соотношение должны быть одновременно заменены формулой .

Правило подстановки позволяет получать из соотношений 1 – 10 новые эквивалентные соотношения. Заметим, что равенство означает в данном контексте, что формулы и описывают одну и ту же логическую функцию. Следовательно, если какая-то формула содержит в качестве подформулы, то замена её на не изменит значения формулы . Это утверждение представляет собой правило замены подформул, которое позволяет, используя эквивалентные соотношения, получать формулы, эквивалентные данной. Практическое применение описанных правил будет рассмотрено ниже.

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

 

1. Эквивалентные преобразования.

Пример 2. Возьмём соотношение 8а и подставим вместо переменной выражение . Получим: . Здесь в обеих частях стоят формулы, неэквивалентные исходным формулам, но эквивалентные между собой. Если же в правой части нового соотношения формулу заменить формулой , эквивалентной ей в силу соотношения 8а и затем заменить на (согласно 6), то получим . Причём все формулы в полученной цепи преобразований являются эквивалентными:

.

Такие преобразования, использующие эквивалентные соотношения и правило замены, называют эквивалентными преобразованиями. Эквивалентные преобразования являются мощным средством доказательства эквивалентности формул, как правило, более эффективным, чем их вычисление на наборах значений переменных.

В булевой алгебре принято опускать скобки в следующих двух случаях: а) при последовательном выполнении нескольких конъюнкций или дизъюнкций; б) если они являются внешними скобками у конъюнкции. Оба соглашения совершенно аналогичны общепринятому опусканию скобок для операции умножения в арифметических выражениях.

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

а) Поглощение: 1) и 2) . Докажем данное равенство подробно, используя для доказательства соотношения 3, 7а и 7в.

.

Далее будем опускать доказательства приводимых равенств, которые при желании можно получить из соотношений 1 – 10 и уже доказанных равенств.

б) Склеивание: .

в) Обобщённое склеивание: .

г) .

Одним из главных видов упрощения формул является приведение их к дизъюнктивной нормальной форме (ДНФ).

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

Заметим, что СДНФ является частным случаем ДНФ.

Приведение формулы к ДНФ выполняется так. Сначала с помощью соотношений 6 и 8 все отрицания “спускаются” до переменных. Затем раскрываются скобки. После этого с помощью соотношений 5, 9 и 10 удаляются лишние конъюнкции и повторения переменных в конъюнкциях. Наконец, с помощью соотношений 7а – 7е удаляются лишние константы. При этом необходимо помнить, что ДНФ данной формулы может быть не единственной.

Пример 3. Привести к ДНФ формулу .

Решение:

. В итоге получили дизъюнкцию элементарных конъюнкций, то есть ДНФ.

Доказано, что если из формулы можно с помощью эквивалентных преобразований получить формулу , то можно из формулы (с помощью тех же соотношений) получить формулу . Иначе говоря, всякое эквивалентное преобразование обратимо. Это позволяет сформулировать следующую теорему.

Теорема 8.3. Для любых двух эквивалентных формул и существует эквивалентное преобразование в и наоборот с помощью соотношений 1 – 10.

Аналогично понятию ДНФ определяется понятие конъюнктивной нормальной формы (КНФ), то есть КНФ есть конъюнкция элементарных дизъюнкций. Переход от КНФ к ДНФ и обратно всегда осуществим (обычно, с помощью формул Де Моргана).

Пример 4. Привести формулу к КНФ.

Заменим исходную формулу её двойным отрицанием, а затем применим соотношения 8.

.

 

Назад, в начало конспекта.