Алгоритм построения ДНФ

( Наибольшие и наименьшие, максимальные и минимальные элементы частично упорядоченных множеств. Примеры. )

Линейно упорядоченное множество или цепь ― частично упорядоченное множество, в котором для любых двух элементов

имеет место

или

(Высказывания и логические операции над ними. Свойства логических операций. Базовая таблица истинности для логических операций.)

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

Базовыми понятиями логики высказываний являются пропозициональная переменная — переменная, значением которой может быть логическое высказывание, — и (пропозициональная) формула, определяемая индуктивно следующим образом:

1) Если P — пропозициональная переменная, то P — формула.

4) Каждая формула может быть получена за конечное число шагов при помощи предыдущих трёх правил.

Знаки

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

Конъюнкция Дизъюнкция Материальная импликация

(Индуктивный подход к построению множества всех формул алгебры высказываний посредством применения логических операций к исходным простым высказываниям

. Сложность формулы. Примеры.)

Одним из наиболее методов определения объектов и совокупностей объектов назыв. метод индуктивных определений. Предположим, что нужно построить класс объектов К для этого:

1) Опред-ся исходные объекты, без всяких доп. обоснований. То есть непосредст. указ. те объекты(своеобраз атомы, которые нужно считать принадлежащим области К.

2) Указ-ся совокупность эффект-х правил которые позвол строить из ране построенных объектов строить все более и более слож объектов совокупности К

Построение совокупности К опред по шагам. Применим этот метод для построения совокуп К всех множеств которые можно получ из исход множеств(атомов) посредством приминения к ним теоретиком нож-ых операции.

А) базис индуктивного опред-я. Всякое исход мн-во А_і(і=1,2….) (вроде спит.) множеством строящихся совокуп-тей К. Всем этим множ-ам присвое-я сложность 0.

Б) индуктивное предполож.(шаг t). Предположим, что на шагах с номерами 0,1,2,…. t уже построены все множ-ва из класса К и определенны их сложности

В)Индукционный шаг(шаг t+1) множество шага t+1 строется исходя из мно-ва предшествующих шагов посредством прим к ним(не более раза) одной из теоретиком нож-х операций

При этом сложность множ М с шагом t+1 опред. По формуле S(M)=max[S(A);S(B)]+1, где А и В множество шагов 0,1,2,… t из которых получ мн-во М посредством прим-я теорет множ операции (т.е M=AᴗB; M=AᴖB; M= B\A)

(Отношение равносильности на множестве высказываний. Примеры. Основные равносильности (законы логики).)

Определение 4.1. Формулы

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

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

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

Следствие 4.3. Отношение равносильности между формулами алгебры высказываний:

а) рефлексивно: ;
б) симметрично: если , то ;
в) транзитивно: если и , то , т.е. отношение равносильности является отношением эквивалентности.

(Индуктивный подход к таблицам истинности данных формул алгебры высказываний и методы получения по данным таблицам истинности формул алгебры высказываний.)

1. Каждая отдельно взятая пропозициональная переменная есть формула алгебры высказываний.

2. Если

— формулы алгебры высказываний, то выражения также являются формулами алгебры высказываний:

3. Никаких других формул алгебры высказываний, кроме получающихся согласно пунктам 1 и 2, нет.

Определения такого типа называются индуктивными. В них имеются прямые пункты (в данном случае п. 1 и п. 2), где задаются объекты, которые в дальнейшем именуются определяемым термином (в данном случае — формулами алгебры высказываний), и косвенный пункт (в данном случае п. 3), в котором говорится, что такие объекты исчерпываются объектами, заданными в прямых пунктах. Среди прямых пунктов имеются базисные пункты (в данном случае п. 1), где указываются некоторые конкретные объекты, именуемые в дальнейшем определяемым термином, и индуктивные пункты (в данном случае п. 2), где даются правила получения определяемых объектов, в частности из объектов, перечисленных в базисных пунктах.

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

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

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

Приведем примеры формул. На основании п. 1 определения 2.1 формулами будут пропозициональные переменные:

Далее на основании п. 2 того же определения из этих формул построим следующие:

Из построенных формул также на основании п. 2 строим еще более сложные формулы:

Ясно, что процесс построения все более сложных формул может продолжаться безгранично.

Приведем примеры выражений, не являющихся формулами. Это в каком-то смысле нелепые выражения. К примеру, выражение

было бы формулой на основании п. 2 определения 2.1, если бы формулами были выражения

. Выражение

есть пропозициональная переменная и потому на основании п. 1 определения 2.1 является формулой. Рассмотрим выражение

. Оно было бы формулой, если бы между формулами

стоял один из знаков логических связок. Но такого знака нет. Следовательно, выражение

не формула, и исходное выражение

формулой также не является.

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

(Релейно-контактные схемы. Методы перехода от Р.К.С. к приведенным формулам и от приведенных формул к Р.К.С. Методы упрощения Р.К.С.)

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

Каждому реле можно поставить в соответствие значение 1, если оно находится под током, и 0, если нет. Все замыкающие контакты, подключенные к реле х, будем обозначать x₁,... x_n, а размыкающие -

Всей схеме также можно поставить одно из двух значений 1, если схема проводит ток, и 0, если не проводит. Это значение есть функция переменных х_i,

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

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

т.е. дизъюнкция моделируется параллельным соединением проводников, конъюнкция - последовательным.

Можно установ такое соотв м\у приведенными формулами и рел контактными схемами при которых формулыбудут приним значения истины тога когда соотв РКС будет пропуск электр ток.

(Построение Р.К.С. по заданным условиям. Пример на решение задачи о перевозе.)

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

т.е. дизъюнкция моделируется параллельным соединением проводников, конъюнкция - последовательным.

(Общая схема построения формальной аксиоматической теории и реализация этой схемы применительно к построению исчисления высказываний.)

Формальные аксиоматические теории. Аксиомы и правила вывода И.В.

(Аксиомы и правила вывода И.В. Понятие доказательства (вывода) и теоремы в И.В. Примеры выводов и выводимых формул.)

Формальные аксиоматические теории. Аксиомы и правила вывода И.В.

Понятие вывода (доказательства) в исчислении высказываний. Теоремы И.В. Примеры.

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

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

Теорема о дедукции: если Г, В ├ А, то Г ├ В → А, где Г - это набор некоторых формул Г={F₁, F₂,..., F_n}.

Следствие: тогда и только тогда F₁, F₂,..., F_n ├ A, когда ├F₁→(F₂→...→(F_n-1→(F_n→A))...)

Доказательство: пусть F₁, F₂,..., F_n ├ A. Тогда, применяя теорему о дедукции, имеем F₁, F₂,..., F_n-1 ├ F_n→A.

Аналогично F₁,F₂,...,F_n-2├F_n-1→(F_n→A), и т.д. Продолжая этот процесс необходимое число раз, получаем ├F₁→(F₂→...→(F_n-1→(F_n→A))...)

Для доказательства достаточности предположим, что ├B, где B=F₁→(F₂→...→(F_n-1→(F_n→A))...). По правилу заключения получаем F₁├(F₂→...→(F_n-1→(F_n→A))...). Далее, через n шагов имеем F₁,F₂,...,F_n├A.

Таким образом, благодаря следствию, проверка выводимости формулы A из формул F₁,F₂,...,F_n, сводится к проверке доказуемости формулы F₁→(F₂→...→(F_n-1→(F_n→A))...).

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

Теорема о полноте. Формула A доказуема тогда и только тогда, когда A тождественно истинна т(автология): ├A⇔A - тавтология.

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

Пример. Докажем, что P├P. По теореме о дедукции это равносильно тому, что ├(Р→Р). В свою очередь, по теореме о полноте, достаточно доказать, что (Р→Р) тавтология. Составляя таблицу истинности для формулы (Р→Р), убеждаемся, что (Р→Р) тождественно истинна и, следовательно, доказуема.

Теорема о непротиворечивости. Исчисление ИВ непротиворечиво.

Доказательство. По теореме о полноте любая формула, не являющаяся тождественно истинной, не доказуема в ИВ. Например, такой формулой является формула А∧(А).

Множество формул Г называется противоречивым, если Г├А∧(А). Если Г — противоречивое множество формул, будем обозначать этот факт через Г├.

Утверждение. Формула А выводима из множества формул Г тогда и только тогда, когда множество Г∩{A} — противоречиво.

(Дизъюнктивные и конъюнктивные нормальные формы и алгоритмы приведения к ним. Примеры. Истинностные характеризации Д.Н.Ф. и К.Н.Ф.)

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

Дизъюнктивные нормальные формы и алгоритмы приведения к ним

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

Легко построить СДНФ, представляющую произвольную булеву функцию, заданную в табличной форме. Для этого достаточно выделить наборы (σ₁,σ₂,…,σ_n), на которых функция принимает значение 1, и для каждого из них ввести в СДНФ полную элементарную конъюнкцию, где любая переменная X_i присутствует с отрицанием, если σ_i=0, и без отрицания, если σ_i=1.

Очевидно, для любой булевой функции f(x₁,x₂,…,x_n), кроме константы 0, существует единственная СДНФ (с точностью до порядка литералов и конъюнкций). Поэтому данная форма представления булевой функции является канонической

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

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

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

Выразим логические операции → и ↓ через:v ^ ך

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

Используя закон дистрибутивности, приводим формулу к ДНФ:

Конъюнктивная нормальная форма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкцийлитералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ. Для этого можно использовать: Закон двойного отрицания, Закон де Моргана, Дистрибутивность.

Но эти 3 формулы не в КНФ эквивалентны следующим формулам в КНФ:

Преобразуем формулу F к формуле не содержащей →:

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

k -конъюнктивной нормальной формой называют конъюнктивную нормальную форму, в которой каждая дизъюнкция содержит ровно k литералов.

Например, следующая формула записана в 2-КНФ:

Если в простой дизъюнкции не хватает какой-то переменной (например, z), то добавляем в нее выражение: (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:

(XvY)^(Xv ך Yv ך Z)=(XvYv(Z^ ך Z))^(Xv ך Yv ך Z)=(XvYvZ)^(XvY vך Z)^(Xv ךYv ךZ)

Если в простой дизъюнкции не хватает какой-то переменной (например, z), то добавляем в нее выражение:Z^ ך Z=0 (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:

(XvY)^(Xv ךY ךZ)=(XvYv(Zv ךZ))^(Xv ךYv ךZ)=(XvYvZ)^(XvYv ךZ)^(Xv ךYv ךZ) Таким образом, из КНФ получена СКНФ.

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: