БИЛЕТ 1

Элементы и множества.

Под множеством интуитивно понимают совокупность определенных, вполне различимых объектов, рассматриваемых как единое целое.

Отдельные объекты, из которых состоит множество, называются элементами множества.

Из определения следует, что элементы множества должны быть:

· вполне различимыми;

· иметь общее свойство.

Будем обозначать множества большими буквами латинского алфавита, а элементы – малыми буквами с индексами или без.

Отношение принадлежности элемента a множеству A обозначается а ϵ А.

Множество B называется подмножеством множества A, если всякий элемент B принадлежит A. Такое отношение обозначается как

В с А. Если В с А и В ≠ А, то В с А. В этом случае говорят, что B есть собственное подмножество A.

Ø - пустое множество;

U – универсальное множество.

Множество, состоящее из конечного числа элементов, называется конечным, в противном случае – бесконечным. Число элементов в конечном множестве A называется его мощностью и обозначается |A|.

Множества, равномощные множеству натуральных чисел N, называются счетными.

Множества, равномощные множеству вещественных чисел R, называются континуальными.

Если все рассматриваемые в ходе данного рассуждения множества являются подмножествами некоторого множества U , то такое множество называется универсальным.

Основоположником теории множеств Г. Кантором были сформулированы несколько интуитивных принципов, играющих роль аксиом. Нас интересуют два таких принципа.

Принцип объемности. Множества A и B считаются равными (A=B), если они состоят из одних и тех же элементов.

Принцип абстракции. Любая форма P(x) определяет некоторое множество A, а именно множество тех и только тех элементов a ϵ A, для которых P(a), – истинное предложение.

БИЛЕТ 2

Способы задания множеств

1. Перечислительный

А₁={3,6,9,…}

2. С помощью характеристического предиката (высказывания)

M = {x : P(x)}

M = {x | P(X)}

A₂ = {x : x²-6x+5=0}

A₃ = {(x,y) : x,y-вещественные, x²+y²≤1}

3. Порождающие процедуры

1. 1 ϵ А₄

2. Если х ϵ А₄, то 2*х ϵ А₄

А4={1,2,4,8,16,…}

4. Решающие процедуры

Ответ: да/нет.

5. Использование характеристического вектора

U={a₁,a₂,a₃,…a_n}

X_A={X₁,X₂,X₃,…X_N}

БИЛЕТ 3

Сравнее множеств.

А – подмножество множества В, если каждый элемент множества А является элементом множества В.

А с В, А=В. А с В, В с А.

А с В, елси А с В, А ≠ В.

А с В, если А not c B.

Ø с А.

А с U. (универсальное множество)

Если А с В и В с С, то А с С.

Если множество А – конечное, то |A| - мощность (количество элементов). А и В имеют одинаковую мощность, если существует взаимно-однозначное соответствие.

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

Вещественное множество не является счетным.

БИЛЕТ 4

Операции над множествами.

1. Объединение С=А В

С = {x | x ϵ A OR x ϵ B}

2. Пересечение С=А В

С = {x | x ϵ A AND x ϵ B}

3. Разность С = А \ В

C = {x | x ϵ A AND x ∉ B}

4. Симметрическая разность С= А В

C = {x | (x ϵ А AND x ∉ B) OR (x ϵ B AND x ∉ A)}

5. Дополнение С = Ᾱ

Ᾱ = U \ A.

БИЛЕТ 5

Диаграммы Венна.

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

Точки внутри фигур обозначают элементы множества.

БИЛЕТ 6

Булеан

Множество всех подмножеств множества А называется булеаном и обзначается 2^А.

2^А={Х|Х с А}

Теорема. Для конечного множества А |2^A|= 2^|A|.

Доказательство.

Индукция по А. Если |A|=0, то А = Ø и 2^ᴓ=Ø => |2^ᴓ|=|{ᴓ}=1=2⁰=2^|ᴓ|.

Индукционный переход: Пусть V A |A|<k => |2^A|=2^|A|.

Рассмотрим А={a₁,a₂,…,a_k}, |A|=k. Положим: А₁={Х с 2^А | a_k ϵ X} и А2={Х с 2^А | a_k ϵ X}

БИЛЕТ 7

Свойства операций над множествами

1. Коммутативность

A B = B A

A B = B A

2. Ассоциативность

(A B) C = A (B C)

(A B) C = A (B C)

3. Дистрибутивность

(A B) C = (A С) (C B)

(A B) C = (A С) (C B)

4. A Ᾱ = U

5. A Ᾱ = Ø

6. Законы нуля и единицы

A Ø = A

A U = U

A Ø = Ø

A U = A

7. Законы Де-Моргана

БИЛЕТ 8

Пусть M1 и M2 – два множества. Прямым (декартовым) произведением двух множеств (M1 и M2 ) называется множество всех упорядоченных пар, в котором первый элемент каждой пары принадлежит M1, а второй принадлежит M2 :

M1 х M2 ={(a,b) | a ϵ M1,b ϵ M2}.

БИЛЕТ 9

Между элементами множеств могут устанавливаться различные взаимосвязи, обычно называемые отношениями.

Имеем А1, А2,…,Аn. Рассматриваем их декартовое произведение А1 х А2 х … х Аn.

А = {(a1, …,an) : a1 A1, …, an An}.

n-местные отношения – есть R с A1x A2 x … x An.

Пример трехместных отношений: (a,b,c),c=a+b

Пример. ()

- человек;

– отец (

- мать (

Выражаем через бинарные отношения (декомпозицией):

A₁ x A₂ x …x A_n = (A₁ x … x A_n-1) x A_n.

БИЛЕТ 10

Бинарные отношения. Основные определения.

Бинарным, или двухместным, отношением R называется подмножество упорядоченных пар (а,b)€R прямого произведения M1 х M2 , т. е. R с M1 х M2 . Говорят, что отношение R задано на M1 х M2 .

Часто все элементы принадлежат одному множеству M , т. е. R с M х M , или R с M² . Так, на множестве студентов группы могут быть заданы такие бинарные отношения, как «жить в одной комнате общежития», «быть моложе», «быть земляком» и т. д. Тогда говорят, что отношение R задано на множестве M . Наравне с обозначением (а,b) ϵ R, R c M² в литературе используется обозначение аRb, R c M² .

В общем случае могут рассматриваться n -местные отношения, например отношения между тройками элементов (тернарные) и т. д.

Пример. Равенство x² + y² = z² задает тернарное отношение на множестве целых чисел. Отношение является множеством, включающим все тройки чисел (x, y, z), удовлетворяющие данному равенству. Пусть R c A х B определено в соответствии с рис., из которого следует, что в отношении R задействованы не все, а лишь некоторые

элементы исходных множеств A и B .

Тогда подмножество D(R) ={a | (a,b) ϵ R} называется областью определения отношения R, а подмножество Q(R) ={b | (a,b) ϵ R} – областью значений этого отношения.

БИЛЕТ 11

Способы задания бинарных отношений

Отношения, определенные на конечных множествах, могут задаваться:

1. Списком (перечислением) пар, для которых это отношение вы- полняется. Например, R ={(a,b), (a,c), (b,d)}.

2. Матрицей – бинарному отношению R c M₁ x M₂ , где M₁ ={a1 ,a2 ,...,an }, M2 ={b1,b2,...,bm }, соответствует матрица размера n х m , в которой элемент c_ij , стоящий на пересечении i–й строки и j-го столбца, равен 1, если между а_i и b_j имеет место отношение R , или 0,если нет:

c_ij=

3. Направленным графом, т. е. структурой, состоящей из вершин и дуг (направленных ребер). Элементы множеств отображаются в виде вершин графа, а отношения – в виде дуг, соединяющих эти вершины. Два первых способа одинаково применимы как для отношений, за- данных на разных множествах, так и для отношений на одном множестве. Третий способ больше подходит для отношений на одном множестве, т. к. позволяет получить более компактный граф.

Пример. Пусть M ={1,2,3,4,5,6}. Задать в явном виде (списком), описанием характеристических свойств, матрицей и графом отношение R с M² , если R означает – «быть строго меньше».

1. С использованием распознающей процедуры можно записать R={(a,b)|a,b ϵ M, a <b}.

2. Списком R ={(1,2),(1,3),(1,4),(1,5),(1,6).(2,3),...}.

3. Матрица данного отношения имет вид

R 1 2 3 4 5 6

1 0 1 1 1 1 1

2 0 0 1 1 1 1

3 0 0 0 1 1 1

4 0 0 0 0 1 1

5 0 0 0 0 0 1

6 0 0 0 0 0 0

Граф имеет вид

Билет 12

Свойства бинарных отношений

Пусть R – отношение на множестве M , R с M² , т. е. множество отражается само в себя. Для отношений этого типа могут быть определены следующие свойства:

1. R – рефлексивно, если имеет место aRa для любого a ϵ M . Например, отношение R={(a,b)/a≤b}рефлексивно.

2. R – антирефлексивно, если ни для какого a ϵ M не выполняется aRa. Например, отношение «быть сыном».

3. R – симметрично, если aRb влечет bRa. Например, отношение «жить в одном городе» симметрично.

4. R – антисимметрично, если aRb и bRa влекут a = b, т. е. ни для каких различающихся элементов a и b (a≠b) не выполняется одновременно aRb и bRa. Например, отношение «быть начальником» антисимметрично.

5. R – транзитивно, если aRb и bRc влекут aRc. Например, отношение «быть моложе» транзитивно. Для отношений, заданных на прямом произведении различных множеств, т. е. при R с M₁*M₂ , свойства рефлексивности, симметричности и транзитивности не определяются.

Пример. Каковы свойства отношения «Быть не больше» (R₁ ={(a,b) / a≤b}), заданного на множестве натуральных чисел N?

Рефлексивно, т. к. a ≤ a для всех a ϵ N .

Антисимметрично, поскольку если a≤b и b≤a, то a=b.

Транзитивно, т. к. если a≤b и b≤c, то a≤c.

Пример. Пусть A ={±,⊕,х,*} и пусть R с A х A определено в виде R={(±,±),(±,⊕), (±,*),

(⊕,±), (*,±),(*,*),(х,*),(х,х)}. Каковы свойства отношения?

R не является рефлексивным, т. к. ⊕ ϵ A, но (⊕, ⊕) ∉ R.

R не является симметричным, поскольку (х,*) ϵ R , но (*,х) ∉ R.

R не является антисимметричным, поскольку (⊕, ±) ϵ R и(±,⊕) ϵ R, но ±≠⊕.

R не является транзитивным, т. к. (⊕,±) ϵ R и (±,*) ϵ R, но(⊕,*) R.

БИЛЕТ 13

Разбиения и отношения эквивалентности.

Отношением эквивалентности (или просто эквивалентностью) называют бинарное отношение на множестве, если оно рефлексивно, симметрично, транзитивно. Например, отношение «жить в одном городе» на множестве людей – эквивалентность.

Отношение эквивалентности имеет важную особенность: эквивалентность R разбивает множество M , на котором оно задано, на непересекающиеся подмножества так, что элементы одного и того же подмножества находятся в отношении R , а между элементами разных подмножеств оно отсутствует. В этом случае говорят, что отношение R задает разбиение на множестве R , или систему классов эквивалентности по отношению R . Мощность этой системы называется индексом разбиения.

БИЛЕТ 14

Оношения порядка.

Оношение порядка – антисимметричное тразитивное отношение.

Отношением нестрогого порядка (или нестрогим порядком) называют бинарное отношение на множестве, если оно рефлексивно, антисимметрично, транзитивно, и отношением строгого порядка (строгим порядком), – если оно антирефлексивно, антисимметрично, транзитивно. Оба эти отношения называются отношениями порядка.

Например, отношение «быть не старше» на множестве людей, «быть не больше» на множестве натуральных чисел – нестрогий порядок. Отношения «быть моложе», «быть прямым потомком» на множестве людей – строгий порядок.

Элементы a,b сравнимы по отношению порядка R на M , если выполняется aRb или bRa .

Множество M , на котором задано отношение порядка R , может быть:

·полностью упорядоченным множеством, если любые два элемента этого множества сравнимы по отношению порядка R;

·частично упорядоченным множеством, если сравнимы лишь некоторые элементы этого множества.

БИЛЕТ 15

Комбинаторные конфигурации. Выборки.

Рассматриваем конфигурации на языке отображения.

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

Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.

Выборка объема r из элементов – набор элементов a_i1, a_i2, … a_ir из множества U={a₁,a₂,…,a_n}.

Типы выборок: все элементы разны; допускаются одинаковые.

Выборки бывают упорядоченные и неупорядоченные. Упорядоченные выборки называются размещениями, неупорядоченные – сочетаниями. Неупорядоченная – выборка, порядок следования элементов в которой не существенен. Упорядоченная – выборка, порядок следования элементов в которой задан, и и две выборки с разным порядком следования элементов считаются различными.

БИЛЕТ 16

Основные правила комбинаторики.

Основными правилами комбинаторики являются правило суммы и правило произведения.

Правило суммы (∑). Если объект А может быть выбран М способами, а объект В другими N способами, то выбор «либо А, либо В» может быть выполнен M+N способами.

х ϵ А и х ϵ В. Сколько вариантов для выбора элементов х? число=|A|+|B|.

Правило произведения (П). Если объект А может быть выбран М способами и после каждого из таких выборов объект В, в свою очередь, может быть выбран N способами, то выбор «А и В» в указанном порядке может быть выполнен MN способами.

Выбираем х ϵ А и у ϵ В (не зависит, что сперва), А и В могут быть как одинаковыми, так и разными. Число способов=|A|*|B|.

(x,y) ϵ A x B. A x B – декартово произведение. А х В = {(x,y)|x ϵ A, y ϵ B}. Число элементов в декартовом произведении равно: |A x B| = |A|*|B|.

Декартово произведение: А₁ х А₂ х А₃ х … х А_n ={(x₁, … , x_n) | x_i ϵ A_i}.

БИЛЕТ 17

Размещения.

Размещения – упорядоченные независимые выборки.

U(n,r) – число n элементов по r упорядоченных с допустимыми повторениями.

U ϵ A. |A|= n. Перестановки – все элементы разные.

В комбинаторике размеще́нием (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов.

В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы (2,1,3) и (3,2,1) являются различными, хотя состоят из одних и тех же элементов {1, 2, 3} (то есть совпадают как сочетания).

Количество размещений из n по k, обозначаемое , равно убывающему факториалу:

При k=n количество размещений равно количеству перестановок порядка n:

По правилу умножения количество размещений с повторениями из n по k, обозначаемое , равно:

БИЛЕТ 18

Сочетания.

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

В комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данного множества, содержащего n различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Так, например, наборы (3-элементные сочетания, подмножества, k=3) {2, 1, 3} и {3, 2, 1} 6-элементного множества {1, 2, 3, 4, 5, 6} (n=6) являются одинаковыми (в то время как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}.

В общем случае число, показывающее, сколькими способами можно выбрать k элементов из множества, содержащего n различных элементов, стоит на пересечении k-й диагонали и n-й строки треугольника Паскаля.[1]

Число сочетаний из n по k равно биномиальному коэффициенту:

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

Число сочетаний с повторениями из n по k равно биномиальному коэффициенту:

БИЛЕТ 19

Булевы функции. Способы задания булевых функций.

Логические, переключательные.

Джорж Буль (ввел понятие в 1864г).

B={0,1}.

0 – ложь (false), 1 – истина (true).

f(x₁,…,x_n) – функции алгебры логики, если аргументы функции и сама функция принимает значение из В.

Способы задания булевых функций.

1. Табличный

Лексографический порядок: меньше -> больше.

2. Векторный способ.

Z_f(x1,x2,x3) = (f(0,0,…,0),f(0,0,…,1),…,f(1,1,…,1))

3. Задание областью истинности.

Задаем множество:

N_f={(α₁,α₂,…,α_n) : (α₁,α₂,…,α_n)=1}

Пример. N_f={(011),(101),(110),(111)} или N_f={3,5,6,7}

4. Формулы.

5. И другие.

БИЛЕТ 20

Количество булевых функций от n переменных. Фиктивные и существенные переменные.

Обозначения: P₂ – множество всех булевых функций; P₂ⁿ – множество булевых функций от переменных x₁,x₂,…,x_n.

T1. P₂(n)=|P₂ⁿ|=

[Каждой функции P₂ⁿ можно поставить в соответствие вектор β=(β₁,β₂,…,). С другой стороны каждому двоичному вектору 2ⁿ соответствует булева функция

N=2ⁿ

P₂(n)=2^N=]

растет очень быстро:

P₂(1)=4

P₂(2)=16

P₂(3)=256

Фиктивные и существенные переменные.

Опр. Если задана булева функция f=f(x₁,…,x_n), то x_i , 1≤i≤n, называют фиктивной, если f(x₁,…,x_i-1,0,x_i+1,…, x_n)≡ f(x₁,…,x_i-1,1,x_i+1,…, x_n).

Если функция не является фиктивной, ее называют существенной.

x_i – существенная, если существует (α1,…,αn) :

f(α₁,…,α_i-1,0,α_i+1,…,α_n) ≠ f(α₁,…,α_i-1,1,α_i+1,…,α_n).

Пример. f(x,y) = cosx+sin²y+cos²y

g(x)=cosx+1. Одно и тоже.

Булевы функции рассматриваем с точностью до фиктивных переменных.

Опр. f=g, если функцию g можно получить из функции f добавлением или изъятием фиктивных переменных.

БИЛЕТ 21

Элементарные булевы функции.

g₁(0)=0

g₁(1)=0

g₃(x)=x

g₄-инверсия, отрицание.

f1 – конъюнкция, логическое умножение, “И”

f2 – дизъюнкция, логическое сложение, “ИЛИ”

f3 – сложение по модулю 2, исключение или, «либо-либо».

f4 - импликация

f5 - эквивалентность

f6 – штрих Шеффера, «функция не “И”»

f7 – стрелка Вебба, «не “ИЛИ”».

БИЛЕТ 50

Неформализованное понятие алгоритма

Термин пошел от фамилии азиатского ученого Ал-Хорезмы.

Под алгоритмом принято понимать конечную совокупность инструкций (команд), согласно которой работает исполнитель алгоритма.

Для алгоритма характерны следующие свойства:

1. Пошаговость;

2. Дискретность (точность, четкость);

3. Элементарность каждого шага;

4. Детерминированность каждого шага (такт);

5. Направленность;

6. Должны быть четко указаны форматы входных и выходных данных;

7. Начальная (стартовая) команда и команда остановки должны выполняться.

Долгое время это неформальное понятие алгоритма удовлетворяло потребности.

В начале 20в.появилась необходимость уточнения (формализации) данного понятия. Практически одновременно появилось несколько формализаций. Одной из них было понятие «Машины Тьюринга».

БИЛЕТ 22

Булевы формулы. Представление булевых функций формулами. Эквивалентность формул.

*учебник*

{

Формулы, содержащие только операции конъюнкции, дизъюнкции и отрицания называются булевыми.

Следующие две теоремы, приведенные без доказательств, устанавливают правила перехода от одного базиса к другому.

Теорема 1 Всякая логическая формула может быть представлена булевой

формулой.

Теорема 2 Если все функции функционально полной системы ∑* представимы формулами над ∑ , то ∑ также функционально полна. Таким образом, чтобы перейти в записи логической формулы от одного базиса к другому, нужно просто заменить все операции первого базиса через операции второго базиса.

}

*лекции*

Опр. Пусть задано множество А булевых функций A={f1,f2,…}. Введем понятие булевых формул на базисе А.

Определение индуктивности.

1. Функция f_i ϵ A является формулой в базисе А.

2. f_i(х₁,..,х_n) ϵ A.

Выражения: F₁, F₂, …, F_n.

F_j-любой символ переменной, либо формула в базисе А. Тогда выражение fi(F1, …, Fn) – формула в базисе А.

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

Базис Буля.

A₀={x&y, x˅y, ̚x}

Базис Жегалкина.

А₁={x*y,x⊕y, 0, 1}

Опр. Две формулы F и G называются эквивалентными, если им соответствует одна и та же булева функция: F=G.

БИЛЕТ 23.

Основные эквивалентности в алгебре-логики.

1. Ассоциативность:

x * (y * z ) = (x * y) * z

x ˅ (y ˅ z) = (x ˅ y) ˅ z

2. Коммутативность:

х1 * х2 = х2 * х1

х1 ˅ х2 = х2 ˅ х1

3. Дистрибутивность:

x * (y ˅ z) = x * y ˅ x * z .

x ˅ (y * z) = (x ˅ y) * (x ˅ z)

(x⊕y) * z = (x*z) ⊕ (y*z)

4. Идемпотентность:

x * x = x

x ˅ x = x.

5. Закон двойного отрицания:

= x .

6. Законы нуля и единицы:

х * 1 = х

х * 0 = 0

х ˅ 1 = 1

х ˅ 0 = х

7. Законы де Моргана:

= &

= ˅

8. Закон противоречия:

А * Ᾱ = 0 .

9. Закон всеобщности:

А ˅ Ᾱ =1.

10. Законы связанные со сложением по модулю 2.

х ⊕ х = 0

х ⊕ 1=

11.Законы позволяющие представить элементарные функции в классическом базисе.

x ⊕ y = (x * ) ˄ ( * y)

x ⊕ y = (x ˅ y) * ( ˅ y)

x y = ˅ y

x y = (x y) & (y x)

x y = (x * y) ˅ ( *)

x | y = ̚

x y =

12) Законы полезные для упрощения

x ˅ (x * y) = x –закон поглощения

x & (x ˅ y) = x

x ˅ ( ̚ x * y) = x ˅ y

x & y + x & y = x – закон склеивания

Особенность данных эквивалентных соотношений в том, что:

·они не выводимы друг из друга. Убедиться в их справедливости можно путем построения таблиц истинности;

·этих соотношений достаточно для выполнения любых эквивалентных преобразований.

БИЛЕТ 24

Связь между алгеброй множеств и алгеброй логики.

Пусть имеется система множеств x1,x2,…,xn,и определены операции над множествами. Мы можем рассматривать операции x Вместо этих теоретико-множественных операций мы можем рассматривать логические операции.

x v y, x ˄ y, .

Составим 2 системы:

S1 = () - алгебра множеств

S2 = (v, ˄, - ,1, 0) - булева алгебра

S1S2.

На примере закона Де Моргана.

(1)

˄ (2)

		M’	M”

X Y		˄
0 0
0 1
1 0
1 1

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

БИЛЕТ 41

Основная теорема теории логического вывода.(продолжение билета 40)

(A -> B) = v B

A & (доказательство от противного).

БИЛЕТ 25

Понятие двойственности. Принцип двойственности.

Опр. Для заданной булевой функции двойственной к ней называют: ).

Замечания.

1. 

2. F=G F*=G*

3. x*=x

{

(x)*=

x	f=x	f*
0 1	0 1	0 1

}

4. =

5. 

6. 

7. (x&y)^*=x˅y

8. (x˅y)^*=x&y

(&,˅,-,0,1)

(˅,&,-,1,0)

Пусть задана булева функция .

Замечание. В функциях f_i, i=1,…,m некоторые переменные могут быть фиктивными.

Тогда

[

= = = =

]

Следствие. Если задана булева функция формулой F в базисе Б₀=(x&y,x˅y,-,0,1), то для получения двойственной функции достаточно сделать замену:

(&,˅,-,0,1)

(˅,&,-,1,0)

БИЛЕТ 26

Разложение булевых функций по переменным.

Т. о разложении булевой функции по переменным.

Для любой булевой функции f=f(x₁,…,x_n) и V 1≤k≤n справедливо представление f(x1,…,xn)=, где x¹=x, x⁰= ̚ x.

Возьмем произвольный набор Z=(α1,…,αn) и подставим в левую и правую части формулы:

Л.Ч.=f(α1,…,αn)

П.Ч.= =

{ 1⁰==0; 0¹=0; 1¹=1; 0⁰==1; }

=

Правая часть совпала с левой.

Следствие1. Формула разложения булевой функции по переменным:

Положим k=1. Возьмем разложение по последней переменной.

Следствие2. Разложение функции в совершенную дизъюнктивную нормальную формулу (СДНФ).

V справедливо =.

=1.

Возьмем в теореме случай k=n, т.е. разложение по всем переменным.

Следствие3. О представимости любой функции в классическом базисе.

Любую булеву функцию можно представить в виде формулы над базисом.

Б₀₌{x&y,x˅y,}

f≠0 СДНФ

f≡0

Замечание. Для любой булевой функции существует представление в виде СДНФ и это представление является единственной.

БИЛЕТ 27

Совершенные дизъюнктивные нормальные формы (СДНФ)[сумма произведений ˅&].

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

включает следующие действия:

·для каждого набора значений переменных x₁, x₂ ,..., x_n , на котором функция f (x₁, x₂ ,..., x_n ) равна 1, выписываются конъюнкции всех переменных;

·над теми переменными, которые на этом наборе равны 0, ставятся отрицания;

·все такие конъюнкции соединяются знаками дизъюнкции.

Полученная таким образом формула называется совершенной дизъюнктивной нормальной формой (СДНФ) логической функции.

Для каждой функции СДНФ единствена.

Таким образом, СДНФ функции f (x₁, x₂ ,..., x_n ) представляет собой дизъюнкцию элементарных конъюнкций: D = K₁ ˅ K₂ ˅ ... ˅ K_m, где все конъюнкции имеют одинаковое число сомножителей, равное числу логических переменных, а число конъюнкций равно числу наборов значений переменных x₁, x₂ ,..., x_n , на которых функция f (x₁, x₂ ,..., x_n) равна 1. Любые другие записи логической функции, вида D = K₁ ˅ K₂ ˅ ... ˅ K_m, не отвечающие этим условиям, называются

дизъюнктивными нормальными формами (ДНФ) этой функции.

БИЛЕТ 28

Совершенные конъюнктивные нормальные формы (СКНФ)[произведение сумм &˅].

Утверждение. Для любой булевой функции f=f(x1,…,xn),f≠1 справедливо представление

Имеем: f*≠ 0. Теперь построим СДНФ для f*.

=

Возьмем двойственную от обеих частей уравнения.

= ==

Делаем замены: .

=.

Замечание. Для каждой булевой функции ≠ 1 существует представление в виде СКНФ и это представление является единственным.

БИЛЕТ 54

Тезис Тьюринга-Чёрча.

Класс функций, вычислимых алгоритмически (в интуитивном смысле слова), совпадает с классом функций вычислимых по Тьюрингу.

Доводы:

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

Примеры формализации: частично рекурсивные функции Чёрча, машины Комогорова-Успенского (мощнее машины Тьюринга), программы на алгоритмическом языке (Pascal).

2. Любая функция по Тьюрингу является алгоритмически вычислимой.

3. Все функции, которые признавались алгоритмически вычислимыми, оказались вычислимыми по Тьюрингу.

4. Деятельность тысяч программистов.

БИЛЕТ 29

Полиномы Жегалкина.

В алгебре логики обычно выделяют 3 кононические формы представления функции в виде формулы:

1. СДНФ

2. СКНФ

3. Полиномы Жегалкина

Моном – формула вида 0,1, .

Полином Жегалкина:

P=M₁⊕M₂⊕…⊕M_k, M_i – моном.

Все мономы попарно различны.

Теорема. Любую булеву функцию можно представить в виде полинома Жегалкина и это представление является единственным.

[

I. Доказываем представимость функции в виде полинома Жегалкина.

Рассмотрим 2 случая

1. f ≡ 0, F=0

2. f ≠ 0, тогда

*)

x y	x ˅ y	x
0 0	0	0
0 1	1	1
1 0	1	1
1 1	1	0

Можем заменить ˅ на ⊕, т.к. никакие два слагаемых в СДНФ≠1.

K1= ; K2=

K1*K2 ≡ 0

Значит, существует j ()

Сделаем преобразования

Раскрываем скобки, приводим подобные по правилу АА=0.

В итоге получим полином Жегалкина для каждой функции существует полином Жегалкина.