VI. Минимизация булевых функций

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

1.1. `x ® (`z « (y Å xz));

1.2. (x ® y) ¯ (y « z);

1.3. (x | (xy)) ® z;

1.4. a_f=(1101 1010);

1.5. a_f=(1101 1001);

1.6. a_f=(1100 1100);

1.7. a_f=(0110 1011);

1.8. a_f=(0110 0111);

1.9. a_f=(0011 1001);

1.10. a_f=(0101 1100);

1.11. a_f=(0111 1011);

1.12. a_f=(0010 1111);

1.13. a_f=(1000 0111).

2. Найти МКНФ для заданной функции. Построить геометрическую интерпретацию данной функции.

2.1.

2.2. (x | y) « xz;

2.3. ((((x | y) ¯ z) |`y) ¯ z);

2.4. ((x Å y) « z)(x ®`yz);

2.5. ((x Ú y) ® (y | (yz))) ¯ ((y «`z) ® x);

2.6. (`x ® y) Å ((`y ® z) Å (z ®`x));

2.7.

2.8. a_f=(1000 0110);

2.9. a_f=(0100 0101);

2.10. a_f=(0010 1001);

2.11. a_f=(0001 0010);

2.12. a_f=(1001 0000);

2.13. a_f=(0000 1101).

3. Найти МДНФ для функции, заданной вектором:

3.1. a_f=(1**0 *01* **0* 0111);

3.2. a_f=(*1*0 **01 *0** 1011);

3.3. a_f=(**10 0**1 0**0 *111);

3.4. a_f=(0**1 1**0 *00* 0*11);

3.5. a_f=(***1 0*** 1 0*0 1*01);

3.6. a_f=(1*** 0*0* 01*0 0*11);

3.7. a_f=(10** 1**0 10** 01*1);

3.8. a_f=(***1 1*0* 01*1 101*);

3.9. a_f=(***0 0*11 1**0 0*11);

3.10. a_f=(*10* 1**1 00*1 1***);

3.11. a_f=(**** 0*11 1**1 0**0);

3.12. a_f=(00** 1*01 0**1 **0*);

3.13. a_f=(0*** 01*1 1*00 **1*);

3.14. a_f=(*1*0 1**0 01** 11*0);

3.15. a_f=(11*0 00** 1*11 0***);

3.16. a_f=(**00 1*01 0**1 *110);

3.17. a_f=(*1** **** 11*1 0*00);

3.18. a_f=(**1* ***0 00*1 1*11);

3.19. a_f=(***0 00*1 11** 1*01);

3.20. a_f=(**0* 10** **11 ***1);

3.21. a_f=(*0** 0*11 1*** 000*);

3.22. a_f=(011* 1**1 1**0 00*0);

3.23. a_f=(1*** 1**0 11*1 0*00);

3.24. a_f=(**** 11*1 **00 *0*0);

3.25. a_f=(*0*1 00*1*110 **00);

3.26. a_f=(***0 0**0 *111 1*00);

3.27. a_f=(00*1 1*01 11*0 110*).

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

4.1. N1=(1**0*10)È(***0110)È(11*01**);	N0=(**100*1)È(0*10*11)È(**11**1)
4.2. N1 =(*1*00*1)È(01*0**1) È(**000*1);	N0=(***1100)È(10*1**0) È(0**10*0)
4.3. N1 =(*0101**)È(*10011*) È(1***000);	N0=(0*0*01*)È(0*1**1) È(000**11)
4.4. N1 =(**00*0*)È(***1*10)È(*0*1101);	N0 =(1**1001)È(0*10*00)È(0*00*1*)
4.5. N1 =(**11*00)È(00110**)È(1*1***0);	N0=(1*00**0)È(**00*10)È(0***110)
4.6. N1 =(*0**010)È(00****0)È(*1**110);	N0=(*00*1*1)È(1*0***1)È(1*0*00*)
4.7.N1 =(*011**0)È(**111*0)È(0**111*);	N0=(1000**1)È(***0101)È(*010*0*)
4.8. N1=(0*100*1)È(0*10*01)È(**10101);	N0=(1**0*10)È(***0110)È(*1*01*0)
4.9. N1=(***1100)È(10*1**0)È(0**10*0);	N0=(*1*00*1)È(01*0**1)È(**000*1)
4.10. N1=(0*0*01*)È(0*1**1)È(000**11);	N0=(*0101**)È(*10011*)È(1***000)
4.11. N1=(1**1001)È(0*10*00)È(0*00*1*);	N0=(**00*0*) È (***1*10) È(*0*1101)
4.12. N1=(1*00**0)È(**00*10)È(0***110);	N0=(**11*00)È(00110**)È(1*1***0)
4.13. N1=(*00*1*1)È(1*0***1)È(1*0*00*);	N0=(*0**010)È(00****0)È(*1**110)
4.14. N1=(1000**1)È(***0101)È(*010*0*);	N0=(*011**0)È(**111*0)È(0**111*)
4.15. N1=(*0110*1)È(0**10*1)È(*1111*1);	N0=(0*001**)È(1*1011*)È(1**0010)

5. Записать формулу, полученную в п.4, в виде суперпозиции над {|}.

VII. Элементы комбинаторики

1. Доказать, что мощность булеана конечного множества А равна .

2. Определить максимальное число переборов при попытке взлома пароля, состоящего из 32 двоичных символов.

3. Сколькими способами можно расположить на шахматной доске 8 ладей, чтобы они не могли бить друг друга.

4. Сколькими способами можно указать на шахматной доске два квадрата: белый и черный?

5. Сколькими способами можно указать на шахматной доске два квадрата без ограничения цвета квадратов?

6. Сколькими способами можно выбрать три краски из имеющихся пяти?

7. Из колоды, содержащей 52 карты, вынули 10 карт. В скольких случаях среди этих карт не окажется ни одного туза? В скольких случаях в числе этих десяти карт окажется:

7.1. ровно один туз?

7.2. хотя бы один туз?

7.3. ровно два туза?

8. Сколькими способами можно расставить 12 белых и 12 черных шашек на черных полях шахматной доски?

9. Найти число векторов , координаты которых удовлетворяют условиям:

9.1.

9.2.

9.3.

10. Каково число матриц из n строк и m столбцов с элементами из множества {0,1}?

11. Каково число матриц из n строк и m столбцов с элементами из множества {0,1}, у которых строки попарно различны?

12. Доказать следующие свойства биномиальных коэффициентов:

12.1.

12.2.

12.3.

12.4. Доказать, что  возрастает по n при фиксированном k.

13. Определить мощность множества А´В, если |A|=n, |B|=m.

14. Сколько существует бинарных отношений между элементами множеств А и В, если |A|=n, |B|=m?

15. Сколько имеется функций из А в В, если |A|=n, |B|=m?

16. Сколько имеется 1-1 – функций из множества А в множество В, если |A|=n, |B|=m?

17. При каких значениях m и n существует взаимно однозначное отображение f:A®B, если |A|=n, |B|=m?

18. Определить мощность множества вершин единичного n-мерного куба.

19. Найти двоичный вектор с номером 50+n, где n номер Вашего варианта

20. Чему равно число наборов  удовлетворяющих условию ?

21. Показать, что для любых  из  справедливы соотношения:

21.1.

21.2.

21.3.

21.4.

22. Найти длину СДНФ функции

22.1.

22.2.

22.3.

---

Дата добавления: 2019-03-09; просмотров: 207; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!