5 - Исчисление предикатов . Построение теории P. Правила естественного вывода. Глобальные свойства теории P (1059975), страница 2
Текст из файла (страница 2)
Рассмотрим произвольный вывод Z1 , Z2 , . . . , Zk из гипотез Γ длины k с конечной формулой Y = Zk . Формула Yесть либо логический закон, либо гипотеза, либо получена по правилу модус поненс, либо поправилу всеобщности. В первых двух случаях рассуждения те же, что и при k = 1. В третьемслучае в выводе есть формулы Zj и Zl = Zj → Y . В силу предположения индукции формулыZj θ и (Zj → Y )θ истинны в M .
В этом случае правило модус поненс гарантирует истинностьв M формулы Y θ.Если Y получена по правилу обобщения из формулы Zj для некоторого j, то Y = ∀xZj .В силу структурного требования формула Zj получена из гипотез Xi1 , . . . , Xis , каждая изкоторых не имеет свободных вхождений переменной x. Для всякого объекта a того же сорта,что и x из истинности формул Xi следует истинность (Xi )xa (это то же самое, что и Xi ). В силуиндуктивного предположения заключаем, что M |= ((Zj )xa )θ, а в силу интерпретации кванторавсеобщности это равносильно истинности (∀x X)θ, т.е. Y θ. IÌÃÒÓÌÃÒÓЛемма об истинности при фиксированной оценке и ее следствие.ÔÍ-12ÔÍ-125.3. Глобальные свойства теории PÌÃÒÓÌÃÒÓПоследняя секвенция вытекает из правила p2.ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÌÃÒÓ3. Исчисление высказываний3.1.
Введение . . . . . . . . . . . . .3.2. Основные положения теории N3.3. Правила естественного вывода3.4. Глобальные свойства теории N....2323242530.......35353639424447495. Исчисление предикатов5.1. Построение теории P . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . .5.2. Правила естественного вывода . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5.3. Глобальные свойства теории P . . . . . . . . . . . . . . . . . . . . . . . . . . . . .515152546. Алгоритмы на графах6.1. Введение . . . .
. . . . . . . . . . . .6.2. Деревья . . . . . . . . . . . . . . . . .6.3. Остов графа наименьшего веса . . .6.4. Задача о путях в размеченном графе6.5. Циклы, разрезы и задача Эйлера . .555557606266...............................................................................4. Алгебра предикатов4.1.
Предикаты и кванторы . . . . . . . . . . .4.2. Логико-математические языки . . . . . . .4.3. Переименования и подстановки . . . . . .4.4. Семантика логико-математического языка4.5. Логические законы . . . . . . . . . . . . .4.6. Замены . . . . . . . . . . . . . . . . . . . .4.7. Упрощение формул .
. . . . . . . . . . . .........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ÔÍ-12ÔÍ-12..........ÌÃÒÓ18181921.....ÔÍ-122. Логика высказываний2.1. Алгебра высказываний . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2. Тавтологии и эквивалентность формул . . . . . . . . . . . . . . . . . . . . . . . . .2.3. Способы получения эквивалентных формул . . . . . . . . . . . . . . . . . . . . . ......ÌÃÒÓ.....11291112ÔÍ-1273ÌÃÒÓÔÍ-121. Булевы функции1.1. Булевы алгебры . .1.2. Булевы функции . .1.3.
ДНФ и КНФ . . . .1.4. Критерий Поста . .1.5. Минимизация ДНФÔÍ-12ÌÃÒÓОГЛАВЛЕНИЕÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
