Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Рассмотрим некоторую пропозициональную формулу. Если в пропозицио­ нальную формулу вместо пропозициональных букв подставить формулы логи­ ки предикатов (вместо всех вхождений одной и той же пропозициональной бу­ квы подставлять одну и ту же формулу), получим некоторую формулу, которая называется частным случаем пропозициональной формулы. Тогда легко дока­ зать следующее утверждение. Всякий частный случай любой тавтологии истинен в каждой интерпретации. § 5. Логически общезначимые формулы. Выполнимые и равносильные формулы Формула логики предикатов называется логмчес/<-м общезначимой, если она истинна в любой интерпретации. Примером логически общезначимых формул, очевидно, являются сле­ дующие формулы: УХА^ЗХА, А=А. Если формула А является логически общезначимой, то иногда будем запи­ сывать в сокращенном виде: « ^ АУ> И эта запись читается: «А является логиче­ ски общезначимой формулой (логики предикатов)». Формула логики предикатов А называется выполнимой, если существует интерпретация, в которой выполнима Л. Примером выполнимой формулы является формула VxA(x,y,bi), ибо для нее в предыдущем параграфе была построена интерпретация, в которой она вы­ полнима. Очевидно, что формула А выполнима тогда и только тогда, когда формула —А не является логически общезначимой. Будем называть формулу логики предикатов А противоречием, если формула А ложна во всякой интерпретации. Говорят, что формула А логически влечет формулу В, если в любой ин­ терпретации формула В принимает значение И при каждой совокупности зна­ чений свободных переменных (входящих в А и В), при которых формула А приняла значение И. Иначе говорят, что В является логическим следствием формулы/!. В этом случае записываем А 1=5 и читаем: «из А логически следует В» или «В является логическим следст­ вием из АУ>. Отметим, что «А |= В» не является формулой, а является метаут- верждением относительно формулЛ и в (логики предикатов). ФормулыЛ и в логики предикатов называют равносильными {логически эквивалентными), если каждая из них логически влечет другую. Если формулыЛ и в равносильны, то, как и в логике высказываний, запи­ сываем: А ~В. Имеют место следующие теоремы. 39