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

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

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

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

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

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

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

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

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

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

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

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

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

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

·