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

Урок  17. Функции алгебры логики. Представление БФ формулами.

Опр.1.Функцией алгебры логики  переменных (или функцией Буля) ___________________________________________________________________________________ ________________________________________________________________

Опр.2.Булевой функцией (БФ) f(x1,x2,…,xn) называется ______________________________________________________________________ _________________________________________________________________________

Аргументы БФ принимают значения из {0,1} и сама функция принимает значения из этого же множества {0,1}.

Опр.3.  Двоичной, или булевой переменной называется ____________________________________________________________________ __________________________________________________________________________

Теорема: Всего существует различных функций логики n переменных.

Пример 1:– функция одного переменного. Т.О. существует 4 БФ функции одной переменной

Пример 2: Если  =2, то . Именно столько – 16 существует различных БФ двух переменных. Перечислим их в таблице истинности.

Выразим теперь все эти функции через значения аргументов и.

, , , , , , , , , , , , , , , .

Формулы логики дают нам, по сути, все булевы функции.

Исходя из элементарных функций, можно строить формулы, аналогичные формулам, сформулированным для высказываний: законы и равносильности.

Опр.4.Две БФ называются равным___________________________________________

__________________________________________________________________________

Опр.5. константой 0 наз-ся БФ, которая______________________________________

__________________________________________________________________________

Опр.6. константой 1 наз-ся БФ, которая_______________________________________

__________________________________________________________________________

Для БФ  справедливы равенства, аналогичные формулам, сформулированным для высказываний.  Операции булевой алгебры называются__________________________

 _________________________________________________________________________

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

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

______________________________________________________________________________________________________________________________________________________________________________________________________________________________

Дизъюнктивная нормальная форма.

Элементарной конъюнкцией (ЭК)    n переменных ____________________________

__________________________________________________________________________

Дизъюнктивной нормальной формой (ДНФ) формулы  называется ___________ __________________________________________________________________________

Для любой формулы алгебры логики путем элементарных преобразований можно получить ее ДНФ, причем не единственную (не все формулы в цепочке преобразований будут ДНФ, но многие именно те, которые содержат лишь операции __________________________________________________________________________

Однако среди многих ДНФ лишь одна будет удовлетворять всем условиям совершенства.

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

СДНФ получают прямо из таблицы истинности.

Правило получения СДНФ из формулы  с помощью равносильных преобразований.

______________________________________________________________________________________________________________________________________________________________________________________________________________________________

Конъюнктивная нормальная форма.

Элементарной дизъюнкцией (ЭД)   n переменных ____________________________

__________________________________________________________________________

Конъюктивной нормальной формой (КНФ) формулы  называется _______ __________________________________________________________________________

Здесь ситуация такая же, что и для ДНФ. Для любой формулы  существует несколько КНФ, среди них есть только одна удовлетворяющая условиям совершенства. Эта КНФ называется совершенной конъюктивной нормальной формой (СКНФ).  

СКНФ может быть получена из таблицы истинности для формулы

Правило получения СКНФ из формулы  с помощью равносильных преобразований.

__________________________________________________________________________

____________________________________________________________________________________________________________________________________________________

Проблема разрешимости.

Все формулы алгебры логики делятся на три класса:

1). тавтологии,

2). тождественно ложные,

3). Выполнимые

4). опровержимые.

Вопрос к какому классу формул относится текущая формула  и называется ________________________________________________________

 Эта проблема решается элементарно с помощью таблицы истинности, однако для больших формул таблицы очень громоздки и их использование затруднительно.

Другой способ основан на приведение формулы  к КНФ или ДНФ и использовании специального алгоритма, который позволяет определить является ли данная формула тождественно истинной или не является. Одновременно с этим решается проблема разрешимости.

Урок 18. Двойственность формул. Канонический многочлен Жегалкина.

Опр 1. Булева функция  f * (x,y) называется двойственной по отношению к булевой функции f(x,y),  если_______________________________________________________

Опр 2. Булева функция называется самодвойственной, если ____________________

_________________________________________________________________________

Теорема1 (принцип двойственности):  если , то  

Двойственные операции:

Пример 1. Найти для БФ  двойственную ей и отрицание.

__________________________________________________________________________________________________________________________________________________

Опр 3. Будем говорить, что БФ f(x,y) представлена в виде полинома (многочлена) Жегалкина, ______________________________________________________________

 где  a0,a1,a2,a12,

Если БФ f(x1, x2,…xn), то ее полином (многочлен) Жегалкина имеет вид:

где  a0 ,…,a1..n

Свойства суммы Жегалкина:

Теорема 2: Любую БФ можно представить полиномом Жегалкина, _______________________________________________________________________

Алгоритм представления:

Пример 2. Запишите полином Жегалкина для отрицания БФ примера 1.

_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Урок 19. Тема: Полнота системы БФ. Теорема Поста.

Опр1. Система булевых функций {f1(x,y),f2(x,y),…,fn(x,y)} называется полной, если  любую булеву функцию f(x,y) можно представить в виде______________________

__________f1(x,y),f2(x,y),…,fn(x,y)(т.е._______________________________________)

Опр2. Функция называется суперпозицией функций f1(x,y),f2(x,y),…,fn(x,y), если  f может быть получена с помощью следующих операций:

1. ________________________________________________________________
2. _________________________________________________________________

Пример 1: _________________________________

Пример 2: _________________________________

Опр2.Булева функция f(х,у ) называется  монотонной, если она удовлетворяет условию:________________________________________________________________

Опр3.  Булева функция  f* (x,y) называется двойственной  по отношению к булевой функции f(x,y),  если    

Опр4.  Булева функция называется самодвойственной, если ___________________

________________________________________________________________________

Опр5. Булева функция f(x,y) называется сохраняющей 0, если __________________

________________________________________________________________________

Опр6. Булева функция f(x,y) называется сохраняющей 1, если __________________

________________________________________________________________________

Опр7. БФ называется линейной, если ее логический многочлен Жегалкина имеет степень не выше первой:________________________________________________________

Свойства функций двух переменных.

Полноту системы БФ можно определить по теореме Поста. Для этого определим 5 классов функций:

Т0 – класс функций, сохраняющих 0

Т1– класс  функций, сохраняющих 1

S – класс самодвойственных функций

L – класс линейных функций

M – класс монотонных функций

Теорема Поста.  Для того чтобы система булевых функций {f1(x,y),f2(x,y),…,fn(x,y)} была полной, необходимо и достаточно, чтобы __________

______________________________________________________________________________________________________________________________________________

Система, не являющаяся полной является___________________________________

Пример3:

Определить полноту системы БФ

1. По т . Поста {}={f4,f9}

_________________________________________________________________________

2. С пом. суперпозиции функций:

Урок 21. Минимизация булевых функций

Постановка задачи: Рассмотрим задачу минимизации булевых функций в классе ДНФ.

Задача. Найти ДНФ булевой функции, в которой число входящих букв наименьшее. Такую ДНФ будем называть минимальной ДНФ булевой функции. Отметим, что речь идет о минимальном числе букв, а не переменных, например ДНФ БФ f(x, у, z)=xy  xz содержит четыре буквы, но три переменные (x,y,z). Уменьшить число букв в формуле можно, применяя некоторые равносильности логики высказываний:

1. Kx  К = К - _________________________
2. Кх  К = К - ________________________
3. Kx  Ку = К(ху) - ___________________

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

При минимизации БФ используют различные термины (и обозначения) для полных элементарных конъюнкций (ПЭК). Наиболее часто используются термины «минтерм» и «конституента единицы». (Для ПЭД используются термины «макстерм» и «конституента нуля»). Слово «конституента» означает «составляющая», а название «минтерм» исходит из определения конъюнкции, как минимального значения ее операндов. При этом используются обозначения mi - для минтерма и Mi - для макстерма. Номер i соответствует двоичной записи той оценки переменных, для которой тi=1.

Пример 1:

ПЭК  принимает значение единица на оценке (l,0,0,l), что соответствует двоичной записи числа 910= 10012, поэтому - Такая форма записи удобна для представления СДНФ,

Пример 2:

Часто вместо знака "" используют знак "+" и перечисляют только номера ПЭК, входящих в СДНФ булевой функции:

Последнюю форму записи мы и будем использовать.

Рассмотрим один метод минимизации булевых функций.

Метод карт Карно

Этот метод используется для БФ не более, чем с шестью аргументами и основан на тождестве склеивания: Кх  Кх = К - две ЭК склеиваются, если они отличаются только знаком инверсии одного аргумента. Чтобы облегчить нахождение таких пар (четверок, восьмерок,...) склеивающихся ЭК, используют специальное представление БФ в виде таблицы - карты Карно (другое название - диаграмма Вейча).

Рассмотрим карту Карно для БФ одного аргумента. Таких БФ всего четыре (), а ПЭК имеют вид х и . Карта Карно БФ f(x) состоит из двух клеток, соответствующих этим ПЭК: Причем на карте выделена область, соответствующая вхождению переменной  х в ПЭК в неинверсной форме. Номер клетки - это номер ПЭК:

Аналогично определяется карта Карно для БФ двух аргументов:

Число ПЭК здесь равно четырем: . И на этой карте выделены области вхождения х1, х2 в ПЭК в неинверсной форме. Пересечение этих областей соответствует ПЭК т3=, а ПЭК т0 =  лежит вне выделенных областей.

Для записи в СДНФ булевой функции трех аргументов используют восемь ПЭК, и карта Карно такой БФ имеет вид:

Карта Карно БФ четырех аргументов состоит из 16 клеток.

В таблице представлены возможные значения ПЭК и соответствующие им двоичные числа.   Таблица ПЭК булевой функции четырех аргументов::

Пример 3.

 Составить карты Карно для следующих БФ:

.

Карта Карно обладает той особенностью, что две ПЭК, соответствующие соседним клеткам карты, отличаются знаком инверсии только одного аргумента, т.е. их можно склеивать. Причем соседними являются не только клетки, например, с номерами 1 и 3, но и клетки с номерами 12 и 8, 12 и 4, т.е. карту можно «сворачивать» в цилиндр, соединяя горизонтальные (вертикальные) ее границы.

Какие группы единиц можно объединять, применяя тождество склеивания?

- Группы из двух соседних единиц:

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

Одну и ту же единицу мы можем использовать для склеивания дважды (по закону__________)

-Группы из четырех соседних единиц

В этом случае мы применяем склеивание дважды, и число букв уменьшается на две.

-Группы из восьми соседних единиц:

Урок 22. Схемы из функциональных элементов и конечные автоматы. Переключательные элементы.

Применения БФ связаны с цифровой техникой.

БФ можно рассматривать как мат-кие модели дискретных устройств переработки информации. В процессе работы каждый вход такого устройства может нах-ся только в одном из 2-ух состояний (0 и 1) , и в зависимости от комбинации 0 и 1 на входе устройства получим преобразованную устройством комбинацию 0 и 1 на выходе, при это каждое значение у можно считать функцией от х1, х2,…,хn

Основные логические элементы компьютера

Формальная логика играет большую роль в работе компьютера. Центральная часть процессора так и называется «Арифметико-логическое устройство (АЛУ)». Процессор управляет компьютером по программе, записанной в оперативную память. Команды программы поступают в устройство управления процессора, а оттуда в АЛУ, в котором команды выполняются. Команды раскладываются на простые операции обработки данных: арифметические, логические и др. Арифметической операцией называется обработка данных с использованием сложения, вычитания, умножения, деления и др.

Под логической операцией понимают построение по законам формальной логики сложного высказывания с операциями И, ИЛИ, НЕ и т. д.

Основные логические элементы компьютера —___________________________

_____________________________________________________________________________________________________________________________________________ 

Они применяются для вычислений. Для хранения информации в регистрах и оперативной памяти компьютера, а также во флэш-картах применяют комбинацию логических вентилей, которая называется триггер.

В регистры микропроцессора информация (данные) поступают как из ячеек памяти, так и из внешних устройств. Данные регистров доступны для микропроцессора. Обработка данных происходит в регистрах. Результаты обработки или данные, хранимые в регистрах, можно вывести в любую ячейку оперативной памяти или на внешнее устройство.

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

Логические вентили И, ИЛИ и НЕ

Логические вентили И, ИЛИ имеют по два (или больше) входа и один выход.

Логический вентиль И _________________

___________________________________

___________________________________

____________________________________

__________________________________

Логический вентиль ИЛИ _____________________

____________________________________________

____________________________________________

_________________________________________

Логический вентиль НЕ _______________________

____________________________________________

_____________________________________________________________________________________________________________________

Эти элементы наз-ся _______________________________________________________

 Их можно соединять друг с другом, совмещая выходы некоторых с входами других.

Мат. модель возникающего при этом объекта - _________________________________

_________________________________________________________________________

Переключательные схемы (ПС).

В компьютерах и других автоматических устройствах широко применяются электрические схемы, содержащие сотни и тысячи переключательных элементов: реле, выключателей и т.п. Разработка таких схем весьма трудоёмкое дело. Оказалось, что здесь с успехом может быть использован аппарат алгебры логики.

Переключательная схема — это схематическое изображение некоторого устройства, состоящего из _________________________________________________

____________________________________________________________________________________________________________________________________________________

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

__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Всей ПС также можно поставить в соответствие логическую переменную, равную единице, если схема проводит ток, и равную нулю — если не проводит. Эта переменная является функцией от переменных, соответствующих всем переключателям схемы, и называется ______________________________________.

Найдем функции проводимости F некоторых переключательных схем:

a)    ______________

б)     _________________

в)      __________________

г)    ___________________

д)    ___________________________

е)

   ____________________________

ж) 

   ____________________________

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

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

При рассмотрении переключательных схем возникают две основные задачи: синтез и анализ схемы.

СИНТЕЗ СХЕМЫ по заданным условиям ее работы сводится к след. трём этапам:

1. составлению функции проводимости по таблице истинности, отражающей эти условия;
2. упрощению этой функции;
3. построению соответствующей схемы.

АНАЛИЗ СХЕМЫ сводится к:

1. определению значений её функции проводимости при всех возможных наборах входящих в эту функцию переменных.
2. получению упрощённой формулы.

Пример 1.________________________________

Записать логическую функцию, описывающую состояние логической схемы.

___________________________

Пример 2._________________________________

 По заданной таблице истинности записать логическую функцию (СДНФ). Упростить полученную логическую функцию. Составить логическую схему.

___________________________________________________