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

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

Пусть А и В – два множества и <a,b> – упорядоченная пара, где первый элемент , а второй элемент . Декартово произведение – это множество пар таких что . Бинарным отношением f из множества А в множество В называется подмножество : .

Функция – это такое отношение, что из и следует, что x=z, то есть функциональность – это однозначность.

Пример.

А={1,2,3,4,5}

B={1,4,9,16,25}

={<1,1>, <1,4>, <1,9>, <1,16>, <1,25>, <2,1>, <2,4>, <2,9>, <2,16>, <2,25>,….<3,9>, …. ,<4,16>,…..<5,25>}

f={<1,1>, <2,4>, <3,9>, <4,16>, <5,25>} – это функция, где b=a².

Теперь перейдем к определению булевых функций.

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

Если область значений функций содержит k различных элементов, то она называется k-значной функцией.

Определение 1.5.Логическая функция – это функция, в которой переменные принимают только два значения: логическая единица или логический ноль.

Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a, b).

Логические функции могут зависеть от одной, двух и любого числа переменных (аргументов) х₁, …, х_n.

В теоретико-множественном смысле логические функции n переменных y=f(x₁, …, x_n) представляет собой отображение множества наборов (n-мерных векторов, кортежей последовательностей) вида (х₁, х₂, …, х_n) являющегося областью ее определения, на множество ее значений.

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

Определение 1.6. Всякая логическая переменная и символы«истина» (1) и «ложь» (0) –формулы.Если Аи В–формулы,то , А В, А В, А B, А В –формулы.

Функция называется функцией алгебры логики.

y=f(x₁,x₂) – бинарная функция,

y=f(x₁,x₂,…., x_n) – n- арная функция.

Пример.

Логическую функцию можно также рассматривать как операцию, заданную законом композиции

Х₁ Х₂ … Х_n N, где Х₁, …, Х_n – множества, на которых определены аргументы

х₁ Х₁ , х₂ Х₂ , …, х_n Х_n .

Если Х₁= Х₂=…= Х_n=N, и однородная функция, рассматриваемая как закон композиции

Nⁿ N, определяет n-местную операцию на конечном множестве N.

Наиболее простым и важнейшим классом однородных функций являются двузначные (булевы) функции (иногда ее называют переключательной). Функция f(x₁, x₂, …, x_n-1, x_n) принимает два значения 0,1 и зависит от переменных x_i {0,1}, i= .

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

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

Таким образом, каждое элементарное высказывание может принимать значение либо 0, либо 1. Каждому набору значений соответствует одно значение всего сложного высказывания (0 или 1).

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

Каждому набору α=(α₁, …,α_n) α_i {0,1} становится в соответствии число

N=α₁2^n-1+…+ α_n-12+ α_n.

Наборам (0, 0, …, 0, 0), (0, 0, …, 0, 1), …, (1, 1, …, 1, 1) соответствуют числа 0,1, …, 2^n-1.

Легко видеть, что число n-мерных наборов из 0 и 1 равно 2ⁿ.

Если зафиксировать n переменных x₁, x₂, …, x_n, то разные функции от переменных x₁, x₂, …, x_n задаются разными таблицами. Число различных таблиц равно числу всех функций от переменных x₁, x₂, …, x_n. Число булевых функций от n переменных x₁, x₂, …, x_n равно .

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

Итак, пусть – множество булевых функций. Формулой над F называется выражение либо переменная, либо формула над F. F называется базисом формулы, f – главной (внешней) операцией, t_i – подформулами.

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

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

Примеры.

1.

x1	x2	x1 x2

Функция реализует дизъюнкцию на базисе .

2.

x1	x2	x1~ x2

Функция реализует дизъюнкцию на базисе .

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

Функции алгебры логики и их основные свойства.

Рассмотрим множество векторов ={x₁, x₂, …, x_n}, пусть координаты этих векторов принимают значения 0 или 1. Таким образом, множество Х состоит из 2ⁿ различных векторов.

Совокупность координат некоторого фиксированного вектора из множества будем называть двоичным набором или просто набором.

Сопоставим каждому вектору Х число 0 или 1, т.е. произведем однозначное отображение Х на множество Y={0,1}.

Определение 1.7. Функцией алгебры логики (ФАЛ) называется функция, дающая однозначное отображение Х в Y.

1. Число различных ФАЛ, зависящих от n аргументов, конечно и равно .

x1, x2, …, xn-1, xn	f (x1, x2, …, xn-1, xn)
0 0 … 0 0	α1
0 0 … 0 1	α2
… … … … …	… … …… … … …
1 1 … 1 0
1 1 … 1 1

Если наборам значений аргументов ФАЛ сопоставляет точки n- мерного пространства, то множество наборов определяет множество вершин n- мерного единичного куба. Таким образом, областью определения ФАЛ, зависящей от n аргументов, является множество вершин такого куба.

Пример.

ФАЛ f(x₁, x_2, x₃) может быть задана геометрически. f(101, 110, 010, 011)=1. Значения ФАЛ могут быть заданы не на всех возможных наборах аргументов. На некоторых значения функции могут быть не определены. Такие функции называют не полностью определенными.

2. Если две ФАЛ f₁(x₁, x₂, …, x_n-1, x_n) и f₂(x₁, x₂, …, x_n-1, x_n) принимают на всех возможных наборах значений аргументов одинаковые значения, то функции f₁ и f₂ называются равными.

3. ФАЛ f(x₁, x₂, …, x_i, x_i+1, …, x_n-1, x_n) существенно зависит от аргумента x_i, если имеет место соотношение

f(x₁, x₂, …, x_i-1,0 , x_i+1, …, x_n-1, x_n)¹ f(x₁, x₂, …, x_i-1,1 , x_i+1, …, x_n-1, x_n)

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

Как найти несущественные аргументы? Для этого, если ФАЛ задана таблично, поступают следующим образом.

Разбивают множество наборов аргументов функции на два подмножества:

- подмножество, на котором заданная функция принимает значение 1;

- подмножество, на котором заданная функция принимает 0.

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

Пример:

Таблица

Произведем разбиение набора аргументов:

x₁ x₂ x₃ x₄

0 0 0 0

0 0 0 1 x₁ x₂ x₃ x₄

0 0 1 0 0 1 0 0

0 0 1 1 наборы х 0 1 0 1

0 1 1 0 на которых 1 1 0 0 f( )=1

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

1 0 0 0 1 1 1 0

1 0 0 1 1 1 1 1

1 0 1 1

Вычеркнем в наборах четвертый столбец. Оставшиеся наборы таковы, что ни один из них не входит одновременно в оба подмножества. Это свидетельствует о фиктивности аргумента x₄.

Элементарные функции алгебры логики

Рассмотрим множество элементарных ФАЛ. Начнем со случая, когда длина слова n=0. По формуле, определяющей число функций логики, вычисляем, что при n=0

f₁=0; f₂=1.

Эти две функции совпадают с константами.

В случае n=1 мы имеем две функции, существенно зависящие от аргумента x, эти две функции определяются таблицей

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

f ₃=x ; f ₄= (читается «не x»).

Функцию f ₄ называют функцией отрицания.

В случае n=2 имеем десять различных функций, существенно зависящих от аргументов x₁ и x₂.

		x1Úx2	x1&x2	x1~x2	x1®x2	x1 ¯ x2	x1/x2	x1 x2
x 1	x 2	f 5	f 6	f 7	f 8	f 9	f 10	f 11

Функция f₅(x_1,x₂) =x₁Úx₂ (дизъюнкция).

Функция f₆(x_1,x₂) =x₁&x₂ (конъюнкция).

Вместо символов & часто применяют символ умножения «•» или вообще опускают также, как и в обычной алгебре.

Функция f₇ носит название функции эквивалентности или функции равнозначности

f₇(x_1,x₂) = x1~x2

и f₇(x_1,x₂) = x₁ºx₂.

Функция f₈ носит название импликации x₁ в x₂. Она обозначается f₈(x_1,x₂) = x₁®x₂.

Функция f₉ носит название функции Вебба (или ее называют еще стрелкой Пирса) и обозначается

f ₉(x_1,x₂) = x₁vx₂.

Функция f₉ называется функцией (штрихом) Шеффера и обозначается следующим образом f ₁₀(x_1,x₂) = x₁ ¯ x₂.

Функция f ₁₁ обычно называется функцией сложения по модулю 2.

f ₁₁(x_1,x₂) = x₁ x₂.

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

1. путем перенумерации аргументов;

2. путем подстановки в функцию новых функций вместо аргументов.

Функцию, полученную из функций f ₁, f ₂, f ₃, …, f _k путем применения этих правил будем называть суперпозицией функции f ₁, f ₂, f ₃, …, f _k .

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

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

Пример. Пусть требуется представить в виде таблицы следующую функцию

f (x₁,x₂,x₃)={[( ~x₂)Ú (x₁ ¯ x₂)] (x₁ x₂)}®x₃.

Будем строить ФАЛ последовательно.

x1	x2	x3		~x2	x1¯x2	[ ]	x1 x2	{ }	f (x1,x2,x3)

Выражение одних элементарных функций через другие

1. Функция f ₈(x_1,x₂) = x₁®x₂ (импликация x₁ в x₂) может быть записана посредством функций дизъюнкции и отрицания

x₁®x₂= Úx ₂.

Доказательство осуществляется посредством таблиц истинности.

2. Функцию эквивалентности f₇(x_1,x₂)=x₁~x₂ = x₁ºx₂ выразим посредством других функций x₁~x₂= ( Úx₂)&(x ₁Ú )

3. f ₁₁(x_1,x₂) = x₁ x₂= или f (x_1,x₂) = x₁ x₂=( & x₂) (x₁& )

4. =x

5. x₁& x₂=

6. x₁ x₂=

7. x₁ x₂=

Свойства конъюнкции, дизъюнкции и отрицания

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

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

x₁&(x₂&x₃)= (x₁&x₂)&x₃,

x₁ (x₂ x₃)= (x₁ x₂) x₃,

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

x₁ x₂= x₁ x₂,

x₁& x₂= x₁&x₂,

и дистрибутивности. Кроме того, выполняется закон дистрибутивности дизъюнкции относительно конъюнкции.

x₁ (x₂&x₃)= (x₁ x₂)& (x₁ x₃).

Рассмотрим теперь ряд простых, но весьма важных соотношений

х х=х;

х&х=х.

х 1=1; х 0=х; х =1;

х&1=х. х&0=0. х& =0.

И как следствие получаем

х х … х=х,

х&х&…&х=х.

Как обобщение формул получаем следующие формулы, называемые формулами (законами) де Моргана

х₁ х₂ … х_n= ;

х₁&х₂&…&х_n= .

Свойства функций сложения по модулю 2, импликации, штриха Шеффера и стрелки Пирса (функции Вебба)

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

Для функции сложения по модулю 2 выполняются переместительный и сочетательный законы, а также распределительный закон относительно конъюнкции:

x₁ x₂= x₂ x₁;

x₁ (x₂ x₃)= (x₁ x₂) x₃;

x₁&(x₂ x₃)= (x₁&x₂) ( x₁&x₃).

Справедливы также очевидные соотношения

x x=0;

x 0=х;

x 1= ;

х =1.

Кроме того, выполняется формула х₁ х₂= x₁ x₂ x₁&x₂.

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

х®x=1;

x® = ;

x®1=1;

х®0= ;

0®х=1;

1®х=х;

х₁®х₂= ® ;

х₁®х₂® х₁= х₁.

Функции дизъюнкции и конъюнкции могут быть выражены через импликацию следующим образом:

х₁ х₂= ® х₂;

х₁&х₂= .

Для функции Шеффера и Вебба справедлив переместительный закон:

х₁ /х₂= х₂/х₁;

х₁¯х₂= х₂¯х₁.

Сочетательный закон для них не выполняется:

х₁/(х₂/х₃)¹(х₁/х₂)/х₃ ;

х₁¯( х₂¯х₃)¹ (х₁¯ х₂)¯ х₃.

Справедливы следующие очевидные соотношения, проверка которых аналогична приведенным выше примерам и осуществляется при помощи таблиц истинности:

х /х= , х¯ х= ;

х/ =1, х¯ =0;

х/1= , х¯1 =0;

х/0=1, х¯0= ;

х₁/х₂= = ;

х₁¯х₂= = & .

Функции Шеффера и Вебба связаны между собой соотношениями, аналогичными формулами де Моргана для функций конъюнкции и дизъюнкции:

х₁/х₂= ;

х₁¯х₂= .