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

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

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

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

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

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

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

ЛР №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

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

2.1. Элементарные функции алгебры логики ………………………… 26

2.2. Формульное задание функций алгебры логики …………………31

2.3. Принцип двойственности ………………………………………… 35

2.4. Разложение булевой функции по переменным …………………. 40

2.5. Полнота, примеры полных систем ………………………………. 43

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

Функции 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}, элементы которого не являются числами в обычном смысле, хотя по некоторым свойствам и похожи на них. Наиболее распространенная интерпретация двоичных переменных – логическая: «да» – «нет», «истинно» (и) – «ложно» (л). В контексте, содержащем одновременно двоичные и арифметические величины и функции, эта интерпретация обычно фиксируется явно, например, в языках программирования. В данном пособии логическая интерпретация двоичных переменных необходима только в разделе, посвящённом логике высказываний.

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

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

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

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