Равносильные формулы логики предикатов

После квантификации, т.е. использование квантора всеобщности или существования к свободной переменной одноместного или /и-местного предиката, можно получить различные формулы. Например, V* VyP(x, у); /в VxP(x, у); Зап VyP(x, у); /х ЗхР(х, у); Зап 3yP(xt у).

Формулы, которые содержат одинаковые кванторы, называют равносильными, или эквивалентными. Они имеют такой вид:

Vx VyP(x, у) = VxP(xf у) (формулы вида Vx УуР(х, у) и вида /в УхР(х, у) истинно тогда и только тогда, когда Р(х, у) - тождественно истинный предикат);

Зап 3yP(xt у) = Зу ЗхР(х, у) (формулы вида Зап 3yP(xt у) и вида Зу 3xP(xt у) истинны только тогда, когда Р(х, у) является тождественно-истинным предикатом).

Отрицание высказываний с кванторами

Возражения в символической логике - логическая операция, выраженная с помощью союза "неправильно". Например, отрицанием высказывания "Все студенты изучают математику" будет высказывание "Неверно, что все студенты изучают математику".

Отрицание высказывания с кванторами всеобщности формально выражается: -" VxP(x), с квантором существования так: - 3xF(x).

оспаривающее его высказывания с квантором всеобщности -" VxP(x) имеет то же значение истинности, что и высказывания с квантором существования, с отрицанием высказывания Зап -* F(x), а отрицания высказывания с квантором существования -" 3xF(x) имеет то же значение истинности, что и высказывания с квантором всеобщности с отрицанием высказывания Vx -" Р(х).

На основании определения взаимозависимости квантификаторы всеобщности и существования с возражениями устанавливают равносильность (эквивалентность) таких формул: VxP(x) = Зх -" Р(х); -> 3xF(x) = Vx - F(x).

Отношение следования в логике предикатов

Между формулами F и Q логики предикатов существует отношение логического следования (F -> Q) тогда и только тогда, когда в процессе определения значений свободных переменных, входящих в структуру формулы "если F - истинно, то Q - истинное", между формулами вида Fr F2,... Fn и формулой вида Q существует отношение логического следования тогда и только тогда, когда при определении значений свободных переменных всех формул и если Fx, F2,... Fn истинно, то Q - истинно.

Законы логики предикатов

Законом логики предикатов называют формулу (регулярное выражение), что за любого подставления значений свободных переменных принимает значение "истина". Такая формула - общезначимая (тождественно-истинна): Vx(P(x) V v - Г(х)).

Законы логики предикатов можно вывести из законов логики высказываний через подстановку вместо пропозиційних переменных предикатов. Возьмем, например, первый закон контра-позиции логики высказываний (А -> В) -> (->- " -" А). Вместо переменной А подставляем предикат Р(х), а вместо переменной В - предикат Q(x). Получаем формулу ((Р(х) ->Q(x)) ->((-" Q(x) -" -> -и Г (х))9 которая является загальнозначущою формуле, то есть законом логики предикатов.

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

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

Правила построения аналитической таблицы:

где F(t) - результат замены всех свободных переменных х в F на любой замкнутый терм t.

где Р(Л) - результат замены всех свободных вхождений х в Г на предметную константу к, которая еще не была в таблице.

где Р(£) - результат замены всех свободных вхождений х в Г на предметную константу которая не была в таблице.

где F(t) - результат замены всех свободных вхождений х в F на любой замкнутый терм.

Исчисление предикатов (система вывода формул вида Q из формул вида F по принципу логического следования) - это система символов и правил логического вывода из аксиом произвольных формул с целью их доведения на истинность; осуществление логических операций над одноместными и многоместными предикатами. Различают два вида исчисления предикатов: натуральное и аксиоматическое.

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

1. Правило устранение импликации (УИ) (правило модус понненс):

(чит.: из двух формул вида Г, Г -> ф можно получить формулу вида (5).

2. Правило введения квантора всеобщности (ВУ):

(чит.: если х не является свободным в Г, то из формулы вида Р -* ф(я) можно вывести формулу вида Г-ьУуЖу))-

3. Правило устранение квантора всеобщности (УУ):

(чит.: из формулы вида VF(x) -> Q(y) можно вывести формулу вида F(x) -" Q(y)).

4. Правило введения квантора существования (ВЗ):

(чит.: если х не является свободной в Q, то из формулы вида F(x) -" Q можно вывести формулу вида 3yF(y) -► Q)"

5. Правило устранение квантора существования (УЗ):

(чит.: из формулы вида 3F(x) -> Q можно вывести формулу вида F(x) -> Q).

Аксиоматическое исчисление логики предикатов означает построение системы доказательства теорем на основании аксиом по правилам вывода.

Аксиомы логики предикатов (ЛП) дополняют аксиомы логики высказываний (ЛВ) (см. 4.2.1), то есть к ним добавляют новые аксиомы:

На основании аксиом выводят (доказывают) формулы, которые являются теоремами на основании таких правил введения квантификаторы всеобщности V и существования 3:

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

Атрибутивные (категорические) высказывания и простой категорический силлогизм, которые исследуют в традиционной логике (см. 3.4.2; 3.4.3), формализуются на языке логики предикатов.

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

1. Загальностверджувальне высказывания (А), формальное выражение которого в традиционной логике "все 5 есть Р" - высказывания, в котором утверждается присущие свойства Г всем предметам определенного класса, В логике предикатов 5 и Р определяют как пропозиційні переменные, вместо которых можно подставить аргументы и придать высказыванию значение истинности или ложности. Например: "Все треугольники являются геометрическими фигурами" (/), "Все имена собственные пишут с большой буквы"; "Все птицы летают" (х), а именно высказывания как высказывания, выражающий одноместный предикат.

Регулярное выражение загальностверджувального высказывания на языке логики предикатов: Ух(Р(х) ->(?(*))" Дв V - символ, что обозначает квантор всеобщности, Г, (? - свойство, х о-позиционная переменная (чит.: для всех х, если присуще свойство Р, то х присуще свойство <?).

2. Загальнозаперечне высказывания (Е), формальное выражение которого в традиционной логике "ни одно 5 не есть Р" - высказывания, в котором отрицается свойство Р у всех предметов определенного класса: "Ни одна собака не является кошкой" (/), "Ни одно живое существо не может жить долго без еды"; "Ни один студент не учится на отлично" (х).

Регулярное выражение загальнозаперечного высказывания на языке логики предикатов: Ух(Р(х) -> - Я(х)) (чит.: для всех х, если х присуще свойство Р, то х не обладает свойством в).

3. Частковостверджувальне высказывания (/), формальное выражение которого в традиционной логике "некоторые 5 есть Р" - высказывания, в котором свойство Р приписывается определенным предметам определенного класса (подкласса класса А). Например: "Некоторые люди являются спортсменами"; "Некоторые люди являются долгожителями" (и).

Регулярное выражение частковостверджувального высказывания на языке логики предикатов Зх(Р(х) Я(х)) (чит.: существует такой предмет х, которому присуще свойство Р и присуще свойство (и), где 3 - символ, что обозначает квантор существования.

4. Частковозаперечне высказывания (О), формальное выражение которого в традиционной логике "некоторые 5 не есть Р" - высказывания, в котором определенное свойство Г отрицается в определенном количестве предметов определенного класса (подкласса класса А): "Некоторые логические теории не являются двузначными по значению истинности"; "Некоторые люди не играют в шахматы" (и).

Регулярное выражение частковозаперечного высказывания на языке логики предикатов ЗхР(х) Л -"Я{х)) (чит.: существует такой предмет х, которому присуще свойство Р и не присуще свойство А).

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

1. Загальностверджувальне высказывания (А):

II. Формализация простого категорического силогизма языке логики предикатов. Первую формализацию простого категорического силогизма совершил Я. Лукасевич.

Формализация простого категорического силогизма означает его формальное изображение языке логики предикатов с целью более точного выведения заключения из предположений. Подаем выведения заключения из оснований по правилам первой фигуры и правильного модуса AAA (модус Barbara). В традиционной логике он имеет вид:

на Языке логики предикатов:

(Vx(M(x) -> Р(х)) а Vx(Q(x) -" М(х))) -> Vx(Q(x)) -*Р(х)) (чит.: если правильно, что для каждого х из М(х) следует Р(х), и если правильно, что для каждого х из Q(x) следует М(х), то для каждого х верно, что Q(x) следует Р(х).Формалізація высказываний на языке логики предикатов и интерпретация формул логики предикатов.

Формализация высказываний с определенным содержанием означает их превращение в язык логики предикатов, а интерпретация логики предикатов - установление сферы действия кванторних выражений вида УхР(х), ЗхР(х), УхР(х, у), УхР{х, у, г)в контексте рассуждений о определенное множество предметов, которым присуще свойство Р и установление определенного вида отношений между предметами, которые относятся к этой множественного числа.

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

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

Последовательность осуществления названных логических операций:

I. Определяют предметную сферу рассуждений, в рамках которой формализуют высказывания и интерпретируют кванторні формулы.

II. Задают точную сферу соображений - класс (множество) М, в пределах которой кванторна формула определяет свойства и отношения.

Например:

- в математике: множество всех натуральных чисел (арифметика); множество всех множеств (теория множеств); множество всех геометрических фигур (геометрия) и т.п.;

- в логике: множество всех логических законов; множество всех высказываний; множество всех формально-логических систем и т.п.;

- в социальном мире: множество всех людей; множество всех политиков, всех юристов, всех ученых, всех студентов и др.;

- в сфере права: множество всех государств; множество всех граждан определенного государства; множество всех субъектов права, социальные действия которых регулируются нормами права; множество всех нормативно-правовых актов, разработанных государством ИУ, и т.д.

III. В точно определенном множестве М чисто абстрактно задают свойства, присущие предметам, которые принадлежат к определенной множества и отношения (бинарные, тернарні и др.) между предметами, которые относятся к этой множества М.

IV. Придают значение истинности высказываний, выражающих свойства или отношения.

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

1. Каждая тождественно-истинная формула является логическим законом в пределах определенной формальной системы. Это означает, что каждой тождественно-истинной формуле присуще свойство "быть логическим законом". Для формализации этого выражения определяем: слово "каждый", что естественным языком выражает квантор всеобщности (V), "логический закон" - одноместный предикат Р(х), "тождественно-истинная формула" (одноместный предикат Я(х) "определенная формальная система" (сфера действия квантора всеобщности (чит.: каждая формула имеет свойство "быть тождественно-истинной формулой", имеет свойство "быть логическим законом" в пределах определенной формальной системы). Формула: Ух(Р(х) -> С?(дг)£)).

2. Создаем формулу логики предикатов: Зх(Р(х) л-и (?(*). Интерпретируем ее в сфере символической логики. "Существует выражение х, который имеет свойство "формуле" и не имеет свойства "быть законом символической логики".

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

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

"В каждой (квантор всеобщности V) науке (одноместный предикат Р(х)) является (квантор существования 3) гипотезы (одноместный предикат Жу)> которые после их проверки на истинность (Ег) не становятся (отрицание следования) теориями (одноместный предикат Р(д)". Формула: УхР(х) -> ((ЗуЯ(в) -> (вг -> -" #(?))).

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

"Существуют (3) люди (Р(х)), которые (3) студентами ((?(*/)) и среди них есть (3) такие {Щг)), что учатся на отлично (В(с)) и занимаются научной работой (#д)). Формула: ЗхР(х) -> (((Зу () ()- > -> ((Згй(г) -> (В(с) Л На))).

На основании логического анализа определенного высказывания и определения его структуры можно осуществить символическая запись этого высказывания на языке традиционной логики и языком классической символической логики (логики высказываний и логики предикатов). Например:

И. "Все люди, которые работают, платят налоги".

1. На языке традиционной логики: "Все (квантор всеобщности выраженный на естественном языке) люди, работающие (субъекта), платят налоги (свойство Г)" (в этом высказывании связка "есть" выражена неявно, но она мыслится). Все 5 есть Р.

2. На языке логики высказываний. В логике высказываний абстрагируются от субъектно-предикатної структуры высказывания, и это высказывание определяют как простое. Обозначается символом А.

3. На языке логики предикатов (учитывается внутренняя структура высказывания): "Все (квантор всеобщности выраженный искусственным языком V) люди, работающие (подмножество индивидов, принадлежащих к множеству людей, которым присуще свойство работать Р(х) оплачивают налоги (свойство "платить налоги" <?(дг) (чит.: для всех индивидов, которым присуще свойство "работать", присуще свойство "платить налоги"). Формула: УхР(х) -> Я(х)).

II. "Некоторые языки являются трудными для изучения".

1. На языке традиционной логики: "Некоторые (квантор существования "некоторые" выражено на естественном языке) языка (S) есть (связка) трудными для изучения (предикат Р)". Некоторые S есть Р.

2. На языке логики высказываний. Простое высказывание А.

3. На языке логики предикатов: "Некоторые (квантор существования выражено искусственным языком 3) языка (Р(х)) является (3) трудными для изучения (Q(x)". ЗхР(х) -" Q(x).

Этому примеру может соответствовать и более сложный символический запись соответственно более точного выражения. Существуют (3) языка (Р(х)), которым присуще свойство "быть знаковой системой" (Q(y)) и свойство "быть трудными для изучения" (Н(г)). Формула: ЗхР(х) -> ((Q(y) (H(z)).

 
< Пред   СОДЕРЖАНИЕ   След >