- •Ахметова Наиля Абдулхамитовна
- •Введение
- •1. Элементы комбинаторики
- •1.1. Перестановки. Размещения. Сочетания
- •Теорема.
- •1.2. Задачи по комбинаторике
- •2. Функции алгебры логики
- •2.1. Элементарные функции алгебры логики
- •Пример 2.
- •2.2. Формульное задание функций алгебры логики
- •Упрощение записи формул:
- •Теорема о замене подформул на эквивалентные
- •Некоторые свойства элементарных функций
- •Следствия из свойств элементарных функций
- •Пример 3:
- •2.3 Принцип двойственности
- •Пример 1. Покажем с помощью таблицы истинности, что константа 0 двойственна к 1:
- •Пример 3. Покажем, что функция х1х2 двойственна к x1&x2, функция х1х2 двойственна к функции x1|x2.
- •Принцип двойственности
- •Лемма о несамодвойственной функции
- •2.4 Разложение булевой функции по переменным
- •Теорема о разложении функции по переменным
- •2.5. Полнота, примеры полных систем
- •Полные системы
- •Представление функции в виде полинома Жегалкина
- •Теорема Жегалкина
- •2.6. Замыкание и замкнутые классы
- •Важнейшие замкнутые классы в р2
- •Теорема Поста о полноте
- •Примеры использования теоремы Поста.
- •3. Составим критериальную таблицу для другой полной системы функций из р2: {0, 1,x1x2,x1x2}.
- •Теорема о достаточности четырех функций.
- •2.7. Функции k - значной логики
- •Теорема о полной в Рk системе функций
- •2.8. Задачи и упражнения по функциям алгебры логики
- •1. Построить таблицы соответствующих функций, выяснить, эквивалентны ли формулы и :
- •2. Построив таблицу для соответствующих функций, убедитесь в справедливости следующих эквивалентностей:
- •3. Минимизация булевых функций
- •3.1. Минимизация нормальных форм
- •Алгоритм Квайна построения сокращенной днф.
- •Метод Блейка
- •Алгоритм построения сокращенной днф с помощью кнф (метод Нельсона)
- •Построение всех тупиковых днф.
- •Алгоритм минимизации функций в классе днф
- •Алгоритм минимизации функций в классе кнф
- •Алгоритм минимизации функций в классе нормальных форм
- •3.2 Минимизация частично определенных функций
- •Алгоритм минимизации частично определенных функций в классе днф
- •Алгоритм минимизации частично определенных функций в классе кнф
- •Метод минимизирующих карт Карно
- •3.3 Задачи по минимизации и доопределению булевых функций
- •4. Логика высказываний
- •4.1. Введение в логику высказываний
- •4.2. Задачи по алгебре высказываний
- •Список литературы
Теорема Жегалкина
Каждая функция из может быть представлена в виде полинома Жегалкина единственным образом.
Здесь единственность понимается с точностью до порядка слагаемых в сумме и порядка сомножителей в конъюнкциях:
,s= 0, 1, ...,n.Доказательство.Любая функция изР2может быть представлена формулой над {x1&x2,x1x2, 0, 1}, а эта формула после раскрытия всех скобок и приведения подобных членов дает полином Жегалкина. Докажем единственность представления. Рассмотрим функцииf(x1, ...,xn) отnпеременных. Мы знаем, что всего таких функций, т.е. их таблиц истинности , 2n. Подсчитаем число различных полиномов Жегалкина отnпеременных, т.е. число вариаций вида: . Число наборов равно числу всех подмножеств множества {x1, ...,xn}, сюда входит и пустое множество (еслиs= 0). Число подмножеств множества из n элементов равно 2n, а так как каждый набор входит с коэффициентом , принимающим два значения: 0 или 1, то число всевозможных полиномов будет . Так как каждому полиному соответствует единственная функция, число функций отnпеременных равно числу полиномов, то каждой функции будет соответствовать единственный полином.
Определение. Функцияf(x1, ...,xn), полином Жегалкина для которой имеет следующий линейный относительно переменных вид:f=а0 а1х1 а2х2 ...аnхn, называется линейной.
Лемма о нелинейной функции. Суперпозицией нелинейной функции, отрицания и константы 1 можно получить конъюнкцию.
Доказательство.Пустьf(x1, ...,xn) – нелинейная функция. Тогда полином Жегалкина содержит для нее слагаемое, в котором присутствует произведениеxixj. Будем считать для простоты, чтоx1x2в многочлене Жегалкина является этим произведением. Произведя группировку слагаемых, функциюfпредставим в виде
Функция h0не есть тождественный нуль, иначе в полиноме Жегалкина отсутствует слагаемое с произведениемx1x2. Тогда существует набор (3, …,n) из 0 и 1, для которогоh0(3, …,n) = 1. Пусть h1(3, …, n) = a, h2(3, …, n) = b, h3(3, …, n) = c. Тогда
Построим функцию:
гдеd=abc. Еслиd= 0, тоh(x1,x2) =x1x2. Еслиd= 1, тоh(x1,x2) =x1x2 1 и тогдаЛемма доказана.
Функция f(x1, ...,xn) сохраняет константуa{0, 1}, еслиf(a, …,a) =a.
Пример 4.Функцияxyсохраняет 0, сохраняет 1. Функцияxyсохраняет 1 и не сохраняет 0.
2.6. Замыкание и замкнутые классы
Определение 1.ПустьMР2. ЗамыканиемМназывается множество всех функций изP2, которые можно выразить формулами надМ. ЗамыканиеМобозначается [M].
Определение 2. Множество функцийМназывается замкнутым классом, если [M]=M.
Пример 1.
1) P2 – замкнутый класс.
2) Множество {1,x1x2} не является замкнутым классом. Его замыканием будет класс линейных функций: [{1, x1 x2}] = {f(x1, ..., xn) = c0 c1x1 cnxn}. Действительно, по определению формулы над М, функция f(G1, x3), где f – есть сумма по модулю 2, G1 – функция х1 х2, будет формулой над М: f(G1, x3) = (x1 x2) x3.
Замечание. В терминах замыкания и замкнутого класса можно дать другое определение полноты, эквивалентное исходному:
М– полная система, если [M] =P2.
3) A= {f(x1, ...,xn)f(1, 1, ..., 1) = 0} – незамкнутый класс. Возьмем формулу над этим множеством. Пустьf,g1, ...,gn A, т.е.f(1, 1, ..., 1) = 0,g1(1, 1, ..., 1) = 0, тогдаf(g1, ...,gn)[A]. Посмотрим, принадлежит ли функцияf(g1, ...,gn) множествуА.f(g1(1, ..., 1),g2(1, ..., 1), ...,gn(1, ..., 1) =f(0, ..., 0)), ноf(0, ..., 0) не обязано быть равным 0. Действительно, пустьg1(x1,x2) =x1 x2,g2(x) =xA. Возьмемg2(g1(x1,x2)) =x1 x2 [A],g2(g1(1, 1)) = 11 = 0, следовательно,g2(g1(x1,x2))A, отсюда [A]AиА– незамкнутый класс.