Дискретная математика

  • 18 сент. 2011 г.
  • 23139 Слова
АХМЕТОВА Наиля Абдулхамитовна

УСМАНОВА Зинира Масгутовна

Дискретная математика

Функции алгебры логики
Учебное пособие

Редактор Г.Р. Орлова
ЛР №020258 от 08.01.98
Подписано в печать 10.02.2000г. Формат 80х64 1/16
Бумага писчая. Печать плоская. Гарнитура «Таймс».
Усл. печ. 7,9. Усл. кр.-отт. 7,9. Уч.-изд.л. 7,8.
Тираж 100 экз. Заказ № . С(3).
Уфимский государственныйавиационный технический университет

Редакционно – издательский комплекс УГАТУ

450000, Уфа-центр, ул. К. Маркса, 12

Содержание
Введение ………………………………………………………...............3
1. Элементы комбинаторики ……………………………………...... 6
1.1. Перестановки. Размещения. Сочетания ………………………… 6
1.2. Задачи по комбинаторике …………………………………………12

2. Функции алгебры логики................................................................... 26

2.1. Элементарные функции алгебры логики ………………………… 26
2.2. Формульное задание функций алгебры логики …………………31
2.3. Принцип двойственности ………………………………………… 35
2.4. Разложение булевой функции по переменным …………………. 40
2.5. Полнота, примеры полных систем ………………………………. 43

2.6.Замыкание и замкнутые классы ………………………………….. 48

2.7. Функции k – значной логики ……………………………………55

2.8. Задачи и упражнения по функциям алгебры логики....................... 58
3. Минимизация булевых функций .......................................................... 80
3.1. Минимизация нормальных форм …………………………………80
3.2. Минимизация частично определенных функций………………… 93
3.3. Задачи по минимизации и доопределению булевых функций……102
4. Логика высказываний ……………………………………………… 106
4.1. Введение в логику высказываний ……………………………… 106
4.2. Задачи по алгебре высказываний ………………………………… 117

Список литературы .............................................................................. 126

ВВЕДЕНИЕ

Дискретнаяматематика – часть математики, которая зародилась в глубокой древности. В широком смысле этого слова к дискретной математике относятся как классические разделы математики: алгебра, теория чисел, теория множеств, математическая логика и т.д., так и новые разделы, которые возникли в середине нашего столетия в связи с внедрением ЭВМ в практическую жизнь. В узком смысле, а в настоящее время именно вузком смысле слова «дискретная математика» и употребляются, сюда относят только те разделы, которые связаны с анализом сложных управляющих систем.
Курс дискретной математики, входящий в программу для ряда специальностей УГАТУ, включает в себя функции алгебры двузначной и к-значной логики, автоматные функции, теорию графов, теорию кодирования, синтез схем из функциональных элементов, элементыкомбинаторики и алгебру высказываний.
В этом пособии будут рассмотрены элементы комбинаторики, функции двузначной и к-значной логики и логика высказываний.
При этом будет использован формализм, который оказался особо подходящим для строгого описания многих разделов компьютерной математики – булева алгебра. Булева алгебра содержит в себе основные положения элементарной логики.Примерами булевой алгебры являются алгебра множеств и алгебра высказываний. Название связано с именем английского математика Джорджа Буля (1815 – 1864). Полное формальное представление булевой алгебры было дано лишь в 1904 году Хантингтоном. Он ввел систему аксиом, из которых могут быть выведены все утверждения булевой алгебры. Предпошлем основному изложению определение булевой алгебры.
Алгеброй Буляназывается произвольное множество элементов {α, β, ...}, для которых определены две бинарные операции, условно называемые «сложение» и «умножение», которые каждым двум элементам α и β ставят в соответствие третий, и одна унарная операция, условно называемая «черта», которая каждому элементу ставит в соответствие другой. В этом множестве имеются два особых элемента, назовем...
tracking img