- •Раздел 1 Основные понятия и методы теории информатики
- •Тема 1.1 Понятие информации
- •Свойства информации
- •Формы представления информации
- •Операции с данными
- •Тема 1.2 Меры и единицы представления, измерения и хранения информации Единицы представления данных
- •Единицы измерения данных
- •Единицы хранения данных
- •Понятие о файловой структуре
- •Тема 1.3 Системы счисления
- •Двоичная арифметика
- •Тема 1.4 Кодирование данных в эвм Кодирование данных двоичным кодом
- •Формы представления чисел
- •Кодирование текстовых данных
- •Универсальная система кодирования текстовых данных
- •Кодирование графических данных
- •Кодирование звуковой информации
- •Тема 1.5 Основные понятия алгебры логики
- •1.5.1 Функции алгебры логики (булевы функции)
- •1.5.2 Основные законы алгебры логики
- •1.5.3 Формы описания логических функций
- •1.5.4 Логические элементы
- •Тема 1.6 Логические основы эвм
- •1.6.1 Минимизация булевых функций
- •Метод непосредственных преобразований
- •Метод Карно-Вейча
- •1.6.2 Построение логических схем
Тема 1.5 Основные понятия алгебры логики
Алгебра логики – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Алгебра логики является теоретической основой построения электронных вычислительных машин и цифровых устройств. Логические двоичные функции получили название булевых по имени английского математика XIX в. Дж. Буля.
1.5.1 Функции алгебры логики (булевы функции)
Таблица 1.5.1 – Значения булевых функций
№ п/п |
Значения булевых функций в зависимости от значений аргументов x и y |
Обозначение функции |
Название функции |
||||
|
x |
0 |
0 |
1 |
1 |
|
|
|
y |
0 |
1 |
0 |
1 |
|
|
1 |
F0(x, y) |
0 |
0 |
0 |
0 |
0 |
Константа ноль |
2 |
F1(x, y) |
0 |
0 |
0 |
1 |
|
Конъюнкция, логическое умножение, И, , AND |
3 |
F2(x, y) |
0 |
0 |
1 |
0 |
|
Запрет по x, отрицание импликации |
4 |
F3(x, y) |
0 |
0 |
1 |
1 |
|
Переменная x |
5 |
F4(x, y) |
0 |
1 |
0 |
0 |
|
Запрет по y, отрицание импликации |
6 |
F5(x, y) |
0 |
1 |
0 |
1 |
|
Переменная y |
7 |
F6(x, y) |
0 |
1 |
1 |
0 |
|
Сумма по модулю 2, логическая неравнозначность, М2, XOR |
8 |
F7(x, y) |
0 |
1 |
1 |
1 |
|
Дизъюнкция, логическое сложение, ИЛИ, OR |
9 |
F8(x, y) |
1 |
0 |
0 |
0 |
|
Стрелка Пирса, отрицание дизъюнкции, ИЛИ-НЕ, NOT OR |
10 |
F9(x, y) |
1 |
0 |
0 |
1 |
|
Эквивалентность |
11 |
F10(x, y) |
1 |
0 |
1 |
0 |
|
Отрицание, инверсия y, НЕ, NOT |
12 |
F11(x, y) |
1 |
0 |
1 |
1 |
|
Импликация от y к x |
13 |
F12(x, y) |
1 |
1 |
0 |
0 |
|
Отрицание, инверсия x, НЕ, NOT |
14 |
F13(x, y) |
1 |
1 |
0 |
1 |
|
Импликация от x к y |
15 |
F14(x, y) |
1 |
1 |
1 |
0 |
|
Штрих Шеффера, отрицание конъюнкции, И-НЕ, NOT AND |
16 |
F15(x, y) |
1 |
1 |
1 |
1 |
1 |
Константа единица |
1.5.2 Основные законы алгебры логики
Законы нулевого множества:
, , ,
т.е. конъюнкция любого числа переменных обращается в ноль, если хотя бы одна переменная имеет значение 0, независимо от значений других переменных.
Законы универсального множества:
, , ,
т.е. дизъюнкция любого числа переменных обращается в единицу, если хотя бы одна переменная имеет значение 1, независимо от значений других переменных.
Законы идемпотентности (повторения, тавтологии):
, .
Закон двойной инверсии:
, т.е. двойную инверсию можно снять.
Законы дополнительности:
закон логического противоречия
, т.е. конъюнкция любой переменной и ее инверсии есть 0;
закон исключенного третьего
, т.е. дизъюнкция любой переменной и ее инверсии есть 0.
Коммутативные законы (законы перемещения):
,
т.е. результаты выполнения операции конъюнкции и дизъюнкции не зависят от того, в каком порядке следуют переменные.
Ассоциативные законы (законы сочетания):
,
т.е. для записи конъюнкции или дизъюнкции скобки можно опустить.
Дистрибутивные законы (законы распределения):
конъюнкции относительно дизъюнкции:
;
дизъюнкции относительно конъюнкции:
.
Законы поглощения:
, .
Законы склеивания (распространения):
, .
Законы де Моргана (законы инверсии):
для двух переменных:
, т.е. инверсия конъюнкции есть дизъюнкция инверсий;
, т.е. инверсия дизъюнкции есть конъюнкция инверсий;
в общем виде:
или ,
т.е. инверсия функции есть функция от инверсий её аргументов и операций дизъюнкции и конъюнкции.