Теорема о полноте ИП

41. Системы одноместных предикатов формульных в арифметике. Определение 1. Одноместным предикатом Р(x) называется произвольная функция переменного x, определенная на множестве M и принимающая значение из множества {1; 0}. Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x). Множество всех элементов , при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x), т.е. множество истинности предиката Р(х)- это множество . Так, например, предикат Р(x) – “x – простое число” определен на множестве N, а множество истинности I_P для него есть множество всех простых чисел.

Р(х) – “х есть простое число”

П(х) – “x=p^a, где р-простое”

Sq(x) – “х есть квадрат нат. числа”

Сub(x) – “х есть куб нат. числа”

Even(x) – “х есть четное число”

Odd (x) – “х есть нечентное число”

Even(x)~ ØOdd (x)

42. Система одноместных операций формульных в арифметике. Предикаты, так же, как высказывания, принимают значения И или Л, поэтому и к предикатам и к высказываниям применимы все операции логики высказываний. Одноместная операция это такая операция, где участвует только одно высказывание или предикат. Л огическое отрицание является одноместной операцией. Таблица истинности одноместной логической операции состоит из двух строк: два различных значения аргумента — «истина» (1) и «ложь» (0) и два соответствующих им значения функции. Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее: Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот. Приведем примеры отрицания: Высказывание «Земля вращается вокруг Солнца» истинно. Высказывание «Земля не вращается вокруг Солнца» ложно.

43. Система двухместных предикатов формульных в арифметике. Определение 1. Двухместным предикатом Р(x,y) называется функция двух переменных x и y, определенная на множестве М=М₁хМ ₂ и принимающая значения из множества {1;0}. В числе примеров двухместных предикатов можно назвать такие предикаты: Q(x, y) – “x=y” - предикат равенства, определенный на множестве RхR=R²;

44. Система двухместных операций формульных в арифметике. Предикаты, так же, как высказывания, принимают значения И или Л, поэтому и к предикатам и к высказываниям применимы все операции логики высказываний. Двухместная операция – операция в которой участвуют два высказывания или предиката. в таблице истинности двуместной логической операции — четыре строки: 4 различных сочетания значений аргументов — 00, 01, 10 и 11 и 4 соответствующих им значения функции. 45.Система двухместных операций формульных в арифметике.

Двуместные операции

z=lcm(x,y) наименьшее общее кратное

z=gcd(x,y) наибольший общий делитель

z=DIV(x,y) частное от деления x на y

z=MOD(x,y) остаток от деления x на y

z=exp(x,y) z=x^y=e^ylnx

p=gcd(x,y) ~ [(x|p&y|p)& A v(v|x&v|y)=>v|p]

x=1 ~ A y [lcm(x,y)=y]

x=1 ~ A y [gcd(x,y)=x]

x=0 ~ A y [gcd(x,y)=y]

45.Определимость констант 0.1.2,… в системах не менее сильных чем следование.

Neib(x,y) ~ [(x=s(y) v y=s(x)]

S^K(x)=y ~ S(S…(x)) /*K раз*/ =y

x=0 ~ -E y(S(y)=x)

x=1 ~ E y (S(y)=x & y=0)

x=2 ~ E y (S(y)=x & y=1)