Какие у Вас корни? Часть 1

Решение уравнений является одной из основных задач, рассматриваемых в школьном курсе математики. В алгебре, тригонометрии рассматриваются алгебраические и тригонометрические функции, аргументы которых являются вещественными числами, и сами функции принимают вещественные значения. Основным предметом изучения в школе являются функции F(x) от одной переменной. В области вещественных чисел таких функций бесконечно много, в отличие от логических функций от одной переменной, пересчитать которые достаточно пальцев одной руки, а интерес представляет только одна функция – отрицание.

Как связаны функции и уравнения?

Пусть F(x) – вещественная функция с вещественным аргументом. Если она задана, то можно, например, построить график этой функции y = F(x), вычисляя значение функции y для заданных значений аргументов.

Уравнением называют запись:

F(x) = a,

Где а – некоторое число.

Решить уравнение означает найти такое значение x*, при котором уравнение превращается в тождество, другими словами, функция F, вычисленная в точке x*, имеет значение a: F(x*) = a.

Уравнение может не иметь корней, может иметь один или несколько корней. Если a равняется нулю, то корнями являются те значения x, в которых функция обращается в нуль, то есть точки, в которых график функции пересекается с осью абсцисс.

Уравнение:

F(x) = a

Всегда можно привести к каноническому виду, перенеся значение а в левую часть уравнения:

Ф(x) = 0

Если рассматривать одно уравнение от нескольких переменных:

F(x1, x2, …xk) = 0,

То заниматься поиском корней обычно не имеет смысла, поскольку в общем случае их бесконечно много. Можно конечно, зафиксировать значения всех аргументов, кроме одного, прийти к уравнению с одной переменной и искать его корни.

Поиск корней становится осмысленным, когда мы имеем дело с системой уравнений.

Как меняется ситуация, когда речь идет о логических функциях?

Рассмотрим уравнение:

F(x) = a

Пусть F – логическая функция, а x – логическая переменная. Прежде всего, заметим, что параметр a может принимать только 2 значения – 0 или 1, поскольку логическая функция имеет только эти два возможных значения.

Рассматривать уравнение с одним неизвестным для логических функций не имеет смысла, поскольку, как уже говорилось, их всего-то четыре, все они элементарны, о них все известно.

Но зато для логических функций становится осмысленным решение уравнения:

F(x1, x2, …xk) = a

Осмысленно потому, что область определения такой функции содержит конечное число элементов, каждый из которых можно рассматривать как кортеж из k значений аргументов, как слово длины k в двоичном алфавите. На некоторых кортежах функция принимает значение 0, на других – 1.

Что значит найти решение такого уравнения? Решением являются те наборы аргументов из таблицы истинности функции F, на которых функция принимает значение a – 0 или 1.

Канонической записью логического уравнения является запись:

F(x1, x2, …xk) = 1,

Решением являются те кортежи аргументов, на которых функция принимает значение 1 (Истина).

Уравнение, записанное в дополняющей форме:

F(x1, x2, …xk) = 0,

всегда можно привести к каноническому виду, применив операцию отрицания:

F(x1, x2, …xk) = 0

эквивалентно уравнению:

!F(x1, x2, …xk) = 1

Под корнем уравнения будем понимать тот набор аргументов, тот кортеж, на котором функция принимает истинностное значение, - значение 1.

Рассмотрим уравнение с k переменными:

F(x1, x2, …xk) = 1

Число всех возможных наборов равно 2k. Пусть F имеет n корней, то есть принимает значение 1 на n наборах. Тогда остальные наборы, на которых функция равна 0, являются корнями уравнения:

F(x1, x2, …xk) = 0

Число корней этого уравнения равно m = 2k – n.

Задача решения уравнения сводится, по сути, к построению таблицы истинности функции F. Имея таблицу истинности нетрудно сказать, сколько корней уравнения и какие это корни.

Рассмотрим пример:

Задача. Найти число корней и сами корни уравнения:

X1 | X2 X3 ∧ !X1 ⇒ X2 ≡ !X1 | X2 X3 = 1

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

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

! – отрицание;

- конъюнкцию;

| - дизъюнкцию;

∧ - исключающее или;

⇒ - импликацию;

≡ - тождество.

Определение этих операций, надеюсь, известно. При вычислении значения функции, заданной формулой следует следить за порядком выполнения операций, определяемого приоритетом операций. В приведенном выше списке операции следуют в соответствии с их приоритетом. Две операции "Или" - дизъюнкция и исключающее или имеют одинаковый приоритет и выполняются в порядке их следования.

С помощью скобок можно менять порядок выполнения операций, поскольку выражение в скобках имеет самый высокий приоритет.

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

(((X1 | (X2 X3)) ∧ (!X1 ))⇒; X2 )≡ ((!X1) | (X2 X3))

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

Приведу таблицу истинности для функции от трех переменных, заданной нашей формулой. Она определена на восьми наборах. Вот ее вид:

Анализируя нашу таблицу, мы видим, что наше уравнение имеет 5 решений – 5 корней. Первое решение задается набором (0 1 0). Так как наборы можно интерпретировать как числа от 0 до 2n – 1, записанные в двоичной системе, то все решения можно упорядочить в соответствии с числовым значением набора. Можно считать, что первый корень соответствует набору с числовым значением – 2, последний корень имеет числовое значение – 7. Можно задать все 5 корней как числа – 2, 3, 4, 5, 7. Числа – 0, 1, 6 являются корнями уравнения F(X1, X2, X3) = 0, где F – функция, заданная нашей формулой.

Таков один из возможных способов решения логического уравнения с n переменными. Он хорошо работает, когда n сравнительно мало. Уже при n > 5 утомительно строить таблицу истинности из-за быстрого роста числа строк этой таблицы с ростом n. Правда, можно написать программу, как это сделал я, которая сама будет строить эту таблицу.