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

1.

Способы представления
логических функций
Лунев Сергей Александрович

2.

2
Дискретная математика
Цель работы: научиться по цифровой записи
функции строить таблицу истинности,
временную
диаграмму,
совершенные
дизъюнктивную
и
конъюнктивную
нормальные формы логической функции

3.

Порядок выполнения задания
1. Получить индивидуальное задание на практическое занятие.
2. По индивидуальному заданию составить таблицу истинности, доопределить
безразличия и построить временные диаграммы полученных четырех функций.
3
3. Построить СДНФ полученных четырех функций на основе следующего алгоритма
3.1. Выделить комбинации в таблице истинности, на которых функция равна 1
(минтермы).
3.2. Для каждой выделенной комбинации составить логическое произведение
независимых переменных, из которых она образована, причем если в комбинации
значение переменной равно 0, то в логическое произведение эта переменная входит с
инверсией, если в комбинации значение переменной равно 1, то в логическое
произведение эта переменная входит без инверсии.
3.3. Формула функции образуется путем логического сложения полученных
логических произведений (минтермов).
Дискретная математика

4.

4
4. Построить СКНФ полученных четырех функций на основе следующего алгоритма
4.1. Выделить комбинации в таблице истинности, на которых функциSя равна 0
(макстермы).
4.2. Для каждой выделенной комбинации составить логическое сложение независимых
переменных, из которых она образована, причем если в комбинации значение
переменной равно 0, то в логическое сложение эта переменная входит без инверсии,
если в комбинации значение переменной равно 1, то в логическое сложение эта
переменная входит с инверсией.
4.3. Формула функции образуется путем логического умножения полученных
логических сложений (макстермов).
Дискретная математика

5.

Пример выполнения работы
Исходные данные:
f={1, 4, 5, 7 (0, 6)}x, y, z
Составим таблицу истинности заданной функции:
Номер комбинации
x
y
z
f
0
0
0
0
~
1
0
0
1
1
2
0
1
0
0
3
0
1
1
0
4
1
0
0
1
5
1
0
1
1
6
1
1
0
~
7
1
1
1
1
5
Дискретная математика
На наборах аргументов 1, 4, 5, 7 логическая
функция f трех переменных x, y, z
принимает значения «1», на наборах 0, 6
функция f принимает значение «~»
(безразличие). Следовательно, на наборах 2,
3 функция принимает значение «0».
Учитывая это, заданную функцию можно
представить в числовом виде иным
способом:
f={1, 4, 5, 7 / 2, 3)}x, y, z

6.

Номер
комбинации
x
y
z
f
f1 f2 f3 f4
0
0
0
0
~
0
1
0
1
6
1
1
0
~
0
0
1
1
Доопределим безразличия следующим
образом:
По результатам доопределения безразличий получим четыре логических функции f1, f2, f3, f4:
Номер комбинации
x
y
z
f
f1
f2
f3
f4
0
0
0
0
~
0
1
0
1
1
0
0
1
1
1
1
1
1
2
0
1
0
0
0
0
0
0
3
0
1
1
0
0
0
0
0
4
1
0
0
1
1
1
1
1
5
1
0
1
1
1
1
1
1
6
1
1
0
~
0
0
1
1
7
1
1
1
1
1
1
1
1
6
Дискретная математика
Запишем полученные функции
в числовой форме:
f1={1, 4, 5, 7}x, y, z
f2={0, 1, 4, 5, 7}x, y, z
f3={1, 4, 5, 6, 7}x, y, z
f4={0, 1, 4, 5, 6, 7}x, y, z

7.

Представление логической функции
временной диаграммой
7
Номер
комбинации
x
y
z
f1
0
0
0
0
0
1
0
0
1
1
2
0
1
0
0
3
0
1
1
0
4
1
0
0
1
5
1
0
1
1
6
1
1
0
0
7
1
1
1
1
Дискретная математика
Значения аргументов функции:
Значения функции f1:
Номера наборов функции:
«1»
«0»
x
y
z
f1
t
0
1
2
3
4
5
6
7
Временные диаграммы для функций f2, f3, f4 строятся
аналогично

8.

Построение СДНФ заданной логической функции
001
8
0
1
2
3
4
5
6
7
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
Дискретная математика
z f1
0 0
1 1
0 0
1 0
0 1
1 1
0 0
1 1
100
101
111
Построение СДНФ функций f2, f3, f4
выполняется аналогично

9.

Построение СКНФ заданной логической функции
000
9
0
1
2
3
4
5
6
7
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
Дискретная математика
z f1
0 0
1 1
0 0
1 0
0 1
1 1
0 0
1 1
010
011
110
Построение СКНФ функций f2, f3, f4
выполняется аналогично