Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Конъюнктивные нормальные формы





Определение. Элементарной дизъюнкцией называется дизъюнкция литералов (переменных или их отрицаний), взятых не более чем по одному разу.

Например, дизъюнкции , , 1 являются элементарными. Причем первая элементарная дизъюнкция имеет ранг (число литералов) 2, вторая - 3, а третья - 0.

Следующие дизъюнкции: , , , , 0 не являются элементарными.

Определение. Элементарная дизъюнкция булевой функции , содержащая n литералов, называется полной.

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

Например, КНФ имеет длину, равную 3.

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

Определение. Две (или несколько) КНФ, реализующих одну и ту же булеву функцию F, называются эквивалентными (или равносильными).

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

Например, - СКНФ функции F, заданной вектором значений таблицы истинности w(F)=(01100111).

Отметим, что КДНФ является единственной (с точностью перестановки множителей) для конкретной булевой функции F.

 

Любую булеву функцию F, заданную формулой, можно с помощью основных равносильностей преобразовать к КНФ, а затем к СКНФ.

Пример. Привести к виду СКНФ булеву функцию F = .

Решение. С помощью основных равносильностей преобразуем к КНФ:

= = = =

=

― КНФ.

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

Применяя закон склеивания (в обратном порядке: ), дополняем дизъюнкции , до полных элементарных дизъюнкций:

.

Так как , то после сокращения одинаковых конъюнкций получаем СКНФ: F .

Составим таблицу истинности для булевой функции F = (функция из предыдущего примера). Отметим связь между СКНФ и таблицей истинности.

Таблица истинности СКНФ

Элементарные дизъюнкции СКНФ
           
           
             
             
             
           
           
             

В общем случае также можно вывести закономерности построения СКНФ по таблице истинности булевой функции, что является очень удобным.

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

Пример. По таблице истинности составить СКНФ.

 

F
       
       
       
       
       
       
       
       

 

Решение: F .

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

Решение: Применяя формулу , из ДНФ получаем КНФ:

.

Применяя закон склеивания (в обратном порядке: ), дополняем дизъюнкции , до полных элементарных дизъюнкций:

.

Так как , то после сокращения одинаковых дизъюнкций получаем СКНФ:

.

Таблица истинности СКНФ

Элементарные дизъюнкции СКНФ
           
           
             
           
             
             
             
             

 







Дата добавления: 2014-10-22; просмотров: 947. Нарушение авторских прав; Мы поможем в написании вашей работы!




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


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


Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...


Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Неисправности автосцепки, с которыми запрещается постановка вагонов в поезд. Причины саморасцепов ЗАПРЕЩАЕТСЯ: постановка в поезда и следование в них вагонов, у которых автосцепное устройство имеет хотя бы одну из следующих неисправностей: - трещину в корпусе автосцепки, излом деталей механизма...

Понятие метода в психологии. Классификация методов психологии и их характеристика Метод – это путь, способ познания, посредством которого познается предмет науки (С...

ЛЕКАРСТВЕННЫЕ ФОРМЫ ДЛЯ ИНЪЕКЦИЙ К лекарственным формам для инъекций относятся водные, спиртовые и масляные растворы, суспензии, эмульсии, ново­галеновые препараты, жидкие органопрепараты и жидкие экс­тракты, а также порошки и таблетки для имплантации...

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

Йодометрия. Характеристика метода Метод йодометрии основан на ОВ-реакциях, связанных с превращением I2 в ионы I- и обратно...

Броматометрия и бромометрия Броматометрический метод основан на окислении вос­становителей броматом калия в кислой среде...

Studopedia.info - Студопедия - 2014-2025 год . (0.013 сек.) русская версия | украинская версия