"Информатика (базовый и углублённый уровни) (в 2 частях)", Поляков К.Ю., Еремин Е.А.
Синтез логического выражения — это построение формулы по заданной таблице истинности. Для этого используют совершенные нормальные формы: СДНФ собирают по строкам, где функция равна 1, а СКНФ — по строкам, где она равна 0. В каждой форме значения входных переменных определяют, где поставить отрицания, а порядок операций задаёт способ соединения частей. Полученную формулу можно упростить, если её таблица истинности останется прежней.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Логическая функция — зависимость значения логической переменной от значений одной или нескольких входных переменных. Например, функция f(x, y) получает значения x и y и выдаёт 0 или 1. Её удобно записывать таблицей истинности: в столбцах перечисляют входы и результат, а в строках — все возможные наборы значений входов. Такая таблица наглядно задаёт функцию и помогает не пропустить ни один вариант.
Дизъюнктивная нормальная форма (ДНФ) — выражение, в котором элементарные конъюнкции соединены операцией ИЛИ. Элементарная конъюнкция — часть из переменных или их отрицаний, объединённых операцией И; например, x И не y. Скобки помогают увидеть границы таких частей и порядок действий: сначала выполняется И внутри каждой части, затем ИЛИ между ними. ДНФ позволяет описать случаи, когда функция принимает значение 1.
Совершенная дизъюнктивная нормальная форма (СДНФ) — ДНФ, в которой для каждой строки таблицы с результатом 1 записана отдельная конъюнкция всех переменных или их отрицаний. Поэтому каждая часть учитывает полный набор входов, а не только некоторые из них. СДНФ нужна, чтобы получить формулу непосредственно по таблице, без догадок о том, какие переменные важны.
Совершенная конъюнктивная нормальная форма (СКНФ) — КНФ, в которой каждой строке со значением функции 0 соответствует дизъюнкция всех переменных или их отрицаний. КНФ — это конъюнкция, то есть И, между дизъюнкциями, внутри которых используется ИЛИ. Каждая такая скобка составляется так, чтобы быть ложной на своей строке с нулём. СКНФ задаёт функцию через наборы, на которых результат должен быть 0.
Синтез начинают с задания функции: перечисляют входные переменные и составляют таблицу истинности. Если переменных n, возможны 2ⁿ наборов, ведь каждая переменная принимает два значения. Таблицу заполняют в одном и том же порядке, например от 000 до 111 для трёх переменных. Полный список нужен потому, что формула должна описывать поведение функции не только на удобных или заметных примерах, но и на каждом возможном входе.
Для СДНФ сначала находят строки, в которых результат равен 1. В каждой такой строке создают свою конъюнкцию, включающую все переменные: переменную со значением 1 пишут без отрицания, а со значением 0 — с отрицанием. Например, при x = 1 и y = 0 часть будет x И не y. Выбор знака не случаен: эта часть истинна именно при x = 1 и y = 0, а при любом другом наборе хотя бы один её множитель равен 0.
Все полученные конъюнкции соединяют операцией ИЛИ. Это соответствует таблице: достаточно, чтобы сработала хотя бы одна часть, ведь каждая из них описывает строку, где результат функции равен 1. При этом одна часть не становится истинной на соседнем наборе, поскольку содержит условие для каждой переменной. Значит, выражение выдаёт 1 ровно в выбранных строках, а во всех остальных — 0.
Для СКНФ выбирают строки с результатом 0 и для каждой составляют дизъюнкцию всех переменных. Здесь правило отрицания обратное: переменную со значением 0 записывают без отрицания, а со значением 1 — с отрицанием. Например, для строки x = 1, y = 0 скобка имеет вид не x ИЛИ y и равна 0 именно на этом наборе. Чтобы функция была равна 1 на остальных строках, такую скобку соединяют с другими операцией И.
СДНФ и СКНФ описывают одну функцию, но строятся с противоположных сторон таблицы: по единицам и по нулям. Совершенная форма может получиться громоздкой, потому что в ней для каждой подходящей строки есть отдельная часть со всеми переменными. После построения выражение разрешается упростить законами логики, если его таблица истинности не меняется. Поэтому совершенная форма удобна как точный исходный вариант, а упрощённая — как более короткая запись той же функции.
| Характеристика | СДНФ | СКНФ |
|---|---|---|
| По каким строкам строят | По строкам, где функция равна 1 | По строкам, где функция равна 0 |
| Какую операцию ставят между частями | ИЛИ | И |
| Какую операцию ставят внутри части | И | ИЛИ |
| Как записывают переменную при значении 0 | С отрицанием | Без отрицания |
| Как записывают переменную при значении 1 | Без отрицания | С отрицанием |
Пользуйтесь таблицей отдельно для каждой формы: сначала определите, какие строки выбирать, затем проверьте операции и правила отрицания. Не переносите правило для СДНФ на СКНФ — в них знаки при переменных выбирают по-разному. После составления формулы сверьте её значение с таблицей на каждом наборе.
Условие. Функция двух переменных x и y равна 1 только при наборе (1, 0). Требуется составить СДНФ. Поскольку единица встречается ровно один раз, в выражении будет одна конъюнкция.
Ответ: СДНФ равна x И не y. Проверка подтверждает, что формула даёт единицу только на заданном наборе.
Условие. Для переменных x, y, z функция равна 1 в строках 001, 101 и 110. Требуется составить СДНФ и СКНФ. Чтобы не спутать знаки, будем читать каждую строку в порядке x, y, z.
Ответ: СДНФ — дизъюнкция трёх найденных конъюнкций; СКНФ — конъюнкция пяти скобок. Сверьте список строк: три строки с единицами и пять строк с нулями в сумме дают все восемь наборов.
Условие. Составить СДНФ для трёх переменных по таблице, затем упростить выражение и проверить его на всех наборах. В условии не указаны конкретные строки с единицами, поэтому решение покажет порядок действий для любой такой таблицы. Подставлять выдуманные значения функции нельзя: выражение зависит именно от её таблицы.
Ответ: сначала получается механическая СДНФ, затем — равносильная ей упрощённая формула. Конкретное сокращённое выражение можно назвать только по значениям в исходной таблице.
В СДНФ иногда включают строки, где функция равна 0, потому что смотрят на значения переменных, а не на столбец результата. Тогда формула описывает не те наборы, на которых функция должна быть истинной. Перед записью частей отдельно отметьте строки с единицами в столбце функции. В конце проверьте, что каждой части соответствует именно одна из этих строк.
При составлении СКНФ можно по привычке применить правило отрицания из СДНФ. Тогда скобка перестанет быть ложной на нужной строке с нулём и вся формула может измениться. Для СКНФ пишите переменную без отрицания при входном значении 0, а при 1 — с отрицанием. Самопроверка простая: подставьте в соответствующую скобку значения её строки и убедитесь, что она равна 0.
Ещё одна ошибка — перепутать операции: поставить И между частями СДНФ или ИЛИ между скобками СКНФ. Её допускают, когда помнят только названия форм, но теряют из виду смысл таблицы: в СДНФ достаточно одной истинной части, а для СКНФ должны быть истинны все скобки. Запишите рядом правило «СДНФ: И внутри, ИЛИ снаружи; СКНФ: ИЛИ внутри, И снаружи». Затем проверьте значения выражения на нескольких строках обоих типов.
Если пропустить набор или поменять порядок переменных, части будут соответствовать не тем строкам. Особенно легко ошибиться с трёхзначными строками, когда столбцы таблицы расположены не так, как в записи формулы. Заранее зафиксируйте порядок, например x, y, z, и придерживайтесь его при чтении каждой строки. Проверьте, что перечислены все 2ⁿ наборов и ни один не повторён.
Для построения нормальных форм нужны таблицы истинности и знание трёх базовых операций: отрицания, конъюнкции и дизъюнкции. Также важно учитывать порядок логических операций и понимать, зачем выражение заключают в скобки. Эти знания помогают читать формулы и вычислять их значения. Если результат не совпал с таблицей, проверка операций и скобок часто позволяет найти ошибку.
Построение по таблице используют при проектировании логических схем: операциям формулы соответствуют логические элементы, которые обрабатывают сигналы 0 и 1. Тот же приём служит отправной точкой для преобразования и упрощения выражений. Сначала получают гарантированно правильную формулу, а затем сокращают её, сохраняя исходное поведение. Это позволяет перейти от таблицы к более компактному описанию функции.
Зачем строить логическое выражение по таблице истинности?
Таблица показывает, какой результат функция выдаёт при каждом наборе входных значений. По ней можно составить формулу, которая точно повторяет это поведение, а затем использовать её, например, для проектирования логической схемы.
Почему в СДНФ берут только строки со значением функции 1?
Каждая часть СДНФ — конъюнкция, которая равна 1 только на одном конкретном наборе переменных. Поэтому части составляют именно для тех наборов, на которых заданная функция должна быть равна 1.
Как понять, какую переменную в элементарной конъюнкции нужно отрицать?
В СДНФ переменную записывают без отрицания, если в выбранной строке её значение равно 1, и с отрицанием, если оно равно 0. Так конъюнкция становится истинной именно на этой строке.
Чем СКНФ отличается от СДНФ?
СДНФ строят по строкам с результатом 1: переменные объединяют операцией И, а полученные части — операцией ИЛИ. СКНФ строят по строкам с результатом 0: внутри частей используют ИЛИ, а части соединяют операцией И.
Можно ли упростить полученное совершенное нормальное выражение?
Да, совершенную нормальную форму можно преобразовать по законам логики. После упрощения проверьте таблицу истинности: для каждого набора значений результат должен совпадать с исходным.
§ 22. Синтез логических выражений
