Презентация "Минимизация булевых функций в классе дизъюнктивных нормальных форм" 10 класс

Подписи к слайдам:
Минимизация булевых функций в классе дизъюнктивных нормальных форм

Дж. Буль (1815-1864)

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

Что такое булева функция?

Область определения и множество значений булевой функции?

Как их еще называют?

Назовите способы задания

логических функций?

Какие булевы функции вы знаете?

С помощью каких операций можно выразить любую логическую функцию и зачем это нужно?

Назовите алгоритм построения СДНФ по таблице истинности.

x

y

F

0

0

1

0

1

1

1

0

0

1

1

0

x

y

f

0

0

1

0

1

1

1

0

0

1

1

1

x

y

z

F1

F2

0

0

0

1

0

0

0

1

1

1

0

1

0

0

0

0

1

1

0

0

1

0

0

0

1

1

0

1

0

1

1

1

0

0

1

1

1

1

1

0

метод минимизирующих карт.

X1

X2

….

X1 X2

X1 X3

….

X1 X2…Xn-1Xn

X1

X2

….

X1 X2

X1 X3

….

X1 X2…Xn-1 Не Xn

X1

X2

….

X1 X2

X1 X3

….

X1 X2… Не Xn-1 Xn

….

….

….

….

….

….

….

Не X1

Не X2

….

Не X1 Не X2

Не X1 Не X3

….

Не X1 Не X2… Не Xn-1 Не Xn

  • Строим минимизирующую карту.
  • Вычеркнем из таблицы (минимизируюшей карты) все строки, в которых конъюнкция последнего столбца не входит в СДНФ функции.
  • Конъюнкции «вычеркнутых строк» вычеркнем во всех остальных строках таблицы.
  • Если в строке остались конъюнкции с различным числом сомножителей, то конъюнкции с не минимальным числом сомножителей оставляем только тогда, когда они встречаются в других строках.
  • Отметим конъюнкции, оставшиеся единственными на строке. Вычеркнем строки, в которых присутствуют такие же конъюнкции.
  • Взяв по одной конъюнкции для всех не зачёркнутых строк и записав их дизъюнкцию, получают минимальную форму.

x

y

z

F1

0

0

0

1

0

0

1

1

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

x

y

z

xy

xz

yz

xyz

x

y

не z

xy

x не z

y не z

xy не z

x

не y

z

x не y

xz

не yz

x не yz

x

не y

не z

x не y

x не z

не y не z

x не y не z

не x

y

z

не xy

не xz

yz

не xy z

не x

y

не z

не xy

не x не z

y не z

не xy не z

не x

не y

z

не x не y

не xz

не yz

не x не yz

не x

не y

не z

не x не y

не x не z

не y не z

не x не y не z

x

y

z

xy

xz

yz

xyz

x

y

не z

xy

x не z

y не z

xy не z

x

не y

z

x не y

xz

не yz

x не yz

x

не y

не z

x не y

x не z

не y не z

x не y не z

не x

y

z

не xy

не xz

yz

не xy z

не x

y

не z

не xy

не x не z

y не z

не xy не z

не x

не y

z

не x не y

не xz

не yz

не x не yz

не x

не y

не z

не x не y

не x не z

не y не z

не x не y не z

F(x,y,z)=xyнеz+xнеyz+xнеyнеz+неxнеyz

F(x,y,z)=неxнеyнеz+неxyнеz+неxyz+xyнеz+xyz

Домашнее задание:

учить основные понятия лекции, минимизировать логические функцию (F(x,y,z)= xyнеz+xнеyz+xнеyнеz+неxyнеz+неxнеyz+неxyz), выполнить заготовки для практической работы.