Ахметова Н.А., Усманова З.М. Дискретная математика. Функции алгебры логики. Учебное пособие - файл n1.doc

приобрести
Ахметова Н.А., Усманова З.М. Дискретная математика. Функции алгебры логики. Учебное пособие
скачать (3884.5 kb.)
Доступные файлы (1):
n1.doc3885kb.15.09.2012 03:24скачать

n1.doc

  1   2   3   4   5   6   7   8   9   ...   16

АХМЕТОВА Наиля Абдулхамитовна

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


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


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

Учебное пособие


Редактор Г.Р. Орлова

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

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

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

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

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

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

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

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

7) = и =0;

8) .

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

Например, алгебру Буля образует множество подмножеств любого множества (универсума), где в качестве бинарных операцией взяты пересечение(и объединение (  множеств, в роли особого элемента 0 служит пустое множество  а в роли   сам универсум, в роли операции отрицания – дополнение.

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

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

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

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

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

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




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



1.1. Перестановки. Размещения. Сочетания
Пусть есть некоторое конечное множество элементов U={a1, a2, ..., an}. Рассмотрим набор элементов , где U, j = 1, 2, ..., r.

Этот набор называется выборкой объема r из n элементов. Любое подмножество U является выборкой, но не всякая выборка является подмножеством U, так как в выборку один и тот же элемент может входить несколько раз (в отличие от подмножества).

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

Принцип суммы: если card A = m, card B = n и AB =  , то card AB = =m+n. На комбинаторном языке это означает: если объект A можно выбрать m способами, объект B другими n способами и их одновременный выбор невозможен, то выбор “A или B” может быть осуществлен m+n способами.

Принцип произведения: если card A=m, card B=n, то card (AB)=m+n. На комбинаторном языке это означает: если объект A может быть выбран m способами, при любом выборе A объект B может быть выбран n способами, то выбор “A и B” может быть осуществлен mn способами.

Пример 1. A = 10 {различных шоколадок}, B = 5 { различных пачек печенья}. Выбор “A или B” означает, что выбирается что-то одно и способов выбора в этом случае будет 15. Выбор “A и B” означает, что выбирается 1 шоколадка и 1 пачка печенья и различных вариантов для такого выбора будет 50.

Пример 2. Бросают 2 игральные кости. Сколькими способами они могут выпасть так, что на каждой кости выпадет четное число очков либо на каждой кости выпадет нечетное число очков?

Пусть m – число возможностей для выпадения четного числа на одной кости, n – число возможностей для выпадения нечетного числа. Здесь m = n = 3. По правилу произведения количество выпадения четных чисел, как и нечетных, равно 9. По правилу суммы количество возможностей для выпадения двух четных и двух нечетных чисел будет 18.

Рассмотрим основные способы формирования выборок.

Определение. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Если порядок следования элементов несущественен, то выборка называется неупорядоченной.

Из определения следует, что две упорядоченные выборки, состоящие из одних и тех же элементов, но расположенных в разном порядке, являются различными.

Перестановки. Упорядоченные выборки, объемом n из n элементов, где все элементы различны, называются перестановками из n элементов. Число перестановок из n элементов обозначается Pn.

Теорема. P = n!

Доказательство проводится по индукции. Очевидно, если n = 1, то перестановка только одна и P1 = 1!. Пусть для n = k теорема верна и Pk = k!, покажем, что она тогда верна и для n = k+1. Рассмотрим (k+1)- й элемент, будем считать его объектом A, который можно выбрать k+1 способами. Тогда объект B – упорядоченная выборка из оставшихся k элементов по k. B соответствии с индуктивным предположением объект B можно выбрать k! способами. По принципу произведения выбор A и B можно осуществить k!(k+1) = (k+1)! способами. Совместный выбор A и B есть упорядоченная выборка из k + 1 элементов по k + 1.

Пример 3. Сколько существует способов, чтобы расположить на полке 10 различных книг? Ответ: 10!

Можно рассуждать иначе. Выбираем первый элемент, это можно сделать n способами. Затем выбираем второй элемент, это можно сделать (n  1) способами. По правилу произведения упорядоченный выбор двух элементов можно осуществить n(n  1) способами. Затем выбираем третий элемент, для его выбора останется n  2 возможности, последний элемент можно выбрать единственным способом. Мы вновь приходим к формуле: n(n  1)(nr) ... 1.

Размещения. Упорядоченные выборки объемом m из n элементов (mn), где все элементы различны, называются размещениями. Число размещений из n элементов по m обозначается .
  1   2   3   4   5   6   7   8   9   ...   16


АХМЕТОВА Наиля Абдулхамитовна УСМАНОВА Зинира Масгутовна
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации