Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 24
Текст из файла (страница 24)
ТОГда тОЧКа О1О2... О „, в координатах х1, хт, ..., х„будет соответствовать точке 00...0 в координатах х«1, х«2, ..., х'„. Используя разложение (2.21) булевой функции в точке 00...0 в координатах х«1, х«2, ..., х„' и заменяя каждую переменную х! на х; 9 «г;, з = 1, 2,..., и, получаем теорему о разложении булевой функции 1(х1, хт, ..., х„) в тачке «Г1 «Г2 Теорема 2А. Любая булева функция 1(х1, хт, ..., х„) определяется своим значением в точке огот...о„и значениями всех своих производных д1 д21 д 1 дх;,' дх;,дх;,' ' ' дх,дхт...дх в точке 0000 равны иуто, остальные — единице.
Согласно вырвнонивз (2.21) имеем ровлононне рассматриваемой булавой функкии в тачке 0000 в виде в этой точке согласно выражению Л*,**, ",")=Л...", .)»Е — ~ ь д1 дх; — а1»З -.а» д2 уз ос(Х19о«)га ф: ~ Зс(х;Щсг)(х 9о)ф... У «а«аз...а» «ззу дьу ) и 01«З "1«З чаи« -. «ь-11«з диуа и Е д д ~ Й(х; гТг о;); (2.22) 41, 12,, зь, ..., т Е (1, 2, ..., и), Э(41, 42, ..., 41, .. » т„) Найдем разложение рассматриваемой булевой функции 1(х1, хт, хз, х4) в точке 1010. Производные дУ дУ дУ дтпл д21 дтпл дтпл д21 дхт' дхз' дх ' дх дхт' дх дхз' дх дхз' дхтдх ' дх дх дата дзу дзу дх1 дхт дхз дх1 дх2 дх4 дх1 дхз дх равны нулю в точке 1010, остальные — единице.
Согласно теореме 2.3 имеем разложение булевой функции в виде у (х1! х2«хз«Х4) = (х1 цг 1) «2г (х1 91) х.1 Яхт (хз Щ 1) ° х.1 Щ 9 (х1 чг 1) ' хт(хз йг 1) х4 = х1 «Тг хгх4 йг хтхзх4 «зг хгхтхзх4. $2.7. Исчисление высказываний Исчисление высказываний как формальную теорию можно определить с помощью аксиоматического метода. Аксиоматическая (формальная) теория Т считается определенной, если выполнены следующие условия: 1) задана некоторое счетное множеспзво, т. е. множество, элементы которого могут быть взаимно однозначно сопоставлены элементам натурального ряда 1, 2, ... символов — символов теории Т.
Конечные последовательности символов теории называются выражениями теории Т; 129 Гл. 2. Математическая логика 128 3 2 7 Исчисление высказываний 2) имеется подмножества выражений теории Т, называемых формулами теории Т (формулы теории Т часто называют правильно посгпроенными формулами).
Чтобы определить, является ли выражение формулой в теории, существует эффективная процедура; 3) выделено некохорое множество формул, называемых аксиомами Гпсории Х; 4) имеется конечное множество В1, Вт, .. ч В„отношений между формулами, называемых правилами вывода. Для каждого В; существует натуральное у такое, что для всякого множества, состоящего из у формул, н для всякой формулы Р эффективно решается вопрос о том, находятся ли данные у формул в отношении В; с формулой Е, и если да, то Г называется непосредственным следствием данных у формул по правилу В;. Выводом в Т называется всякая последовательность Г1, Г2, ..., Г формул такая, что для любого 1 формула г) есть либо аксиома теории Т, либо непосредственное следсхвне каких-либо предыдуших формул.
Формула Г теории Т называехся теоремой теорий Т, если существует такой вывод в Т, в лахором последней формулой является В; этот вывод называется выводом формулы Г. В общем случае может не существовать эффективной процедуры, с помощью которой можно определить по данной формуле, сущесхвует ли ее вывод в теории Т. Формула, для которой такая процедура существует, называется разрешимой в этой теории, в противном случае — неразрешимой. Иначе говоря, для неразрешимых формул нельзя построить алгоритм выяснения свойсхва формулы быть теоремой, для этого хребуются все новые и новые озарения (изобрехахельства), не поддающиеся формализации.
Используя понятие аксиоматической теории Т, определим исчисление высказываний в дизъюнктивном базисе Буля. 1. Символами теории Т являются Ч,, (, ) и буквы т; с целыми положительными числами в качестве индексов: т1, тт, ... Символы Ч, называются связками, а буквы тп; — щюпозиииональными буквами. 2. а) Все пропозициональные буквы являются формулами; б) если А и  — формулы, хо (АЧВ) и (А) — также формулы; в) выражение являехся формулой хогда и только тогда, когда это может быть установлено с помощью п.
а) и б). Таким образам, всякая формула исчисления высказываний есть некая пропозициональная формула, построенная из пропозициональных букв с помощью связок Ч и 3. Каковы бы ни были формулы А, В, С теории Т, следующие формулы есть аксиомы Т: АЧА-ьА, АЧВ-+ВЧА, А-+ АЧВ, (В-+ С) -й(АЧВ-+ АЧС), ,где запись и сг -+ уу эквивалентна записи сг Ч 1у'. 4.
Правила вывода исчисления высказываний следующие. Правило подстановки; если сг — выводимая формула н вме- сто любой переменной в этой формуле всюду произвести подста- новку любой формулы, то новая формула хакже является выводи- мой. Правило заключения: если ст -+ Д и ст — выводимые формулы, то )3 также выводимая формула; Например, если высказывания А и А -+ (а -+ А) истинны, то высказывание д -+ А также является истинным согласно правилу заключения. Аналогично можно определихь и другие булевы алгебры: алгебру Вебба А = (М, о); алгебру Шеффера А = (М, )); импвикативную алгебру А =' (М, -+, 0); коимпликативную алгебру А = (М, -ч, 1); алгебру Жегалкина А = (М, Й, 9, 1).
Логический эьнюд широко искользуегся в современных ииформвкионных технологиях при рюработке экспертных систем. Рассмотрим механизм логи- ческого вывода ив примере прогнозирования месторондений полезных ископаеПусть геологическая партия после изучения олного ив районов Тянь-Швня получила впостериориую информапию вила:  — если обиарунеи крутопвдвющкй сфвлерит, то имеем иерулное тело; уз — азимут падения доломита равен 160'; уз — интервал угла падения рудного тела, содернвщего варит равен 35-60', Ул — пологое залегание квэькитв имеет азимут падения 300; 2. Уз — гвленит имеет ввнмут падения 160', уе — полезное ископаемое с крутопвдвющнм залеганием и азимутом падения от б' до 270' является рудным телом; Уà — ВанМут Падсиня, Равный 271-360', имеют рудные тела иэн крутопв- лвющие полезные ископаемые; з — пологое залегание иерудного тела имеет азимут падения 320'.
ель геологоравзедки — кропюзироввиие месторондення рудного теэв. Априорная информапия по этому району: — крутоввдвющим залеганием считается залегание с углом падения, превы- шающим 30'; — результат мннервэиаапни иерудного тела — доломит, варит, квльпит; — рудная минервлиаапия крелставлеив преимущественна гвленнтом и сфв- леритом, причем последний нередко обраауег обособленные зелени. Обозначим первичными термами: хà — рудное тело, Ц~ — нерудное тело; хз — галеннт, сфалерит;эз — доломит, варит, кальннт.
Угол падению хз — пологое залегание (0-30'), хз — крутопадающее за- легание (сзыше ЗО'); взимУт надеина: х< — от 271' до 360', Цз — от 0' до 270з 5 з. л. Газзаев 131 $ 2 7 Исчисление еыскоэыеомий Гл. 2. Моглемотоическол логика 130 =У1УзхаЧ хгУзха = Узха. 2) 8г /; — 00000101 0101 0101, а=з,т,в Й /1~ = Ч(5, 7, 13, 15) = 1=2,7,Ь х1х2Уэха Ч х1хзхзхаЧ Ч х1хзхвха Ч х1хзхзха = Угхзха Ч х1хзха х2ха Рис. 2.9 Секеениией нааыэается высказывание, записываемое в вице Р -а Ф, тле Р— конъюикдия формул (/а), Ф вЂ” ливьюнкция формул (Чгг ), аэо /1 ~ 'т/ 77„ и читаемое неформально как "Р влечет Ф" или формально — вР импдици.
руст Ф". Левая часть секвеипии называется англепедемгоом (оосмлкой), прввая— сркпедемгоом (комсекееммтом, заключением). Зги термикы являээтся терминами схоластической лагявн. Используя ээеленные обоаначеиня хн Уо 1 ю 1, ..., 4, и секвенцнальнае исчисление, аиостериориую информацию аюгишем в следующем виде: /1 зз хзпв -в Уг, /2 = хз -а ха, /з гл хгпз -+ Уэ, /а зз Узхэ -а ха, /э =хз-эха, /в =УэУа а ха, /т = ха ЧУз -+ ха, /в =хгхэ -эха. Система секвенций (/а) месовмесоано, если антепелеит этой системы Й /, тоидестэевиа равен нулю. В пространстве Р(хг, хз, хэ, ха) характеристические векторы секвенций /, имеют вида /1 хг, хз, хэ, ха — 111111111111 0011, /2 хю хз, хэ, ха — 1010111110101111, /э хг, хз, хэ, ха — 1111111111001111, /а хг, хз ~ хэ, ха — 1101 1111 1101 1111, /э хг, хз, хэ, ха — 1111101011111010, /в хг, хз, хв, ха — 0111011111111111, /т хг, хз, хз, ха — 011101110101 0101, /з хг, хз, хз, ха — 1101110111111111, где каидый характеристический вектор прецставляет собой аначення соответ- ствующей функция /1(хг, хз, хэ, ха) в точках О, 1, 2, ..., 15.
Аитецедент й /, гй ОООООООО00000000 равен нулю, следовательно, секвеициальная система (Я противоречива. Для пороидення всех непротиворечивых секвенциальнылснстем,испальзуясвойство вритичности пакрьатия лвоичныц таблиц,предлоиим следующий алгоритм. 1. Построим двумерную таблицу Я (табл. 2.32), каидая строка которой взаимно одноаизчно саатвегспгует секвеицни /1, столбец — точке пространства Р(хг, хз, хэ, ха) и 1-я строка вредставляег собой /;(хг, хз, хз, ха) = /,(хг, хз, хэ, ха) Е1 Таблица 2.32 2.
Покрываем столбцы строками. Строки /2, /э, /г, /в являются обявательнымн, онн образуют нокрэовие гг = (/,/ 1 = 2, 5, 7, 8). Покрытие ядерное, следовательно, аио одко. В общем случае алгоритмом Петрика пораидаем все покрытия таблицы О. 3. Удаляем из каидога покрытия любой злюлетат. С учетом свойства кри- тичности покрытия очевидн, очевидно что и//1 является иепраткворечивай системой. манные удаленяя ив покрытий, получаем все мнвкество непратк- Проведя возмоиные каречивмц секвенциониых систем. Для исследуемого случая имеем четыре непротиворечивые секвенциальные юютемыг 1) х//2; 2) и//э', 3) гг//т, 4) з//э. Вычисляем непротиворечивые антепеденты. Ц Й /; — 0101000001010000, в,т,з Й /1 =У1Узхэха Чхгхзхэха Чхгйзхэха Ч хгхзхзха = ° этз !1 Па основании истинности этого аитецецеита закэзочаем, что реаультвт мниерализапии неруднаго тела — доломит барит, кальдит — проявляется в зоне с азимутом падения ат 271' до 360'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
