13. Алгебра предикатов, основные понятия и определения, логические операции.

Множество предметных переменных Т₁= {x, y, z,..} и постоянных Т₂= {a, b, c,..}, функциональных символов Т₃={f ⁱ₁ ; f ^j₂ ; f ^k₃ ;..} и предикатных Т₄=(P ⁱ₁ ; P ^j₂ ; P ^k₃ ;..} с заданными над T={T₁; T₂; T₃; T₄} логическими операциями F={; ; ; ; ; ; } формируют алгебру предикатов.

Любую предметную переменную и предметную постоянную называют терм и обозначают символом t_i.

Если f ⁿ_i есть n - местный функциональный символ и t₁, t₂, t_n - термы, то f ⁿ_i ( t₁; t₂; t_n ) также есть терм, где n –число аргументов функции, i – числовой индекс функции.

Никаких иных термов нет.

Если P ⁿ_i – n-местный предикатный символ и t₁; t₂; t_n - термы, то F= Pⁿ_i (t₁; t₂; t_n ) - элементарная формула или атом.

Предметные переменные, входящие в термы атома, являются свободными.

Если F формула, a x - предметная переменная, входящая в атомы формулы F, то _x(F) и _x(F) также формулы. В этих формулах предметная переменная x среди множества термов формулы F является связанной.

Никаких иных формул нет.

Отрицание (F(t₁; t₂; t_n)) есть одноместная операция, посредством которой из данной формулы F(t₁; t₂; t_n) полу­чают ее отрицание.

Конъюнкция (F₁(t₁₁; t₁₂; ..t_1n)F₂(t₂₁; t₂₂;..t_2n)) есть двуместная операция, посредством которой из двух формул F₁ и F₂ получают новую формулу F (t₁₁; t₁₂; t_1n; t₂₁; t₂₂; t_2n ) с числом предметных переменных и постоянных, равным их объединению у исходных формул. Значение формулы истинно тогда и только тогда, когда истинны обе форму­лы F₁ и F₂.

Дизъюнкция (F₁(t₁₁; t₁₂; ..t_1n)F₂(t₂₁; t₂₂; ..t_2n)) есть двуместная опе­рация, посредством которой из двух формул F₁ и F₂ получают новую формулу F (t₁₁; t₁₂; t_1n; t₂₁; t₂₂; t_2n ) с числом предметных переменных и постоянных, равным их объединению у исходных формул. Значение формулы истинно тогда и только тогда, когда истинна хотя 6ы одна из формул F₁ или F₂.

Импликация (F₁(t₁₁; t₁₂;..t_1n)F₂(t₂₁; t₂₂;..t_2n)) есть двухместная операция, посредством которой из двух формул F₁и F₂ получают новую формулу F(t₁₁; t₁₂;..t_1n; t₂₁; t₂₂;..t_2n ) с числом предметных переменных и постоянных, равным их объедине­нию у исходных формул. Значение формулы ложно тогда и только тогда, когда F₁ истинно, а F₂ - ложно.

Эквиваленция (F₁(t₁₁;t₁₂;..t_1n)F₂(t₂₁; t₂₂;..t_2n)) есть двумест­ная операция, посредством которой из двух формул F₁ и F₂ получают новую формулу F (t₁₁; t₁₂; t_1n; t₂₁; t₂₂; t_2n ) c числом предметных переменных и постоянных, равным их объединению у исходных формул. Значение формулы истинно тогда и только тогда, когда обе формулы F₁ и F₂ имеют одно и то же значение истины или лжи.

14. Законы алгебры предикатов.

Формулы называют равносильными, если при любых подстановках предметных постоянных они принимают одинаковое значение. Если две формулы F₁ и F₂ равносильны, т.е F₁=F₂, то они эквивалентны.

Если формула алгебры предикатов F имеет вхождением подфор­мулу F_i , т.е. F( t₁; t₂;; F_i;  ), для которой существует экви -валентная ей подформула F_j т.е. F_i = F_j, то возможна подстановка всюду в формулу F вместо формулы F_i подформулу F_j без нарушения истинности формулы.

Наименование закона и правила	Равносильные формулы Fi=Fj
коммутативности	xy(F2(x; y))=yx(F2(x; y))*); xy(F2(x; y))=yx(F2(x; y))*). *) только для одноименным кванторов.
дистрибутивности	x(F1(x))x(F2(x))=x(F1(x)F2(x))*); x(F1(x))x(F2(x))=x(F1(x)F2(x))**); *)для логической связки “” формул только с кванторами  по одной переменной x. **)для логической связки “” формул только с кванторами  по одной переменной x.
идемпотентности {;}	x(F(x)) x(F(x))= x(F(x)); x(F(x))x(F(x))= x(F(x))
исключенного третьего	x(F(x))x(F(x))=и, где {;}
противоречия	x(F(x))x(F(x))=л, где {;}
де Моргана	x(F(x))=x(F(x)); x(F(x))=x(F(x))
дополнения	 (x(F(x)))= x(F(x)), где {;}
свойства констант	x(F(x)) и=и; x(F(x))л=x(F(x)); x(F(x))л=л; x(F(x))и=x(F(x)), где {;}.