close

Вход

Забыли?

вход по аккаунту

?

Совершенная дизъюнктивная нормальная форма

код для вставкиСкачать
Совершенная дизъюнктивная нормальная форма
§
32, 3
-
6
Алгоритм построения логической формулы по таблице истинности Дана таблица истинности некоторой функции. Для построения формулы необходимо выполнить
следующую последовательность шагов: •
Выбрать все строки таблицы, в которых функция принимает значение 1. •
Каждой такой строке поставить в соответствие конъюнкцию всех аргументов или их инверсий. При этом аргумент, принимающий значение 0, входит в конъюнкцию с отрицанием, а значение 1 –
без отрицания. •
Наконец, образуем дизъюнкцию всех полученных конъюнкций. Количество конъюнкций должно совпадать с количеством единиц логической функции. Выбираем все строки таблицы, в которых функция принимает значение 1...
A
B
C
F(A,
B, C)
0
0
0
1
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
0
A
B
C
F(A,
B, C)
¬
A
¬
B
¬
C
1
¬A
B
C
1
A
¬B
C
1
A
B
¬
C
1
Каждой такой строке поставить в соответствие конъюнкцию всех аргументов или их инверсий. При этом аргумент, принимающий значение 0, входит в конъюнкцию с отрицанием, а значение 1 –
без отрицания...
¬
A&
¬
B
&
¬
C
¬
A&B&C
A&
¬
B&C
A&
¬
B&C
V
V
V
=
F(A, B, C)
Особенности полученного выражения
•
Используются только операции &, V, ¬
;
•
Отрицание применяется только к переменным;
•
Конъюнкцией соединены переменные или их отрицания;
•
Каждая переменная в конъюнкции входит только один раз;
•
Конъюнкции соединены дизъюнкциями.
Выражение, удовлетворяющее таким признакам, называется совершенной дизъюнктивной нормальной формой (
СДНФ
)
Упрощение полученного выражения
Упростить полученное выражение можно по правилам:
•
(
a
& b
& c
)
V
(
a
& ¬
b
& c
) = a
& c
(
a
& b
)
V
(
a
& ¬
b
) = a
(
b
& c
) (
¬
b
& c
) = c
•
То есть, если в СДНФ обнаруживаются две скобки, которые отличаются только знаком ¬
перед одним из элементов, их можно заменить на одну скобку, в которой этого элемента нет.
•
Например, f(x,y,z) = (
¬
x & y & z) (x & ¬
y & ¬
z) (x & y & ¬
z)
=
(
¬
x & y & z) (x & ¬
z)
Алгоритм построения СКНФ по таблице истинности Дана таблица истинности некоторой функции. Для построения СКНФ необходимо выполнить следующую последовательность шагов: •
Выбрать все строки таблицы, в которых функция принимает значение 0. •
Каждой такой строке поставить в соответствие дизъюнкцию всех аргументов или их инверсий. При этом аргумент, принимающий значение 1, входит в дизъюнкцию с отрицанием, а значение 1 –
без отрицания. •
Наконец, образуем конъюнкцию всех полученных дизъюнкций. Количество конъюнкций должно совпадать с количеством нулей логической функции. Если условиться из двух форм (СДНФ или СКНФ) отдавать предпочтение той, которая содержит меньше букв, то СДНФ предпочтительней, если среди значений функции таблицы истинности меньше единиц, СКНФ –
если меньше нулей.
Автор
zukovaivik
Документ
Категория
Презентации
Просмотров
1 789
Размер файла
54 Кб
Теги
дизъюнктивная, нормальная, формы, совершенный
1/--страниц
Пожаловаться на содержимое документа