Введение в алгебру логики
Описание файла
Документ из архива "Введение в алгебру логики", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 4 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "дискретная математика" в общих файлах.
Онлайн просмотр документа "Введение в алгебру логики"
Текст из документа "Введение в алгебру логики"
6
ВВЕДЕНИЕ В АЛГЕБРУ ЛОГИКИ
1. Аксиомы алгебры логики
Переменные, рассматриваемые в алгебре логики, могут принимать только два значения – 0 или 1. В алгебре логики определены отношение эквивалентности (обозначается знаком =), операция логического сложения (дизъюнкции), обозначаемая знаком 
(иногда знаком +), логического умножения (конъюнкции), обозначаемая знаками &, 
или точкой (иногда конъюнкция никак не обозначается, например, A&B = A B = A∙B = AB), и отрицания (инверсии), обозначаемая надчеркиванием или апострофом ‘.
В алгебре логики задаются следующие аксиомы:
x = 1, если x 
0; x = 0, если x 1;
0&0 = 0; 1 1 = 1
1&1 = 1; 0 0 =0;
1&0 = 0&1 = 0; 0 1 = 1 0 = 1;
1; 
= 0.
2. Тождества алгебры логики
Для преобразования и упрощения логических выражений используются различные логические тождества, например:
Соотношения 12) и 13) носят название формул де-Моргана. Эти и другие тождества могут быть доказаны с помощью таблиц истинности (см. ниже).
3. Логические функции
Любое логическое выражение, составленное из n переменных с помощью конечного числа операций алгебры логики, можно рассматривать как некоторую функцию n переменных. Такую функцию называют логической. В соответствии с аксиомами алгебры логики функция может принимать в зависимости от значения переменных значение 0 или 1. Функция n логических переменных может быть определена для 2n значений переменных, соответствующих всем возможным комбинациям n-разрядных двоичных чисел. Основной практический интерес представляют следующие функции двух переменных х и у:
f1(x,y) = x & y = x y = x
– логическое умножение (конъюнкция);
f2(x,y) = x y – логическое сложение (дизъюнкция);
f3(x,y) = 
= 
– штрих Шеффера;
f4(x,y) = 
= 
– стрелка Пирса;
f5(x,y) = x
y = 
– сложение по модулю 2;
f6(x,y) = 
– равнозначность.
4. Таблица истинности
Так как область определения любой функции n переменных конечна (2n значений), такая функция может быть задана таблицей значений f(i), которые она принимает на наборах переменных с номером i, где i = 0,…, 2n-1. Такие таблицы называют таблицами истинности. В табл. 1.1 представлены таблицы истинности, задающие перечисленные выше функции.
Таблица 1.1
| № | Значения переменных | Функции | ||||||
| x | у | f1 | f2 | f3 | f4 | f5 | f6 | |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 2 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 3 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
В таблице номер строки (№) есть десятичная запись соответствующего двоичного кода набора переменных.
1.5. Аналитическое представление логических функций
Аналитически запись логических функций может быть представлена в виде дизъюнктивной или конъюнктивной нормальной формы (СДНФ, СКНФ). В дизъюнктивной форме функция записывается как логическая сумма логических произведений, в конъюнктивной форме – как логическое произведение логических сумм. Порядок выполнения действий такой же, как и в обычных алгебраических формулах.
Представление функции в виде СДНФ или СКНФ легко получить по таблице истинности данной функции.
Чтобы получить аналитическое выражение в СДНФ функции, заданной таблицей истинности, нужно записать логическую сумму произведений входных переменных для тех наборов, на которых функция принимает единичное значение, причем, переменная берется без знака инверсии, если ее значение в наборе равно 1 и с инверсией, если ее значение в наборе равно 0.
Чтобы получить аналитическое выражение в СКНФ функции, заданной таблицей истинности, нужно записать логическое произведение сумм входных переменных для тех наборов, на которых функция принимает нулевое значение, причем, переменная берется со знаком инверсии, если ее значение в наборе равно 1 и без знака инверсии, если ее значение в наборе равно 0.
6. Карты Карно
Основной целью логических преобразований является получение компактного логического выражения (минимизация). Минимизацию производят объединением соседних наборов (термов). Объединяемые наборы должны иметь одинаковые значения функции (все 0 или все 1). Если число логических переменных не превышает 5, преобразования логических функций удобно производить с помощью карт Карно.
Для наглядности рассмотрим пример: пусть требуется найти логическое выражение для мажоритарной функции fm трех переменных x, у, z, описываемой таблицей истинности, показанной в табл. 1.2.
Функция fm строится по принципу голосования “два из трех”, т.е. принимает то значение, которое имеют большинство переменных.
Составим карту Карно функции fm (табл. 1.3). В карте столбцам и строкам соответствуют наборы переменных (или одна из переменных), причем переменные располагаются в таком порядке, чтобы при переходе к соседнему столбцу или строке изменялось значение только одной переменной. Например, в строке xy табл. 1.3 значения переменных xy могут быть представлены следующими последовательностями 00, 01, 11, 10 или 00, 10, 11, 01. Внутри таблицу заполняют значениями функции, соответствующими комбинациям значений переменных.
Таблица 1.2
| № | x | y | z | fm |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 | 1 |
На карте Карно отмечаем группы, состоящие из 2k соседних клеток (2, 4, 8,…) и содержащие 1. В результате объединения (склеивания) таких ячеек в записи функции получаются более простые логические выражения. Три овала в таблице определяют логические выражения xy, xz, yz, полученные путем применения следующих операций склеивания:
Таблица 1.3
| xy | 00 | 01 | 11 | 10 |
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
zyz xy xz
Окончательное выражение, описывающее функцию, представляет собой дизъюнкцию полученных при помощи карты конъюнкций. В итоге получаем выражение в дизъюнктивной нормальной форме (ДНФ)
fm = xy v xz v yz .
Самая короткая по числу букв ДНФ будет представлять собой минимальную дизъюнктивную нормальную форму (МДНФ).
Если объединять 0, то получим запись в конъюнктивной нормальной форме (КНФ)
fm = (x v y)( x v z)(y v z).
Обратим внимание на то, что полученные записи функции fm в ДНФ или КНФ являются более компактными, чем ее представления в СДНФ или СКНФ.
7. Логические элементы и схемы
Физическое устройство, реализующее одну из операций алгебры логики или простейшую логическую функцию, называется логическим элементом.
На рис. 1.1 показаны условные графические обозначения типовых логических элементов, принятые в России и за рубежом.
Схема, составленная из конечного числа логических элементов по определенным правилам, называется логической схемой. Логическая схема реализует логическую функцию.
