Игошин Математическая логика и теория алгоритмов (1019110), страница 35
Текст из файла (страница 35)
Причем сопоставление осуществляется по правилам, определяемым следующими таблицами: Если теперь всем переменным, входящим в формулу формализованного исчисления высказываний, придать некоторые значе- 142 ния из М, то согласно введенным правилам сама формула примет некоторое значение из М. Формулу, всегда принимающую значение О, назовем выделенной. Во-первых, можно показать, что всякая формула, получающаяся по схеме аксиомы (А2), является выделенной. Для этого составим таблицу значений формулы (А2) (предпоследний столбец соответствует формуле Км (Г-+ 6) -+ (Г-э Н)): (А 2) и Во-вторых, необходимо показать, что всякая формула, получающаяся по схеме аксиомы (АЗ), также является выделенной. Предлагается самостоятельно составить таблицу значений форму- 143 лы (АЗ) и убедиться в том, что в ее последнем столбце стоят лишь нули (в таблице будет девять строк).
В-третьих, покажем, что правило вывода МР сохраняет свойство вьиеленности, т.е. если формулы г" и Р-э 6 выделенные, то и формула 6 — выделенная. В самом деле, в таблице, определяющей операцию — > над элементами множества М = (О, 1, 2), видим, что формулы г" и Г-+ 6 принимают одновременно значение О только в первой строке.
Но в этой строке и формула 6 также принимает значение О. Итак, на основании трех доказанных утверждений можно сделать следующий вывод: всякая формула, выводимая из аксиом (А2) и (АЗ) с помощью правила МР, является выделенной. Теперь, чтобы убедиться, что формула (А1) не может быть выведена из аксиом (А2) и (АЗ) с помощью правила МР, нужно установить, что она не является выделенной. В самом деле, если, например, г" принимает значение 1, а 6 принимает значение 2, то вычисляем значение формулы (А!): à — > (6-э г ) = 1 — ~ (2 -э !) = = 1 -~ О = 2 и О. Требуемая модель построена, и лемма тем самым полностью доказана.
П Независимость аксиомы (А2). Здесь строится модель, в которой выполняются аксиомы (А1) и (АЗ), но не выполняется аксиома (А2). Лемма 17З. Аксиома (А2) не зависит от аксиом (А1) и (АЗ) формализованного исчисления высказываний. Доказательство. Снова рассмотрим трехэлементное множество М = (О, 1, 2), но операции и — ~ над его элементами зададим по-другому, с помощью следующих таблиц: Снова назовем формулу исчисления высказываний выделенной, если при всякой подстановке вместо ее переменных любых элементов из Мона принимает значение О. Предлагается самостоятельно проверить, что всякая формула, построенная как по схеме аксиом (А1), так и по схеме аксиом (АЗ), является выделенной. Нетрулно также видеть, что правило вывода МР сохраняет свойство выделенности, т.е.
если формулы Г и à — ~ 6 выделенные, то и формула 6 — выделенная. Следовательно, всякая формула, выводимая из аксиом (А1) и (АЗ) с помощью правила МР, является выделенной. Теперь, чтобы убедиться, что формула (А2) не может быть выведена из аксиом (А1) и (АЗ) с помощью правила МР, нужно установить, что (А2) не является выделенной. Действительно, если, например, Г придать значение О, 6 — 0 и Н вЂ” 1, то (А2) примет значение 2. П Независимость аксиомы (АЗ). Метод построения соответствующей модели не единственный путь доказательства независимости той или иной аксиомы от остальных аксиом данной системы. Покажем независимость аксиомы (АЗ) другим методом.
Лемма 17.4. Аксиома (АЗ) не зависит от остальных аксиом (А1) и (А2) формализованного исчисления высказываний. Доказательство. Пусть à — произвольная формула формализованного исчисления высказываний. Обозначим через н(Г) формулу, полученную из Г стиранием всех вхождений знака в формуле Г. Легко понять, что для всякого частного случая Гсхем (А1) и (А2) формула й(Г) есть тавтология алгебры высказываний.
Далее, правило вывода МР обладает следующим свойством: если й(Г-+ 6) и й(Г) — тавтологии, то и н(6) — тавтология (так как й(Г-~ 6) совпадает с формулой Ь(Г) -+ Ь(6)). Следовательно, всякая формула Г, выводимая из (А1) и (А2) с помощью правила МР, имеет в качестве й(Г) тавтологию. Убедимся, что формула (АЗ) не выводима из (А1), (А2) с помощью правила МР. Для этого нужно проверить, что какая-либо конкретная формула Г, получающаяся по схеме (АЗ), имеет в качестве й(Г) формулу, не являющуюся тавтологией. Действительно, формула и[(-Х-э Х) — > ((- Х-+ Х) -+ Х)] есть следующая (Х-+ Х) -+ ((Х вЂ” ~ Х) — > Х). Нетрудно проверить, что последняя формула не является тавтологией.
(Найдите ее значение при Х= 0.) Следовательно, формула (АЗ) не выводима из (А1) и (А2). П Независимость системы аксиом. Из лемм 17.2 — 17.4 вытекает следующая теорема. Теорема 17.5. Система аксиом (А1), (А2), (АЗ) формализованного исчисления высказываний независима. Глава 1У ЛОГИКА ПРЕДИКАТОВ Предикаты вслед за высказываниями являются следующим важным предметом, исследуемым математической логикой.
Понятие предиката обобщает понятие высказывания, а теория предикатов представляет собой более тонкий инструмент, по сравнению с теорией высказываний, для изучения закономерностей процессов умозаключения и логического следования, составляющих предмет математической логики. В настоящей главе рассматриваются основы теории предикатов. й 18.
Основные понятия, связанные с предикатами Понятие предиката. В высказывании все четко: это — конкретное утверждение о конкретных объектах — истинное или ложное. Предикат — предложение, похожее на высказывание, но все же им не являющееся: о нем нельзя судить, истинно оно или ложно. Дадим точное определение. Онределение 18.1. Определенным на множествах М,, Мв ..., М„ н-местным нрединатом называется предложение, содержащее и переменных х„хп ..., х„превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств Мь Мп ..., М„соответственно. Для н-местного предиката будем использовать обозначение Р(х„ хм ..., х„).
Переменные хн хв ..., х, называют предметными, а элементы множеств Мн Мв ..., М„, которые эти переменные пробегают, — конкретными предметами. Всякий и-местный предикат Р(хн х,, ..., х„), определенный на множествах М„М„..., М„, представляет собой функцию и аргументов, заданную на указанных множествах и принимающую значения в множестве всех высказываний. Поэтому предикат называют также функцией-высказыванием. Рассмотрим пример. Предложение «Река х впадает в озеро Байкал» является одноместным предикатом, определенным над множеством всех названий рек. Подставив вместо предметной переменной х название «Баргузин», получим высказывание «Река Баргузин впадает в озеро Байкал». Это высказывание истинно.
Под- 146 ставив вместо предметной переменной х название «Днепр», получим ложное высказывание «Река Днепр впадает в озеро Байкал». Другой п р и м е р. Предложение (выражение) аз + у' < 9» является двухместным предикатом, заданным над множествами Я, А. Множества, на которых задан двухместный предикат, совпадают (говорят, что «двухместный предикат задан на множестве А~»). Пара действительных чисел 2, 2 превращает данный предикат в истинное высказывание: «2' + 2' < 9», а пара чисел 2, 3 — в ложное: «2з + Зз < 9». Отметим еше один подход к понятию предиката.
Как отмечалось, предикат Р(х„х,, ..., х„), определенный на множествах М„ Мь ..., М„, превращается в конкретное высказывание Р(аь аь ..., а„), если вместо предметных переменных хь хь ..., х„подставить в него конкретные предметы (элементы ап ам ..., а„) из множеств М„М„..., М„соответственно. Это высказывание может быль либо истинным, либо ложным, т.е. его логическое значение равно 1 или О. Следовательно, данный предикат определяет функцию л аргументов, заданную на множествах М„М,, ..., М„и принимающую значение в двухэлементном множестве (О, 1). Иногда эту функцию и называют предикатом. Классификация предикатов.
Определение 18.2. Предикат Р(х„ х„..., х„), заданный на множествах М„М,, ..., М„, называется: а) тождественно истинным, если при любой подстановке вместо переменных хь х„..., х„любых конкретных предметов аь аь ..., а„ из множеств М„М„..., М„соответственно он превращается в истинное высказывание Р(аь ап ..., а„); б) тождественно ложным, если при любой подстановке вместо переменных х„хп ..., х„любых конкретных предметов из множеств Мп Мп ..., М„соответственно он превращается в ложное высказывание; в) выполнимым (опровержимым)„если существует по меньшей мере один набор конкретных предметов а„ап ..., а„из множеств М„Мп ..., М„соответственно, при подстановке которых вместо соответствующих предметных переменных в предикат Р(хп хп ..., х„) последний превратится в истинное (ложное) высказывание Р(ап а,, ..., а„). Приведем п р и м е р ы.
Одноместный предикат «Город х расположен на берегу реки Волги», определенный на множестве названий городов, является выполнимым, потому что существуют горола, названия которых превращают данный предикат в истинное высказывание, или, иначе, удовлетворяют этому предикату (например, Ульяновск, Саратов и т.д.). Но данный предикат не будет тождественно истинным, потому что существуют города, названия которых превращают его в ложное высказывание, или, иначе, не удовлетворяют этому предикату (например, Прага, Якутск и т.д.). Этот же предикат являет собой пример опровержимого, но не тождественно ложного предиката (продумайте!). 147 В другом примере одноместный предикат «айпзх+ соИх = 1», определенный на множестве действительных чисел, тождественно истинный.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
