Основные законы логики предикатов

Как и в ЛВ, в логике предикатов существуют логически истинные формулы, называемые тавтологиями или законами ЛП. Ниже приводятся и комментируются наиболее важные.

Закон удаления квантора общности

Общее правило, истинное для каждого ξ, должно быть истинно и для отдельного случая а, являющегося элементом расширения формулы φξ.

Закон введения квантора существования

То, что истинно для отдельного случая а, являющегося элементом расширения формулы φξ, должно быть истинно в качестве произвольно­го примера подстановки предметной переменной ξ формулы φξ. Из ис­тинности высказывания «Вещь а, принадлежащая универсуму, является круглой» следует истинность высказывания «Существует такая ξ, что ис­тинно ^uξ круглая”»:

Закон подчинения кванторов

Из истинности универсально квантифицированного высказывания следует истинность экзистенциально квантифицированного высказыва­ния; из ложности экзистенциально квантифицированного высказывания следует ложность универсально квантифицированного высказывания:

Закон противоречия

Противоречащие друг другу высказывания не могут быть вместе ни истинны, ни ложны:

Закон непустоты универсума логического квадрата

В универсуме логического квадрата должна существовать хотя бы одна вещь, выполняющая формулу φξ или ее отрицание -φξ (или и то и другое):

Законы взаимной определимости кванторов

Каждый квантор может быть определен в терминах противополож­ного ему квантора.

Законы дистрибутивности кванторов относительно знака конъюнкции

Высказывание «Все вещи в универсуме круглые и синие» эквивален­тно высказыванию «Все вещи в универсуме круглые и все вещи в уни­версуме синие». Значит, квантор общности дистрибутивен относительно знака конъюнкции без ограничений:

Из высказывания «В универсуме существует круглая и синяя вещь» выводимо высказывание «В универсуме существует круглая вещь и в универсуме существует синяя вещь», но обратная выводимость в общем неверна. Из того, что какая-то вещь круглая, а другая синяя, не следует с необходимостью, что какая-то (возможно, третья) вещь круглая и синяя одновременно. Значит, квантор существования дистрибутивен относи­тельно знака конъюнкции с ограничением:

Законы дистрибутивности кванторов относительно знака дизъюнкции

Из высказывания «Все вещи в универсуме круглые или все вещи в универсуме синие» выводимо высказывание «Все вещи в универсуме круглые или синие», но обратная выводимость в общем и целом неверна. Например, из того что все целые числа четные или нечетные, не доказу­емо, что все целые числа четные или все целые числа нечетные. Значит, квантор общности дистрибутивен относительно знака дизъюнкции с ог­раничением:

Высказывание «В универсуме существует круглая или синяя вещь» эквивалентно высказыванию «В универсуме существует круглая вещь или в универсуме существует синяя вещь». Значит, квантор существова­ния дистрибутивен относительно знака дизъюнкции без ограничений:

Законы дистрибутивности кванторов относительно знака импликации

Из высказывания «Для каждого числа, если оно четное, то оно целое» выводимо высказывание «Если каждое число четное, то каждое число це­лое».

Из высказывания «Если существует четное число, то существует це­лое число» выводимо высказывание «Существует такое число, что если оно четное, то оно целое». Но обратная выводимость в общем и целом неверна:

Из высказывания «Существует такое число, что если оно четное, то оно целое» выводимо высказывание «Если каждое число четное, то су­ществует целое число». Но обратная выводимость в общем и целом не­верна:

Из высказывания «Если существует четное число, то все числа це­лые» выводимо высказывание «Для каждого числа верно, что если оно четное, то оно целое». Но обратная выводимость в общем и целом не­верна:

Из сказанного следует, что кванторы общности и существования дис­трибутивны относительно знака импликации лишь с ограничением.

Законы перестановки кванторов

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

Контрольные вопросы и задания

1. Формализуйте в терминах логики предикатов следующие выска­зывания:

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

б) Всякому случается попасть в неожиданные ситуации, но не каждый выходит из них достойно;

в) Если ты даешь кому-нибудь что-нибудь, то тем самым ты ока­зываешь услугу и вправе надеяться на благодарность;

г) Все люди любят, чтобы с ними обходились вежливо, но только некоторые из них вежливы сами;

д) Татьяна любит всех, кроме самой себя.

2. Проверьте общезначимость следующих выводимостей:

² Метапеременная ζ, вместо которой могут подставляться различные пред­метные переменные х, у, z, ., читается как «дзета».

3. Формализуйте и докажите:

а) Каждый человек мыслит. Следовательно, некоторые двуногие животные мыслят;

б) Татьяна любит Онегина. Онегин не любит Татьяну. Следова­тельно, не всегда истинно, что если какой-то человек любит другого, то и другой человек любит первого;

в) Если существует некто, кого любят все, то каждый любит кого- нибудь;

г) Число 5 больше числа 3. Следовательно, число 3 не больше числа 5;

д) Эту девушку зовут Татьяна Ларина. Если вам не нравится Та­тьяна Ларина, значит, вам не нравится эта девушка.