Поскольку из вида СДНФ бывают ясны ее переменные, будем говорить просто СДНФ, опуская слова: «относительно переменных 
».
Всякую ДНФ можно привести к СДНФ расщеплением конъюнкций, которые содержат не все переменные, например:
.
Если из формулы F с помощью некоторых равносильностей можно получить формулу Ф, то F можно получить из Ф, используя те же равносильности. Это соображение позволяет доказать следующую теорему.
Теорема 1.1
Для любых двух равносильных формул F и Ф существует тождественное преобразование F в Ф с помощью соотношений (I.1.) – (IV.8).
Замечание
Важность этой теоремы в том, что соотношений (I.1.) – (IV.8) оказывается достаточно для любого тождественного преобразования в булевой алгебре.
Аналогично ДНФ определяется конъюнктивная нормальная форма (КНФ) как конъюнкция элементарных дизъюнкций.
Переход от ДНФ к КНФ можно осуществить следующим образом. Пусть ДНФ F имеет вид: 
, где 
– элементарные конъюнкции. Формула 
приводится к ДНФ 
.
Тогда 
. По законам Де Моргана отрицания элементарных конъюнкций преобразуются в элементарные дизъюнкции, что и даст КНФ.
Аналогом СДНФ является совершенная конъюнктивная нормальная форма (СКНФ), каждая элементарная дизъюнкция которой содержит все переменные. Построение СКНФ из КНФ проводится аналогично тому, как из ДНФ получается СДНФ.
Таким образом, любая формула алгебры логики высказываний может быть записана в СДНФ (кроме тождественно-ложной) или в СКНФ (кроме тождественно-истинной).
Примеры
Пример 1.13
Убедиться, является ли данная формула ДНФ, КНФ, СДНФ или СКНФ:
а) 
;
б) 
;
в) 
;
г) 
;
д) 
;
е) 
.
Решение
а) Данная формула является КНФ (конъюнкция элементарных дизъюнкций), но не СКНФ, так как элементарные дизъюнкции не являются полными.
б) Формула не является ДНФ, так как последняя конъюнкция не является элементарной. Но формулу можно с помощью закона Де Моргана преобразовать к равносильному виду
,
который является ДНФ, но не СДНФ (не все элементарные конъюнкции полны).
в) Формула не является ни ДНФ, ни КНФ, поскольку содержит импликацию.
г) СДНФ, состоящая из одной элементарной полной конъюнкции; либо КНФ, но не СКНФ, так как состоит из трех элементарных неполных дизъюнкций.
д) СКНФ.
е) СДНФ.
Пример 1.14
Зная таблицу истинности формулы F, записать ее СДНФ и СКНФ:
Решение
1) Получение СДНФ.
Выбираем те наборы значений А, В, С, при которых F = 1, и строим по ним соответствующие элементарные конъюнкции:
1 1 0 
,
1 0 0 
.
Тогда дизъюнкция этих элементарных конъюнкций и будет СДНФ формулы F:
.
2) Получение СКНФ.
Выбираем те наборы значений А, В, С, при которых F = 0, и строим по ним соответствующие элементарные дизъюнкции:
1 1 1 
,
1 0 1 
,
0 1 1 
,
0 1 0 
,
0 0 1 
,
0 0 0 
.
Тогда конъюнкция этих элементарных дизъюнкций и будет СКНФ формулы F:
.
Пример 1.15
Преобразовать формулу F(a, b. c)= к СДНФ и СКНФ.
Решение
1). Получим вначале СДНФ:
.
2). Для получения СКНФ преобразуем каждый конъюнктивный член:
;
.
Тогда имеем:
.
Пример 1.16
Преобразовать формулы к ДНФ:
а) 
;
б) 
;
в) 
;
г) 
.
Решение
а) 
– СДНФ.
б) 
- ДНФ.
в) 
– ДНФ.
г) 
– ДНФ.
Пример 1.17
Построить цепь для электрифицированной игры с монетами. По установленному сигналу каждый из двух игроков замыкает или размыкает переключатель, находящийся под его управлением. Если оба игрока делают одно и то же, то выигрывает первый игрок (А); если противоположное, то выигрывает второй игрок (В). Построить цепь так, чтобы загоралась лампочка, если выигрывает игрок А. Записать ДНФ соответствующей формулы.
Решение
Обозначим переменными А и В действия игроков, приписывая переменной значение 1, если игрок замыкает свой переключатель, и 0, если размыкает. Тогда таблица истинности для искомой формулы будет иметь следующий вид:
По описанной ранее технологии с помощью строк, в которых формула принимает значение 1, записываем ДНФ:
.
Для построения соответствующей электрической цепи будем использовать прямые (для описания значений А и В) и обратные (для описания значений 
и 
) двухпозиционные переключатели. Значение 1 переменной интерпретируется как состояние переключателя «ток проходит», значение 0 – «ток не проходит». Последовательное соединение переключателей будет имитировать конъюнкцию соответствующих переменных (ток по этому участку цепи пойдет только в случае, когда обе переменные истинны одновременно). Параллельное соединение будет имитировать
 |
дизъюнкцию.
Тогда условиям задачи будет удовлетворять, например, следующая электрическая цепь (рис. 1.7).
Задачи
1.16. Привести к ДНФ:
а) 
;
б) 
.
1.17. Привести к СДНФ формулы из задачи 1.16.
1.18. Доказать тождественную истинность формул:
а) 
;
б) 
;
в) 
;
г) 
;
д) 
.
1.19. Доказать тождественную ложность формул:
а) 
;
б) 
.
1.20. Привести формулы к ДНФ (с помощью тождественных преобразований) и, если можно, упростить:
а) 
;
б) 
;
в) 
;
г) 
;
д) 
;
е) 
;
ж) 
.
1.21. Доказать тождественную истинность формул:
а) 
;
б) 
;
в) 
;
г) 
.
1.22. Доказать тождественную ложность формул:
а) 
;
б) 
;
в) 
.
1.23. Двумя способами: с помощью истинностных таблиц и с помощью тождественных преобразований привести к СДНФ формулы из задачи 1.20.
1.24. Привести к СДНФ, т. е. найти СДНФ, равносильную данной формуле:
а) 
;
б) 
;
в) 
.
1.25. Привести к СКНФ, т. е. найти СКНФ, равносильную данной формуле:
а) 
;
б) 
;
в) 
.
1.26. Пусть формула U записана в СКНФ. Строим формулу В следующим образом:
1) выписываем конъюнкцию дизъюнктивных членов, не входящих в U;
2) меняем Ù на Ú, Ú на Ù, 
на 
, на .
Доказать, что В – СДНФ формулы U.
1.27. По СКНФ формулы U построить:
а) СКНФ формулы 
;
б) СДНФ формулы .
1.28. По СДНФ формулы U и СДНФ формулы В построить:
а) СКНФ и СДНФ формулы 
;
б) СКНФ и СДНФ формулы 
;
в) СКНФ и СДНФ формулы 
.
1.4. Применение формул логики высказываний в теории
однотактных дискретных автоматов
Сводка теории
Автомат предназначен участвовать в некотором процессе. В него поступают сигналы: информация о ситуациях, существующих в данный момент времени. В зависимости от поступивших сигналов автомат должен выполнять то или иное предусмотренное действие. Принято говорить, что сигналы поступают на вход автомата, а действия осуществляются на его выходе.
Желаемое действие автомата в общем случае может зависеть как от сигналов, поступающих в данный момент времени, так и от сигналов, поступивших ранее.
В самой общей форме автомат должен решать следующую задачу. Некоторые действия на выходе автомата в момент времени 
должны быть функцией от сигналов, поступивших на вход автомата за все время до этого момента. Следовательно, выявление, запись и анализ функциональной зависимости вход/выход – первый и наиболее важный этап при создании автомата. Именно на этом этапе может быть с успехом использован аппарат логики высказываний.
Действие автомата условно можно изобразить схемой (рис. 1.8), где 
, ... , 
– входы; 
, ... , 
– выходы.
При построении дискретного автомата принимают ряд упрощающих допущений:
1) действие автомата должно состоять в исполнении одного акта с двумя возможными исходами (например, включить или выключить электродвигатель);
2) в каждый момент времени на вход автомата поступает некоторое конечное число (
) сигналов, каждый из которых может принимать одно из двух значений (например, для автомата стрелки сигналы могут принимать значения «Поезд прошел семафор» или «Поезд не прошел семафор»);
3) сигналы поступают на вход не непрерывно, а в некоторые дискретные моменты времени, обозначаемые целыми числами 
(например, через каждую секунду).
С учетом перечисленных допущений зависимость вход/выход для абстрактного автомата может быть описана следующим образом:
. (1.1)
Здесь 
– действие на выходе автомата; 
– сигналы на n-м входе автомата в моменты времени 
.
Как следует из равенства (1.1), задача выявления и описания зависимости вход/выход для автомата сводится к получению развернутого описания функционала 
и состоит в формулировке тех логических условий, при которых действие на выходе автомата выполняется, и при которых не выполняется. Именно эти условия формулируются на языке булевых функций с применением булевых операций и формул. По этим формулам уже нетрудно составить из некоторых элементарных узлов (например, из цифровых микросхем) схему, выполняющую желаемое действие.
Будем рассматривать частный, но очень важный случай, когда действие автомата на выходе зависит от сигналов, поступающих на вход в данный момент времени (а не во все предыдущие). Такие автоматы называются однотактными или автоматами без памяти. В этом частном случае выражение для действия автомата упрощается и принимает вид:
.
Для упрощенного наглядного изображения автомата используют функциональные, релейно-контактные и контактные схемы. Смысл этих названий будет ясен из их графических образов.
Элементарными автоматами, «строительными блоками» для более сложных, являются автоматы, реализующие логические функции (связки): 
(как следует из теории, они образуют полную систему, т. е. остальные логические функции могут быть выражены через эти три). Они называются соответственно логическими элементами «или», «и», «не» и изображаются следующими функциональными схемами (рис. 1.9).
Заметим, что для реализации отрицания требуется инвертор, но микросхем-инверторов в чистом виде не бывает. Они строятся либо на базе элементов логического умножения, либо на базе элементов логического сложения (т. е. элементов, реализующих дизъюнкцию, как показано на рис. 1.9). Отметим также, что в схемах, реализующих сложные логические функции (формулы), могут применяться функциональные элементы с несколькими входами.
Логические элементы – это простейшие автоматы, которые могут работать на различных физических принципах (гидравлических, пневматических, электрических). В последнем случае используются релейно-контактные схемы на электромагнитных реле.
Для конъюнкции эта схема выглядит следующим образом (рис. 1.10).
Нажатие кнопки А сообщает логическому элементу о том, что высказывание: А = 1, в противном случае: А = 0. Если нажать кнопку А, то по катушке реле 
потечет ток и контакты прямого переклю чателя а замкнутся. То же произойдет, если нажать на (отрицательный потенциал) кнопку В.
Сигнал 1 на выходе элемента зажжет лампочку х. Понятно, что лампочка загорится только в том случае, когда одновременно нажаты кнопки А и В, т. е. конъюнкция реализуется именно последовательным соединением переключателей. Сопротивление R требуется для снятия остаточного напряжения.
Для дизъюнкции релейно-контактная схема имеет вид (рис. 1.11).
Принцип действия – тот же, только используется параллельное соединение пере ключателей, т. е. лампочка загорится, если нажата хотя бы одна из кнопок А или В.
Наконец, для отрицания релейно-контактная схема реализуется с применением обратного переключателя, т. е. контакты переключателя замкнутся при А = 0 и наоборот (рис. 1.12).
Используется и другое графическое изображение релейно-контактных схем. Логической переменной 
ставится в соответствие проводник, по которому ток идет или нет в зависимости от того: 
или 
.
Тогда отрицание реализуется при помощи устройства, называемого реле с размыкающим (отрицательным) контактом (рис. 1.13).
Если по катушке А ток не идет (), то пружина оттягивает контакт В вверх и цепь замыкается. В результате, на выходе С будет ток. Если же 
и по обмотке А идет ток, то контакт В притягивается вниз и на выходе С нет тока. В результате, реализуется функция 
.
Дизъюнкция (рис. 1.14, а) и конъюнкция (рис. 1.14, б) реализуются при помощи реле с замыкающим (положительным) контактом.
Принято считать, что ток распространяется мгновенно, а на срабатывание реле (замыкание контакта) уходит один такт. Это значит, что на схеме для конъюнкции сигнал 
поступит на один такт позже сигнала ; сигнал на выходе возникает одновременно с сигналом .
В связи с этим необходимо учитывать время, которое уходит на обработку сигналов в схеме, и иногда менять его, не меняя логической функции, реализуемой схемой. Это достигается при помощи элементов задержки, роль которых играют реле с замыкающим контактом (типа конъюнкции), на контакт которых подается сигнал 
(т. е. 
). При этом происходит задержка на один такт.
Если после подачи на входы релейно-контактной схемы сигналов 
, 
,..., 
через 
тактов независимо от сигналов на входах в другие моменты времени на выходе возникает сигнал 
, то говорят, что схема реализует функцию с задержкой . Таким образом, в данной интерпретации возникают многотактные схемы. При этом предполагается, что если в два последовательных момента времени подаются два набора сигналов, то через тактов после каждого из них на выходе появляется сигнал, отвечающий значению 
на соответствующем наборе. Иначе говоря, последовательные наборы сигналов обрабатываются независимо.
Контактные схемы, в которых соединяются лишь контакты (нет соединений обмоток реле с контактами) представляют собой графы: ребрам графа приписаны символы логических переменных или их отрицаний; вершины означают соединения контактов, соответствующих отрезкам (двухполюсникам), которые в этих вершинах сходятся. Если по одному изконтактов, идущему в вершину, идет ток, то он распространяется по всем замкнутым в данный момент контактам, имеющим данную вершину в качестве полюса. В графе выделяются две вершины: вход и выход. На вход всегда подается ток. На другие полюсы ток извне никогда не поступает.
Если на обмотки некоторых катушек подан ток, то через один такт замкнутся соответствующие им замыкающие контакты и разомкнутся размыкающие; на контактах остальных катушек возникнет противоположная картина. Если при этом на выход схемы поступит ток, то говорят, что при данных значениях переменных (состояниях обмоток катушек) в схеме есть проводимость; в противном случае – что проводимости нет. Итак, контактная схема работает в один такт.
Логическую функцию (и соответствующую формулу), реализуемую схемой, называют ее функцией проводимости. Такая функция равна при тех значениях аргументов, при которых в схеме есть проводимость, и равна 
, если проводимости нет.
Для основных логических операций контактные схемы выглядят следующим образом (рис. 1.15).
Комбинируя те или иные схемы, моделирующие основные логические элементы, в соответствии со структурой формулы, предварительно записанной через дизъюнкцию, конъюнкцию и отрицание (например, в виде ДНФ или КНФ), получаем функциональные, релейно-контактные или контактные схемы для формул.
При синтезе (создании) дискретных однотактных автоматов обычно действуют по следующему алгоритму:
1) описать автомат словесно;
2) определить число входов и выходов автомата;
3) составить таблицу желаемой работы автомата (типа таблицы истинности);
4) используя полученную таблицу выписать структурную формулу (как правило, в виде ДНФ или КНФ);
5) вычертить функциональную или иную схему.
Примеры
Пример 1.18
Начертить релейно-контактные схемы и выписать соответствующие структурные формулы для следующих функциональных элементов:
 |
Решение
а) Для получения структурной формулы есть два пути «прочтения» схемы: двигаясь по схеме слева направо, строим формулу как бы «изнутри» (от переменных и внутренних логических связок к внешним логическим связкам), двигаясь же по схеме справа налево, строим формулу «снаружи» (от внешних логических связок к внутренним).
В обоих случаях приходим к формуле: 
.
Для построения релейно-контактной схемы преобразуем формулу в равносильную ей (иначе инвертировать конъюнкцию на схеме не удастся):
.
Теперь строим схему (рис. 1.17).
 |
б) Структурная формула
содержит только инверсию переменной, поэтому можем сразу построить релейно-контактную схему (рис. 1.18).
Пример 1.19
Для каждой из приведенных функциональных схем (рис. 1.19) выписать соответствующую структурную формулу.
Решение
а) 
;
б) 
.
Пример 1.20
Используя структурные формулы начертить функциональные схемы:
а) 
; б) 
;
в) 
; г) 
.
Решение
Заметим, что инвертирование выходного сигнала конъюнкции и дизъюнкции можно изобразить по-другому (рис. 1.21), что упрощает схемы (рис. 1.20).
При построении схемы имеет смысл по возможности оптимизировать ее структуру в первую очередь по числу используемых блоков, а затем по числу каналов связей и их разветвлений (элементы дороже линий связи).
Пример 1.21
Найти функции проводимости для следующих контактных схем (рис. 1.22).
Решение
а) 
.
б) 
.
в) 
.
Пример 1.22
Реализовать данные функции в виде контактных схем:
а) 
;
б) 
.
Решение
а) Представим функцию в виде ДНФ:
.
Каждой элементарной конъюнкции, входящей в ДНФ, поставим в соответствие схему из последовательно соединенных контактов, а затем отождествим соответственно все входы и все выходы полученных цепочек (рис. 1.23).
б) По тому же алгоритму получим ДНФ:
,
и соответствующую контактную схему (рис. 1.24).
Пример 1.23
Построить функциональную схему для автомата управления подачей электроэнергии.
Решение
1) Словесное описание системы приведено в условиях задачи.
2) Число входов автомата определяется количеством цехов как источников исходной информации о потребности в электроэнергии (а, b, c), число выходов – количеством генераторов (х, у).
3) Таблица работы автомата (0 – цех не нуждается в электроэнергии или генератор не включен, 1 – в противном случае):
4) По полученным таблицам истинности составим ДНФ для выходных сигналов:
;
.
Для оптимизации функциональной схемы воспользуемся основными логическими законами и упростим полученную формулу для х, добавляя еще два дизъюнктивных члена (они выделены):
.
5) Начертим функциональную схему автомата (рис. 1.25).
Задачи
1.29. Построить функциональные схемы, реализующие следующие формулы:
а) 
;
б) 
.
1.30. Построить релейно-контактные схемы, реализующие следующие функции:
а) 
;
б) 
.
 |
1.31. По данной релейно-контактной схеме (рис. 1.26) построить соответствующие функциональную и контактную схемы.
1.32. Сконструировать автомат для подсчета голосов при тайном голосовании. Голосуют три человека. Автомат выдает сигнал «избран», если число голосов «за» не менее двух, причем один из голосов – голос председателя.
Как изменится автомат, если:
а) убрать последнее условие?
б) допустить для голосующих решение «воздержался»?
Контрольные вопросы
1. Дайте определение высказывания, простого высказывания.
2. Дайте определения основных логических операций: отрицания, конъюнкции, дизъюнкции, альтернативной дизъюнкции, импликации, эквивалентности; приведите их таблицы истинности их технические аналоги (электрические цепи).
3. Какая существует связь между формулами логики высказываний и булевыми функциями?
4. Что такое равносильные формулы? Как можно доказать равносильность двух формул?
5. Могут ли равносильные формулы содержать несовпадающие наборы простых высказываний? Приведите пример.
6. Что такое фиктивная переменная? Приведите пример булевой функции с фиктивными переменными.
7. Восстановите доказательства основных логических законов.
8. В чем разница между подстановкой формулы вместо переменной и заменой подформул?
9. Что называют тождественными преобразованиями формул?
10. Дайте определение тавтологии и противоречия. Что такое логически истинное и логически ложное высказывание?
11. Какие свойства тавтологий Вы можете привести?
12. Приведите определения и примеры полной системы логических функций; базисной системы логических функций.
13. Дайте определения ДНФ, КНФ, СДНФ, СКНФ.
14. Что такое дискретный конечный автомат?
15. В чем главное отличие автомата с памятью от автомата без памяти?
ВВЕДЕНИЕ В МАТЕМАТИЧЕСКУЮ ЛОГИКУ.. 1
ВВЕДЕНИЕ.. 3
1. ЭЛЕМЕНТЫ ЛОГИКИ ВЫСКАЗЫВАНИЙ.. 4
1.1. Высказывания и операции над ними, формулы.. 4
1.2. Упрощение формул. Тождественные преобразования. Доказательство равносильности, тождественной истинности и тождественной ложности формул и булевых функций.. 12
1.3. Нормальные формы формул логики высказываний.. 17
1.4. Применение формул логики высказываний в теории однотактных дискретных автоматов 23
Контрольные вопросы.. 33
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 |
