3 - Исчисление высказываний. Введение. Основные положения теории N. Правила естественного вывода. Глобальные свойства теории N (1059974), страница 4
Текст из файла (страница 4)
В данном случае в качестве такого алгоритма может рассматривать процедуру построения истинностной функции и проверки ее на наличие значений 0. Отсутствие таких значенийозначает, что функция является постоянной, а формула — тавтологией, т.е. выводимой в теории N . Указанная процедура выполняется за конечное число алгебраических операций и даетоднозначный ответ, выводима формула или нет. В этом смысле теория N является разрешимойтеорией.Еще один вопрос, связанный с построением формальной теории — независимость аксиом.Аксиома формальной теории не зависит от остальных аксиом этой теории, если эта аксиомане является выводимой формулой в теории, которая получается из исходной удалением указанной аксиомы. Если ни одна из аксиом формальной теории не является логическим следствиемостальных, то говорят о независимой системе аксиом.Система аксиом теории N является независимой в том смысле, что удалив одну из схемаксиом теории, мы не сможем вывести ни одну из формул, получаемой в рамках этой схемыаксиом.
Как можно доказать утверждения подобного рода. Напомним, что в формальной теории формулы теряют всякий содержательный смысл; например, знак импликации может означать какую угодно бинарную операцию на множестве возможных значений переменных, а самипеременные могут быть связаны с любыми математическими объектами. Придание смысласимволам формальной теории называют интерпретацией этой теории.
В данном случае множество всех высказываний как область изменения переменных и естественный логический смыслсимволов операций — это одна из возможных интерпретаций исчисления N .Интерпретация формальной теории строится в рамках какой-либо другой математическойÌÃÒÓÔÍ-12ÌÃÒÓ33ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-123. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙÌÃÒÓÌÃÒÓÔÍ-12теории. Надежность интепретации определяется надежностью той теории, в которой интепретируется исчисление. Так, суждения о непротиворечивости, полноте и разрешимости исчисления N получены в рамках так называемой теории булевых функций, т.е. теории функций собластью изменения переменных и функций 0 и 1.
В этом смысле подобные суждения носятотносительный характер. В математике считают абсолютно надежными теории, связанные сконечными множествами. В этом смысле утверждения о непротиворечивости, полноте и разрешимости исчисления N являются абсолютными. Утверждение о независимости системы аксиомтоже будет абсолютным, если оно будет получено на базе какой-либо конечной интерпретации.Теорема 3.8. Схемы аксиом исчисления N не зависят друг от друга.ÔÍ-12ÌÃÒÓJ Наиболее просто доказать независимость схем, начиная с 3-й, так как все эти схемы используют, кроме импликации, еще одну операцию, которая участвует лишь в двух других схемахаксиом.
Можно ограничиться двухэлементной областью изменения переменных и стандартнойинтепретацией операций, кроме одной. В табл. 3.1 приведены схемы аксиом и новая интерпретация одной из операций. При этой интерпретации указанная схема аксиом при некоторыхзначениях входящих в нее формул принимает значение 0, в то время как остальные аксиомыимеют постоянное истинностное значение 1. Изменение интерпретации не затрагивает правилаmodus ponens, так что при удалении указанной схемы аксиом мы получаем теорию, в которой все выводимые формулы — тавтологии, но некоторые формулы, получаемые из указаннойсхемы, выводимыми не являются.
Это и означает, что указанная схема аксиом не зависит отостальных.Независимость первых двух схем доказать сложнее, поскольку они касаются импликации,затрагивающей все схемы. Ответ можно найти, рассмотрев в качестве области изменения переменных множество из трех целых чисел {0, 1, 2} и выбрав следующие интерпретации операций:x ∧ y = min{x, y}, x ∨ y = max {x, y}, ¬x = 2 − x. Для импликации потребуем выполнения условия, что x→y = n тогда и только тогда, когда x 6 y. При поставленных условиях схемы 3, 4, 6,7, 10, 11 будут давать формулы с тождественным значением n, а в силу условия, наложенногона импликацию, значение Y будет тождественное n при X ≡ n и X → Y ≡ n.
Недоопределенность импликации можно использовать для получения нужных значений первых двух схемаксиом и для обеспечения тождественного значения n схем 5, 8, 9.Положим x → y = 0 при x > y. Тогда схема X → (Y → X) будет иметь значение 0 приX = 1, Y = 2, в то время как остальные аксиомы будут давать тождественное значение 2.Действительно, в схеме 2 исключаем случай X > Y или X 6 Z, так как тогда она имеет вид0→W или W →1. Значит, Z < X 6 Y и схема имеет вид 2→(X →0→0). Но X > Z > 0, значит,X → 0 = 0 и 2 → (X → 0 → 0) = 2 → (0 → 0) = 2 → 2 = 2. В схеме 5 исключаем случай X > Yили X > Z, когда она имеет значение 2.
Но тогда X 6 min{Y, Z} и X → Y ∨ Z = 2. ПоэтомуX → Y → (X → Z → (X → Y ∧ Z)) = X → Y → (X → Z → 2) = 2. В схеме 8 исключаем случайX > Z или Y > Z. Тогда max {X, Y } 6 Z, X ∨ Y → Z = 2 и схема 8 имеет тождественноезначение 2. В схеме 9 исключаем случай X > Y . Но тогда X 6 Y , ¬Y 6 ¬X и формула имеетвид 2 → 2.Положим x → y = 1 при x > y. Тогда схема 8 будет иметь значение 1, например, при X = 1,Y = 2, Z = 0. В схеме 1 исключаем случай Y 6 X.
Тогда X < Y 6 2, а значит, X 6 1 иX → (Y → X) = X → 1 = 2. Схемы 5, 8, 9 проверяются так же, как выше. IÌÃÒÓÌÃÒÓÌÃÒÓ34ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-123. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙÔÍ-12ÌÃÒÓÔÍ-1234567Интерпретируемая №ИнтерпретируемаяСхема аксиомоперацияоперацияX ∧Y →Xx∧y =y8 X →Z →(Y →Z →(X ∨Y →Z))x∨y =1X ∧Y →Yx∧y =x9X → Y → (¬Y → ¬X)¬x = xX →Y →(X →Z →(X →Y ∧Z))x∧y =010¬¬X → X¬x = 1X →Y ∨Zx∨y =z11X → ¬¬X¬x = 0Y →Y ∨Zx∨y =yСхема аксиомÌÃÒÓ№ÔÍ-12ÔÍ-12Таблица 3.1ÌÃÒÓÌÃÒÓ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}
