Шаг 4.
Основы логического программирования.
Формулы логики предикатов первого порядка

    На этом шаге мы рассмотрим формулы логики предикатов первого порядка.

    Формулы логики предикатов первого порядка рекурсивно определяются следующим образом:

  1. атом есть формула;
  2. если A и B - формулы, то ~A, AÙB, AÚB, A® B, A«B - тоже формулы;
  3. если A(x) - есть формула, а x - свободная переменная в A(x) , то ("x)A(x) и ($x)A(x) - тоже формулы;
  4. других формул, кроме составленных с помощью правил (1) - (3), нет.

    Язык изучают с помощью языка исследователя - метаязыка. В нем могут использоваться различные знаки, не входящие в алфавит изучаемого языка - метасимволы. Мы будем использовать различные метасимволы, в том числе A, B, C, ..., E, A1, A2, A3, ... (большие буквы латинского алфавита с индексами или без них) - для обозначения произвольных формул, x,y,z - для обозначения произвольных предметных переменных, t, t0, t1,. .. - произвольных термов и так далее.

    Для упрощения записи формул в метаязыке используют те или иные соглашения. Будем считать, что можно опустить все те скобки, которые будут восстановлены при выполнении следующей процедуры: запись просматриваем слева направо и вокруг каждого очередного вхождения знака Ù расставляем пару скобок так, чтобы подслово, в котором эти скобки служат началом и концом соответственно, являлось формулой, причем возможно более длинной; затем ту же операцию повторяем для связок Ú, ® (именно в этом порядке!).

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

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

  1. каждой константе ставится в соответствие некоторый элемент из области значений переменных D;
  2. каждому n-местному функциональному символу ставится в соответствие отображение элемента из Dn в D, где Dn ={(x1, x2, ..., xn) | x1Î D, ..., xnÎD};
  3. каждому n-местному предикатному символу ставится в соответствие отображение элемента из Dn в {И,Л}.

    Когда мы определяем истинностное значение формулы на области D, то "x и $x интерпретируются как "для всех элементов x из Dn" и "существует элемент x из Dn" соответственно.

    Формула, интерпретируемая на области D, принимает значение И или Л согласно следующим правилам:

  1. если заданы значения формул A и B, то истинностные значения формул ~A, AÙB, AÚB, A®B, A«B получают по таблице истинности, которая справедлива так же и для логики предикатов первого порядка;
  2. формула ("x)A(x) получает значение "истина", если A(x) - "истина" для каждого x из D; в противном случае (("x)A(x)) получает значение Л;
  3. формула ($x)A(x) получает значение И, если A(x) - И хотя бы для одного x из D; в противном случае (($x)A(x)) получает значение Л.

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

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

    В логике предикатов первого порядка формула является:

    Формула A есть логическое следствие формул B1, B2, ..., Bn тогда и только тогда, когда для любой интерпретации, если B1ÙB2Ù ...Ù Bn истинна при этой интерпретации, то A так же истинна.

    На следующем шаге мы рассмотрим предваренную нормальную форму формулы.




Предыдущий шаг Содержание Следующий шаг