Булевы функции

Введение
Литературный и разговорный языки, которые используют люди для своего общения, не являются строгими и однозначными. Поэтому естественно, что при использовании таких языков возникают затруднения в процессе рассуждений и при получении выводов из этих рассуждений.
Считается, что именно эти причины послужили толчком для развития логики как науки о законах и формах мышления. Развитие логики связывают, прежде всего, с именем Аристотеля, который жил в IV веке до нашей эры. Его сочинение “Аналитики” долгое время рассматривали как труд, завершающий развитие этой науки.
В настоящее время математическая логика широко используется в различных областях человеческой деятельности: математике, юриспруденции, экономике, информатике и т. п.
Основным объектом изучения в математической логике являются различные исчисления, например, исчисление высказываний, исчисление предикатов. Основным предметом алгебры логики являются высказывания и логические операции над ними.
Высказыванием (суждением) называется всякое повествовательное предложение, о котором можно сказать истинно оно или ложно. Иногда для понятия “высказывание” используют также термин “пропозиция”.
Не всякое повествовательное предложение является высказыванием. Например, предложения “Волга впадает в Каспийское море”, “2+2=5” и “Снег черный” являются высказываниями. Первое из них истинно, а последние два – ложные. Предложения “Который час?”, “Я лгу” не являются высказыванями, так как в данном случае мы не можем говорить об истинности или ложности предложения.
В исчислении высказываний не рассматривают внутреннюю структуру и содержание высказываний, а ограничиваются рассмотрением их свойств представлять истину или ложь. Поэтому на высказывание можно смотреть как на величину, которая может принимать только одно из двух значений: “истина” или “ложь”.
Таким образом, истинность или ложность высказывания рассматривают как его значение. Эти значения сокращенно обозначают “И” и “Л” соответственно для значений “истина” и “ложь”. Используется также обозначения 1 и 0 для значений “истина” и “ложь”.
Если суждение об истинности высказывания можно вынести из самого высказывания, то такое высказывание называют простым. В противном случае мы имеем сложное высказывание.
Из простых высказываний можно образовывать сложные высказывания с помощью логических связок. Примерами таких логических связок являются союзы И, ИЛИ, НЕ, конструкция ЕСЛИ…, ТО ….
Простые высказывания обычно обозначаются некоторыми буквами латинского алфавита – большими или маленькими, с индексами или без них.
Логические связки часто имеют свои общепринятые обозначения. Так, союз И, который называют также конъюнкцией, обозначают символом & или ∧, союз ИЛИ, который называют также дизъюнкцией, обозначают символом ∨, а союз НЕ, который называют также отрицанием – символом ⌐ перед высказыванием, или чертой над соответствующим высказыванием, связка ЕСЛИ…, ТО…, которую называют импликацией, – символом →. Например, A&B (или A∧B), A∨B, ⌐A (или Ā), A→B.
Значение сложного высказывания, которое оно принимает в зависимости от значений составляющих ее простых высказываний, задается таблицей истинности. Эта таблица содержит все комбинации значений истинности простых высказываний и для каждой такой комбинации указывается значение истинности сложного высказывания.
Приведем таблицы истинности для сложных высказываний, образованных с помощью некоторых наиболее часто используемых логических связок.

Таблица 1: Таблица истинности для отрицания
A A
И Л
Л И

Мы видим, что отрицание НЕ образует из высказывания A новое высказывание Ā, которое истинно, если A ложно, и обратно.
Таблица 2: Таблица истинности для конъюнкции
A B A∧B
Л Л Л
Л И Л
И Л Л
И И И

Конъюнкция образует новое высказывание, которое истинно тогда и только тогда, когда оба составляющих его высказываний истинны. В противном случае новое высказывание является ложным.
Таблица 3: Таблица истинности для дизъюнкции
A B A∨B
Л Л Л
Л И И
И Л И
И И И

Мы видим, что новое высказывание, образованное дизъюнкцией, является истинным, если истинно хотя бы одно из составляющих его высказываний.
Таблица 4: Таблица истинности для импликации
A B A→B
Л Л И
Л И И
И Л Л
И И И
Импликацию A→B читают также: из A следует B. Импликация образует новое высказывание, которое ложно тогда и только тогда, когда A истинно, а B ложно. Иногда говорят, что импликация утверждает, что из лжи может следовать что угодно (истина или ложь), а из истины только истина. Из ложной предпосылки не может следовать истина.
Элементарные булевы функции
Во многих приложениях значения высказываний И или Л интерпретируются как численные значения 1 или 0 соответственно. В этом случае простые высказывания можно рассматривать как некоторые переменные, которые принимают свои значения из множества E={0;1}. Такие переменные называют булевыми переменными в честь английского математика Джорджа Буля.
Тогда сложные высказывания можно рассматривать как функции, определенные на множестве всевозможных значений n булевых переменных и принимающих значения из множества E. Такие функции называют булевыми функциями. Другими словами, всякая булева функция рассматривается как отображение f:
En→E.
Каждый элемент множества En называют набором значений n булевых переменных, или просто набором. Очевидно, существует 2n различных наборов n булевых переменных. На каждом наборе булева функция f может принимать два значения: 0 или 1. Поэтому существует 22n различных булевых функций n переменных

. Набор значений переменных, на котором булева функция f принимает значение, равное 1, называют единичным набором.
Булевы функции нуля, одной и двух переменных называют элементарными. XE "элементарные булевы функции" Функции нуля переменных - это константы 0 и 1.
Имеется 4 булевых функции одной переменной. Это две константы 0 и 1, одна тождественная функция f(x)=x и отрицание fx=x. В первых двух случаях функция независимо от значения переменной x принимает постоянное значение 0 или 1. Тождественная функция повторяет значение переменной, а функция отрицания принимает значения, противоположные значению переменной x.
Имеется 16 булевых функций от двух переменных. Любая булева функция может быть задана таблицей, в которой перечисляются всевозможные значения переменных и для каждого набора значений переменных указывается соответствующее ему значение булевой функции. Таким образом, это есть аналог таблицы истинности для высказываний, только вместо значений И и Л используются значения 1 и 0 соответственно. Такая таблица также называется таблицей истинности булевой функции.
Важное значение имеет также операция неравнозначности, или сложения по модулю 2. Обозначение: x⊕y.
Таблица 5: Таблица истинности для сложения по модулю 2.
A B A⊕B
0 0 0
0 1 1
1 0 1
1 1 0
Две булевы функции f, f1 называются равными, если их таблицы истинности одинаковы. Этот факт записывают так: f=f1.
Основные свойства элементарных булевых функций
Сложные булевы функции можно преобразовывать, используя свойства элементарных функций. Приведем без доказательства основные из этих свойств. В их справедливости легко убедиться, если отдельно построить таблицу истинности для левой и правой частей приведенных ниже соотношений.
1.x ∨ y = y ∨ x – коммутативность дизъюнкции;
2.x∧y = y∧y – коммутативность конъюнкции;
3.x∧(y ∨ z) = (x∧y)∨(x∧z) – дистрибутивность конъюнкции относительно дизъюнкции;
4.x∨(y∧z) = (x∨y)∧(x∨z) – дистрибутивность дизъюнкции относительно конъюнкции;
5.(x∧y)∧z = x∧(y∧z) – ассоциативность конъюнкции;
6.(x∨y)∨z = x∨(y∨z) – ассоциативность дизъюнкции;
7.x∧x = x – идемпотентность конъюнкции;
8.x∨x = x – идемпотентность дизъюнкции;
9.x⋁x=1 – тавтология, или закон исключения третьего;
10.x∧̄x = 0 – непротиворечивость;
11.(x∧y)∨y=y – поглощение конъюнкции;
12.(x∨y)∧y=y – поглощение дизъюнкции;
13.̄̄x = x – закон двойного отрицания.
Коммутативность конъюнкции и дизъюнкции показывает, что безразличен порядок записи переменных в конъюнкции и дизъюнкции (аналог в обычной алгебре – произведение и сумма не зависит от порядка записи сомножителей и слагаемых).
Дистрибутивность определяет правила раскрытия скобок. В обычной алгебре мы имеем дистрибутивность (распространимость) умножения относительно сложения.
Ассоциативность показывает, что безразлично в каком порядке выполняются множественные операции конъюнкции и дизъюнкции.
Законы поглощения позволяют упрощать булевы функции.
Законы де-Моргана
x⋁y=x⋀y,
x⋀y=x⋁y.
Законы де-Моргана устанавливают связь между дизъюнкцией и конъюнкцией.
Операции с константами
1.0∨x=x
2.1∨x=1
3.0∧x=0
4.1∧x=x
5.1=0
6.0=1
Классы булевых функций
Ранее мы определили, что общее число булевых функций равно 22т. Обозначим множество всех булевых функций через P2.
Из множества этих функций выделяют некоторые классы (подмножества) функций, играющие важную роль в теории булевых функций.
Пусть имеется булева функция f(x1,x2,…,xn), зависящая от n переменных. Пусть, далее, переменным этой функции присвоены значения: x1=σ1, x2=σ2, …, xn=σn, где σj ∈{0;1}, (j=1,2,…,n). Тогда f(σ1,σ2,…,σn) есть значение функции f при заданных значениях аргументов.
Говорят, что булева функция f сохраняет константу 0, если
f(0,0,…,0)=0.
Множество всех булевых функций, сохраняющих константу 0, образуют класс T0⊆P2.
Говорят, что булева функция f сохраняет константу 1, если
f(1,1,…,1)=1.
Множество всех булевых функций, сохраняющих константу 1, образуют класс T1⊆P2.
Функция gx1,x2,…,xn=f(x1,x2,…,xn) называется двойственной функцией к функции f и обозначается f*.
Например, имеем по определению
(x⋀y)*=x⋀y=x⋁y.
Таким образом, функция x⋁y является двойственной к функции x⋀y.
Рассмотрим, что происходит с таблицей истинности двойственной функции.
Замена набора x1,x2,…,xn на набор x1,x2,…,xn соответствует ``переворачиванию'' таблицы, т.е записью наборов в обратном порядке. Или, что тоже самое, ``переворачиванию'' значений функции при сохранении порядка записи наборов. Действительно, наборы x1,x2,…,xn и x1,x2,…,xn расположены симметрично относительно середины таблицы. Теперь остаётся применить операцию отрицания к значению функции, т.е. поменять 0 на 1 и 1 на 0. В результате мы получим таблицу истинности двойственной булевой функции.
Рассмотрим эту операцию для вышеуказанного примера.
x y x⋀y
x⋀y
x⋀y=x⋁y
0 0 0 1 0
0 1 0 0 1
1 0 0 0 1
1 1 1 0 1
Булева функция f называется самодвойственной, если она совпадает с двойственной себе функцией, т.е. имеет место равенство: f=f*. Класс самодвойственных функций обозначим через S⊆P2.
Например, функции f=x и xy⋁xz⋁yz являются самодвойственными.
Булева функция f называется линейной, если она может быть записана в следующем виде:
fx1,x2,…,xn=c0⊕c1x1⊕c2x2⊕∙∙∙⊕cnxn,
где ci∈0;1, ( i=0,1,…,n).
Множество всех линейных булевых функций обозначают через L.
Будем говорить, что набор значений переменных (σ1,σ2,…,σn) не меньше набора (σ1',σ2',…,σn'), если σj≥σj' для всех j=1,2,…, n.
В этом случае мы записываем:
σ1,σ2,…,σn≥σ1',σ2',…,σn'.
В противном случае наборы называются несравнимыми.
Булева функция называется монотонной, если для любых двух наборов таких, что
σ1,σ2,…,σn≥σ1',σ2',…,σn'.
имеет место неравенство
fσ1,σ2,…,σn≥fσ1',σ2',…,σn'.
Множество всех монотонных булевых функций обозначим через M ⊆ P2.
Функционально полные системы
Нетрудно убедиться, построив соответствующие таблицы истинности, что одни булевы функции можно выразить через другие