Исчисление предикатов. Высказывания над предикатами. Кванторы. Теория классов

Лекция 10

Исчисление предикатов. Высказывания над предикатами. Кванторы. Теория классов.

I.  Отношения, предикаты, высказывания над

предикатами, кванторы.

1.  Отношения.

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

Х – конечное или бесконечное множество. Например, множество натуральных чисел. Само «Х» является уникальным именем.

Понятие сущности должно быть конструктивно, т. е. каждая сущность должна иметь либо алгоритм распознавания, либо алгоритм порождения. Например, каждое натуральное число «n» имеет десятичный (двоичный) код, отличающий его от другого числа.

Объединение сущностей в то или иное множество должно быть также конструктивно. В множество обычно объединяются сущности, которые имеют одинаковые свойства. Конструктивно то или иное свойство задаётся набором признаков (элементарных свойств). Например, множество параллелограммов объединяет фигуры, которые обладают общим свойством (признаком) – параллельностью противоположных сторон. Если четырехугольные фигуры нужно определить в виде взаимосвязей четвёрок отрезков, то необходимо ввести признаки замкнутости, выпуклости и др.

Понятие признак и свойство, вообще говоря эквивалентны, и требуют их конструктивного распознавания.

1.1 Унарные отношения на множестве .

Унарным отношением a называется любое подмножество множества Х (записывается или ).

Пример 1. Пусть в списке российских городов выделены те, которые имеют аэропорты, тогда a есть отношение «быть городом с аэропортом» (города, имеющие свойство a).

Пусть среди городов со свойством a выделены города, имеющие свойство b (аэропорт 1-й категории), тогда .

1.2 Бинарные отношения. Образуем на Х все возможные пары , . Множество пар называется декартовым произведением 2-го порядка .

Бинарным отношением s называется любое подмножество .

Замечание 1. может быть образовано на различных множествах .

Замечание 2. Декартово произведение есть само множество .

Замечание 3. – есть пустое множество.

Пример 2. На множестве городов, имеющих аэропорты 1й категории (для примера определим такой список ), введём бинарное отношение s такое, что , если город соединён авиатрассой с . Возможные трассы могут быть показаны бинарным графом.

1)  Трасса имеет свой-ство «самолёт может лететь из города в город » (обратной трассы нет).

2)  Из города в нет трассы (ни туда, ни обратно).

3)  Города соединены пря-мой и обратной трассой.

Пример 3. Множество чисел имеет линейный порядок. , это бинарное отношение может быть показано графом.

Пример 4. Частичный порядок. Пусть задано множество . Множество всех подмножеств образует отношение включения «h», где, например, код подмножества определяет, что состоит из элемента, а элемент не входит в .

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

Аналогичным образом могут быть определены декартовы произведения и т. д. и отношения соответствующей арности.

2.  Предикаты.

Предикатом называется функция, определённая на отношении (любой арности) и принимающая два значения (истина – и (1), ложь – л (0))

.

Пример 5. Унарный предикат.

– некоторое имя города из списка, a – отношение «город, имеющий аэропорт», – предикат.

.

Пример 6. Чётное число. Пусть любое натуральное число «n» представляется двоичным кодом, тогда предикат «четное число» Рr(п) определяется признаком чётности.

Пример 7. Бинарный предикат s.

s – список трасс из примера 2. Тогда, предикат «авиатрасса»

.

Пример 8. Бинарный предикат h – (отношение непосредственного включения).

3.  Высказывания, содержащие предикат.

Структура высказывания – «S есть Р», где S называется субъектом, а Р предикатом. Субъект есть сущность, предмет, набор (множество) предметов.

Предикат Р определяет свойство «принадлежать». В математической записи – . Высказывание принимает значение«и», если значение «и» принимает соответствующий предикат со значением .

Пример 9. Высказывание: «4 есть чётное число» – истинно, т. к. при .

Пример 10. «Маршрут Казань–Москва принадлежит к списку авиатрасс» – истинное высказывание.

4.  Сложные высказывания.

Предикативные высказывания в отличии от обычных высказываний содержат внутреннюю структуру (субъект и предикат). Но если субъект определён и истинность/ложность предиката может быть вычислена, тогда предикативные высказывания ничем не отличаются от обычных и из них могут быть при помощи известных логических связок сконструированы сложные высказывания. Обычно применяют следующие логические связки : ù – отрицание, Ú – дизъюнкция, & – конъюнкция, ® импликация с известной интерпретацией истинностными таблицами.

Пример 11.Высказывание: Студент Иванов спит на лекции, поэтому он не является отличником.

Элементарные высказывания.

1)  S (субъект – Иванов), Р1 (предикат – студент, т. е. имеет свойство «быть студентом»). Иванов принадлежит к множеству «студенты» и это истинно. .

2)  Р2 (предикат – свойство «спать на лекции»).

3)  Р3 (предикат – свойство «быть отличником»).

Сложное высказывание , где х = Иванов, читается так:

«Если Иванов есть студент и спит на лекции , то он не отличник ». Для субъекта = Иванов, это высказывание истинно.

Заметим, что тождественная истинность высказывания, относится только к студентам, спящим на лекции.

Например, Бен Ладен не является студентом.

.

Для Бен Ладена высказывание может быть как истинным, так и ложным, т. к. всегда ложен, , а из лжи может следовать как истина, так и ложь.

5.  Кванторы.

Пусть задан предикат , который означает, что х обладает свойством Р.

Рассмотрим утверждение: «Для всякого предмета х свойство выполнено». Это утверждение (высказывание) будет истинным, если на самом деле все возможные предметы, объединённые в множество, обладают свойством Р.

Пример: – все предметы из Х обладают свойством чётности . Это означает, что – истинное утверждение.

В случае бесконечного множества Х вводится специальный знак – квантор общности (всеобщности) – ". Тогда утверждение будет иметь вид "х.

Таким образом квантор всеобщности служит обобщением операции конъюнкции.

Пример: Рассмотрим утверждение: «Некоторые натуральные числа является чётными».

, тогда утверждение для Х, может быть представлено как дизъюнкция

Для дизъюнкции бесконечного множества значений вводится квантор существования – .

Для примера вид стандартного утверждения будет: «В множестве Х существуют числа, обладающие свойством четности». Для квантора $ может употребляться ещё формулировка – : «Верно, что некоторые числа из Х являются чётными». На самом деле это утверждение для множества Х является истинным.

II.  Исчисление предикатов. Теория классов.

Рассмотрим исчисление унарных предикатов. Формальная аксиоматическая система в этом случае называется теорией классов (типов, категорий). Впервые теория классов была сформулирована и использована для ведения публичных споров Аристотелем. В настоящее время она получила «второе дыхание» и была усовершенствована для применения в объектно-ориентированных языках (при построении формальной семантики), базах знаний (в фреймовых системах), построении хранилищ данных (Data Ware Haus – DWH), методов построения семантических профилей (набора свойств) типовых объектов и их поиска в сверхбольших массивах данных (Data Mining).

1.  Базовые утверждения (высказывания) теории классов.

Утверждения рассматривают отношения между двумя объектами S и Р. S и Р являются классами, а «S» и «Р» являются именами классов. Структура утверждения – «S есть Р», где S называется субъектом, а Р предикатом (свойством). Всего различных типов утверждений – 4.

1)  Общеутвердительное (А) – Всякий предмет х из S есть всякий предмет из Р. (Всякий ромб есть параллелограмм).

Формула –.

2)  Общеотрицательные (Е) – Всякий S не есть Р. (Всякий треугольник не есть ромб).

Формула – .

3)  Частноутвердительные (I ) – некоторые S есть Р. (Некоторые параллелограммы есть ромбы).

Формула – .

4)  Частноотрицательное (О) – Некоторые S не есть Р. (Некоторые параллелограммы не есть ромбы).

Формула – .

2.  Правильно построенные рассуждения в теории

классов.

Структура рассуждения: имеет содержательную интерпретацию «из R следует P». Посылок может быть несколько, все суть базовые утверждения, следствие – единственное базовое утверждение. Рассуждение называется правильным или силлогизмом, если оно тождественно истинно (общезначимо) при любых интерпретациях. «» называется выводом (дедукцией) из посылок R, (пишется RP либо R ® P ), если есть силлогизм. Знак «├» вывода интерпретируется логической операцией «®» импликации (следования). Правильный вывод (рассуждение): из истинности посылки R следует истинный вывод P. При интерпретации силлогизма логической операцией импликации: . В зависимости от количества посылок силлогизмы могут быть 0, 1, 2, и т. д. рангов.

3.  Логические законы теории классов – (0-й ранг).

Законы считаются изначально выводимыми (аксиомами), пишется «├ Р». Имеется всего три закона 0-го ранга.

1) ├ Закон тождества. Всякий обладает свойством S.

2) ├ù Закон противоречия. Невозможна ситуация, когда предметы из класса S входят в Р (см. таблицу жердановых интерпретаций) и не входят в Р.

3) ├ Закон исключённого третьего. Для каждой конкретной сущности х, входящей в S, истинно одно из утверждений: «х входит в Р или х не входит в Р».

Если отменить закон исключённого третьего, то можно построить т. н. интуиционистскую логику.

4.  Интерпретация базовых утверждений.

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

Для интерпретации утверждений (высказываний) в теории классов выбраны т. н. Жердановы соотношения (Жердан – французский математик; исследовал теорию классов в 1947 – 1953), которые связывают два класса множеств предметов: класс S и класс Р.

Четыре Жердановых соотношения (интерпретации).

пересечение независимость включение тождество

классов классов классов классов

Жерданова таблица интерпретации утверждений.

Содержит истинность/ложность каждого базового утверждения.

5.  Логический (Аристотелев) квадрат.

(силлогизмы 1-го ранга с одной посылкой)

Вид квадрата предложил византийский логик Михаил Псёл.

Логический квадрат содержит все комбинации силлогизмов 1– го ранга.

R├ P, когда R и P принимает вид

различных базовых утверждений

A, E, I, O или их отрицаний.

Семантика элементов логического квадрата определяется следующими таблицами

Жерданова таблица Жерданова таблица

базовых утверждений элементов логического квадрата

а

б

в

г

семантика

A

O

л

и

л

и

и

л

и

л

противоречие

I

E

и

л

л

и

и

л

и

л

противоречие

A

E

л

л

л

и

и

л

и

л

противность

I

O

и

и

л

и

и

л

и

л

частичная

совместимость

A

I

л

и

л

л

и

и

и

и

подчиненность

E

O

л

и

и

и

л

л

л

л

подчиненность

а

б

в

г

A

л

л

и

и

E

л

и

л

л

I

и

л

и

и

O

и

и

л

л

Семантика логического квадрата

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

1)  Противоречие. Диагонали (А–О), (IE). Два утверждения не могут быть одновременно истинными либо ложными (см. Жерданову таблицу логического квадрата)

2)  Подчиненность. Ребра (A–I), (E–O). Если утверждения А, Е истинны, то обязательно должны быть истинны соответствующие утверждения I и О.

3)  Противность. Ребро (А–Е). Утверждения А, Е не могут быть одновременно истинными.

4)  Частичная совместимость. Ребро (IO). Утверждения I, O могут быть только одновременно истинными.

5.1. Примеры отрицаний высказываний:

а) I(S, P). Некоторые параллелограммы есть ромбы . Неверно, что некоторые параллелограммы есть ромбы (ложное высказывание).

б) . Некоторые параллелограммы не есть ромбы, . Неверно, что некоторые параллелограммы не есть ромбы.

5.2. Пример проверки тождественной истинности некоторых рассуждений. Каждый силлогизм должен быть истинным при всех интерпретациях а), б), в), г), тогда он называется правильным рассуждением.

1) 2) × 3)

а) л ® и = и а) л ® а) л ® и = и

б) л ® л = и б) л ® б) л ® и = и

в) и ® и = и в) и ® в) и ® л = л

г) и®и=и г) и ® г) и ® л = л

правильное правильное неправильное

1)  Все ромбы суть параллелограммы, отсюда следует, что некоторые параллелограммы суть ромбы.

2)  Все ромбы есть параллелограммы, но неверно, что некоторые ромбы не есть параллелограммы.

3)  Все ромбы не есть треугольники, отсюда следует, что некоторые ромбы не есть параллелограммы. Это неправильное рассуждение, ложный вывод.

Аристотелев квадрат представляет собой отношение выводимости между парами базовых утверждений и их отрицаний. При этом посылки и следствия могут меняться местами, образуя т. н. Прямые и обратные рассуждения.

Прямые рассуждения Обратные рассуждения

1. R ├ P 1. P ├ R

2. R ├ P 2. R

3. ├ P 3. P ├

4. ├ P 4.

Из 48 возможных прямых и обратных рассуждений и их отрицаний, которые можно составить по квадрату Аристотеля, правильными являются только 16. Далее строится таблица правильных рассуждений 1-го ранга.

1)  Диагональ .

Прямое рассуждение

О

А

а)

б)

в)

г)

не правильное

правильное

Правильное

не правильное

Обратное рассуждение

а)

б)

в)

г)

не правильное

правильное

Правильное

не правильное

2)  Ребро. и

а)

б)

в)

г)

не правильное

не правильное

Правильное

не правильное

а)

б)

в)

г)

не правильное

не правильное

правильное

не правильное

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

Таблица правильных прямых и обратных рассуждений

1-го ранга

Элемент

квадрата

Правильные прямые и

обратные рассуждения

Название

правильного рассуждения

1

Диагональ

(А–О)

*

противоречие

2

Ребро

(AI)

подчиненность

3

Ребро

(A–Е)

противность

4

Диагональ

(IE)

противоречие

5

Ребро

(I–О)

частичная

совместимость

6

Ребро

(Е–О)

подчиненность

Все неправильные рассуждения «вычеркнуты» из таблицы.

6.  Основные силлогизмы Аристотеля (2-го ранга)

Схемы рассуждений из двух посылок с тремя классами известны со времён Аристотеля, изучались во всех средневековых университетах. Из них могут быть составлены схемы рассуждений любого ранга >2. Схема рассуждений ранга=2 имеет вид ; .

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

Каждый элемент фигуры может быть одним из базовых утверждений . Таким образом можно получить различных троек, состоящих из 2-х посылок и 1-го заключения. Например, пусть умозаключение с двумя посылками имеет схему I-й фигуры и базовые утверждения . Обычно говорят, что I-я фигура имеет модус (АЕЕ).

Модус АЕЕ не является правильным рассуждением. Это проверяется по Жердановым таблицам. Ниже приводится пример умозаключения, построенного по этому модусу.

Таким образом, модус для 1-й фигуры даёт ложное умозаключение в формальном и содержательном смысле.

Оказывается из 256 комбинаций только 24 модуса общезначимы и дают правильные умозаключения (рассуждения).

Таблица правильных рассуждений 2-го ранга

Фигуры

Модусы

I

AAA, EAE, EIO, AII, AAI, EAO

II

EAE, AEE, EIO, AOO, EAO, AEO

III

AAI, IAI, AII, EAO, OAO, EIO

IV

AAI, AEE, IAI, EAO, EIO, AEO

Примеры:

Это рассуждение (умозаключение) имеет I-ю фигуру, модус ААА, который входит в таблицу правильных модусов.

Это рассуждение имеет I-ю фигуру, модус AII общезначимый, который входит в таблицу правильных рассуждений.

Для лучшего запоминания все силлогизмы имеют мнемонические имена, принятые еще в средние века в университетских курсах логики. Например,

В настоящее время таблица правильных силлогизмов включается в трансляторы объективно ориентированных языков высокого уровня (ООЯ). Например, трансляторы с ООЯ UML (Unified Modeling Language) универсального языка моделирования и язык «С++» содержит Аристотелевы таблицы.



Подпишитесь на рассылку:

Исчисление

Квант

Проекты по теме:

Основные порталы, построенные редакторами

Домашний очаг

ДомДачаСадоводствоДетиАктивность ребенкаИгрыКрасотаЖенщины(Беременность)СемьяХобби
Здоровье: • АнатомияБолезниВредные привычкиДиагностикаНародная медицинаПервая помощьПитаниеФармацевтика
История: СССРИстория РоссииРоссийская Империя
Окружающий мир: Животный мирДомашние животныеНасекомыеРастенияПриродаКатаклизмыКосмосКлиматСтихийные бедствия

Справочная информация

ДокументыЗаконыИзвещенияУтверждения документовДоговораЗапросы предложенийТехнические заданияПланы развитияДокументоведениеАналитикаМероприятияКонкурсыИтогиАдминистрации городовПриказыКонтрактыВыполнение работПротоколы рассмотрения заявокАукционыПроектыПротоколыБюджетные организации
МуниципалитетыРайоныОбразованияПрограммы
Отчеты: • по упоминаниямДокументная базаЦенные бумаги
Положения: • Финансовые документы
Постановления: • Рубрикатор по темамФинансыгорода Российской Федерациирегионыпо точным датам
Регламенты
Термины: • Научная терминологияФинансоваяЭкономическая
Время: • Даты2015 год2016 год
Документы в финансовой сферев инвестиционнойФинансовые документы - программы

Техника

АвиацияАвтоВычислительная техникаОборудование(Электрооборудование)РадиоТехнологии(Аудио-видео)(Компьютеры)

Общество

БезопасностьГражданские права и свободыИскусство(Музыка)Культура(Этика)Мировые именаПолитика(Геополитика)(Идеологические конфликты)ВластьЗаговоры и переворотыГражданская позицияМиграцияРелигии и верования(Конфессии)ХристианствоМифологияРазвлеченияМасс МедиаСпорт (Боевые искусства)ТранспортТуризм
Войны и конфликты: АрмияВоенная техникаЗвания и награды

Образование и наука

Наука: Контрольные работыНаучно-технический прогрессПедагогикаРабочие программыФакультетыМетодические рекомендацииШколаПрофессиональное образованиеМотивация учащихся
Предметы: БиологияГеографияГеологияИсторияЛитератураЛитературные жанрыЛитературные героиМатематикаМедицинаМузыкаПравоЖилищное правоЗемельное правоУголовное правоКодексыПсихология (Логика) • Русский языкСоциологияФизикаФилологияФилософияХимияЮриспруденция

Мир

Регионы: АзияАмерикаАфрикаЕвропаПрибалтикаЕвропейская политикаОкеанияГорода мира
Россия: • МоскваКавказ
Регионы РоссииПрограммы регионовЭкономика

Бизнес и финансы

Бизнес: • БанкиБогатство и благосостояниеКоррупция(Преступность)МаркетингМенеджментИнвестицииЦенные бумаги: • УправлениеОткрытые акционерные обществаПроектыДокументыЦенные бумаги - контрольЦенные бумаги - оценкиОблигацииДолгиВалютаНедвижимость(Аренда)ПрофессииРаботаТорговляУслугиФинансыСтрахованиеБюджетФинансовые услугиКредитыКомпанииГосударственные предприятияЭкономикаМакроэкономикаМикроэкономикаНалогиАудит
Промышленность: • МеталлургияНефтьСельское хозяйствоЭнергетика
СтроительствоАрхитектураИнтерьерПолы и перекрытияПроцесс строительстваСтроительные материалыТеплоизоляцияЭкстерьерОрганизация и управление производством

Каталог авторов (частные аккаунты)

Авто

АвтосервисАвтозапчастиТовары для автоАвтотехцентрыАвтоаксессуарыавтозапчасти для иномарокКузовной ремонтАвторемонт и техобслуживаниеРемонт ходовой части автомобиляАвтохимиямаслатехцентрыРемонт бензиновых двигателейремонт автоэлектрикиремонт АКППШиномонтаж

Бизнес

Автоматизация бизнес-процессовИнтернет-магазиныСтроительствоТелефонная связьОптовые компании

Досуг

ДосугРазвлеченияТворчествоОбщественное питаниеРестораныБарыКафеКофейниНочные клубыЛитература

Технологии

Автоматизация производственных процессовИнтернетИнтернет-провайдерыСвязьИнформационные технологииIT-компанииWEB-студииПродвижение web-сайтовПродажа программного обеспеченияКоммутационное оборудованиеIP-телефония

Инфраструктура

ГородВластьАдминистрации районовСудыКоммунальные услугиПодростковые клубыОбщественные организацииГородские информационные сайты

Наука

ПедагогикаОбразованиеШколыОбучениеУчителя

Товары

Торговые компанииТоргово-сервисные компанииМобильные телефоныАксессуары к мобильным телефонамНавигационное оборудование

Услуги

Бытовые услугиТелекоммуникационные компанииДоставка готовых блюдОрганизация и проведение праздниковРемонт мобильных устройствАтелье швейныеХимчистки одеждыСервисные центрыФотоуслугиПраздничные агентства

Блокирование содержания является нарушением Правил пользования сайтом. Администрация сайта оставляет за собой право отклонять в доступе к содержанию в случае выявления блокировок.