Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по дискретной математике - файл DM1.DOC


Лекции по дискретной математике
скачать (708 kb.)

Доступные файлы (5):

DM1.DOC406kb.07.01.2002 03:57скачать
DM2.DOC2358kb.07.01.2002 04:00скачать
DM3.DOC7024kb.05.08.1999 16:35скачать
DM4.DOC9644kb.10.12.1999 17:40скачать
info.txt1kb.03.07.2002 04:57скачать

содержание
Загрузка...

DM1.DOC

Реклама MarketGid:
Загрузка...
1. Алгебра высказываний
В данном разделе будут использоваться латинские буквы x, y, z, … для обозначения произвольных переменных, а большие готические буквы Â, Á, À,… для обозначения формул алгебры высказываний.

Символы ù, &, Ú, ®, ~ называются логическими связками, причем ù называется отрицанием, & - конъюнкцией, Ú - дизъюнкцией, ® - импликацией, ~ - эквивалентностью.

Будем интерпретировать логические связки как функции, определенные на множестве {и, л}(“истина”,”ложь”), со значениями в этом же множестве следующим образом:

Отрицание: ù и = л, ù л = и.

Конъюнкция: и & и = и, и & л = л, л & и = л, л & л = л.

Дизъюнкция: и Ú и = и, и Ú л = и, л Ú и = и, л Ú л = л.

Импликация: и ® и = и, и ® л = л, л ® и = и, л ® л = л.

Эквиваленция: и ~ и = и, и ~ л = л, л ~ и = л, и ~ и = и.

Тогда каждая формула будет интерпретироваться как функция, определенная на множестве {и, л}, со значениями на этом же множестве, полученная из ù, &, Ú, ®, ~ по правилам построения данной формулы.

Значением формулы Â при данных значениях переменных в множестве {и, л} называется значение функции, соответствующей формуле Â, при этих значениях переменных.

Формула называется выполнимой, если существует такой набор значений переменных, при которых эта формула принимает значение “истинно”.

Формула называется тождественно истинной, если эта формула принимает значение “истинно” при всех наборах переменных.

Формула называется тождественно ложной, если эта формула принимает значение “ложно” при всех наборах переменных.

Пусть x1, x 2, …, x n – произвольные переменные (n ³ 1). Будем называть конъюнкцией переменных x1, x 2, …, x n формулу x1 & x 2 & … & x n.Будем называть дизъюнкцией переменных x1, x 2, …, x n формулу x1 Ú x 2 Ú … Ú x n.

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

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

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

а) ( x ® y ) Ú ( x ® ( y & x ));

б) ù (y ® ù (x & y)) ® (x Ú z);

в) x & (y ® x) ®ù x ;

г) (x &ù y) ® y ® (x ® y);

д) x ® (y ® z) ® ((x ® y) ® (x ® z)).
1.2. Доказать выполнимость формул:
а) ù (x ® ù y);

б) (x ® y) ® (y ® x);

в) x ® (y & z) & ù ((y Úz) ® x).
1.3. Доказать тождественную истинность формул:
а) (x ® y) Ú (y ® x);

б) (x ® y) Ú (x ®ù y);

в) x ® (y ® (x &y));

г) (x ® y) ® ((y ® z) ® (x ® z));

д) (ù x ® ù y) ® (y ® x);

е) (x ® y) ® ((x ® ù y) ®ù x);

ж) (ù x ® ù y) ® (ù x ® y) ® x .
1.4. При каких значениях переменных x, y, z, u, v, w следующие формулы ложны?
а) x ® (y & z) ® (ù y ® x) ®ù y;

б) (x Ú y) Ú z ® (x Ú y) & (x Ú z);

в) (x Ú y) & (y Ú z) & (z Ú x) ® x & y & z;

г) (x Ú y) ® (ù x & y) Ú (x &ù y).
1.5. Доказать, что если формулы  и ®Á тождественно истинны, то формула Á - тождественно истинна.
1.6. Доказать, что если формулы ÂÚÁ иù Â Ú À тождественно истинны, то формула Á Ú À тождественно истинна.
1.7. Доказать, что если формулы ù ÂÚÁ и ù ÀÚù Á тождественно истинны, то формула ®ù À тождественно истинна.

1.8. Доказать, что из Â1 = Â2 и Á1 = Á2 следует:

а) (Â1 & Á1) = (Â2 & Á2);

б) (Â1 Ú Á1) = (Â2 Ú Á2);

в) (Â1 ® Á1) = (Â2 ® Á2).
1.9. Доказать эквивалентности:
а) (x ® y) = ù x Ú y;

б) ù (x & y) = ù x Ú ù y;

в) x & (y Ú ù y) = x;

г) (x Ú y) & (x Ú z) & (y Ú t) & (z Ú t) = (x & t) Ú (y & t);

д) x & (x Ú z) & (y Ú z) = (x & y) Ú (x & z);

е) (x Ú y) & (x Ú ù y) = x;

ж) (x & y) Ú ((x Ú y) & (ù x Ú ù y)) = x Ú y;

з) x Ú (ù x & y) = x Ú y.

1.10. Привести к ДНФ и КНФ:

а) (x ® y) ® (z ® ù x) ® (ù y ®ù z);

б) ((((x ® y) ® ù x) ® ù y) ® ù z) ® z;

в) (x ® (y ® z)) ® ((x ® ù z) ® (x ® ù y)).

1.11. По таблице истинности построить СДНФ и СКНФ следующих формул:


x

y

z

t

Â1

Â2

Â3

Â4

л

л

л

л

и

л

л

и

л

л

л

и

и

л

л

и

л

л

и

л

и

л

л

и

л

л

и

и

л

л

л

и

л

и

л

л

л

л

л

и

л

и

л

и

л

л

л

и

л

и

и

л

и

и

л

и

л

и

и

и

и

и

л

и

и

л

л

л

л

и

л

и

и

л

л

и

л

л

л

и

и

л

и

л

и

л

л

и

и

л

и

и

л

л

л

и

и

и

л

л

л

л

л

и

и

и

л

и

л

л

л

и

и

и

и

л

и

л

л

и

и

и

и

и

и

л

л

и


1.12. Доказать, что для любой выполнимой формулы существует эквивалентная ей СДНФ.
1.13. Доказать, что для тождественно ложной формулы не существует эквивалентной ей СДНФ.
1.14. Доказать, что для любой ложной формулы существует эквивалентная ей СКНФ.
1.15. Найти СКНФ:
а) (ù x ® ù y) ® (y & z) ® (x & z);

б) ((x ® y) ® ù x) ® (x ® (y & x));

в) (ù (x & y) ® ù x) & ((x & y) ® ù y);

г) x Ú y;

д) x & y.

1.16. Найти СДНФ:
а) (z ® x) ® (ù (y Ú z) ® x);

б) (ù (x & y) ® x) Ú (x & (y Ú z));

в) ù (x &(y Ú z)) ® ((x & y) Ú z).
1.17. Найти СДНФ для формулы трех переменных, принимающей значение “истинно”, если большинство переменных имеет значение “истинно”.
1.18. Построить формулу Â, такую, чтобы данная формула была тождественно истинной:
а) ((Â & x) ®ù y) ® ((y ®ù x) ® Â);

б) ((Â ® (ù x & y)) ® Â) ® ((Â & y) & (y ® x)).
1.19. По СКНФ формулы Â построить:
а) СДНФ Â** - двойственная к Â);

б) СКНФ формулы ù Â;

в) СДНФ формулы ù Â.

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

Функцией алгебры логики (булевой функцией) называется любая n–местная функция имеющая областью определения и областью значения множество {0, 1}.

Будем говорить, что функция f (x1, …xi-1, xi, xi+1 …, xn) существенно зависит от переменной xi , если f (x1, …xi-1, 0, xi+1 …, xn) ¹ f (x1, …xi-1, 1, xi+1 …, xn). Переменные, от которых функция f (x1, …, xn) существенно зависит, называются существенными переменными для функции f (x1, …, xn), остальные – фиктивными.

В параграфе рассмотрено 11 элементарных булевых функций:

1. Две функции константы f1 = 0; f2 = 1;

2. Две функции одного переменного f3 = x; f4 = ù x;

3. Семь функций f5 = x Ú y - дизъюнкция;

двух переменных f6 = x & y - конъюнкция;

f7= x ~ y - эквиваленция;

f8 = x ® y - импликация;

f9 = x ¯ y - функция Вебба;

f10 = x / y - функция Шеффера;

f11 = x Å y - сложение по модулю 2.



x

y

f1

f2

f3(x)

f4(x)

f5

f6

f7

f8

f9

f10

f11

0

0

0

1

0

1

0

0

1

1

1

1

0

0

1

0

1

0

1

1

0

0

1

0

1

1

1

0

0

1

1

0

1

0

0

0

0

1

1

1

1

0

1

1

0

1

1

1

1

0

0

0


Функцию f, полученную из функций f1,…, fk путем подстановки, возможно многократной, этих функций вместо переменных функции f, называют суперпозицией функций f1,…, fk.

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

Класс функций, сохраняющих константу ноль (f (0,…,0) = 0);

Класс функций, сохраняющих константу единицу (f (1,…,1) = 1);

Класс самодвойственных функций (f (x1,…,xn) = ùf (ù x1,…,ù xn);

Класс линейных функций (f (x1,…, xn) = C0 Å C1x1 Å … Å Cnxn);

Класс монотонных функций (если (x1(1),…, xn(1)) ³ (x1(2),…, xn(2)) , то f (x1(1),…, xn(1)) ³ f (x1(2),…, xn(2))).

Система функций G называется независимой, если ни одна из функций f этой системы не может быть представлена суперпозицией функций из G \ {f}.

Система функций {f1,…, fm} является полной, тогда и только тогда, когда она содержит функцию: 1) не сохраняющую 0; 2) не сохраняющую 1; 3) несамодвойственную; 4) нелинейную; 5) немонотонную (т. Поста-Яблонского).


2.1. Найти все существенные переменные следующих функций:
а) (y & x) Ú (ù y & z);

б) (x & y) Ú z;

в) (x ® (y ® z)) ® ((x ® y) ® (x ® z)).
2.2. Выразить с помощью суперпозиций:
а) & и ® через Ú и ù;

б) Ú и ® через & и ù;

в) & и Ú через ® и ù;

г) &, Ú, ®,ù через /;

д) ù через ® и 0;

е) ù через Å и 1;

ж) Ú через ®.

2.3. Доказать, что нельзя выразить с помощью суперпозиций:

а) ù через &, ®, ~ ;

б) ® через & и Ú;

в) & через Ú и ®.
2.4. Доказать полноту систем функций:
а) { &, Ú, ù };

б) { Ú, ù };

в) { &, ù };

г) { ®, ù };

д) { / };

е) { ¯ };

ж) { Å, Ú, 1 };

з) { ®, 0 }.
2.5. Доказать неполноту систем функций:
а) { &, Ú, ® };

б) { ù }.
2.6. Показать, что следующие системы функций независимы:
а) { ù, ~ };

б) { ù, Å };

в) { ~, Å };

г) { ~, Ú }.
2.7. Показать полноту и независимость системы функций { ~, Ú, 0 }.
2.8. Покажите, что функции ~, Å не составляют полной системы функций. Какие возможны варианты сделать эту систему функций полной добавлением только одной 2-местной функции.

2.9. Привести пример полной сстемы, состоящей из одной 2-местной функции.
2.10. Привести пример полной системы функций :

а) состоящей из одной 3-местной функции;

б) состоящей из одной n-местной функции.
2.11. Доказать,что

а) из всякой немонотнной функции и функций 0 и 1 можно получить суперпозициями функцию ù ;

б) из всякой несамодвойственной функции и функции ù можно получить функции 0 и 1;

в) из всякой нелинейной функции и функций 0 и 1 можно получить суперпозициями функцию &
2.12. Доказать, что всякий базис содержит не более четырех функций.

3. Минимизация булевых функций
В разделе 1 было введено определение элементарной конъюнкции. Рангом элементарной конъюнкции назовем число букв в ней (под буквой понимается либо переменная, либо ее отрицание).

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

Конъюнкции большего ранга покрываются конъюнкциями меньшего ранга. Если имеет место соотношение:
x1 & x2 & … & xn Ú x1 & x2 &… &ù xn = x1 & x2 & … & xn-1
то такая операция называется склеиванием.

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

Выделив все ТДНФ из Сокр.ДНФ и сравнив их по числу букв, можно определить МДНФ.

Таким образом процесс получения МДНФ можно разбить на 2 этапа. Первый этап – получение Сокр.ДНФ. Для этого применяются методы Квайна-Мак-Класки и Блека-Порецкого. Второй этап – построение МДНФ из Сокр.ДНФ, для чего существуют методы Квайна-Мак-Класки и Петрика.

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

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

Задача минимизации булевых функций сформулирована как задача определения МДНФ. Однако в базисе {Ú, &, ù} задача минимизации может быть решена как задача определения МКНФ. С этой целью в двойственных терминах следует определить понятия Сокр. КНФ, ТКНФ, МКНФ, а процесс решения задачи будет аналогичен данному.


Найти МДНФ методом неопределенных коэффициентов:


x

y

z

f1

f2

f3

f4

0

0

0

1

0

0

1

0

0

1

1

1

0

1

0

1

0

0

0

0

1

0

1

1

0

1

1

1

1

0

0

0

0

0

0

1

0

1

1

1

0

0

1

1

0

1

0

0

0

1

1

1

0

1

1

1


Найти МДНФ методом Квайна-Мак-Класки:
а) f (x, y, z) = x & y & z Ú x &ùy &ùz Ú ùx &ùy & z Ú x &ùy & z Ú ùx & y & z Ú ùx &ùy &ùz;
б) f (x, y, z, t) = x & y &ùz &ùt Ú x &ùy & z & t Ú ùx & y & z &ùt Ú x &ùy &ùz &ùt Ú ùx & y &ùz &ùt.

3.3. Найти МДНФ, используя метод Блека-Порецкого:
а) f (x, y, z, t) = x & z &ùt Ú x &ùy &z Ú x &ùy &ùz Ú ùy & z & t Ú x &ùz &ùt;
б) f (x, y, z, t) = ùx & y & z Ú ùy & z & t Ú ùx &ùy & z & t Ú x &ù y Ú ùx & z &t .

3.4. Найти МДНФ, используя метод Петрика:

а) f (x, y, z) = x & y & z Ú x &ùy & z Ú x & y &ùz Ú ùx &ùy & z Ú x &ùy &ùz Ú ùx &ùy &ùz;
б) f (x, y, z, t) = x & y & z & t Ú ùx &ùy & z & t Ú x & y &ùz &ùt Ú x &ùy &ùz &ùt Úùx &ùy &ùz & t Ú ùx &ùy &ùz &ùt;
в) f (x, y, z) = x &ùy Ú y &ùz Ú ùx &ùz Ú x & y & z.
3.5. Найти МДНФ неполностью определенных функций:



x

y

z

t

f1

f2

f3

0

0

0

0

1

0

0

0

0

0

1

*

0

*

0

0

1

0

1

*

0

0

0

1

1

0

*

0

0

1

0

0

0

0

0

0

1

0

1

0

0

*

0

1

1

0

1

*

0

0

1

1

1

*

1

0

1

0

0

0

0

1

*

1

0

0

1

0

0

0

1

0

1

0

1

*

0

1

0

1

1

0

0

*

1

1

0

0

0

0

0

1

1

0

1

0

*

0

1

1

1

0

*

0

*

1

1

1

1

1

0

0



4. Анализ и синтез логических сетей
Сеть, имеющая n входов , k выходов и вершины, соответствующие логическим функциям из заданного множества, называется логическим (n,k)-полюсником или конечным автоматом без памяти. Пример логического (2,2)-полюсника приведен на рис.1, где X = {X1, X2} – множество входов логической сети, F = {F1, F2, F3, F4} – множество логических функций, Y = {Y1, Y2} – множество выходов логической сети.

X1 X2



F1



F2 F1 F3


F4




Y1 Y2

Логическая сеть.
Функции, входящие в (n,k) – полюсник образуют ,следующую систему:




Y1 = j1 (x1,…, xn)

Y2 = j2 (x1,…, xn)

………………….. ( * )

Yk = jk (x1,…, xn)
Эта система называется системой собственных функций (n,k)-полюсника. Анализ логической сети сводится к написанию системы собственных функций для заданной схемы логической сети. Задача синтеза обратна задаче анализа и заключается в построении схемы (n,k)-полюсника, реализующего систему собственных функций (*)

Задача синтеза логической схемы с одним выходом, заключается в построении (n,1)-полюсника, реализующего единственную функцию Y = j (x1,…, xn). В этом случае решение сводится к нахождению МДНФ или МКНФ функции Y и осуществлению синтеза по найденному минимальному представлению.

Синтез схем со многими выходами можно осуществлять несколькими способами:

1. Задачу синтеза (n,k)-полюсника рассматривать как задачу раздельного синтеза k (n,1)-полюсников.

2. Методом простых (первичных) импликант. Для этого находят простые импликанты для каждой из собственных функций, и из них получают МДНФ системы функций.

3.Методом каскадов. При этом любая собственная функция n переменных может быть записана в следующем виде:
ji (x1,…, xn) = xn & ji1 (x1,…, xn-1) Ú ù xn & ji2 (x1,…, xn-1) = xn & (xn-1 & ji11 (x1,…, xn-2) Ú ù xn-1 & ji12 (x1,…, xn-2)) Ú ù xn & (xn-1 & ji21 (x1,…, xn-2) Ú ù xn-1 & ji22 (x1,…, xn-2)) = …

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

4. Методом неполностью определенных собственных функций.

Построить функциональную схему, работа которой определяется следующей функцией :
а) j (x1, x2, x3) = (x1 ¤ x2) Å (ù x3 ® x1);

б) j (x1, x2, x3, x4) = (x1 ¯ x2) & (ù x3 Ú x4) & (x2 ®ù x3).

4.2. Построить функциональную схему (4,1)-полюсника, работа которого определяется следующей функцией j (x1, x2, x3, x4):


x1

x2

x3

x4

a) j

б) j

в) j

0

0

0

0

1

0

0

0

0

0

1

1

0

1

0

0

1

0

1

1

1

0

0

1

1

0

1

1

0

1

0

0

0

0

0

0

1

0

1

0

0

1

0

1

1

0

1

1

0

0

1

1

1

0

1

1

1

0

0

0

0

1

1

1

0

0

1

0

0

1

1

0

1

0

1

1

0

1

0

1

1

0

0

1

1

1

0

0

0

0

1

1

1

0

1

0

1

0

1

1

1

0

1

0

1

1

1

1

1

1

0

1


4.3. Построить функциональную схему (3,4)-полюсника, работа которого определяется следующими собственными функциями j1, j2, j3, j4, с помощью метода первичных импликант :


x1

x2

x3

j1

j2

j3

j4

j1

j2

j3

j4

0

0

0

1

1

1

0

1

0

1

0

0

0

1

1

0

0

0

1

0

0

0

0

1

0

1

0

1

0

1

0

1

1

0

1

1

1

0

0

1

0

1

1

1

1

0

0

1

1

1

1

0

1

0

0

1

0

1

0

1

0

0

0

1

0

0

1

1

0

0

0

1

0

0

1

1

1

1

1

1

1

0

0

1

0

1

0

0



4.4. Построить функциональную схему (3,3)-полюсника, работа которого определяется следующими собственными функциями j1, j2, j3, с помощью метода каскадов:


x1

x2

x3

j1

j2

j3

j1

j2

j3

0

0

0

0

1

1

1

0

1

0

0

1

0

0

0

1

0

0

0

1

0

1

0

0

1

0

1

0

1

1

1

0

0

0

1

0

1

0

0

1

1

1

0

1

0

1

0

1

0

1

0

0

1

0

1

1

0

0

1

1

1

0

1

1

1

1

1

1

0

1

0

1

4.5. Синтезировать схему (3,2)-полюсника методом неполностью определенных функций:


x1

x2

x3

j1

j2

j1

j2

0

0

0

0

0

0

0

0

0

1

0

0

1

0

0

1

0

1

0

1

0

0

1

1

1

0

0

1

1

0

0

0

1

0

1

1

0

1

0

1

0

1

1

1

0

0

1

1

0

1

1

1

1

1

1

0

ЛИТЕРАТУРА
Гаврилов Г.П. Сборник задач по дискретной математике. – М.: Наука, 1977.

Мендельсон Э. Введение в математическую логику. – М. : Наука, 1984.

Марков А.А. Элементы математической логики. – М. Изд-во МГУ, 1984.

Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику: Учеб. пособие. – М. : Изд-во МГУ, 1982.

5. Ершов Ю.Л., Палютин Е.А. Математическая логика:Учеб. пособие

для ВУЗов. – М.: Наука, 1979.





Скачать файл (708 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации