Файл: Дизъюнктивная и конъюнктивная совершенные нормальные формы.docx

Скачать файл (0,87Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 24.11.2023

Просмотров: 15

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

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

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

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

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

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

Определение. Формулу называют элементарной конъюнкцией, если она образованна конъюнкцией некоторого числа переменных или их отрицаний.

Примеры: y, ¬ y, х1 ∧ ¬ х2 ∧ х3 ∧ х4

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

ДНФ записывается в следующей форме: F1 ∨ F2 ∨ ... ∨ Fn, где Fi - элементарная конъюнкция

Примеры: ¬ х1 ∧ х2 ∨ х1 ∧ ¬ х2 ∨ х1 ∧ ¬ х2 ∧ х3, ¬ y1 ∨ y1 ∧ y2 ∨ ¬ y2

Определение. Логическая формула от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:

1) формула является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х1, х2, …, хk, причем на i-м месте этой конъюнкции стоит либо переменная хi, либо ее отрицание;

2) все элементарные конъюнкции в такой ДНФ попарно различны.

Пример: (¬ х1 ∧ х2 ∧ х3) ∨ (х1 ∧ ¬ х2 ∧ х3) ∨ (х1 ∧ х2 ∧ ¬ х3)

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

Определение. Формулу называют элементарной дизъюнкцией, если она образована дизъюнкцией некоторого числа переменных или их отрицаний.

Примеры: ¬ х3, х1 ∨ х2, х1 ∨ х2 ∨ ¬ х3

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

КНФ записывается в следующей форме: F1 ∧ F2 ∧ ... ∧ Fn, где Fi - элементарная дизъюнкция

Примеры: (х1 ∨ ¬ х2) ∧ х3, (х1 ∨ х2) ∧ ( ¬ х1 ∨ х2 ∨ х3) ∧ ( х1 ∨ ¬ х2 ∨ ¬ х3)

Определение. Логическая формула от k переменных называется совершенной конъюнктивной нормальной формой (КДНФ), если:

1) формула является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных х1, х2, …, хk, причем на i-м месте этой дизъюнкции стоит либо переменная хi, либо ее отрицание;

2) все элементарные дизъюнкции в такой КНФ попарно различны.

Пример: (х1 ∨ х2 ∨ х3) ∧ ( ¬ х1 ∨ ¬ х2 ∨ х3)

Заметим, что любую логическую функцию, не равную тождественно 0 или 1, можно представить в виде СДНФ или СКНФ.

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

1.Выбрать все строки таблицы, в которых значение функции равно единице.

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

3.Все полученные конъюнкции связываем операциями дизъюнкции.

Алгоритм построения СКНФ по таблице истинности

Выбрать все строки таблицы, в которых значение функции равно нулю.

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

3.Все полученные дизъюнкции связываем операциями конъюнкции.

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

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

Т.к. на большинстве строк таблицы истинности значение функции равно 1, то построим СКНФ. В результате получим следующую логическую формулу:

F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Проверим полученную формулу. Для этого построим таблицу истинности функции.

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

Построение СКНФ и СДНФ по таблице истинности

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

Выделяют такие виды формы нормального типа:

•КНФ (конъюнктивная нормальная форма), где подразумевается конъюнкция того или иного количества дизъюнкций, как пример,

(A∨

∨C)Λ(A ∨C);

•ДНФ (дизъюнктивная нормальная форма), где осуществляется дизъюнкция конъюнкций, как пример, .

(A Λ

Λ C) ∨ (A Λ C);

СКНФ

Совершенная КНФ является разновидностью конъюнктивной нормальной формы, удовлетворяющей такие условия:

•отсутствие одинаковых элементарных дизъюнкций;

•дизъюнкции не содержат одинаковые переменные;

• все дизъюнкции содержат каждую переменную из входящих в конъюнктивную НФ такого типа.

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

СДНФ

Совершенная ДНФ является разновидностью дизъюнктивной нормальной формы, удовлетворяющей следующие условия:

• отсутствие одинаковых элементарных конъюнкций;

• конъюнкции не свойственно обладать одинаковыми переменными;

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

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

Построение СДНФ согласно таблице истинности

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

Нахождение СКНФ и СДНФ:

Примеры Согласно таблице истинности записать логическую функцию: