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

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

Например, формула является функцией трех переменных f (p, q, r). Особенность этой функции является то обстоятельство, что ее аргументы принимают одно из двух значений 0 и 1.

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

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

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

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

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

Таблица 15

p

Из таблицы видно, что а

Таблица истинности для всевозможных функций двух переменных имеет вид: где i = 1, 2, …, (табл. 16)

Таблица 16

p

q

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

~1, ,

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

Пусть F ( ) – произвольная функция алгебры логики n переменных. Рассмотрим формулу

. ( 1 ).

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

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

Ясно, что формула ( 1 ) полностью определяет функцию F( ). Иначе говоря, значения функции F и формулы ( 1 ) совпадают на всех наборах значений переменных .

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

При этом логическое слагаемое

F ( 0, 1, 1, …, 1 )

входящее в формулу ( 1 ), принимает также значение F( 0, 1, …, 1 ), все остальные логические слагаемые формулы ( 1 ) имеют значение 0.

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

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

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

1.Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F( ).

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

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

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

Перечисленные свойства называются свойствами совершенства.

Каждое не тождественно ложной функции соответствует единичная формула вида ( 1 ).

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

Пусть, например, функция F( ) имеет следующую таблицу истинности ( табл. 17 )

Таблица 17

			F( )				F( )

Для наборов значений переменных ( 1, 1, 0 ), ( 1, 0, 1 ),

( 0, 1, 0 ), ( 0, 0, 0 ), на некоторых функция принимает значение 1, запишем конъюнкции

а искомая формула, обладает свойствами совершенства, имеет вид

Пусть формула А содержит только операции конъюнкции, дизъюнкции и отрицания. Будем называть операцию конъюнкции двойственной операции дизъюнкции, а операцию дизъюнкции двойственной операции конъюнкции.

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

Например, для формулы двойственной будет формула .

Лемма. Если для формулы А двойственной является формула А*, то справедлива равносильность

Теорема. Если формулы А и В равносильны, то равносильны и двойственные им формулы, т.е. А* ~ В*.