- •Ахметова Наиля Абдулхамитовна
- •Введение
- •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. Задачи по алгебре высказываний
- •Список литературы
Упрощение записи формул:
1) внешние скобки можно отпускать;
2) приоритет применения связок возрастает в следующем порядке: ~,,,&;
3) связка – над одной переменной сильнее всех связок;
4) если связка – стоит над формулой, то сначала выполняется формула, затем отрицание;
5) если нет скобок, то операции и выполняются в последнюю очередь.
Теорема о замене подформул на эквивалентные
Пусть N<M> и имеет вид:N(x1, ...,xn) =g(G1, ...Gi, ...,Gm). Пусть подформулаGi~Gi, тогда формулаN(x1, ...,xn) =g(G1, ...,Gi,...,Gm) эквивалентна формулеN(x1, ...,xn) = g(G1, ...,Gi, ...,Gm).
Доказательство.ФормулыNиNэквивалентны, если реализуют одну и ту же функцию. Согласно построению функции, реализующей формулу имеем:
N(x1, ...,xn) =g(f1(x1, ...,xn), ...,fi(x1, ...,xn), ...,fm(x1, ...,xn)),
N(x1, ...,xn)= g(f1(x1, ...,xn), ...,fi(x1, ...,xn), ...,fm(x1, ...,xn)).
По условию Gi~Gi, следовательно на наборе1, ...,n) имеемfi 1, ...,n) = =fi1, ...,n) следовательно, на любом наборе1, ...,n)значения функцииg(f1, ...,fi, ...,fm) иg(f1, ...,fi, ...,fm) совпадают. ПолучимN~N.
Некоторые свойства элементарных функций
1. Идемпотентность & и :х&x=x,xx=x.
2. Коммутативность &,,,|,~,.
3. Ассоциативность &,,,~, поэтому в формулах видаxyzможно не ставить никаких скобок.
4. Дистрибутивность:
а) & по отношению к :x&(yz)=xyxz,
б) по отношению к &:x(y&z)=(xy)&(xz) ,
в) & по отношению к :x(yz)=xyxz.
5. Инволюция : =х.
6. Правило де Моргана: =&и =.
7. Законы действия с 0 и 1:
x0=x,x1=1 ,x=1 ,x&0=0 ,x&1=x,x&=0 ,x1=,x0=x.
8. Самодистрибутивность импликации: x(yz)=(xy)(xz).
Равенство всех этих формул доказывается по определению, т.е. по равенству функций, которые они реализуют.
Проверим для примера самодистрибутивность импликации : x(yz)=(xy)(xz).
-
x
y
z
yz
x(yz)
xy
xz
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
0
0
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
1
0
1
Следствия из свойств элементарных функций
1. Законы склеивания:
xyx=x(y)=x1=x(дистрибутивность & относительно);
(xy)&(x)=xy=x0=x(дистрибутивностьотносительно &).
2. Законы поглощения:
xxy=x(1y)=x1=x;x&(xy)=xxy=x.
Свойства элементарных функций и теорема о замене подформул на эквивалентные позволяют упрощать формулы.
Пример 3:
Упростим формулы:
1. x2x3x12x3 =x3(x2x12) = x3((x2x1)&(x22)) = (x1x2)x3.
2. x11x212x312x3x4 =x11(x223x4) =x11(x2x323x4) = (x11)(x1x2x323х4) =x1(x2x3)()x4 =x1(x2х3())(x2x3x4) =x1x2x3x4.
2.3 Принцип двойственности
Определение 1.Функцииf*(x1, ...,xn) называется двойственной к функцииf(x1, ...,xn), еслиf*(x1, ...,xn) = (1, ..., n).
Пример 1. Покажем с помощью таблицы истинности, что константа 0 двойственна к 1:
-
x
f
f*
0
1
0
0
1
1
Функции f(x) = x и g(x) = двойственны сами себе:
-
x
f
f*
g
g*
0
1
0
1
0
1
1
0
1
0
так как f*(0)=(1).
Определение 2.Еслиf*(x1, ...,xn) =f(x1, ...,xn), тоf(x1, ...,xn) называется самодвойственной.
Пример 2. Покажем, чтоf(x1,x2,x3)=x1x2x3 – самодвойственна:
-
x1
x2
x3
f
f*
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
1
0
0
1
0
1
1
0
1
0
0
1
Если f*– самодвойственна, то (1, ..., n) =f(x1, ...,xn), т.е. на противоположных наборах функция принимает противоположные значения.