Понятие логической функции

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

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

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

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

Столь энергичный выход математической логики за пределы математики объясняется тем, что ее аппарат легко распространяется на объекты самой общей природы, лишь бы только они характеризовались конечным числом состояний.

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

Устоявшееся представление о математической логике как науке, изучающей законы мышления с применением аппарата математики, главным образом, для нужд самой математики, в современных условиях становится слишком узким. С расширением областей применения и дальнейшим развитием математической логики изменяется и взгляд на нее. Объектами математической логики являются любые дискретные конечные системы, а ее главная задача – структурное моделирование таких систем.

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

и И (истинно).

Отношения между булевыми переменными представляются булевыми функциями, которые подобно числовым функциям могут зависеть от одной, двух и, вообще, n переменных (аргументов). Запись у = f(x₁, x₂, …,x_N) означает, что у - функция аргументов x₁, x₂, …,x_N. Важнейшая особенность булевых функций состоит в том, что они, как и их аргументы, принимают свои значения из двухэлементного множества {0,1}, или (И, Л}, т. е. характеризуются одним из двух возможных состояний.

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

Отрицание - функция у = f(х), принимающая значения 1, когда х = 0, и значение 0, когда х = 1; она обозначается у = (читается «не х»).

Дизъюнкция — функция у = f(x₁, x₂), принимающая значение 0 тогда и только тогда, когда оба аргумента имеют значение 0; она обозначается у = x₁ \/ x₂ (читается «у = x₁ или x₂»).

Конъюнкция—функция у = f(x₁, x₂), принимающая значение 1 тогда и только тогда, когда оба аргумента имеют значение 1; она обозначается у = x₁ /\ x₂ («у = x₁ и x₂»).

Таблицы для этих функций имеют вид:

			x1 \/ x2			x1 /\ x2
x1	x2		x1	x2
x

Логические операции и формулы. Булевы функции можно рассматривать как логические операции над величинами, принимающими два значения - 0 и 1. Отрицание - это одноместная операция, а дизъюнкция и конъюнкция — двухместные операции. При этом выражения , x₁ \/ x₂, x₁ /\ x₂ являются логическими формулами.

Более сложные формулы получаются замещением входящих в них переменных другими логическими формулами, которые обычно заключаются в скобки. Например, положив x₁ = и x₂ = b /\ c из x₁ V x₂,имеем () \/ (b c). Каждая формула определяет некоторую булеву функцию. Ее значение при различных значениях переменных определяется на основании таблиц функций, приведенных в (2). Так, при а = 0, b = 1 и с = 0 имеем:

x₁ = = =1, x₂ = b /\ с = 1 /\ 0 = 0 и x₁ \/ x₂ = \/ (b \/ c) = 1 \/ 0 = 1. Аналогично получаем значения функции и при других комбинациях значений аргументов.

Две функции (как и определяющие их формулы) считаются равносильными,если при любых значениях аргументов эти функции (формулы) принимают одинаковые значения. Равносильные функции соединяются знаком равенства, например: (х /\ у) \/ = () /\ z или ((х \/ ) /\ у) \/ (у \/ х) == х \/ у. Равносильность функций проверяется по таблицам основных операций, причем необходимо сравнить их значения для всех комбинаций значений переменных.

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

На основе определения основных операций нетрудно убедиться в справедливости следующих тождеств (свойств) булевой алгебры:

коммутативность

х \/ y = y \/ х, х /\ y = y /\ х;

ассоциативность

х \/ (y \/ z) = (х \/ y) \/ z, х /\ (y /\ z) = (х /\ y) /\ z;

дистрибутивность

х /\ (y \/ z) = (х /\ y) /\ (х \/ z), х \/ (y /\ z) = (х /\ y) /\ (х \/ z);

свойство констант

х \/ 0 = x, х /\ 1 = x;

свойство отрицания

х \/ = 1, х /\ = 0.

Приведенные свойства позволяют получить ряд других важных законов и тождеств уже без обращения к таблицам соответствия: (законы де Моргана), х \/ (х /\ у) = х /\ (х \/ у) = х (законы поглощения) х \/ х = х /\ х = х (законы идемпотентности), а также тождества x \/ y; (x /\ y) \/ (x /\ z) \/ (x /\ ); = (x /\ z) \/ (y /\ ); = x; = 0;

= 1; x \/ 1 =1; x /\ 0 = 0 и т. д.

Так, законы идемпотентности доказываются следующими преобразованиями:

х \/ х = (х \/ х) /\ 1 = (х \/ х) /\ (х \/ ) = х \/ (х /\ (х \/ х)) = х \/ 0 = х;

х /\ х = (х /\ х) \/ 0 = (х /\ х) \/ (х /\ ) = х /\ (х \/ ) = х /\ 1 = х.

Используя полученные соотношения, имеем:

х \/ 1 = x \/ (x \/ ) = (х \/ х) \/ = х \/ = 1; x /\ 0 = x /\ (x /\ ) = x /\ = 0.

Доказательство законов поглощения имеет вид:

x \/ (x /\ y) = (x /\ 1) \/ (x /\ y) = x /\ (1 /\ y) = x /\ 1 = x;

x /\ (x \/ y) = (x \/ 0) /\ (x \/ y) = x \/ (y /\ 0) = x \/ 0 = x.

Соотношение = х доказывается следующим образом:

из х \/ = 1 по закону коммутативности следует \/ x = 1, откуда сравнением с = 1 имеем х = .

Интересно доказательство закона де Моргана. На основании свойств отрицания равенство функций и должно означать, что

(х \/ у) \/ () = 1 и (х \/ у) \/ () = 0.

Действительно,

(х \/ у) \/ () = ((х \/ у) \/ ) /\ ((х \/ у) \/ ) = ((x /\ ) \/ y) /\ (x \/ (y \/ )) =

= (1 \/ y) /\ (x \/ 1) = 1 /\ 1 = 1, а также

(х \/ у) /\ () = (х /\ \/ () = (у /\ () = ((x /\ ) /\ ) \/ ((y /\ ) /\ ) =

= (0 /\ ) \/ ( /\ 0) = 0 \/ 0 = 0.

Следовательно, соотношение = доказано. Аналогично доказывается и второй закон.

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

((х₁ \/ x₂) \/ (х₃ \/ x₄) \/ х₅ = х₁ \/ x₂ \/ х₃ \/ x₄ \/ х₅,

а также (х₁ /\ x₂) /\ (x₃ /\ (х₄ /\ x₅) = х₁ /\ x₂ /\ x₃ /\ х₄ /\ x₅.

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

Еще одно упрощение связано с символикой. Знак конъюнкции в формулах можно опустить и вместо х /\ у писать ху. Операцию конъюнкции часто называют логическим умножением, а операцию дизъюнкции - логическим сложением.

С учетом приведенных условий запись существенно упрощается. Например, формуле (x /\ (y /\ )) \/ (() /\ z) соответствует запись \/ z.

Переключательные схемы. В качестве одной из интерпретаций булевых функций рассмотрим электрическую схему, состоящую из источника напряжения (батареи), лампочки и одного или двух ключей (х₁ и x₂). Ключи управляются кнопками с двумя состояниями: кнопка нажата (1) и кнопка отпущена (0). Если в исходном состоянии ключ разомкнут, то при нажатии кнопки он замыкается.

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

При соответствующих состояниях кнопок лампочка принимает одно из двух состояний: горит (1) и не горит (0). Состояния кнопок отождествляются со значениями булевых переменных х₁ и x₂, а состояние лампочки — со значением функций этих переменных.

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

Операции отрицания соответствует схема с одним нормально замкнутым ключом (рис. 17, а). Если кнопка нажата (х = 1), ключ разомкнут и лампочка не горит, т. е. f(х) = 0; при отпущенной кнопке (х = 0) ключ замкнут и лампочка горит, т. е. f(x) = 1. Операциям дизъюнкции и конъюнкции соответствуют схемы с двумя нормально разомкнутыми ключами (рис. 17, б, в). Легко убедиться, что в схеме рис. 17, б лампочка горит при нажатии хотя бы одной из кнопок, а в схеме рис. 17, в - только при нажатии обеих кнопок одновременно.

Рис. 18. Переключательная схема, реализующая логическую функцию (а), и упрощенная схема(б).

Любую сложную булеву функцию можно представить некоторой переключательной схемой. На рис. 18,а показана схема, реализующая функцию у = х₁ \/ x₂x₃ \/ x₃x₄. Та же функция представляется равносильной формулой у = х₁ \/ ( x₂ \/ x₄)x₃, которой соответствует другая более простая схема (рис. 18, б). Следует иметь в виду, что ключи, обозначенные одинаковыми буквами (х или ), связаны между собой и управляются общей кнопкой.

В реальных устройствах используются ключи различной конструкции и физической природы (механические, электромагнитные, электронные, гидравлические, пневматические и т. д.) Однако при реализации логических функций многие технические особенности не имеют значения. Существенными свойствами контактных схем являются исходные положения ключей (нормально разомкнуты или нормально замкнуты) и способ их соединения между собой и внешними устройствами. Эта информация полностью отображается графом, ребра которого соответствуют ключам, а вершины - точкам их соединения. Ребра нормально разомкнутых ключей обозначаются соответствующей переменной (х), а нормально замкнутых - отрицанием переменной (х). Например, контактная схема (рис. 23, б) изображается графом, как показано на рис. 19, а.

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

Рис. 19. Граф переключательной схемы (а) и его упрощенное изображение (б).

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

На рис. 19,б показана контактная схема в обычно принятом виде.

Высказывания. Пусть х₁ и x₂ - некоторые высказывания, которые могут быть истинными (1) или ложными (0), например: «Я пойду в театр» (х₁) и «Я встречу друга» (x₂). Дизъюнкцией х₁ \/ x₂ является сложное высказывание «Я пойду в театр или встречу друга», а конъюнкцией х₁ /\ x₂ - высказывание «Я пойду в театр и встречу друга».

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

Итак, высказывания можно рассматривать как двоичные переменные, а связки «не», «или», «и», с помощью которых образуются сложные высказывания, - как операции над этими переменными. В алгебре высказываний используются еще две операции: импликация х₁ → x₂, соответствующая связке «если, то» и эквиваленция х₁ ~ x₂, соответствующая связке «если и только если». Они задаются следующими таблицами:

В нашем примере импликацией будет высказывание: «Если пойду в театр, то встречу друга», а эквиваленцией – пойду в театр, если и только если встречу друга». Как видно из таблиц, импликация высказываний ложна только в случае, когда первое из простых высказываний истинно, а второе ложно. Эквиваленция является истинным высказыванием, если оба простые высказывания истинны или ложны одновременно.

Обозначив буквами простые высказывания, можно представить сложное высказывание формулой с помощью соответствующих связок. Например, высказыванию «Если давление масла на шарик клапана больше усилия его пружины (х₁), то масло открывает клапан (х₂) и частично перетекает из нагнетательной полости во впускную (х₃)» соответствует формула х₁ → х₂ х₃.

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

Предикат представляет собой логическую функцию Р(х), принимающую, как и булевы функции, значение 0 или 1, но в отличие от них, значения аргумента х выбираются из некоторого множества М объектов (х М). В общем случае такая функция может зависеть от многих аргументов х₁, х₂,...,х_n, принимающих значения из одного и того же или различных множеств. Ее записывают Р(х₁, х₂,...,х_n) и называют n-местным предикатом. Например: «х - четное число», «х - компонент цепи» - одноместные предикаты Р(х);

«х брат у», «х меньше у» — двуместные предикаты Р(х, у); «х и у - родители z»,

«х - сумма y и z» - трехместные предикаты Р(х, y, z) и т. д. Если аргументы х₁, х₂,...,х_n замещены конкретными значениями (объектами), то предикат переходит в высказывание, которое рассматривают как 0 - местный предикат.

Так как предикаты способны принимать только значения 0 и 1, то их, как и булевы переменные, можно связывать логическими операциями. В результате получаем формулы, определяющие более сложные предикаты. Так, если Р(х) означает «х - инженер», а Q(х) - «x - сотрудник нашего отдела», то Р(х) /\ Q(х) = R(х) есть одноместный предикат «х - инженер и сотрудник нашего отдела» или проще «х - инженер нашего отдела». Очевидно, если Р - множество инженеров, а 0 - множество сотрудников данного отдела, то этот предикат соответствует пересечению Р Q. Таким образом, имеет место тесная связь между логикой предикатов и операциями над множествами.

Однородные функции. Если аргументы принимают значения из того же множества, что и сама функция, то ее называют однородной функцией. В этом случае X₁ = Х₂ =... = Х_n = N и однородная функция, рассматриваемая как закон композиции определяет некоторую п-местную операцию на конечном множестве N.

Областью определения однородной функции у = f(х₁, х₂,..., x_n) служит множество наборов (х₁, х₂,..., x_n), называемых словами, где каждый из аргументов х₁, х₂,..., x_n замещается буквами k- ичного алфавита {0, 1,..., k -1}. Количество п букв в данном слове определяет его длину.

Очевидно, число всевозможных слов длины n в k -ичном алфавите равно kⁿ. Так как каждому такому слову имеется возможность предписать одно из k значений множества N, то общее количество однородных функций от п переменных выражается числом k^(kn).

Если буквами алфавита служат числа от 0 до k - 1, то каждое слово (х₁, х₂,..., x_n) символически представляется упорядоченной последовательностью п таких чисел и рассматривается как запись n -разрядного числа в позиционной системе счисления с основанием k, т. е. x₁k^{n -1} + x₂k^{n –2} + … + x_{n -1}k¹ + x_nk⁰. Числа q = = 0, 1,..., kⁿ - 1 служат номерами слов и тем самым на множестве всех слов вводится естественная упорядоченность (отношение строгого порядка). Аналогично номерами функций можно считать kⁿ -разрядные числа в той же системе счисления.

Различные слова длины п в данном алфавите образуются как n -перестановки с повторениями (2. 10. 1). Так, в трехзначном алфавите {0, 1, 2} словами длины 4 будут все четырехразрядные числа с основанием k = 3, т. е. 0000, 0001, 0002, 0010, 0011,..., 2221, 2222, которые соответствуют десятичным числам от 0 до 80 = 2 • З³+ 2 • З²+ 2 • З¹ + 2 • 3⁰. Поставив каждому такому четырехразрядному числу в соответствие одну из букв алфавита {0, 1, 2}, получим некоторую функцию четырех переменных f_i(х₁, х₂, x₃, x₄), причем количество таких функций выражается огромным числом 3⁸¹.

Пусть алфавит состоит из трех букв русского алфавита {о, п, т}. Множество пятибуквенных слов в этом алфавите состоит из 3⁵ = 243 элементов. Наряду с такими имеющими прямой смысл словами, как «топот» и «потоп», оно также включает все другие 5-перестановки, например: «ооппт», «поппп», «тттоп» и др.

Примерами однородных логических функций двух переменных могут служить операции сложения и умножения одноразрядных m -значных чисел по модулю т (2. 8. 7), внутренние операции поля Галуа (2. 8. 9) с четырехзначным алфавитом {0, 1, А, В } и т. п.

Табличное задание функций. Как и бинарный закон композиции (2. 7. 2), однородная функция двух переменных может быть задана таблицей соответствия (матрицей), строки и столбцы которой соответствуют буквам алфавита. Таким способом представлялись функции одной и двух переменных в (1. 5. 2),(1. 5. 8) и (1. 5. 10). Для представления функций трех и большего числа переменных потребовались бы трехмерные и, вообще, n -мерные таблицы. Этого можно избежать, если столбцы матрицы поставить в соответствие не буквам алфавита, а словам, т. е. образовать kⁿ столбцов. Для каждой функции отводится строка, клетки которой заполняются буквами из данного алфавита. Матрица всех функций п переменных в k -значном алфавите содержит строк и называется общей таблицей соответствия. Например, для k = 3 и п = 2 такая матрица имеет вид:

Номера столбцов определяются расположенными над ними n -разрядными числами с основанием k, каждое из которых читается сверху вниз. Номера функций отождествляются с kⁿ -разрядными числами, которые соответствуют строкам матрицы в той же системе счисления.

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

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

Число всевозможных булевых функций п переменных v = 2 ⁿ быстро возрастает с увеличением п (при п = 3 оно равно 256, а при п = 5 превышает 4 миллиарда). Но функции одной и двух переменных еще можно перечислить и подробно исследовать, так как их количество сравнительно невелико (v = 4 при п = 1 и v = 16 при п = 2).

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

x			y
y0
y1			x
y2
y3

Две функции у₀ = 0 и у₃ = 1 представляют собой функции-константы (тождественный нуль и тождественная единица), таккакони не изменяют своих значений при изменении аргумента. Функция y₁ = х повторяет значения переменной х и потому просто совпадает с ней.

Единственной нетривиальной функцией является у₂ = , называемая отрицанием или инверсией ( читается «не х»). Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.