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

Опр. 2. Пусть формула А зависит от списка переменных <Xi1, , Xik> и А не тождественно-истинная

Пусть формула А зависит от списка переменных <Xi1, …, Xik> и А не тождественно-истинная. Тогда такая формула В, что А В и В находится в СКНФ относительно списка переменных <Xi1, …, Xik>.

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

Можно доказать эту теорему в аналогии с док-вом СДНФ. Только в законах идемпотентности, равносильностях заменяются на .

 


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