Игошин Математическая логика и теория алгоритмов (1019110), страница 40
Текст из файла (страница 40)
Наконец, под каждым из универсальных высказываний, стоящих у верхних вершин, стоит высказывание у нижней вершины, следующее из него, т.е. такое, что импликация этих высказываний (для любого предиката Р(х)) является истинным высказыванием. В заключение отметим, что кванторы в явном виде впервые были введены немецким математиком Готлобом Фреге в работе «Вейп(уззс)тпй» («Исчисление понятий», 1879). В 1885 г. английский логик Чарльз Пирс ввел термины «квантор», «квантификация», происшедшие соответственно от лат. г(иапгип — «сколько» и лат.
диапгип +7ас1о — «делать». Это означает, что квантор показывает, о скольких (всех или некоторых) объектах говорится в том или ином предложении. Символику для кванторов в виде перевернутых латинских букв ввел итальянский математик Дж. Пеано в 90-е гг. Х!Х в. После использования кванторов математиками Пеано, Шредером, Расселом они стали широко использоваться. 164 В 21. Формулы логики предиквтов В алгебре высказываний мы подробно изучили (э 2 — 6) одно из важнейших ее понятий и инструментов — понятие формулы алгебры высказываний.
Теперь наша задача состоит в том, чтобы определить и изучить соответствующее понятие в логике предикатов, а затем на его основе продемонстрировать, насколько тоньше и точнее язык и логика предикатов отражают процессы человеческого мышления, нежели это делают язык и логика высказываний. Понятие формулы логики предикатов. Это понятие вводится аналогично понятию формулы алгебры высказываний. Сначала задается алфавит символов, из которых будут составляться формулы: предметные переменные: х„у, г, х» уь г; (1 в Ф)'„ нульместные предикатные переменные: Р, Д, А, Р» Я„А;((а 1У); и-местные (н > 1) предикатные переменные: Р(,, ), О(, ...„), А(, ..., ), Р(, ..., ), Я(, .„, ), А,(, ..., ) (1а Л) с указанием числа свободных мест в них; символы логических операций: —, », ~~, -ь, <-+; кванторы: Ч, Л; вспомогательные символы: (, ) — скобки;, — запятая.
Теперь дадим определение формулы логики предикатов, которое также носит индуктивный характер. Определение 21.1 (формулы логики предикатов). 1) Каждая нуль- местная предикатная переменная есть формула„ 2) если Р(, ..., ) — л-местная предикатная переменная, то Р(х„..., х„) есть формула, в которой все предметные переменные хь ..., х„свободны; 3) если Р— формула, то — à — также формула.
Свободные (связанные) предметные переменные в формуле -Рте и только те, которые являются свободными (связанными) в Г; 4) если Рн Р, — формулы и если предметные переменные, входящие одновременно в обе эти формулы, свободны в каждой из них, то выражения (Г, » Р2), (Р; Рз), (Р; — > Р2), (Р; <-+ Гз) также являются формулами. При этом предметные переменные, свободные (связанные) хотя бы в одной из формул Рн Рм называются свободньини (связанными) и в новых формулах; 5) если à — формула и х — предметная переменная, входящая в Р свободно, то выражения (чх)(Г) и (Лх)(Г) также являются формулами, в которых переменная х связанная, а все остальные предметные переменные, входящие в формулу Гсвободно или связанно, остаются и в новых формулах соответственно такими же; 6) никаких других формул логики предикатов, кроме получающихся согласно пп.
1 — 5, нет. 165 Формулы, определенные в п. 1 и и. 2, называются элементарными (или атомарными). Формулы, не являющиеся элементарными, называются составными, Например, Р, Д(х, у, г), А(хо хг) — элементарные формулы, а (Лу)(Р(х, у, г)), (ех)(ЗуНР(х, у, г)), (((Ъх)(Р(х)) н Д) — э —,(Ву) (А(х, у))) — составные формулы. При этом в первой составной формуле предметная переменная у связана, а переменные х, г— свободные. Во второй составной формуле свободна лишь переменная г, остальные — связаны.
В третьей составной формуле первое вхождение переменной х связано, а второе — свободно. Переменная у связана. Последнюю формулу более целесообразно было бы записать в следующем виде (заменив связанную переменную х какой-нибудь буквой, не входящей в данную ФормУлУ): ((('ге)(Р(е)) л л Д) — > -(Эу)(Я(х, у))). Как и в алгебре высказываний, договоримся внешние скобки у формулы не писать, если только она не является частью более сложной формулы. Отметим кстати, что на основании пунктов 1, 3 и 4 сформулированного определения всякая формула алгебры высказываний будет также и формулой логики предикатов. В формулах вида (~у~)(с) и (Лс)(Г) формула Г называется областью действия нвантора 'чс или Л~ соответственно.
Тогда ясно, что вхождение предметной переменной в формулу будет связанным, если эта переменная находится в области действия квантора по этой переменной. Формулы, в которых нет свободных предметных переменных, называются замкнутыми, а формулы, содержащие свободные предметные переменные, — открытыми. Так, все приведенные выше формулы логики предикатов, кроме формулы Р, являются открытыми. П р и м ер ы замкнутых формул: Р, (1Гг)(А(г)), (Лх)('Уу)(Р(х, у)), (Ъ'х)(Д(х)) -э — (Чх)(Лх)(А(х, у)). Классификация формул логики предикатов. Если в формулу логики предикатов вместо каждой предикатной переменной подставить конкретный предикат, определенный на некотором выбранном множестве М, то формула превратится в конкретный предикат, заданный над множеством М.
При этом, если исходная формула была замкнутой, то полученный конкретный предикат окажется нульместным, т.е. будет высказыванием. Если же исходная формула была открытой, т.е. содержала свободные вхождения предметных переменных, то в результате подстановки получим предикат, зависящий от некоторых предметных переменных. Если теперь подставить вместо этих предметных переменных конкретные предметы из множества М, то полученный предикат, а следовательно, и исходная формула превратятся в конкретное высказывание.
Превращение формулы логики предикатов в высказывание описанным выше способом (а также само получаемое высказывание) 166 называется интерпретацией этой формулы на множестве М. Итак, если формула логики предикатов замкнутая, т.е. не содержит свободных предметных переменных, то ее интерпретация состоит из одного этапа и сводится к подстановке вместо всех предикатных переменных конкретных предикатов, в результате чего формула превращается в конкретное высказывание (нульместный предикат).
Если же формула логики предикатов открытая, т.е. содержит ряд свободных предметных переменных, то ее интерпретация состоит из двух этапов. Во-первых, вместо всех предикатных переменных необходимо подставить конкретные предикаты, в результате чего формула превратится в конкретный предикат, зависящий от такого количества предметных переменных, сколько было свободных предметных переменных в исходной формуле. Во-вторых, нужно придать значение каждой предметной переменной, от которой зависит получившийся предикат, в результате чего этот предикат (и, значит, вся исходная формула) превратится в конкретное высказывание (истинное или ложное).
Прцмер 21.2. Дадим интерпретацию формуле (»х)(Бу)(Р(х, у)). В качестве множества М возьмем множество всех мужчин, а вместо предикатной переменной Р(х, у) подставим конкретный предикат, определенный на М: «х есть отец у». Тогда исходная формула превратится в следующее (очевидно, ложное) высказывание (чх)(Лу)(х есть отец у) — «у каждого мужчины есть сын».
Этой же формуле можно дать и другую интерпретацию. Возьмем в качестве М множество Ф всех натуральных чисел, а вместо предикатной переменной Р(х, у) подставим предикат «х < у», определенный на Ф'. Тогда исходная формула превратится в (очевидно, истинное) высказывание (чх)(Лу)(х < у) — «Для каждого натурального числа существует большее по сравнению с ним натуральное число». Пример 21.3. В предыдущем примере была рассмотрена интерпретация замкнутой формулы.
Дадим интерпретацию открытой Формуле (Зг)(Р(х, у, г) — > О(х, у, г)) » А. В качестве множества М возьмем множество Ф всех натуральных чисел. Вместо предикатных переменных Р(х, у, г) и О(х, у, г) подставим трехместные предикаты «х. у= г» и «х+ у= г» соответственно, а вместо нульместного предиката А подставим (ложное) высказывание «2 = 4». Тогда данная формула превратится в двухместный предикат (от предметных переменных х, у): (Лг)(х у = г -» х+ у = г) -» 2 = 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
