оп. Представление булевой функции в виде сднф и скнф, минимальной днф и кнф

Название	Представление булевой функции в виде сднф и скнф, минимальной днф и кнф
Дата	26.05.2022
Размер	371.8 Kb.
Формат файла
Имя файла	Prakticheskaya_rabota__4_-_Predstavlenie_bulevoi_774_funktsii_v_.pdf
Тип	Практическая работа #550325

ПРАКТИЧЕСКАЯ РАБОТА № 4
Тема: Представление булевой функции в виде СДНФ и СКНФ, минимальной ДНФ и
КНФ.
Цель работы: овладеть навыкамисоставления СДНФ функций алгебры логики.
Задание:
Выполните задание согласно варианту.
1 вариант
1. Найдите СДНФ для данной формулы c помощью таблицы истинности:
2. Применяя равносильные преобразования, найдите СДНФ для данной формулы:
3. Применяя равносильные преобразования, найдите СКНФ для данной формулы
4. Построить таблицу истинности для функции


, .
(
)
f x y z
ху
z x

 
, найти СДНФ, упростить ее. Представить функцию в виде многочлена Жегалкина.
2 вариант
1. Найдите СДНФ для данной формулы c помощью таблицы истинности:
2. Применяя равносильные преобразования, найдите СДНФ для данной формулы:
3. Применяя равносильные преобразования, найдите СКНФ для данной.
4. Построить таблицу истинности для функции


, .
f x y z
х
у
z
  
, найти СДНФ, упростить ее. Представить функцию в виде многочлена Жегалкина.
3 вариант
1. Найдите СДНФ для данной формулы c помощью таблицы истинности:
2. Применяя равносильные преобразования, найдите СДНФ для данной формулы:
3. Применяя равносильные преобразования, найдите СКНФ для данной формулы:
4. Построить таблицу истинности для функции


, .
f x y z
х у
z
  
, найти СДНФ, упростить ее. Представить функцию в виде многочлена Жегалкина.


A
B
B
A



)
(
_______


_______
(
)
A
B
A
A
B












B
A
A
B
A










)
(
_______

4 вариант
1. Найдите СДНФ для данной формулы c помощью таблицы истинности:
2.Применяя равносильные преобразования, найдите СДНФ для данной формулы:
3. Применяя равносильные преобразования, найдите СКНФ для данной формулы:
4. Построить таблицу истинности для функции


, .
f x y z
х у z
 
, найти СДНФ.
Представить функцию в виде многочлена Жегалкина.
5 вариант
1. Найдите СДНФ для данной формулы c помощью таблицы истинности:
2. Применяя равносильные преобразования, найдите СДНФ для данной формулы:
3.Применяя равносильные преобразования, найдите СКНФ для данной формулы:
4. Построить таблицу истинности для функции


, .
f x y z
xz
х у

 
, найти СДНФ, упростить ее. Представить функцию в виде многочлена Жегалкина.
6 вариант
1. найдите СДНФ для данной формулы c помощью таблицы истинности:
2. Применяя равносильные преобразования, найдите СДНФ для данной формулы:
3. Применяя равносильные преобразования, найдите СКНФ для данной формулы:
4. Построить таблицу истинности для функции


, .
f x y z
х
у
z
  
, найти СДНФ, упростить ее. Представить функцию в виде многочлена Жегалкина.
7 вариант
1. Найдите СДНФ для данной формулы c помощью таблицы истинности:
2. Применяя равносильные преобразования, найдите СДНФ для данной формулы:
3. Применяя равносильные преобразования, найдите СКНФ для данной формулы:
4. Построить таблицу истинности для функции


, .
f x y z
х у
z
  
, найти СДНФ, упростить ее. Представить функцию в виде многочлена Жегалкина.

 

z
y
z
x




 

x
z
y
x







y
z
y
x







A B
B
A
  

8 вариант
1. Найдите СДНФ для данной формулы c помощью таблицы истинности:
2. Применяя равносильные преобразования, найдите СДНФ для данной формулы:
3. Применяя равносильные преобразования, найдите СКНФ для данной формулы:
4. Построить таблицу истинности для функции


, .
(
)
f x y z
ху
z x

 
, найти СДНФ, упростить ее. Представить функцию в виде многочлена Жегалкина.
9 вариант
1. Найдите СДНФ для данной формулы c помощью таблицы истинности:
2. Применяя равносильные преобразования, найдите СДНФ для данной формулы:
3. Применяя равносильные преобразования, найдите СДНФ для данной формулы:
4. Построить таблицу истинности для функции


, .
f x y z
х у z
 
, найти СДНФ.
Представить функцию в виде многочлена Жегалкина.
10 вариант
1. Найдите СДНФ для данной формулы c помощью таблицы истинности:
2. Применяя равносильные преобразования, найдите СДНФ для данной формулы:
3. Применяя равносильные преобразования, найдите СДНФ для данной
4. Построить таблицу истинности для функции


, .
f x y z
xz
х у

 
, найти СДНФ, упростить ее. Представить функцию в виде многочлена Жегалкина.
Контрольные вопросы:

1. Что такое СДНФ, СКНФ?
2. Что такое формула?

3. Что такое таблица истинности?
4. Правила построения СДНФ, СКНФ?

5. Что такое многочлен Жегалкина?
6. Какой многочлен Жегалкина называется линейным?
7. Алгоритм представления Булевых функций в виде многочлена Жегалкина.


 
x
y
x
z


A B
A
A


 







 


x
z
y
x



Теоретические сведения и примеры решения задач:
Совершенная дизъюнктивная нормальная форма (СДНФ) – это такая ДНФ, которая удовлетворяет трём условиям:

в ней нет одинаковых элементарных конъюнкций;

в каждой конъюнкции нет одинаковых пропозициональных букв;

каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причём в одинаковом порядке.
Для любой функции алгебры логики существует своя СДНФ, причём единственная.
Пример нахождения СДНФ:
Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности.
X
1
X
2
X
3
𝑓(𝑥
1
, 𝑥
2
, 𝑥
3
)
0 0
0 1
0 0
1 1
0 1
0 1
1 0
1 0
1 1
0 0
0 1
1 0
1 1
0 1
1 1
1 0
В ячейках результата
𝑓(𝑥
1
, 𝑥
2
, 𝑥
3
) отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы. Далее рассматриваются значения переменных при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.
Первая строка содержит 1 в указанном поле. Отмечаются значения всех четырёх переменных, это:
𝑥
1
= 0, 𝑥
2
= 0, 𝑥
3
= 0
Нулевые значения – тут все переменные представлены нулями – записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так:
𝑥
1
̅̅̅̅ ∙ 𝑥
2
̅̅̅ ∙ 𝑥
3
̅̅̅
Переменные второго члена:
𝑥
1
= 0, 𝑥
2
= 0, 𝑥
3
= 1
𝑥
3
в этом случае будет представлен без инверсии:
𝑥
1
̅̅̅̅ ∙ 𝑥
2
̅̅̅ ∙ 𝑥
3
Таким образом анализируются все ячейки
𝑓(𝑥
1
, 𝑥
2
, 𝑥
3
). Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов (элементарных конъюнкций).
Совершенная ДНФ этой функции:
𝑓(𝑥
1
, 𝑥
2
, 𝑥
3
) = 𝑥
1
̅̅̅̅ ∙ 𝑥
2
̅̅̅ ∙ 𝑥
3
̅̅̅ ∨ 𝑥
1
̅̅̅̅ ∙ 𝑥
2
̅̅̅ ∙ 𝑥
3
∨ 𝑥
1
̅̅̅̅ ∙ 𝑥
2
∙ 𝑥
3
̅̅̅ ∨ 𝑥
1
∙ 𝑥
2
∙ 𝑥
3
̅̅̅
Совершенная конъюнктивная нормальная форма (СКНФ) – это такая КНФ, которая удовлетворяет трём условиям:

в ней нет одинаковых элементарных дизъюнкций;

в каждой дизъюнкции нет одинаковых пропозициональных переменных;

каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.
Пример нахождения СКНФ:
Для того, чтобы получить СКНФ функции, требуется составить её таблицу истинности.
X
1
X
2
X
3
𝑓(𝑥
1
, 𝑥
2
, 𝑥
3
)
0 0
0 1
0 0
1 1
0 1
0 1
1 0
1 0
1 1
0 0

0 1
1 0
1 1
0 1
1 1
1 0
В ячейках строки́ 𝑓(𝑥
1
, 𝑥
2
, 𝑥
3
)отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля.
Четвёртая строка содержит 0 в указанном поле. Отмечаются значения всех четырёх переменных, это:
𝑥
1
= 1, 𝑥
2
= 0, 𝑥
3
= 1
В дизъюнкцию записывается переменная без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так:
𝑥
1
̅̅̅̅ ∨ 𝑥
2
∨ 𝑥
3
̅̅̅
Остальные члены СКНФ составляются по аналогии.
Совершенная KНФ этой функции:
𝑓(𝑥
1
, 𝑥
2
, 𝑥
3
) = (𝑥
1
̅̅̅̅ ∨ 𝑥
2
∨ 𝑥
3
̅̅̅) ∙ (𝑥
1
̅̅̅̅ ∨ 𝑥
2
̅̅̅ ∨ 𝑥
3
) ∙ (𝑥
1
∨ 𝑥
2
̅̅̅ ∨ 𝑥
3
̅̅̅) ∙ (𝑥
1
̅̅̅̅ ∨ 𝑥
2
̅̅̅ ∨ 𝑥
3
̅̅̅)
Многочленом Жегалкина называется альтернативная дизъюнкция, каждый член которой представляет собой конъюнкцию переменных или переменные, или 1. Любая функция может быть представлена многочленом (полиномом) Жегалкина и это представление единственно. Функция является линейной, если многочлен Жегалкина не содержит конъюнкции переменных.
Пример:
Записать булеву функцию




, ,
(
)
f x y z
x
y
z
x




в виде многочлена
Жегалкина. Определить является ли функция линейной.
Решение:
Преобразуем равенство, используя формулы алгебры логики.










(
)
` (
)
1
(
)
1
(
)
1 1
1 1
1 1
1
x
y
z
x
xy
x
y
z
x
xy
x
y
z
x
xy
x
y
xyz
xyx
xy
xz
x
x
yz
yx
y
xy
x
y
xz y
xy
xy
xz
y
z
y
x
y
xyz
xz
xz
yz
z
x
xyz
yz
z
x




 

  

 
  
 
 




  

 
 
  
 




  
  



   

  
Функция не является линейной, т.к. многочлен Жегалкина содержит конъюнкции переменных.
Многочлен Жегалкина, соответствующий данной функции:


; ;
1
f x y z
xyz
yz
z
x


  