УДК 519
МИНИСТЕРСТВО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
––––––––––––––
––––––––––––––––––––––
Учебное пособие
по курсу
дискретная математика
 |
2003
Введение. 3
Аксиомы и законы булевой алгебры.. 4
Аксиомы булевой алгебры.. 4
Законы булевой алгебры.. 5
Приоритеты логических операций. 8
Функции алгебры логики. 9
Формы задания функций алгебры логики. 9
Полином Жегалкина. 17
Классы логических функций. 18
Теорема о функциональной полноте. 21
Минимизация функций алгебры логики. 23
Правила склеивания. 26
Правило поглощения. 27
Правило развертывания. 27
Этапы минимизации ФАЛ.. 29
Расчетный метод. 29
Табличный метод. 32
Литература. 41
Теоретической базой при проектировании современных цифровых устройств, предназначенных для числовых вычислений, решения логических задач и задач управления, являются булева алгебра, двоичная арифметика и теория конечных автоматов.
Логика - это наука о законах и формах мышления, математическая же логика занимается применением формальных математических методов для решения логических задач.
В цифровых устройствах чрезвычайно широко используется простейший раздел математической логики - исчисление высказываний или алгебра логики. Алгебру логики часто называют булевой алгеброй в честь английского математика Джоржа Буля, который в 1847 году опубликовал краткую брошюру “Математический анализ логики, сопровождаемый наброском исчисления дедуктивных рассуждений”, а в 1854 году вышел его основной труд “Исследование законов мысли, на которых основаны математические теории логики и вероятностей”.
Базовым понятием булевой алгебры является понятие высказывания, под которым понимается любое утверждение, рассматриваемое только с точки зрения его истинности или ложности. В булевой алгебре не существует истинно-ложных или ложно-истинных высказываний. Высказывание можно рассматривать как логическую переменную, которая может принимать различные значения, например, высказывание “сегодня понедельник” будет истинным в понедельник и ложным во все остальные дни недели. Исчисление высказываний как раз и основано на том, что их можно рассматривать как двоичные переменные, которые могут принимать одно из двух своих значений. Примерами двоичных логических переменных являются разряды чисел, представленных в двоичной системе счисления; замкнутый или разомкнутый контакт; наличие или отсутствие тока в цепи; высокий или низкий потенциал в какой-либо точке схемы и т.п.
Высказывание называется простым, если значение его истинности не зависит от значений истинности других высказываний, и сложным, если значение его истинности зависит от других высказываний. Сложное высказывание можно рассматривать логической функцией, зависящей от простых высказываний и принимающей также два значения (истина, ложь). В свою очередь сложные высказывания могут служить переменными (аргументами) более сложных функций, т.е. при построении логических функций справедлив принцип суперпозиции.
Булеву алгебру как математическую структуру представляют совокупностью следующих объектов:
БА=(0, 1, xi, И, ИЛИ, НЕ, =), (1)
где 0 - символ, обозначающий абсолютную ложь (константа”0”),
1 - символ, обозначающий абсолютную истину (константа “1”).
Примечание: здесь 0 и 1 не цифры!
xi - i-я логическая переменная, от которой зависит какая-либо логическая функция.
И - как минимум двухместная (т.е. зависящая от двух переменных) логическая операция, определяемая как логическое произведение (другое название - конъюнкция). Это такое сложное высказывание, которое истинно только в том случае, когда истинны высказывания, от которых оно зависит, в остальных случаях оно ложно.
ИЛИ - как минимум двухместная логическая операция, определяемая как логическая сумма (другое название - дизъюнкция). Это такое сложное высказывание, которое ложно только в том случае, когда ложны высказывания, от которых оно зависит, в остальных случаях оно истинно.
НЕ - одноместная логическая операция, определяемая как логическое отрицание (другое название - инверсия).
= - отношение эквивалентности.
Объекты (1) булевой алгебры определяются следующими аксиомами:
1. x= 0, если x не равно 1.
x = 1, если x не равно 0.
Аксиома 1 утверждает, что в булевой алгебре рассматриваются только двоичные переменные (закон исключенного третьего).
2. а) 0.0 = 0, б) 1+1 = 1,
0.1 =1.0 = 0, 1+0 = 0+1 = 1,
1.1 = 1. 0+0 = 0.
Аксиомы 2,а определяют логическую операцию И. В качестве знака операции И кроме точки используются знаки: отсутствие знака, &, ^ .
Аксиомы 2,б определяют логическую операцию ИЛИ. В качестве знака операции ИЛИ кроме + используются знаки V.
3. 
Аксиома 3 определяет операцию логического отрицания.
Отношение эквивалентности, обозначаемое символом =, удовлетворяет следующим свойствам:
1) рефлексивности: x = x;
2) симметричности: если x1 = x2, то x2 = x1;
3) транзитивности: если x1 = x2 и x2 = x3, то x1 = x3.
Из свойств отношения эквивалентности следует принцип подстановки: если x1 = x2, то в любом логическом выражении, содержащем x1, вместо x1 можно подставить x2 и в результате будет получено эквивалентное выражение.
С помощью аксиом булевой алгебры можно доказать целый ряд законов методом перебора всех значений переменных. Если закон истинен, то с учетом аксиом 1…3 при подстановке любых
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
