Определение монотонности

Предмет: Математическая логика

Раздел: Логические функции и их свойства

Определение монотонности

Логическая функция \( f(x_1, x_2, \dots, x_n) \) называется монотонной, если для любых наборов значений \( X = (x_1, x_2, \dots, x_n) \) и \( Y = (y_1, y_2, \dots, y_n) \), таких что \( x_i \leq y_i \) для всех \( i \), выполняется: \[ f(X) \leq f(Y). \]

Простыми словами, это означает, что при увеличении хотя бы одного аргумента значение функции не становится меньше.

Критерий монотонной функции

Функция не является монотонной, если в её аналитическом выражении содержится отрицание переменной (например, \( \neg x \)).

Теперь выполним проверку для каждой функции.

Задание

а) (((x \lor y) \land \neg x) \rightarrow y)

Разберём выражение по шагам:

1. \( x \lor y \) — дизъюнкция \( x \) и \( y \).
2. \( \neg x \) — отрицание \( x \).
3. \( (x \lor y) \land \neg x \) — конъюнкция результата с отрицанием \( x \).
4. \( ((x \lor y) \land \neg x) \rightarrow y \) — импликация, где левая часть \( ((x \lor y) \land \neg x) \) и имплицирует на \( y \).

Проверка по критерию монотонности:

• В выражении присутствует отрицание \( \neg x \), что является признаком не монотонности функции.

Таким образом, выражение не является монотонной функцией по критерию.

Проверка по определению монотонности:

Составим таблицу истинности:

Из таблицы видно, что функция хоть и принимает постоянные значения 1 при всех наборах, её структура содержит отрицание переменной, что подтверждает, что функция не монотонна.

б) \( \neg (x \lor y) \land \neg (x \lor y \land z) \)

Разберём выражение по шагам:

1. \( x \lor y \) — дизъюнкция \( x \) и \( y \).
2. \( \neg (x \lor y) \) — отрицание дизъюнкции \( x \) и \( y \).
3. \( y \land z \) — конъюнкция \( y \) и \( z \).
4. \( x \lor (y \land z) \) — дизъюнкция \( x \) и \( (y \land z) \).
5. \( \neg (x \lor (y \land z)) \) — отрицание результата второй дизъюнкции.
6. \( \neg (x \lor y) \land \neg (x \lor (y \land z)) \) — конечная конъюнкция двух отрицаний.

Проверка по критерию монотонности:

• В выражении присутствуют отрицания \( \neg (x \lor y) \) и \( \neg (x \lor (y \land z)) \), что также является признаком не монотонности.

Таким образом, выражение не является монотонной функцией по критерию.

Проверка по определению монотонности:

Составим таблицу истинности:

Ответ:

• а) Логическая функция \( ((x \lor y) \land \neg x) \rightarrow y \) не является монотонной.
• б) Логическая функция \( \neg (x \lor y) \land \neg (x \lor (y \land z)) \) не является монотонной.

Из таблицы видно, что отрицания присутствуют, что также подтверждает отсутствие монотонности в функции.