Методическая разработка «Булевы функции »

УПРАВЛЕНИЕ ОБРАЗОВАНИЯ И НАУКИ ЛИПЕЦКОЙ ОБЛАСТИ

ГОАПОУ «Липецкий металлургический колледж»

для специальности (группы специальностей):

Липецк-2021

Методические указания по выполнению практических работ по учебной дисциплине ОП 08 «Дискретная математика»

Составитель : Афанасьева Л.Н., преподаватель математических дисциплин

Методические указания по проведению практических работ предназначены для студентов ГОАПОУ «Липецкий металлургический колледж» специальности 09.02.01 Компьютерные системы и комплексы для подготовки к практическим работам с целью освоения практических умений и навыков и профессиональных компетенций.

Методические указания по проведению практических работ составлены в соответствии с рабочей программой учебной дисциплины « Дискретная математика» (дисциплина входит в математический и общий естественнонаучный учебный цикл учебного плана специальности 09.02.01 Компьютерные системы и комплексы по программе базовой подготовки).

Введение

Методические указания по проведению практических работ составлены в соответствии с содержанием рабочей программы учебной дисциплины « Дискретная математика» (дисциплина входит в математический и общий естественнонаучный учебный цикл учебного плана специальности 09.02.01 Компьютерные системы и комплексы по программе базовой подготовки).

Практические работы направлены на освоение следующих практических умений и знаний согласно требованиям ФГОС СПО специальности09.02.01 Компьютерные системы и комплексы, рабочей программы дисциплины « Дискретная математика».

уметь:

-представлять булеву функцию в виде СДНФ и СКНФ

-исследовать функцию на принадлежность к классам

-исследовать булеву функцию на полноту

знать:

-основные классы функций

-полноту множества функций

-теорему Поста

Методические указания по проведению практических работ содержат теоретическую часть, который кратко представляет основной материал, необходимый для освоения коммуникативных умений и знаний; практические задания; контрольные вопросы для самопроверки.

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

Практические работы следует проводить по мере прохождения студентами теоретического материала.

Методические указания к выполнению практической работы для студентов

1. К выполнению практической работы необходимо подготовиться до начала учебного занятия.

2. При подготовке к практической работе используйте рекомендованную литературу, предложенную в данных методических указаниях, конспекты лекций.

3. К выполнению работы допускаются студенты, освоившие необходимый теоретический материал.

4. Студенты обязаны иметь при себе линейку, карандаш, калькулятор, тетрадь.

5. По окончании выполнения практической работы проверьте себя, ответив на контрольные вопросы для самопроверки.

6. Если практическая работа не сдана в указанные сроки (до выполнения следующей практической работы) по неуважительной причине, оценка снижается.

Практическая работа №3

Цель практического занятия:

1.Корректировать знания, умения и навыки по теме:«Представление БФ в виде СДНФ и СКНФ ».

2.Закрепить и систематизировать знания по теме.

Порядок выполнения работы:

1. Усвоить теоретический материал по теме«Представление БФ в виде СДНФ и СКНФ ».

2. Ответить на контрольные вопросы для самопроверки.

3. Выполнить и записать задания практической работы в тетрадь по математике.

4. Сдать выполненную практическую работу на проверку преподавателю.

Теоретическая часть:

Определение 1. Пусть– булевы переменные. Формулы алгебры высказываний вида

… (1)

..., (2)

..., (3)

Где и для каждого i ,

,называются соответственно элементарно конъюнкцией, элементарной дизъюнкцией, монотонной конъюнкцией на множестве переменных .

Определение 2. Дизъюнктивный нормальной формой (ДНФ) называется формула алгебры высказываний, представляющая собой дизъюнкцию различных элементарных конъюнкций.

Определение 3. Конъюнктивной нормальной формой (КНФ) называется формула алгебры высказывания, представляющая собой конъюнкцию различных элементарных дизъюнкций.

Теорема 1. Для каждой булевой функции, отличной от тождественной нуля, существует и единства единственно (с точностью до порядка слагаемых) следующее представление в виде дизъюнктивной нормальной формы:

(4)

В дальнейшем для сокращения записи формул знак конъюнкции () в (1) , (2), (4) будем опускать.

Дизъюнктивная нормальная форма (4) называется совершенной (СДНФ).

Теорема 2. Для каждой булевой функции, отличной от тождественной единицы, существует и единственно (с точностью до порядка сомножителей) следующие представление в виде конъюнктивной нормальной формы:

(5)

Конъюнктивная нормальная форма (5) называется совершенной (СКНФ).

Алгоритм построения СДНФ (с использованием таблиц истинности ) :

Построить таблицу истинности данной функции ;

В таблице выделить наборы, на которых функция принимает значение 1;

Каждому такому набору поставить в соответствие элементарную конъюнкцию

;(7)

Найденные элементарные конъюнкции объединить знаком дизъюнкции

Полученная формула является совершенной дизъюнктивной, нормальной формой функции f.

Алгоритм построения СКНФ (с использованием таблиц истинности ):

Построить таблицу истинности данной функции f;

В таблице выделить наборы, на которых функция принимает значение 0;

Каждому такому набору поставить в соответствие элементарную дизъюнкцию вида:

… (8)

Найденные элементарные дизъюнкции объединить знаком конъюнкции

Полученная формула, является совершенной конъюнктивной нормальной формой функцииf.

Пример 1.1. Построить СДНФ, СКНФ и ПЖ для функции

c использованием таблицы истинности

Построим таблицу истинности для данной функции:

Из таблицы следует, что функция принимает значение 1 на наборах : (0,0,0), (0,1,0), (1,0,1), которым соответствует элементарные конъюнкции: ,дизъюнкция этих конъюнкций есть СДНФ данной функции:

СДНФ=.

Для построения СКНФ выделим те наборы , на которых функция принимает значение 0: (0,0,1), (0,1,1), (1,0,0), (1,1,0), (1,1,1). Им соответствуют элементарные дизъюнкции :; конъюнкция этих дизъюнкций является СКНФ данной функции:

СКНФ=

.

Контрольные вопросы для самопроверки:

Дайте определение ДНФ?

Дайте определение КНФ?

Что такое СДНФ и СКНФ?

Задание для выполнения практических работ

Практическая работа №4

Цель практического занятия:

1.Корректировать знания, умения и навыки по теме: «Важнейшие замкнутые классы. Теорема поста. Исследование БФ на принадлежность к классам ».

2.Закрепить и систематизировать знания по теме.

Порядок выполнения работы:

1. Усвоить теоретический материал по теме«Важнейшие замкнутые классы. Теорема поста. Исследование БФ на принадлежность к классам ».

2. Ответить на контрольные вопросы для самопроверки.

3. Выполнить и записать задания практической работы в тетрадь по математике.

4. Сдать выполненную практическую работу на проверку преподавателю.

Теоретическая часть:

Обозначим через Б множество всех булевых функций.

Определение 1.Замыканием множества М ⊆Бназывается множество суперпозиций, которые можно построить из функций множества М.

Определение 2. Класс (множество) булевых функций называетсязамкнутым, если он совпадает со своим замыканием.

Определение 3. Система ( множество) булевых функций называетсяполнойвБ, если ее замыкание совпадает с множеством всех булевых функций.

Определение 4. Система (множество) булевых функций называетсябазисом, если она полна и любая подсистема не является полной в Б.

Основные замкнутые классы:

1) Класс Т0функций, сохраняющих константу 0:

Т0={f∈ Б| f ( 0,0,…, 0) = 0} ;

2) Класс Т1функций, сохраняющих константу 1:

Т1={f∈ Б| f (1,1,…,1)= 1};

3) Класс Sсамодвойственных функций:

S = { f∈Б|f (x1,x2,…,xn) = f( x1, x2, …, xn)} ;

4)КлассMмонотонныхфункций:

M = {f∈Б|f(α₁,α₂,…,α_n)≤f(β₁,β₂,…,β_n),

Еслиα₁≤β₁,α₂≤β₂,…,α_n≤β_n};

5)КлассLлинейныхфункций:

L= { f∈Б|f (x1,x2,…,xn)=α₀α₁x₁…α_nx_n

Теорема 4. (Критерий ПОСТА).Для того чтобы система булевых функций F={f₁,f₂…} была в полной в Б, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из замкнутых классовT₀ , T₁,S , M , L.

Алгоритм решения задачи о принадлежности функцииf

классамT₀ , T₁,S , M , L.

Построить таблицу истинности функции f;

Если значение функции в первой строке таблицы равно 0 (f(0,0,…,0)=0), то f∈T₀ , иначе f∉T₀;

Если значение функции в последней строке таблицы равно 1 1 (f(1,1,…,1)=1), то f∈T₁ , иначе f∉T₁;

Если в таблице истинности можно указать пару противоположных выборов (α₁,α₂,…,α_n) и (ā₁, ā₂,…, ā_n), на которых функция f принимает одинаковые значения(f(α₁,α₂,…,α_n) = f(ā₁, ā₂,…, ā_n)), то f∉S, иначе f∈S;

Если в таблице истинности можно указать наборы (α₁,α₂,…,α_n) и (β₁,β₂,…,β_n), такие чтоα₁≤β₁,α₂≤β₂,…,α_n≤β_nиf(α₁,α₂,…,α_n)=1,f(β₁,β₂,…,β_n)=0, то f∉M ,иначе f∈M;

Для проверки принадлежности функции fклассуL нужно построить ее полином Жегалкина; Если степень ПЖ не превосходит 1

(α₁₂=α₁₃=…=α_12…n=0), то f∈L,иначеf∉L.

2.3 Примеры решения задач

Пример 1. Для функции f=(x۸ȳ)→(xz), определить ее принадлежность к каждому из классов T₀ , T₁,S , M , L.

Построим таблицу истинности

Из анализа построенной таблицы следует:

f∈T₀,так какf(0,0,0)=1;

f∈T₁, так как f(1,1,1)=1

f∈S, так как f(1,1,0)=f(0,0,1)

f∈M, так как f(0,0,0)=f(0,1,0)=0

Для определения принадлежности функцииfклассуL, построим ПЖ. Система уравнений для неопределенных коэффициентов имеет вид:

α₀ = 1,

α₀α₃ = 1,

α₀α₂ = 1,

α₀α₁ = 1,

α₀α₂α₃α₂₃ = 1,

α₀α₁α₂α₁₂= 1,

α₀α₁α₃α₁₃ =0,

α₀α₁α₂α₃α₁₂α₁₃α₂₃α₁₂₃= 1.

Откуда находим : α_{1 =} α₂=α_{3 =} α₁₂=α_{23 = 0,} α_{0 =} α_{13 =} α_{123 = 1;
ПЖ=xyzxz 1.}Следовательно,f ∉ L.

Контрольные вопросы для самопроверки:

1. Какой класс называется замкнутым?

2.Когда система булевых функций является полной?

3.Сформулируйте теорему Поста?

Задание для выполнения практических работ

Практическая работа №5

Цель практического занятия:

Корректировать знания, умения и навыки по теме:«Исследование системы БФ на полноту ».

Закрепить и систематизировать знания по теме.

Порядок выполнения работы:

1. Усвоить теоретический материал по теме«Исследование системы БФ на полноту ».

2. Ответить на контрольные вопросы для самопроверки.

3. Выполнить и записать задания практической работы в тетрадь по математике.

4. Сдать выполненную практическую работу на проверку преподавателю.

Теоретическая часть:

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

1) построить таблицу ,число строк в которой равно числу функций в F , а число столбцов равно 5 по числу основных замкнутых классов ;

2) проверить принадлежность функции f₁ и Т₀строки и столбца знак "+", если f₁€ Т_0; и знак "-", если F₁ € Т;

3) если на предыдущем шаге в результате исследования получен знак "+",то продолжить исследование по "вертикале" - проверить принадлежность функции f₂ классу Т₀ и т.д., если же на предыдущем шаге получен знак "-", то продолжить исследование по "горизонтали"- проверить принадлежность функции f₁классу Т₁ и т.д.,;

4) исследование заканчивается ,если выполнено одно из двух условий:

1.в каждом столбце таблицы стоит по крайней мере один знак "-", либо

2. в одном из столбцов таблицы стоят только знаки "+".

5) В первом случае система функций F целиком не содержится ни в одном из классов и, согласно критерию Поста, является полной, во втором случае она целиком содержится в одном из классов и потому не является полной.

6) Для выделения базиса из полной системы функций нужно упорядочить по числу функций множество подсистем системыF:

{f₁}, {f₂}, ..., {f₁,f₂}, ... ,

и, начиная с первой ,исследовать их на полноту. Первая из полных в последовательности (19) систем базисом на множестве всех булевых функций.

Пример. Исследовать полноту системы функций F = {⊕ y ;x /\ yz; y→ } и, если она полна выделить из нее базис.

В соответствии с формулированным выше алгоритмом решение состоит из следующих шагов:

f₁ (0,0)=⊕ 0 = 1,⇒f₁ ∉ Т₀;

f₁ (1,1)=⊕ 1=1,⇒f₁ ∈ Т₁;

f₂ (1,)=1/\0 = 1,⇒f₂ ∈ Т₁;

f₃(1,1)=1→=0⇒f₃∉Т₁.

Посмотри таблицу истинности функции f₃:

Из таблицы следует f₃ (0,1)=f₃ (1,0), поэтому функция f₃ ∉ S .Далееf₃(0,0)=1,f₃ (1,1)=0,поэтому функция f₃ ∉ М.

Построим полином Жегалкина для функции f₃ :

f₃(х,y) = y→= \/ =()= х y⊕ 1 = ПЖ ,

откуда следует f₃∉L , так как степень полинома Жегалкина равна 2 .По результатам исследований построим таблицу

В каждом столбце таблицы стоит знак"-" , откуда следует ,что данная система является полной . Каждая из функций f₁иf₂и обе они вместе не могут быть базисом в Б , так как принадлежит классу Т₁. Функция f₃ является базисом ,так как в дополнение к проведенному анализу f₃(0,0)=1 и f₃∉Т₀ .

Ответ : системаF полна ;функция {f₃} является базисом на множестве всех булевых функций.

Контрольные вопросы для самопроверки:

1.Какая функция является полной?

2 .Сформулируйте алгоритм исследования полноты?

Задание для выполнения практических работ