Приложение логики предикатов в теории множеств

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

Ограниченные и конечные множества всегда на практике представляют некоторую интерпретацию объектов — обозначаются буквами, номерами и др.^[1], и на этом связь с областью интерпретации обрывается. Для понимания логики предикатов помогает теоретико-множественная интерпретация. Интересно обратить внимание на относительно новые демонстрации противоречивости в теории множеств, которые приводят к противоречиям в других приложениях с ее использованием^[2]. Вопрос, который остается открытым: существует ли логика, применимая к бесконечным множествам?

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

Предлагается рассмотреть применение теории множеств в популярном способе интерпретации классической логики диаграммами Венна.

Множество высказываний Р (х) представляется на диаграмме Венна как множество истинных высказываний Р (х) = Т. Тогда в любой подстановке Р (х/с) уже предполагается истинное значение Р© = с = Т, хотя в формуле после замены Р (с) = с подразумевается как булевская переменная.

Множество истинных высказываний на диаграммах Эйлера — Венна (рис. 3.2) задается следующим образом:

• 1) универсальный класс (универсум) W (x) обозначает некоторое ограниченное квадратом множество;
• 2) одноместный предикат Р (х) — характеристическая функция, собственное подмножество Р (х) с W (x), где истинный предикат Р (х) называется экзистенциалом;
• 3) инверсия одноместного предиката —Р (х) — дополнение Р{х) в W (x).

Рис. 3.2. Диаграмма Эйлера — Венна для высказываний Алгебра подмножеств W (x) может быть интерпретирована на ограниченных множествах и представлена графически — диаграммами Эйлера — Венна, что позволяет получить представление о структуре объекта, определяемого двумя или тремя свойствами ограниченных множеств (рис. 3.3).

Любую формулу с двумя и тремя предикатами можно интерпретировать на подмножествах из области определения 1У, рассматривать ее как утверждение относительно свойств некоторого множества и представить соответствующий экзистенциал графически с использованием операций с подмножествами или формулой в булевой алгебре.

Рис. 33. Представление алгебры подмножеств Диаграммы Эйлера — Веныа^[3] определяют результаты выполнения множественных операций с точками, искусственно упорядоченными в одном подмножестве.

Если W (x) — множество высказываний, которые могут принимать истинные или ложные значения, то подможество Р (х) < W (x) можно интерпретировать как распределение истинностных высказываний в упорядоченном размещении высказываний в W (x).

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

В приложениях теории множеств операции с собствеными подмножествами формируют новые собственные подмножества, которые характеризуются распределением значений истинности в W (x).

Лемма 3.1. Алгебра собственных подмножеств является булевой алгеброй.

Доказательством является выполнение законов булевой алгебры, что следует из применения этих законов к поразрядным двоичным логическим операциям с двоичными кодами. Длина двоичного кода, или двоичного вектора, — число высказываний в W (x). Бит i = (0, 1, 2,…, N- 1) Л^г-разрядного двоичного кода — истинный (1), если выбрано i-e высказывание в подмножество Р (х) из W (x) как иистинное, но может быть определено как ложное. К двоичным векторам (параллельно — к одноименным высказываниям) применимы логические операции (&, v, -.) и законы булевой алгебры.

Пусть W (x) = {а> Ь_у Су d_y е,/, g, h) — восемь высказываний, истинных или ложных.

Двоичный вектор 1 011 001 представляет упорядоченное собственное подмножество истинных высказываний {b, d, е_} /?}.

На множестве собственных подмножеств W_y представленным 8-разрядными двоичными строками кодов, определены код единицы 11 111 111 и код нуля 0, к которым, очевидно, поразрядно применимы законы нулевого и единичного элементов.

Рассмотрим булевские операции с подмножествами.

6. Законы нуля и единицы.

7. Свойство транзитивности импликации (силлогизм):

Интерпретация операции импликации для предикатов — отношение включения для подмножеств: если А (х) — подмножесто В (х) и В (х) — подмножество Q (x), то А (х) — также подмножество Q (x).

Преобразуем правило:

Проверяем:

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

Соответствующие теоретико-множественные отношения контролируются тестом с множествами А & В & Q = А:

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

Сохраняется в вычислениях только поразрядная логика операций с высказываниями и операциями &, v, -1.

Подстановку двоичных векторов для интерпретации формул логики называем М-интерпретацией в отличие от других множественных интерпретаций.

Операция инверсии вектора —А эквивалентна дополнению множества А до единичного (универсального) множества.

Операция конъюнкции с векторами А (х) & В (х) эквивалентна операции пересечения собственных подмножеств А (х) п В (х).

Операция дизъюнкции с векторами А (х) v В (х) эквивалентна операции объединения множеств А (х) и В (х).

Операция импликации А (х) —"В (х) с векторами эквивалентна отношению на собственных подмножествах «А (х) — подмножество множества В (х)».

В операциях с собственными подмножествами подразумевается, что истинности А (х) —> В (х) и А (х) & В (х) = Л (х) совпадают при выполнении операций с векторами, также —В —> -Л = Л —"? = —Л v й.

К предикатам, определяемым как собственные подмножества универсального множества W (x), применима только М-интерпретация.

• [1] Кантор Г. Труды по теории множеств. М.: Наука, 1985.
• [2] Биркгоф Г., Барты Т. Современная прикладная алгебра.
• [3] Мощепский В. А. Лекции по математической логике.