 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Опр. 3. Элементарная дизъюнкция является тавтологией тогда и только тогда, когда в ней присутствует одновременно какая-нибудь переменная и ее отрицание
Элементарная дизъюнкция является тавтологией тогда и только тогда, когда в ней присутствует одновременно какая-нибудь переменная и ее отрицание.
Если в элементарную дизъюнкцию входят какая-либо переменная и ее отрицание, то это тавтология в силу тавтологии А 
А. Тогда пусть ни одна переменная не входит в элементарную дизъюнкцию вместе с ее отрицанием. Пусть <Xi1,…,Xik> - список переменных от которых зависит А. переменная Хil принимает значение Л, если она входит в А как дизъюнктивный член, и значение И – в противном случае. На этой оценке все диз. члены А примут значение Л. Либо такой член – сама переменная Хil, либо ее отрицание. В последнем случае Хil не может быть диз. членом и, следовательно принимает значение И, а Хil – значение Л. Таким образом, формула А опровержима.
Однако для ЛП проблема разрешимости неразрешима. Об этом гласит теорема Черча.
Поиск по сайту: