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

f. линейным (или полным), если

Теорема 4.3.1. Пусть – отношение на . Тогда:

1) рефлексивно тогда и только тогда, (далее используется знак Û) когда .

2) симметрично Û .

3) транзитивно Û

4) антисимметрично Û .

5) антирефлексивно Û Æ.

6) полно Û .

§5. Функции

Определение 5.1. Свойство отношения из в такое, что

называется однозначностью (или функциональностью). Само отношение называется функцией из в .

Обозначение: или

Замечание 5.1.: всякому отношению из в можно поставить в соответствие функцию , полагая (такая функция называется характеристической).

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

Определение 5.3. Если , то функция называется тотальной. В противном случае – частичной. Сужением функции на множестве называется функция, определяемая (и обозначаемая) следующим образом:

Замечание 5.2.: для тотальной функции .

Определение 5.4. Функция называется функцией - аргументов (или - местной функцией).

Определение 5.5. Функция называется:

а) инъективной (или инъекцией),

если ;

б) сюръективной (или сюръекцией),

если

в) биективной (или биекцией), если она инъективна и сюръективна.

Определение 5.6. Пусть и .

Множество называется образом множества .

Множество .

Замечание 5.3.: является отношением из множества во множество :

& &

§6. Отношения эквивалентности

Определение 6.1. Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности.

Обозначение: º

Определение 6.2. Пусть º - отношение эквивалентности на множестве и пусть . Подмножество множества , состоящее из элементов, эквивалентных , называется классом эквивалентности для :

Обозначение: &

Теорема 6.1. Всякое отношение эквивалентности на множестве определяет разбиение этого множества, причем среди элементов разбиения нет пустых. Обратное также верно: всякое разбиение множества , не содержащее пустых элементов, определяет отношение эквивалентности на множестве .

Определение 6.3. Если – отношение эквивалентности на множестве , то множество классов эквивалентности называется фактор - множеством множества по эквивалентности .

Обозначение:

Замечание 6.1.: Фактор – множество является подмножеством булеана, т.е.

.

§7. Отношения порядка

Определение 7.1. Антисимметричное, транзитивное отношение называется отношением порядка. Если отношение порядка является рефлексивным, то оно называется отношением нестрогого порядка. Если же отношение порядка является антирефлексивным, то оно называется отношением строгого порядка.

Определение 7.2. Если отношение порядка является полным, то оно называется отношением полного порядка. Если отношение порядка не обладает свойством полноты, то оно называется отношением частичного порядка.

Обозначение: < - отношение строгого порядка, £ - отношение нестрогого порядка.

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

Пример 7.1. Множество действительных чисел вполне упорядоченно. Булеан – частично упорядоченное множество.

Определение 7.4. Элемент множества с отношением порядка называется минимальным, если не существует элементов, меньших :

&

Пример 7.2. Пустое множество Æ является минимальным элементом булеана по включению.

Теорема 7.1. Во всяком конечном, непустом, частично упорядоченном множестве существует минимальный элемент.

Замечание 7.1. Вполне упорядоченное конечное множество содержит один минимальный элемент. Конечное частично упорядоченное множество может иметь несколько минимальных элементов.

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

Определение 7.6. Пусть и - отношения на множестве . Отношение называется замыканием отношения относительно свойства , если выполняются условия:

1. обладает свойством

2. является надмножеством

3. является наименьшим: &

Глава 2. Булевы функции

§1. Элементарные булевы функции. Основные понятия.

Определение 1.1 :булевой (логической) переменной называется переменная, принимающая лишь два значения “ ” и “ ”.

Определение 1.2 :булевой функцией от логических переменных называется функция, принимающая также лишь два значения “ ” и “ ”.

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

Например, функция трех переменных f(x,y,z) может определяться следующей таблицей истинности:

Это означает, что f (0,0,0)=1, f (0,0,1)=0, f (0,1,0)=1 и т.д.

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

Определение 1.3: Если функция не зависит от некоторой переменной, то такую переменную будем называть фиктивной (несущественной).

§ 2. Булевы функции одной переменной

Переменная x
Название	Обозначение			Фиктивные
нуль
тождественная	x
отрицание	x, ,
единица

§3.Булевы функции двух переменных

Переменная
Переменная
Название	Обозначение					Фиктивные
нуль
конъюнкция	·, &,
сложение по модулю 2	+, ,
дизъюнкция
стрелка Пирса
эквивалентность	~,
импликация	, ,
штрих Шеффера	|
единица

§ 4. Свойства конъюнкции, дизъюнкции и отрицания

Эти функции принято считать основными. Определение этих функций легко может быть перенесено на любое число переменных.

Определение 4.1: Конъюнкцией переменных называется функция, которая принимает значение 1, тогда и только тогда, когда все переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0).

Определение 4.2: Дизъюнкцией переменных называется такая функция, которая равна 0 тогда и только тогда, когда все переменные равны 0 (и, значит, равна 1, когда хотя бы одна из этих переменных равна 1).

Будем обозначать через новую функцию, которая на наборе переменных x ₁, x ₂, …, x_n принимает значение, противоположное f(x ₁, x₂,…, x_n).

Основные свойства этих функций:

1) Идемпотентность.

2) Ассоциативность конъюнкции и дизъюнкции.

3) Поглощение (“Целое поглощает часть”):

4) Распределительные законы:

5) Закон двойного отрицания

6)

7) Правила де Моргана:

Эти правила обобщаются на любое число переменных:

;

§ 5. ДНФ, СДНФ, КНФ, СКНФ

Определение 5.1: Простой конъюнкцией называется конъюнкция одной или нескольких переменных, при этом каждая переменная (либо сама, либо ее отрицание) встречается не более одного раза.

Например, является простой конъюнкцией.

Определение 5.2: Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций.

Например, выражение является ДНФ.

Определение 5.3: Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одном и том же порядке.

Например, выражение является ДНФ, но не СДНФ. Выражение

является СДНФ.

Определение 5.4: Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная (либо сама, либо ее отрицание) входит в дизъюнкцию не более одного раза.

Например, выражение является простой дизъюнкцией.

Определение 5.5: Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций.

Например, выражение является КНФ.

Определение 5.6: Совершенной конъюнктивной нормальной формой (СКНФ) называется такая КНФ, у которой в каждую простую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания) причем в одном и том же порядке.

Например, выражение является СКНФ.

§ 6. Представление логических функций в виде СДНФ (СКНФ)

Теорема 6.1. Всякая булева функция (кроме 0) имеет единственную СДНФ.

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

Теорема 6.2. Всякая булева функция (кроме 1) может быть единственным образом представлена в виде СКНФ.

Алгоритм построения СДНФ булевой функции по заданной таблице истинности:

берем только те наборы переменных , для которых и составляем простую конъюнкцию для этого набора так: если , то берем в этой конъюнкции , если , то берем . Составляя дизъюнкцию этих простых конъюнкций, мы придем к СДНФ.

По аналогии с представлением любой функции (не равной 0) в виде СДНФ можно любую функцию (не равную 1), представить в виде СКНФ. А именно, простые дизъюнкции составляются для тех наборов переменных , для которых , причем если в наборе , то в простую дизъюнкцию включаем , если же , то в неё включаем - .

Пример 6.1. Составим СДНФ и СКНФ для импликации и сложения по модулю 2.

0 0	1
0 1	1
1 0	0	1
1 1	1	0

Дата добавления: 2017-01-13