Материал: Shporochki_MLITA

16. Замкнутость множества относительно операции: определение, примеры.

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

– все булевы функции, обладающие свойством k-класс замкнутости булевых функций относительно свойства , если любая композиция функций из k лежит в k.

?Пример: если сохраняет 0 и -новые переменные, то очевидно что также сохраняет ноль. Это означает, что класс T₀ замкнут относительно операции переименования переменных. Пусть сохраняет 0. Тогда Это означает, что T₀ замкнут относительно операции подстановки. Следовательно, замкнутый класс.

16. Класс замкнутости T₀: определение. Примеры функций, принадлежащих и не принадлежащих классу T₀ . Критерий принадлежности классу T₀ в терминах полинома Жегалкина.

Функцию называют сохраняющей ноль, если Через T₀ обозначим класс всех функций, сохраняющих 0, т.е.

Пример: принадлежит Критерий принадлежности классу T₀ в терминах полинома Жегалкина: коэффициент при свободном члене равен нулю.

16. Класс замкнутости T₁: определение. Примеры функций, принадлежащих и не принадлежащих классу T₁ . Критерий принадлежности классу T₁ в терминах полинома Жегалкина.

Функцию называют сохраняющей единицу, если Через T₁ обозначим класс всех функций, сохраняющих 1, т.е.

Пример: принадлежит Критерий принадлежности классу T₁ в терминах полинома Жегалкина: полином Жегалкина имеет нечетное число слагаемых.

16. Класс замкнутости L: определение. Примеры функций, принадлежащих и не принадлежащих классу L.

Функцию называют линейной, если она представима в виде линейного полинома Жегалкина, т.е. если существуют такие, что .

Пример: принадлежит Не принадлежит

16. Класс замкнутости S: определение. Примеры функций, принадлежащих и не принадлежащих классу S. Критерий принадлежности классу S в терминах ТИ.

Булеву функцию называют самодвойственной, если выполняется равенство . Другими словами, функция самодвойственна, если она совпадает со своей двойственной. Критерий принадлежности классу S в терминах ТИ: При лексикографическом упорядочивании строк таблицы значений самодвойтвенной функции последний столбец (значения функции) антисимметричен относительно середины таблицы. Пример: не принадлежит . Принадлежит .

16. Понятие сравнимых наборов аргументов для булевой функции. Приведите примеры пары сравнимых и несравнимых наборов аргументов. Является ли соответствующий порядок частичным, линейным, полным? Ответ обоснуйте.

; ;

Определение: Будем говорить, что набор не превосходит набор . Наборы называются сравнимыми, если ; в противном случае они называются несравнимыми. Примеры: сравнимые (0,1,0,0) и (1,1,0,1); не сравнимы (0,1,0,0) и (1,0,0,1).

Частичный порядок: рефлексивно антисимметрично ; транзитивно Линейный порядок – частичный порядок с доп. условием, хоть одно из для любых , равно единице.

16. Класс замкнутости M: определение. Примеры функций, принадлежащих и не принадлежащих классу M. Какую информацию о принадлежности классу M можно получить, анализируя принадлежность функции классам

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

Пример: не монотонна . Монотонна Рассматривая классы , мы определяем крайние значения функции, тем самым в некоторых случаях можно сразу определить монотонность.

16. Полная система булевых функций: определение. Приведите примеры полной и неполной систем, состоящих их трех функций каждая. Ответ обоснуйте.

Класс булевых функций K является полным тогда и только тогда, когда он не содержится ни в одном из основных замкнутых классов.

Примеры: полная система: Неполная система:

16. Критерий полноты системы булевых функций. Каково минимально возможное количество функций в полной системе? Приведите пример, обоснуйте.

Необходимый и достаточный критерий полноты класса булевых функций, это и есть теорема Поста: Класс булевых функций K является полным тогда и только тогда, когда он не содержится ни в одном из основных замкнутых классов.

Минимально возможное количество функций в полной системе:1. X nor Y и X nand Y – полные системы.

16. Теорема Поста. Может ли полная система содержать более трех функций, так, чтобы ни одну из них нельзя было исключить? Приведите пример или докажите, что это невозможно.

Теорема Поста: Класс булевых функций K является полным тогда и только тогда, когда он не содержится ни в одном из основных замкнутых классов.

Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре. Во всяком базисе F содержится не более 4-х функций. Пример: .

31) Шифр Вернама. Определение, криптоустойчивость. Примеры шифровки и дешифровки при помощи шифра Вернама.

Шифра Вернама – система симметричного шифрования, изобретенная в 1917 году. Обладает абсолютной криптографической стойкостью, т. е. противостоит криптоанализу.

Сообщение – a

k – ключ, такой же длины, как и сообщение.

Шифровка: сообщение объединяется с операцией исключающее ИЛИ с секретным ключом.

Дешифровка: зашифрованное сообщение объединяется с операцией исключающее ИЛИ с секретным ключом.

Пример: шифровка: (11000) (11101) = (00101)

дешифровка: (00101) (11101) = (11000)

32) Разложение Шеннона: определение, примеры. Связь с бинарными диаграммами решений.

Разложение Шеннона – метод представления булевой функции от n переменных в виде суммы двух подфункций от (n-1) остальных переменных.

,

Пример: f(x,y,z)=x+y+z=x(1+y+z) + (0+y+z)

34) Определение предиката. Связанная и свободная переменная. Приведите примеры формул в логике предикатов, иллюстрирующие фактическое изменение количества переменных при навешивании кванторов.

Предикат – функция, определенная на некотором множестве параметров и со значениями в {0,1}.

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

x – связанная переменная, y – свободная.

Пример: F(x) – х переменная, x – константа.(хз правильный ли пример)

35) Тождества логики предикатов для формул, содержащие связанные переменные: отрицание и замена переменной.

36) Тождества логики предикатов для формул, содержащие связанные переменные: вынесение квантора всеобщности из конъюнкции и дизъюнкции.

37) Тождества логики предикатов для формул, содержащие связанные переменные: вынесение квантора существования из конъюнкции и дизъюнкции.

38) Тождества логики предикатов для формул, содержащие связанные переменные: перестановка связанных переменных.

39) Предваренная нормальная форма: определение. Примеры формул, находящихся и не находящихся в ПНФ. Приведите пример формулы, для которой ПНФ и СНФ имеют разное количество связанных переменных. Обосновать.

Формула имеет ПНФ, если все кванторы вынесены в начало.

Пример:

Пример: ПНФ - , СНФ - У ПНФ 2 связанные переменные, у СНФ одна.

40) Сколемовская нормальная форма: определение. Примеры формул, находящихся и не находящихся в СНФ. Приведите пример формулы, для которой ПНФ и СНФ имеют одинаковое количество связанных переменных. Обосновать.

Формула имеет СНФ, если она в ПНФ, матрица в КНФ и нет кванторов существования.

Пример:

Пример: ПНФ - , СНФ -

41) Унификация и НОУ – определения. Приведите пример пары формул, требующих унификации, укажите их НОУ (не менее трех подстановок)

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

. Множество называют унифицируемым, если существует унификатор этого множества.

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

Пример: P(x,y,k(c)) P(f(a),g(b),z)

НОУ = {x=f(a),y=g(b),z=k(c)}

42-44. МТ - определение. Стандартная МТ.

Машина Тьюринга — это строгое математическое построение, математический аппарат, созданный для решения определенных задач, всякий интуитивный алгоритм может быть реализован с помощью нее

Состоит из:

1) Ленты, разбитой на ячейки и бесконечной в обе стороны.

2) Управляющего устройства, которое может находиться в одном из конечного числа внутренних состояний 

3) Считывающей/пишущей головки, которая может перемещаться вдоль ленты и в каждый момент времени обозревает (считывает) одну из ячеек ленты.

Функционирование:

А) записывает в эту ячейку символ внешнего алфавита;

Б) сдвигает считывающую головку на один шаг влево или один шаг вправо или оставляет ее на месте;