Элементами. Из определения следует, что элементы множества обладают двумя свойствами 1 вполне различимы 2

• Название: Элементами. Из определения следует, что элементы множества обладают двумя свойствами 1 вполне различимы 2
• Дата: 16.01.2018
• Размер: 0.67 Mb.
• Имя файла: shpora_dmiml.docx
• Тип: Документы; #34346
• страница: 4 из 9

Так как A [B UC] = [A B]U[AC] то:

m(A) + m(B UC) − m(A [B UC]) = m(A) + m(B UC) − m([A B]U[AC]) ,

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

m(A) + m(B UC) − m(A [B UC])=m(A)+m(B)+m(C)-m(B)-(m(A)+m(A)-m[A]).

После очевидных преобразований, получим в итоге доказываемую формулу

m(AUBUC)= m(A)+m(B)+m(C)-m(B)-m(A)-m(A)++m(A 29.

30. Схемы правильных рассуждений. Аксиоматические теории

Формула, содержащая булевы переменные называется тождественно истинной или тавтологией, если она выражает булеву функцию f()1. Аналогичная формула называется тождественно ложной, если эта формула выражает булеву функцию f()0.Формула называется выполнимой, если f()0. Опровержима, если f()1.Перечислим основные тавтологии:

1)Av.

2)A.

3)A(B).

4)(A)(A)).

5)(A

6)A&B.

7)A

8)A; B(A).

9)()((A)

10)((AB).

1)-10)-тавтологии, ABC-произвольная формула.

Рассуждение будем считать правильным, если из конъюнкций правильных посылок следует истинность заключений. Пусть P₁…P_n посылки заключения Q для правильности. Схемы рассуждений из P₁…P_n Q необходимо установить, что формула (P₁&P₂&…&P_n) Q. При этом правильным является лишь рассуждения формулы Pi,Q не обязательно должны быть истины. Если какая либо из формул Pi=0, то P₁&…&P_n=0; 0 Q всегда истина. P_i=1,i=; P₁&…&P_n=1;1 Q; если Q=1;

Опр: Формальной аксиоматической теорией T,будем называть систему состоящую из 1)некоторого алфавита А.Элементы которого аi будем называть символами теории слова ai,ai+1,…,ai+n. –выражения в Т.2)выделенные выражения в Т называются формулами теории. 3) В Т выделены подмножества формул называемые аксиомами.4) в теории Т определяется множества правил R₁,…,R_k. k называется правилом вывода. Если А₁…А_n, В-формулы и выполнены отношения R(A₁,…,A_n,B),то формула B называется непосредственно следствием формулы A₁,…,A_n подчиненные правилу R.

Выводом в Теории называется любая последовательность формулы B₁,…B_n такая что формула B_i где i=. Являлась либо аксиомой теории Т либо непосредственным следствием предыдущей формулы этой последовательности.

Формула С называется теоремой теории Т, если существует вывод последней формулы которой является С. Таким образом теорема в теории Т формула которой может быть выведена из аксиом теории по имеющимся правилам вывода. В общем случае множества формул {В₁,…,В_n}=Г.

Пусть {A₁,…,A_m} такая что А_i либо аксиомы теории, Либо формулы последовательности Г. Тогда формула А_m называется следствием системы формул Г и обозначается ГА:

Основные правила вывода:

Пусть Г произвольное множество формул. АВС –некоторые формулы.

1)Г, А

Г

3)()&(Г)&(АВ)(Г).

4) ()&())&(Г).
31. Формула содержащая булевые переменные называется тождественно истинной или тавтологией, если она выражает собой булевую функцию f(ⁿ).

Аналогично, формула тождественно ложная, если эта формула выражает функцию f(ⁿ).

Формула называется выполнимой, если f(ⁿ); опровержимой, если f(ⁿ).

Перечислим основные тавтологии:

1) А

2) A→A;

3) A→(B→A);

4) (A→B)→((B→C)→(A→C));

5) (A→(B→C))→((A→B)→(A→C));

6) A&B→A , A&B→B;

7) A→(B→A&B);

8) A→(A˅B) , B→(A˅B);

9))→(()→B);

10)((A→B)→A)→A; (Закон Пирса) (A,B,C – произвольные формулы)

Предикативные формулы:

Предикатом будем называть ф-цию P:Mⁿ→{0,1}, где M- И либо Л , где М – произвольное множество, т.е. ф-ция P сопоставляет каждому вектору ∀(m₁,m₂,…,m_k) координату 0 или 1.

Множество M называется предметной областью предиката, m₁,m₂,…,m_n предметными переменными , а P– предикатным символом n-местного предиката.

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

P-символ предиката.

1) x₁,…,x_n–предикатные переменные, то P(x₁,…,x_n) –n-местный предикат и все его переменные свободны.

2) Если A-предикатная формула, то – так же предикатная формула с тем же набором свободных переменных.

3) Если A,B– предикатные формулы и нет переменных свободных в одной формуле и связанных в друг., то формулы A&B, A˅B , AB , A→B также формулы с теми же свободными и связанными переменными .

4) Если A – формула содержащая свободную переменную –x, то ∀x:A , ∃x:A так же предикатные формулы в каждой из которых х – связная переменная (количество свободных переменных уменьшилось на одну)

Эквивалентными будем называть те предикатные формулы, у которых области истинности совпадают.

Исчисление предикатов:

Теорема: (о подстановке) Пусть F-тождественно истинная формула, тогда подстановка на места её переменных x₁ ,…, x_n формул B₁ ,…, B_n такая , что получаем правильных предикативная формула даёт общезначимую формулу логики предикатов.

Теорема: (Черча) Не существует алгоритма, который для любой формулы логики предикатов устанавливал бы, общезначимая формула либо нет.

Составим аксиоматическую теорию исчисления предикатов:

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

1. 
   , → А₁ -А_{4 –} совпадают с соответствующими аксиомами исчисления высказываний. А₅ , ∀x_i (P(x_i)→P(x_k)) если P(x_i) не содержит переменной x_k A₆ , P(x_i)→∃x_k(P(x_k))
   

3)Правило вывода:

1)A,(A→B)/B ; (A,A→B⊦B)

2)B→A(x_i)/B→∀x_iA(x_i) ;если B не содержит переменной x_i

3) A(x_i)→B/ ∃x_i( A(x_i))→B; при этом B не содержит x_i

4)Любую связанную переменную в формуле А можно заменить в кванторе и во всех вхождениях этой переменной в области действия этого квантора.

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

1. 
   Аксиомы исчисления предикатов общезначимые формулы
   
2. 
   Формула полученная из общезначимой по любому из правил вывода 1-4 так же является общезначимой
   
3. 
   Любая выводимая в исчислении предикатов формула является общезначимой
   

Исчисления предикатов не противоречивы, т.к. невозможно одновременно вывести формулы Aи .

32. Минимальные , кратчайшие и тупиковые ДНФ.

Элементарную конъюнкцию К будем называть импликантой функции f , если для ∀ã , K(ã)=1 влечет за собой выполнение условия f(ã)=1.

Импликант К –простой, если выражение получающееся из его выбрасывания любых их множителей не является импликантой f.

ДНФ называют минимальной, если она содержит наименьшее число литералов, среди всех ДНФ, эквивалентных ей.

Длиной ДНФ называют число входящих в нее элементарных конъюнкций.

ДНФ называют кратчайшей, если она имеет наименьшую длину среди всех эквивалентных ей ДНФ.

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

Тупиковой ДНФ функции f(ⁿ) называется такая ДНФ её простых импликант из которой нельзя выбросить ни одного импликанта не изменив функцию f.

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

Алгоритм построения тупиковой ДНФ:

Пусть f(ⁿ) – функция алгебры логики (булевая).

1)находим табличные значения функции f(ⁿ)=(101…01)

2)по табличным значениям строим СДНФ

3)строим СДНФ функции f в виде: f=K₁˅ K₂˅….˅K_{m ,} где K_i – простые импликанты.

4)строим матрицу покрытий простых импликант функции f

5)для каждого столбца j (1jK) находим множество E_j номеров строк для которых a_j=1.

Cоставляем множество E_jтаких элементов, E_j= (e_j1 ,e_j2 ,…, e_ji), где e_ji– импликанты соответствующие значению 1.

Полученное выражение A=˅(j=1,k)E_j– называется решёточным покрытием ДНФ функции f.

Удаляя все дублирующиеся символы получаем тупиковую ДНФ.
33. Сокращённые ДНФ. Построение сокращённых ДНФ булевых функций методом Блейка.Пример.

Элементарную конъюнкцию К будем называть импликантой функции f , если для ∀ ã, K(ã)=1 влечет за собой выполнение условия f(ã)=1.

Импликант К –простой, если выражение получающееся из его выбрасывания любых их множителей не является импликантой f.

Теорема: Всякая функция реализуется дизъюнкцией своих простых импликант. Сокращённая –дизъюнкция всех простых импликант функции f.

Любая функция f реализуется своей СДНФ.

Для преобразования ДНФ в СДНФ:

1. 
   (полное склеивание)
   
2. 
   (неполное склеивание)
   
3. 
   (обобщенное склеивание)
   
4. 
   A˅A*B=A (поглощение)
   
5. 
   A˅A=A ; A&A=A (удаление дублирующих членов)
   

Метод Блейка: получение СДНФ состоит в применении правил обобщенного склеивания и поглощения, причем правила применяются слева направо.

На первом этапе производится операция обобщенного склеивания, до тех пор пока это возможно. На втором этапе операция поглощения.

Пример: D=x*y˅⌐x*z˅⌐y*z;

D₁=x*y˅⌐x*z˅⌐y*z˅y*z˅x*z˅z=x*y˅z˅z˅z=x*y˅z


34. Построение сокращённых ДНФ булевых функций методом Квайна.Пример.

Теорема Квайна: Если в ДНФ функции f провести все операции неполного склеивания, после чего все операции поглощения и удаления дублирующих членов, то в результате получится СДНФ функции f.

Пример:f( ⁴)=(0101101001101001) ;

ДНФ=⌐x₁⌐ x₂⌐ x₃ x₄ ˅⌐x₁⌐x₂ x₃ x₄ ˅⌐x₁ x₂⌐x₃ ⌐ x₄ ˅⌐x₁ x₂ x₃ x₄ ˅x₁⌐x₂⌐ x₃ x₄ ˅x₁⌐x₂ x₃ ⌐ x₄ ˅x₁ x₂⌐x₃ ⌐ x₄ ˅x₁ x₂ x₃ x₄

X1	X2	X3	X4	f
0	0	0	0	0
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	1
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	0	1
1	0	1	1	0
1	1	0	0	1
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1

	x4	x3 x4	x2 x4	x2 x3	x1 x4	x1 x3	x1 x2	x1 x2 x3 x4
x4		x4	x4		x4
x3 x4	x4
x2 x4	x4
x2 x3
x1 x4	x4
x1 x3
x1 x2
x1 x2 x3 x4

	⌐x1⌐ x2⌐ x3 x4	⌐x1⌐x2 x3 x4	⌐ x1 x2⌐x3 x4	⌐x1 x2 x3 ⌐x4	x1⌐x2⌐ x3 x4	x1⌐x2 x3 ⌐ x4	x1 x2⌐x3 ⌐ x4	x1 x2 x3 x4
⌐x1⌐x2 x4	Ӿ	Ӿ
⌐x1⌐x3 x4	Ӿ		Ӿ
⌐x2⌐ x3 x4	Ӿ				Ӿ

⌐x₁⌐x₂x₄ ˅⌐x₁x₂⌐x₃ x₄ ˅x₁⌐x₂⌐x₃ x₄
35.Построение Сокращенных ДНФ геометрическим методом. Пример.

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

a = (a₁, a₂,..., a _{i – 1}, a _i, a _{i + 1}, …, a_n),

b = (a₁, a₂,…, a _{i – 1}, ¬a _i, a _{i + 1}, …, a_n).

Это значит, что наборы a и b таковы, что один из них доминирует над другим (они различаются значением только одной компоненты, значит a ≤ b или b ≤ a), т.е. они образуют ребро булева куба Вⁿ. Следовательно, простой склейке, применяемой к элементарным конъюнкциям исходной СДНФ, представляющей функцию, подлежат те и только те элементарные конъюнкции, которые соответствуют элементам какого-либо ребра булева куба, на котором функция принимает единичное значение. Образно говоря, две соседние вершины куба, на которых функция равна 1, "склеиваются" в ребро, их "соединяющее".

Пример:

F(x,y,z)=(01101110)

x	y	z	F
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

(Нарисовать куб)

N_f={(001),(010),(100),(101),(110)}

ДНФ= ⌐x⌐yz˅⌐xy⌐z˅x⌐y⌐z˅x⌐yz˅xy⌐z

СДНФ=x⌐z˅⌐yz˅⌐xy⌐z

36. Построение минимальных ДНФ с помощью карт Карно.

Метод минимизаций карт Карно:

Применяется для построения СДНФ функций четырех переменных.

В этом методе для функции f( ⁴) составляется таблица размером 4*4 каждая клетка которой соответствует вершине четырехмерного куба, причем соответствия зад. Таким образом, что если склеить карту по вертикали и горизонтали, то соседние карты клетки будут соответствовать соседним вершинам куба.

Клетка в таблице соответствующая вершинам куба в котором функция принимает значение 1 ставят Ӿ.

Гранью называют множество Ӿ карты соответствующей какой-либо грани четырехмерного куба.

Мощность грани – количество Ӿ.

Максимальной гранью для каждой Ӿ будем считать грань с наибольшей мощностью.

Полезной мощностью будем называть множество еще непокрытых Ӿ данной грани (0,1,2,…,m)(m-максимальная мощность грани)

Пример:f( ⁴)=(0010101001010111)

			Ӿ
Ӿ			Ӿ
	Ӿ	Ӿ	Ӿ
	Ӿ	Ӿ

Ӿ	Ӿ		Ӿ
Ӿ	Ӿ		Ӿ
Ӿ	Ӿ	Ӿ

37. Метод Нельсона. (Построение сокращенной ДНФ с помощью КНФ).

1. 
   Суть метода: в КНФ раскрываются скобки и удаляются дублирующие члены, затем удаляем те дизъюнктивные слагаемые, которые содержат одновременно и переменную и ее отрицание. В полученном выражении удаляют все нулевые диз. слагаемые, проводят все поглощения и удаляют дублирующие члены. A˅A*B=A (поглощение)
   

Пример:

()()

Найдем СДНФ:

=

Произведем поглощения :

- СДНФ
38.Построение всех тупиковых ДНФ. Алгоритм минимизации функций в классе нормальных форм.

Пусть f(x₁, …, x_n) – булева функция

1)находим табл. Значения функции f(x₁, …, x_n)=(101…01)

2)по табличным значения строим СДНФ функции f

3)строим СДНФ f=K₁Ú K₂Ú …Ú K_m где K_i -простые импликанты

4)строим матрицу покрытий простых импликант функции f

5)для каждого столбца 1 ≤ j ≤ k находим множество E_jномеров строк для которых a_j = 1 составляем множество =(, , … , ), где импликанты соответствующие значение 1. Получаем выражение A= назыв. Решеточным покрытием ДНФ ф-ции f. Удаляем все дублирующеюся символы получаем ТДНФ.
39. Понятие о функциях k-значной логики. Их особенности.

Функция f(х₁,х₂,…,х_n) аргументы которой определены на мн-ве E^k = {0, 1, 2, …, k – 1} назыв. функцией k-значной логики.

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

В этой таблице k_n – строк. Р_к – множество всех

х1	…	xn-1	xn	f (x1,…,xn-1,xn)
0	…	0	1	f (0,0,…,0)
0	…	0	1	f (0,0,…,1)
……	…	……	……	…….
0	…	0	k-1	……
……	…	….	……	…..
k-1	…….	k-1	k-1	f (k-1, k-1,…, k-1)

функций к-значной логики. Р_к(n) – множество функций из Р_к, зависящих от n-переменной.
Множество всех функций k-значной логики будем обозначать . В P_k часто употребляется задание таких функций, при помощи алгоритма вычислимости функций.

Следующие функции к-значной логики считаются элементарными:

1. 
   Константы 0, 1, …, k-1
   
2. 
   Отрицание Поста : =x+1 mod k.
   
3. 
   Отрицание Лукашевича x = k-1-х;
   
4. 
   Характеристическая функция 1^го рода ;
   
5. 
   Характеристическая функция 2^го рода (возведение в степень);
   
6. 
   xÙy = min{x,y}
   
7. 
   xÚy=max{x,y}.
   
8. 
   Сумма по модулю k x+y=(x+y) mod k;
   
9. 
   Усеченная разность:
   
10. 
    Импликация (x содержит в себе y) xy=
    
11. 
    - функция Вебба.
    
12. 
    Разность:
    

Пусть E будем говорить, что ф-ция f-сохраняет множество E, если "=(), таком, что значения ф-ции . Множество всех функций P_k ,сохраняющих мн-во E обозначим .и называется классом функций, сохраняющих множество Е. Очевидно, что класс Т_Е является замкнутым.
40.Графы. Изоморфизм графов.

Графом G называется совокупность двух мн-в G=(V, E), где V- мн-во вершин графа, а Е –мн-во ребер графа. Между вершинами и ребрами графа G устанавливают отношение инцидентности. Считают, что ребро инцидентно вершинам , если оно соединяет эти две вершины. При этом вершины , называются смежными.

Отношения инцидентности являются самым главным элементом графа, т.к. указывается способ объединении v и e в единый объект.

Ребра инцидентные одной и той же паре вершин назыв. кратными. Граф содер. Кратные ребра назыв. мультиграфом.

Ребро(дуга) концевые вершины которого совпадают назыв. узлом.

Вершина неинцидентная ни одному ребру назыв. изолированной.

Если граф состоит только из изолированных вершин, то он назыв. нульграфом.

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

Дополнением графа G называется граф имеющий те же вершины что и граф G и содержащий только те ребра которые нужно добавить к G, что бы получался полный граф.

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

,

Для вершин ор-графа определяют две локальные степени и , где -кол-во дуг исходящих из вершины v, - кол-во дуг входящих в вершину v.

Петля дает вклад 1 в обе эти степени. В ор-графе суммы этих степеней



Графы G=(V,E) и G'=(V',E') изоморфны (пишут G), если существует взаимно-однозначное соответствие между множествами Vи V', сохраняющее смежность вершин (т.е. такое соответствие, при котором вершины v_i и v_j из множества Vсмежны тогда и только тогда, когда смежны соответствующие им вершины     и  из множества V')
41.Способы задания графов.

Способы задания графов:

Графический способ

Задание графа при помощи матрицы инцидентности

nm – где n кол-во вершин графа, m – кол-во ребер графа. По вертикали и горизонтали указываются вершины и ребра, а на пересечении i-строки и j-столбца, если ребро i инцидентно вершине j ставим 1 и 0 в противном случае.



В случае орграфа



В петле присваивается любое другое число!!! (чаще всего 2)

Списком ребер графа

Список ребер графа представл. столбцом. В левом столбце перечисляется все ребра, а в правом инцидентные ему вершины, причем для n-графа порядок написания вершин произвольный, а для ор-графа первым стоит номер начала дуги.

Если граф имеет изолированные вершины, то они помещаются в конец списка.

Матричный способ:

Матрица смежности - это квадратная матрица размера , где n – кол-во вершин графа.

В случае n-графа проставляется число ребер соединяющих эти две вершины.

В случае ор-графа проставляется кол-во дуг имеющих начало в вершине и конец в вершине .

Определение 2.21. Матрицей смежности конечного графа G с p вершинами называется матрица A(G)=||a_ij|| (i, j = 1, 2, …, p), в которой если смежны вершины то ставим 1, иначе 0.
42. Действия над графами.

Граф H будем называть