Лекция 6. 2. Функции алгебры логики

ТЕМА: АЛГЕБРА БУЛЯ. БУЛЕВЫ ФУНКЦИИ. ПРИЛОЖЕНИЯ АЛГЕБРЫ ЛОГИКИ В ТЕХНИКЕ.

ПЛАН:

1. Алгебра Буля.

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

3. Представление произвольной функции в виде формулы алгебры логики.

4. Приложения алгебры логики в технике (релейно – контактные схемы).

Главная

1. Алгебра Буля.

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

Но в алгебре логики возможны и другие преобразова­ния, основанные на использовании равносильностей:

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

Рассмотрим непустое множество М элементов любой природы { х, у, г,... }, в котором определены отношение «=» (равно) и три операции: «+» (сложение), «×» (умно­жение) и «-» (отрицание), подчиняющиеся следующим аксиомам:

Коммутативные законы:

Такое множество М называется булевой алгеброй.

Если под основными элементами х, у, г,... подразу­мевать высказывания, под операциями «+», «×», «-» дизъюнкцию, конъюнкцию, отрицание соответственно, а знак равенства рассматривать как знак равносильнос­ти, то, как следует из равносильностей I, II и III групп, все аксиомы булевой алгебры выполняются.

В тех случаях, когда для некоторой системы аксиом удается подобрать конкретные объекты и конкретные соотношения между ними так, что все аксиомы выпол­няются, говорят, что найдена интерпретация (или мо­дель) данной системы аксиом.

Значит, алгебра логики является интерпретацией бу­левой алгебры. Алгебра Буля имеет и другие интерпрета­ции. Например, если под основными элементами х, у, г,... множества М подразумевать множества, под операци­ями «+», «×», «-» объединение, пересечение, дополнение соответственно, а под знаком равенства - знак равенства множеств, то мы приходим к алгебре множеств. Нетруд­но убедиться, что в алгебре множеств, все аксиомы алгеб­ры Буля выполняются.

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

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

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

Например, формула является функцией трех переменных f(x, у, z). Особенностью этой функции является то обстоятельство, что ее аргументы принима­ют одно из двух значений: ноль или единицу, и при этом функция также принимает одно из двух значений: ноль или единицу.

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

Тождественно истинные и тождественно ложные формулы алгебры логики представляют собой постоянные функции, а две равносильные формулы вы­ражают одну и ту же функцию.

Выясним, каково число функций n переменных. Оче­видно, каждую функцию алгебры логики (как и формулу алгебры логики) можно задать с помощью таблицы ис­тинности, которая будет содержать 2ⁿ строк. Следователь­но, каждая функция n переменных принимает 2ⁿ значе­ний, состоящих из нулей и единиц. Таким образом, фун­кция nпеременных полностью определяется набором зна­чений из нулей и единиц длины 2ⁿ.Общее же число на­боров, состоящих из нулей и единиц, длины 2ⁿ равно . Значит, число различных функций алгебры логики n переменных равно .

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

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

Из таблицы следует, что f₁(x) º 1, f₄(x) º 0, f₂(x) º x,

Таблица истинности для всевозможных функций двух переменных имеет вид:

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

3. Представление произвольной функции алгебры логики в виде формулы алгебры логики.

Пусть F(x₁, x₂, …, x_n) - произвольная функция алгеб­ры логики п переменных. Рассмотрим формулу

которая составлена следующим образом: каждое слагае­мое этой логической суммы представляет собой конъюн­кцию, в которой первый член является значением функ­ции F при некоторых определенных значениях перемен­ных x₁, x₂, …, x_n,остальные же члены конъюнкции пред­ставляют собой переменные или их отрицания. При этом под знаком отрицания находятся те и только те пере­менные, которые в первом члене конъюнкции имеют зна­чение 0.

Вместе с тем формулаэта содержит в виде логичес­ких слагаемых всевозможные конъюнкции указанного вида.

Данная формула полностью определяет функ­цию F(x₁, x₂, …, x_n). Иначе говоря, значения функции Fи формулы совпадают на всех наборах значений пере­менных x₁, x₂, …, x_n.

Например, если x ₁ принимает значение 0, а осталь­ные переменные принимают значение 1, то функция F принимает значение F(0,1,1,...1). При этом логическое

слагаемое входящее в форму­лу, принимает также значение F(0,1,...1), все ос­тальные логические слагаемые формулыимеют зна­чение 0. Действительно, в них знаки отрицания над переменными распределяются иначе, чем в рассмотрен­ном слагаемом, но тогда при замене переменных теми же значениями в конъюнкцию войдет символ 0 без знака от­рицания, символ 1 под знаком отрицания. В таком слу­чае один из членов конъюнкции имеет значение0, а по­этому вся конъюнкция имеет значение 0. В связи с этим на основании равносильности х v 0 º х значением фор­мулы является.F(0,l,...,l).

Ясно, что вид формулыможет быть значительно упрощен, если в ней отбросить те логические слагаемые, в которых первый член конъюнкции имеет значение0 (и, следовательно, вся конъюнкция имеет значение 0).Если же в логическом слагаемом первый член конъюнк­ции имеет значение1, то, пользуясь равносильностью 1& х º х, этот член конъюнкции можно не выписывать.

Таким образом, в результате получается формула,которая содержит только элементарные переменные выс­казывания и обладает следующими свойствами:

1) Каждое логическое слагаемое формулы содержит

все переменные, входящие в функцию F(x₁, x₂, …, x_n).

2) Все логические слагаемые формулы различны.

3) Ни одно логическое слагаемое формулы не содер­жит одновременно переменную и ее отрицание.

4) Ни одно логическое слагаемое формулы не содер­жит одну и ту же переменную дважды.

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

Если функция F(x₁, x₂, …, x_n) задана таблицей ис­тинности, то соответствующая ей формула алгебры ло­гики может быть получена следующим образом:

для каждого набора значений переменных, на котором фун­кция F(x₁, x₂, …, x_n) принимает значение1, запишем конъюнкцию элементарных переменных высказываний, взяв за член конъюнкции х_к,если значение х_к на ука­занном наборе значений переменных есть 1 и отрицание ,если значение х_к есть 0. Дизъюнкция всех записан­ных конъюнкций и будет искомой формулой.

Пусть, например, функция F(x₁, x₂, х₃) имеет следу­ющую таблицу истинности:

Для наборов значений переменных, на которых функция принимает значение 1составим дизъюнкцию соответствующих конъюнкций:

.