Реферат: Логика предикатов с одним переменным

Мы будем говорить, что в формулах

( "х) U(х) и ( $х) U(х)

кванторы ( "х) и ( $х) относятся к переменному х или что переменное х связано соответствующим квантором.

Предметное переменное, не связанное никаким квантором, мы будем называть свободным переменным.

Формулы, в которых из операций алгебры высказываний имеются только операции , и , а знаки отрицания относятся только к элементарным предикатам и высказываниям, будем называть приведёнными формулами.

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

Если две формулы U и B, отнесённые к некоторому полю M, при всех замещениях переменных предикатов, переменных высказываний и свободных предметных переменных соответственно индивидуальными предикатами, определёнными на M, индивидуальными высказываниями и индивидуальными предметами из M, принимают одинаковые значения И или Л, то мы будем говорить, что эти формулы равносильны на поле M.

Если две формулы равносильны на любых полях M, то мы будем их называть просто равносильными .

Нормальную формулу, равносильную некоторой формуле U, мы будем называть нормальной формой формулы U.

§1. Логика предикатов с одним переменным

Мы будем рассматривать формулы логики предикатов, содержащие предикаты, которые зависят только от одного переменного. Логика, в которой употребляются только такие выражения, соответствует той, которая описана Аристотелем и вошла как традиционный элемент в систему гуманитарного образования. Известные формы высказываний этой логики и формы умозаключений, так называемые «модусы силлогизмов», выражаются полностью в символике логики предикатов от одного переменного.

Теорема. Если формула логики предикатов, содержащая только предикаты от одного переменного, выполнима на некотором поле M, то она выполнима на поле , содержащем не более элементов, где n - число предикатов, входящих в рассматриваемую формулу.

Пусть формула U(A₁ , ..., A_n ), содержащая только символы предикатов A₁ , ..., A_n , каждый из которых зависит от одного переменного, выполнима на некотором поле M. эту формулу мы можем предполагать представленной в нормальной форме, а все предметные переменные в ней связанными. В самом деле, какова бы ни была формула U, мы можем, произведя над ней преобразования, привести её к виду, в котором все кванторы предшествуют остальным символам формулы, при этом состав её предикатов и предметных переменных не изменяется. Если в U есть свободные предметные переменные, то можно связать их квантором общности.

Итак, допустим, что U – нормальная формула. Тогда мы можем представить её следующим образом:

(s x ₁ )(s x ₂ )...(s x_p ) B(A ₁ , ..., A_n , x ₁ , ..., x_p ),

где каждый из символов (s x_i ) обозначает квантор ("x_i ) или ($x_i ), а формула

B(A ₁ , ..., A_n , x₁ , ..., x_p )

кванторов не содержит.

В формуле B(A ₁ , ..., A_n , x ₁ , ..., x_p ) все переменные x ₁ , ..., x_p входят в предикаты A ₁ , ..., A_n , и её можно записать в виде

B(A ₁ (), ..., A_n ()),

где i ₁ , ..., i_n – числа от 1 до p . Однако, будет удобнее пользоваться выражением

B(A ₁ , ..., A_n , x₁ , ..., x_p ),

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

Покажем, что если для некоторого поля M существуют индивидуальные предикаты

,..., ,

для которых формула U(,..., ) истинна, то эта формула истинна и на некотором подмножестве этого поля, содержащем не более элементов, так как иначе наше утверждение тривиально. Разобьём элементы множества M на классы следующим образом. Для каждой последовательности, содержащей n символов И и Л в произвольном порядке (И , Л , Л , ..., И ,), существует часть (может быть, пустая) множества M, содержащая те и только те элементы x , для которых последовательность значений предикатов (x ), (x ), ..., (x ) совпадает с данной последовательностью символов И и Л .

Обозначим через ₁ , ₂ , ...,_n

последовательность символов И и Л, где _i представляет собой И или Л , а соответствующий этой последовательности класс элементов x обозначим

, , ..., .

Некоторые из этих классов могут оказаться пусты, так как может случиться, что для некоторой последовательности ₁ , ₂ , ...,_n не существует такого элемента, для которого предикаты , , ..., принимают соответствующие значения ₁ , ₂ , ...,_n . Вместе с тем каждый элемент множества M принадлежит одному из классов , и различные классы общих элементов не имеют. Число всех классов (пустых и непустых) равно числу последовательностей ₁ , ₂ , ...,_n , т. е. . Следовательно, число q непустых классов не превышает . Выберем из каждого непустого класса по одному элементу и обозначим эти элементы

a ₁ , a ₂ , ..., a _q .

Множество всех этих элементов обозначим .докажем, что если формула U(, ..., ) истинна на поле M, то она истинна и на поле (так как –­ часть поля M, то предикаты определены на ). каждому элементу x поля M поставим в соответствие элемент из , принадлежащий тому же классу, что и х . В существует один и только один такой элемент. Элемент из , поставленный в соответствие х , обозначим (х ). Можно сказать, что мы построили функцию, определённую на множестве M и принимающую значения из множества .

Легко видеть, что имеет место следующая равносильность:

(х ) ~ ((х )).

Действительно, (x ) принадлежит тому же классу , что и x . Но, по определению, для элементов одного и того же класса каждый предикат принимает одно и то же значение. Отсюда следует, что если в формуле U(, ..., ) для каждого предметного переменного t заменить каждое выражение (t ) через ((х )), то формула U(, ..., ) перейдёт в формулу (, ..., ), равносильную первой. Написание формулы отличается от U только тем, что все предметные переменные x, y, z, …, u формулы U замещены соответственно через (х ), (y ), ..., (u ). Это следует из того, что по условию формула U(, ..., ) содержит только предикаты , и поэтому всякое предметное переменное входит только под знаком одного из этих предикатов.

Пусть R (x, y, ..., u ) – предикат, определённый на поле M. Введём обозначение

R (x, y, ..., u ).

Под этим выражением мы будем понимать предикат, зависящий от y, z, ..., u (или высказывание, если, y, z, ..., u отсутствуют) и принимающий значение И , когда R (y, z, ..., u ) имеет значение И для данных y, z, ..., u и для всех x , принадлежащих полю , и принимающий значение Л в противоположном случае. Введём также выражение

R (x, y, ..., u ),

которое представляет собой предикат от y, ..., u и принимает значение И , когда R (x, y, ..., u ) имеет значение И для y, ..., u и по крайней мере для одного значения x из поля , и значение Л в противоположном случае. Знаки и будем называть ограниченными кванторами . Если мы все переменные предиката R (x, y, ..., u ) свяжем ограниченными кванторами, например

... R (x, y, ..., u ),

то получим формулу, отнесённую к полю . покажем, что выражение

("x ) R ((х ), y, ..., u )