Элементарные логические функции. Система логических функций

Элементарные логические функции – функции существенно зависящие от одного или двух аргументов.

1 аргумент:

X			x	⌐x

x1

x2

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

Пустое множество

↓ Стрелка Пирса

Обратные импликации

Обратные импликации

Исключающее или

Штрих Шевффера

Конъюнкция

Функция равнозначности ~

Импликация →

Импликация ←

Дизъюнкция

f₀ и f₁₅ фиктивно зависит от x₁ и x₂; f₀ = 0 f₁₅ = 1

f1= f2= f3= f4= f5= f6= f7=

f8= f9= f10= f11= f12= f13= f14=

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

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

Полные базисы:

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

Тьюринг, Пост.

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

5 замкнутых классов – особенные.

1. Сохраняющие константу 0.

2. Сохраняющие константу 1.

3. Самодвойственные

4. Монотонные (возрастающие).

5. «Линейные».

Теорема о функциональной полноте базиса. Теорема Поста и Яблонского.

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

1.

f(0,0,…,0) = 0

2. f(1,1,…1) = 1

3.

4. Монотонность

x_i =1

x_j = 0

x_i>x_j

x_j = 0 x_i =0 x_i=x_j

x_j = 1 x_i =1 x_i=x_j

Определение монотонности

Функция называется монотонной, если

При условиях

И так на всем наборе из всех 2ⁿ аргументов

5. Свойство «линейности»

попадают между 0,1,

			Самодвойств.	Монотонность	Линейность
	+	+	-	+	-
	+	+	-	+	-
~	-	-	+	-	+
	+	-	-	-	+
	-

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

Стрелка Пирса:

-

-

-

-

-

Булева:

Жегалкина:

Алгебра Гильберта:

Алгебра Новикова:

2.4 Основные законы и правила преобразования выражений в булевой алгебре.

как *

как +

Переместительный:

Сочетательный:

Распределительный:

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

Правило склеивания

Правило поглощения

Операции над одним аргументом:

х*х=х

Простейшие формулы приводят к правилу склеивания.

Также:

Правило поглощения:

Любые преобразования, минимизация выражений – это эффективное применение правил склеивания и поглощения.

	при при

Уравнение Решение

Теорема разложения:

Любая ПФ в виде n аргументов (конечного) может быть представлена в виде формулы:

- сумма всем наборам

Следствие:

Из этого следует появление СДНФ – сокращенной дизъюнктивной нормальной формы.

по наборам из f(…)=1

Это СДНФ или запись по условию истинности.

(далее в тетрадке идет пример)

СКНФ – сокращенная конъюнктивная нормальная форма.

Запись по условию ложности

2.5 Минимизация выражений в булевой алгебре.

Задача минимизации:

- Установить целевую функцию. Формально описать цель поиска минимума.

- Разработка формального алгоритма достижения экстремума целевой функции.

Формальная запись КНФ или ДНФ.

Базис:

Вхождение: появление аргумента или его инверсии в выражении для функции.

Цель: минимизировать число вхождений.

Геометрическая интерпретация:

	a	b	c

СДНФ

ДНФ =

булева – просто алгебра

(Далее идет пример)

7 определений.

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

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

3. Длиной ДНФ называется число различных конъюнкций, попарно в неё входящих.

4. Кратчайшей ДНФ называется ДНФ с наименьшей, среди всех возможных ДНФ для заданной булевой функции, длиной.

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

Строгое определение: у минимальной ДНФ наименьшая сумма рангов всех конъюнкций.

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

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

Последовательность минимизации ДНФ:

1. Запись СДНФ
2. Поиск всех вариантов ДСНФ
3. Среди них поиск тупиковых ДНФ
4. Назначение минимальной ДНФ из числа тупиковых

Метод Квайна-МакКласки

1 шаг. В исходной формуле нужно произвести все операции неполного склеивания и неполного поглощения. (В результате записывается не только результат склеивания/поглощения, но и исходное выражение.)

Получив сокращенную ДНФ, среди них ищутся тупиковые.

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

Среди множества тупиковых одна или несколько являются минимальными ДНФ.

МакКласки предложил осуществлять поиск склеивающихся аргументов среди конъюнкций, отличающихся друг от друга одним аргументом.

Метод карт Карно (метод Вейча)

(идет пример)

Как выглядит карта Карно для четырех переменных переменных:

Метод 4х Z для 6 переменных.

Карты Карно для n>6 практически не используются.

? все нечетные по вертикали

Для первого нижнего квадрата: (в другие симметрично от центра)

1. 4*4

2. 2*4

3. 4*2

4. 4*4

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

- не полностью определенные переключательные функции

- скобочные формы

- переход к универсальным базисам

1. Не полностью определенные ПФ

Не полностью определенной называется ПФ из n аргументов, значения которых определены не на всех 2ⁿ аргументах

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

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

Запрещенные наборы могут быть использованы при синтезе устройства, реализующего ПФ

Пример:

x4	x3	x2	x1	f
				-
				-
				-

TODO: пример из тетрадки целиком

1. Минимизация конъюнктивных нормальных форм

Цель: построение минимальной КНФ.

2 способа:

1. Реализовать минимизацию ДНФ, а потом каким-либо способом (через формулы де Моргана) перейти к КНФ.

2. Непосредственная минимизация КНФ (по способу зеркально аналогичному минимизации ДНФ).

На картах Карно:

1. Контуры, охватывающие 0.
2. В записи дизъюнкций инвертируют аргументы

1. Скобочные формы.

Общего метода минимизации скобочных форм нет.

(Бинарные программы (алгоритмы), два типа: условный переход и присвоение).

1. Запись и минимизация в неканонических базисах.

В не избыточных базисах невозможна минимизация.

Переход к неканоническому базисы: стрелка пирса, штрих Шеффера.

Есть способ через минимальную КНФ и минимальную ДНФ.

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

X3	X2	X1	g	F

Порождающая матрица:

Каждый элемент в случае 1 заменить порождающей матрицей, а случае 0:

	x1	x2	x1x2	x3	x1x3	x2x3	x1x2x3

2.7 Технические аналоги элементарных переключательных функций.

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

Условимся называть такие устройства функциональными логическими элементами.

Дополнительные характеристики.

1. Полярность и значение питающего напряжения.
2. Электрические уровни 0 и 1.
3. Коэффициент объединения по входу.
4. Коэффициент разветвления по входу (нагрузочная способность элемента).
5. Помехоустойчивость.
6. Рассеиваемая мощность.
7. Быстродействие

2.8 Алгоритм синтеза комбинационной схемы.

Этапы:

1. Запись ПФ (или системы) в формализованном виде, допускающем последующие этапы синтеза.

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

1. Запись ПФ в виде формул через элементарные переключательные функции.
2. Минимизация форму (если таковая возможна и необходима).
3. Перевод в используемый применяемый базис, соответствующих применяемых логических элементов.
4. Получение окончательной схемы, учитывающей не только вид логических выражений, но и конкретные типы и характеристики выбранных логических элементов.

Конкретный пример:

x3	x2	x1	f1	f2

x1	x2	f1(сумма)	f2(перенос)

Полусумматор

Полный сумматор должен быть трехвходовым

x, y и перенос.

	yi	xi	Ci	Пi

Схема сумматора:

Также через формулы полусумматора

можно выразить через схему полусумматора.

Среднее распространение волны переноса ~log₂n, n – разрядность сумматора.

Возможность построить комбинационную схему, не используя переносы.

A+B=S

(Это три регистра)

P₀ – перенос из нулевого разряда

Так можно построить «комбинационный параллельный сумматор» и «сумматор с параллельным переносом».

2 промежуточных варианта:

- групповой перенос

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

(далее про модель нейрона) TODO:?

- сквозной перенос

Можно ли вычислить, что переноса из i-того разряда не будет.

если = 1, то перенос есть

q_i – отсутствие переноса в i-том разряде.

если =1, то переноса нет

Т.е можно получить функции переноса и отсутствия переноса.

Wi – сигнал, что формирование переноса в i-том разряде закончено.

При сквозном переносе формируются независимо (параллельно с суммированием) в разрядах также Pi и Qi.

Требуются три регистра:

1. Суммы
2. Признаки переноса
3. Признаки отсутствия переноса.

И учет функции на последнем этапе формирования суммы.

(Возвращаемся к пороговым элементам), рассматриваем сложное арифметическое действие

X2	X1	f	F3	F2	f1

X – совокупность аргументов (вектор). А – совокупность параметров (вектор). I-тый разряд этого представления.

F – логическая функция

Есть другие варианты.

Это представление – арифметический функционал. Можно реализовать совершенно разные арифметические функции.

Функция Радемахера (меандр):