[ Вивчення функцій в курсі математики ] | 1 | 0 | 0 | 0 | 0 | |||||
5 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
6 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Стовпці, відповідні F 1 і F 2, збігаються. Це означає, що аналітичні перетворення початкової формули вірні.
Завдання 4. Нижче наведена Клауза
Необхідно з'ясувати за допомогою алгоритму Вонга і методу резолюції є Клауза теоремою.
Рішення
Метод Вонга.
Побудуємо дерево докази.
Усі гілки дерева закінчуються Клаузена, в яких по обидва боки символу присутня одна і та ж буква. Отже, логічна теорема вірна.
Метод резолюція.
Необхідно перетворити клауз таким чином, щоб після знака вийшов нуль, при цьому позбудемося імплікації.
Ǿ
Випишемо по порядку всі посилки і далі почнемо їх «склеювати».
1 |
| 7 | (2, 3) А | ||||||||||||||||||||||||||||||||||
2 |
| 8
Інакше, порядок «склеювання» можна представити у вигляді ланцюжка рівносильних перетворень:
Завдання 5. Задані номера наборів аргументів, на яких булева функція приймає значення, рівне одиниці. Необхідно:
f (x 1, x 2, x 3, x 4) = 1010010010110011 Рішення
СДНФ (1): № 0,2,5,8,10,11,14,15 f = 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 СКНФ (0): № 1,3,4,6,7,9,12,13 f = ( 1 2 3 4) ( 1 2 3 4) ( 1 2 3 4) ( 1 2 3 4) ( 1 2 3 4) ( 1 2 3 4) ( 1 2 3 4) ( 1 2 3 4)
Шаг1.
| x 2 | x 3 | x 4 | x 1 x 2 | x 1 x 3 | x 1 x 4 | x 2 x 3 | x 2 x 4 | x 3 x 4 | x 1 x 2 x 3 | x 1 x 2 x 4 | x 1 x 3 x 4 | x 2 x 3 x 4 | x 1 x 2 x 3 x 4 | f | ||||||||||||||||||||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | |||||||||||||||||||||
1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | |||||||||||||||||||||
2 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 2 | 1 | 0 | 2 | 2 | 2 | 1 | |||||||||||||||||||||
3 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 3 | 1 | 1 | 3 | 3 | 3 | 0 | |||||||||||||||||||||
4 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 2 | 2 | 0 | 2 | 2 | 0 | 4 | 4 | 0 | |||||||||||||||||||||
5 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 5 | 5 | 1 | |||||||||||||||||||||
6 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 3 | 2 | 2 | 3 | 2 | 2 | 6 | 6 | 0 | |||||||||||||||||||||
7 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 7 | 7 | 0 | |||||||||||||||||||||
8 | 1 | 0 | 0 | 0 | 2 | 2 | 2 | 0 | 0 | 0 | 4 | 4 | 4 | 0 | 8 | 1 | |||||||||||||||||||||
9 | 1 | 0 | 0 | 1 | 2 | 2 | 3 | 0 | 1 | 1 | 4 | 5 | 5 | 1 | 9 | 0 | |||||||||||||||||||||
10 | 1 | 0 | 1 | 0 | 2 | 3 | 2 | 1 | 0 | 2 | 5 | 4 | 6 | 2 | 10 | 1 | |||||||||||||||||||||
11 | 1 | 0 | 1 | 1 | 2 | 3 | 3 | 1 | 1 | 3 | 5 | 5 | 7 | 3 | 11 | 1 | |||||||||||||||||||||
12 | 1 | 1 | 0 | 0 | 3 | 2 | 2 | 2 | 2 | 0 | 6 | 6 | 4 | 4 | 12 | 0 | |||||||||||||||||||||
13 | 1 | 1 | 0 | 1 | 3 | 2 | 3 | 2 | 3 | 1 | 6 | 7 | 5 | 5 | 13 | 0 | |||||||||||||||||||||
14 | 1 | 1 | 1 | 0 | 3 | 3 | 2 | 3 | 2 | 2 | 7 | 6 | 6 | 6 | 14 | 1 | |||||||||||||||||||||
15 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 7 | 7 | 7 | 7 | 15 | 1 |
Крок 2. Викреслюємо рядки, в яких функція звертається в нуль.
Крок 3. У кожному стовпці зі збережених чисел викреслюємо ті, рівні яким вже викреслені в цьому стовпці на попередньому кроці.
Крок 4. У збережених рядках вибираємо «значення» найменших за кількістю множників кон'юнкція (включаючи і кон'юнкції з одним множником - змінні) і обводимо їх.
Крок 5. Якщо в одному стовпці обведено кілька однакових чисел, то викреслюємо все, крім одного.
Результуюча таблиця має вигляд:
№ | x 1 | x 2 | x 3 | x 4 | x 1 x 2 | x 1 x 3 | x 1 x 4 | x 2 x 3 | x 2 x 4 | x 3 x 4 | x 1 x 2 x 3 | x 1 x 2 x 4 | x 1 x 3 x 4 | x 2 x 3 x 4 | x 1 x 2 x 3 x 4 | f |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
2 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 2 | 1 | 0 | 2 | 2 | 2 | 1 |
3 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 3 | 1 | 1 | 3 | 3 | 3 | 0 |
4 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 2 | 2 | 0 | 2 | 2 | 0 | 4 | 4 | 0 |
5 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 5 | 5 | 1 |
6 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 3 | 2 | 2 | 3 | 2 | 2 | 6 | 6 | 0 |
7 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 7 | 7 | 0 |
8 | 1 | 0 | 0 | 0 | 2 | 2 | 2 | 0 | 0 | 0 | 4 | 4 | 4 | 0 | 8 | 1 |
9 | 1 | 0 | 0 | 1 | 2 | 2 | 3 | 0 | 1 | 1 | 4 | 5 | 5 | 1 | 9 | 0 |
10 | 1 | 0 | 1 | 0 | 2 | 3 | 2 | 1 | 0 | 2 | 5 | 4 | 6 | 2 | 10 | 1 |
11 | 1 | 0 | 1 | 1 | 2 | 3 | 3 | 1 | 1 | 3 | 5 | 5 | 7 | 3 | 11 | 1 |
12 | 1 | 1 | 0 | 0 | 3 | 2 | 2 | 2 | 2 | 0 | 6 | 6 | 4 | 4 | 12 | 0 |
13 | 1 | 1 | 0 | 1 | 3 | 2 | 3 | 2 | 3 | 1 | 6 | 7 | 5 | 5 | 13 | 0 |
14 | 1 | 1 | 1 | 0 | 3 | 3 | 2 | 3 | 2 | 2 | 7 | 6 | 6 | 6 | 14 | 1 |
15 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 7 | 7 | 7 | 7 | 15 | 1 |
f = 2 4 1 3 1 2 3 4
Будуємо матрицю покриттів:
№ | Прості імпліканти | Констітуенти одиниці функції f | ||||||||||
x 1 | x 2 | x 3 | x 4 | 0000 | 0010 | 0101 | 1000 | 1010 | 1011 | 1110 | 1111 | |
1 | - | 0 | - | 0 | 1 | 1 | 1 | 1 | ||||
2 | 1 | - | 1 | - | 1 | 1 | 1 | 1 | ||||
3 | 0 | 1 | 0 | 1 | 1 |
Послідовно вибираємо складові 1,2,5
В результаті отримуємо МДНФ:
f = 1 3 2 4 1 2 3 4
3. Побудуємо алгоритм Куайна.
Побудуємо таблицю значень функції
х 1 | х 2 | х 3 | х 4 | f | |
0 | 0 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 0 | 1 | 0 |
2 | 0 | 0 | 1 | 0 | 1 |
3 | 0 | 0 | 1 | 1 | 0 |
4 | 0 | 1 | 0 | 0 | 0 |
5 | 0 | 1 | 0 | 1 | 1 |
6 | 0 | 1 | 1 | 0 | 0 |
7 | 0 | 1 | 1 | 1 | 0 |
8 | 1 | 0 | 0 | 0 | 1 |
9 | 1 | 0 | 0 | 1 | 0 |
10 | 1 | 0 | 1 | 0 | 1 |
11 | 1 | 0 | 1 | 1 | 1 |
12 | 1 | 1 | 0 | 0 | 0 |
13 | 1 | 1 | 0 | 1 | 0 |
14 | 1 | 1 | 1 | 0 | 1 |
15 | 1 | 1 | 1 | 1 | 1 |
СДНФ (1): № 0, 2, 5, 8, 10, 11, 14, 15
1)
2)
3)
4)
5)
6)
7)
8)
Складові | Склеювання по змінній | Результат склеювання | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1, 2 | x 3 |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1, 4 | x 1 |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2, 5 | x 1 |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4, 5 | x 3 |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4, 6 | х 4 |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5, 6 | х 4 |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5, 7 | х 2 |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
6, 8
З результатами таблиці повторимо операцію склеювання. 1) 2) 3) 4) 5) 6) 7) 8) 9)
В результаті отримаємо: f = 1 3 2 4 1 2 3 4 4. Побудуємо таблицю значень функції
Для того щоб з'ясувати, чи є функція лінійної побудуємо многочлен Жегалкина (за допомогою трикутника Паскаля)
Поліном Жегалкина має вигляд: 1 + x 4 + x 2 + x 2 x 3 x 4 + x 1 x 3 x 4, f
Завдання 6. Розбити висловлювання на елементарні і записати у вигляді кванторное формули логіки предикатів, використовуючи найменшу можливу кількість предикатів найменшою місцевості Через всяку точку, не лежить на прямій, можна провести не більше однієї прямої, паралельної даній. Рішення 1. Введемо позначення: P (x, y): «точка y належить прямий x» Q (x, y): «x / / y» Початкове вираз можна записати у вигляді такої формули:
2. Спочатку наведемо формулу до наведеної нормальній формі, тобто позбудемося знака імплікації, використовуючи равносильности логіки висловлювань і логіки предикатів:
Для приведення до упереджені нормальній формі необхідно винести всі квантори в початок формули (використовуючи равносильности логіки предикатів):
Завдання 7. Побудувати інтерпретацію формули логіки предикатів:
Рішення Дана формула є відкритою (перше входження змінної у не пов'язано квантором) і формула містить нульместний предикат (S). Значить, інтерпретація буде складатися з чотирьох кроків.
P (x, y): "x> y"; R (x, y, z): "xy = z", S (z): "z = 1"; При даній інтерпретації висловлювання є хибним (читається: для будь-яких дійсних чисел x і y, x> y), - Істинне висловлювання (читається: існують такі дійсні числа x, y, z, що xy = z), - Істинне висловлювання (читається: існує таке дійсне число z, що z = 1). В результаті отримали висловлювання, яке можна записати:
Значить, дана інтерпретація звертає формулу логіки предикатів в істинне висловлення. Будь ласка, не зберігайте тестовий текст. |