25. Теорема дедукции. Предикаты, кванторы.

ДЕДУКЦИИ ТЕОРЕМА

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

Теорема дедукции-одно из важнейших содержательных утверждений математической логики,определяющее связь между логически правильными (аподиктическими) рассуждениями (илиумозаключениями, или выводами) и законами (доказуемыми формулами) логики, лежащими в их основе.Прообраз Т. о д. было известно в виде общего принципа связи между выводимостью и импликацией. Т. о д. была сформулирована независимо франц. математиком Ж. Эрбраном (1928) и А. Тарским (1930) и доказана Эрбраном (1930) для исчислений, включающих положительное импликативное исчисление высказываний Гильберта. Формулировки Т. о д. зависят,, от того как в том или ином исчислении определяются понятия "выводимость" и "импликация";поэтому всегда следует иметь в виду тот или иной в а р и а н т Т. о д.

Предика́т (n-местный, или n-арный) — это функция с множеством значений (или {ложь, истина}), определённая на множестве . Таким образом, каждый набор элементов множества M характеризуется либо как «истинный», либо как «ложный». Предикат называют тождественно-истинным и пишут:

если на любом наборе аргументов он принимает значение 1.

Предикат называют тождественно-ложным и пишут:

если на любом наборе аргументов он принимает значение 0.

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

Так как предикаты принимают только два значения, то к ним применимы все операции булевой алгебры, например: отрицание, импликация, конъюнкция, дизъюнкцияи т. д.

Ква́нтор — общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих высказывание. Чаще всего упоминают:

• Квантор всеобщности (обозначение: , читается: «для любого…», «для каждого…», «для всех…» или «каждый…», «любой…», «все…»).

• Квантор существования (обозначение: , читается: «существует…» или «найдётся…»).

• Правило отрицания кванторов — применяется для построения отрицаний высказываний, содержащих кванторы, и имеет вид:

• 

26. Формулы логики предикатов, их равносильность, выполнимость и общезначимость.

Классификация формул логики предикатов. Сформулируем классификационные определения для формул логики предикатов. Рассмотрим некоторую интерпретацию с множеством М.

Определение. Формула А выполнима в интерпретации, если существует набор <a₁, …, a_n>, a_iÎ M, значений свободных переменных x_i1, …, x_inформулы А такой, что А|<a₁, …, a_n>=И.

Определение. Формула А истинна в данной интерпретации, если она принимает значение И на любом наборе <a₁, …, a_n>, a_iÎ M, значений своих свободных переменных x_i1, …, x_in.

Определение. Формула А выполнима (в логике предикатов), если существует интерпретация, в которой А выполнима.

Определение. Формула А, истинная при любой интерпретации, называется общезначимой или тождественно-истинной (в логике предикатов).

Теорема Черча. Не существует алгоритма, который для любой формулы логики предикатов устанавливает, общезначима она или нет.

Определение. Формулы А и В равносильны в данной интерпретации, если на любом наборе значений свободных переменных они принимают одинаковые значения (т. е. если формулы выражают в данной интерпретации один и тот же предикат).

Определение. Формулы А и В равносильны на множестве М, если они равносильны во всех интерпретациях, заданных на множестве М..

Определение. Формулы А и В равносильны в логике предикатов, если они равносильны на всех множествах (АºВ).

Укажем несколько правил перехода от одних формул к другим, им равносильным.

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

Утверждение. Всякую формулу логики предикатов, содержащую символы ® и », можно преобразовать в равносильную ей формулу, не содержащую этих символов.