Теоретический минимум по Computer Science

Правило де Моргана[11]. Одновременно лета и зимы не бывает, поэтому у нас либо не лето, либо не зима. С другой стороны, оба выражения «не лето» и «не зима» истинны, если (и только) у нас не тот случай, когда либо лето, либо зима. Согласно этой логике, выполнение операций AND может быть сведено к операциям OR и наоборот:

!(A AND B) =!A OR! B;

!A AND!B =!(A OR B).

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

Перегрев сервера Сервер выходит из строя из-за перегрева, когда кондиционирование воздуха выключено. Он также выходит из строя из-за перегрева, если барахлит кулер. При каких условиях сервер работает?

Моделируя эту задачу в логических переменных, можно в одном выражении сформулировать условия, когда сервер выходит из строя:

A: Сервер перегревается.

B: Кондиционирование отключено.

C: Не работает кулер.

D: Сервер вышел из строя.

(A AND B) OR (A AND C) D.

Используя правило дистрибутивности, выведем за скобки A:

A AND (B OR C) D.

Сервер работает, когда! D. Противопоставление записывается так:

!D !(A AND (B OR C)).

Применим правило де Моргана и раскроем скобки:

!D !A OR!(B OR C).

Воспользуемся правилом де Моргана еще раз:

!D !A OR (!B AND!C).

Данное выражение нам говорит, что когда сервер работает, мы имеем либо! A (он не перегревается), либо! B AND!C (все в порядке и с кондиционированием воздуха, и с кулером).

Таблицы истинности

Еще один способ анализа логических моделей состоит в сверке данных со всевозможными сочетаниями ее переменных. Каждой переменной в таблице истинности соответствует свой столбец. Строки представляют комбинации состояний переменных.

Рис. 1.5. Таблицы со всеми возможными сочетаниями от одной до пяти логических переменных

Одна переменная требует двух строк: в одной она имеет значение True, в другой — False. Чтобы добавить переменную, нужно удвоить число строк. Новой переменной задается True в исходных строках и False — в добавленных (рис. 1.5). Размер таблицы истинности увеличивается вдвое с каждым добавлением переменной, поэтому такую таблицу оправданно использовать лишь в случаях, когда переменных немного[12].

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

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

1) если база данных заблокирована, то мы можем сохранить данные;

2) база данных не должна блокироваться при заполненной очереди запросов на запись;

3) либо очередь запросов на запись полна, либо полон кэш;

4) если кэш полон, то база данных не может быть заблокирована.

Возможно ли это? При каких условиях станет работать такая система?

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

A: База данных заблокирована	1: A —> B
B: Есть возможность сохранить данные	2:!(A AND C).
C: Очередь запросов на запись полна	3: C OR D.
D: Кэш полон	4: D —>!A.

Далее создадим таблицу истинности со всеми возможными сочетаниями переменных (табл. 1.2). Дополнительные столбцы добавлены для проверки соблюдения технических требований.

Таблица 1.2. Таблица истинности для проверки четырех выражений

Все технические требования удовлетворяются в состояниях с 9-го по 11-е и с 13-го по 15-е. В этих состояниях A = False, а значит, база данных не может быть заблокирована никогда. Обратите внимание, что кэш не заполнен лишь в состояниях 10 и 14.

Чтобы проверить, чему вы научились, попробуйте разгадать загадку «Кто держит зебру?»[13]. Это известная логическая задача, ошибочно приписываемая Альберту Эйнштейну. Говорят, что только 2 % людей могут ее решить, но я сильно сомневаюсь. Используя большую таблицу истинности и правильно упрощая и объединяя логические высказывания, вы ее разгадаете, я уверен в этом.

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

А теперь давайте взглянем на самое впечатляющее применение логики: проектирование электронно-вычислительных машин.

Логика в вычислениях