Таблицы сложения и умножения в восьмеричной системе 4 страница

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)=12.

Конъюнкция (логическое умножение) – функция 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). Возможность описания переключательных схем с помощью логических формул оказалась весьма ценной по двум причинам. Во-первых, с помощью формул удобнее проверять работу схем. Во-вторых, задание условий работы любой переключательной схемы в виде формул упрощает процесс построения самой переключательной схемы, так как оказалось, что существует ряд эквивалентных преобразований, в результате которых логические формулы упрощаются. При описании переключательных схем замкнутое состояние контакта принимается за истинное высказывание, а разомкнутое – за ложное, поэтому последовательное соединение контактов можно рассматривать как функцию И, а параллельное – как функцию ИЛИ.

Использование логических функций оказалось особенно полезным для описания работы логических элементов ЭВМ.