Дискретно-непрерывная математика (стр. 86 )

Определение 1.4. ДНФ в БЛ над множеством называется дизъюнкция БЛ любого конечного множества попарно различных эле­ментарных конъюнкций БЛ над а. Аналогично, КНФ над множеством а на­зывается конъюнкция БЛ любого конечного множества попарно различных элементарных дизъюнкций БЛ над а.

Теорема 1.1. Произвольная функция БЛ сформирован-

ная с помощью только операций дизъюнкции, конъюнкции и отрицания БЛ, может быть представлена: 1) в эквивалентной ДНФ над множеством а = ; 2) в эквивалентной КНФ над тем же множеством.

Доказательство конструктивно и может быть проведено подоб­но соответствующему для булевых функций. Докажем только 1), а 2) до­казывается аналогично. На 1-м шаге при помощи формул де Моргана (1.13) и закона двойного отрицания (1.15) производим "спуск отрицаний" на сами аргументы аі, т. е. F придается вид выражения, построенного из бyкв и их отрицаний с помощью только конъюнкции и дизъюнкции БЛ, что, очевидно, всегда возможно. Если в результате 1-го шага полу­чилось выражение F, не содержащее дизъюнкций, то оно является элементарной конъюнкцией, так что приведение F к ДНФ окончено. В противном глуше переходим ко 2-му шагу, состоящему в следующем.

Пусть в результате 1-го шага получилось выражение (т. е. последняя операция в выражении F — конъюнкция); тогда часть из Fі — элементарные конъюнкции, а другая часть (обязательно непустая) — дизъюнкция. Раскрыв на основе распределительного закона все скобки, содержащие дизъюнкции, и выполнив в получившихся конъюнктивных членах необходимые упрощения, приведем выражение F к форме дизъюнк­ции, каждый конъюнктивный член которой содержит меньше операций дизъюнкции, чем исходная форма После этого та же процедура проделывается с каждым конъюнктивным членом и т. д. Оканчи­вается 2-й шаг тогда, когда выражение F получает форму дизъюнкции, каждый конъюнктивный член которой уже не содержит собственных опе­раций дизъюнкции, т. е. является элементарной конъюнкцией. Если же в результате 1-го шага получилось выражение (т. е. последняя операция в выражении F — дизъюнкция), то приведение F к ДНФ сводится к уже решенной задаче приведения к ДНФ функций Fі, в выражениях которых последней операцией является конъюнкция.

Для представления произвольной функции БЛ в ДНФ или КНФ удобно исходить из аналитического задания этой функции. Алгоритм перехода от такой формы представления функции к ее ДНФ состоит в поочередном вы­полнении двух операций: 1) спуск отрицаний с более сложных выражений на менее сложные в соответствии с законами де Моргана (1.13) и двойного отрицания (1.15); 2) раскрытие скобок в соответствии с распределитель­ным законом (1.12). Алгоритм перехода от аналитической формы записи функций БЛ к ее КНФ состоит в поочередном выполнении двух операций: 1) спуск отрицаний с более сложных выражении на менее сложные соглас­ии законам де Моргана (1.13) и двойного отрицания (1.15); 2) введение скобок согласно распределительному закону (1.12).

Пример 1.2. Привести к ДНФ функцию БЛ

По формуле де Моргана раскрыв скобки согласно распределительному закону, находим

Пример 1.3. Привести к КНФ функцию F из примера 1.2. Применив дважды распределительный закон к скобке и подставив найденное в примере 1.2 выражение получим

1.5. Обыкновенные уравнения и неравенства в бесконечнозначной логике

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

Определение 1.5. Обыкновенным уравнением БЛ называется уравнение вида

(1.62)

где F и L — заданные функции БЛ (вообще говоря, различные), -известные, а - неизвестные (искомые) аргументы, лежащие в заданном замкнутом и ограниченном интервале С = [А, В] множества всех вещественных чисел. Частным решением этого уравнения называется любой набор для которого равенство (1.62) справедливо.

Совокупность всех частных решений называется общим решением.

Примечание 1.1. Для дальнейшего нам достаточно ограничиться таким классом функций БЛ (F, L), в котором любая функция выра­жается аналитически суперпозицией трех операций БЛ, введенных выше — дизъюнкции, конъюнкции и отрицания. Из этих операций лишь одна (отри­цание) существенно нуждается в том, чтобы оперируемый аргумент принад­лежал ограниченному интервалу. Для двух других операций аргументы мо­гут принимать любые значения из множества всех вещественных чисел. Поэтому в случае неиспользования в F и L операции отрицания определе­ние 1.5 можно расширить, приняв

Определение 1.6. Неравенством БЛ называется неравенство вида

(1.63)

где удовлетворяют определению 1.5 и примечанию 1.1. Решение этого неравенства определяется аналогично решению уравнения (1.62).

Определение 1.7. Системой обыкновенных уравнений и неравенств БЛ называется совокупность рассматриваемых совместно конечного мно­жества уравнений вида (1.62) и конечного множества неравенств вида (1.63) (одно из двух множеств может быть пустым). Уравнения и неравенства БЛ удобно записывать в терминах векторов параметров и векторов неизвестных

Перейдем к классификации обыкновенных уравнений и неравенств БЛ.

Прежде всего, уравнение (1.62) может быть с одним неизвестным

(п = 1) или с несколькими Более подробная классификация проводится с использованием ДНФ функций, стоящих в левой и правой частях урав­нения. Это использование позволяет, объединив элементарные конъюнкции, содержащие одно и то же подмножество множества неизвестных, представить уравнение (1.62) в следующей канонической форме:

(1.64)

где коэффициенты a, d, с, е — элементарные конъюнкции параметров Здесь дизъюнкции, заключенные в скобки, берутся по всем наборам индексови т. д., в которых любые два индекса і, j не могут быть равными, когда соответствующие им неизвестные xі, хj входят оба без отрицания или оба с отрицанием. Если же хі входит с отрицанием, a хj без него (или наоборот), то в число наборов индексов, по которым берутся дизъюнкции, входят и все наборы с і= j.

Из (1.64) сразу получаем общий вид уравнения с одним неизвестным

(1.65)

Определение 1.8. Порядком I обыкновенного уравнения БЛ называется максимальное число различных неизвестных и их отрицаний, содержащихся в одной элементарной конъюнкции формы (1.64) этого уравнения.

Так, для полного уравнения с п неизвестными, согласно (1.64), І= 2п, в частности І=2 для полного уравнения с одним неизвестным (1.65). Уравнения с І = 1 назовем линейными, а с — нелинейными. Общий вид линейного уравнения с п неизвестными получается из (1.64)

(1.66)

Отсюда линейное уравнение с одним неизвестным может быть представлено в общем виде следующим образом:

(1.67)

Обыкновенные уравнения БЛ можно также разделить на уравнения с отрицаниями и без отрицаний неизвестных. Первый тип уравнения может быть представлен в общем виде (1.64), а второй —в следующем, вытекаю­щем из (1.64)

(1.68)

В частности, в случае одного неизвестного первый тип уравнения имеет общее представление (1.65), а второй тип — линейное представление

(1.69)

Oтметим, что при изучении большинства систем уравнения с отрицаниями неизвестых не появляются.

Неравенства БЛ классифицируются точно так же, как и уравнения. Что касается систем уравнений и неравенств, то отнесение к тому или иному классу производится в соответствии с типами входящих в них уравнений и неравенств. При этом за основу берется наиболее сложный тип уравнения (неравенства). Так, система из двух линейных и одного нелинейного уравне­ния считается нелинейной; система из двух уравнений с отрицаниями неиз­вестных и двух - без отрицаний считается системой уравнений с отрицания­ми неизвестных и т. д.