Вопросы типа 2
Понятие примитивно-рекурсивых функций
Примитивно рекурсивная функция — вычислимая функция нескольких натуральных переменных, частный случай рекурсивной функции.
Определение
Определение понятия примитивно рекурсивной функции является индуктивным. Оно состоит из указания класса исходных примитивно рекурсивных функций и двух операторов (подстановки и примитивной рекурсии), позволяющих строить новые примитивно рекурсивные функции на основе уже имеющихся.
К числу исходных примитивно рекурсивных функций относятся функции следующих трёх видов:
Нулевая функция O одного переменного, сопоставляющая любому натуральному числу значение 0.
Функция следования S одного переменного, сопоставляющая любому натуральному числу xнепосредственно следующее за ним натуральное число x + 1.
Функции
,
где 
,
от n переменных, сопоставляющие
любому упорядоченному наборуx1,...xn натуральных
чисел число xm из
этого набора.
Операторы подстановки и примитивной рекурсии определяются следующим образом:
Пусть f — примитивно рекурсивная функция от m переменных, а g1,... gm — упорядоченный набор примитивно рекурсивных функций от n переменных каждая. Тогда результатом подстановки функций gkв функцию f называется функция h от n переменных, сопоставляющая любому упорядоченному наборуx1,...xn натуральных чисел число
.
Пусть f — примитивно рекурсивная функция от n переменных, а g — примитивно рекурсивная функция от n+2 переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций f и g называется функция h от n+1 переменной вида
;
.
Примеры примитивно-рекурсивых функций
Укажем на ряд широко известных арифметических функций, допускающих рассмотрение в качестве примитивно рекурсивных.
Сложение двух натуральных чисел может быть рассмотрено в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям
и
f, вторая из которых получается
подстановкой основной функции 
в
основную функцию S:
+ (x,0) = x;
+ (x,y + 1) = f(x,y, + (x,y));
.
Умножение двух натуральных чисел может быть рассмотрено в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям O и f, вторая из которых получается подстановкой основных функций
и
в
функцию сложения:
;
;
.
Симметрическая разность (абсолютная величина разности) двух натуральных чисел может быть рассмотрена в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения следующих подстановок и примитивных рекурсий:
− (x,y) = + ( − 1(x,y), − 2(x,y));
;
;
;
Примеры примитивно-рекурсивых операторов
О
ператор
условного перехода:
F(x1,x2,…,xn)= g1(x1,…,xn), если P(x1…xn) – истинно g2(x1,…,xn), если P(x1…xn) - ложно
Оператор суммирования ∑
Y(x11,…,xn1,z)=∑y<zf(x1,x2,…,xn)
G(x1,x2,…,xn,0)=0 G(x1,x2,…,xn,y+1)= G(x1,x2,…,xn,z)+ F(x1,x2,…,xn,z)
13) Понятие и построение СДНФ
СДНФ - это такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одном и том же порядке.
Для построения СДНФ из таблицы истинности выбираются функции f=1. Для каждого единичного набора записывается элементарная конъюнкция, в которую переменная входит без инверсий, если в наборе она равна 1, иначе с инверсией.
14) Понятие и построение СКНФ
СКНФ – это такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одном и том же порядке.
Для построения СДНФ из таблицы истинности выбираются функции f=0. Для каждого нулевого набора записывается элементарная дизъюнкция, в которую переменная входит без инверсий, если в наборе она равна 0, иначе с инверсией.
15) Эквивалентные преобразования логических формул. Основные законы
Ассоциативность
X & Y & Z=X&(Y&Z)=(X&Y)&Z
X или Y или Z=X или (Y или Z)
Коммутативность
X&Y=Y&X
X или Y=Y или X
Дистрибутивность
X&(Y или Z)=X&Y или X&Z
(Y или Z)&X=Y&X или Z&X
X или (Y&Z)=(X или Y)&(X или Z)
Идемпотентность
X&X=X
X или X=X
Закон де-Моргана
Не(X&Y)=неX или не
Не(X или Y)=неX&неY
Двойное отрицание
Не(неX)=X
Законы универсальных множеств
X&1=X
X или 1=1
Законы нулевого множества
X&0=0
X или 0=X
Не 0=1 не 1=0
Закон противоречия
(Не X)&X=0
Закон исключенного третьего
(Не X) или X=1
16) Правило склеивания
Дизъюнкцию 2х соседних конъюнкций можно заменить одной элементарной конъюнкцией, являющейся общей частью исходных конъюнкций.
X&Y&Z или Y&Z=Y&Z
Конъюнкцию 2х соседних дизъюнкций можно заменить одной элементарной дизъюнкцией, являющейся общей частью исходных дизъюнкций.
(X или Y или Z)&((не X) или Y или Z)=Y или Z
Правило поглощения
Дизъюнкцию 2х элементарных конъюнкций, одна из которых является частью другой, можно заменить одной элементарной конъюнкцией, имеющей меньшее ко-во операндов.
X&Y&Z или X&Y=X&Y&Z или X&Y&1=X&Y
Конъюнкцию 2х элементарных дизъюнкций, одна из которых является частью другой, можно заменить одной элементарной дизъюнкцией, имеющей меньшее ко-во операндов.
(X или Yили Z)&(X или Y)=X или X&Y или Y&X или Y или X&Z или Z&Y=
=X или Y
Правило развертывания
Это правило противоположно правилу склеивания и позволяет получить из элементарной конъюнкции дизъюнкцию элементарных конъюнкций большего ранга.
В исходной конъюнкции ранга r вводятся в качестве сомножителей R-r единиц.
Каждая единица заменяется дизъюнкцией некоторой переменной , которой нет в конъюнкции, и ее инверсией.
Выполняется раскрытие всех скобок
Если R=n, то получаем СДНФ. Каждое слагаемое будет представлять свою конъюнкцию.