Общезначимость и выполнимость формул. Проблема разрешимости.

§8.   Общезначимость   и   выполнимость   формул.   Проблема разрешимости. Определение 1. Формула   А   логики   предикатов   называется  выполнимой   в   области   М,   если существуют значения переменных входящих в эту формулу и отнесенных к области М (иначе – существует модель), при которых формула А принимает истинные значения. Определение 2. Формула А логики предикатов называется выполнимой, если существует область, на которой эта формула выполнима. Определение 3. Формула   А   логики   предикатов   называется  тождественно­истинной   в   области   М (выполнимой),   если   она   принимает   истинные   значения   для   всех   значений   переменных, входящих в эту формулу и отнесенных к этой области. Определение 4. Формула А логики предикатов называется  общезначимой, если она тождественна истинна на всякой области (на любой модели).  Если   две   равносильные   формулы   логики   предикатов   соединить   знаком эквиваленции   , то полученная формула будет принимать значение И для любого набора переменных в любой области, т.е. будет общезначимой. Это понятие является обобщением понятия тождественной истинности   формулы логики   высказываний.   Все   логические   законы,   представленный   в   логике   высказываний формулами (1 ­30) являются общезначимыми формулами логики предикатов и выражают, как и другие общезначимые формулы, законы логики на языке логике предикатов.  Наиболее   употребительные   специфические   законы   логики   предикатов,   как   было отмечено выше, представлены формулами (31 ­54). ├ Общезначимость формулы логики предикатов, например, F обозначается  F. Все  формул. Например, подставляя   – вместо х предикат Р(х1,…,хn), получаем x  (х1,…,хn). При n=1 имеем общезначимую формулу ­   общезначимая   формула   логики )( [ xPx общезначимые формулы могут быть источниками новых   в (14) – закон исключенного третьего   общезначимую формулу Р(х1,…,хn) P  )( )( xP xP предикатов. ,   и,   таким   образом   , xP Из   тождественно   истинной     формулы   логики   высказываний   (2)   x подстановкой   вместо   х   предиката   Р(х,   y),   а   вместо   y­   предиката   Q(x,y)   получаем общезначимую формулу  yxQyxQyxP  и т. д. yxP ,(  y y ,( ,( ,( )  )  )   ( )] x ├ x )  Определение 5. Формула А логики предикатов называется тождественно ложной в области М,  если она принимает ложные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области (иными словами, на данной модели). Определение 6. Формула А логики предикатов называется  тождественно ложной (невыполнимой), если она  тождественно ложна на всякой области (на всякой модели). Например,   формула    )( xPx [  xP ( )]   является   тождественно   ложной (невыполнимой) формулой логики предикатов. Из приведенных определений с очевидностью следует: 1. Если формула А общезначима, то она и выполнима на всякой области (модели). 2. Если формула А тождественно истинна в области М, то она и выполнима в этой области . 3. Если формула А тождественно ложна в области М , то она не выполнима в этой области . 4. Если формула А не выполнима, то она  тождественно ложна на всякой области (на всякой  модели). 5. Для того, чтобы формула А логики предикатов была общезначима, необходимо и достаточно, чтобы ее отрицание было не выполнимо. 6. Для того, чтобы формула А логики предикатов была выполнимой, необходимо и достаточно, чтобы формула  A  была не общезначима. Рассмотрим пример Пример  Доказать равносильность (логическое тождество):  ( yxPyx   ,( uv ,( )) ( yPx Заметив, что в каждой из кванторных подформул обе предметные переменные связаны и что, таким образом, они являются высказываниями, введем обозначения: uvuPv vPu xPy ),( yx ,( )) )   ),( xy  А= В= vuvPu ),( ), ,( xy yPx вторую предметные переменные через n1 и n2, соответственно: uvuPv ),( ) ,( yx xPy yPx vPu ,( yx ) ),( uv       ,   или   обозначив   первую   и 1 2 1 2 , ( ), nnPnn  А= В этих обозначениях заданное для рассмотрения тождество будет выглядеть так:  ) Произведя равносильные преобразования, можем убедиться в справедливости этого nnPn 1 n  AB BA   В= ). ( ,  ) ( . 2 1 2 ( BA  тождества:  ( ABBA )  6  ABA  BAB 9,15  ЛB  BA 10  BA Если   охарактеризовать   рассматриваемое   выражение   в   целом,   то   видим,   что   это общезначимая формула.  Пример  Определить тип формулы  Пусть Р(х) : “ Число х ­ четно –” предикат, определенный в М=N2. Таким образом, рассматриваемая формула на данной модели представляет собой следующее   утверждение:   “   Среди   натуральных   чисел   существуют   как   четные,   так   и нечетные ”. Очевидно, что это высказывание истинно и, таким образом, на данной модели формула F тождественно истинна. xPyx )( yP  )] F  ( [ . . Однако, если этот же предикат задать на множестве  M=NхN,где  N  – множество четных чисел, то формула F  на такой модели  окажется тождественно ложной. Учитывая изложенное, заключаем, что рассматриваемая формула F выполнима (но не общезначима). Пример  Для   формулы   yP ,( ), zyx подобрать   модель,   на   которой   она   является тождественно истинной (и, таким образом, в целом выполнимой).  Пусть Р(x, x, y): “x∙x=y”, или иначе “x2=y” – предикат, определенный на множестве натуральных чисел, т.е. М=N. Тогда рассматриваемая формула выражает утверждение о существовании   натурального   квадрата   натурального   числа,   что,   очевидно,   является истиной,   т.е.   на   данной   модели   формула   тождественно   истинна,   что   и   требовалось доказать. Пример  Рассмотрим формулу   . Это выполнимая формула. Действительно, если Р(х, y, x): “x+y=x” – предикат суммы, то на M=N существует подстановка вместо y соответствующего значения, дающего значение истинности данной формуле. Очевидно, это y=0, поскольку в этом случае получаем “х=х”. ,( xyx ) , xP Если же P(x, y, x): “xy=x” – предикат произведения, то таким значением y является y=1, так как при нем получаем истинное высказывание   xx (  1 x ) . Но   это   единственные   подстановки,   приводящие   к   верным   утверждениям,   что   и говорит именно о выполнимости данной формулы (но не об ее общезначимости). Пример  ,( yx Является ли общезначимой формула:  Пусть P(x, y) – предикат порядка (бинарного отношения ) “ x  ”, определенный на конечном множестве натуральных чисел M1. Тогда при подстановке в формулу вместо свободной переменной  y  величины     мы получим истинное утверждение, а при подстановке  любой другой  константы  из  множества М1  – ложное.  Таким  образом, рассматриваемая формула не является общезначимой.  max M xP ,( yx  a xP ? y    y ) )   1 zA )( z  )( yA . Покажем, что она невыполнима.  Пример  Рассмотрим формулу  Допустим противное, т.е. что она выполнима. Это означает, что существует такое , то данная множество М и такой конкретный предикат   формула превращается в такой конкретный предикат  , который, в свою очередь, превращается в истинное высказывание при всякой подстановке вместо y элементов   из   множества   М.   Тогда   высказывание   истинно,   как   мы   только   что   установили.   Следовательно, zA yB истинны высказывания  0A   в нем, что когда   )( yA Mzy ,  )( z   Возьмем   любое )( z 0 yA ( My 0 zA )(0 z yA )( yB   и  zA   ) ) ( ) ( . . 0 0 0 0 0 0 0 Из   истинности   второго   высказывания   заключаем,   что   высказывание   ) истинно (поскольку “для всех предметных переменных”, как бы они ни обозначались). Но это противоречит истинности первого высказывания  0 yA 0 yA ( ) ( . 0 0 Таким образом, наше предположение о выполнимости формулы неверно. Проблема   разрешимости  в   логике   предикатов   ставится  так  же,   как  и   в  алгебре логики: существуют ли алгоритмы, позволяющие для любой формулы А логики предикатов установить, к какому типу (классу) она относится, т.е. является ли она общезначимой, выполнимой   или   тождественно   ложной   (невыполнимой).   Если   бы   такой   алгоритм существовал, то, как и в алгебре высказываний, он сводился бы к критерию тождественной истинности   любой   формулы   логики   предикатов.   Отметим,   что,   в   отличие   от   алгебры логики,   в   логике   предикатов   не   применим   метод   перебора   всех   вариантов   значений переменных,  входящих  в формулу,  так  как   таких  вариантов  может  быть  бесконечное множество.