49769 (597461), страница 3
Текст из файла (страница 3)
Рис.2.4. Соответствие логических констант всегда замкнутому и всегда разомкнутому контактам.
Условимся, наконец, обозначать через Xi и Xi такую пару контактов, что когда контакт Xi замкнут, контакт Xi обязательно разомкнут, и наоборот. Техническое осуществление такой пары контактов показано на рис.2.5.
Рис.2.5. Реализация контактов Xi и Xi.
Ясно, что параллельное и последовательное соединение переключательных схем обладает свойствами коммутативности, ассоциативности, идемпотентности.
Несколько сложнее проверяется выполнимость двух законов дистрибутивности:
Приведены попарно эквивалентные переключательные схемы, подтверждающие справедливость указанных законов дистрибутивности для переключательных схем.
Таким образом, все законы логики высказываний имеют аналоги в логике переключательных схем. Это, во-первых, позволяет моделировать сложные высказывания с помощью электрических цепей. Во-вторых, конструировать (синтезировать) переключательные схемы, удовлетворяющие наперед заданным условиям (которые могут быть и достаточно сложными).
Булевские функции
Многим из читателей, мы полагаем, приходилось иметь дело с так называемыми числовыми функциями: алгебраическими, тригонометрическими, логарифмическими и т.д. Все они характеризовались тем, что область определения и область значений функций представляли собой подмножества множества действительных чисел.
Например, функция y = f(x), задаваемая формулой y = sin(x) + 1, имеет в качестве области определения (обычно обозначается буквой Х) все множество действительных чисел, а в качестве области значений (чаще обозначаемой буквой Y) множество неотрицательных чисел, принадлежащих интервалу [0, 2]; функция y = (x) , задаваемая формулой (x)=|lgx|+5, в качестве области определения имеет множество всех положительных действительных чисел, а в качестве области значений - множество положительных действительных чисел, больших 5.
Рассматриваемые нами здесь булевские (логические) функции характеризуются тем, что аргументы и сама функция принимают значения из множества логических констант {И, Л}.
В теории булевских функций чаще используются "числовые" эквиваленты логических констант: 1 вместо И, 0 - вместо Л. Ниже мы будем придерживаться именно этих обозначений.
Булевская функция в общем случае может содержать n аргументов: y=f(x1,x2,…,xn).
Как и математические функции, булевские функции могут задаваться: словесно, таблично или аналитически. Мы будем использовать последние два способа задания булевских функций: табличный (в виде таблиц истинности) и аналитический (в виде формул логики высказываний). Одна и та же функция может, естественно, задаваться по-разному.
Булевские функции одной переменной
Булевских функций от одной переменной всего 4. Эти функции и задающие их формулы логики высказываний приведены в следующей таблице:
| x | 0 | 1 | Формулы логики высказываний, задающие функции |
| φ1 | 0 | 0 | φ1(x) = 0 (константа 0) |
| φ2 | 0 | 1 | φ2(x) = x (совпадает с переменной х) |
| φ3 | 1 | 0 | φ3(x) = x (является отрицанием переменной х) |
| φ4 | 1 | 1 | φ4(x) = 1 (константа 1) |
Булевских функций от двух переменных всего насчитывается 16. Все они представлены в следующей таблице:
| x | 0 | 0 | 1 | 1 | Формулы логики высказываний, задающие функции |
| y | 0 | 1 | 0 | 1 | |
| f1 | 0 | 0 | 0 | 0 | f1(x,y) = 0 (константа 0) |
| f2 | 0 | 0 | 0 | 1 | f2(x,y) = x&y (конъюнкция) |
| f3 | 0 | 0 | 1 | 0 | f3(x,y) = (xy) (отрицание импликации) |
| f4 | 0 | 0 | 1 | 1 | f4(x,y) = x (совпадает с переменной x) |
| f5 | 0 | 1 | 0 | 0 | f5(x,y) = (yx) (отрицание обратной импликации) |
| f6 | 0 | 1 | 0 | 1 | f6(x,y) = y (совпадает с переменной y) |
| f7 | 0 | 1 | 1 | 0 | f7(x,y) = xy (строгая дизъюнкция) |
| f8 | 0 | 1 | 1 | 1 | f8(x,y) = xy (дизъюнкция) |
| f9 | 1 | 0 | 0 | 0 | f9(x,y) = xy (конъюнкция отрицаний) |
| f10 | 1 | 0 | 0 | 1 | f10(x,y) = xy (эквиваленция) |
| f11 | 1 | 0 | 1 | 0 | f11(x,y) = y (отрицание y) |
| f12 | 1 | 0 | 1 | 1 | f12(x,y) = yx (обратная импликация) |
| f13 | 1 | 1 | 0 | 0 | f13(x,y) = x (отрицание x) |
| f14 | 1 | 1 | 0 | 1 | f14(x,y) = xy (импликация) |
| f15 | 1 | 1 | 1 | 0 | f15(x,y) = (xy) (отрицание конъюнкции) |
| f16 | 1 | 1 | 1 | 1 | f16(x,y) = 1 (константа 1) |
Естественно, многие из перечисленных функций могут быть заданы другими, но равносильными формулами логики высказываний.
Булевские функции n переменных
Областью определения такой булевской функции будет n-тая декартова степень множества {0,1}, то есть всевозможные двоичные наборы длины n вида <12…n>, где i{0,1}. Число таких всевозможных наборов (n-ок) составляет 2n.
Область значений булевской функции от n переменных - это множество {0,1}.
В дальнейшем мы будем рассматривать только всюду определенные булевские функции, то есть область определения таких функций совпадает с n-той декартовой степенью множества {0,1}.
Булевские функции от большего числа переменных могут быть так же заданы таблично, или с помощью формул логики высказываний, или в виде суперпозиции (взаимной подстановки) булевских функций одной и/или двух переменных.
Например, булевская функция y=f(x,y,z), задаваемая формулой логики высказываний x&y x&y z может быть задана в виде следующей суперпозиции функций от одной и двух переменных: y=f8(f8(f2(x,y),f9(x,y)),φ2(z)).
Учитывая принципиальную возможность выразить булевскую функцию от любого числа переменных в виде суперпозиции (взаимной подстановки) булевских функций от одной и двух переменных, мы чаще будем использовать либо табличный способ задания таких функций, либо с помощью формул логики высказываний.
Табличный способ задания булевских функций от одной и двух переменных (см. приведенные выше таблицы, определяющие эти функции) наводит нас на некоторые соображения:
-
число наборов истинностных значений, на которых определена булевская функция от n переменных, составляет 2n (при n=1 это число составляет 2, при n=2 - 4);
-
значение каждой булевской функции от n переменных представляет собой двоичный набор длины 2n;
-
каждая булевская функция отличается от любой другой булевской функции с тем же числом переменных своим значением хотя бы на одном из таких наборов
А отсюда можно сделать предположение о том, число N различных булевских функций от n переменных равно числу различных двоичных наборов длины 2n, то есть: 
При n=1 это число равно 4, при n=2 - 16, n=3 - 256, n=4 - 65536 и т.д.
Полные системы булевских функций
В предыдущем пункте было отмечено, что можно выразить любую булевскую функцию от n переменных в виде суперпозиции (взаимной подстановки) булевских функций от одной и двух переменных. В свою очередь эти функции задаются формулами, содержащими логические операции: отрицание(), конъюнкцию (&),строгую дизъюнкцию (), дизъюнкцию(), импликацию(), эквиваленцию ().
Но как известно из логики высказываний, операции логики высказываний строгая дизъюнкция (), импликация (), эквиваленция () могут быть выражены через дизъюнкцию (), конъюнкцию (&) и отрицание ().
В свою очередь, дизъюнкция () может быть выражена через конъюнкцию (&) и отрицание (), а конъюнкция (&) - через дизъюнкцию () и отрицание ().
Таким образом, конъюнкция и отрицание, а также дизъюнкция и отрицание, образуют полную систему логических связок, то есть через эти операции могут быть выражены все остальные.
Более того, можно определить логическую операцию, через которую выражаются все шесть операций: отрицание (), конъюнкция (&), дизъюнкция (), строгая дизъюнкция (), импликация (), эквиваленция (). Таковой, например, является операция, соответствующая сложному союзу "не А или не В" ("или" соединительное). Эта операция обозначается символом (например, АВ) и получила название штрих Шеффера. Штрих Шеффера определяется с помощью следующей таблицы:
| X | Y | XY |
| Л | Л | И |
| Л | И | И |
| И | Л | И |
| И | И | Л |
Как легко видеть, штрих Шеффера представляет собой отрицание конъюнкции: XY XY (X&Y).
Можно убедиться, что X XX.
А отсюда: X&Y ( XY) (XY) ( XY).
Таким образом, через штрих Шеффера могут быть выражены конъюнкция и отрицание, а значит и все остальные операции логики высказываний. То есть система логических связок, содержащая единственную операцию - штрих Шеффера, является полной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
