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

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

Любая логическая функция n переменных может быть задана таблицей, в левой части которой перечислены 2 наборов значений переменных; в правой части- значения функции на этих наборах. Наборы переменных располагаются в лекси-кографическом порядке, который совпадает с порядком возрастания наборов, рас-сматриваемых как двоичные числа.

Число различных функций n переменных, обозначается Р₂(n). Оно равно Р₂(n)= – числу различных двоичных векторов длины 2 . Рассмотрим табличное за-дание функции одной переменной ( n=1 ). В этом случае различных наборов пере-менной - 2, 0 и 1. Число различных функций равно Р₂(1) = 2² = 4, а различные векторы длины 2 имеют вид (0,0), (0,1), (1,0), (1,1).

Все эти функции представлены в табл. 1.1.

Таблица 1.1

Эти функции называются и обозначаются следующим образом:

f₀(x) = 0 - константа ноль, f₁(x) = x – тождественная функция,

f₂(x) = –отрицание x (читается “ не х“), f₃(x) = 1 – константа единица.

Рассмотрим функции двух переменных ( n=2 ). В этом случае разных наборов переменных будет 2² = 4, а разных функций Р₂(2) = 2⁴ = 16. Вcе эти функции представлены в табл.1.2 в порядке, соответствующем возрастанию чисел от 0 до 15, записанных в двоичной системе счисления. Номера функций соответствуют этим числам.

Таблица 1.2

Некоторые из этих функций имеют специальные названия и обозначения:

f₀( х₁, х₂ ) = 0 – константа 0.

f₁( х₁, х₂ ) = х₁ & х₂ – конъюнкция х₁ и х₂ (читается х₁ и х₂). Эту функцию часто назы-вают логическим умножением и обозначают х₁∙ х₂ или х₁ х₂ или х₁ х₂.

f₆( х₁, х₂ ) = х₁ х₂ – сложение по mod 2.

f₇( х₁, х₂ ) = х₁ х₂ –дизъюнкция х₁ и х₂ ( читается х₁ или х₂ ). Эту функцию часто называют логическим сложением и обозначают х₁ + х₂.

f₈ ( х₁, х₂ ) = х₁ ↓ х₂ – стрелка Пирса ( или функция Даггера или антидизъюнкция).

f₉ ( х₁, х₂ ) = х₁ ~ х₂ – эквивалентная функция. Иногда ее обозначают так: x x .

f₁₃ ( х₁, х₂ ) = х₁ → х₂ – импликация х₁ и х₂ ( читается из х₁ следует х₂ ). Эту функцию часто называют логическим следованием и обозначают х₁ х₂.

f₁₄ ( x₁, х₂ ) = х₁ / х₂ – функция Шеффера (или штрих Шеффера или антиконъюнкция).

f₁₅ ( х₁, х₂ ) = 1 – константа 1.

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

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

Обозначается алгебра обычно парой: ( Μ, Ω ), где Μ – множество элементов алгебры, а Ω – множество операций алгебры над её элементами (называется сигнатурой). Результаты операций всегда принадлежат Μ.

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

логические переменные и логические функции, а сигнатура – логические операции, т.е.

Ω = { −, , & , → , ↓ , ~ , / , }.

С помощью логических операций из одних функций можно получать другие функции. Например, из f₇( x₁,x₂ ) с помощью операции отрицания получим: (x ,x ). Из f₂ и f₃ с помощью операции конъюнкции получим: f = f₂ & f₃.

Определение. Эквивалентными ( равносильными ) функциями алгебры логи-ки называются функции, имеющие одинаковые таблицы задания функции. Будем обозначать эквивалетные функции так: f₁ ~ f₂.

Можно отметить, что операции дизъюнкцию и конъюнкцию можно записать так: х₁ & х₂ ~ min( х₁, х₂ ), х₁ х₂ ~ max ( х₁, х₂ ). Остальные функции табл. 1.2 названий не имеют и легко выражаются через перечисленные выше.

Например, f₁₁ ~ , f₂ ~ , f₄ ~ х₂ & f₆.

С помощью понятия несущественной переменной остальные функции табл. 1.2 можно выразить через переменные х₁ и х₂.

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

f ( х₁, … , х_{i -1}, 0, х_{i +1}, … ,x_n ) = f (x₁, …, x_i-1, 1, x_i+1, … , x_n ),

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

В этом случае функция по существу зависит от n-1 переменной, т.е. представляет собой функцию g( x₁, … , x_i-1, x_i+1, … , x_n ).

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

Если переменная не является несущественной, то она называется существенной.

Можно дать такое определение существенной переменной.

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

f( a , …, a , 0, a , …, a ) ≠ f( a , …, a , 1, a , …, a ),

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

Из данных определений следует, что в функциях f₀ и f₁₅ табл. 1.2 переменные х₁ и х₂ являются фиктивными, т.к. их изменение не приводит к изменению значений этих функций. Покажем, что в функциях f₃, f₅, f₁₀, f₁₂ табл. 1.2 одна из переменных является фиктивной.

Согласно табл. 1.2 функция f₃( х₁, х₂ ) задается табл. 1.3. Из этой таблицы видно, что

f₃( 0, 0 ) = f₃( 0, 1 ) = 0, f₃( 1, 0 ) = f₃( 1, 1 ) = 1,

т.е. изменение значения переменной х₂, при одинаковых значениях х₁, не приводит к изменению значения функции. Следовательно х₂ – фиктивная переменная, а значит функция f₃( x₁, x₂ ) является функцией только одной переменной х₁.

Исключая х₂ из табл.1.3, получим табл.1.4 – таблицу задания функции f₃. Из этой таблицы следует, что f₃( x_1, x₂ ) ~ x₁, т.е. функция эквивалентна переменной х₁.

Таблица 1.3

Таблица 1.4

Аналогичные рассуждения приводят к следующим соотношениям для остальных функции: f₅( x₁, x₂ ) ~ x₂, f₁₀( x₁, x₂ ) ~ , f₁₂( x₁, x₂ ) ~ .

Таким образом, из 16 функций табл. 1.2, 6 функций имеют фиктивные переменные. Можно показать, что с ростом числа переменных доля фиктивных переменных убывает и стремится к нулю.

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

Например, задание функции f₁( x₁,x₂ ) табл. 1.2 в векторном виде будет следующее: f₁ = ( 0, 0, 0, 1 ).

Векторное задание функции f( x₁, x₂, x₃ ) = ( 0, 0, 1, 1, 1, 1, 0, 0 ) соответствует табличному заданию функции в виде табл. 1.5.

Таблица 1.5

Определим фиктивные переменные для этой функции. Подвергнем “испытанию” на фиктивность переменную х₃. Для этого мы должны сравнить значения функции при одинаковых наборах х₁ и х₂. Запишем их:

f ( 0,0,0 ) = f( 0,0,1 ) = 0, f( 0,1,0 ) = f( 0,1,1 ) = 1,

f( 1,0,0 ) = f( 1,0,1 ) = 1, f( 1,1,0 ) = f( 1,1,1 ) = 0.

Из этих соотношений следует, что изменение значения переменной х₃ при одинаковых значениях х₁ и х₂ не приводит к изменению значения функции. Следовательно, х₃ является фиктивной переменной.

Исключая из табл. 1.5 переменную х₃ т.е. вычеркивая третий столбец и строки где х₃ = 1, получим табл.1.6, задающую функцию двух переменных g( x₁,x₂ ), эквивалентную функции f. В полученной функции переменные х₁ и х₂ являются существенными.

Таблица 1.6

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

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

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

логическая функция трёх переменных задана следующей таблицей:

Эта таблица является неполной, в ней отсутствуют следующие наборы переменных (0, 1, 1) и (1, 1, 1) и соответствующие им значения функций. Можно дополнить данную таблицу следующим образом f( 0, 1, 1 ) = 1 и f( 1, 1, 1 ) = 0.

.