Задачи по "Финансам"

1-1. Функция с неотрицательными целыми значениями от неотрицательных целочисленных переменных называется частично рекурсивной функцией, если ее можно получить из трех элементарных функций О(х), S(x), Imn(x1,x2,...,xn)= xm,1≤m≤n, путем конечного числа применений операций суперпозиции, примитивной рекурсии и минимизации.

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

Это следующие функции:

1. нулевая функция О(х)= 0;

2. функция следования s(x)= х+1;

3. функции выбора Imn(x1,x2,...,xn)= xm, 1≤ m≤n

Пусть заданы n функций от m переменных:

g1=g1(x1, … ,xm); g2=g2(x1, … ,xm); .………………… gn=gn(x1, … ,xm);

и пусть определена функция f(z1,…,zn)

F(x1,..,xn)=f(g1(x1, … ,xm), …, gn(x1, … ,xm))

Будем говорить, что F получена операцией суперпозиции.

Пусть процедуры f, g1,...,gn вычисляют одноименные функции. Тогда программа Р вычисляет функцию F.

Р : y1:= g1(x1, x2,...,xm); …………................... yn:= gn(x1, x2,...,xm);
y:= f(y1, y2,...,yn).

Если применить оператор суперпозиции конечное число раз, то будет построено конечное число функциональных термов. Очевидно, что конечным числом применения оператора суперпозиции к вычислимым функциям могут быть построены только вычислимые функции.

Заданы две функции:

g(x1,…,xn-1) – n-1 местная вычислимая функция

h(x1,…,xn+1) – (n+1) местная вычислимая функция

Тогда n-местная функция f строится примитивной рекурсией из функций g и h, если для всех натуральных значений х1, х2, ..., хm, у имеем:

f(х1, х2, ..., хn-1 , 0) = g(х1, х2, ..., хn-1)          

f(х1, х2, ..., хn-1,y+1) = h (х1, х2, ..., хn-1,y, f(х1, х2, ..., хn-1, y)).

схема примитивной рекурсии

Говорят, что f получена из g и h операцией примитивной рекурсией.

Определение: Функция с неотрицательными целыми значениями от неотрицательных целочисленных аргументов называется примитивно-рекурсивной функцией, если ее можно получить из трех элементарных функций О(х), S(x), Imn(x1,x2,...,xn)= xm,1≤m≤n, путем конечного числа применений операций суперпозиции и примитивной рекурсии.

Пусть необходимо вычислить значение функции f при у = k. Тогда из определения (1) схемы примитивной рекурсии имеем последовательность функциональных термов, вычисляющих значение функции f(x1, х2, ... ,xn, k):

to: fo=f(x1, х2, ... ,xn, 0) =g(x1, х2, ... ,xn);

t1: f1=f(x1, х2, ... ,xn, 1) =h(x1, х2, ... ,xn, 0, g(x1, х2, ... , xn));

t2: f2=f(x1, х2, ... ,xn, 2) =h(x1, х2, ... ,xn, 1, f(x1, х2, ... , xn, 1));

… … …

tk: fk=f(x1, х2, ... ,xn, k) =h(x1, х2, ... ,xn, k-1, f(x1, х2, ... , xn, k-1));

Здесь представлен способ вычисления f, следовательно, функция f определена однозначно.

1-2. Теорема. Множество дизъюнктов логики высказываний S невыполнимо тогда и только тогда, когда из S выводим пустой дизъюнкт.

Доказательство. Докажем  достаточность.

Отметим, что правило резолюции сохраняет истинность.

Это означает, что если ϕ(¬X∨F)=1 и ϕ(X∨G)=1 для некоторой интерпретации ϕ, то ϕ(F∨G)=1. Действительно, пусть ϕ(¬X∨F)=1 и ϕ(X∨G)=1. Тогда если ϕ(F)=1, то и ϕ(F∨G)=1. Если же ϕ(F)=0, то ϕ(¬X)=1, поскольку ϕ(¬X∨F)=1. Но в этом случае ϕ(X)=0 и ϕ(G)=1, так как ϕ(X∨G)=1. Если же ϕ(G)=1, то и ϕ(F∨G)=1.