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

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

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

Первое доказательство. Пусть А А1и А1 не содержит символов ~ и . Пусть В1 – ДНФ для формулы А*1. Тогда В*1 находится в КНФ и, кроме того, по принципу двойственности В*1 (А*1)* А1 А. значит В*1 удовлетворяет условию теоремы.

Второе доказательство. Применим все три этапа док-ва ДНФ, только в третьем этапе будет заменять сложение, а - умножение. В результате будет получена КНФ.

 

Билет 17.

«Теорема о приведении формулы к СДНФ и СКНФ формул ЛВ».


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.003 сек.)