Закон двойственности

Библиографический список

1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. - М.: Энергоатомиздат, 1988. - 480 с.

2. Коршунов Ю.М. Математические основы кибернетики: Учеб. Пособие для вузов. - 3-е изд. перераб. и доп. - М.: Энергоатомиздат, 1987. - 496 с.: ил.

3. Новиков Ф.А. Дискретная математика для программистов. – Спб: Питер, 2000. – 304 с.: ил.

4. Яблонский С.В. Введение в дискретную математику: Учебное пособие для Вузов/ Под ред. В.А. Садовничего – 3-е изд. стер. – М.: Высш. шк., 2001. – 384 с.

5. Гудстейн Р.Л. Математическая логика: Пер. с англ. - М.: Издат. иностр. лит., 1961, - 162 с.

6.

8. Эдельман С.Л. Математическая логика. - М.: Высш. школа, 1975. - 176 с.

9. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Наука, 1984. - 223 с.

Рассмотрим формулы, которые содержат только операции, Λ, V. Будем говорить, что операция Λ двойственна операции V и наоборот.

Определение:

Формулы α и α* называются двойственными, если одна получается из другой заменой каждой операции на двойственную.

Из законов Д Моргана легко вывести следующее положение: если формулы α(x₁, x₂,…, x_n) и α*(x₁, x₂,…, x_n) двойственна, а x₁, x₂,…, x_n – элементарные высказывания, то α(x₁, x₂,…, x_n) равносильно α*(x₁, x₂,…, x_n).

Отсюда вытекает Закон двойственности:

Если формулы α и β равносильны, то двойственные им формулы α* и β* также равносильны.

α≡β => α*≡β*

1.4. Проблема разрешения.

Определение:

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

Определение:

Будем называть формулу выполнимой, если она принимает значение истина при некоторых значениях входящих в нее переменных высказываний.

Определение:

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

Поставим перед собой задачу: указать единый алгоритм, позволяющий для каждой формулы выяснить, является она тождественно истинной или нет? Также решается выполнимость. Возьмем, к примеру, α и решим, является ли α тождественно истинной. Если α - тождественно истинна, следовательно α – тождественно ложна, то есть невыполнимая, а если α – не является тождественно истинной, следовательно, α не тождественно ложна и значит выполнима. Поставленная задача называется проблемой разрешения, которая легко решается для алгебры высказываний.

К примеру, возьмем функцию α(x₁, x₂,…, x_n), которая, как и ее переменные x₁, x₂,…, x_n может принимать только два значения. Имеем 2ⁿ комбинаций значений переменных x₁, x₂,…, x_n. Мы можем вычислить значение функции α для каждой комбинации, подставив вместо переменных их значения, и тогда можно выяснить тождественно истинная функция или нет. Но этот способ не рационален, так как число испытаний очень велико. Существует другой способ: привидение формул к нормальной форме.

Определение:

Будем называть элементарной конъюнкцией (соответственно – элементарной дизъюнкцией) произведение (сумму) переменных и их отрицаний.

Теорема 1:

Элементарная дизъюнкция тождественно истинная тогда и только тогда когда содержит некоторые элементарные высказывание вместе с его отрицанием.

Теорема 2:

Элементарная конъюнкция тождественно ложна тогда и только тогда когда содержит некоторое элементарное высказывание вместе с его отрицанием.

Определение:

Формула, равносильная исходной формуле и представляющая собой дизъюнкцию элементарных конъюнкций, называется дизъюнктивной нормальной формой (ДНФ) исходной формулы.

Определение:

Формула. равносильная исходной формуле и представляющая собой конъюнкцию элементарных дизъюнкций, называется конъюнктивной нормальной формой (КНФ) исходной формулы.

Для любой формулы существует КНФ (ДНФ), то есть любая формула высказываний может быть приведена к КНФ (ДНФ) за конечное число конечных преобразований, используя алгебру высказываний.

Замечание:

Для каждой формулы α существует не одна ДНФ и не одна КНФ.

Дата добавления: 2015-06-27