Привести к днф формулу: Как привести к днф и кнф

ПДНФ и ПКНФ | Введение в математическую логику

Ранее в курсе мы научились определять истинность формул двумя способами:

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

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

В этом уроке мы изучим четыре типа нормальных форм:

• Дизъюнктивная нормальная форма (ДНФ)

• Полная дизъюнктивная нормальная форма (ПДНФ)

• Конъюнктивная нормальная форма (КНФ)

• Полная конъюнктивная нормальная форма (ПКНФ)

В разных источниках полные формы иногда называют совершенными: тогда используются сокращения СДНФ и СКНФ.

Между полными и совершенными формами нет никакой разницы — это один и тот же термин.

Дизъюнктивная нормальная форма (ДНФ)

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

Другими словами, дизъюнктивная нормальная форма — это дизъюнкция нескольких элементарных конъюнкций. В дизъюнктивной нормальной форме используются операторы AND, OR и NOT.

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

$ \left ( P \wedge \sim Q \right ) \vee \left ( Q \wedge R \right ) \vee \left ( \sim P \wedge Q \wedge \sim R \right ) $

Логическая формула находится в дизъюнктивной нормальной форме только при таких условиях: если существует чередование одной или нескольких конъюнкций одного или нескольких литералов.

Есть еще несколько способов получить дизъюнктивную нормальную форму для логических формул:

• Метод таблицы истинности

• Метод деревьев истинности

• Таблица логических эквивалентностей

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

Полная дизъюнктивная нормальная форма (ПДНФ)

У ДНФ есть еще и полная версия. Полная дизъюнктивная нормальная форма — это формула ДНФ, в которой все задействованные переменные представлены только один раз в каждом предложении.

Обратите внимание, что у функции может быть только одна ПДНФ. Это упрощает доказательство и снижает вероятность ошибок. Если есть всего один верный ответ, его намного легче проверить.

ПДНФ относится к сумме произведений. Например:

Чтобы не запутаться, рассмотрим основное отличие между ДНФ и ПДНФ:

Посмотрим на еще двух примерах:

• Выражение в ДНФ, которое не считается ПДНФ из-за разной длины переменных:
  $ \left ( P \wedge \sim Q \wedge R \right ) \vee \left ( \sim P \wedge Q \wedge R \right ) \vee \left ( P \wedge Q \right ) $

• Выражение в ДНФ и ПДНФ одновременно:
  $ \left ( P \wedge \sim Q \wedge R \right ) \vee \left ( \sim P \wedge Q \wedge R \right ) \vee \left ( P \wedge Q \wedge \sim R \right ) $

Конъюнктивная нормальная форма (КНФ)

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

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

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

Другими словами, конъюнктивной нормальной формой называется формула, которая эквивалентна данной формуле и состоит из произведения элементарных произведений. Например:

$ \left ( P \sim \vee Q \right ) \wedge \left ( Q \vee R \right ) \wedge \left ( \sim P \vee Q \vee \sim R \right ) $

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

Проще говоря, высказывание — это серия OR, соединенных AND, как в примере ниже:

OR AND OR

OR AND ¬ OR

Полная конъюнктивная нормальная форма (ПКНФ)

ПКНФ относится к продукту сумм. Например:

Снова рассмотрим основные отличия между формами:

Например:

• Выражение в КНФ, но не в ПКНФ:
  $ \left ( P \vee \sim Q \vee R \right ) \wedge \left ( \sim P \vee Q \vee R \right ) \wedge \left ( P \vee Q \right ) $

• Выражение в КНФ и ПКНФ одновременно:
  $ \left ( P \vee \sim Q \vee R \right ) \wedge \left ( \sim P \vee Q \vee R \right ) \wedge \left ( P \vee Q \vee \sim R \right ) $
  

2_ ДНФ ,КНФ ДНФ, СКНФ алгоритмы преобразования

Логические функции, СДНФ СКНФ

1.4 Формы представления функций алгебры логики

Функции алгебры логики могут быть заданы различными способами:

— таблицей истинности — в аналитической форме- в числовой форме..

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

элементарная дизъюнкция — дизъюнктивный терм или макстерм — это дизъюнктивный терм или макстерм — это дизъюнкция произв числа попарно независимых перем Например,

элементарная конъюнкция — конъюнктивный терм или минтерм — конъюнкция произв числа попарно независимых перем. Напр, Х ₁Х ₂ Х₃ — минтерм 3-его ранг

– это не минтерм, так как перем и зависимы.

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

1) Дизъюнктивную Нормальную Форму — ДНФ

2) Конъюнктивную Нормальную Форму – КНФ

ДНФ это дизъюнкция минтермов разл ранга

КНФ это конъюнкция макстермов различного ранга

Если все термы, входяшие в нормальную форму имеют одинаковый и максимальный ранг,= числу переменных функции — n, то такая форма называется совершенной. При этом, минтерм называют констинтуентой (составля) 1 (КЕ), а макстерм — конституентой 0 (КН).

— это СДНФ

— это СКНФ

Т е СДНФ есть дизъюнкция конституент 1, а СКНФ — есть конъюнкция конституент 0

Составление совершенных форм по табл истинности

Совершенные формы составляют по табл истинности функции. СДНФ : для каждого набора переменных на которых функция=1, записывают минтерм ранга n , в которых с отрицанием берутся переменные = 0 на данном наборе. Все минтермы объединены дизъюнктивно.

СКНФ =для каждого набора переменных, на которых функция=0, записывают макстерм ранга n, в кот с отрицанием берутся переменные, имеющие значение=1 на данном наборе. Все макстермы объединены конъюнктивно

Для компактной записи функций исп числовую форму, в которой заданы только номера наборов. Числовая форма для СДНФ:

Числовая форма для СКНФ:

Алгоритм преобразованияя в ДНФ

1) Сначала избавляемся от операций импликации, эквивалентности и неравнозначности, выразив их через логические связки ¬, & и ∨ по законам:

2) Доводят знаки отрицания до независимых переменных, используя законы де Моргана:

3) Применяя з-н дистрибутивности

преобразуют формулу к дизъюнкции элементарных конъюнкций

4) 4) Постоянно избавляются от двойных отрицаний:
ДНФ A наз совершенной и обозн СДНФ, если каждая переменная формулы A входит с отрицанием или без отрицания в каждый конъюнкт точно 1 раз.

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

Если кажд слаг содер все арг или их отриц, то получ соверш дизъюнкт норм форму (СДФН), напр

Для перехода от табл истинн к СДНФ учит только те сост, для кот функц= 1. Для каждого такого сост запис элем произв всех ар. Если арг имеет зн «0», то запис его отриц. Для привед примера СДНФ имеет вид   (17.4)

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

ДНФ, но не СДНФ от 3 перем

-ДНФ от 2 перем

-представл импликации в виде ДНФ.

-СДНФ для импликации

-СДНФ для оп эквивалентности

-СДНФ для оп неравнозначности

Прим. 1 Привести к ДНФ формулу

Реш.

2. Привести ту же формулу к СДНФ. Начав преобразования с ДНФ

Нахождение СДНФ по табл истинности функции	Нахождение СКНФ по табл истинности функции
1)Отметить те строки таблицы истинности, в последнем столбце которых стоят 1. 2)Выписать для каждой отмеченной строки конъюнкцию всех переменных так: если значение некоторой переменной в данной строке — 1, то в конъюнкцию включать саму эту переменную, если равно 1, то ее отрицание. 3)Все полученные конъюнкции связать в дизъюнкцию.	1)Отметить те строки таблицы истинности, в последнем столбце которых стоят 0. 2)Выписать для каждой отмеченной строки дизъюнкцию всех переменных так: если значение некоторой переменной в данной строке= 1, то в дизъюнкцию включать саму эту переменную, если равно 0, то ее отрицание. 3)Все полученные дизъюнкции связать в конъюнкцию.

Прим1

Прим 2

построение СДНФ:	построение СКНФ:

Для перехода от таблицы истинности к СКНФ учитывают только те состояния, для которых функция= «0». Для каждого такого состояния записывается элементарная сумма аргументов. Если аргуент имеет значение «1», то пишут его отрицание. Для примера СКНФ имеет вид

 

Примеры

1)Привести к КНФ и СКНФ.

Реш. упростим выражение, используя законы де Моргана и правило x y x y → = ∨

Теперь приводим к КНФ

Приведем к СКНФ:

2) С помощью эквивалентных преобразований построить д.н.ф. функции f (x):

Решение. Преобразуем функцию:

3) Используя СКНФ, найти наиболее простую формулу алгебры высказываний от 4 переменных, принимающую значение 0 на следующих наборах значений переменных, и только на них:

Решение. Запишем СКНФ функции по данным задачи

Получили

ЛИТЕРАТУРА и ССЫЛКИ

1)Курилова М.Н. Информатика-логика, СПБ Лес-техн ун-т им.Кирова

https://studfiles.net/preview/2069515/page:5/

2) http://ptca.narod.ru/lec/lec4_3.html

3) https://www.matburo.ru/ex_dm.php?p1=bfpg

Логика

— Преобразование DNF в CNF

Задавать вопрос

спросил 8 лет, 6 месяцев назад

Изменено 1 год, 2 месяца назад

Просмотрено 38 тысяч раз

$\begingroup$

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

Мой учитель преобразовал $F: (A \wedge \neg B) \vee (B \wedge D)$ в CNF-форму $(A \vee B) \wedge (\neg B \vee D)$. Как это происходит? Есть ли способ преобразовать его без рисования таблиц истинности?

• логика
• исчисление высказываний
• конъюнктивная нормальная форма
• дизъюнктивная нормальная форма

$\endgroup$

0

$\begingroup$

Закон Де Моргана гласит: $\neg(a + b) \equiv \neg a\neg b $ и $\neg(ab) \equiv \neg a + \neg b$. $$\begin{equation} \begin{aligned}A\neg B + BD \equiv & \neg(\neg(A\neg B)\neg(BD)) \text{ Де Морган снаружи} \\ \equiv & \neg((\neg A + B)(\neg B + \neg D)) \text{ Внутри Де Моргана} \\ \equiv & \neg(\neg A \neg B + \neg A \neg D + B \neg D) \text{ Дистрибутивность} \\ \equiv & \neg(\neg A \neg B + \neg A \neg D (\neg B + B) + B \neg D) \text{ Дополнение} \\ \neg & \neg(\neg A \neg B + \neg A \neg D \neg B + \neg A \neg D B + B \neg D) \text{ Распределение} \\ \equiv & \neg(\neg A \neg B(1 + \neg D) + B \neg D (1 + \neg A)) \text{ Распределение} \\ \equiv & \neg(\neg A \neg B + B \neg D) \ text{ Аннигилятор} \\ \equiv & (A + B)(\neg B + D) \text{ Снаружи Де Моргана}\end{aligned}\end{equation} $$

Вы также можете изучить К-карты.

$\endgroup$

5

$\begingroup$

Я думаю, что есть более простой способ, чем принятый ответ:

$$\begin{equation} \begin{aligned}A\neg B \vee BD \equiv & (A \vee B)(A \vee D)(\neg B \vee B)(\neg B \vee D) \text{ Дистрибутивность} \\ \equiv & (A \vee B)(A \vee D) 1 (\neg B \vee D) \text{ Tertium non datur} \\ \equiv & (A \vee B)(A \vee D)(\neg B \vee D) \text{ Нейтральный элемент $\wedge$} \\ \equiv & (A \vee B)(\neg B \vee D) \text{ средний термин лишний*} \end{выравнивание}\end{уравнение} $$

* $A\vee D$ ложно только в том случае, если и A, и D ложны, но тогда весь термин в любом случае ложен, потому что он сводится к $(B)(A \vee D)(\neg B)$.

$\endgroup$

Преобразователь CNF

Преобразователь CNF

Статьи | Новости | Блоги | Книги | Форумы

Проспонсированная ссылка, ссылка на спонсора •

Конвертер CNF

Реклама

Эта страница преобразует вашу формулу пропозициональной логики в конъюнктивная нормальная форма. Просто введите его ниже и нажмите кнопка «Конвертировать»:

Ваша формула:

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

(или просто атомов ) и логические связки . Атом — логическое суждение, не содержащее никакого логического связки, такие как Q или Glorp . Каждый атом можно интерпретировать как обозначение некоторого утверждения в человеческий язык, который может быть либо истинным, либо ложным. Например, Q может означать утверждение «Кошка под кроватью». Логические связки: И, ИЛИ, НЕ, УСЛОВНОЕ и БИУСЛОВНЫЙ. (УСЛОВНЫЙ означает «если-то»; ДВУХУСТОЙЧНЫЙ означает если и только если.)

Формула, которую вы вводите выше, должна использовать следующие символы для логические связки:

И:	и
ИЛИ:	|
НЕ:	~
УСЛОВНЫЕ:	=> или 9050 9011 57	ДВУСТОРОННИЙ:	<=>

Атомы должны начинаться с буквы и впоследствии могут содержать числа и символы {, }, - и +. Некоторые действительные атомы: " А ", " ThisIsReallyGroovy ", " X{k-1} ", " Y{k+1} ", " боб ".

Конвертер CNF недоволен круглыми скобками. Вы должны поставить круглые скобки вокруг термины, соединенные И, ИЛИ, УСЛОВНЫМ или ДВУХУСЛОВНЫМ. Так " (A & ~B) " подходит, а " A & ~B " - нет. Но вы не можете помещать скобки вокруг атомов и отрицаний. Итак, " А " и " ~A " в порядке, но " (A) " и " (~A) " не.

Некоторые действительные формулы логики высказываний:

   (~ А и Б)
   ~((А | ~В)<=>С)
   (X{k} <=> (Y{k} & (Z{k} | X{k-1})))
   (кошка => мышь)
   (кошка <= собака)
 

Формула логики высказываний находится в конъюнктивной нормальной форме, если она это союз предложений, где каждое предложение является дизъюнкцией атомы. Конъюнкция — это набор формул, связанных соотношением И, а дизъюнкция представляет собой набор формул, связанных соотношением ИЛИ.