3) Конъюнкция (логическое умножение).

Соответствующие выражения языка:

· Х и Y

· Х вместе с Y

· Х несмотря на Y

· Х в то время, как Y

· как Х так и Y

f (x,у) = x & у

Построим таблицу истинности для конъюнкции. Изобразим прямоугольником множество всех значений. Первый круг будет содержать значения множества А, второй круг значения множества В. Множеством А и В будет пересечение этих кругов (на рисунке закрашена темно-серым цветом). Будем «бросать» точку в прямоугольник с множествами. Результаты попадания в множество А, В и А и В внесем в левую таблицу. В правой таблице заменим попадание во множество А на х, В на у, попадание во множество А и В на f, «нет» на 0, «да» на 1. Правая таблица и есть таблица истинности для конъюнкции.

А

В

А и В

В ЭВМ операция конъюнкции физически реализуется стандартным логическим элементом «и» - конъюнктером.

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

4) Импликация (логическое следование).

Соответствующие выражения языка:

· Х имплицирует Y

· Если Х, то Y

· Х достаточно для Y

· Y следует из Х

· Y необходимо для Х

· Y тогда, когда Х

f (x) = x ® у

Построим таблицу истинности, для импликации используя выражение – не может из «истины» следовать «ложь».

А

В

В следует из А

В ЭВМ нет логического элемента, который реализует операцию импликации. Для реализации данной операции строиться комбиноторно - логическая схема. На основании таблицы истинности составляется булева функция (СДНФ – совершенная дизъюнктивная нормальная форма ).

Выписываем те строчки, где имеются 1 на выходе. Для всех таких наборов переменных запишем конъюнкции, инвертируя те переменные, которым соответствуют 0. Объединим полученные конъюнкции знаком дизъюнкции.

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

Будем упрощать аналитически, используя закон логического склеивания.

5) Эквивалентность (логическая равнозначность ).

Соответствующие выражения языка:

· Х эквивалентно Y

· Х необходимо и достаточно для Y

· Х тогда и только тогда, когда Y

· Х если и только Y

· Х такое же, как и Y

f (x) = x ~ у

Построим таблицу истинности, подставляя в значения эквивалентности «Да», если А и В принимают одинаковые значения и «Нет» в случае различных А и В.

А

В

А эквивалентно В

В ЭВМ нет логического элемента, который реализует операцию эквивалентности. Для реализации данной операции строиться комбинаторно - логическая схема. На основании таблицы истинности составляется булева функция (СДНФ – совершенная дизъюнктивная нормальная форма ).

Выписываем те строчки, где имеются 1 на выходе. Для всех таких наборов переменных запишем конъюнкции, инвертируя те переменные, которым соответствуют 0. Объединим полученные конъюнкции знаком дизъюнкции.

Минимизацию двоичной функции произведем на основании закона де Моргана.