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

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

  • автор:

ДНФ и КНФ

Стандартный базис. Элементарные формулы — литералы. Элементарная конъюнкция (дизъюнкция). Дизъюнктивная (конъюнктивная) нормальная форма и совершенная форма. Теорема: любая булева функция, отличная от 0 (от 1) представима в виде СДНФ (СКНФ). Полнота стандартного базиса. Примеры полных базисов: базис Жегалкина, штрих Шеффера, стрелка Пирса.

Стандартный базис — это набор из трех исходных операций булевой алгебры: сложения (объединения), умножения (пересечения) и отрицания.

Здесь мы будем называть литералом переменную x или ее отрицание x и обозначать xˆ. Булево пересечение нескольких литералов, определяемых различными переменными, т.е. выражение вида X = xˆ12 . . . xˆл, называется элементарной конъюнкцией. Требование, чтобы все переменные были различны обусловливается следующим. Если в конъюнкцию входит несколько одинаковых литералов, то в силу коммутативности, ассоциативности и идемпотентности конъюнкции можно, переходя к эквивалентной формуле, оставить лишь один литерал (например, x 1 x 1 = x 1). Если в конъюнкцию входит переменная и ее отрицание, то формула эквивалентна константе 0, поскольку x x = 0 и для любой формулы Y имеем Y x x = 0.

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

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

есть совершенная форма.

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

Теорема 1.4. Любая булева функция, отличная от константы 0 представима в виде СДНФ.

Дискретная математика

◀Условимся под x σ понимать формулу x, если σ = 1, и формулу x , если σ = 0. Пусть функция f(y1, . . . , yn) принимает значение 1 на векторе (t1, . . . , tn) (такой вектор называют конституэнтой единицы). Тогда элементарная конъюнкция также принимает значение 1 на этом наборе, но обращается в нуль на всех остальных n-мерных булевых векторах. Рассмотрим формулу

Формула Φ. ДНФ и КНФ

в которой сумма (объединение) распространяется на все те наборы (t1, . . . , tn) значений аргументов, на которых заданная функция принимает значение 1. Отметим, что множество таких наборов не пусто, так что в сумме есть по крайней мере одно слагаемое.

Нетрудно заметить, что формула Φ обращается в 1 при тех, и только при тех значениях переменных, при которых обращается в 1 рассматриваемая функция. Значит, формула Ψ представляет функцию f. ▶

Следствие 1.1. Стандартный базис является полным.

◀ Действительно, если функция не является константой 0, то она представима либо в виде СДНФ, которая является формулой над стандартным базисом. Константу 0 можно представить, например, формулой f(x1, x2, . . . , xn) = x1 x 1. ▶

Пример 1.2. Рассмотрим функцию трех переменных m(x1, x2, x3) (табл. 1.4), называемую мажоритарной функцией. Эта функция принимает значение 1, если больше половины ее аргументов имеют значение 1. Поэтому ее часто называют функцией голосования. Построим для нее СДНФ.

Мажоритарная функция имеет 4 конституэнты единицы, а значит, в ее СДНФ должно быть четыре слагаемых. Результат будет следующий:

Аналогично строится СКНФ. Выбираем конституэнты нуля и для каждой составляем элементарную дизъюнкцию. Получим:

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

Пример 1.3. Множество из операций сложения по модулю 2, умножения и константы 1 называют базисом Жегалкина. Сложение по модулю 2 и умножение — базовые операции кольца Z2, выражения, составленные с их помощью — это многочлены над кольцом Z2. Кон- станта 1 в данном случае необходима для записи свободного члена. Поскольку xx = x, то все сомножители в многочлене имеют степень 1. Поэтому при записи многочлена можно обойтись без понятия степени. Примеры формул над базисом Жегалкина:

xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

Любую такую формулу называют полиномом Жегалкина. Фактически полином Жегалкина — это многочлен над кольцом Z2.

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

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

(точнее, с точностью до порядка слагаемых). Коэффициенты полинома Жегалкина при небольшом количестве переменных можно найти методом неопределенных коэффициентов.

Пример 1.4. Рассмотрим множество из единственной функции — штриха Шеффера*. Это множество полно, что следует из следующих легко проверяемых тождеств:

x =x|x, xy= x|y =(x|y)|(x|y), x+y= x | y =(x|x)|(y|y).

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

*Штрих Шеффера — бинарная, но не ассоциативная операция. Поэтому при использовании инфиксной формы следует быть внимательным: результат зависит от порядка выполнения операций. В этом случае рекомендуется явно указывать порядок операций при помощи скобок, например писать (x | y) | z, а не x | y | z, хотя обе формы равнозначны.

18 Нормальные формы формул, приведение к днф, кнф.

Элементарная конъюнкция – это конъюнкция конечного множества переменных и их инверсий.

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

Число аргументов, образующих элементарную дизъюнкцию или конъюнкцию, называется рангом.

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

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

Алгоритм приведения формулы к ДНФ:

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

2.Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания по правилу

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

Алгоритм приведения формулы к КНФ:

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

2.Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания по правилу

3.Используя закон дистрибутивности , преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.

(Алгоритм приведения формул булевых функций к ДНФ (КНФ)).

Шаг 1. Все подформулы A вида B  C (т.е. содержащие импликацию) заменяем на BVC или на (B&C).

Шаг 2. Все подформулы A вида B ~ C (т.е. содержащие эквивалентность) заменяем на (A&B) V (A&B) или на (AVB)&(AVB).

Шаг 3. Все отрицания, стоящие над сложными подформулами, опускаем по законам де Моргана.

Шаг 4. Устраняем все двойные отрицания над формулами (в соответствии с равносильностью 8).

Шаг 5. Осуществляем раскрытие всех скобок по закону дистрибутивности конъюнкции относительно дизъюнкции для ДНФ (в соответствии с равносильностями 3а и 17) или по закону дистрибутивности дизъюнкции относительно конъюнкции для КНФ.

19 Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы.

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

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

Алгоритм получения сднф по таблице истинности.

1. Отметить те строки таблицы истинности, в последнем столбце ко­торых стоят 1:

2. Выписать для каждой отмеченной строки конъюнкцию всех пере­менных следующим образом: если значение некоторой переменной в дан­ной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание: — для 2-й строки; — для 3-й строки.

3. Все полученные конъюнкции связать в дизъюнкцию: (1*)

(Алгоритм приведения формулы булевой функции к СДНФ)

Шаг 1. Используя алгоритм построения ДНФ, находим формулу В, являющуюся ДНФ формулы А.

Шаг 2. Вычеркиваем в B все элементарные конъюнкции, в которые одновременно входят какая-нибудь переменная и ее отрицание. Это обосновывается равносильностями:

A&A  0, B&0  0, СV0  С.

Шаг 3. Если в элементарной конъюнкции формулы B некоторая переменная или ее отрицание встречается несколько раз, то оставляем только одно ее вхождение. Это обосновывается законом идемпотентности для конъюнкции: A&A  A.

Шаг 4. Если в элементарную конъюнкцию С формулы В не входит ни переменная x, ни ее отрицание x, то на основании 1- го закона расщепления заменяем С на (С&x) V (C&x).

Шаг 5. В каждой элементарной конъюнкции формулы B переставляем конъюнктивные члены так, чтобы для каждого i (i = 1, . n) на i-м месте была либо переменная xi, либо ее отрицание xi.

Шаг 6. Устраняем возможные повторения конъюнктивных членов согласно закону идемпотентности для дизъюнкции: СVС  С.

1. Преобразование исходной формулы в кнф.

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

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

2.Преобразование кнф в скнф.

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

Делаем все элементарные дизъюнкции правильными с помощью следующих двух преобразований:

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

— если некоторая переменная входит в элементарную дизъюнкцию несколько раз, причём либо во всех случаях без отрицаний, либо во всех случаях с отрицаниями, то оставляем только одну эту переменную.

Преобразуем правильные дизъюнкции в полные. Пусть в некоторую элементарную дизъюнкцию не входит переменная x, тогда рассмотрим выражение (x ) и повторим шаги 2 и 3. Если недостающих переменных несколько, то проделать аналогичные преобразования со всеми недостающими переменными.

Построение совершенных нормальных форм с помощью таблиц истинности

Для построения СДНФ или СКНФ, исходя из теоремы о разложении функции алгебры логики от n переменных по k переменным (k=n), можно воспользоваться таблицами истинности.

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

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

Построение совершенных нормальных форм, используя принцип двойственности.

Построение совершенной конъюнктивной нормальной формы.

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

Построение совершенной дизъюнктивной нормальной формы.

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

Как привести формулу к виду КНФ?

Дана задача, привести формулу к виду КНФ. С точки зрения булевой алгебры вопросов не возникает, все логично и ясно, но вот с приведением данной задачи в плоскость реализации на любом ЯП — возникают вопросы. Гугл выдаёт результаты на таблицы истинности в качестве решения, а в задании необходимо вывести формулу приведенную к виду КНФ. Может кто-то подкинет каких-либо решений. Я что-то уже неделю гугл мучаю, но вот решений хотя бы близких к требуемому заданию — не нахожу.

ЗЫ: предлагать гугл в помощь не надо. Спасибо! За ранее очень преблагодарен.

  • Вопрос задан более трёх лет назад
  • 5994 просмотра

Комментировать
Решения вопроса 0
Ответы на вопрос 3

Mrrl

Заводчик кардиганов

Считать значение формулы при заданных значениях переменных научились? Если да — перебираете все наборы значений (a_1. a_n) (их всего 2^n), считаете для каждого значение формулы, и если получился 0 — добавляете в формулу очередную дизъюнкцию ((x_1 xor a_1) or (x_2 xor a_2) or . or (x_n xor a_n)).

Ответ написан более трёх лет назад
Михаил @cocain1988 Автор вопроса
Не совсем вас понял.

Mrrl

Михаил: Тогда расскажите, что на входе (если речь про ЯП, значит это строка — в каком формате?), что хотите получить и в каком виде (желательно, с примером), что уже умеете.

Михаил @cocain1988 Автор вопроса

На входе мы имеем строку с формулой вида: x( A(x)y( B(y)))(B(x)A(x)) пардон, не могу вывести значки кванторов и импликаторов, а на выходе должны получить тоже строку, но уже после операций по приведению к виду КНФ.

Mrrl

Михаил: Так напишите строку не со значками, а со словами. И обязательно с желаемым результатом — КНФ с кванторами это для меня что-то новое.

КНФ строится по табице истинности простым проходом по строкам таблицы. Так что задача сводится к нахождению таблицы истинности. Построить таблицу истинности можно двумя путями: 1. Привести формулу к виду, содержащему только дизъюнкции и конъюнкции — затем просто вычислить. 2. Написать разбор формулы: например построение дерева по формуле и последующее вычисление значения выражения. Можно посмотреть примеры решения задачи с арифметическим калькулятором и немного поменять. Случайно не было ли условий, какого вида могут быть входящие формулы? Это бы могло упростить построение

Ответ написан более трёх лет назад
Комментировать
Нравится Комментировать

Мне кажется, вы просто не поняли, что такое КНФ.

Вот пусть у нас есть булева функция f. Она зависит от n переменных x1, x2, . xn. Переменным можно сделать 2^n различных подстановок. На одних подстановках функция возвращает 1, на других — 0. Хотим это как-то закодировать булевой формулой.

Есть два типичных способа это сделать. Первый — описать все подстановки, дающие 1 — ДНФ. Второй — описать все подстановки, дающие 0 — КНФ. Нам нужно второе.

Посмотрим на КНФ. Это конъюнкция дизъюнкций, например такая:
(not x1 or x2) and (x1 or not x2 or x3).
То, что записано в скобках можно переписать чуть понятней:
(x1 = 0 or x2 = 1) and (x1 = 1 or x2 = 0 or x3 = 1).
Теперь, можно воспользоваться логикой, математической =), и еще раз переписать:
(not (x1 = 1 and x2 = 0)) and (not (x1 = 0 and x2 = 1 and x3 = 0)).
Что говорит последняя формула? Что функция дает единицу, если подстановка не содержит паттерна (x1 = 1 и x2 = 0) или (x1 = 0 и x2 = 1 и x3 = 0).

Итого, перебираем все подстановки, на которых функция дает 0, записываем такие подстановки в заперещенные паттерны, а потом просто записываем их в КНФ, как я описал выше.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *