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

.

Разложение булевой функции по k переменным x₁, x₂,…, x_k называется разложением Шеннона.

1.3 Теорема Шеннона

Любая булева функция представима в виде разложе-ния Шеннона:

где , - первичные термы.

Пример.

Пусть п = 4, k = 2. Тогда разложение Шеннона будет иметь вид

Следствие.

Предельное разложение Шеннона (k = n) булевой функции имеет вид

.

Предельное разложение Шеннона булевой функции является ее СДНФ.

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

по k переменным

двойственное предельное разложение

.

Двойственное предельное разложение Шеннона булевой функции является ее СКНФ.

2 Булевы функции двух переменных

Рассмотрим простой бинарный элемент – выключатель, который имеет два состояния. Если данный выключатель контролируется входной переменной х,то говорят, что он выключен (открыт) при х = 0 и включен (закрыт) при х = 1, как показано на рис. 1:

х = 0 х = 1

Рис. 1 - Два состояния выключателя

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

х

Рис. 2 - Графическое обозначение выключателя

Рассмотрим соединения лампы с источником питания, представленные следующими схемами:

Рис. 3 - Лампа, управляемая выключателем: а – простое соединение с батареей; б – использование заземления, как обратной связи

Используя условное обозначение L, можно описать состояние лампы как функции входной переменной. Если лампа светится, то L = 1. Если лампа не светится, то L = 0. Поскольку L = 1 при х = 1, L = 0 при х = 0, то можно говорить, что L(х) = х – логическая функция, х – логическая переменная. Это простое логическое выражение описывает выход как функцию от входа.

2.1 Булевы функции от двух переменных

Рассмотрим теперь возможность использования двух выключателей для управления состоянием лампы. Пусть х₁ и х₂ – управляющие переменные (входы) для этих выключателей. Выключатели могут быть соединены последовательно или параллельно, как показано на рис. 4:

Рис. 4 - Две основные функции: а – последовательное соединение (функция логического умножения AND); б – параллельное соединение (функция логического сложения OR)

2.2 Последовательное соединение двух выключателей

При последовательном соединении лампа будет светиться только, если оба выключателя включены (одновременно). Это поведение может быть описано выражением: , где L = 1 при х₁ = х₂ = 1,

L = 0 в противном случае.

Символ называется AND-оператором. Говорят, что схема на рис. 3.4,а реализует логическую AND-функцию (логическое умножение).

2.3 Параллельное соединение двух выключателей

При параллельном соединении двух выключателей лампа будет гореть, если выключатели х₁ и х₂ включены. Лампа также будет гореть, если оба выключателя включены (одновременно). Лампа не будет гореть только, если оба выключателя открыты (разомкнуты, выключены). Это поведение может быть описано как:

, где L = 1 при х₁ = 1 или х₂ = 1, или х₁ = х₂ = 1; L = 0 при х₁ = х₂ = 0.

Символ называется OR-оператором. Говорят, что схема на рис. 4,б реализует логическую OR-функцию (логическое сложение).

В приведенных выше выражениях для AND и OR реализует результат (выход) есть логическая функция с двумя входными переменными. Функции AND и OR являются двумя наиболее важными логическими функциями. Вместе с некоторыми другими простыми функциями они могут быть использованы как составные части (строительные блоки) для реализации логических схем.

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

.

Лампа горит, если х₃ = 1 и одновременно равны 1 либо х₁, либо х₂ (х₁ = 1 или х₂ = 1)

Рис. 5 - Последовательно-параллельное соединение выключателей

2.4 Инверсия

Пусть лампа подсоединяется к источнику питания так, как показано на рис. 6:

Рис. 6 - Инвертирующая схема

В этом случае выключатель соединяется параллельно с лампой. Лампа будет гореть, когда выключатель выключен. Формально такое функци- ональное поведение выражается: , где L = 1 при х = 0 и L = 0 при х = 1. Значение этой функции обратно значению входной переменной.

Вместо слова инверсия существует более общий термин отрицание.

Таким образом, есть отрицание х: . Символ ¯ называют NOT-оператором.

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

Индекс I функциональной переменной f_i, I = 0, 1, 2, 3, равен десятичному эквивалентному набору значений этой функции, читаемому сверху вниз.

Функции f₀(x) и f₃(x) – константы 0 и 1 соответственно. Их значения не зависят от значения переменной х. Функция f₁(x) “ повторяет “ х: f₁(x) = x.

Функция f₂(x) называется отрицанием х (или функцией НЕ) и обозначается , т.е. f₂(x) = . Ее значение противоположно значению х.

Булевых функций двух переменных – шестнадцать:

Индекс I функциональной переменной f_i, I = 0, 1, 2, …, 15, равен десятичному эквивалентному набору значений этой функции, читаемому сверху вниз. Приведем эти булевы функции:

- константа ноль;

- конъюнкция;

х₁ –|→ - левая коимпликация (читается «не если х₁, то х₂ », префикс ко – от лат. conversus – обратный);

;

х₁ ←|– х₂ - правая коимпликация;

;

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

- дизъюнкция;

х₁ ◦ х₂ = х₁ ↓ х₂ - функция Вебба (Пирса);

х₁ ~ х₂ – функция эквивалентности, равнозначности;

- отрицание х₂;

- правая импликация (читается « если х₂, то х₁ »);

- отрицание х₁;

- левая импликация (читается «если х₁, то х₂ »);

- функция Шеффера;

- константа единица.

2.5 Свойства элементарных функций алгебры логики

2.5.1 Функция сложения по модулю два (по mod 2)

Пусть Операция “сложениe по mod p “ определяется следующим образом: а b = c, где с – остаток от деления на p числа a + b. Например, если р = 7, то . Тогда , .

При сложении по mod 2: р = 2, . Тогда при а = х₁, b = x₂ получим:

.

Справедливы коммутативный и ассоциативный законы. Дистрибутивный закон имеет вид:

Аксиомы:

Связь с функциями ¯:

.

2.5.2 Функция Вебба (Пирса)

Аксиомы: .

Коммутативность: .

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

.

2.5.3 Функция импликации