 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Опр. 2. (о приведении к КНФ). Для любой формулы А можно найти такую формулу В, что А находится в КНФ и А В
(о приведении к КНФ). Для любой формулы А можно найти такую формулу В, что А находится в КНФ и А 
В.
Первое доказательство. Пусть А А1и А1 не содержит символов ~ и 
. Пусть В1 – ДНФ для формулы А*1. Тогда В*1 находится в КНФ и, кроме того, по принципу двойственности В*1 (А*1)* А1 А. значит В*1 удовлетворяет условию теоремы.
Второе доказательство. Применим все три этапа док-ва ДНФ, только в третьем этапе 
будет заменять сложение, а 
- умножение. В результате будет получена КНФ.
Билет 17.
«Теорема о приведении формулы к СДНФ и СКНФ формул ЛВ».
Поиск по сайту: