Изучение функций в курсе математики
f =
2
4
1
3
1
2
3
4
Строим матрицу покрытий:
| № | Простые импликанты | Конституенты единицы функции f | ||||||||||
|
x1 |
x2 |
x3 |
x4 |
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 |
x3 |
|
| 1, 4 |
x1 |
|
| 2, 5 |
x1 |
|
| 4, 5 |
x3 |
|
| 4, 6 |
х4 |
|
| 5, 6 |
х4 |
|
| 5, 7 |
х2 |
|
| 6, 8 |
х2 |
|
| 7, 8 |
х4 |
|
С результатами таблицы повторим операцию склеивания.
1)
![]()
2)
![]()
3)
![]()
4)![]()
5)![]()
6)![]()
7)![]()
8)![]()
9)![]()
| Слагаемые | Склеивание по переменной | Результат склеивания |
| 1, 4 |
x1 |
|
| 2, 3 |
x3 |
|
| 6, 9 |
х2 |
|
| 7, 8 |
х4 |
|
В итоге получим:
f =
1
3
2
4
1
2
3
4
4. Построим таблицу значений функции
|
х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 |
f(0,0,0,0)≠0
0f(1,1,1,1)=1
1f(0,0,0,0)=f(1,1,1,1)≠0

Поскольку набор (1,1,1,1) больше любого другого набора и f(0,0,1,0)=1, f(0,0,1,1)=0, то

Для того чтобы выяснить, является ли функция линейной построим многочлен Жегалкина (с помощью треугольника Паскаля)
| слагаемое |
х1 |
х2 |
х3 |
х4 |
f |
D Паскаля |
| 1 | 0 | 0 | 0 | 0 | 0 | f=1010010010110011 |
|
х4 |
0 | 0 | 0 | 1 | 0 | 111011011101010 |
|
х3 |
0 | 0 | 1 | 0 | 1 | 00110110011111 |
|
х3 х4 |
0 | 0 | 1 | 1 | 1 | 0101101010000 |
|
х2 |
0 | 1 | 0 | 0 | 0 | 111011111000 |
|
х2 х4 |
0 | 1 | 0 | 1 | 1 | 00110000100 |
|
х2 х3 |
0 | 1 | 1 | 0 | 0 | 0101000110 |
|
х2 х3 х4 |
0 | 1 | 1 | 1 | 1 | 111100101 |
|
х1 |
1 | 0 | 0 | 0 | 1 | 00010111 |
|
х1 х4 |
1 | 0 | 0 | 1 | 1 | 0010100 |
|
х1 х3 |
1 | 0 | 1 | 0 | 0 | 011110 |
|
х1 х3 х4 |
1 | 0 | 1 | 1 | 0 | 11111 |
|
х1 х2 |
1 | 1 | 0 | 0 | 1 | 0000 |
|
х1 х2 х4 |
1 | 1 | 0 | 1 | 0 | 000 |
|
х1 х2 х3 |
1 | 1 | 1 | 0 | 1 | 00 |
|
х1 х2 х3 х4 |
1 | 1 | 1 | 1 | 0 | 0 |
Полином Жегалкина имеет вид:
1+x4+x2+x2x3x4+x1x3x4,
f![]()
|
T0 |
T1 |
S | L | M | |
| f | - | + | - | - | - |
Задание 6. Разбить высказывание на элементарные и записать в виде кванторной формулы логики предикатов, используя наименьшее возможное число предикатов наименьшей местности
Через всякую точку, не лежащую на прямой, можно провести не более одной прямой, параллельной данной.
Решение
1. Введем обозначения:
P(x, y): «точка y принадлежит прямой x»
Q(x, y): «x // y»
Исходное выражение можно записать в виде следующей формулы:
![]()
![]()
2. Сначала приведем формулу к приведенной нормальной форме, т. е. избавимся от знака импликации, используя равносильности логики высказываний и логики предикатов:
![]()
Для приведения к предваренной нормальной форме необходимо вынести все кванторы в начало формулы (используя равносильности логики предикатов):
![]()
Задание 7. Построить интерпретацию формулы логики предикатов:
![]()
Решение
Данная формула является открытой (первое вхождение переменной у не связано квантором) и формула содержит нульместный предикат (S). Значит, интерпретация будет состоять из четырех шагов.
Зададим множество, на котором будем рассматривать все предикаты: М=R, где R – множество действительных чисел.
Каждой предикатной букве ставим в соответствие предикат:
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). В результате
получили
высказывание,
которое можно
записать:
![]()
Значит, данная интерпретация обращает формулу логики предикатов в истинное высказывание.