Вопросы 1 типа

1 Функция следования

Функция следования (λ – оператор сдвига) – унарная функция, для которой: “Значением принять натуральное число, следующее за числом, являющимся значением аргумента x”.

Примеры:

; .

Замечание: базисные функции имеют значения только для заданных значений их аргументов.

2 Функции тождества в базисе примитивной рекурсии

Функция тождества (x1, x2,…,xm,…,xn)= xm ( - оператор проектирования) – n-арная функция, алгоритм вычисления которой: “Значением функции принять значение m-го аргумента.” (m, n>0, m n).

Примеры:

(7,6,1,4)= 6, (6)= 6, (7,15)= 15.

3 Перечислите объекты базиса примитивной рекурсии

Константы

f(x)=0; f(x)=1;…

Тождества

(x1, x2, …, xm,…, xn)=xm

4 Оператор суперпозиции (подстановки)

Оператором суперпозиции(подстановки) Sⁿ_m называется операция подстановки в функцию от m переменных m функций от n переменных. (одних и тех же). ,а сопутствующий алгоритм которого: «Значения m –арных функций принять за значения аргументов n–арной функции и вычислить её значение». В этом случае говорят, что m –арная функция получена в результате операции суперпозиции Sⁿ⁺¹ из функций .

Пример.

Функция f(x₁,…, x_n) возникает из функций h(x₁,…, x_m), g₁(x₁,…, x_n), …g_m(x₁,…, x_n) суперпозицией, если f(x₁,…, x_n)= Sⁿ_m(h, g₁,…, g_m) = h(g₁(x₁,…, x_n), …, g_m (x₁,…, x_n)).

Если заданы функции Jⁿ_m и операторы Sⁿ_m, то можно считать заданными всевозможные операторы подстановки функции в функцию, а также переименования, перестановки и отождествления переменных.

Так, если f(x₁, x₂)= h(g₁(x₁, x₂), g₂(x₁)), то ее стандартный вид следующий: f(x₁, x₂)= S²₂(h(x₁, x₂), g₁ (x₁, x₂), S¹₂ (J²₁(x₁, x₂), g₂(x₁), g₃(x₁))), где g₃ – любая функция от х₁. Если же имеем f(x₂, x₁, х₃, …, x_n) и f(x₁, x_1, x₃,…, x_n), то пишем:f(x₂, x₁, х₃, …, x_n) = f(J²₂(x₁, x₂), J²₁(x₁, x₂), х₃, …, x_n),

f(x₁, x_1, x₃,…, x_n)= f(J²₁(x₁, x₂), J²₁(x₁, x₂), х₃, …, x_n).

Пример:

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

Оператором примитивной рекурсии R_n[f₁^n-1,f₂ⁿ⁺¹,x₁(n)]=f_mⁿ называется процесс определения функции f (n+1) переменных через n-местную функцию g и (n+2)- местную функцию h в следующем виде:

f(x₁, x_2, …, x_n, 0)= g(x₁, x₂,…, x_n)

f(x₁, x_2, …, x_n, y+1)=h(x₁, x₂,…, x_n, y, f(x₁, x_2, …, x_n, y)),

где g и h – две различные функции соответственно n и n+2 аргументов.

Эта пара равенств называется схемой примитивной рекурсии. Тот факт, что функция f определена схемой примитивной рекурсии выражается равенством f(x₁, x_2, …, x_n, y)=R_n(g, h). В случае, когда n=0, то есть определяемая функция f является одноместной, схема примитивной рекурсии принимает более простой вид:

f(0)=с, f(у+1)=h(y, f(y)), где с – константа.

Схема примитивной рекурсии определяет f рекурсивно не только через другие функции g и h, но и через значения f в предшествующих точках: значение функции f в точке у+1 зависит от значения функции f в точке у. Очевидно, что для вычисления f(x₁,…, x_n, k) понадобиться k+1 вычислений по схеме примитивной рекурсии – для у=0, k.

Замечания:

Существенным в операторе примитивной рекурсии R_n является то, что независимо от числа переменных в f рекурсия ведется только по одной переменной у (остальные n переменных x₁, x_2, …, x_n на момент применения схемы примитивной рекурсии зафиксированы и играют роль параметров).

6 Перечислите действия в определении примитивной рекурсии

Хз

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

Смотрим пункт 5

8 Оператор минимизации функции по переменной

Оператор минимизации (- оператор).

Оператором минимизации  (наименьшего числа оператора) называется преобразование (n+1)-местной функции (в общем случае частичной)  в n-местную f, такую, что для любых х₁, х₂, …х_n, у равенство f(х₁, х₂, …х_n)=у имеет место лишь в том случае, если определены и не равны нулю значения ( х₁, …, х_n, 0), …, ( х₁, …, х_n, у-1) и при этом ( х₁, х₂, …х_n, у)=0. Применение оператора минимизации обозначают [, (y)], где у - исчезающий аргумент.

Говорят, что n-местная арифметическая функция f: NⁿN получается из функции : Nⁿ⁺¹N с помощью -оператора, если выполнено условие: для любых k₁, k₂,…, k_n, kN. f(k₁, k₂,…, k_n)=k, тогда и только тогда, когда для всех l<k значения ( k₁, k₂,…, k_n, l) определены и отличны от нуля, а значение ( k₁, k₂,…, k_n, k) определено и равно нулю.

Если f получается из функции  с помощью оператора наименьшего числа , то пишут: f(x₁, x₂,…, x_n)=y[(x₁,…, x_n, y)=0].

Важным свойством -оператора является то, что с его помощью из вычислимой функции всегда получается частичная вычислимая функция f. Именно, если имеется алгоритм для вычисления , то значение f(x₁, x₂,…, x_n) может вычисляться следующим образом: вычисляется (x₁, x₂,…, x_n, 0); если процесс вычисления закончился, то есть значение (x₁, x₂,…, x_n, 0) определено, и (x₁, x₂,…, x_n, 0)=0, то полагаем f(x₁, x₂,…, x_n)=0, а если (x₁, x₂,…, x_n, 0)0, то начинают вычислять (x₁, x₂,…, x_n, 1). Если процесс вычисления закончился и (x₁, x₂,…, x_n, 1)=0, то полагают f(x₁, x₂,…, x_n)=1, а если (x₁, x₂,…, x_n, 1)0, то переходят к вычислению (x₁, x₂,…, x_n, 2) и так далее.

Процесс вычисления закончится, если найдется такое у, что для всех z < y значение (x₁, x₂,…, x_n, z) определено и отлично от нуля, а (x₁, x₂,…, x_n, у) определено и равно нулю. Тогда f(x₁, x₂,…, x_n) = у.

Пример:

f(x)=y[12*y-x=0]. Тогда f(x)=x/2 при всех четных значениях хN.

Замечание:

Примитивно-рекурсивные функции всегда определены (имеют значения) для любых значений аргументов. Иначе обстоит дело с функциями, полученными при помощи -оператора. Для некоторых комбинаций значений аргументов они могут быть не определены, потому что исходная функция не принимает нулевых значений.

Пример:

det f(x)=[J²₁(x, y), (y)].

Полученная функция f(х) обладает следующими свойствами:

f(0)=0, f(k) не существует при k0. Последнее означает, что для заданной функции J²₁(x, y) -оператор не может построить f(k) kN, так как при x=k функция (x, y)= J²₁(x, y) ни для какого значения у не будет равной нулю.

9 Частично-рекурсивная функция и Общерекурсивная функция

Функция называется частично-рекурсивной, если она может быть получена из простейших функций с помощью конечного числа операторов суперпозиции, примитивной рекурсии и минимизации. Указанные операции могут быть выполнены в любой последовательности и любое конечное число раз. Если такие функции оказываются всюду определенными, то они называются общерекурсивными функциями.

11 Смежные слова в ассоциативном исчислении

Ассоциативным исчислением называют совокупность всех слов алфавита с системой допустимых подстановок. Задается алфавитом и системой подстановки.

Два слова P1 и P2 называются смежными в ассоциативном исчислении, если одно из них может быть преобразовано в другое путем подстановок.

12 Дедуктивная цепочка в ассоциативном исчислении

Последовательность слов P1, P2,…, M называется дедуктивной цепочкой от слова P к слову M, если каждое из 2-х рядом стоящих слов смежное с соседним.

13 Эквивалентные слова в ассоциативном исчислении

Слова P и M называются эквивалентными, если существует дедуктивная цепочка от P к M и обратно.

14 Суперпозиция нормальных алгоритмов

Хз

15 Объединение нормальных алгоритмов

См пункт 14

18 Логика

Это наука, изучающая методы установления истинности или ложности одних высказываний на основе истинности или ложности других высказываний.

Математическая логика – это современная форма логики, использующая формальные математические методы.

19 Цель математической логики

Свести логические заключения к формальным действиям над символами, не затрагивая содержание утверждения (высказывания)

20 Высказывание

Это предположение, относительно которого можно сказать истинно оно или ложно в настоящее время

21 Перечислите основные логические связки (операции)

• Конъюнкция И

• Дизъюнкция ИЛИ

• Инверсия НЕ

• Импликация ЕСЛИ – ТО

• Неравнозначность ЛИБО – ЛИБО

• Эквивалентность

22 Таблица истинности дизъюнкции

A	B	A или B
0	0	0
0	1	1
1	0	1
1	1	1

23 Таблица истинности конъюнкции

A	B	A и B
0	0	0
0	1	0
1	0	0
1	1	1

24 Таблица истинности импликации

Ложно, если первое 1, а второе 0

A	B	A -> B
0	0	1
0	1	1
1	0	0
1	1	1

25 Таблица истинности эквивалентности

Если одинаковые, то истинно

A	B	A <-> B
0	0	1
0	1	0
1	0	0
1	1	1

26 Таблица истинности неравнозначности

Если есть одна 1, то истинно

A	B	A B
0	0	0
0	1	1
1	0	1
1	1	0

27 Порядок выполнения логических операций

Круглые скобки

При отсутствии:

• Отрицание

• &

• Дизъюнкция

• Все остальное слева направо

28 Понятие алгебры

Алгебра логики – наука, рассматривающая логические формулы как алгебраические выражения, которые можно преобразовать по определенным правилам.

29 Носитель алгебры

Множество M с заданной совокупностью операций называют системой алгебры.

O = {M, f1, f2, …, fm}

тут M – носитель алгебры, а O – сигнатура алгебры.

30 Тип алгебры

Хз

31 Сигнатура алгебры

См пункт 29

32 Подалгебра

Подалгебра — подмножество алгебры над кольцом (алгебраической системы), замкнутое относительно всех операций этой алгебры, и само являющееся алгеброй. Другими словами, если результат бинарной операции над множеством А, не выходит за пределы этого множества.

33 Ассоциативная бинарная операция

Ассоциативная операция — это бинарная операция  , обладающая ассоциативностью  (лат associatio — соединение), или сочетательностью:

 для любых элементов  .

Для ассоциативной операции результат вычисления   не зависит от порядка вычисления (расстановки скобок), и потому позволяется опускать скобки в записи. Для неассоциативной операции выражение   при   в общем случае не определено.

34 Коммутативная бинарная операция

Коммутативная операция — это бинарная операция  , обладающая коммутативностью (от позднелат commutativus — «меняющийся»), то есть переместительностью

 для любых элементов  .

В частности, если групповая операция является коммутативной, группа называется абелевой. Если операция умножения является коммутативной, то кольцо называется коммутативным.

35 Бинарная операция, дистрибутивная слева и справа

свойство согласованности двух бинарных операций, определённых на одном и том же множестве.

Говорят, что две бинарные операции + и × удовлетворяют свойству дистрибутивности, если для любых трех элементов  :

 — дистрибутивность слева;

 — дистрибутивность справа.

Если операция × является коммутативной то свойства дистрибутивности слева и справа совпадают.

36 Логическая переменная

Переменная, принимающая значения 0 или 1, т.е истина или ложь

37 Логическая функция

Это функция вида f(x1, x2, … , xn ), которая принимает логические значения, заданные логическими переменными.

38 Булева алгебра

Алгебра А вида

А = {B, f1, f2,…,fn} называется булевой, если B={0,1}, а f – это логические функции.

39 Фиктивная переменная в логической функции

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

-Если фактически функция не зависит от некоторой переменной, то такую переменную называют фиктивной.

40 Логические функции одной переменной

		Значения переменной   х	0	1
	Название функции	Обозначение функции	Значения  функции
f1	Тождественный нуль	0	0	0
f2	Тождественная	х	0	1
f3	Отрицание		1	0
f4	Тождественная единица	1	1	1

41 Формула

Совокупность переменных и применимых к ним операций (?)

42 Глубина формулы

Не знаю как объяснить

43 Эквивалентные формулы

44 Способы доказательства равносильности формул

45 Формула разложения функции от n переменных по m переменным

46 Совершенная дизъюнктивная нормальная форма

47 Алгоритм построения СДНФ

48 Совершенная конъюнктивная нормальная форма

49 Алгоритм построения СКНФ

50 Ассоциативность логических операций

51 Коммутативность логических операций

52 Дистрибутивность логических операций

53 Законы идемпотентности (тавтологии)

54 Законы универсального и нулевого множества

55 Правила (законы) де Моргана

56 Закон дополнительности

57 Элементарная дизъюнкция

58 Элементарная конъюнкция

59 Ранг элементарной дизъюнкции (конъюнкции)

60 Конституента нуля

61 Конституента единицы

62 Соседние элементарные дизъюнкции (конъюнкции)

63 Правило склеивания

64 Правило поглощения

65 Правило развертывания

66 Полная система в алгебре логики

67 Минимальный базис

68 Перечислите примеры полных систем