6. Булевы функции Основные определения и понятия темы
Булева функция одной переменной, виды булевых функций одной переменной (отрицание, тождественный 0, тождественная 1, тождественная функция), булева функция двух переменных, виды булевых функций двух переменных (конъюнкция, дизъюнкция, импликация, эквиваленция, сумма Жегалкина, стрелка Пирса, штрих Шеффера), булева функция nпеременных, равносильные булевы функции, суперпозиция булевых функций, совершенная конъюнктивная форма булевой функции, совершенная дизъюнктивная форма булевой функции, булева функция, сохраняющая 1, булева функция, сохраняющая 0, двойственная булева функция, самодвойственная булева функция, полином Жегалкина, линейная булева функция, монотонная булева функция, полная система булевых функций.
Основные теоремы и утверждения темы
Теорема о числе булевых функций nпеременных, основные равносильности булевых функций, теорема о разложении любой булевой функции в суперпозицию конъюнкции, дизъюнкции и отрицания, отнесенного к атому, алгоритмы построения СДНФ и СКНФ с помощью таблицы истинности, алгоритм построения полинома Жегалкина методом неопределенных коэффициентов, критерий полноты системы булевых функций.
Рекомендуемая литература
Конспект лекций О.Б. Лупанова по курсу «Введение в математическую логику». – М.: Изд-во ЦПИ при механико-математическом факультете МГУ им. М.В. Ломоносова. – 2007.
Игошин В.И. Задачник-практикум по математической логике. М.: Просвещение, 1986.
С.В. Судоплатов, Е.В. Овчинникова. Элементы дискретной математики. – Москва – Новосибирск, 2002.
Задание 6.1. Проверить эквивалентность булевых функций двумя способами:
с помощью таблицы истинности;
с помощью равносильных преобразований.
и
;
и
;
и
;
и
;
и
;
и
;
и
;
и
;
и
;
и
;
и
;
и
;
и
;
и
;
и
;
и
;
и
;
и
;
и
;
и
.
Задание 6.2. Найти СДНФ и СКНФ булевой функции двумя способами:
с помощью таблицы истинности;
с помощью равносильных преобразований.
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
.
Задание 6.3. Построить полином Жегалкина для булевой функции методом неопределенных коэффициентов. Является ли данная функция линейной?
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
.
Задание
6.4. Построить
функцию, двойственную к булевой функции
.
Проверить, эквивалентна ли полученная
формула функции
.
;
;
;
;
;
,
;
;
;
;
;
;
;
;
;
;
;
;
;
;
.
Задание 6.5. Выяснить, является ли булева функция монотонной.
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
.
Задание 6.6. Проверить, является ли полной система булевых функций (полином Жегалкина находить с помощью эквивалентных преобразований).
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
;
.
Задание 6.7. Упростить релейно-контактную схему. Найти ее функцию проводимости.
Задание 6.8.
Построить наиболее простую релейно-контактную схему с тремя переключателями, которая должна проводить электрический ток тогда и только тогда, когда выполнено по меньшей мере одно из условий: а) все три переключателя
разомкнуты; б) переключатель
разомкнут, а два остальных замкнуты.Построить наиболее простую релейно-контактную схему с тремя переключателями, которая должна проводить электрический ток тогда и только тогда, когда выполнены два условия: а) первый переключатель замкнут; б) только один из двух остальных переключателей замкнут.
Построить наиболее простую релейно-контактную схему с четырьмя переключателями, которая должна проводить электрический ток тогда и только тогда, когда выполнены условия: а) первые три переключателя разомкнуты, а последний замкнут; б) первый и последний переключатели замкнуты, а остальные два разомкнуты; в) первые два переключателя разомкнуты, а остальные замкнуты; г) второй переключатель разомкнут, а три остальных замкнуты.
Построить наиболее простую релейно-контактную схему с четырьмя переключателями, которая должна проводить электрический ток тогда и только тогда, когда выполнено условие: замкнуты два, и только два переключателя, но контакты
и
вместе не замкнуты.Построить наиболее простую релейно-контактную схему с четырьмя переключателями, которая должна проводить электрический ток тогда и только тогда, когда выполнено по меньшей мере одно из условий: а) первые два переключателя разомкнуты, а остальные – замкнуты; б) первые три переключателя замкнуты, а последний – разомкнут; в) первый и последний переключатели разомкнуты, а два остальных замкнуты.
Построить наиболее простую релейно-контактную схему с четырьмя переключателями, которая должна проводить электрический ток тогда и только тогда, когда выполнено по меньшей мере одно из условий: а) первые два переключателя разомкнуты, а остальные – замкнуты; б) первые три переключателя разомкнуты, а последний – замкнут; в) первый и последний переключатели замкнуты, а два остальных – нет.
Построить релейно-контактную схему с шестью переключателями, замыкающуюся тогда и только тогда, когда замкнута тройка последовательных контактов.
Каждый из трех членов комитета, голосуя «за», нажимает на кнопку. Построить по возможности более простую схему, через которую проходил бы ток и включал электрическую лампочку тогда и только тогда, когда не мене двух членов комитета голосуют «за».
Комитет состоит из пяти человек. Решение выносится большинством голосов. Если председатель «против», то решение не принимается. Построить такую схему, чтобы, голосуя «за», каждый из пяти человек нажимал бы на кнопку, и в случае принятия решения зажигалась бы сигнальная лампочка.
Постройте релейно-контактную схему с четырьмя переключателями, которая проводит ток тогда и только тогда, когда замыкаются некоторые, но не все переключатели.
Постройте релейно-контактную схему с пятью переключателями, которая проводит ток тогда и только тогда, когда замкнуты все ее переключатели или когда не замкнут ни один из них.
Постройте релейно-контактную схему с тремя переключателями, которая проводит ток тогда и только тогда, когда замкнуты либо ровно один, либо ровно два переключателя.
Постройте релейно-контактную схему с пятью переключателями, которая проводит ток тогда и только тогда, когда замкнуты ровно четыре ее переключателя.
Постройте релейно-контактную схему с пятью переключателями, которая проводит ток тогда и только тогда, когда замкнуты либо ровно два, либо ровно три переключателя.
Требуется составить схему с четырьмя переключателями
.
Схема должна проводить ток тогда и
только тогда, когда будут замкнуты
переключатели
и
или
и
.Требуется составить схему с тремя переключателями
.
Схема должна проводить ток тогда и
только тогда, когда либо переключатель
замкнут, либо переключатель
замкнут, либо переключатель
разомкнут.Постройте релейно-контактную схему с пятью переключателями, которая проводит ток тогда и только тогда, когда меньшая часть переключателей замкнута, но если последний переключатель замкнут, то схема проводит ток, независимо от положения остальных переключателей.
Машина-экзаменатор дает сигнал «зачет» (зажигается лампочка) в том и только в том случае, если экзаменующийся ответил правильно хотя бы на два из трех вопросов билета. При вводе в машину правильного ответа замыкается контакт в цепи сигнальной лампочки. Постройте схему этой цепи.
По установленному сигналу каждый игрок замыкает или размыкает выключатель, находящийся под его управлением. Если оба делают одно и то же, то выигрывает игрок А, в противном случае – игрок В. Построить такую схему, чтобы при выигрыше А зажигалась лампочка.
Имеется одна лампа в лестничном пролете двухэтажного здания. Построить схему так, чтобы на каждом этаже своим выключателем можно было бы гасить и зажигать лампу, независимо от положения другого выключателя.