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

Введение ………………………………………………………...............3

1.Элементы комбинаторики ……………………………………...... 6

1.1.Перестановки. Размещения. Сочетания ………………………… 6

1.2.Задачи по комбинаторике …………………………………………12

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

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

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

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

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

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

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

3.1.Минимизация нормальных форм …………………………………80

3.2.Минимизация частично определенных функций ………………… 93

3.3.Задачи по минимизации и доопределению булевых функций……102

4.Логика высказываний ……………………………………………… 106

4.1.Введение в логику высказываний ……………………………… 106

4.2.Задачи по алгебре высказываний ………………………………… 117

ВВЕДЕНИЕ

Дискретная математика – часть математики, которая зародилась в глубокой древности. В широком смысле этого слова к дискретной математике относятся как классические разделы математики: алгебра, теория чисел, теория множеств,

математическая логика и т.д., так и новые разделы, которые возникли в середине нашего столетия в связи с внедрением ЭВМ в практическую жизнь. В узком

2

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

Курс дискретной математики, входящий в программу для ряда специальностей УГАТУ, включает в себя функции алгебры двузначной и к-

значной логики, автоматные функции, теорию графов, теорию кодирования,

синтез схем из функциональных элементов, элементы комбинаторики и алгебру

высказываний.

В этом пособии будут рассмотрены элементы комбинаторики, функции

двузначной и к-значной логики и логика высказываний.

При этом будет использован формализм, который оказался особо подходящим для строгого описания многих разделов компьютерной математики – булева алгебра. Булева алгебра содержит в себе основные положения элементарной логики. Примерами булевой алгебры являются алгебра множеств и алгебра высказываний. Название связано с именем английского математика Джорджа Буля (1815 – 1864). Полное формальное представление булевой алгебры

было дано лишь в 1904 году Хантингтоном. Он ввел систему аксиом, из которых

«сложение» и «умножение», которые каждым двум элементам и ставят в соответствие третий, и одна унарная операция, условно называемая «черта»,

которая каждому элементу ставит в соответствие другой. В этом множестве имеются два особых элемента, назовем их 0 и и выполняются cледующие правила:

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

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

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

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

3

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

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

7)0 = и =0;

8).

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

абстрактное описание которых позволило обнаружить далеко идущие аналогии.

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

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

Во втором разделе рассматриваются основные положения алгебры логики.

Здесь особую роль играет множество {0,1}, элементы которого не являются числами в обычном смысле, хотя по некоторым свойствам и похожи на них.

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

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

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

4

сложности схем, и «автоматные функции» – для доопределения частично

определённых функций.

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

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

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

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

1.1.Перестановки. Размещения. Сочетания

Пусть есть некоторое конечное множество элементов U={a1, a2, ..., an}. Рассмотрим набор элементов ai1 , ai2 , ...,a j j , a j j где U, j = 1, 2, ..., r.

Этот набор называется выборкой объема r из n элементов. Любое подмножество

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

Комбинаторные задачи связаны с подсчетом числа выборок объема r из n

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

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

5

способами, объект B другими n способами и их одновременный выбор невозможен, то выбор “A или B” может быть осуществлен m+n способами.

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

способами, при любом выборе A объект B может быть выбран n способами, то выбор “A и B” может быть осуществлен m n способами.

Пример 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!

6

Доказательство проводится по индукции. Очевидно, если 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)(n r) ... 1.

Размещения. Упорядоченные выборки объемом m из n элементов (m n),

где все элементы различны, называются размещениями. Число размещений из n

элементов по m обозначается

Обозначим x = Anm . Тогда оставшиеся (n – m) элементов можно упорядочить (n – m)! способами. По принципу произведения, если объект A можно выбрать x

способами, объект B (n – m)! способами, то совместный выбор “A и B” можно осуществить x (n – m)! способами, а выбор “A и B” есть перестановки и Pn = n!

n! Отсюда x = Anm = (n - m)! .

7

Рассуждая иначе: первый элемент выбираем n способами, второй – (n – 1)

способами и т.д. , m–й элемент выбираем (n – m + 1) способом. По принципу произведения вновь имеем: n(n – 1)...(n – m +1), что совпадает с Anm .

Пример 4. Группа из 15 человек выиграла 3 различных книги. Сколькими способами можно распределить эти книги среди группы?

Имеем A3 15! = 15 14 13 = 2730.

15 12!

Сочетания. Неупорядоченные выборки объемом m из n элементов (m n)

называются сочетаниями. Их число обозначается

неупорядоченная выборка из n элементов по m, их число Cnm . После того, как эти m элементов отобраны, их можно упорядочить m! способами (в роли объекта B

выступает “порядок“ в выборке). Совместный выбор “A и B“ – упорядоченная выборка.

Пример 5. Группа из 15 человек выиграла 3 одинаковых книги. Сколькими способами можно распределить эти книги?

Сочетания, размещения и перестановки являлись подмножествами исходного множества. Рассмотрим выборки, которые не являются подмножествами.

Размещения с повторениями. Упорядоченные выборки объемом m из n элементов,

где элементы могут повторяться, называются размещениями с повторениями. Их число обозначается Anm (n).

Теорема. Anm (n) = nm.

8

Доказательство. Первый элемент может быть выбран n способами, второй элемент также может быть выбран n способами и так далее, m -й элемент также может быть выбран n способами. По принципу произведения получаем nm .

Пример 6. Кодовый замок состоит из четырех разрядов, в каждом разряде независимо от других могут быть выбраны цифры от 0 до 9. Сколько возможных комбинаций?

Здесь n = 10, m = 4 и ответом будет 104.

Пример 7. Рассмотрим вектор длины m, каждая координата которого может принимать всего 2 значения: 0 или 1. Сколько будет таких векторов?

Это есть выборка, объемом m из двух элементов. Ответ: 2m

Перестановки с повторениями. Пусть имеется n элементов, среди которых k1 элементов первого типа, k2 элементов второго типа и т.д., ks элементов s-го типа, причем k1 + k2 + ... + ks = n. Упорядоченные выборки из таких n

элементов по n называются перестановками с повторениями, их число обозначается Cn(k1, k2, ..., ks). Числа Cn(k1, k2, ..., ks) называются полиномиальными коэффициентами.

n! Теорема. Cn(k1, ..., ks)= k1! k2 !...ks ! .

Доказательство проведем по индукции по s, т. е. по числу типов элементов. При s

= 1 утверждение становится тривиальным: k1 = n, все элементы одного типа и

Cn(n) = 1. В качестве базы индукции возьмем s = 2, n = k1 + k2. В этом случаем перестановки с повторениями превращаются в сочетания из n элементов по k1

(или k2): выбираем k1 место, куда помещаем элементы первого типа.

Пусть формула верна для s = m , т.е. n = k1 + ... + km и

9

Докажем, что она верна для s = m + 1 (n = k1 +... + km + km+1). В этом случае перестановку с повторениями можно рассматривать как совместный выбор двух объектов: объект A – выбор k m + 1 места для элементов (m + 1)-го типа; объект B –

перестановка с повторениями из (n – km+1) элементов. Объект A можно выбрать

коэффициентами. Из этой формулы следует, что Cnm Cnn-m .

Пример 8. Сколько различных слов можно получить, переставляя буквы в слове “математика”?

Решение. Буква “а” входит 3 раза (k 1= 3), буква “м” – 2 раза (k2 = 2), “т” – 2 раза

(k3 = 2), буквы “е”, ”к”, ”и” входят по одному разу, отсюда k3 = k4 = k5 = 1.

10!

C10 (3, 2, , 2, 1, 1, 1) = 3!2!2! =151200.

Сочетания с повторениями. Пусть имеется n типов элементов, каждый тип содержит не менее m одинаковых элементов. Неупорядоченная выборка объемом m из имеющихся элементов (их число m n ) называется сочетанием с повторением. Число сочетаний с повторениями обозначается Cnm (n).

Теорема. Cnm (n) = Cnm+m-1 .

Доказательство. Пусть в выборку вошло m1 элементов первого типа, m2 элементов второго типа, ...mn – n-го типа. Причем каждое 0 m i m и m1+m2+ ...+ mn= =m. Сопоставим этой выборке вектор следующего вида: bn (11...1011...10...011...1).

10