ДНФ и импликанты

Сентябрь 12, 2022

Главная
Математика
ДНФ и импликанты

Содержание

2. ДНФ и импликанты Функция f имплицирует функцию g, если . Замечание: Если , то .
3. Импликант Если f имплицирует g, и f представлена единственной элементарной конъюнкцией, то f называется импликантом g.
4. Если функция представима единственной элементарной конъюнкцией – всех n переменных, то ; – m . Теорема
5. Пусть . Она принимает значение 1 тогда и только тогда, когда x = 1, y =
6. Пример Пусть . Она принимает значение 1 тогда и только тогда, когда y = 0, z
7. Утверждение 1 Представление функции в виде ДНФ соответствует представлению ее единичного множества в виде объединения единичных
8. Пример Пусть функция представлена своей ДНФ. . Тогда ее единичное множество может быть представлено в виде:
9. Утверждение 2 Любая конъюнкция ДНФ функции является импликантом данной функции.
10. Утверждение 3 Если конъюнкция ДНФ функции не является простым импликантом, то можно найти соответствующий ей простой
11. Определение ДНФ, состоящая только из простых импликантов, называется сокращенной. .
12. Пример Пусть функция представлена своей ДНФ. Тогда ее единичное множество имеет вид:
13. Пример Очевидно, что – это простой импликант. Он состоит из одной буквы, и если ее вычеркнуть,
14. Пример Проверим, будет ли простым импликант . Вычеркнем из него переменную х.
16. Скачать презентацию

Слайд 2

ДНФ и импликанты
Функция f имплицирует функцию g, если .
Замечание: Если ,

то .

Слайд 3

Импликант
Если f имплицирует g, и f представлена единственной элементарной конъюнкцией,

то f называется импликантом g.
Если из импликанта нельзя удалить ни одной переменной, то оно называется простым импликантом.

Слайд 4

Если функция представима единственной элементарной конъюнкцией
– всех n переменных, то

;
– m < n переменных, то
.

Теорема

Слайд 5

Пусть .
Она принимает значение 1 тогда и только тогда, когда x

= 1, y = 1, z = 1. Значит .

Пример

Слайд 6

Пример
Пусть .

Она принимает значение 1 тогда и только тогда,

когда y = 0, z = 1. Значит, чему равняется переменная х – неважно, и она может принимать любые значения. Поэтому
.

Слайд 7

Утверждение 1
Представление функции в виде ДНФ соответствует представлению ее единичного множества в

виде объединения единичных множеств входящих в эту ДНФ элементарных конъюнкций.

Слайд 8

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

представлено в виде:
Получилось, что

Слайд 9

Утверждение 2
Любая конъюнкция ДНФ функции является импликантом данной функции.

Слайд 10

Утверждение 3
Если конъюнкция ДНФ функции не является простым импликантом, то можно найти

соответствующий ей простой импликант (или импликанты) и заменить им (или их дизъюнкцией) непростой импликант.

Слайд 11

Определение
ДНФ, состоящая только из простых импликантов, называется сокращенной.
.

Слайд 12

Пример
Пусть функция представлена своей ДНФ.
Тогда ее единичное множество имеет вид:

Слайд 13

Пример
Очевидно, что – это простой импликант. Он состоит из одной буквы,

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

Слайд 14

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