Правила упрощения логических функций

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

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

Эта простейшая формула может иметь

а) либо нормальную дизъюнктивную форму

б) либо нормальную конъюнктивную форму

в) либо какой-нибудь тип.

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

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

Если количество наборов аргументов, при которых функция равна 1 меньше количества наборов, при которых она равна 0, то наиболее простой окажется СДНФ, в противном случае – СКНФ.

Если исходная функция задана аналитически, то преобразование ее в СДНФ или СКНФ выполняется в такой последовательности:

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

2) Путем раскрытия скобок (по известным формулам) логическая функция приводится к дизъюнктивной нормальной или конъюнктивной нормальной форме (где ДНФ – дизъюнкция ряда членов, которые есть конъюнкция аргументов, взятых с инверсией или без нее; а КНФ – конъюнкция ряда членов, которые есть дизъюнкция аргументов, взятых с инверсией или без нее).

3) Если это ДНФ, и каждый член представляет собой конъюнкцию менее n членов, (n – количество аргументов функции), то каждый такой член умножается на выражение (), тождественно равное 1 (X – один из аргументов, которые в данной дизъюнкции отсутствуют). В результате чего конъюнкция превращается в дизъюнкцию двух конъюнкций:

Если же это КНФ, то к каждому члену, представляющему собой дизъюнкцию менее n членов (n – количество аргументов), добавляется член (). В результате чего каждый из этих членов превращается в конъюнкцию двух дизъюнкций:

4) Приводятся подобные члены.

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

1.5.Типовые задачи по преобразованию логических функций

Существует несколько типов задач по преобразованию логических функций или их сочетания:

1) Упрощение логических функций.

2) Определение тождественности логических функций.

3) Построение таблиц истинности.

Задача 1.1. Путем тождественных преобразований получить минимальную форму

записи логической функции F1 и проверить, является ли она тождественной функции F2.

Заданы функции F1 и F2:

Решение.

Упростим функцию F1. Так как функция F1 задана аналитически, то будем производить упрощение по шагам:

1-й шаг

                                                     свертка

2-й шаг

3-й шаг

F1 = (полученный результат)

F2= (исходная функция)

Вывод: F1 тождественно равна функции F2. .

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

Заданы функции F1 и F2:

Решение.

1) Функция F2 определена таблично, запишем ее в СДНФ:

склеивание

                      

 

    Свертка

2) Упрощаем функцию F1

вторая скобка. Тогда

Вывод: логическая функция F1, заданная аналитически, тождественна функции F2, заданной таблично

Задача 1.3. Заданы функции F1 и F2:   F1=0 на наборе 0, 2, 3, 4, 6, 7,

. Постановка задачи аналогична задаче 2.2.

Решение.

Так как F1=0 на 0, 2, 3, 4, 6, 7, то F1=1 на 1, 5 (см. таблицу истинности F1):

X1	X2	X3	F1
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

Следовательно, нужно представить F1 в СДНФ

Преобразуем F2:

Используя основные соотношения алгебры логики  можно представить функцию F2 в виде:

Применяя правило склеивания для КНФ ко 2-ой и 4-ой скобкам и к 3-ей и 5-ой скобкам, получим следующее:

Применив склеивание к 1-ой и 3-ей скобке, получим:

 - функции тождественны.

Задача 1.4. Логические функции F1 и F2 заданы таблично (на наборах):

F1 = 0 на наборах: 0, 4, 6, F2 = 1 на наборах: 0, 3, 6, 7. Необходимо получить их минимальную форму записи.

Решение

Представим функцию F1 в СНКФ, а функцию F2 в СДНФ и проведем необходимые преобразования .

Исходя из основных соотношений алгебры логики, представим функцию F1 в виде

.

Применив правило склеивания для 1-ой и 2-ой и для 3-ей и 4-ой скобок:

F1 =

Применив еще раз, правило склеивания, получим окончательный вид функции F1: .

Минимальные формы записи функций:

Задача 1.5. Задана функция F2 аналитически . Необходимо получить таблицу истинности.

Решение

Для построения таблиц истинности необходимо, прежде всего, представить функцию в совершенной форме.

Приведем функцию F2 к совершенной дизъюнктивной форме:

1) Упростим вторую скобку.

2)

Применим правило расширения, чтобы получить СДНФ.

Умножим X1X2 на  и получим:

Эта функция соответствует СДНФ и принимает значение равное 1 на наборах:

Тогда таблица истинности будет выглядеть следующим образом:

X1	X2	X3	F2
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Проверьте

Знаете ли Вы:	Умеете ли Вы:
1.Что такое логические константа и функция? 2.Какие существуют элемен-тарные логические функции? 3.Что такое таблица истинности? 4.Что такое КНФ и ДНФ? 5.Как составлять КНФ и ДНФ? 6.Что такое минимальная форма?	1. Применять соотношения и законы алгебры логики. 2. Упрощать логические функции. 3. Получать минимальную форму для КНФ и ДНФ. 4. Составлять СДНФ и СКНФ.

 

Лекция № 3