Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 11 стр.

UptoLike

Составители: 

Таким образом, минимальное значение переменной z, обращающее предикат в "истину",
дает значение функции в точке (1, 5), и оно равно 4.
2.5.3. Использование ограниченного оператора минимизации
Ограниченный оператор минимизации является удобным средством для построения
обратных функций.
Пример 1. C помощью ограниченного оператора минимизации определить функцию y(x,
z) =
x
z
- "целая часть от деления z на x" - как функцию, обратную умножению.
Решение.
z / x = y, тогда y x = z,
z / x < y + 1, поэтому z < x(y + 1).
С использованием ограниченного оператора минимизации запишем исходную функцию
через обратную:
y(x, z) =
x
z
= µ
z y
(P(x, y, z)),
предикат P(x, y, z) = z < x(y + 1).
Тогда
x
z
= µ
z y
(z < x( y+1)).
Вычислим значение функции при z = 11, x = 2.
При y = 0: P(2, 11, 0) = 2(0+1) < 11 - "ложь",
y = 1: P(2, 11, 1) = 2(1+1) < 11 - "ложь",
. . .
y = 5: P(2, 11, 5) = 2(5+1) > 11 - "истина".
Следовательно,
x
z
= 5.
Пример 2. С помощью ограниченного оператора минимизации определить функцию
[
]
x)x(f =
- "целая часть от корня из х".
Решение.
Пусть
[
]
x
= z. Тогда
x
< z +1, а предикат P равен:
P(x, z) = x < (z + 1)
2
.
С использованием ограниченного оператора минимизации запишем исходную функцию
через обратную:
[
]
x
= µ
z x
(x < (z +1)
2
).
Вычислим значение функции при x = 17.
При z = 0: P(17, 0) = 17 < 1 - "ложь",
z = 1: P(17, 1) = 17 < 4 - "ложь",
. . .
z = 4: P(17, 4) = 17 < 25 - "истина".
Следовательно,
[
]
x
= 4, что и требовалось доказать.
Пример 3. С помощью ограниченного оператора минимизации определить функцию f(x,
y) =
[
]
xlog
y
- "целая часть от log
y
x".
Решение.
Пусть y
z
= x. Тогда y
z+1
> x.
С использованием ограниченного оператора минимизации запишем исходную функцию
как:
[
]
xlog
y
= µ
z < x
(y
z+1
> x).