рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Нормальные формы формул

Нормальные формы формул - раздел Философия, Глава 1. Основы теории множеств   Содержание Этого Параграфа Изложим, Следуя [24]. Буд...

 

Содержание этого параграфа изложим, следуя [24].

Будем рассматривать формулы, содержащие только логические операции &, Ú, Ø. Символы & и Ú называются двойственными друг другу.

Формула A* называется двойственной формуле A, если она получена из A одновременной заменой всех символов &, Ú на двойственные. Например, формула X1&(X2ÚØX1) двойственна формуле X1Ú(X2&ØX1). Заметим, что A* содержит те же высказывательные переменные, что и A.

Очевидно, что (A*)* совпадает с A.

Пусть <X1, X2,...,Xn> - некоторый упорядоченный список высказывательных переменных. Пусть <s1, s2,...,sn> - соответствующий список распределения истинностных значений для этих переменных (каждое si, i=1,2,..,n, есть И или Л). Список истинностных значений <t1, t2,...,tn> назовем двойственным к списку <s1, s2,...,sn>, если <t1, t2,...,tn> получается из <s1, s2,...,sn> заменой всех И на Л и всех Л на И.

Лемма 2.3. Пусть A -формула и <X1, X2,...,Xn> - высказывательные переменные этой формулы. Пусть <s1, s2,...,sn> - соответствующий список распределения истинностных значений для этих переменных. Тогда A принимает значение И при этих значениях переменных тогда и только тогда, когда A* принимает значение Л на списке истинностных значений <t1, t2,...,tn>, двойственном к списку <s1, s2,...,sn>.

Доказательство. Проведем математическую индукцию по числу k логических связок в формуле A.

Базис индукции. При k=0 формула A совпадает с одной из высказывательных переменных Xi и A* также совпадает с этой переменной. Поэтому формулы A и A* имеют противоположные истинностные значения si и ti и утверждение леммы выполнено.

Индуктивный переход. Пусть утверждение леммы справедливо при числе логических операций, меньшем k. Докажем, что оно остается справедливым и при числе операций, равном k. Рассмотрим три различных случая, в зависимости от того какой вид имеет формула A.

1. Пусть формула A совпадает с формулой ØB. Тогда A* совпадает с формулой Ø (B*). Пусть <s1, s2,...,sn> - некоторый список истинностных значений. Истинностное значение формулы B на этом списке противоположно истинностному значению формулы A на этом же списке. Так как количество логических операций в формуле B меньше k, то значение формулы B* на двойственном списке <t1, t2,...,tn> противоположно значению B на списке <s1, s2,...,sn>. Следовательно, значение Ø (B*) на списке <t1, t2,...,tn> совпадает со значением формулы B на списке распределения истинностных значений <s1, s2,...,sn>. Отсюда сразу получаем искомое утверждение для формулы A.

2. Пусть формула A имеет вид B&C. Из определения операции двойственности сразу следует, что A* = (B&C)* = B* Ú C*. Для распределения истинностных значений <s1, s2,...,sn> формула A истинна тогда и только тогда, когда формулы B и C также истинны. Поскольку B и C имеют логических операций меньше k, то значения формул B* и C* ложны на двойственном наборе истинностных значений <t1, t2,...,tn>. На этом же наборе ложна и формула B*ÚC* = A*. Эти рассуждения показывают справедливость искомого утверждения в данном случае.

3. Пусть формула A имеет вид BÚC. Из определения операции двойственности сразу следует, что A* = (BÚC)* = B* & C*. Для распределения истинностных значений <s1, s2,...,sn> формула A ложна тогда и только тогда, когда формулы B и C также ложны. Поскольку B и C имеют логических операций меньше k, то значения формул B* и C* истинны на двойственном наборе истинностных значений <t1, t2,...,tn>. На этом же наборе истинна и формула B*&C* = A*. Тем самым мы получаем справедливость искомого утверждения и в данном случае.

Разбор всех случаев позволил нам закончить индуктивный переход и убедиться в справедливости леммы.

Теорема 2.3. (принцип двойственности) Если A º B, то A* º B*.

Доказательство. Пусть <t1, t2,...,tn> - произвольный набор распределения истинностных значений для истинностных переменных в формуле A*. Тогда истинностное значение A* противоположно истинностному значению A (а, следовательно, и B) на двойственном списке <s1, s2,...,sn>. С другой стороны, значение формулы B* на списке истинностных значений <t1, t2,...,tn> противоположно истинностному значению B на списке <s1, s2,...,sn>. Следовательно, значения формул A* и B* при произвольном распределении истинностных значений переменных совпадают. Что и требовалось доказать.

Принцип двойственности можно использовать для нахождения новых равносильностей. Например, используя следующий частный случай дистрибутивности & относительно Ú

X & (Y Ú Z) º (X&Y)Ú(X&Z),

получаем равносильность

X Ú (Y & Z) º (XÚY)&(XÚZ).

Заметим, что в силу ассоциативности операций & и Ú, как бы мы не расставляли скобки в выражениях A1&A2&…&An и A1ÚA2Ú…ÚAn (n>3), всегда будем приходить к равносильным формулам. Допуская некоторую вольность речи, каждое из этих выражений будем считать формулами и называть соответственно многочленной конъюнкцией и дизъюнкцией формул A1, A2,…, An. Для этих формул, используя, например, индукцию по max(k, n), нетрудно получить равносильности, выражающие обобщенную дистрибутивность (для простоты записи, положим k=2, n=3):

(A1ÚA2) & (B1ÚB2ÚB3) º (A1&B1) Ú (A1&B2) Ú (A1&B3) Ú

(A2&B1) Ú (A2&B2) Ú (A2&B3),

(A1&A2) Ú (B1&B2&B3) º (A1ÚB1) & (A1Ú B2) & (A1ÚB3) &

(A2ÚB1) & (A2ÚB2) & (A2ÚB3).

Точно также получаем обобщенные законы де Моргана:

Ø( A1&A2&…&An) º ØA1ÚØA2Ú…ÚØAn,

Ø( A1ÚA2Ú…ÚAn) º ØA1&ØA2&…&ØAn.

Определим теперь некоторые канонические виды формул.

Формула называется элементарной конъюнкцией, если она является конъюнкцией (быть может, одночленной) переменных и отрицаний переменных. Например, формулы ØX2, X1, X1&X2, X1&ØX2&ØX1&X4 являются элементарными конъюнкциями.

Говорят, что формула находится в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией (быть может, одночленной) элементарных конъюнкций. Например, формулы ØX2, X1, X1&X2, X1&ØX2&ØX1&X4, (X1&X2)Ú( X1&ØX2&ØX1&X4)&X1 находятся в ДНФ.

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

Доказательство теоремы распадается на три этапа:

1-ый этап. Для формулы A строим такую формулу A1, что AºA1 и в A1 не содержатся символы ~ и É (теорема 2.2).

2-ой этап. Докажем теперь, что для формулы A1 можно найти формулу A2 такую, что A1 º A2 и в A2 отрицание находится только перед переменными. Такая формула называется формулой с "тесными" отрицаниями. Докажем это утверждение математической индукцией по числу n логических операций формулы A1.

Базис индукции. Если n=0, то A1 есть какая-то переменная Xi. В качестве A2 нужно взять Xi.

Индуктивный переход. Пусть утверждение выполняется для всех формул A1 с числом связок меньше n. Пусть в формуле A1 содержится точно n логических связок. Рассмотрим следующие случаи:

1) A1 имеет вид B1ÚC1. Тогда в B1, C1 логических символов меньше, чем n. Поэтому существуют формулы B2, C2 такие, что B1ºB2, C1ºC2 и в B2 и C2 отрицание встречается только перед переменными. Ясно, что B2ÚC2 равносильна A1 и является формулой с "тесными" отрицаниями;

2) A1 имеет вид B1&C1. Доказательство аналогично предыдущему случаю;

3) A1 имеет вид ØØB1. Тогда A1º B1 в B1 логических символов меньше, чем n. Поэтому к B1 применимо индуктивное предположение;

4) A1 имеет вид Ø(B1ÚC1). Тогда A1ºØB1&ØC1 и в ØB1, ØC1 логических символов меньше, чем n. Поэтому существуют такие формулы B2, C2, что ØB1ºB2, ØC1ºC2 и в B2 и C2 отрицание встречается только перед переменными. Ясно, что A1ºB2&C2 и B2&C2 является формулой с "тесными" отрицаниями;

5) A1 имеет вид Ø(B1&C1). Тогда A1ºØB1ÚØC1, и далее поступаем как в предыдущем случае.

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

Пример 2.5. Преобразуем к формуле с "тесными" отрицаниями:

Ø(ØØ(X1&ØX2)Ú(X2&ØX1)) º ØØØ(X1&ØX2)&Ø(X2&ØX1) º

Ø(X1&ØX2)&(ØX2ÚØØX1) º (ØX1ÚØØX2)&(ØX2ÚX1) º

(ØX1ÚX2)&(ØX2ÚX1).

3-ий этап. Полученная формула A2 построена из переменных и их отрицаний с помощью многочленных конъюнкций и дизъюнкций. Применив теперь обобщенную дистрибутивность & относительно Ú, последовательно преобразуем формулу (аналогично приведению алгебраического выражения, составленного из переменных, с помощью сложений и умножений, к виду многочлена). Заметим, что при этом Ú аналогично сложению, а & - умножению. Полученная в результате преобразований формула B будет удовлетворять требованиям теоремы.

Пример 2.6. Применим преобразования третьего этапа к формуле с "тесными" отрицаниями, полученной в примере 2.5:

(ØX1ÚX2)&(ØX2ÚX1) º (ØX1&ØX2)Ú(ØX1&X1)Ú(X2&ØX2)Ú(X2&X1).

Говорят, что формула A находится в конъюнктивной нормальной форме (КНФ), если формула A* определена (т. е. в A нет символов ~ и É) и находится в ДНФ.

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

Теорема 2.5 (о приведении к КНФ). Для любой формулы A можно найти такую формулу B, что В находится в КНФ и AºB. Формула B называется конъюнктивной нормальной формой формулы A.

Первое доказательство. Пусть A º A1 и A1 не содержит символов ~, É. Пусть B1 - дизъюнктивная нормальная форма формулы A*1. Тогда B*1 находится в КНФ и, кроме того, по принципу двойственности B*1 º (A*1)* º A1 º A. Значит, B*1 удовлетворяет требованиям теоремы.

Второе доказательство. Применив первые два этапа из доказательства теоремы 2.6 о ДНФ, получим формулу A2, равносильную A, не содержащую символов ~, É и содержащую отрицания только перед переменными. Преобразуем теперь A2 как алгебраическое выражение, считая на этот раз & аналогом сложения, а Ú - аналогом умножения и применяя дистрибутивность Ú относительно &. Приведение формулы A2 к виду многочлена даст на этот раз КНФ.

Пример 2.7. Приведем к КНФ формулу:

(X1&X2)~(ØX1&X3) º

((X1&X2)&(ØX1&X3))Ú(Ø(X1&X2)&Ø(ØX1&X3)) º

(X1&X2&ØX1&X3)Ú((ØX1ÚØX2)&(ØØX1ÚØX3)) º

(X1&X2&ØX1&X3)Ú((ØX1ÚØX2)&(X1ÚØX3)) º

(X1ÚØX1ÚØX2)&(X1ÚX1ÚØX3)&(X2ÚØX1ÚØX2 )&(X2ÚX1ÚØX3)&

(ØX1ÚØX1ÚØX2)&(X1ÚX1ÚØX3)&(X3ÚØX1ÚØX2)&(X3ÚX1ÚØX3).

Заметим, что первое преобразование основано на равносильности 16.

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

– Конец работы –

Эта тема принадлежит разделу:

Глава 1. Основы теории множеств

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

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Нормальные формы формул

Что будем делать с полученным материалом:

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

Все темы данного раздела:

Начальные понятия теории множеств
  Понятие множества является основным, неопределяемым понятием, поэтому мы можем его только пояснить, например, с помощью следующего псевдоопределения. Определение:

Интуитивный принцип объемности
Определение. Множества Aи B считаются равными, если они состоят из одних и тех же элементов. Записывают A=B, если A и B равны, и A

Отношения
Определение. Упорядоченная пара <x, y> интуитивно определяется как совокупность, состоящая из двух элементов x и y, расположенных в определенном порядке. Две пары <

Функции
Определим понятие "функция", следуя Дирихле. По сути дела при таком определении мы отождествляем функци

Эквивалентность
  Одним из самых важных типов отношений является отношение эквивалентности на множестве. Определение. Рефлексивное, симметричное и транзитивное отношение r н

Зачем мы изучаем математическую логику?
  Логика есть наука о законах и формах познающего мышления. Логика изучает мышление, но не всякое мышление, а лишь те мыслительные процессы, которые направлены на обнаружение и обосно

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

Логические связки
  Грамматическими средствами в разговорном языке из нескольких высказываний можно составить сложное (составное) высказывание. Например, с помощью союзов "и", "или"

Формулы логики высказываний
  Мы определим формальный язык для описания логики высказываний. Это описание чисто синтаксическое и оно не требует, чтобы формулы логики высказывания имели какую-то семантику (смысл)

Равносильность формул
  Пусть A и B - две формулы и {X1, X2,…, Xn} - множество всех выск

Определение.
· Формула называется выполнимой, если на некотором наборе распределения истинностных значений переменных она принимает значение И. · Формула называется тождественно-ложной ил

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

Абстрактное определение булевых алгебр
  Определение.Множество элементов B с заданным на нем двуместными операциями &Ugra

Модель исчисления высказываний
Пусть B - множество высказываний с обычными логическими операциями конъюнкции, дизъюнкции и отрицания и равенство высказываний интерпретируется как их равносильность. Во второй главе показ

Булевы функции. Теорема о нормальной булевой форме
  Рассмотрим еще одну модель булевой алгебры. Определение. Пусть M - произвольная булева алгебра с базисными операциями Ù, Ú, Ø. Рассмот

Определение.
Если булева алгебра M - двухэлементна (т. е. содержит только Ë и Î), то булевы функции называются двоичными функциями. Если в двухэлементной булевой алгебре элементы &Eum

Полные системы булевых функций
  Определение.Система функций {f1, f2,…, fn} называется полной, если любая булева функция может быть выражена через функции f

Переключательные элементы
Пусть имеется "черный ящик" - некоторое устройство, внутренняя структура которого нас не интересует, а известно лишь, что оно имеет n упорядоченных "входов" (например, занумеров

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

Интерпретации
  Формулы имеют смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов. Определение. Под интерпретацией мы будем понимат

Выполнимость и общезначимость
Определение.Формула A выполнима в данной интерпретации, если существует такой набор <a1, a2,…, an>, aiÎM, значений св

Формальные аксиоматические теории
Формальная теория представляет собой множество чисто абстрактных объектов (не связанных с внешним миром), в которой представлены

Исчисление высказываний
  Оказывается множество тавтологий логики высказываний можно описать в рамках простой формальной аксиоматической теории - исчисления высказываний. Определим исчисление высказ

Теорема 5.2
1. Любая аксиома в исчислении высказываний является тавтологией. 2. Любая теорема в исчислении высказываний является тавтологией. Доказательство. То, что каждая аксиома A1-A3 явля

Исчисление предикатов
  Исчисление предикатов - это аксиоматическая теория, символами которой являются, по существу, те же символы, что и в логике предикатов: 1) символы предметных переменных: x

Теорема 5.4
1. Аксиомы исчисления предикатов - общезначимые формулы. 2. Формула, получающаяся из общезначимых формулы по любому из правил вывода 1-4, является общезначимой. 3. Любая доказуема

Логический вывод
  Терпеть не могу логики. Она всегда банальна и нередко убедительна. Оскар Уайльд   Формальная математика основывается на аксиоматическом методе. Внача

Метод резолюций
  Логическое программирование является, пожалуй, наиболее впечатляющим примером применения идей и методов математической логики (точнее, одного из ее разделов - теории логического выв

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

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

Определения
Этот подход к формализации понятия алгоритма принадлежит Гёделю и Клини (1936). Основная идея Гёделя сос

Ламбда - исчисление
Значение ламбда-исчисления   Ламбда-исчисление было изобретено Алонсом Чёрчем около 1930 г. Чёрч первоначально строил l-исчисление как часть

Машины Тьюринга
  Рассмотрим еще один способ определения вычислимых функций, следуя в изложении [29, стр. 12-14]. Ф

Тезис Чёрча
  За последние 60 лет было предложено много различных математических уточнений интуитивного понятия алгоритма. Три из этих подхода мы разобрали. Перечислим некоторые другие альтернати

Некоторые алгоритмически неразрешимые проблемы
  Определение. Предикат M(x) называется разрешимым, если его характеристическая функция, задаваемая формулой cM(x

Сложность алгоритмов
  Применение математики во многих приложениях, требует как правило, использования различных алгоритмов. Для решения многих задач не трудно придумать комбинаторные алгоритмы, сводящиес

NP-трудные и NP-полные задачи
  Различные задачи, относящие к классу NP являются эквивалентными относительно некоторого отношения, которое мы сейчас определим. Определение. Задача Q по

Трехзначная система Я. Лукасевича
Эта пропозиционная логика была построена Я. Лукасевичем в 1920 году [34]. Лукасевич обозначил «истину» за «1», «ложь» за «0» и ввел третье значение – «нейтрально» - ½. Основными функциями им

Логика Гейтинга
  Из закона исключенного терьего в двузначной логике выводятся: 1. ØØх É х 2. х É ØØх Гейтинг создал трехзначную пропозицио

Трехзначная система Бочвара Д.А.
  Система создавалась Бочваром Д.А. [36] для разрешения парадоксов классической математической логики методом формального доказательства бессмысленности определенных высказываний. Нап

К - значная логика Поста Е.Л.
  Логика Поста [37] является обобщением частного случая – двузначной логики, когда К=2. Действительно, по Посту значения истинности принимают значения 1, 2,…,К (при К ³ 2 и К – к

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

Наименование тем
  Введение   История развития математической логики и теории алгоритмов. Математическая логика и основания математики. Теория алгоритмов и принципиальные возмож

КОНТРОЛЬНАЯ № 2
Вариант 1   1. Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения простых высказываний: "Для того, чтобы x бы

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги