Для самостійної роботи
Критерії оцінювання: Кожне завдання – 4 бали. Максимальна кількість балів – 12.
Завдання 1. Визначити значення функції:
Варіант |
1 |
2 |
3 |
4 |
5 |
6 |
А) |
0(0) |
3(1) |
2(0) |
1(0) |
0(1) |
2(1) |
Б) |
10(1,0) |
13(0,0) |
11(0,1) |
9(1,1) |
14(0,1) |
7(0,0) |
Завдання 2. Скласти таблицю істинності функції:
Варіант |
1 |
2 |
3 |
4 |
5 |
6 |
n(x, y) |
ху |
ху |
ху |
ху |
x | y |
ху |
Завдання 3. Визначити значення логічного виразу:
Варіант |
1 |
2 |
3 |
4 |
5 |
6 |
А) |
11 |
01 |
00 |
10 |
11 |
01 |
Б) |
10 |
10 |
1 | 0 |
01 |
11 |
00 |
Самостійна робота № 9
Тема: Складання таблиць істинності до булевих функцій
Мета: Закріпити набуті знання та навички, перевірити їх при виконанні практичних завдань.
Завдання
Засвоїти теоретичний матеріал згідно теми;
Дати відповіді на поставлені питання (лекція 12);
Виконати письмово приведені завдання;
Випишіть питання, що виникли в ході засвоєння матеріалу;
Зробіть висновки.
Рекомендована література:
М.Ф. Бондаренко, Н.В. Білоус, А.Г.Руткас. Комп’ютерна дискретна математика. – Х: „Компанія СМІТ”, 2004.-480с.
Стрыгин В.В., Щарев Л.С. Основы вычислительной микропроцессорной техники и программирования: Учеб. для вузов. – М: Высш. Шк., 1989. – 479с.
Згідно визначенню, таблиця істинності логічної формули виражає відповідність між всілякими наборами значень змінних і значеннями формули.
Для формули, яка містить дві змінні, таких наборів значень змінних всього чотири: (0,0), (0,1), (1,0), (1,1).
Якщо формула містить три змінні, то можливих наборів значень змінних (інтерпритацій) буде вісім: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1).
Кількість наборів для формули з чотирма змінними дорівнює 16 і так далі
Зручною формою запису при знаходженні значень формули є таблиця, що містить окрім значень змінних і значень формули також і значення проміжних формул.
Якщо в виразі відсутні дужки, то операції будуть виконуватись в такій послідовності: інверсія, кон’юнкція, диз’юнкція, імплікація, еквівалентність.
Складемо
таблицю істинності для формули
,
яка містить дві змінні x і y. По-перше, в
двох стовпцях таблиці запишемо чотири
можливі пари значень цих змінних, в
подальших стовпцях — значення проміжних
формул і в останньому стовпці — значення
формули. В результаті отримаємо таблицю:
|
|
|
|
|
|
|
F(x,y) |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
Формули, що зображують одну й ту ж функцію, називають еквівалентними або рівносильними.
Еквівалентність формул позначається знаком рівності. Один із способів встановити еквівалентність функцій – побудувати їх таблиці істинності, а потім порівняти рівність результатів для кожної інтерпретації.
Перевіримо еквівалентність функцій f1 = x ⊕ (y∧z), f2 = (x ⊕ y)∧ (x ⊕ z).
x |
y |
z |
y∧z |
f1 |
|
x ⊕ y |
x ⊕ z |
f2 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
При побудові таблиці істинності для аргументів будуємо всі можливі інтерпретації. Для цього вписуємо в кожен рядок інтерпретації двійкові коди натуральних чисел від 0 до 2n , де n – кількість аргументів. Для кожної операції виділяємо окремий стовпчик.
В результаті робимо висновок, результат не сходиться тільки в одній інтерпретації (0, 0, 1). Але цього досить, щоб зробити висновок: функції не еквіваленті f1 f2.