85990 (Математическая логика), страница 3

Аксиомы: .

Импликация обладает свойством коммутативности в виде:

;

ассоциативность не выполняется.

Формулы преобразования функций ¯ через →:

.

2.5.4 Функция Шеффера

Аксиомы: .

Свойство коммутативности верно только для двух переменных:

ассоциативность не выполняется.

Формулы преобразования:

3. Системы функций алгебры логики

3.1 Функциональная полнота

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

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

Отрицание и дизъюнкция в этой алгебре выражаются следующим образом:

Формулы, содержащие знаки называют полиномами.

Полином вида: , где есть либо 1, либо переменная, либо конъюнкция различных переменных, при , называется полиномом Жегалкина.

Теорема.

Любая булева функция может быть представлена полиномом Жегалки- на

где k_i – коэффициенты, принимающие значения 0 или 1: .

3.2 Класс линейных функций (К _Л)

Булева функция называется линейной, если она представима полиномом первой степени

.

Количество линейных функций равно , где п – число перемен-ных.

Для п = 2 их 8:

3.3 Класс функций, сохраняющих ноль (К ₀)

Если булева функция на нулевом наборе переменных равна нулю, то говорят, что функция сохраняет ноль:

3.4 Класс функций, сохраняющих единицу (К ₁)

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

3.5 Класс монотонных функций (К _м)

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

3.6 Класс самодвойственных функций (К _с)

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

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

Функция, совпадающая со своей двойственной, называется самодвойственной.

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

Распределение булевых функций двух переменных по классам

3.7 Принцип двойственности

Если в формуле алгебры логики F заменить знаки всех логических функций на знаки двойственных функций, то получится двойственная формула F ^*, реализующая функцию, двойственную той, которая реализуется формулой F. При этом, если формулы равны F ₁ = F ₂, то верно равенство двойственных формул , которое называется двойственным предыдущему. Например, равенства, являющиеся двойственными друг другу:

и ;

и ;

и ;

и ;

и .

3.8 Полнота функций алгебры логики

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

Например, суперпозицию функций f₁, f₂, f₃ можно задать формулой

.

Если f₁ обозначает дизъюнкцию, f₂ – конъюнкцию, а f₃ – сложение по mod 2, то последняя формула примет вид:

.

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

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

Следовательно, система функций должна быть функционально полной.

3.9 Теорема Поста – Яблонского (критерий функциональной полноты)

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

1) не сохраняющую ноль;

2) не сохраняющую единицу;

3) нелинейную;

4) немонотонную;

5) несамодвойственную.

Примерами функционально полных систем являются, например, системы:

.

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

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

К базису относятся системы функций:

базис 1: ;

базис 2: ;

базис 3: ;

базис 4: функция Шеффера: x₁ | x₂;

базис 5: функция Пирса (Вебба): x₁ ↓ x₂.

Базис 1 – избыточный, базисы 4 и 5 – минимальные (удаление хотя бы одной функции превращает систему ФАЛ в неполную).

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

Пример.

Является ли система булевых функций полной? Если является, то выписать все возможные базисы.

Рассмотрим функцию .

1. Исследуем ее принадлежность к классу К₀:

.

Следовательно, .

2. Исследуем принадлежность функции к классу К₁:

.

Следовательно, .

3. Установим, является ли функция f₁ линейной. Используем метод неопределенных коэффициентов. Предположим, что функция линейная и, следовательно, представима в виде полинома Жегалкина первой степени:

.

Найдем коэффициенты , исходя из предположения линейности этой функции. Зафиксируем набор 000:

, , .

Следовательно, .

Зафиксируем набор 100:

,

,

.

Следовательно, .

Фиксируем набор 010:

,

Фиксируем набор 001:

.

Следовательно, функция (по нашему предположению) может быть представлена полиномом первой степени вида:

.

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

4. Исследуем заданную функцию на самодвойственность.

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

Построим таблицу: ; вычислим значения функции на оставшихся наборах:

:

На наборах 0 и 7, 1 и 6 функция принимает одинаковые значения. Следовательно .