- •Графы. Булевы функции
- •231000.62 «Программная инженерия»
- •Оглавление
- •Введение
- •1. Контрольная работа «Исследование графов»
- •1.1. Цель работы
- •1.2. Задание на выполнение работы
- •1.3. Варианты заданий
- •1.4. Пример выполнения работы
- •1.4.1. Исследование неориентированного графа.
- •1.4.2. Исследование ориентированного графа.
- •2. Контрольная работа «Исследование булевых функций»
- •2.1. Цель работы
- •2.2. Задание на выполнение работы
- •2.3. Варианты заданий
- •2.4. Пример выполнения работы
- •2.4.1. Составление таблиц истинности формул.
- •2.4.2. Проверка эквивалентности формул.
- •2.4.3. Приведение формулы к днф, кнф, сднф, скнф, полиному Жегалкина.
- •2.4.4.Нахождение сокращенной, тупиковых и минимальных днф булевой функции.
- •2.4.5. Минимизация по картам Карно.
- •2.4.6. Полнота системы булевых функций.
- •3. Требования к содержанию и оформлению отчетов
2. Контрольная работа «Исследование булевых функций»
2.1. Цель работы
Целью работы является получение практических навыков по исследованию булевых функций и закрепление теоретических знаний по разделу «Теория булевых функций».
2.2. Задание на выполнение работы
2.2.1. Составьте таблицы истинности формул.
2.2.2. Проверьте двумя способами, будут ли эквивалентны следующие формулы:
а) составлением таблиц истинности;
б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.
2.2.3. С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ. Постройте полином Жегалкина.
2.2.4. Найдите сокращенную, все тупиковые и минимальные ДНФ булевой функции f(x,y,z) тремя способами:
а) методом Квайна;
б) с помощью карт Карно;
в) методом Квайна-МакКлоски.
Каким классам Поста принадлежит эта функция?
2.2.5. С помощью карт Карно найдите сокращенную, все тупиковые и минимальные ДНФ или КНФ булевой функции f(x1,x2,x3,x4), заданной вектором своих значений.
2.2.6. Является ли полной система функций? Образует ли она базис?
Данные для заданий 2.2.1...2.2.6 по вариантам приведены ниже.
2.3. Варианты заданий
Вариант 1: 1. (xVy)↔(y↓⌐x), (x│⌐y)→(z+⌐(xy)); 2. x→(y+z), (x→y)+(x→z); 3. (xV⌐y)→(⌐z+⌐x); 4. f(0,1,0)=f(1,0,0)=f(1,0,1)=0; 5. f=(1101 1101 0011 0011); 6. J={xVy, ⌐x+y}.
|
Вариант 2: 1. (x↔⌐y)V(y↓x), ((x→⌐y)│⌐z)+⌐(xy); 2. x│(y→z), (x│y)→(x│z); 3. ⌐((xV⌐y)→(z+⌐x)); 4. f(0,1,1)=f(1,0,0)=f(1,1,0)=0; 5. f=(1111 1100 1011 1011); 6. J={x→y, ⌐x⌐y}. |
Вариант 3: 1. (xV⌐y)↔(y↓x), ((x│⌐y)→z)+⌐(xy); 2. x(y+z), xy+xz; 3. (⌐xV⌐y)→ ⌐(z+x); 4. f(0,0,0)=f(0,0,1)=f(1,0,1)=f(1,1,1)=1; 5. f=(1110 0101 0011 0101); 6. J={x↔y, ⌐x│⌐y}.
|
Вариант 4: 1. (x↔⌐y)V(y↓x), ((x→⌐y)│⌐z)+⌐(xy); 2. x(y+z), xy+xz; 3. (xV⌐y)→ ⌐(z↔⌐x); 4. f(0,0,1)=f(1,1,1)=f(1,1,0)=0; 5. f=(1101 0011 1101 0011); 6. J={x+y, ⌐xVy}. |
Вариант 5: 1. (xV⌐y)→(y+x), ((x↔⌐y)│⌐z)↓⌐(xy); 2. x(y→z), xy→xz; 3. ⌐((xV⌐y)→(z↔⌐x)); 4. f(0,0,0)=f(1,1,1)=f(1,1,0)=0; 5. f=(1100 1011 1111 1011); 6. J={⌐x→y, x⌐y}.
|
Вариант 6: 1. (x+⌐y)↔(y│x), ((x↓y)↔⌐z)V⌐(xy); 2. x(y↔z), xy↔xz; 3. ⌐((x│⌐y)+(z→⌐x)); 4. f(0,0,1)=f(0,1,1)=f(1,1,0)=f(1,1,1)=1; 5. f=(0101 0101 1110 0011); 6. J={⌐x↔y, x│⌐y}.
|
Вариант 7: 1. (xV⌐y)↓(y→x), ((x│⌐y)↔⌐z)+⌐(xy); 2. x(y│z), xy│xz; 3. ⌐((z→x)↔(y│x)); 4. f(0,0,0)=f(1,0,1)=f(1,1,1)=0; 5. f=(0011 0011 1101 1101); 6. J={x+⌐y, ⌐xVy}. |
Вариант 8: 1. (x+⌐y)→(y↓x), ((x│⌐y)V⌐z)↔⌐(xy); 2. xV(y→z), (xVy)→(xVz); 3. (x│⌐y)+(⌐z→x); 4. f(1,0,1)=f(0,1,0)=f(1,1,1)=0; 5. f=(1011 1011 1100 1111); 6. J={x→⌐y, ⌐xy}. |
Вариант 9: 1. ⌐x↔(y→(⌐y↓x)), ((⌐x│y)V⌐z)+⌐(xy); 2. xV(y│z), (xVy)│(xVz); 3. (⌐z→x)↔(⌐x│y); 4. f(1,0,0)=f(1,1,0)=f(0,1,1)=f(0,1,0)=1; 5. f=(0101 0011 0101 1110); 6. J={x↔⌐y, ⌐x│y}.
|
Вариант 10: 1. x↓(⌐y→(y↓x)), x+(⌐yV⌐z↔⌐(xy)); 2. xV(y↔z), (xVy)↔(xVz); 3. (z→x)+(x│⌐y); 4. f(0,1,1)=f(1,0,0)=f(1,0,1)=0; 5. f=(0011 1101 0011 1100); 6. J={⌐x+⌐y, xV⌐y}. |
Вариант 11: 1. x↔(⌐y→(y+x)), x│(⌐yV⌐z↓⌐(xy)); 2. x+(y↔z), (x+y)↔(x+z); 3. ((x↓y)→z)+y; 4. f(0,0,1)=f(1,0,0)=f(1,1,0)=0; 5. f=(1011 1111 1011 1100); 6. J={xy, ⌐x→⌐y}.
|
Вариант 12: 1. x→(⌐y│(y+x)), x↔(⌐yV⌐z↓⌐(xy)); 2. x+(y→z), (x+y)→(x+z); 3. ⌐((x│y)→z)+y; 4. f(0,0,1)=f(0,1,1)=f(1,1,1)=0; 5. f=(0011 1110 0101 0101); 6. J={x│y, ⌐x↔⌐y}.
|
Вариант 13: 1. x↓(⌐y→(yVx)), x│(⌐y↔⌐z+⌐(xy)); 2. x+(y│z), (x+y)│(x+z); 3. ⌐((x↓y)→⌐z)+y); 4. f(0,0,0)=f(0,0,1)=f(1,1,0)=0; 5. f=(0011 0011 1100 1111); 6. J={⌐x+y, ⌐xV⌐y}.
|
Вариант 14: 1. x+(⌐y→(y↔x)), x↓(⌐yV⌐z│⌐(xy)); 2. x↓(y↔z), (x↓y)↔(x↓z); 3. (⌐(x↓y)→⌐z)↔y; 4. f(0,0,0)=f(0,1,0)=f(1,1,1)=0; 5. f=(1100 0101 0011 0011); 6. J={xy, x→⌐y}. |
Вариант 15: 1. (x↓y)│(yV⌐x), (x↔⌐y)+(z→⌐(xy)); 2. x│(y+z), (x│y)+(x│z); 3. ⌐(((x↓y)→⌐z)↔y); 4. f(0,0,0)=f(0,0,1)=f(1,0,0)=f(1,1,0)=1; 5. f=(0010 0111 1010 1101); 6. J={xVy, ⌐x↔y}. |
Вариант 16: 1. (x│y)→(y+⌐x), (x⌐y)V(z↔⌐(x↓y)); 2. x→(y│z), (x→y)│(x→z); 3. (⌐(x↓y)→⌐z)+y; 4. f(1,0,1)=f(0,1,1)=f(0,1,0)=0; 5. f=(0011 1111 0011 1100); 6. J={x+y, xV⌐y}. |
Вариант 17: 1. (xVy)→(y↓⌐x), (x│⌐y)↔(z+⌐(xy)); 2. x→(y↔z), (x→y)↔(x→z); 3. ⌐((xVy)→(⌐z↔y)); 4. f(1,0,0)=f(0,1,1)=f(0,1,0)=0; 5. f=(0101 0011 1100 0011); 6. J={x⌐y, ⌐x→⌐y}. |
Вариант 18: 1. (xVy)↓(y→⌐x), (x+⌐y)→(z│⌐(xy)); 2. xV(y+z), (xVy)+(xVz); 3. ⌐((x│y)+(⌐z→y)); 4. f(0,0,1)=f(0,1,1)=f(1,0,0)=f(1,0,1)=1; 5. f=(0111 1101 0010 1010); 6. J={x↓⌐y, ⌐x↔⌐y}.
|
Вариант 19: 1. (x+y)│(y↓⌐x), (x↔⌐y)→(zV⌐(xy)); 2. x↓(y+z), (x↓y)+(x↓z); 3. ⌐(((x↓y)→z)↔x); 4. f(1,0,0)=f(0,0,1)=f(0,1,1)=0; 5. f=(1111 1100 0011 0011); 6. J={x+⌐y, xVy}. |
Вариант 20: 1. xy↔(y↓⌐x), (x→⌐y)│(z+⌐(xVy)); 2. x↔(y+z), (x↔y)+(x↔z); 3. (⌐xVy)→⌐(⌐z↔y); 4. f(0,0,1)=f(0,1,1)=f(1,1,0)=0; 5. f=(0011 0011 0101 1100); 6. J={x→y, ⌐xy}.
|
Вариант 21: 1. x↓(⌐y+(y→⌐x)), xV(⌐y│⌐z+⌐(xy)); 2. x→(y↓z), (x→y)↓(x→z); 3. ⌐(((x↔y)│⌐z)+y); 4. f(0,0,0)=f(0,0,1)=f(1,0,0)=f(1,1,0)=0; 5. f=(1110 1001 0111 0001); 6. J={⌐x↓y, ⌐x↔⌐y}.
|
Вариант 22: 1. x│(⌐y+(yVx)), x→(⌐y↓(⌐z↔⌐(xy))); 2. x↓(y│z), (x↓y)│(x↓z); 3. ⌐(x↓y)→(z↔⌐y); 4. f(0,1,1)=f(1,0,0)=f(1,0,1)=1; 5. f=(0001 0011 1100 1110); 6. J={⌐x+⌐y, ⌐xVy}. |
Вариант 23: 1. x+(⌐y→(y↔⌐x)), x↓(⌐y│(zV⌐(xy))); 2. x↔(y│z), (x↔y)│(x↔z); 3. ⌐(((x↓y)→⌐z)↔y); 4. f(0,0,1)=f(1,0,0)=f(1,1,0)=1; 5. f=(0011 1100 0011 0101); 6. J={⌐x⌐y, ⌐x→y}. |
Вариант 24: 1. x↔(y(⌐y→x)), xV(⌐y+(z↓⌐(x│y))); 2. x→(y↓z), (x→y)↓(x→z); 3. (⌐(x↔y)→⌐z)│y; 4. f(0,1,1)=f(0,1,0)=f(1,0,1)=f(1,1,1)=1; 5. f=(0011 1101 0010 1100); 6. J={xV⌐y, ⌐x↔y}. |