Элементы комбинаторики. Правила умножения и сложения

Пример:

Любую булеву функцию , не равную тождественной единице, можно представить в виде СКНФ.

Получить СКНФ можно преобразовывая формулы, а  можно по таблице истинности.  

7.   Совершенная  дизъюнктивная нормальная форма.

Представление булевой функции  в виде дизъюнкции несовпадающих элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ) этой функции.

Пример 

Одна третья конъюнкции является полной элементарной.

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

Любую булеву функцию  можно представить в виде ДНФ, причем любая булева функция может быть представлена множеством различных ДНФ, равносильных между собой.

Если каждая входящая в ДНФ элементарная конъюнкция является полной относительно набора , то ДНФ называется совершенно дизъюнктивной нормальной формой (СДНФ)

Пример:

Получить СДНФ можно преобразовывая формулы, а можно по таблице истинности.  
 

8.   Переключательные функции. Способы задания.

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

Основы перекл функций заложил англ матем Дж.Буль в 19 веке.

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

Отсутствие сигнала как на входе, так и на выходе будет сигнализировать 0, наличие – 1.

Каждому кортежу  , состоящему из 0 и 1, соответствует одно из 2х значений 0 или 1. По сути, имеем булеву функцию . В данном случае её называют переключательной функцией.

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

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

НЕ ПОЛНОСТЬЮ!!!!

 

9.   Переключательные  функции от 2-х и п переменных.

Переключательные  функции от 2х переменных – это  булевы функции двух переменных. 

10. Определение и примеры функционально полных базисов.

Система F переключательных функций называется функционально полной, если любую переключательную функцию φ можно выразить с помощью суперпозиции некоторого набора переключательных функций системы F.

Очевидно, что  если F – функционально полная система, то добавление любого числа перекл функций не изменит статуса вновь полученной системы, т.е. она останется функц полной.

Функционально полная система функции называется функциональным базисом, если она минимальна, т.е. удаление хотя бы одной из функций приводит к тому, что система теряет свойство полноты.

Система из 3х  функций: дизъюнкции, конъюнкции и отрицания, явл полной, т.к. через них можно  выразить любые функции алгебры логики.

Заметим, что  в силу законов де Моргана:

Дизъюнкцию можно  представить через конъюнкцию и  отрицание. Следовательно, функционально  полной является система функций  и (конъюнкция и отрицание).

Также конъюнкцию можно представить через дизъюнкцию и отрицание. Следовательно, функционально полной является система функций и (дизъюнкция и отрицание).

Итак, примеры функциональных систем:

Системы F3 и F4 являются базисами, т.к. удаление из них любой функции приводит к системе, не являющейся полной. 
 

11. Специальные  разложения переключательных функций.

Любую перекл функцию  кроме тожд нуля можно представить  в виде СДНФ. А в свою очередь,  любую функцию, представленную в  виде СДНФ, можно представить с  помощью суммы по модулю 2, конъюнкции и константы 1. Т.е. любую перекл функцию можно представить с помощью функций: сумма по модулю 2, конъюнкция и константы 1. Отсюда следует, что система функций явл полной.

Более того эта  система является еще и базисом.

Базис называется системой Жегалкина.

Теорема.Каждая перекл функция единственным образом допускает представление в виде полинома Жегалкина.

Пример: . Представим эту функцию в виде полинома Жегалкина.

Решение

 

Другим, более  распространенным способом нахождения полинома Жегалкина явл метод  неопределенных коэффициентов, который  основан на выше указанной теореме 
 

12. Классы Поста.  Теорема о функциональной полноте.

Под классом  функций будем понимать множество  функций, замкнутых относительно операций взятия суперпозиции.

Существуют 5 классов  перекл функций. Это классы Поста (Пост – Америк логик 20 века.

1. Класс линейных функций

Перекл функция  назыв линейной, если она представима  полиномом Жегалкина первой степени:

Число линейных функций рано например при n=2 число линейных функций равно 8:

2. Класс функций, сохраняющих 0

Если перекл функция на кортеже 00…0 равна нулю, то говорят, что функция сохран нуль

Т.о. функция  принадлежит классу функций, сохраняющих 0, если

Для 2х переменных таких функций 8.

3. Класс функций, сохраняющих 1

Если перекл функция на кортеже 11…1 равна 1, то говорят, что функция сохран единицу

Т.о. функция  принадлежит классу функций, сохраняющих 1, если

Для 2х переменных таких функций 8

4. Класс монотонных функций

- монотонная функция

Таких функций 6

5. Класс самодвойственных функций.

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

На кортежах 00 и 11,01,10 противоположные значения могут иметь функции

Теорема Поста  о функциональной полноте. Для того чтобы система булевых функций  была полной необходимо и достаточно, чтобы она содержала: 
-хотя бы одну функцию, не сохраняющую 0

-хотя бы одну  функцию, не сохраняющую 1

-хотя бы одну  функцию, не явл линейной

-хотя бы одну  функцию, не явл монотонной

-хотя бы одну  функцию, не явл самодвойственной.

Каждый базис  содержит не более 4х булевых функций. 

13. Минимизация  переключательных функций. Основные  понятия, 

14. Способы построения  минимальных ДНФ.

Минимизация ДНФ  включает следующие этапы:

1. Получение простых импликант и сокращенной ДНФ
2. Получение тупиковой ДНФ
3. Выбор из тупиковых ДНФ минимальной

Для реализации первого этапа алгоритма будем  применять один из след методов: Метод  Квайна, геометрический, карты Карно

Метод Квайна

В его основе лежат следующие равносильности:

1. Полного склеивания 

2. Поглощения 

3. Не полного  склеивания 

Если в СДНФ провести все операции неполного  склеивания (тем самым усложнив СДНФ), а затем провести операции поглощения, то получится сокращенная ДНФ. 

Геометрический  метод

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

Суть метода: 1) для функции n переменных отмечаются вершины куба, соответств кортежам, на которых функция принимает значение 1.

2) проводят склеивание  – отмечают ребра, содерж 2 отмеч вершины.

3) проводят поглощение  – отмечают грани, содерж все  4 склеенные вершины.

Цель действий – накрыть множество, всех отмеченных вершин, как можно меньшим числом граней, ребер. 
 

Карты Карно

Могут быть использованы для минимизации булевой функции любого числа переменных. Но наиболее удобно использовать его, если n=3 или n=4

Переменные кортежа  разбиваются на 2 части. Первая часть  является кодом столбца, вторах –  строк. Таким образом, карты Карно  неявно задают сами кортежи.

Например:  

 

Процесс минимизации  СДНФ представляет собой склеивание кодов кортежей для каждого сплошного  участка причем колво единиц на таком  сплошном участке должно быть степенью числа 2. 
 

15. Понятие графа.  Виды графов. Изоморфизм.

Во многих прикладных задачах изучаются системы связей между различными объектами. Объекты  удобно изображать точками системы, связи между ними – дугами со стрелками(или без них). Такие системы образ графы. Объекты называют вершинами, дуги – ребрами графа.

Графом G называется совокупность 2х конечных множеств V(множество вершин) и E(множество ребер), между элементами которых определено отношение инцидентности. Каждое ребро инцидентно 2м вершинам , которое оно соединяет.

Граф, содержащий направленные ребра (дуги), называется ориентированным (орграфом). Если ребра не имеют направлений, то граф называют не ориентированным.