План урока информатики 11 класс «Построение логический схем по заданной логической функции»
Тема: Построение логических схем по заданной логической функции.
Цель урока: Рассмотреть понятие СДНФ и СКНФ, научиться строить схемы, используя СДНФ и СКНФ, закрепить полученные знания на примере решения задач.
В задачах по логике часто встречаются следующие задания: записать функцию, реализующую логическую схему, упростить её и построить таблицу истинности для этой функции. А как решить обратную задачу? Дана произвольная таблица истинности, нужно построить функциональную или релейно-контактную схему. Этот вопрос мы сейчас и рассмотрим.
Любую функцию алгебры логики можно представить комбинацией трёх операций: конъюнкции, дизъюнкции и инверсии. Как это делается?
Минтерм – это функция, образованная конъюнкцией некоторого числа переменных или их отрицаний. Минтерм принимает значение 1 при единственном из всех возможных наборов аргументов, и значение 0 при всех остальных.
Например: 
Макстерм – это функция, образованная дизъюнкцией некоторого числа переменных или их отрицаний. Макстерм принимает значение 0 в одном из возможных наборов аргументов, и значение 1 при всех других.
Например: 
Функция в дизъюнктивной нормальной форме (ДНФ) является суммой Минтермов.
Например: 
Конъюнктивная нормальная форма (КНФ) является логическим произведением элементарных дизъюнкций (макстермов)
Например: 
Совершенной дизъюнктивно-нормальной формой (СДНФ) называется ДНФ, в каждом минтерме которой присутствуют все переменные или их отрицания.
Например: 
Совершенной конъюнктивно-нормальной формой (СКНФ) называется КНФ, в каждом минтерме которой присутствуют все переменные или их отрицания.
Например: 
Запись логической функции по таблице.
Любая логическая функция может быть выражена в виде СДНФ или СКНФ.
Функции G 0, G 1, G 4, G 5, G 7 – это минтермы. Каждая из этих функций является произведением трёх переменных или их инверсией и принимает значение 1 только в одной ситуации.
Таким образом СДНФ имеет вид:
Аналогично можно построить СКНФ. Количество сомножителей равно количеству нулей в значении функции.
Таким образом, можно записать в виде формулы любую логическую функцию, заданную в виде таблицы.
Алгоритм построения СДНФ по таблице истинности.
Дана таблица истинности некоторой логической функции.
Для построения СДНФ нужно выполнить следующее:
Выбрать все строки таблицы, в которых функция принимает значение 1.
Каждой такой строке поставить в соответствие конъюнкцию всех аргументов или их инверсий (минтерм). При этом аргумент, принимающий значение 0, входит в минтерм с отрицанием, а значение 1 – без отрицания.
Наконец, образуем дизъюнкцию всех полученных минтермов. Количество минтермов должно совпадать с количеством единиц логической функции.
Алгоритм построения СКНФ по таблице истинности.
Дана таблица истинности некоторой логической функции.
Для построения СКНФ нужно выполнить следующее:
Выбрать все строки таблицы, в которых функция принимает значение 0.
Каждой такой строке поставить в соответствие дизъюнкцию всех аргументов или их инверсий (макстерм). При этом аргумент, принимающий значение 1, входит в макстерм с отрицанием, а значение 0 – без отрицания.
Наконец, образуем конъюнкцию всех полученных макстермов. Количество макстермов должно совпадать с количеством нулей логической функции.
Если условиться из двух форм (СДНФ или СКНФ) отдавать предпочтение той, которая содержит меньше букв, то СДНФ предпочтительней, если среди значений функции таблицы истинности меньше единиц, СКНФ – если меньше нулей.
Пример: Дана таблица истинности логической функции от трёх переменных. Построить логическую схему, реализующую эту функцию.
Выберем те строки в таблице истинности, в которых значение функции равно нулю
Сравнив начальную и итоговую таблицы истинности, можно сделать вывод, что логическая функция построена верно.
Три преподавателя отбирают задачи для олимпиады. На выбор предлагается несколько задач. По каждой задаче каждый преподаватель высказывает своё мнение: легкая (0) или трудная (1) задача. Задача включается в олимпиадное задание, если не менее двух преподавателей отметили её как трудную, но если все три преподавателя считают её трудной, то такая задача не включается в олимпиадное задание как слишком сложная.
Составьте логическую схему устройства, которое будет выдавать на выходе 1, если задача включается в олимпиадное задание и 0, если не включается.
Анализируя условия задачи, получаем следующую таблицу истинности:
Строим СДНФ: 
Теперь строим логическую схему этой функции
Постройте логическую схему для подъезда трёхэтажного дома такую, чтобы выключателем на любом этаже можно было бы включить или выключить свет во всём доме.
Итак, у нас есть три выключателя, которыми мы должны включать и выключать свет. У каждого выключателя есть два состояния: верхнее (0) и нижнее (1). Предположим, что если все три выключателя в положении 0, свет в подъезде выключен. Тогда при переводе одного из выключателей в положение 1, свет в подъезде должен загореться. Очевидно, что при переводе любого другого переключателя в положение 1, свет в подъезде выключится. Если третий выключатель перевести в положение 1, свет в подъезде загорится. Строим таблицу истинности:
Строим СДНФ : 
Условие изменения значения логической функции 
при одновременном изменении аргументов B и С равно:
1) 
2) 
3) 
4) 
5) 
Для успешного решения данной задачи вспомним следующие формулы:
Нам дана логическая функция от трёх переменных
Изменим одновременно переменные B и С : 
Построим таблицы истинности этих двух функций:
Анализируем полученную таблицу. Из восьми строк только в двух (2-й и 3-й) функция не изменяет своего значения. Обратите внимание что в этих строках переменная А не изменяет своего значения, а переменные В и С – изменяют своё значение на противоположное.
Строим СКНФ функции по этим строкам:
Искомый ответ – 4.
Условие изменения значения логической функции 
при одновременном изменении аргументов А и В равно:
1) 
2) 
3) 
4) 
5) 
Строим таблицу истинности:
Анализируем полученную таблицу. Из восьми строк только в двух (1-й и 7-й) функция меняет своё значение. Обратите внимание, что в этих строках переменная С не меняет своё значение, а переменные А и В меняют своё значение. Строим СДНФ этой функции:
Искомый ответ – 2.
5) Условие изменения значения логической функции
при одновременном изменении аргументов А и В равно :
1) 
2) 
3) 
4) 
5) 
Р
ешение : 
= 
= 