Файл: Дизъюнктивная и конъюнктивная совершенные нормальные формы.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.11.2023
Просмотров: 65
Скачиваний: 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.Все полученные конъюнкции связываем операциями дизъюнкции.Алгоритм построения СКНФ по таблице истинности
Нормальной форме логической формулы не свойственна эквивалентность, отрицание формул неэлементарного типа и знаки импликации.Выделяют такие виды формы нормального типа:•КНФ (конъюнктивная нормальная форма), где подразумевается конъюнкция того или иного количества дизъюнкций, как пример,(A∨ ∨C)Λ(A ∨C);•ДНФ (дизъюнктивная нормальная форма), где осуществляется дизъюнкция конъюнкций, как пример, .(A Λ Λ C) ∨ (A Λ C);СКНФСовершенная КНФ является разновидностью конъюнктивной нормальной формы, удовлетворяющей такие условия:•отсутствие одинаковых элементарных дизъюнкций;•дизъюнкции не содержат одинаковые переменные;• все дизъюнкции содержат каждую переменную из входящих в конъюнктивную НФ такого типа.Если функция равна нулю, то в случае каждого набора записывают сумму, причем с отрицанием берутся те переменные, которые равны единице.СДНФСовершенная ДНФ является разновидностью дизъюнктивной нормальной формы, удовлетворяющей следующие условия:• отсутствие одинаковых элементарных конъюнкций;• конъюнкции не свойственно обладать одинаковыми переменными;в случае любой конъюнкции элементарного типа имеет место быть переменная, входящая в такую нормальную дизъюнктивную форму. При этом в одинаковом порядке.Все формулы булевого типа, которые не относятся к тождественно ложным, могут быть представлены в совершенной разновидности ДНФ, при этом в единственном возможном варианте.Построение СДНФ согласно таблице истинностиЕсли функция соответствует единице, то в случае каждого набора записывается произведение, причем с отрицанием берутся те переменные, которые равны нулю.Нахождение СКНФ и СДНФ: Примеры Согласно таблице истинности записать логическую функцию:РЕШЕНИЯПрибегнем к правилу построения совершенной ДНФ
Получаем такую СДНФF(x1 ,x2,x3)= (
)
) 
) Задействовав правило её построенияПолучаем СКНФF(x1 ,x2,x3)= (
1) формула является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных х1, х2, …, хk, причем на i-м месте этой дизъюнкции стоит либо переменная хi, либо ее отрицание;2) все элементарные дизъюнкции в такой КНФ попарно различны.Пример: (х1 ∨ х2 ∨ х3) ∧ ( ¬ х1 ∨ ¬ х2 ∨ х3)Заметим, что любую логическую функцию, не равную тождественно 0 или 1, можно представить в виде СДНФ или СКНФ.Алгоритм построения СДНФ по таблице истинности1.Выбрать все строки таблицы, в которых значение функции равно единице.2.Для каждой такой строки записать конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае — ее отрицание.3.Все полученные конъюнкции связываем операциями дизъюнкции.Алгоритм построения СКНФ по таблице истинности
-
Выбрать все строки таблицы, в которых значение функции равно нулю.
Нормальной форме логической формулы не свойственна эквивалентность, отрицание формул неэлементарного типа и знаки импликации.Выделяют такие виды формы нормального типа:•КНФ (конъюнктивная нормальная форма), где подразумевается конъюнкция того или иного количества дизъюнкций, как пример,(A∨ ∨C)Λ(A ∨C);•ДНФ (дизъюнктивная нормальная форма), где осуществляется дизъюнкция конъюнкций, как пример, .(A Λ Λ C) ∨ (A Λ C);СКНФСовершенная КНФ является разновидностью конъюнктивной нормальной формы, удовлетворяющей такие условия:•отсутствие одинаковых элементарных дизъюнкций;•дизъюнкции не содержат одинаковые переменные;• все дизъюнкции содержат каждую переменную из входящих в конъюнктивную НФ такого типа.Если функция равна нулю, то в случае каждого набора записывают сумму, причем с отрицанием берутся те переменные, которые равны единице.СДНФСовершенная ДНФ является разновидностью дизъюнктивной нормальной формы, удовлетворяющей следующие условия:• отсутствие одинаковых элементарных конъюнкций;• конъюнкции не свойственно обладать одинаковыми переменными;в случае любой конъюнкции элементарного типа имеет место быть переменная, входящая в такую нормальную дизъюнктивную форму. При этом в одинаковом порядке.Все формулы булевого типа, которые не относятся к тождественно ложным, могут быть представлены в совершенной разновидности ДНФ, при этом в единственном возможном варианте.Построение СДНФ согласно таблице истинностиЕсли функция соответствует единице, то в случае каждого набора записывается произведение, причем с отрицанием берутся те переменные, которые равны нулю.Нахождение СКНФ и СДНФ: Примеры Согласно таблице истинности записать логическую функцию:РЕШЕНИЯПрибегнем к правилу построения совершенной ДНФ
Получаем такую СДНФF(x1 ,x2,x3)= (
) ) ) Задействовав правило её построенияПолучаем СКНФF(x1 ,x2,x3)= (