Нормальные формы логики высказываний.

Совершенные нормальные формы


Дизъюнктивная нормальная форма называется совершенной дизъюнктивной нормальной формой (с.д.н.ф.), если она удовлетворяет следующим трем свойствам:
все элементарные конъюнкции, входящие в нее, различны;
в каждой элементарной конъюнкции нет двух вхождений одной и той же переменной
если какая-то переменная входит в одну элементарную конъюнкцию, то она входит и во все остальные.
Например, формулы:
и ; являются с.д.н.ф., а формулы , не являются с.д.н.ф.
Выполнимые формулы с одним и тем же набором пропозиционных букв равносильны тогда и только тогда, когда они приводятся к одной с.д.н.ф.
Этот критерий можно использовать и для формул с разным набором пропозиционных букв, так как каковы бы ни были формулы и можно предполагать что они содержат одни и те же переменные. Если, например формула не содержит букву Р, содержащуюся в , то вместо можно рассматривать равносильную формулу &(), которая уже содержит букву P.
Способ приведения к с.д.н.ф. относится к методу равносильных преобразований. По этому способу:
исходная формула приводится к д.н.ф.;
с помощью законов поглощения и идемпотентности производится упрощение формул и тем самым удовлетворяются условия 1 и 2 определения с.д.н.ф.;
если после выполнения п. 1 и п. 2 окажется, что не выполняется третье условие из определения с.н.д.ф., т.е. какая то элементарная конъюнкция не содержит букву Р, содержащуюся в других элементарных конъюнкциях, то заменяем ее дизъюнкцией двух элементарных конъюнкций (, равносильной этот процесс продолжается до тех пор, пока не будет удовлетворятся третье условие определения с.н.д.ф.
Пример: Привести формулу к с.д.н.ф., т.е. найти формулу равносильную данной и являющуюся с.д.н.ф.
Решение:
а). Приведем к д.н.ф.:

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

Конъюнктивная нормальная форма (к.н.ф.) называется совершенной к.н.ф. (с.к.н.ф.), если она удовлетворяет следующим трем условиям:
все входящие в конъюнкцию элементарные дизъюнкции различны;
в каждой элементарной дизъюнкции нет двух вхождений одной и той же буквы;
если какая то буква входит в одну элементарную дизъюнкцию, то она входит и во все остальные.
Например, формулы ; ; А; являются с.к.н.ф., а формулы: ; ; не являются с.к.н.ф.
Способ приведения формулы к с.к.н.ф. состоит в следующем:
исходная формула приводится к к.н.ф.;
с помощью законов поглощения и идемпотентности упрощается к.н.ф.;
если какая – то элементарная дизъюнкция не содержит буквы Р, имеющуюся в других элементарных дизъюнкциях, то заменяется конъюнкцией , равносильной .
Так поступают до тех пор, пока не удовлетворяется условие 3 с.к.н.ф.
Пример: Привести формулу к с.к.н.ф., т.е. найти формулу, равносильную данной и являющуюся с.к.н.ф.
Решение:
а). Приводим к к.н.ф.:

б). Используя законы идемпотентности дизъюнкцией, упростим полученную к.н.ф., которая будет иметь вид с.к.н.ф.:
=
в). Нет необходимости применять правило 3, так как условие 3 оказалось выполненным.
Заключение

Логика возникла из изучения использования языка в споре для убеждения слушателя. Практически это сводится к получению критериев для решения механическим путем вопроса о том, можно ли некоторую цепь рассуждений основывать на ее форме (а не на содержании), считать правильной. Цепь рассуждений представляет собой просто конечную последовательность высказываний, приводимых в обоснование утверждения, что последнее высказывание в этой последовательности (заключение) может быть выведено из некоторых начальных высказываний (посылок). В обыденных условиях посылки вывода считаются истинными (на основании имеющегося опыта, эксперимента, убеждения и т.п.) Если признать посылки вывода истинными, а принципы, использованные в цепи рассуждений, основанных на этих посылках, правильными, то вынуждены рассматривать полученное как истинное. Следует подчеркнуть, что истинность посылок определяется вне математической логики. Математическая логика формальна в том смысле, что она не делает ссылок на значение.
Итак, логика высказываний (или пропозициональная логика) — это формальная теория, основным объектом которой служит понятие логического высказывания. С точки зрения выразительности, её можно охарактеризовать как классическую логику нулевого порядка. Логика высказываний является простейшей логикой, максимально близкой к человеческой логике неформальных рассуждений и известна ещё со времён античности. Нормальными формами логики высказываний являются конъюнктивная и дизъюнктивная. Каждой форме присущи свои особенности. Существуют различные способы приведения формул – высказываний к этим формам, а также специальные закономерности, о которых нужно всегда помнить.
Литература

Гетманова А.Д. Учебник по логике – М., изд. «Просвещение», 2003г.;
Горский Д.П. Краткий словарь по логике – М., изд. «Просвещение», 2004г.;
Ивин А.А. Логика – Спб., изд. «Питер», 2005г.;
Кириллов В.И., Старченко А.А. Логика – М., изд. «Норма», 2007г.;
Никифоров А.Л. Логика – М., изд. «Флинта», 2007г.;
Свинцов В.И. Логика – Спб., изд. «Спец.Лит.», 2001г.;
Челпанов Г.Н. Логика – М., изд. «Просвещение», 2005г.





Гетманова А.Д. Учебник по логике – с.25-28
Никифоров А.Л. Логика – с.41-47
Свинцов В.И. Логика – с. 12
Ивин А.А. Логика – с.87
Горский Д.П. Краткий словарь по логике – с. 17
Гетманова А.Д. Учебник по логике – с. 127-149
Горский Д.П. Краткий словарь по логике – с. 34
Челпанов Г.Н. Логика – с.231-245
Свинцов В.И. Логика – с.318-325
Никифоров А.Л. Логика – с. 300-303












2