Алгебра логики

Август 11, 2022

Главная
Математика
Алгебра логики

Содержание

2. Высказывания Множество путем описания свойств его элементов может быть выделено из универсального множества. U = {
3. Множества истинности высказывания Подмножество универсального множества, выделенное свойством, о котором утверждается в высказывании, называют множеством истинности
4. Простые и составные высказывания Высказывания, которым соответствуют простые (атомарные, выделяемые одним свойством) множества истинности, называются простыми.
5. Логические переменные Для обозначения высказываний вводят логические переменные. Логической переменной называется такая величина х, которая может
6. Логические операции Связки в составных высказываниях являются логическими операциями, определенными на множестве логических переменных. Элементарные логические
7. Логическое отрицание Логическим отрицанием (инверсией) высказывания х является высказывание х (не х) со множеством истинности Х,
8. Логическое сложение Логическим сложением (дизъюнкцией) высказываний х и у является высказывание х∨у (х или у) со
9. Логическое умножение Логическим умножением (конъюнкцией) высказываний х и у является высказывание х∧у (х и у) со
10. Алгебра высказываний (Булева Алгебра) Совокупность логических операций, определяемых на множестве логических переменных В образует «алгебру высказываний»
11. Формулы и порядок операций алгебры высказываний Выражения, построенные из конечного числа логических переменных, знаков логических операций
12. Тождественность выражений алгебры высказываний Каждая булева формула, содержащая n переменных, может рассматриваться как булева (логическая) функция
13. Логические функции Для обозначения сложных составных высказываний вводятся логические функции. Имея n простых высказываний x1,x2,…,xn, каждое
14. Способы задания логических функций Логическая функция – это функция вида f(x1,x2,…,xn), принимающая значение 0 или 1
15. Число различных логических функций
16. Логические функции одной переменной
17. Логические функции двух переменных
18. Свойства элементарных функций Конъюнкция, дизъюнкция, отрицание Сложение по модулю 2 Импликация Функция Шеффера Функция Пирса Эквивалентность
19. Свойства конъюнкции, дизъюнкции, отрицания Аксиомы Двойное отрицание Подобные преобразования Операции с отрицанием Операции с 0 и
20. Свойства конъюнкции, дизъюнкции, отрицания Законы Сочетательный (свойство ассоциативности) Переместительный (свойство коммутативности) Распределительный (свойство дистрибутивности) Де Мóргана
21. Свойства операции сложения по модулю 2 x ⊕ y = x ⋅y +x ⋅ y =
22. Свойства операции сложения по модулю 2 Законы Сочетательный (свойство ассоциативности) x ⊕ ( y ⊕ z
23. Свойства импликации x → y =x + y Аксиомы Подобные преобразования x → х = 1
24. Свойства функции Шеффера x | y = Аксиомы Подобные преобразования x | х = x Операция
25. Свойства функции Пирса Аксиомы Подобные преобразования x ↑ х = x Операция с отрицанием x ↑x
26. Эквивалентность
27. Аналитическое представление логических функций Булевым выражением n переменных являются Элементы идентичности 0 и 1; Булевы переменные
28. Литералы Литерал – это булева переменная х или ее дополнение х. Литералы записывают как х1 для
29. Термы Терм – это выражение составленное из литералов различных переменных (по одному литералу на каждую переменную),
30. Минтермы Минтерм (полное произведение или конъюнктивный терм) n переменных – это булево выражение, которое имеет форму
31. Минтермы Теорема. Среди 2n различных минтермов для n переменных х1, х2… хn ни одна из пар
32. Дизъюнктивные формы представления логических функций Теорема. Любая таблично заданная, отличная от 0, логическая функция может быть
33. Следствие. Любая таблично заданная логическая функция может быть представлена в виде: где Доказательство: Операция, объединяющая минтермы
34. Объединение конъюнктивных термов переменного ранга называют нормальной дизъюнктивной формой (НДФ) представления логической функции. Например, f(x1, x2,
35. Объединение конъюнктивных термов максимального ранга называют совершенной нормальной дизъюнктивной формой (СНДФ) представления логической функции. Свойства СНДФ
36. Разложение булевой функции по m переменным Теорема. Каждая булева функция f(х1, х2… хn), отличная от 0,
37. Разложение булевой функции по m переменным 2. Для функции n переменных Если представить эту функцию в
38. Следствие 1. Если m=1, то логическая функция представляется в виде f(х1, х2… хn) = x1· f(0,
39. Порядок получения СНДФ по таблице истинности Процедура построения СНДФ Параметры: таблица истинности (ТИ), n – количество
40. Макстермы Макстерм (полная сумма или дизъюнктивный терм) n переменных – это булево выражение, которое имеет форму
41. Макстермы Теорема. Среди 2n различных макстермов для n переменных х1, х2… хn ни одна из пар
42. Конъюнктивные формы представления логических функций Теорема. Любая таблично заданная, отличная от 1, логическая функция может быть
43. Следствие. Любая таблично заданная логическая функция может быть представлена в виде: где Доказательство: Операция, объединяющая макстермы
44. Пересечение дизъюнктивных термов переменного ранга называют нормальной конъюнктивной формой (НКФ) представления логической функции. Например, f(x1, x2,
45. Пересечение дизъюнктивных термов максимального ранга называют совершенной нормальной конъюнктивной формой (СНКФ) представления логической функции. Свойства СНКФ
46. Базис представления логических функций Набор логических операций называется полным, если он позволяет представить любую логическую функцию.
47. Геометрическое представление логических функций Функцию 2-х переменных можно представить на плоскости в декартовой системе координат. Две
48. Геометрическое представление логических функций Функцию 3-х переменных можно представить в 3-мерном пространстве декартовой системы координат в
49. Геометрическое представление логических функций Функцию 4-х переменных представляют в виде 4-мерного куба.
50. Геометрическое представление логических функций Каждый набор х1, х2… хn может рассматриваться как n-мерный вектор, определяющий точку
51. Минимизация логических функций Форма представления логической функции, которая содержит минимальное количество термов с минимальным количеством литералов
52. Пример: Минимизация логических функций
53. Пример: Минимизация логических функций
54. Карты Карно Карты Карно – развертки кубов на плоскости, где вершины куба – клетки карты, координаты
55. Правила минимизации 2 соседние клетки (2 0-куба) образуют 1-куб. Клетки, лежащие на границах карты, также являются
56. Минимизация функций большой размерности При числе переменных больше 4 отобразить логическую функцию в виде единой плоской
57. Анализ и синтез логических моделей Понятие математической модели Логические модели Виды логических моделей Задача синтеза Задача
58. Понятие математической модели Пусть А – произвольное множество. n-арная функция f, определенная на А со значениями
59. Понятие системной модели
60. Логические модели Логическая модель в отличии от логической функции, имея n входов, преобразует их в логические
61. Задачи анализа и синтеза логической модели Задача анализа логической модели (схемы) сводится к построению логической формулы,
62. Синтез логических моделей с одним выходом Пример: Синтезировать схему в базисе «не-импликация», если функция имеет вид
63. Задача синтеза модели с n входами и m выходами отличается от задачи синтеза m моделей с
64. Методы синтеза схем моделей Классический (основан на выделении простых импликант заданной схемы) Найти простые импликанты заданной
65. Временные логические функции Так как время – непрерывная величина, то вводят понятие автоматного времени, принимающего дискретные
66. Представление ВБФ y = f(x1,x2,…xn,t) = f0·τ0 Δ f1·τ1 Δ…Δ fs-1·τs-1, где fi – конъюнктивный/дизъюнктивный терм
67. Представление ВБФ. Пример
68. Представление ВБФ. Пример Схему такой функции можно построить, используя специальный дешифратор для генерации тактового времени -
69. Рекуррентные булевы функции Логическая функция, зависящая как от текущих значений входных переменных, так и от предшествующих
70. Элементы задержки Любая РБФ может быть реализована с помощью набора логических операторов обычных функций алгебры логики
71. Последовательные автоматы Рассмотрим частный случай РВБФ, когда на вход сигналы не подаются, а поступают только по
72. Последовательные автоматы
73. Анализ и синтез последовательных автоматов Задача анализа последовательного автомата формулируется с.о.: определить по заданной таблице состояний
74. Автоматы Обобщим модель последовательного автомата: F Ф Dk Xt Yt St-1 St X = { (x1,
76. Скачать презентацию

Слайд 2

Высказывания
Множество путем описания свойств его элементов может быть выделено из универсального

множества.
U = { ☺ ? ☹ :-) ;-) :-| ;-| ;-( :-( :) ;) }
M = { ☺ :-) :) }
Высказывание – это утверждение, которое может быть истинным или ложным.

U
Высказывание
ложно

M
Высказывание
истинно

Высказывание
- утверждение для элемента универсума о обладании выделенным свойством

Слайд 3

Множества истинности высказывания
Подмножество универсального множества, выделенное свойством, о котором утверждается в

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

Слайд 4

Простые и составные высказывания
Высказывания, которым соответствуют простые (атомарные, выделяемые одним свойством)

множества истинности, называются простыми.
Высказывания, множество истинности которых является результатом какой-либо алгебраической операции над несколькими простыми множествами истинности, называют составным.
Для получения составных высказываний используют различные логические связки: и (∧, &, *, ∩), или (∨, |, +, ∪), не (¬, ), если … то ( → ).

Слайд 5

Логические переменные
Для обозначения высказываний вводят логические переменные.
Логической переменной называется такая величина

х, которая может принимать только 2 значения: 1 – истина или 0 – ложь.
где Х ⊆ U – множество истинности высказывания х в некотором универсуме U.

Слайд 6

Логические операции
Связки в составных высказываниях являются логическими операциями, определенными на

множестве логических переменных.
Элементарные логические операции.
Логическое отрицание «не» ( ¬ ).
Логическое сложение «или» ( ∨, |, +, ∪ ).
Логическое умножение «и» ( ∧, &, *, ∩ ).

Слайд 7

Логическое отрицание
Логическим отрицанием (инверсией) высказывания х является высказывание х (не х)

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

U
Х

Слайд 8

Логическое сложение
Логическим сложением (дизъюнкцией) высказываний х и у является высказывание х∨у

(х или у) со множеством истинности Z=Х∪Y, являющимся объединением множества истинности Х высказывания х и множества истинности Y высказывания y.

X
Y

Слайд 9

Логическое умножение
Логическим умножением (конъюнкцией) высказываний х и у является высказывание х∧у

(х и у) со множеством истинности Z=Х∩Y, являющимся пересечением множества истинности Х высказывания х и множества истинности Y высказывания y.

Z
Y

Слайд 10

Алгебра высказываний (Булева Алгебра)
Совокупность логических операций,
определяемых
на множестве логических переменных В

образует «алгебру высказываний» или «булеву алгебру».
А = < B, { , ∧, ∨ } >

Слайд 11

Формулы и порядок операций алгебры высказываний
Выражения, построенные из конечного числа логических

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

Слайд 12

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

как булева (логическая) функция n переменных.
Две функции n переменных тождественны, если на всех 2n наборах своих переменных они принимают одинаковое значение.
Способы установления тождественности
Вычисление значений формул на всех наборах переменных
Установление совпадения их множеств истинности

Слайд 13

Логические функции
Для обозначения сложных составных высказываний вводятся логические функции.
Имея n простых

высказываний x1,x2,…,xn, каждое из которых может быть истинным или ложным, можно рассматривать совокупность этих высказываний как кортеж (x1,x2,…,xn).
Выполнив над ними набор логических операций получаем новое высказывание q, которое так же может быть истинным или ложным, при этом каждой комбинации значений x1,x2,…,xn будет соответствовать определенное значение q∈{0, 1}.
Значит, логическую операцию или их последовательность можно рассматривать как отображение f множества значений кортежа (x1,x2,…,xn) на множество значений q:
f : (x1,x2,…,xn) → q.

Слайд 14

Способы задания логических функций
Логическая функция – это функция вида f(x1,x2,…,xn), принимающая

значение 0 или 1 на наборе логических переменных x1,x2,…,xn.
Выражение алгебры логики
f(x1, x2, x3) = x1 + x2 *x3
Таблица истинности
Логическая схема

х1

х2

x1 + x2 *x3

х3

х3

Слайд 15

Число различных логических функций

Слайд 16

Логические функции одной переменной

Слайд 17

Логические функции двух переменных

Слайд 18

Свойства элементарных функций
Конъюнкция, дизъюнкция, отрицание
Сложение по модулю 2
Импликация

Функция Шеффера
Функция Пирса
Эквивалентность

Слайд 19

Свойства конъюнкции, дизъюнкции, отрицания
Аксиомы
Двойное отрицание
Подобные преобразования
Операции с отрицанием
Операции с 0 и

Слайд 20

Свойства конъюнкции, дизъюнкции, отрицания
Законы
Сочетательный
(свойство ассоциативности)
Переместительный
(свойство коммутативности)
Распределительный
(свойство дистрибутивности)
Де Мóргана
следствие:
Поглощения

Слайд 21

Свойства операции сложения по модулю 2
x ⊕ y = x

⋅y +x ⋅ y = ( x + y ) ⋅ (x +y )
Аксиомы
Подобные преобразования
x ⊕ х = 0
Операция с отрицанием
x ⊕x = 1
Операции с 0 и 1
x ⊕ 1 = x ; x ⊕ 0 = х

Слайд 22

Свойства операции сложения по модулю 2
Законы
Сочетательный (свойство ассоциативности)
x ⊕ ( y

⊕ z ) = ( x ⊕ y ) ⊕ z
Переместительный (свойство коммутативности)
x ⊕ y = y ⊕ x
Распределительный (свойство дистрибутивности)
x ⋅ ( y ⊕ z ) = ( x ⋅ y ) ⊕ ( x ⋅ z )
Представление базовых функций
Отрицание x = x ⊕ 1
Сложение x + y = x ⊕ y ⊕ x ⋅ y
Умножение x ⋅ y = ( x ⊕ y ) ⊕ ( x + y )

Слайд 23

Свойства импликации
x → y =x + y
Аксиомы
Подобные преобразования x → х

= 1
Операция с отрицанием x →x = x
Операции с 0 и 1 x → 0 = x ; x → 1 = 1
0 → x = 1; 1 → x = x
Законы
“Переместительный” (свойство коммутативности)
x → y = y → x
Представление базовых функций
Отрицание x = x → 0
Сложение x + y =x → y
Умножение

Слайд 24

Свойства функции Шеффера
x | y =
Аксиомы
Подобные преобразования x | х

= x
Операция с отрицанием x |x = 1
Операция с 0 и 1 x | 0 = 1; x | 1 = x
x | 0 = 1; x | 1 = x

Законы
Переместительный (свойство коммутативности)
x | y = y | x
Представление базовых функций
Отрицание x = x | x
Сложение x + y = ( x | x ) | ( y | y )
Умножение x ⋅ y = ( x | y ) | ( x | y )

Слайд 25

Свойства функции Пирса

Аксиомы
Подобные преобразования x ↑ х = x
Операция с

отрицанием x ↑x = 0
Операция с 0 и 1 x ↑ 0 =x ; x ↑ 1 = 0 x ↑ 0 =x ; x ↑ 1 = 0

Законы
Переместительный (свойство коммутативности)
x ↑ y = y ↑ x
Представление базовых функций
Отрицание x = x ↑ x
Сложение x + y = ( x ↑ y ) ↑ ( x ↑ y )
Умножение x ⋅ y = ( x ↑ x ) ↑ ( y ↑ y )

Слайд 26

Эквивалентность

Слайд 27

Аналитическое представление логических функций
Булевым выражением n переменных являются
Элементы идентичности 0 и

1;
Булевы переменные х1, х2… хn;
(P+Q), (P·Q) иQ, где P и Q – булевы выражения.
Булева функция n переменных – это функция f:Bn→B [ B = {0, 1} ] такая, что f(х1, х2… хn) является булевым выражением.
При фиксированном наборе переменных х1, х2… хn и множестве значений каждой переменой xi∈{0,1}, каждый i набор представляет собой двоичное число:
i = х1·2n-1 + х2 ·2n-2 + … + хn-1 ·21 + хn ·20

Слайд 28

Литералы
Литерал – это булева переменная х или ее дополнение х.
Литералы записывают

как
х1 для переменной х, и
х0 для ее дополнения.

Слайд 29

Термы
Терм – это выражение составленное из литералов различных переменных (по одному

литералу на каждую переменную), соединенных либо операцией умножения (конъюнктивный терм), либо операцией сложения (дизъюнктивный терм).
Например,
Ранг терма определяется количеством переменных, входящих в данный терм.

Слайд 30

Минтермы
Минтерм (полное произведение или конъюнктивный терм) n переменных – это булево

выражение, которое имеет форму произведения всех булевых переменных или их дополнений, то есть минтерм состоит из n литералов по 1-му литералу на каждую переменную.

Слайд 31

Минтермы
Теорема. Среди 2n различных минтермов для n переменных х1, х2… хn

ни одна из пар минтермов не представляет собой эквивалентные булевы выражения.
Доказательство:
Так как 00 =0 =1, а 11=1, то если xi=ei, то xiei=1.
Значит, для минтерма m=me1e2…en подстановка xi=ei для i=1,2,…,n дает произведение n термов, все из которых равны 1, следовательно, минтерм равен 1.
Любой другой минтерм содержит хотя бы 1 литерал-дополнение для xi из m. А замена хотя бы 1-го литерала минтерма m на его дополнение (1→0) обнуляет минтерм m.
Т.о., для любых 2-х различных минтермов существует по крайней мере 1 набор значений переменных, для которого значения минтермов различны и, следовательно, ни какие 2 различных минтерма не являются эквивалентными. ❒

Слайд 32

Дизъюнктивные формы представления логических функций
Теорема. Любая таблично заданная, отличная от 0,

логическая функция может быть представлена аналитически в виде суммы ее минтермов, на которых она равна 1.
, где i – номера наборов, на которых функция равна 1.
Доказательство:
Если на каком-либо наборе функция f(х’1, х’2…х’n)=1, то вследствие того, что х∨1=1 в представлении функции всегда найдется минтерм mi=1.
Если же на наборе х”1, х”2… х”n f(х”1, х”2…х”n )=0, то в данном представлении не найдется ни одного элемента, равного 1, так как 0 ∨ 0 ∨ … ∨ 0 = 0.
Получается, что каждому набору i, для которого fi=1, соответствует минтерм mi, а для наборов j, на которых fj=0, нет ни одного минтерма mi=1. Поэтому таблица истинности однозначно отображается аналитической записью вида: ❒

Слайд 33

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

объединяющая минтермы в представлении функции должна удовлетворять следующим требованиям:
1) когда все минтермы представления равны 0, функция равна 0;
2) функция равна 1, когда в представлении есть 1 минтерм, равный 1.

Дизъюнктивные формы представления логических функций

Слайд 34

Объединение конъюнктивных термов переменного ранга называют нормальной дизъюнктивной формой (НДФ) представления

логической функции.
Например,
f(x1, x2, x3) = x1 + x2 ·x3
f(x1, x2, x3 , x4, x5) = x1 + x2 ·x3 · x4 ·x5 +x2 ·x3

Дизъюнктивные формы представления логических функций

Слайд 35

Объединение конъюнктивных термов максимального ранга называют совершенной нормальной дизъюнктивной формой (СНДФ)

представления логической функции.
Свойства СНДФ
СНДФ не имеет двух одинаковых минтермов
Ни один минтерм СНДФ не содержит двух одинаковых множителей
Ни один минтерм СНДФ не содержит вместе с переменной ее отрицание

Дизъюнктивные формы представления логических функций

Слайд 36

Разложение булевой функции по m переменным
Теорема. Каждая булева функция f(х1, х2…

хn), отличная от 0, может быть представлена в виде суммы булевых выражений типа .
Или
Доказательство:
1. Для функции одной переменной
f(x) = f(0) · x0 + f(1) · x1 = f(0) ·x + f(1) · x
(a) f(x) = 0, f(x) = f(0) ·x + f(1) · x = 0 ·x + 0 · x = 0 ?
f(x) = 1; f(x) = f(0) ·x + f(1) · x = 1 ·x + 1 · x = 1 ?
(b) f(x) = x; f(x) = f(0) ·x + f(1) · x = 0 ·x + 1 · x = x ?
(c) f(x) =x; f(x) = f(0) ·x + f(1) · x = 1 ·x + 0 · x =x ?
(d) f(x) = 0+x, f(x) = 1+x, f(x) = 0 +x, f(x) = 1 +x,
f(x) = 0·x, f(x) = 1 · x, f(x) = 0 ·x, f(x) = 1 ·x.
( … ? выполнение показать самостоятельно)

Слайд 37

Разложение булевой функции по m переменным
2. Для функции n переменных
Если представить

эту функцию в виде функции одной переменной х1 и применить к ней результаты теоремы, то получим: f(х1, х2… хn) = [f(0, х2… хn) ·x1] + [f(1, х2… хn) · x1].
Теперь функции f(0, х2… хn) и f(1, х2… хn) также рассматриваем как функции одной переменной х2 и применяем к ним теорему, что дает: f(0, х2… хn) = [f(0, 0, х3… хn) ·x2] + [f(0, 1, х3… хn) · x2],
f(1, х2… хn) = [f(1, 0, х3… хn) ·x2 ] + [f(1, 1, х3… хn) · x2].
f(х1, х2… хn) = [f(0, 0, х3… хn) ·x1 ·x2] + [f(0, 1, х3… хn) · x1 · x2] + +[f(1, 0, х3… хn) · x1 ·x2 ] + [f(1, 1, х3… хn) · x1 · x2].
Продолжая в этом направлении разложение по всем остальным переменным, получаем окончательный результат теоремы:
где f(e1,e2,…,en) – это либо 0, либо 1; и это значение получается при подстановке xi=ei в исходную функцию. ❒

Слайд 38

Следствие 1. Если m=1, то логическая функция представляется в виде
f(х1, х2…

хn) = x1· f(0, х2… хn) + x1· f(1, х2… хn).
Следствие 2. Если m=n, то логическая функция представляется в виде СНДФ

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

Слайд 39

Порядок получения СНДФ по таблице истинности
Процедура построения СНДФ
Параметры: таблица истинности

(ТИ), n – количество аргументов
{Переменные: i – номер набора (№ строки в ТИ)
f = “”;
Для каждого i-го набора ТИ (0 { Если на данном наборе функция равна 1,
то сформировать минтерм mi
добавить его к представлению функции (f=f+mi)
}
}
Процедура построения минтерма
Параметры: i-й набор ТИ
{Переменные: j – номер элемента в наборе
mi=“”;
Для каждого j-го элемента i-го набора ТИ (0 {
Если xj = 0, то mi = mi ·xj , иначе mi = mi · xj
}
}

Слайд 40

Макстермы
Макстерм (полная сумма или дизъюнктивный терм) n переменных – это булево

выражение, которое имеет форму суммы всех булевых переменных или их дополнений, то есть макстерм состоит из суммы n литералов по 1-му литералу на каждую переменную.

Слайд 41

Макстермы
Теорема. Среди 2n различных макстермов для n переменных х1, х2… хn

ни одна из пар макстермов не представляет собой эквивалентные булевы выражения.
Доказательство: Так как xe = e · x +e ·x, то если xi = ei, то xiei = 0.
Значит, для макстерма M=Me1e2…en подстановка xi=ei для i=1,2,…,n дает сумму n термов, все из которых равны 0, следовательно, макстерм равен 0.
Любой другой макстерм содержит хотя бы 1 литерал-дополнение для xi из M. А замена хотя бы 1-го литерала макстерма M на его дополнение (0→1) делает макстерм M единичным.
Т.о., для любых 2-х различных макстермов существует по крайней мере 1 набор значений переменных, для которого значения макстермов различны и, следовательно, ни какие 2 различных макстерма не являются эквивалентными. ❒

Слайд 42

Конъюнктивные формы представления логических функций
Теорема. Любая таблично заданная, отличная от 1,

логическая функция может быть представлена аналитически в виде произведения ее макстермов, на которых она равна 0.
, где i – номера наборов, на которых функция равна 0.
Доказательство:
Если на каком-либо наборе функция f(х’1, х’2…х’n)=0, то вследствие того, что х∧0=0 в представлении функции всегда найдется макстерм Мi=0.
Если же на наборе х”1, х”2… х”n f(х”1, х”2…х”n )=1, то в данном представлении не найдется ни одного элемента, равного 0, так как 1 ∧ 1 ∧ … ∧ 1 = 1.
Получается, что каждому набору i, для которого fi=0, соответствует макстерм Мi, а для наборов j, на которых fj=1, нет ни одного макстерма Мi=1. Поэтому таблица истинности однозначно отображается аналитической записью вида: ❒

Слайд 43

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

объединяющая макстермы в представлении функции должна удовлетворять следующим требованиям:
1) функция равна 0, когда в представлении есть 1 макстерм, равный 0;
2) функция равна 1, когда все макстермы представления равны 1.

Конъюнктивные формы представления логических функций

Слайд 44

Пересечение дизъюнктивных термов переменного ранга называют нормальной конъюнктивной формой (НКФ) представления

логической функции.
Например,
f(x1, x2, x3) = (x1 + x2) ·x3
f(x1, x2, x3 , x4, x5)=(x1+x2)·(x3 +x4 +x5 )·(x2 +x3)

Конъюнктивные формы представления логических функций

Слайд 45

Пересечение дизъюнктивных термов максимального ранга называют совершенной нормальной конъюнктивной формой (СНКФ)

представления логической функции.
Свойства СНКФ
СНКФ не имеет двух одинаковых макстермов
Ни один макстерм СНКФ не содержит двух одинаковых множителей
Ни один макстерм СНКФ не содержит вместе с переменной ее отрицание

Конъюнктивные формы представления логических функций

Слайд 46

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

представить любую логическую функцию.
Примеры полных базисов
{ и, или, не }
{ и, не }
{ или, не}
{ функция Шеффера }
{ функция Пирса }

Избыточный набор операций

Минимальный базис

Слайд 47

Геометрическое представление логических функций
Функцию 2-х переменных можно представить на плоскости в

декартовой системе координат.
Две вершины, принадлежащие одному и тому же ребру, называются соседними и «склеиваются» по переменной, меняющейся вдоль этого ребра.

«склеивание» по х

Слайд 48

Геометрическое представление логических функций
Функцию 3-х переменных можно представить в 3-мерном пространстве

декартовой системы координат в виде 3-мерного куба.

Слайд 49

Геометрическое представление логических функций
Функцию 4-х переменных представляют в виде 4-мерного куба.

Слайд 50

Геометрическое представление логических функций
Каждый набор х1, х2… хn может рассматриваться как

n-мерный вектор, определяющий точку n-мерного пространства.
Все множество наборов, на которых определена функция n-переменных f(х1,х2,..,хn), представляется в виде вершин n-мерного куба.
Отмечая точками вершины, где функция равна 1, получаем ее геометрическое представление.

Слайд 51

Минимизация логических функций
Форма представления логической функции, которая содержит
минимальное количество термов

с минимальным количеством литералов в них,
называется минимальной формой представления логической функции.
Термы максимального ранга называют 0-кубами (точки) и обозначают К0.
Если 2 0-куба из комплекта К0 отличаются только по 1-й координате, то они образуют путем «склеивания» 1-куб К1 (отрезок).
Если 2 1-куба из комплекта К1 отличаются только по 1-й координате, то они образуют путем «склеивания» 2-куб К2 (плоскость).
И т.д.

Слайд 52

Пример:
Минимизация логических функций

Слайд 53

Пример:
Минимизация логических функций

Слайд 54

Карты Карно
Карты Карно – развертки кубов на плоскости, где вершины куба

– клетки карты, координаты которых совпадают с координатами соответствующих вершин куба.
Карта заполняется также как таблица истинности: в клетке ставится 1, если эта клетка соответствует набору, на котором функция равна 1.

Слайд 55

Правила минимизации
2 соседние клетки (2 0-куба) образуют 1-куб. Клетки, лежащие на

границах карты, также являются соседними.
4 соседние клетки могут объединяться, образуя 2-куб.
8 соседних клеток могут объединяться, образуя 3-куб.
16 – 4-куб.
И т.д.

3-куб

2-куб

4-куб

Слайд 56

Минимизация функций большой размерности
При числе переменных больше 4 отобразить логическую функцию

в виде единой плоской карты Карно невозможно.
В этом случае строят комбинированную карту, состоящую из более простых (например, 4-мерных), и процедура минимизации состоит в следующем:
Сначала находят минимальные формы внутри 4-х мерных кубов.
Затем, расширяя понятие соседних клеток, отыскивают минимальные термы для совокупности карт.

Примечание: Соседними клетками являются клетки, совпадающие при совмещении карт поворотом вокруг общего ребра.

Слайд 57

Анализ и синтез логических моделей
Понятие математической модели
Логические модели
Виды логических моделей
Задача синтеза
Задача

анализа

Слайд 58

Понятие математической модели
Пусть А – произвольное множество.
n-арная функция f, определенная на

А со значениями на множестве { «Истина», «Ложь» }, называется n-арным предикатом на А.
Алгебраической системой называется тройка
< А, QF, QP >, состоящая из
непустого множества А,
множества операций QF, определенных на множестве А,
и множества предикатов QP, заданных на множестве А.
Алгебраическая система <А,Q> называется алгеброй, если QP=∅, и моделью, если QF =∅.

Слайд 59

Понятие системной модели

Слайд 60

Логические модели
Логическая модель в отличии от логической функции, имея n входов,

преобразует их в логические значения m выходов (m≥1).
Комбинационные модели (схемы) – логические модели, в которых логические преобразования входных логических значений не зависят от времени и определяются только этими значениями на входе.
Накапливающие модели (элементы с памятью) – логические модели, в которых логические преобразования входных логических значений зависят от состояния модели в предыдущие моменты времени.

Слайд 61

Задачи анализа и синтеза логической модели
Задача анализа логической модели (схемы) сводится

к построению логической формулы, являющейся моделью функции, выполняемой данной схемой, с целью минимизации ее элементов.
Задача синтеза логической модели (схемы) сводится к построению диаграммы логической модели по заданным входам (входным переменным) и выходной функции, при этом может быть необходимо учитывать ограничения в виде:
Либо базиса логических элементов, на которых должна быть построена схема;
Либо по количеству логических элементов.

Слайд 62

Синтез логических моделей с одним выходом
Пример: Синтезировать схему в базисе «не-импликация»,

если функция имеет вид x → (x ·y + z).
Шаг 1.
Найти выражение для выходной функции в заданном базисе.
Перейдем от смешанной системы логических функций к заданному базису «не-импликация» на основе правил перехода: x → y = = x + y = и .
Шаг 2.
Найти минимальную форму
для логической функции и
построить схему.

х

x→y

(x→y)→z

f(x,y,z)

Слайд 63

Задача синтеза модели с n входами и m выходами отличается от

задачи синтеза m моделей с n входами и 1 выходом тем, что при решении необходимо исключить дублирование в m схемах синтезируемых функций.
Например, дешифратор.
Таблица истинности (n=3,m=8)

Синтез логических моделей с несколькими выходами

… …

Слайд 64

Методы синтеза схем моделей
Классический (основан на выделении простых импликант заданной схемы)
Найти

простые импликанты заданной системы логических функций;
Выразить каждую функцию через них;
Синтезировать схему, включающую только простые импликанты и связи между ними.
Метод каскадов (основан на теореме о разложении логической функции по k переменным)
Каждая логическая функция раскладывается по k переменным до тех пор, пока не будут получены функции fij…k, зависящие только от 2-х аргументов;
Синтезируется система, соответствующая системе уравнений минимального ранга и строится ее схема.

f(х1, х2… хn) =xn f1 + xnf2;
f1(х1, х2… хn-1) =xn-1 f11 + xn-1f12;
f2(х1, х2… хn-1) =xn-1 f21 + xn-1f22;
f11(х1, х2… хn-2) =xn-2 f111 + xn-2f112;
f12(х1, х2… хn-2) =xn-2 f121 + xn-2f122;
f21(х1, х2… хn-2) =xn-2 f211 + xn-2f212;
f22(х1, х2… хn-2) =xn-2 f221 + xn-2f222;
… … …

Слайд 65

Временные логические функции
Так как время – непрерывная величина, то вводят понятие

автоматного времени, принимающего дискретные целочисленные значения 0, 1, 2, … .
Логическая функция y=f(x1,x2,…xn,t), принимающая значения {0,1} при 0 ≤ t ≤ s-1, где s – количество тактов автоматного времени, называется временной.
Число различных ВБФ равно

Время принимает s значений

2n наборов для каждого ti

Слайд 66

Представление ВБФ
y = f(x1,x2,…xn,t) = f0·τ0 Δ f1·τ1 Δ…Δ fs-1·τs-1, где
fi

– конъюнктивный/дизъюнктивный терм от x1,x2,…xn;
τi – вспомогательная функция, принимающая значение из множества {0,1} в момент времени ti;
Δ - операция дизъюнкции/конъюнкции.
Такая форма представления позволяет применять к временным булевым функциям (ВБФ) все методы упрощения и минимизации простых логических (булевых) функций.

Слайд 67

Представление ВБФ. Пример

Слайд 68

Представление ВБФ. Пример
Схему такой функции можно построить, используя специальный дешифратор для

генерации тактового времени - функций τi ( τi =1, если i=mod3(t) ).

f(x1,x2,t)

Слайд 69

Рекуррентные булевы функции
Логическая функция, зависящая как от текущих значений входных переменных,

так и от предшествующих значений самой функции, называется рекуррентной булевой функцией.
yt = f(x1t,x2t,…,xnt,yt-1,yt-2,…,yt-k),
где yt∈{0,1}, при t>0;
xit - текущие значения входных переменных;
yj - значения выходной функции в моменты времени j = t, t-1, t-2, …

Слайд 70

Элементы задержки
Любая РБФ может быть реализована с помощью набора логических операторов

обычных функций алгебры логики и операторов задержки

Слайд 71

Последовательные автоматы
Рассмотрим частный случай РВБФ, когда на вход сигналы не подаются,

а поступают только по цепям обратной связи: [ i=1,2,…,m ]
yi t+1 = fi(y1 t, y1 t-1,…, y1 t-l1,
y2 t, y2 t-1,…, y2 t-l2,
…
ym t, ym t-1,…, ym t-lm).
Если задержка осуществляется только на 1 такт, то yi t+1 = fi(y1 t, y2 t,…, ym t), i=1÷m.
Модели, описывающиеся системой уравнений вида yi t+1 = fi(y1 t, y2 t,…, ym t), i=1÷m, при заданных начальных условиях, называются последовательными автоматами.

Слайд 72

Последовательные автоматы

Слайд 73

Анализ и синтез последовательных автоматов
Задача анализа последовательного автомата формулируется с.о.: определить

по заданной таблице состояний автомата систему уравнений, описывающих работу автомата, и по заданным начальным условиям построить диаграмму переходов автомата.
Задача синтеза последовательного автомата формулируется с.о.: определить по заданной системе уравнений, описывающих работу автомата, и заданным начальным условиям таблицу состояний и/или диаграмму переходов автомата и построить его схему при заданных ограничениях.

Слайд 74

Автоматы
Обобщим модель последовательного автомата:
F
Ф
Dk
Xt
Yt
St-1
St
X = { (x1, x2,…, xn) }
Y =

{ (y1, y2,…, ym) }
S = { (s1, s2,…,ss) }
F : Xt×St-1 → Yt
Ф : Xt×St-1 → St

Система уравнений:

(в каноническом виде)

Алгебра логики

Содержание

ВысказыванияМножество путем описания свойств его элементов может быть выделено из универсального

Множества истинности высказыванияПодмножество универсального множества, выделенное свойством, о котором утверждается в

Простые и составные высказыванияВысказывания, которым соответствуют простые (атомарные, выделяемые одним свойством)

Логические переменныеДля обозначения высказываний вводят логические переменные.Логической переменной называется такая величина

Логические операции Связки в составных высказываниях являются логическими операциями, определенными на

Логическое отрицаниеЛогическим отрицанием (инверсией) высказывания х является высказывание х (не х)

Логическое сложениеЛогическим сложением (дизъюнкцией) высказываний х и у является высказывание х∨у

Логическое умножениеЛогическим умножением (конъюнкцией) высказываний х и у является высказывание х∧у

Алгебра высказываний (Булева Алгебра)Совокупность логических операций, определяемых на множестве логических переменных В

Формулы и порядок операций алгебры высказыванийВыражения, построенные из конечного числа логических

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

Логические функцииДля обозначения сложных составных высказываний вводятся логические функции.Имея n простых

Способы задания логических функцийЛогическая функция – это функция вида f(x1,x2,…,xn), принимающая

Число различных логических функций

Логические функции одной переменной

Логические функции двух переменных

Свойства элементарных функций Конъюнкция, дизъюнкция, отрицание Сложение по модулю 2 Импликация

Свойства конъюнкции, дизъюнкции, отрицанияАксиомыДвойное отрицаниеПодобные преобразованияОперации с отрицаниемОперации с 0 и

Свойства операции сложения по модулю 2 x ⊕ y = x

Свойства операции сложения по модулю 2ЗаконыСочетательный (свойство ассоциативности) x ⊕ ( y

Свойства импликации x → y =x + yАксиомыПодобные преобразования x → х

Свойства функции Шеффера x | y = АксиомыПодобные преобразования x | х

Свойства функции Пирса АксиомыПодобные преобразования x ↑ х = x Операция с

Эквивалентность

Аналитическое представление логических функцийБулевым выражением n переменных являютсяЭлементы идентичности 0 и

ЛитералыЛитерал – это булева переменная х или ее дополнение х.Литералы записывают

ТермыТерм – это выражение составленное из литералов различных переменных (по одному

МинтермыМинтерм (полное произведение или конъюнктивный терм) n переменных – это булево

МинтермыТеорема. Среди 2n различных минтермов для n переменных х1, х2… хn

Дизъюнктивные формы представления логических функцийТеорема. Любая таблично заданная, отличная от 0,

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

Объединение конъюнктивных термов переменного ранга называют нормальной дизъюнктивной формой (НДФ) представления

Объединение конъюнктивных термов максимального ранга называют совершенной нормальной дизъюнктивной формой (СНДФ)

Разложение булевой функции по m переменнымТеорема. Каждая булева функция f(х1, х2…

Разложение булевой функции по m переменным2. Для функции n переменныхЕсли представить

Следствие 1. Если m=1, то логическая функция представляется в видеf(х1, х2…

Порядок получения СНДФ по таблице истинностиПроцедура построения СНДФ Параметры: таблица истинности

МакстермыМакстерм (полная сумма или дизъюнктивный терм) n переменных – это булево

МакстермыТеорема. Среди 2n различных макстермов для n переменных х1, х2… хn

Конъюнктивные формы представления логических функцийТеорема. Любая таблично заданная, отличная от 1,

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

Пересечение дизъюнктивных термов переменного ранга называют нормальной конъюнктивной формой (НКФ) представления

Пересечение дизъюнктивных термов максимального ранга называют совершенной нормальной конъюнктивной формой (СНКФ)

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

Геометрическое представление логических функцийФункцию 2-х переменных можно представить на плоскости в

Геометрическое представление логических функцийФункцию 3-х переменных можно представить в 3-мерном пространстве

Геометрическое представление логических функцийФункцию 4-х переменных представляют в виде 4-мерного куба.

Геометрическое представление логических функцийКаждый набор х1, х2… хn может рассматриваться как

Минимизация логических функцийФорма представления логической функции, которая содержит минимальное количество термов

Пример:Минимизация логических функций

Пример:Минимизация логических функций

Карты КарноКарты Карно – развертки кубов на плоскости, где вершины куба

Правила минимизации2 соседние клетки (2 0-куба) образуют 1-куб. Клетки, лежащие на

Минимизация функций большой размерностиПри числе переменных больше 4 отобразить логическую функцию

Анализ и синтез логических моделейПонятие математической моделиЛогические моделиВиды логических моделейЗадача синтезаЗадача

Понятие математической моделиПусть А – произвольное множество. n-арная функция f, определенная на

Понятие системной модели

Логические моделиЛогическая модель в отличии от логической функции, имея n входов,

Задачи анализа и синтеза логической моделиЗадача анализа логической модели (схемы) сводится

Синтез логических моделей с одним выходомПример: Синтезировать схему в базисе «не-импликация»,

Задача синтеза модели с n входами и m выходами отличается от

Методы синтеза схем моделейКлассический (основан на выделении простых импликант заданной схемы)Найти

Временные логические функцииТак как время – непрерывная величина, то вводят понятие

Представление ВБФy = f(x1,x2,…xn,t) = f0·τ0 Δ f1·τ1 Δ…Δ fs-1·τs-1, гдеfi

Представление ВБФ. Пример

Представление ВБФ. ПримерСхему такой функции можно построить, используя специальный дешифратор для

Рекуррентные булевы функцииЛогическая функция, зависящая как от текущих значений входных переменных,

Элементы задержкиЛюбая РБФ может быть реализована с помощью набора логических операторов

Последовательные автоматыРассмотрим частный случай РВБФ, когда на вход сигналы не подаются,

Последовательные автоматы

Анализ и синтез последовательных автоматовЗадача анализа последовательного автомата формулируется с.о.: определить

АвтоматыОбобщим модель последовательного автомата:FФDkXtYtSt-1StX = { (x1, x2,…, xn) }Y =

Похожие презентации

Высказывания
Множество путем описания свойств его элементов может быть выделено из универсального

Множества истинности высказывания
Подмножество универсального множества, выделенное свойством, о котором утверждается в

Простые и составные высказывания
Высказывания, которым соответствуют простые (атомарные, выделяемые одним свойством)

Логические переменные
Для обозначения высказываний вводят логические переменные.
Логической переменной называется такая величина

Логические операции
Связки в составных высказываниях являются логическими операциями, определенными на

Логическое отрицание
Логическим отрицанием (инверсией) высказывания х является высказывание х (не х)

Логическое сложение
Логическим сложением (дизъюнкцией) высказываний х и у является высказывание х∨у

Логическое умножение
Логическим умножением (конъюнкцией) высказываний х и у является высказывание х∧у

Алгебра высказываний (Булева Алгебра)
Совокупность логических операций,
определяемых
на множестве логических переменных В

Формулы и порядок операций алгебры высказываний
Выражения, построенные из конечного числа логических

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

Логические функции
Для обозначения сложных составных высказываний вводятся логические функции.
Имея n простых

Способы задания логических функций
Логическая функция – это функция вида f(x1,x2,…,xn), принимающая

Свойства элементарных функций
Конъюнкция, дизъюнкция, отрицание
Сложение по модулю 2
Импликация

Свойства конъюнкции, дизъюнкции, отрицания
Аксиомы
Двойное отрицание
Подобные преобразования
Операции с отрицанием
Операции с 0 и

Свойства операции сложения по модулю 2
x ⊕ y = x

Свойства операции сложения по модулю 2
Законы
Сочетательный (свойство ассоциативности)
x ⊕ ( y

Свойства импликации
x → y =x + y
Аксиомы
Подобные преобразования x → х

Свойства функции Шеффера
x | y =
Аксиомы
Подобные преобразования x | х

Свойства функции Пирса

Аксиомы
Подобные преобразования x ↑ х = x
Операция с

Аналитическое представление логических функций
Булевым выражением n переменных являются
Элементы идентичности 0 и

Литералы
Литерал – это булева переменная х или ее дополнение х.
Литералы записывают

Термы
Терм – это выражение составленное из литералов различных переменных (по одному

Минтермы
Минтерм (полное произведение или конъюнктивный терм) n переменных – это булево

Минтермы
Теорема. Среди 2n различных минтермов для n переменных х1, х2… хn

Дизъюнктивные формы представления логических функций
Теорема. Любая таблично заданная, отличная от 0,

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

Разложение булевой функции по m переменным
Теорема. Каждая булева функция f(х1, х2…

Разложение булевой функции по m переменным
2. Для функции n переменных
Если представить

Следствие 1. Если m=1, то логическая функция представляется в виде
f(х1, х2…

Порядок получения СНДФ по таблице истинности
Процедура построения СНДФ
Параметры: таблица истинности

Макстермы
Макстерм (полная сумма или дизъюнктивный терм) n переменных – это булево

Макстермы
Теорема. Среди 2n различных макстермов для n переменных х1, х2… хn

Конъюнктивные формы представления логических функций
Теорема. Любая таблично заданная, отличная от 1,

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

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

Геометрическое представление логических функций
Функцию 2-х переменных можно представить на плоскости в

Геометрическое представление логических функций
Функцию 3-х переменных можно представить в 3-мерном пространстве

Геометрическое представление логических функций
Функцию 4-х переменных представляют в виде 4-мерного куба.

Геометрическое представление логических функций
Каждый набор х1, х2… хn может рассматриваться как

Минимизация логических функций
Форма представления логической функции, которая содержит
минимальное количество термов

Пример:
Минимизация логических функций

Пример:
Минимизация логических функций

Карты Карно
Карты Карно – развертки кубов на плоскости, где вершины куба

Правила минимизации
2 соседние клетки (2 0-куба) образуют 1-куб. Клетки, лежащие на

Минимизация функций большой размерности
При числе переменных больше 4 отобразить логическую функцию

Анализ и синтез логических моделей
Понятие математической модели
Логические модели
Виды логических моделей
Задача синтеза
Задача

Понятие математической модели
Пусть А – произвольное множество.
n-арная функция f, определенная на

Логические модели
Логическая модель в отличии от логической функции, имея n входов,

Задачи анализа и синтеза логической модели
Задача анализа логической модели (схемы) сводится

Синтез логических моделей с одним выходом
Пример: Синтезировать схему в базисе «не-импликация»,

Методы синтеза схем моделей
Классический (основан на выделении простых импликант заданной схемы)
Найти

Временные логические функции
Так как время – непрерывная величина, то вводят понятие

Представление ВБФ
y = f(x1,x2,…xn,t) = f0·τ0 Δ f1·τ1 Δ…Δ fs-1·τs-1, где
fi

Представление ВБФ. Пример
Схему такой функции можно построить, используя специальный дешифратор для

Рекуррентные булевы функции
Логическая функция, зависящая как от текущих значений входных переменных,

Элементы задержки
Любая РБФ может быть реализована с помощью набора логических операторов

Последовательные автоматы
Рассмотрим частный случай РВБФ, когда на вход сигналы не подаются,

Анализ и синтез последовательных автоматов
Задача анализа последовательного автомата формулируется с.о.: определить

Автоматы
Обобщим модель последовательного автомата:
F
Ф
Dk
Xt
Yt
St-1
St
X = { (x1, x2,…, xn) }
Y =