Таблицы сложения и умножения в восьмеричной системе 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(x1, x2,…xn), принимающая значение, равное нулю или единице на наборе логических переменных x1, x2,…xn.

Логические функции от одной переменной представлены в таблице 1.1.

Таблица 1.1

В соответствии с введенными определениями функция f1(x) является абсолютно истинной (константа единицы), а функция f2(х) – абсолютно ложной функцией (константа нуля).

Функция f3(x), повторяющая значения логической переменной, – тождественная функция [f3(x)х], а функция f4(х), принимающая значения, обратные значениям х, – логическое отрицание, или функция НЕ [f4(x)= ].

Логические функции от двух переменных представлены в таблице 1.2.

Таблица 1.2

Дизъюнкция (логическое сложение) – функция f7(х1,х2), которая истинна тогда, когда истинны или х1, или х2, или обе переменные.

Дизъюнкцию часто называют также функцией ИЛИ и условно обозначают так:

f7(х1,х2)=х1+х2= х1 х2.

От дизъюнкции следует отличать функцию f6(х1,х2), которая называется функцией сложения по модулю 2 (функцией исключительное ИЛИ) и является истинной, когда истинны или х1, или х2в отдельности. Условное обозначение этой функции:

f6(х1, х2)=12.

Конъюнкция (логическое умножение) – функция f1(х1,х2), которая истинна только тогда, когда и х1, и х2истинны. Конъюнкцию часто называют также функцией И; условно обозначают так:

f1(х1,х2)=х1&х2= х1 х2.

Пример. Имеются два высказывания: “Завтра будет холодная погода”, “Завтра пойдет снег”. Дизъюнкция этих высказываний – новое высказывание “Завтра будет холодная погода или пойдет снег”. Соединительный союз, который образовал новое предложение, – ИЛИ. Конъюнкция образуется следующим образом: “Завтра будет холодная погода и пойдет снег”. Это высказывание образовано с помощью союза И.

Штрих Шеффера – функция f14(x1,x2), которая ложна только тогда, когда х1и х2истинны. Условное обозначение функции Шеффера:

f14(х1, х2)=х1/х2.

Немецкий математик Д. Шеффер на основе этой функции создал алгебру, названную алгеброй Шеффера.

Функция Пирса (Вебба) – функция f8(х1,х2), которая истинна только тогда, когда х1и х2ложны. Условное обозначение этой функции:

f8(х1, х2)=х1х2.

Математики Ч.Пирс и Д.Вебб, независимо друг от друга изучавшие свойства этой функции, создали алгебру, названную алгеброй Пирса (Вебба).

Импликация – функция f13(x1, х2), которая ложна тогда и только тогда, когда х1истинно и х2ложно. Условное обозначение:

f13(х1, х2)=х1х2.

Все логические функции, приведенные в таблице 1.2, – элементарные функции.

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

f1(x1,x2,…xn)= f2(x1,x2,…xn).

Булевы переменные могут быть действительными или фиктивными. Переменная хiдействительна, если значение функции f(x1,…xi,…xn) изменяется при изменении хi. Переменная хiфиктивна, если значение функции f(x1,…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 в степени 2n.

Рассмотрим некоторые практические примеры использования алгебры логики.

Пример. Предположим, что имеется система кондиционирования воздуха для помещения, где установлена ЭВМ, состоящая из двух кондиционеров малой и большой мощности и работающая при таких условиях: кондиционер малой мощности включается, если температура воздуха в помещении достигает 19°С , кондиционер большой мощности включается, если температура воздуха достигает 22°С (малый кондиционер при этом отключается), оба кондиционера включаются при температуре воздуха 30° С.

Пусть информация о температуре воздуха поступает от датчиков, которые срабатывают при достижении температуры соответственно 19, 22, 30°С. Каждый из этих датчиков выдает входную информацию для устройства управления кондиционерами. Первые три датчика определяют рабочие режимы, и их можно представить как входы управляющего автомата. Используя двоичный алфавит для задания состояний датчика (0 – нет сигнала о достижении заданного уровня температуры, 1 – есть сигнал), функционирование системы управления кондиционерами можно описать следующим образом (табл. 1.4):

Таблица 1.4

Здесь z1 – сигнал датчика, срабатывающего при t=19°С, z1=0, если температура меньше 19°С; z1=1, если температура равна или больше 19°С; z2– датчик, срабатывающий при t=22°С, z2=0, если t< 22°С , z2=1 при t>22°С; z3 – датчик, срабатывающий при t = 30°С, z3=0 при t<30°С , z3=1 при t>30°С; w1и w2– соответственно сигналы управления маломощным и мощным кондиционерами (w=0 – кондиционер выключен, w=1 —кондиционер включен). Таблица описывает функционирование системы управления без нарушений работы.

Впервые теория Дж. Буля была применена П.С. Эренфестом к анализу контактных цепей (1910). Возможность описания переключательных схем с помощью логических формул оказалась весьма ценной по двум причинам. Во-первых, с помощью формул удобнее проверять работу схем. Во-вторых, задание условий работы любой переключательной схемы в виде формул упрощает процесс построения самой переключательной схемы, так как оказалось, что существует ряд эквивалентных преобразований, в результате которых логические формулы упрощаются. При описании переключательных схем замкнутое состояние контакта принимается за истинное высказывание, а разомкнутое – за ложное, поэтому последовательное соединение контактов можно рассматривать как функцию И, а параллельное – как функцию ИЛИ.

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