6. Информатика. Базовый курс. / Под ред.Симоновича. – СПб., 2001.
7. Косарев В.П., Еремин Л.В. Компьютерные системы и сети. – М., 1999.
8. Дорот В., Новиков Ф. Толковый словарь современной компьютерной лексики. СПб.,2001.
9. Яблонский С.В. Функции алгебры логики и классы Поста. – М., 1966.
10. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. – М., 1976.
ПЕРЕЧЕНЬ УМЕНИЙ
Тематический обзор*
Основы алгебры логики
Основные понятия алгебры логики
Аппарат алгебры логики является одним из важных разделов математической логики. Создатель алгебры логики – английский математик Дж. Буль (1815–1864).
Основное понятие алгебры логики – высказывание. Высказывание – некоторое предложение, о котором можно утверждать, что оно истинно или ложно. Например, высказывание “Земля – это планета Солнечной системы” истинно, а о высказывании “на улице идет дождь” можно сказать, истинно оно или ложно, если указаны дополнительные сведения о погоде в данный момент.
Любое высказывание можно обозначить символом x и считать, что x =1, если высказывание истинно, а x =0 – если высказывание ложно.
Логическая (булева) переменная – такая величина x, которая может принимать только два значения: x = {0,1}.
Высказывание абсолютно истинно, если соответствующая ей логическая величина принимает значение x =1 при любых условиях. Пример абсолютно истинного высказывания – высказывание “Земля – планета Солнечной системы”.
Высказывание абсолютно ложно, если соответствующая ей логическая величина принимает значение x =0 при любых условиях. Например, высказывание “Земля – спутник Марса” абсолютно ложно.
Логическая функция (функция алгебры логики) – функция f (x 1, x 2,… xn), принимающая значение, равное нулю или единице на наборе логических переменных x 1, x 2,… xn.
Логические функции от одной переменной представлены в таблице 1.1.
Таблица 1.1
В соответствии с введенными определениями функция f 1(x) является абсолютно истинной (константа единицы), а функция f 2(х) – абсолютно ложной функцией (константа нуля).
Функция f 3(x), повторяющая значения логической переменной, – тождественная функция [ f 3(x) х ], а функция f 4(х), принимающая значения, обратные значениям х, – логическое отрицание, или функция НЕ [ f 4(x)= ].
Логические функции от двух переменных представлены в таблице 1.2.
Таблица 1.2
Дизъюнкция (логическое сложение) – функция f 7(х 1, х 2), которая истинна тогда, когда истинны или х 1, или х 2, или обе переменные.
Дизъюнкцию часто называют также функцией ИЛИ и условно обозначают так:
f 7(х 1, х 2)= х 1+ х 2= х 1 х 2.
От дизъюнкции следует отличать функцию f 6(х 1, х 2), которая называется функцией сложения по модулю 2 (функцией исключительное ИЛИ) и является истинной, когда истинны или х 1, или х 2в отдельности. Условное обозначение этой функции:
f 6(х 1, х 2)=12.
Конъюнкция (логическое умножение) – функция f 1(х 1, х 2), которая истинна только тогда, когда и х 1, и х 2истинны. Конъюнкцию часто называют также функцией И; условно обозначают так:
f 1(х 1, х 2)= х 1& х 2= х 1 х 2.
Пример. Имеются два высказывания: “Завтра будет холодная погода”, “Завтра пойдет снег”. Дизъюнкция этих высказываний – новое высказывание “Завтра будет холодная погода или пойдет снег”. Соединительный союз, который образовал новое предложение, – ИЛИ. Конъюнкция образуется следующим образом: “Завтра будет холодная погода и пойдет снег”. Это высказывание образовано с помощью союза И.
Штрих Шеффера – функция f 14(x 1, x 2), которая ложна только тогда, когда х 1и х 2истинны. Условное обозначение функции Шеффера:
f 14(х 1, х 2)= х 1/ х 2.
Немецкий математик Д. Шеффер на основе этой функции создал алгебру, названную алгеброй Шеффера.
Функция Пирса (Вебба) – функция f 8(х 1, х 2), которая истинна только тогда, когда х 1и х 2ложны. Условное обозначение этой функции:
f 8(х 1, х 2)= х 1 х 2.
Математики Ч.Пирс и Д.Вебб, независимо друг от друга изучавшие свойства этой функции, создали алгебру, названную алгеброй Пирса (Вебба).
Импликация – функция f 13(x 1, х 2), которая ложна тогда и только тогда, когда х 1истинно и х 2ложно. Условное обозначение:
f 13(х 1, х 2)= х 1 х 2.
Все логические функции, приведенные в таблице 1.2, – элементарные функции.
Две функции равносильны друг другу, если принимают на всех возможных наборах переменных одни и те же значения:
f 1(x 1, x 2,… xn)= f 2(x 1, x 2,… xn).
Булевы переменные могут быть действительными или фиктивными. Переменная хi действительна, если значение функции f (x 1,… xi,… xn) изменяется при изменении хi. Переменная хi фиктивна, если значение функции f (x 1,… xi,… xn) не изменяется при изменении хi.
Пример логической функции от трех переменных представлен в таблице 1.3
Таблица 1.3
Из таблицы 1.3. видно, что переменные х 1и х 2– действительные, а переменная х 3– фиктивная, так как f (х 1, х 2,0)= f (х 1, х 2,1) для всех наборов х 1, х 2.
Использование фиктивных функций дает возможность сокращать или расширять количество переменных для логических функций.
Так как число значений переменных хi ограничено, то можно определить количество функций N от любого числа переменных n: N равно 2 в степени 2 n.
Рассмотрим некоторые практические примеры использования алгебры логики.
Пример. Предположим, что имеется система кондиционирования воздуха для помещения, где установлена ЭВМ, состоящая из двух кондиционеров малой и большой мощности и работающая при таких условиях: кондиционер малой мощности включается, если температура воздуха в помещении достигает 19°С, кондиционер большой мощности включается, если температура воздуха достигает 22°С (малый кондиционер при этом отключается), оба кондиционера включаются при температуре воздуха 30° С.
Пусть информация о температуре воздуха поступает от датчиков, которые срабатывают при достижении температуры соответственно 19, 22, 30°С. Каждый из этих датчиков выдает входную информацию для устройства управления кондиционерами. Первые три датчика определяют рабочие режимы, и их можно представить как входы управляющего автомата. Используя двоичный алфавит для задания состояний датчика (0 – нет сигнала о достижении заданного уровня температуры, 1 – есть сигнал), функционирование системы управления кондиционерами можно описать следующим образом (табл. 1.4):
Таблица 1.4
Здесь z 1 – сигнал датчика, срабатывающего при t =19°С, z 1=0, если температура меньше 19°С; z 1=1, если температура равна или больше 19°С; z 2– датчик, срабатывающий при t =22°С, z 2=0, если t < 22°С, z 2=1 при t >22°С; z 3 – датчик, срабатывающий при t = 30°С, z 3=0 при t <30°С, z 3=1 при t >30°С; w 1и w 2– соответственно сигналы управления маломощным и мощным кондиционерами (w =0 – кондиционер выключен, w =1 —кондиционер включен). Таблица описывает функционирование системы управления без нарушений работы.
Впервые теория Дж. Буля была применена П.С. Эренфестом к анализу контактных цепей (1910). Возможность описания переключательных схем с помощью логических формул оказалась весьма ценной по двум причинам. Во-первых, с помощью формул удобнее проверять работу схем. Во-вторых, задание условий работы любой переключательной схемы в виде формул упрощает процесс построения самой переключательной схемы, так как оказалось, что существует ряд эквивалентных преобразований, в результате которых логические формулы упрощаются. При описании переключательных схем замкнутое состояние контакта принимается за истинное высказывание, а разомкнутое – за ложное, поэтому последовательное соединение контактов можно рассматривать как функцию И, а параллельное – как функцию ИЛИ.
Использование логических функций оказалось особенно полезным для описания работы логических элементов ЭВМ.
