1.2 Некоторые логические функции и реализующие их логические элементы.

Логическое сложение (дизъюнкция).

Логическая функция F является логической суммой переменных Х₁, Х₂…Х_n если она равна «1» на тех наборах, на которых хотя бы одна независимая переменная равна «1», и равна «0» на остальных наборах. Пример суммы, являющейся логической суммой двух переменных Х₁ и Х₂ можно привести в следующей таблице:

Х1	0	0	1	1
Х2	0	1	0	1
F	0	1	1	1

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

Х₁ Х₂.

Сложение n-переменных . Схема с помощью которой из входных переменных Х_1, Х_{2 …}­ Х_n образуется их логическая сумма, называется логическим элементом «ИЛИ». Графическое обозначение этого элемента при двух входных переменных имеет вид (рис.1):

(рис.1)

Логическое умножение (конъюнкция).

Логическая функция F является логическим произведением (конъюнкцией) переменных Х₁,Х₂…Х_n, если она равна «1» только на тех наборах, на которых все переменные одновременно равны «1».

Пример функции F, являющейся логическим произведением двух переменных Х₁ и Х₂ имеет вид:

Х1	0	1	0	1
Х2	0	0	1	1
F	0	0	0	1

Логическое умножение двух переменных будем обозначать так же, как обозначают обычное алгебраическое умножение .

Для n-переменных .

Схема с помощью которой из входных переменных Х₁, Х₂…Х_n образуется их логическое произведение F называется логическим элементом «И»_. Графическое обозначение этого элемента имеет вид (рис.2):

рис.2

Логическое отрицание (инверсия).

Логическая функция F является логическим отрицанием переменной Х, если ее значение противоположно значению переменной Х. Таблицей истинности функция F, являющаяся отрицанием переменной Х, задается следующим образом:

Х	0	1
F	1	0

Логическое отрицание принято обозначать . Схема с помощью которой реализуется логическое отрицание, называется элементом «НЕ». Графическое обозначение этого элемента имеет вид (ис.3):

рис.2

1.3 Структурные формулы.

Запись, содержащая двоичные переменные, соединенные знаками логического умножения, сложения и инверсии, называется логическим выражением.

Такое выражение однозначно определяет комбинационное устройство, построенное на элементах «И», «ИЛИ», «НЕ».

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

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

Чаще всего пользуются двумя формами записи:

1— совершенной дизъюнктивной нормальной формой (СДНФ);

2— совершенной конъюнктивной нормальной формой (СКНФ).

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

Структурная формула в виде СДНФ может быть получена на основе таблицы истинности в следующем порядке:

1. Записывается логическая сумма слагаемых, каждое из которых логическое произведение всех независимых переменных; число слагаемых равно числу наборов таблицы истинности, на которых логическая функция равна «1».

2. Под каждым слагаемым выписывается один из единичных наборов таблицы истинности.

3. Ставится знак инверсии над теми независимыми переменными, которые равны «0» в рассматриваемом наборе.

Пример:

Х1	0	1	0	1	0	1	0	1
Х2	0	0	1	1	0	0	1	1
Х3	0	0	0	0	1	1	1	1
F	0	1	0	1	1	0	1	0

1 0 0 1 1 0 0 0 1 0 1 1

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

Представление логической функции в виде суммы минтермов и есть совершенная дизъюнктивная нормальная форма функции СДНФ.

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

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

Структурная формула в виде СКНФ может быть получена на основе таблицы истинности в следующем порядке:

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

Число сомножителей совпадает с числом наборов таблицы истинности, на которых логическая функция равна «0».

2. Ставится знак инверсии над теми независимыми переменными, которые

равны «1» в рассматриваемом наборе.

Пример:

Х1	0	1	0	1	0	1	0	1
Х2	0	0	1	1	0	0	1	1
Х3	0	0	0	0	1	1	1	1
F	0	1	0	1	1	0	1	0

0 0 0 0 1 0 1 0 1 1 1 1

Такие суммы (наборы переменных) обращаются в «0» только при определенном наборе значений переменных и носят название конституент нуля или макстермов.

Форма представления функции в виде произведения макстермов и есть соверешенная конъюктивная нормальная форма СКНФ.

Структурные формулы в виде СКНФ и СДНФ эквивалентны и могут быть преобразованы одна в другую.