42422

Нормальные формы формул. Проблема разрешения

Лабораторная работа

Математика и математический анализ

Теорема 1 о приведении к ДНФ: Для любой формулы А можно найти такую формулу В находящуюся в ДНФ что АВ. Формула В называется ДНФ формулы А. Конечно например все ДНФ данной формулы равносильны. Выделим среди ДНФ так называемую совершенную дизъюнктивную нормальную форму формулы.

Русский

2013-10-29

89 KB

11 чел.

Практическое занятие №9

 

Тема: Нормальные формы формул. Проблема разрешения.

Цель работы: овладение  умением приведения булевых функций к ДНФ (СДНФ), КНФ(СКНФ).

Теоретическая часть

В силу ассоциативности операций и как бы мы не расставляли скобки в выражениях  A1&A2&…&Ak,   всегда будем приходить к равносильным формулам. Каждое из этих выражений будем считать формулой, и называть соответственно многочленной конъюнкцией и дизъюнкцией формул .

Канонические виды формул

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

Пример 1:    .

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

Пример 2: .

Теорема 1 ( о приведении к ДНФ): Для любой формулы А можно найти такую формулу В, находящуюся в ДНФ, что АВ. Формула В называется ДНФ формулы А.

Аналогично читается теорема для КНФ (конъюнктивной нормальной формы).

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

Теорема 2:  Пусть формула А зависит от списка переменных . Говорят, что А находится в совершенной дизъюнктивной нормальной форме (СДНФ) относительно этого списка, если выполняются следующие условия:

  1.  А находится в ДНФ;
  2.  каждый дизъюнктивный член А является – членной конъюнкцией, причём на L – месте

(1L) этой конъюнкции обязательно стоит либо переменная X, либо её отрицание .

  1.  все дизъюнктивные члены А попарно различны.

Теорема 3 (о единственности СДНФ): Если В1 и В2 – совершенные дизъюнктивные нормальные формы формулы А относительно списка переменных , то В1 и В2 могут отличаться только порядком своих дизъюнктивных членов.

Аналогично определяется СКНФ.

СДНФ и СКНФ можно использовать для распознавания равносильности двух формул.

Критерий равносильности: две формулы А1 и А2 зависящие от списка переменных  и не равные тождественно Л (И), равносильны в том и только в том случае, если они приводятся к СДНФ (СКНФ), отличающимся лишь порядком своих дизъюнктивных (конъюнктивных) членов.

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

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

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

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

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

Это будет означать, что исходная формула является либо нейтральной, либо противоречием (всегда ложной).

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

Контрольные вопросы

  1.  Что называется дизъюнктивной нормальной формой булевой функции?
  2.  Дайте определение СДНФ и СКНФ переключательной функции.
  3.  В чем состоит проблема разрешимости для логики высказываний?
  4.  Какие есть разрешающие методы?

Индивидуальные задания

1. Найдите СДНФ  следующих формул, применяя соответствующие эквивалентные преобразования.

  1.  ~D 11) DС      21) СDС
  2.  DС  12) D~   22) DС
  3.  С~D  13) DС        23) СD
  4.  DС~   14)  С~D         24) DСС;
  5.  ~DС    15) DС   25) D~С
  6.  С~D  16) DСС26) DС;
  7.  ~D    17) С~С   27)  С~D;

8  D~С   18) ~DСС    28) DС

     9)  СD   19) СD    29) СD

    10) D~С    20) ~DСD; 30) DС.

2. Формула с тремя переменными имеет таблицу истинности. Какова наиболее простая эквивалентная ей формула?

А

В

С

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

0

0

0

1

1

0

0

1

1

1

1

1

0

0

0

1

0

1

0

1

0

1

1

0

0

0

1

0

1

0

0

0

1

0

0

1

0

1

1

0

0

0

1

1

0

0

0

1

1

0

0

0

0

1

1

1

1

0

1

1

0

0

0

0

0

0

0

1

0

1

1

1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

1

1

1

1

1

0

0

0

0

0

0

1

1

0

1

1

0

1

1

0

0

1

1

1

0

0

0

0

0

1

1

1

1

1

1

1

0

0

1

0

1

1

1

1

1

0

1

0

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

0

1

0

0

0

1

0

1

0

0

1

0

1

1

1

0

0

0

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

0

0

1

1

0

0

1

1

0

0

0

0

0

0

0

0

1

1

1

1

1

0

0

1

1

0

0

1

1

1

0

1

0

0

0

1

1

1

0

0

1

0

0

1

1

0

1

1

1

1

0

0

0

0

1

1

0

1

1

1

1

0

0

0

1

1

1

0

 

3.  Выпишите СКНФ всякой тождественно ложной формулы, содержащей одну переменную, две переменные, три переменные. Сколько элементарных дизъюнкций содержит СКНФ тождественно ложной формулы, состоящей из n переменных?

4.  Если СДНФ некоторой формулы из четырёх переменных содержит пять членов, то сколько членов содержит СКНФ этой же формулы?

5.  СКНФ некоторой формулы из трёх переменных содержит 6 членов. Какая из двух совершенных нормальных форм этой формулы проще -СДНФ или СКНФ?

6. Определите, какие из данных формул являются тавтологиями, приведя их к КНФ:

  1.  С
  2.  САС
  3.  С

Результаты задачи проверьте при помощи таблиц истинности.

7. Установите, какие из данных формул являются противоречием, приведя каждую из них к ДНФ:

1) (AB)~(A;   2) ((A((A));

3) (AC)C).

Результаты решения проверьте при помощи таблиц истинности.

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

1) (A;

2) ((;

3) CC;

4) ;

5) (( ACC;

6) CCCC.

PAGE  1


 

А также другие работы, которые могут Вас заинтересовать

79410. Жизненный путь личности 24.74 KB
  Сознание активность зрелось личности рассматриваются Рубинштейном как высшие личностные образования которые выполняют функции организации регуляции обеспечения целостности жизненного пути человека как субъекта деятельности. Рубинштейна выступает активность и творчество личности как организатора и преобразователя своей жизни. Ему принадлежит самое крупное лонгитюдное исследование личности и ее жизненного пути на основе которого была определена возрастная периодизация и онтогенез развития личности: детство юность выбор профессии...
79411. Смысл жизни личности в концепции Франкла 25.84 KB
  Смыслы не являются универсальными они уникальны для каждого человека в каждый момент его жизни. Однако существенным отличием Франкла является идея о том что обретение и реализация смысла всегда связана с внешним миром с творческой активностью человека в нем и его продуктивными достижениями. При этом он как и другие экзистенциалисты подчеркивал что отсутствие смысла жизни или невозможность его реализовать приводит к неврозу порождая у человека состояния экзистенциального вакуума и экзистенциальной фрустрации. Он выделяет три класса...
79412. Движущие силы и условия развития личности. Развитие как способ существования личности в представлениях отечественных исследователей 44.04 KB
  Развитие как способ существования личности в представлениях отечественных исследователей. Проблема постоянства и изменчивости личности Асмолов: Факторы развития личности: органические предпосылки среда сама личность. Двухфакторная детерминация развития личности наследственность среда определяет постановку проблемы о соотношении биологического и социального в человеке.
79413. Психологический возраст и социальная зрелость личности. Подходы к определению критериев социальной зрелости личности 34.66 KB
  Следует отметить что и проблема хронологического возраста имеет большое значение для психологии при исследовании жизненного пути личности выделения его основных этапов т. Вместе с тем в современной науке все большее распространение приобретает полиизмерительный подход к изучению возраста как дифференцированной меры времени человеческой жизни. ^ Самооценка возраста. При постановке проблемы возраста которая принята в психологии практически неисследованным остается вопрос о субъективном отношении человека к собственному возрасту о том...
79414. Категория «личность» в системе наук. Междисциплинарный статус проблемы 26.59 KB
  Междисциплинарный статус проблемы Первое отличие познавательной ситуации исследования психологических закономерностей становления и развития личности состоит в том что в психологии до сих пор возникают серьезные затруднения при попытках очертить сферу эмпирических фактов относящихся к предмету психологического изучения личности. Многогранность феноменологии личности отражающая объективно существующее многообразие проявлений человека в истории развития общества и его собственной жизни превращает исходный вопрос любого познания вопрос об...
79415. Проблемы, связанные с изучением личности. Общие представление о личности в психологии 31.43 KB
  Общие представление о личности в психологии Слово личность в английском языке происходит от латинского person. Таким образом с самого начала в понятие личность был включен внешний поверхностный социальный образ который индивидуальность принимает когда играет определенные жизненные роли некая личина общественное лицо обращенное к окружающим. Эта точка зрения совпадает с мнением современного непрофессионала который обыкновенно оценивает личность по критериям обаяния умения вести себя в обществе популярности физической...
79416. Процессы планирования. Планирование ресурсов проекта 50.09 KB
  Планирование ресурсов проекта. Стандарты на процесс проектирования ПО: ограничения налагаемые на применяемые методы проектирования например распределение ресурсов использование прерываний и структур управляемых событиями использование динамических задач повторный вход использование глобальных данных механизм обработки исключительных ситуаций и обоснования для их использования; Спецификация системы подсистемы: должны быть описаны требования к ресурсам вычислителя к аппаратуре коэффициенту использования ресурсов аппаратуры ПО...
79417. Стратегии и методы проектирования информационных систем 41.51 KB
  Данный подход рекомендуется для организаций с узкоспецифическими требованиями не нуждающихся в общем совершенствовании процессов. Нисходящий подход проектирования Сверхувниз подразумевает собой разработку универсальной системы удовлетворяющей потребности нескольких предприятий. Данный подход рекомендуется для относительно зрелых организаций с устоявшимися бизнеспроцессами которые стремятся вложить все необходимые ресурсы в законченный продукт.
79418. Анализ объекта автоматизации. Методологии анализа 137 KB
  Функциональные модели удобны, когда производится автоматизация производства с хорошо описанным производственным циклом. Модель показывает управление объектом автоматизации. В данных моделях выделяем функции у объектов, основные связи между функциями, формальные ресурсы для функций, входы и выходы у функций