Лекции по "Алгебре"

    Раздел 4. Логика предикатов

    Тема 4.1 Основные понятия и определения

    Логика  предикатов или исчисление предикатов – это раздел математической логики, исследующий операции над высказываниями, расчлененными на субъект и предикат.

    Это расширение понятий и логических средств по сравнению с логикой высказываний или Булевой алгеброй. Логические операции с высказываниями, не разделенными на субъект и предикат – это простейший вид логических операций. «В исчислении предикатов делается дальнейший шаг анализа  и разрешается рассматривать объектно–предикатную структуру простых предложений и пользоваться операциями композиции, зависящими от этой структуры», - пишет Клини.

    Слово предикат (от латинского praedicatum – сказуемое), то что высказывается (утверждается или отрицается) в суждении о субъекте. Предикат выражает наличие или отсутствие того или иного признака у субъекта.

    Например: в суждении «Советская ракета достигла Луны» объектом суждения служит «Советская ракета», а предикат – «достигла Луны».

    В логике предикатов под предикатом понимается некоторое свойство или отношение.

    Примеры:

    одноместного  предиката (свойства):

    1. Р(х) - «Быть простым числом». Подставив  значение х, мы получим высказывание  «х – простое число».

    2. Р(х) – «Быть животным», тогда  подставив значение х = Жучка, получим высказывание «Жучка – животное».

    двуместного предиката (отношения)

    3. Р(х,у) – «х и у – муж  и жена». 

    4. Р(х,у) – «х < у ». 

    В логике предикатов, как и в логике высказываний, высказывания представляют собой или «Истину» или «Ложь». Разница в том, что в логике предикатов истинностное значение ставится в соответствие определенному предмету или группе предметов, тогда как в логике высказываний они относились к высказыванию. Так в примере 1 для х = 7 Р(х) – Истинно, а для х = 8, Р(х) – Ложно.

    С точки зрения математики Предикат очень  удобно рассматривать как функцию  от некоторого числа переменных, значением которой будут логические величины.

    Определение: n – местным предикатом называется логическая функция, значениями которой являются высказывания об упорядоченных множествах из n объектов, представляющих значения аргументов.

    Чтобы задать n – местный предикат Р(х₁…х_N) следует указать множества D_i     i=1,N  - области изменения предметных переменных Х. Предикат определяется заданием подмножества М в декартовом произведении D_i. При этом Р(х₁…х_N) понимают как высказывание "упорядоченный набор (х₁…х_N) принадлежит М". Понятие предиката может еще интерпретироваться так: "Из посылок х₁…х_N, следует заключение В".

    Определение: Квантор – это логическая операция, которая по предикату Р(х) строит высказывание, характеризующее область истинности предиката Р(х).

    В математической логике наиболее употребительный  квантор всеобщности " и квантор существования $. Высказывание "х Р(х) означает, что область истинности предиката совпадает с областью значения переменной х. Высказывание $х Р(х) означает, что область истинности предиката не пуста.

Примеры

    $х А(х) – т.е. существует число х, такое что х – простое число.

    "х "у G(х,у) -  для любого х и для любого у выполняется условие G(х,у) 

    Определение: Формула

            1. Любая переменная  – это формула.

                2. Если А и В  – формулы, то ØА, (АÚВ), (А&В), (А®В),"х А, $х А - формулы 

    Пример:

    (АÚØ(В&А) – не формула (не хватает одной закрывающей скобки).

    (АÚØ(В&А)) – формула

    Определение:. Вхождения переменных, которые в процессе построения формулы не связываются кванторами, называются свободными, иначе, говорят что вхождения переменной х – связанные.

    Обратите  внимание, что одна и та же переменная может быть и свободной и связанной  в одной и той же формуле.

    Пример: "х $у (ØР(х,у)) ® Q(у,z)

    В данном примере переменная у имеет  как свободное, так и связанное  вхождение в формулу.

    Определение: Формула называется замкнутой, если никакая предметная переменная не является в ней свободной.

    Приведем  примеры более сложных предикатов:

    Пример1: «Всякий человек смертен»  - "х (Человек(х) ® Смертен(х))

    Пример2: «Всякий студент изучает какую-нибудь науку»  - "х (Студент(х) ® $у Наука(у)&Изучает(х,у))

    Пример3: «Квадрат любого четного числа больше 1» - "х (Четное число(х) ® >(Квадрат(х),1))

    Тема 4.2 Правила вывода

    Определение: Правила, по которым в логике из истинных формул образуются новые истинные формулы называются правилами вывода.

    Определение: Выводом называется непустая конечная последовательность формул С₁…С_n, таких что:

• каждая С_i – есть либо посылка, либо получена из предыдущих формул по одному из правил вывода.
• Если в выводе применялись правила 5 или 7, то все формулы, начиная с последней посылки и вплоть до результата применения данного правила, исключаются из дальнейших шагов построения вывода.

 

    Выпишем правила формального вывода: 

    1.        2.

    3.        4.  

    5.        6.  

    7.        8.  

    Каждое  правило вывода представляет собой  формулировку разрешения нечто осуществить, а именно, если даны формулы того вида, который указан выражениями, стоящими над чертой (посылки правил), то каждое правило позволяет записать после этого формулу того вида, который указан выражением, стоящим под чертой (заключение правила).

    Правило 5 называется правилом введения импликации. Она позволяет по любой формуле В перейти к импликации, но обязательно в качестве посылки используется последнее допущение (или последняя посылка).

    При обнаружении двух противоречащих друг другу формул (правило 7) позволяет  говорить о выводимости отрицания последнего допущения (и только его).

    Пример: Показать выводимость формулы r из посылок p®q, q®r, p

          1.

          2.

    Определение: Доказательство есть вывод из пустого множества посылок. Последняя формула в доказательстве называется доказанной формулой или теоремой.

    Мы  обязательно должны сказать, что приведенный набор правил вывода применим к исчислению высказываний. Набор правил вывода исчисления предикатов несколько шире. Каждое правило вывода не нуждается в доказательстве (является очевидным). Но с помощью них можно получать все новые, далеко не всегда очевидные результаты. Необходимо хорошо понимать тот факт, что в описанных правилах вывода используются формулы, т.е. в качестве А, В, С и т.д. могут использоваться и достаточно сложные высказывания. 

    В следующей главе мы покажем более сложные правила рассуждений, применимые в логике человеческих рассуждений. Все они получены путем вывода из указанных правил вывода.

    Тема 4.3 Умозаключения.

    Определение: Умозаключение – это форма мышления или логическое действие, в результате которого из одного или нескольких известных и определенным образом связанных суждений получается новое суждение, в котором содержится новое знание.

    Логики  и философы, тысячелетия рассуждая  о природе и законах человеческого  мышления, нашли правила получения новых знаний из набора разрозненных, но истинных фактов. Эти правила принято называть умозаключениями. Их достаточно много. Мы приведем самые распространенные из них и рассмотрим примеры их использования. Однако следует хорошо понимать, что все эти типы рассуждений можно получить из базового набора правил вывода математической логики.

    условно-категоричные умозаключения

    К числу правильных, условно-категоричных умозаключений относятся умозаключения следующего типа:

                      

    Данные  способ рассуждения в средневековой логике получил название modus ponens, т е. «утверждающий способ рассуждения».  

    Пример: Если отмечается спад производства, то растет число безработных. В России отмечается спад производства. Следовательно, число безработных растет. 

    Другой тип правильных условно-категорических умозаключений является modus tollens, т е. «Отрицательный способ рассуждения».

        

    Пример: Если благородная цель оправдывает любые средства, то можно лишить человека жизни, если он смертельно болен и Вы хотите укоротить его страдания. Но даже в этом случае нельзя лишать человека жизни. Значит неверно, что благородная цель оправдывает любые средства.

    Покажем вывод этого умозаключения из правил вывода исчисления высказываний. Одновременно продемонстрируем и способы применения этих правил.

    

    Отметим, что неверными являются следующие  способы рассуждения:

    

    Разделительно-категоричные рассуждения

    Эти рассуждения так же являются двухпосылочными  и содержат дизъюнктивную или строго – дизъюнктивную посылку.

    Правильными являются следующие способы рассуждения 

      
 

    Это правило получило название modus tolledo, т.е. «отрицающе-утверждающий способ рассуждения».

    Пример: Этот человек заблуждается сам, или сознательно вводит в заблуждение других. Но сам этот человек не заблуждается. Следовательно, он сознательно вводит в заблуждение других. 

    Приведенные ниже примеры не являются корректными: 

      

    Однако, если дизъюнктивную посылку заменить строго-дизъюнктивной посылкой, то получим правильные способы рассуждений. 

    

    Умозаключения подобного типа называются modus ponendo tolens, что означает «утверждающе-отрицающий способ рассуждений». 

    Пример: Шахматист К. примет участие в одном из двух турниров: он либо выступит на турнире в Тилбурге, либо на турнире в Линаресе. Известно, что К. дал согласие принять участие в Линаресе. Следовательно, К. не выступит на турнире в Тилбурге.