Теоремы поглощения, склеивания и де Моргана

Теорема поглощения записывается в двух формах — дизъюнктивной и

конъюнктивной, соответственно:

А +АВ =А (16)

А(А + В)=А (17)

Докажем первую теорему. Вынесем за скобки букву А:

А + АВ= А(1 + В)

Согласно теореме (3) 1 + В = 1, следовательно

А(1 + В) = А • 1 = А

Чтобы доказать вторую теорему, раскроем скобки:

А(А + В) = А • А + АВ = А + АВ

Получилось выражение, только что доказанное.

Рассмотрим несколько примеров на применение теоремы поглощения при

упрощении булевых формул.

Теорема склеивания также имеет две формы — дизъюнктивную и

конъюнктивную:

Докажем первую теорему:

поскольку согласно теоремам (5) и (4)

Для доказательства второй теоремы раскроем скобки:

Согласно теореме (6) следовательно:

По теореме поглощения (16) А+АВ = А

Теорема поглощения, как и теорема склеивания, применяется при упрощении

булевых формул, например:

Теорема де Моргана связывает все три основные операции булевой алгебры

— дизъюнкцию, конъюнкцию и инверсию:

Первая теорема читается так: инверсия конъюнкции есть дизъюнкция

инверсий. Вторая: инверсия дизъюнкции есть конъюнкция инверсий. Доказать теоремы Моргана можно с помощью таблиц истинности для левой и правой частей.

Теорема де Моргана применима и к большему числу переменных:

Лекция 5

Инвертирование сложных выражений

Теорема де Моргана применима не только к отдельным конъюнкциям

или дизъюнкциям, но и к более сложным выражениям.

Найдем инверсию выражения АВ + CD , представленного в виде дизъюнкции конъюнкций. Инвертирование будем считать законченным, если знаки отрицания стоят только над переменными. Введем обозначения: АВ = Х;

CD = Y, тогда

Найдем и подставим в выражение (22):

Таким образом:

Рассмотрим выражение, представленное в конъюнктивной форме:

(А + В)(С + D)

Найдем его инверсию в виде

Введем обозначения: А + В = X; С + D =Y, тогда

Найдем и подставим их в выражение

(23):

Таким образом:

При инвертировании сложных выражений можно пользоваться следующим правилом. Чтобы найти инверсию, необходимо знаки конъюнкции заменить знаками дизъюнкции, а знаки дизъюнкции — знаками конъюнкции и поставить инверсии над каждой переменной:

Понятие булевой функции

В общем случае функция (лат. functio — исполнение, соответствие,

отображение) — это некоторое правило (закон), согласно которому каждому элементу множества X, представляющего собой область значений независимого переменного х, ставится в соответствие определенный элемент множества F,

под которым понимается область значений зависимого переменного f. В случае булевых функций X = F = {0, 1}. Правилом, при помощи которого задается функция, может служить любая булева формула, например:

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

Аргументы — это независимые переменные, они могут принимать любые значения — либо 0, либо 1. Функция же f — зависимая переменная. Ее значение полностью определяется значениями переменных и логическими связями между ними.

Главная особенность функции: чтобы определить ее значение, в общем случае необходимо знать значения всех аргументов, от которых она зависит. Например, приведенная выше функция зависит от трех аргументов А, В, С.Если принять А = 1, то получим

т. е. получилось новое выражение, не равное ни нулю, ни

единице. Пусть теперь В= 1. Тогда

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

Примем, наконец, С= 0. Тогда получим: f = 0. Таким образом, если в исходном выражении принять А = 1, В= 1, С = 0, то функция примет нулевое значение: f = 0.

Рассмотрим понятие набора значений переменных.

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

называть просто набором. Набор значений аргументов — это последовательность нулей и единиц, например, 110, где первая цифра соответствует первому аргументу, вторая — второму и третья — третьему. Очевидно, что необходимо заранее договориться, что такое первый, второй или, допустим, пятый аргумент. Для этого удобно пользоваться алфавитным расположением букв.

Например, если

то согласно латинскому алфавиту первым является аргумент Р, вторым —

Q, третьим — X, четвертым — У. Тогда по набору значений аргументов легко

найти значение функции. Пусть, например, дан набор 1001. Согласно его

записи т. е. на наборе 1001 заданная функция равна единице.

Еще раз отметим, что набор значений аргументов — это совокупность

нулей и единиц. Двоичные числа также являются наборами нулей и единиц.

Отсюда возникает вопрос — нельзя ли наборы рассматривать как двоичные

числа? Можно, и во многих случаях это очень удобно, особенно если двоичное

число перевести в десятичную систему. Например, если

А = 0, В = 1, С = 1, D = 0,

то набор примет вид 0110. Если его считать двоичным числом, то:

0_*2³+1_*2²+1_*2¹+0_*2⁰ = 4+2 = 6

т. е. заданный набор имеет номер 6 в десятичной системе.

Если по десятичному номеру требуется найти значения аргументов, то

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

Пусть, например, требуется найти значения аргументов А, В, С, D, Е, Fпо набору с номером 23. Переводим число 23 в двоичную систему методом

деления на два:

23 1

11 1

5 1

2 0

1 1

В результате получаем 23₁₀ = 10111₂. Это число пятизначное, а всего

аргументов шесть, следовательно, слева необходимо записать один нуль:

23₁₀ = 010111₂. Отсюда находим:

А = 0, В = 1, С = 0, D = 1, Е = 1, F = 1.

Сколько всего существует наборов, если известно число п аргументов? Очевидно, столько же, сколько существует n-разрядных двоичных чисел, т. е. 2ⁿ

Лекция 6

 

Задание булевой функции

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

На примере функции

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

Функция зависит от трех аргументов А, В, С. Следовательно, в таблице

предусматриваем три колонки для аргументов A, B, C и одну колонку для значений функции f. Слева от колонки А полезно разместить еще одну колонку. В ней будем записывать десятичные числа, которые соответствуют наборам, если их рассматривать как трехразрядные двоичные номера. Эта десятичная

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

ею можно пренебречь.

Заполняем таблицу. В строке с номером ООО записано:

А = В = С = 0.

Определим значение функции на этом наборе:

В колонке f записываем нуль в строке с набором 000.

Следующий набор: 001, т. е. А = В = 0, С = 1. Находим значение функции

на этом наборе:

На наборе 001 функция равна 1, следовательно, в колонке f в строке с

номером 001 записываем единицу.

Аналогично вычисляем значения функций на всех остальных наборах и

заполняем всю таблицу.

 

⇐ Предыдущая123

Поделиться: