Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



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 году Хантингтоном. Он ввел систему аксиом, из которых могут быть выведены все утверждения булевой алгебры. Предпошлем основному изложению определение булевой алгебры.

Алгеброй Буля называется произвольное множество элементов {a, b, ...}, для которых определены две бинарные операции, условно называемые «сложение» и «умножение», которые каждым двум элементам a и b ставят в соответствие третий, и одна унарная операция, условно называемая «черта», которая каждому элементу ставит в соответствие другой. В этом множестве имеются два особых элемента, назовем их 0 и e, и выполняются cледующие правила:

1) коммутативность сложения и умножения;

2) ассоциативность сложения и умножения;

3) дистрибутивность умножения относительно сложения и наоборот;

4) идемпотентность: a+a=a и a a=a;

5) инволюция =a;

6) правила де Моргана: , ;

7) =e и =0;

8) a+0=a, a+e=e, a 0=0, a e=a.

Определение булевой алгебры, кажущееся с первого взгляда громоздким и весьма специальным, на самом деле явилось результатом глубокого проникновения в существо многих внешне не схожих явлений и прoцессов, абстрактное описание которых позволило обнаружить далеко идущие аналогии.

Например, алгебру Буля образует множество подмножеств любого множества (универсума), где в качестве бинарных операцией взяты пересечение(Ç ) и объединение ( È ) множеств, в роли особого элемента 0 служит пустое множество Æ, а в роли e - сам универсум, в роли операции отрицания – дополнение.

Пособие состоит из четырех разделов. В первом разделе излагаются элементы комбинаторики, причем в таком объеме, который позволяет обеспечить приемлемую строгость изложения в последующих разделах, например, при оценке мощностей замкнутых классов.

Во втором разделе рассматриваются основные положения алгебры логики. Здесь особую роль играет множество {0, 1}, элементы которого не являются числами в обычном смысле, хотя по некоторым свойствам и похожи на них. Наиболее распространенная интерпретация двоичных переменных – логическая: «да» – «нет», «истинно» (и) – «ложно» (л). В контексте, содержащем одновременно двоичные и арифметические величины и функции, эта интерпретация обычно фиксируется явно, например, в языках программирования. В данном пособии логическая интерпретация двоичных переменных необходима только в разделе, посвящённом логике высказываний.

Третий раздел содержит методы минимизации булевых функций. Знание этих методов полезно при изучении, например, таких разделов дискретной математики, как «схемы из функциональных элементов» – для понижения сложности схем, и «автоматные функции» – для доопределения частично определённых функций.

В четвёртом разделе приведены элементы логики высказываний – булевой алгебры на множестве {истина, ложь}.

Каждый раздел пособия содержит теоретический материал, сопровождаемый большим числом примеров, и завершается задачами для самостоятельного решения. Причём количество задач таково, что пособие может быть использовано преподавателями на практических занятиях.

Работа выполнена на кафедре математики УГАТУ. Учебное пособие написано по материалам лекций и практических занятий по курсу дискретной математики, которые проводили авторы.

 

 

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

 


Поделиться:



Популярное:

  1. NFMC-30 -инновационный коктейль оказывает комплексное интенсивное воздействие на все аспекты старения, запускает ряд биохимических реакций, восстанавливающих кожу.
  2. Агрокомплекс по проведению поверхностного улучшения природных пастбищ
  3. Административно- правовое регулирование в промышленном и строительном комплексах.
  4. Административно-правовое регулирование в агропромышленном комплексе.
  5. Административно-правовое регулирование в промышленном и строительном комплексах
  6. Административно-правовое регулирование в системе органов управления в хозяйственно-обслуживающем комплексе.
  7. Бальзам-молочко для жирных и склонных к жирности волос с ультралегкими кондиционерами и аминокислотным себонормализующим комплексом 300 мл. 200 руб. Витэкс
  8. Блок управления цифрового информационного комплекса (БУЦИК)
  9. Взаимосвязи цены в комплексе маркетинга
  10. Водопотребление на животноводческих фермах и комплексах
  11. Вопрос: Формирование комплексной системы оценки развития регионов и эффективности и результативности деятельности органов государственной власти
  12. Воспитание ребенка и комплекс «СветЛ».


Последнее изменение этой страницы: 2016-04-09; Просмотров: 595; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.014 с.)
Главная | Случайная страница | Обратная связь