Основные логические тождества:
Идемпотентность:
1) 
2) 
Коммутативность:
3) 
4) 
Ассоциативность:
5) 
6) 
Дистрибутивность:
Конъюнкции относительно диъюнкции:
7) 
Дизъюнкции относительно конъюнкции:
8) 
Законы де Моргана:
9) 
10) 
Закон двойного отрицания:
11) 
Закон противоречия:
12) 
Закон исключения третьего:
13) 
14) 
15) 
16) 
Тождества, содержащие константы:
17) 
18) 
19) 
20) 
21) 
22) 
23) 
24) 
25) 
26) 
Законы поглощения:
27) 
28) 
29) 
30) 
Булева функция n переменных. Способы задания
Теорема о разложении БФ по переменным. СДНФ
СДНФ – совершенная ДНФ
ДНФ – дизъюнктивная нормальная форма
ДНФ – совершенная, если все её составляющие – элементарные конъюнкции (ЭК) являются полными (ПЭК)
ЭК – конъюнкция логических переменных или их отрицаний
ПЭК – ЭК, в которую входят все логические переменные множества
11) Понятие замкнутости класса функции. Классы 
Замыкание над множеством БФ M – множество всех БФ, представимых формулами над M
Множество БФ M – замкнутый класс, если 
Классы функций:
1) Класс функций, сохраняющих 0 ( 
):
БФ сохраняет 0, если на нулевом наборе множество всех функций, сохраняющих 0, образует 
ДНФ (СДНФ) сохраняет 0, если в неё не входит конъюнкция, в которой все элементы с отрицанием
2) Класс функций, сохраняющих 1 ( 
):
БФ сохраняет 1, если на единичном наборе множество всех функций, сохраняющих 1, образует 
ДНФ (СДНФ) сохраняет 1, если в неё входит конъюнкция, в которой все элементы без отрицания
|
|
|
3) Класс самодвойственных функций (S):
БФ 
– двойственна к 
, если 
БФ f – самодвойственная, если f = 
Все самодвойственные функции образуют 
У самодвойственных функций на противоположных наборах значения противоположны
4) Класс монотонных функций (M)
БФ – монотонная, если при любом возрастании набора, значения функции не убывают
ДНФ (СДНФ) – монотонная, если в ней отсутствуют отрицания
Все монотонные функции образуют 
5) Класс линейный функций L
Многочлен Жегалкина – выражение, в котором нет отрицаний, а конъюнкции переменных связаны операцией 
Любую БФ можно представить в виде многочлена Жегалкина
Линейная функция (ЛФ) – БФ, которую можно представить в виде линейного многочлена Жегалкина (ЛМЖ)
Множеством линейных функций образуется 
Полнота системы БФ. Базис. Теорема Поста о полноте.
Понятия минимальной ДНФ
МДНФ – минимальная ДНФ
МДНФ – ДНФ, содержащая наименьшее число вхождений переменных по сравнению с другими ДНФ
Методы минимизации – метод карт Карно, метод Квайна
Метод карт Карно:
Метод Квайна:
1) Построить таблицу конституентов следующий образом:
I гр. – нулевой набор (если F(0,0,…,0) = 1)
|
|
|
II гр. – наборы, содержащие одну единицу
III гр. – наборы, содержащие две единицы
…
N гр. - наборы, содержащие N единиц
Далее склеиваем по 2 набора из соседних групп, если они отличаются на 1 символ
Наборы, которые не были задействованы в склеивании, выписываем отдельно
2) Строим импликантную матрицу Квайна для удаления лишних импликант
Строки – ПИ СоДНФ
Столбцы – конституенты СоДНФ
ПИ поглощают конституенты, если она является их частью
2.1) Строим МДНФ
2.1.1) Ищем столбцы, имеющие 1 метку
Соответствующие этим меткам ПИ – базисные и образуют ядро БУ
2.1.2) Рассматриваем различные варианты выбора совокупности ПИ, которые поглотят оставшиеся столбцы матрицы и выбирается вариант с минимальным суммарным числом символов
ПИ – простая импликация
СоДНФ – сокращённая ДНФ
МДНФ – минимальная ДНФ
БУ – булевое уравнение
Дата добавления: 2018-09-20; просмотров: 781; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!