Исчисление высказываний непротиворечиво, т. к. каждая формула, доказуемая в исчислении высказываний, является тождественно истинной формулой в алгебре высказываний и легко проверяется на таблицах истинности. Тогда отрицание формулы не является тождественно истинной формулой, что проверяется на таблицах истинности и при доказательстве в исчислении высказываний ведет к противоречию.
Проблема непротиворечивости исчисления высказываний заключена в доказательстве невыводимости формулы и ее отрицания.
Проблема разрешимости исчисления выказываний заключена в доказательстве существования алгоритма, который позволил бы для любой формулы исчисления высказываний определить ее доказуемость. Любая формула исчисления высказываний может быть представлена формулой алгебры высказываний. Эффективность процедуры разрешения показана таблицами истинности для различных наборов значений пропозициональных переменных.
Для обоснования исчисления высказываний, как для любой аксиоматической теории, необходимо рассмотреть проблемы разрешимости и непротиворечивости.
Проблемы в исчислении высказываний
Раздел 2. Логика предикатов
2.1. Понятие предиката
В алгебре логики высказывания рассматриваются как
нераздельные целые и только с точки зрения их истинности или ложности. Ни структура высказываний ни тем более, их содержание не затрагиваются. В то же время и в науке, и в практике используются заключения, существенным образом зависящие как от структуры, так и от содержания используемых в них высказываний.
точки зрения этой логики рассматриваются как целые,
неделимые, без учета их внутренней структуры. Следовательно, алгебра логики. будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.
В связи с этим возникает необходимость в расширении логики высказываний, в построении такой логической системы, средствами которой можно было бы исследовать и структуру тех высказываний, которые в рамках логики высказываний рассматриваются как элементарные.
Такой логической системой является логика преди-
катов, содержащая всю логику высказываний в каче-
стве своей части.
Логика предикатов, как и традиционная формаль-
ная логика, расчленяет элементарное высказывание на
субъекm (буквально подлежащее, хотя оно и может
играть роль дополнения) и nредикат (буквально ска-
зуемое, хотя оно может играть и роль определения).
Субъект - это то, о чем что-то утверждается в высказывании; nредикат - это то, что утверждается о
субъекте.
Например, в высказывании «7 простое число», «7»- субъект, «простое число» -предикат. Это высказывание
утверждает, что «7» обладает свойством «быть простым числом».
Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х -простое число». При одних значениях х (например, х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.
Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1.0}.
Здесь предикат становится функцией субъекта и выpa-
жает свойство субъекта.
Определение. Одноместным nредикатом Р(х) нa-
зывается произвольная функция переменного х, опреде-
ленная на множестве М и принимающая значения из
множества {1.0}.
Множество М, на котором определен предикат Р(х).
называется областью оnределенuя nредиката.
Множество всех элементов х є М , при которых преди-
кат принимает значение « истина» , называется множеством истинности предиката Р(х) , то есть множество истинности предиката Р(х)- это множество Iр = {х: х єМ, Р(х) = 1}.
Так, предикат Р(х)- «х простое число» определен
на множестве N, а множество Iр для нeгo есть множество всех простых чисел. Предикат Q(x) – « sin х = о» определен на множестве R, а eгo множество истинности IQ = {kπ, k є z}. Предикат F(x) – «Диагoнали параллелогpамма х перпендикулярны» определен на множестве всех параллелограммов, а eгo множеством истинности является множество всех ромбов.
Приведенные примеры одноместных предикатов выражают свойства предметов.
Определение. Предикат Р(х) , определенный на мно-
жестве М, называется тождественно истииным (тож-
дественно ложным), если Iр = М (I p = Ø).
Естественным обобщением понятия одноместного
предиката является nонятuе многоместного nредика-
та, с помощью котopoгo выражаются отношения меж-
ду предметами.
Примером бинарного отношения (отношения между двумя предметами) является отношение «меньше». Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной формой « х < у » , где х, y є Z, то есть является функцией двух переменных Р(х,у), определенной на множестве Z х Z с множеством значений {1,0}.
Определение. Двухместным nредикатом Р(х,у) нa-
зывается функция двух переменных х и y, определенная
на множестве М = М 1x М 2 и принимающая значения
из множества {1,0}.
В числе примеров двухместных предикатов можно
назвать предикаты: Q(x, y) - «х = y» предикат равен-ства, определенный на множестве R 2 = R х R;
F(х,у) -« х//у», прямая х параллельна прямой у, определенный на множестве прямых, лежащих на данной плоскости.
Аналогично определяется n-местный предикат.
2. 2. Логические операции над предикатами
Предикаты, так же, как высказывания. принимают
два значения «u» и «л» (1, О), поэтому к ним применимы все операции логики высказываний.
Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов.
Пусть на некотором множестве М определены два
предиката Р(х) и Q(х).
Определение 1. Конъюнкцией двух предикатов Р(х)
и Q( х) называется новый предикат Р(х)& Q( х),
который принимает значение «истина» при тех и только тех значениях х є М, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях.
Очевидно, что областью истинности предиката
P(x)&Q(x) является общая часть областей истинно-
сти предикатов Р(х) и Q(x) , то есть пересечение IP ∩ IQ.
Так, например, для предикатов Р(х): «х - четное
число», и Q(х): «х кратно 3» конъюнкцией Р(х)&Q(х)
является предикат «х - четное число и х кратно 3», то
есть предикат «х делится на 6».
Определение 2. Дизъюнкцией двух предикатов Р(х)
и Q(х) называется новый предикат Р(х) ν Q(x), который
принимает значение «ложь» при тех и только тех значе-
ниях х є М, при которых каждый из предикатов при-
нимает значение «ложь» и принимает значение «истина» во всех остальных случаях.
Ясно. что область истинности предиката Р( х) v Q( х)
является объединение областей истинности предикатов Р(х) и Q(x),то есть объединение IP IQ.
Определение 3. Отрицанием предиката Р(х) называется новый предикат , который принимает значение «истина» при всех значениях х є М, при которых предикат Р( х) принимает значение «ложь», и принима-
ет значение «ложь» при тех значениях х є М, при кото-
рых предикат Р(х) принимает значение «истина».
Определение 4. Имnликацией предикатов Р(х) и
Q(x) называется новый предикат Р(х) → Q(x), который
является ложным при тех и только тех значениях х є М,
при которых одновременно Р(х) принимает значение
«истина», а Q(x) значение «ложь» и принимает значение «истина» во всех остальных случаях.
2. 3 Кванторные операции
Пусть имеется предикат Р(х). определенный на множестве М. Если а - некоторый элемент из множества М, то подстановка eгo вместо х в предикат Р(х) превращает этот предикат в высказывание Р(а). Такое высказывание называется единичным. Наряду с образованием из предикатов единичных высказываний в логике предикатов рассматривается еще две операции. которые превращают одноместный предикат в высказывание.
2.3.1 Квантор всеобщности.
Пусть Р(х) предикат, определенный на множестве М. Под выражением x Р(х) понимают высказывание, истинное, когда Р(х) истинно для каждого элемента х из множества М и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение будет «Для всякого х Р(х) истинно». Символ называют "квантором всеобщности».
Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании х Р( х) переменную х называют связанной квантором .
2.3.2 Квантор существования.
Пусть Р(х) предикат определенный на множестве М. Под выражением х Р( х) понимают высказывание. которое является истинным, если существует элемент х є М, для которогo Р(х) истинно, и ложным в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение будет: «Существует х, при котором Р(х) истинно». Символ называют «квантором существованuя».
В высказывании х Р( х) переменная х связана квантором .
Приведем пример употребления кванторов. Пусть на множестве N натуральных чисел задан предикат Р(х): «Число х кратно 5». Используя кванторы, из данного предиката можно получить высказывания:
х є N Р( х) -«Все натуральные числа кратны 5»;
х є N Р(х) –«Cyществует натуральное число, кратное 5».
Очевидно, первое из этих высказываний ложно, а второе истинно.
Ясно, что высказывание х Р( х) истинно только в
том единственном случае, когда Р(х) тождественно
истинный предикат, а высказывание х Р(х) ложно только в том единственном случае, когда Р(х) тождественно ложный предикат .
Кванторные операции применяются и к многомест-ным предикатам. Пусть, например, на множестве М за-
дан двухместный предикат Р(х,у). Применение кванторной операции к предикату Р(х,у) по переменной х ставит в соответствие двухместному предикату Р(х,у) одноместный предикат x Р(х,у) (или одномест-ный предикат х Р(х,у)), зависящий от переменной у и не зависящий от переменной х. К ним можно применить кванторные операции по переменной у, которые приведут уже к высказываниям следующих видов:
yx Р(х,у), yxP(x,y), yxP(x,y), ухР(х,у).
Например, рассмотрим предикат Р( х, у): «х: у»
определенный на множестве N. Применение кванторных операций к предикату Р( х, у) приводит к восьми возможным высказываниям:
1. yx Р(х,у) -«Для всякого у и для всякого х у
является делителем х».
2. yxP(x,y) – «Существует у, которое является
делителем всякого х».
3. yxP(x,y) -«Для всякого у существует х такое,
что х делится на у».
4. ухР(х,у) -«Существует у и существует х тaкие, что у ,является делителем х».
5. xy Р(х,у) –«Для всякого х и для всякого у, у является делителем х».
6. ху Р(х,у)- «Для всякого х существует такое у, что х делится на у».
7. ху Р(х,у) –«Существует х и существует у такие, что у является делителем х».
8. xy Р(х,у) – «Существует х такое, что для всякoгo у х делится на у».
Легко видеть, что высказывания 1, 5 и 8 ложны. а
высказывания 2, 3, 4, 6 и 7 истинны.
Из рассмотренных примеров видно, что в общем случае изменение порядка следования кванторов изменяет смысл высказывания, а значит, и eгo логическое значение (например, высказывания 3 и 8).
Рассмотрим предикат Р( х), определенный на мно-
жестве М = {а1,а2,.....ап} , содержащем конечное число
элементов. Если предикат Р( х) является тождественно
истинным, то истинными будут высказывания Р( а1) ,
Р(а2), ..., Р(а п ). При этом истинными будут высказыва -
ния хР( х) и конъюнкция Р( а1)& Р( а2)& ... & Р( а п ) .
Если же хотя бы для одного элемента ak є М Р( ak)
окажется ложным, то ложными будут высказывание
xР(x) и конъюнкция Р( а1)& Р( а2)& ... & Р( а п ). Следова-
тельно, справедлива равносильность
xР(x) = Р( а1)& Р( а2)& ... & Р( а п ).
Нетрудно показать, что справедлива и равносиль-
ность
х Р(х) = Р( а1)ν Р( а2)ν ... ν Р( а п ).
Отсюда видно, что кванторные операции можно рассматривать как обобщение операций конъюнкции и
дизъюнкции на случай бесконечных областей.
2. 4 Понятие формулы логики предикатов
В логике предикатов будем пользоваться следующей символикой:
1. Символы р, q, r, ... переменные высказывания,
принимающие два значения: 1- истина, О - ложь.
2. Предметные переменные х,у,z..., которые про-
бегают значения из некотopoгo множества М: х0,у0,z0,… предметные константы, то есть значения предметных переменных.
2. Если F( .,.....,.) п-местная предикатная переменная или постоянный предикат, а x 1 , х 2 , .... хп предметные переменные или предметные постоянные (не обяза-
тельно все различные) , то F (х1,х2,... хп) есть формула.
Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.
3. Если А и В формулы, причем такие, что одна и
та же предметная переменная не является в одной из них связанной, а в другой свободна, то слова А ν В ,
А& В , А → В есть формулы. В этих формулах те переменные, которые в исходных формулах были свободными, являются свободными, а те, которые были связанными, являются связанными.
4. Если А формула, то формула, и характер
предметных переменных при переходе от формулы А к
формуле не меняется.
5. Если А(х) формула, в которую предметная пере-менная х входит свободно, то слова x А( х) и хА( х) яв-
ляются формулами, причем предметная переменная
входит в них связанно.
6. Всякое слово, отличное от тех, которые названы
формулами в пунктах 1-5, не является формулой.
Например, если Р( х) и Q( х, у) одноместный и двухместный предикаты, а q и r переменные высказывания, то формулами будут слова: q, Р( х),
Р( х)& Q( х 0, у), хР( х) → xQ(x,y), (Q(x,y) ν q)→ r.
Не является формулой слово: xQ(x,y) → Р(х). Здесь
нарушено условие п.3, так как в формулу xQ(x,y) пе-
ременная х входит связано, а в формулу Р(х) перемен-
ная х входит свободно.
Из определения формулы логики предикатов ясно,
что всякая формула алгебры высказываний является
формулой логики предикатов.
2. 5 Значение формулы логики предикатов
О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множе-
ство М, на котором определены входящие в эту форму-
лу предикаты. Логическое значение формулы логики
предикатов зависит от значений трех видов переменных:
1) значений входящих в формулу переменных высказываний
2) значений свободных предметных переменных из множества М,
3) значений предикатных переменных.
При конкретных значениях каждого из трех видов
переменных формула логики предикатов становится
высказыванием, имеющим истинное или ложное значение.
Рассмотренные логические операции позволяют формализовать с помощью предикатов и кванторов внутреннюю структуру предложения и формировать сложные суждения.
Пример: Суждение “Некоторые действительные числа являются рациональными”.
В этом суждении есть два предиката P1(x):=”быть действительным числом” и P2(x):=”быть рациональным числом”. Формула сложного суждения должна быть записана так:
