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

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

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

Каждый переключатель имеет только два состояния: замкнутое и разомкнутое. Переключателю Х поставим в соответствие логическую переменную х, которая принимает значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток; если же переключатель разомкнут, то х равен нулю.

Будем считать, что два переключателя Х и связаны таким образом, что когда Х замкнут, то разомкнут, и наоборот. Следовательно, если переключателю Х поставлена в соответствие логическая переменная х, то переключателю должна соответствовать переменная .

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

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

a)

Схема не содержит переключателей и проводит ток всегда, следовательно F=1;

б)

Схема содержит один постоянно разомкнутый контакт, следовательно F=0;

в)

Схема проводит ток, когда переключатель х замкнут, и не проводит, когда х разомкнут, следовательно, F(x) = x;

г)

Схема проводит ток, когда переключатель х разомкнут, и не проводит, когда х замкнут, следовательно, F(x) = ;

д)

Схема проводит ток, когда оба переключателя замкнуты, следовательно, F(x) = x . y;

е)

Схема проводит ток, когда хотя бы один из переключателей замкнут, следовательно, F(x)=x v y;

ж)

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

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

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

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

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

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

упрощению этой функции;

построению соответствующей схемы.

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

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

получению упрощённой формулы.

1. Построим схему, содержащую 4 переключателя x, y, z и t, такую, чтобы она проводила ток тогда и только тогда, когда замкнут контакт переключателя t и какой-нибудь из остальных трёх контактов.

Решение. В этом случае можно обойтись без построения таблицы истинности. Очевидно, что функция проводимости имеет вид F(x, y, z, t) = t . (x v y v z), а схема выглядит так:

2. Построим схему с пятью переключателями, которая проводит ток в том и только в том случае, когда замкнуты ровно четыре из этих переключателей.

Схема имеет вид:

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

Решение. Имеется четыре возможных пути прохождения тока при замкнутых переключателях a, b, c, d, e : через переключатели a, b; через переключатели a, e, d; через переключатели c, d и через переключатели c, e, b. Функция проводимости F(a, b, c, d, e) = a . b v a . e . d v c . d v c . e . b.

4. Упростим переключательные схемы:

а)

Решение:

Упрощенная схема:

б)

.

Здесь первое логическое слагаемое является отрицанием второго логического слагаемого , а дизъюнкция переменной с ее инверсией равна 1.

Упрощенная схема :

в)

Упрощенная схема:

г)

Упрощенная схема:

д)

(по закону склеивания)

Упрощенная схема:

е)

Решение:

Упрощенная схема:

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

а)

б)

в)

г)

5.1. Установите, какие из следующих предложений являются логическими высказываниями, а какие — нет (объясните почему):

• а) “ Солнце есть спутник Земли ”;
• б) “ 2+3 ґ 4 ”;
• в) “ сегодня отличная погода ”;
• г) “ в романе Л.Н. Толстого “Война и мир” 3 432 536 слов ”;
• д) “ Санкт-Петербург расположен на Неве ”;
• е) “ музыка Баха слишком сложна ”;
• ж) “ первая космическая скорость равна 7.8 км/сек ”;
• з) “ железо — металл ”;
• и) “ если один угол в треугольнике прямой, то треугольник будет тупоугольным”;
• к) “ если сумма квадратов двух сторон треугольника равна квадрату третьей, то он прямоугольный”.

[ Ответ ]

5.2. Укажите, какие из высказываний предыдущего упражнения истинны, какие — ложны, а какие относятся к числу тех, истинность которых трудно или невозможно установить.
[ Ответ ]

5.3. Приведите примеры истинных и ложных высказываний:

• а) из арифметики; б) из физики;
• в) из биологии; г) из информатики;
• д) из геометрии; е) из жизни.

[ Ответ ]

5.4. Сформулируйте отрицания следующих высказываний или высказывательных форм:

• а) “ Эльбрус — высочайшая горная вершина Европы ”;
• б) “ 2>=5 ”;
• в) “ 10 ”;
• г) “ все натуральные числа целые ”;
• д) “ через любые три точки на плоскости можно провести окружность”;
• е) “ теннисист Кафельников не проиграл финальную игру ”;
• ж) “ мишень поражена первым выстрелом ”;
• з) “ это утро ясное и теплое ”;
• и) “ число n делится на 2 или на 3 ”;
• к) “ этот треугольник равнобедренный и прямоугольный ”;
• л) " на контрольной работе каждый ученик писал своей ручкой".

[ Ответ ]

5.5. Определите, какие из высказываний (высказывательных форм) в следующих парах являются отрицаниями друг друга, а какие нет:

• а) “ 5 ”, “ 5>10 ”;
• б) “ 10>9 ”, “ 10 ”;
• в) “ мишень поражена первым выстрелом ”, “ мишень поражена вторым выстрелом ”;
• г) “ машина останавливалась у каждого из двух светофоров ”, “ машина не останавливалась у каждого из двух светофоров ”,
• д) “ человечеству известны все планеты Солнечной системы ”, “ в Солнечной системе есть планеты, неизвестные человечеству ”;
• е) “ существуют белые слоны ”, “ все слоны серые ”;
• ж) “ кит — млекопитающее ”, “ кит — рыба ”;
• з) “ неверно, что точка А не лежит на прямой а ”, “ точка А лежит на прямой а ”;
• и) “ прямая а параллельна прямой b ”, “ прямая a перпендикулярна прямой b ”;
• к) “ этот треугольник равнобедренный и прямоугольный ”, “ этот треугольник не равнобедренный или он не прямоугольный ”.

[ Ответ ]

5.6. Определите значения истинности высказываний:

• а) “ наличия аттестата о среднем образовании достаточно для поступления в институт ”;
• б) “ наличие аттестата о среднем образовании необходимо для поступления в институт ”;
• в) “ если целое число делится на 6, то оно делится на 3 ”;
• г) “ подобие треугольников является необходимым условием их равенства ”;
• д) “ подобие треугольников является необходимым и достаточным условием их равенства ”;
• е) “ треугольники подобны только в случае их равенства ”;
• ж) “ треугольники равны только в случае их подобия ”;
• з) “ равенство треугольников является достаточным условием их подобия ”;
• и) “ для того, чтобы треугольники были неравны, достаточно, чтобы они были неподобны ”;
• к) “ для того, чтобы четырёхугольник был квадратом, достаточно, чтобы его диагонали были равны и перпендикулярны ”.

[ Ответ ]

5.7. Подставьте в приведённые ниже высказывательные формы вместо логических переменных a, b, c, d такие высказывания, чтобы полученные таким образом составные высказывания имели смысл в повседневной жизни:

• а) если (а или (b и с)), то d;
• б) если ( не а и не b), то (с или d);
• в) (а или b) тогда и только тогда, когда (с и не d).

5.8. Формализуйте следующий вывод: "Если a и b истинны, то c — истинно. Но c — ложно: значит, a или b ложны".
[ Ответ ]

5.9. Формализуйте предостережение, которое одна жительница древних Афин сделала своему сыну, собиравшемуся заняться политической деятельностью: “ Если ты будешь говорить правду, то тебя возненавидят люди. Если ты будешь лгать, то тебя возненавидят боги. Но ты должен говорить правду или лгать. Значит, тебя возненавидят люди или возненавидят боги ”.

Формализуйте также ответ сына: “ Если я буду говорить правду, то боги будут любить меня. Если я буду лгать, то люди будут любить меня. Но я должен говорить правду или лгать. Значит, меня будут любить боги или меня будут любить люди ”.
[ Ответ ]

5.10. Пусть a = “ это утро ясное ”, а b = “ это утро теплое ”. Выразите следующие формулы на обычном языке: [ Ответ ]

5.11. Из двух данных высказываний a и b постройте составное высказывание, которое было бы:

• а) истинно тогда и только тогда, когда оба данных выказывания ложны;
• б) ложно тогда и только тогда, когда оба данных высказывания истинны.

[ Ответ ]

5.12. Из трех данных высказываний a, b, c постройте составное высказывание, которое истинно, когда истинно какое-либо одно из данных высказываний, и только в этом случае.

Ответ: .

5.13. Определите с помощью таблиц истинности, какие из следующих формул являются тождественно истинными или тождественно ложными:

а)	д)
б)	е)
в)	ж)
г)

[ Ответ ]

5.14. Упростите следующие формулы, используя законы склеивания:

• а)
• б)
• в)
• г)
• д)
  Решение:.

[ Ответ ]

5.15. Упростите следующие формулы, используя законы поглощения:

• а)
• б)
• в)
• г)

[ Ответ ]

5.16. Постройте таблицы истинности для логических формул и упростите формулы, используя законы алгебры логики:

• а)
• б)
• в)
• г)
• д)
• е)
• ж)
• з)
• и)
• к)

[ Ответ ]

5.17. Приведите примеры переключательных схем, содержащих хотя бы два переключателя, функция проводимости которых

• а) тождественно равна единице;
• б) тождественно равна нулю.

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

а)		б)
в)		г)

[ Ответ ]

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

• а)
• б)
• в)
• г)
• д)

[ Ответ ]

5.20. Постройте переключательные схемы с заданными функциями проводимости:

5.21. Упростите функции проводимости и постройте переключательные схемы, соответствующие упрощенным функциям:
а)

б)

в)

г)

д)

е)

ж)

з)

и)
[ Ответ ]

5.22. Упростите следующие переключательные схемы:

• а)
• б)
• в)
• г)

[ Ответ ]

5.23. Три девочки — Роза, Маргарита и Анюта представили на конкурс цветоводов корзины выращенных ими роз, маргариток и анютиных глазок. Девочка, вырастившая маргаритки, обратила внимание Розы на то, что ни у одной из девочек имя не совпадает с названием любимых цветов.
Какие цветы вырастила каждая из девочек?
[ Ответ ]

5.24. Виновник ночного дорожно-транспортного происшествия скрылся с места аварии.
Первый из опрошенных свидетелей сказал работникам ГАИ, что это были “Жигули”, первая цифра номера машины — единица.
Второй свидетель сказал, что машина была марки “Москвич”, а номер начинался с семёрки.
Третий свидетель заявил, что машина была иностранная, номер начинался не с единицы.
При дальнейшем расследовании выяснилось, что каждый из свидетелей правильно указал либо только марку машины, либо только первую цифру номера.
Какой марки была машина и с какой цифры начинался номер?
[ Ответ ]

5.25. Пятеро одноклассников: Ирена, Тимур, Камилла, Эльдар и Залим стали победителями олимпиад школьников по физике, математике, информатике, литературе и географии.
Известно, что:

• победитель олимпиады по информатике учит Ирену и Тимура работе на компьютере;
• Камилла и Эльдар тоже заинтересовались информатикой;
• Тимур всегда побаивался физики;
• Камилла, Тимур и победитель олимпиады по литературе занимаются плаванием;
• Тимур и Камилла поздравили победителя олимпиады по математике;
• Ирена cожалеет о том, что у нее остается мало времени на литературу.

Победителем какой олимпиады стал каждый из этих ребят?
[ Ответ ]

5.26. Ирена любит мороженое с фруктами. В кафе был выбор из таких вариантов:

• пломбир с орехами;
• пломбир с бананами;
• пломбир с черникой;
• шоколадное с черникой;
• шоколадное с клубникой.

В четырёх вариантах Ирене не нравились или тип мороженого, или наполнитель, а в одном варианте ей не нравились ни мороженое, ни наполнитель. Она попросила приготовить из имеющихся продуктов порцию по своему вкусу.
Какое же мороженое и с какими фруктами любит Ирена?
[ Ответ ]

5.27. На очередном этапе автогонок “Формула 1” первые четыре места заняли Шумахер, Алези, Хилл и Кулхардт. Опоздавший к месту награждения телерепортёр успел заснять пилотов, занявших второе и третье места, которые поливали друг друга шампанским. В это время Шумахер с четвёртым гонщиком пожимали друг другу руки. Далее в кадр попал мокрый Хилл, поздравляющий пилота, занявшего второе место. Напоследок оператор снял сцену, в которой Шумахер и Кулхардт пытались втащить на пьедестал почёта пилота, занявшего четвёртое место.
Просматривая отснятый материал, режиссёр спортивного выпуска быстро разобрался, кто из пилотов какое место занял. Он знал, что, в соответствии с церемонией награждения победителей гонок, пилоты, занявшие первые три места, поливают друг друга шампанским из огромных бутылок знаменитой фирмы — спонсора соревнований.
Какое же место занял каждый пилот?
[ Ответ ]

5.28. В некотором царстве-государстве повадился Змей Горыныч разбойничать. Послал царь четырёх богатырей погубить Змея, а награду за то обещал великую. Вернулись богатыри с победой и спрашивает их царь: “Так кто же из вас главный победитель, кому достанется царёва дочь и полцарства?”
Засмущались добры молодцы и ответы дали туманные:
Сказал Илья Муромец: “Это все Алеша Попович, царь-батюшка”.
Алеша Попович возразил: “То был Микула Селянинович”.
Микула Селянинович: “Не прав Алеша, не я это”.
Добрыня Никитич: “И не я, батюшка”.
Подвернулась тут баба Яга и говорит царю: “А прав то лишь один из богатырей, видела я всю битву своими глазами”.
Кто же из богатырей победил Змея Горыныча?
[ Ответ ]

5.29. При составлении расписания на пятницу были высказаны пожелания, чтобы информатика была первым или вторым уроком, физика — первым или третьим, история — вторым или третьим.
Можно ли удовлетворить одновременно все высказанные пожелания?
[ Ответ ]

5.30. Обсуждая конструкцию нового трёхмоторного самолёта, трое конструкторов поочередно высказали следующие предположения:
1) при отказе второго двигателя надо приземляться, а при отказе третьего можно продолжать полёт;
2) при отказе первого двигателя лететь можно, или при отказе третьего двигателя лететь нельзя;
3) при отказе третьего двигателя лететь можно, но при отказе хотя бы одного из остальных надо садиться.
Лётные испытания подтвердили правоту каждого из конструкторов. Определите, при отказе какого из двигателей нельзя продолжать полёт.
[ Ответ ]

5.31. В соревнованиях по плаванию участвовали Андрей, Виктор, Саша и Дима. Их друзья высказали предположения о возможных победителях:
1) первым будет Саша, Виктор будет вторым;
2) вторым будет Саша, Дима будет третьим;
3) Андрей будет вторым, Дима будет четвёртым.
По окончании соревнований оказалось, что в каждом из предположений только одно из высказываний истинно, другое ложно.
Какое место на соревнованиях занял каждый из юношей, если все они заняли разные места.
[ Ответ ]

5.32. Для длительной международной экспедиции на околоземной космической станции надо из восьми претендентов отобрать шесть специалистов: по аэронавтике, космонавигации, биомеханике, энергетике, медицине и астрофизике. Условия полёта не позволяют совмещать работы по разным специальностям, хотя некоторые претенденты владеют двумя специальностями. Обязанности аэронавта могут выполнять Геррети и Нам; космонавигатора — Кларк и Фриш; биомеханика — Фриш и Нам; энергетика — Депардье и Леонов; врача — Депардье и Хорхес; астрофизика — Волков и Леонов.
По особенностям психологической совместимости врачи рекомендуют совместные полеты Фриша и Кларка, а также Леонова с Хорхесом и Депардье. Напротив, нежелательно, чтобы Депардье оказался в одной экспедиции с Намом, а Волков — с Кларком.
Кого следует включить в состав экспедиции?
[ Ответ ]

Контрольные вопросы

Приложения алгебры логики в технике (релейно-контактные схемы).

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

Эти устройства (их в общем случае называют пере­ключательными схемами) содержат сотни реле, элект­ронных ламп, полупроводников и электромагнитных элементов. Описание и конструирование таких схем в силу их громоздкости весьма затруднительно.

Еще в 1910 году физик П. С. Эренфест указал на воз­можность применения аппарата алгебры логики при исследовании релейно-контактных схем (РКС). Однако его идеи стали реализовываться значительно позже, когда создание общей теории конструирования РКС стало ост­ро необходимым.

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

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

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

Рассмотрим, как устанавливается связь между фор­мулами алгебры логики и переключательными схемами.

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

1) переключателей, которыми могут быть механичес­кие действующие устройства (выключатели, переключа­ющие ключи, кнопочные устройства и т. д.), электромаг­нитные реле, электронные лампы, полупроводниковые элементы и т.п.;

2) соединяющихих проводников;

3)входов в схему ивыходов из нее (клемм, на кото­рые подается электрическое напряжение). Они называ­ются полюсами схемы.

Сопротивления, конденсаторы и т.д. на схемах не изображаются.

Переключательной схемой принимается в расчет только два состояния каждого переключателя, которые называют «замкнутым» и «разомкнутым».

Рассмотрим простейшую схему, содержащую один переключатель Р и имеющую один вход А и один выход В. Переключателю Р поставим в соответствие высказы­вание р, гласящее: «Переключатель Р замкнут». Если ристинно, то импульс, поступающий на полюс А, может быть снят на полюсе В без потери напряжения. Будем в этом случае говорить, что схема проводит ток. Если рложно, то переключатель разомкнут, и схема тока не проводит или на полюсе В снимается минимальное напря­жение при подаче на полюс А максимального напряже­ния.

Если принять во внимание не смысл высказывания, а только его значение, то можно считать, что любому высказыванию может быть поставлена в соответствие переключательная схема 1.

Формулам, включающим основные логические опе­рации, также могут быть поставлены в соответствие пе­реключательные схемы.

Конъюнкция двух высказываний р v q будет представ­лена двухполюсной схемой с последовательным соедине­нием двух переключателей Р и q (схема 2) .

Эта схема пропускает ток тогда и только тогда, когда истинны высказывания р и q одновременно, то есть pqº 1.

Дизъюнкция двух высказываний рvqдвухполюсной схемой с параллельным соединением переключателей Р и Q (схема 3).

Эта схема пропускает ток в случае, если истинно высказывание р или истинно высказывание q, то есть р v q º 1 .

Если высказывание есть отрицание высказывания р, то тождественно истинная формула изображается схемой, которая проводит ток всегда (схема 4), а тождественно ложная формула р&изобразится схемой, которая всегда разомкнута (схема 5).

Из схем 1, 2 и 3 путем последовательного и парал­лельногоих соединения могут быть построены новые двухполюсные переключательные схемы, которые назы­вают П-схемами.

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

1. Формуле соответствует схема 6:

Для схемы 7 соответствующая формула алгебры логики имеет вид:

Упростим эту формулу следующим образом:

Последней формуле соответствует П-схема 8:

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

Приведем пример построения РКС по заданным усло­виям с оценкой числа контактов.

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

Работа нужной РКС описывается функцией Буля трех переменных F(x, у, z), где перемен­ные высказывания х, у, z означают:

х – судья х голосует «за»,

у – судья у голосует «за»,

z – судья z голосует «за».

Таблица истинности функции F(x, у, z) имеет вид:

х

y

z

F(x, у, z)

Функции соответствует формула:

А этой формуле соответствует РКС, изображенная на схеме 7, которая содержит двенадцать переключателей.

Но как было показано, в результате равносильных преобразований формула F(x, у, z) может быть приведена к виду:

которому соответствует РКС, изображенная на схеме 8, содержащей пять переключателей.

Задачи для самостоятельного решения.

1. По таблице истинности найти формулы, определяющие функции F₁, F₂ .

x

y

z

F1

F2

2. Составьте формулу для булевой функции F(x,y,z) = 1, если а) только одна какая-либо переменная равна нулю; б) если большинство переменных равны нулю. Упростите полученные формулы.

3. Составить РКС для формул:

4. Построить схемы, реализующие следующие булевы операции:

5. Построить РКС для функций, если известно, что:

6. Упростить РКС:

7. Проверить равносильность схем:

1. Какое множество называется алгеброй Буля?

2. Какие интерпретации алгебры Буля нам знакомы?

3. Определение функции алгебры логики.

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

5. Что называется релейно-контактной схемой?

6. Какие виды соединений переключателей соответствуют основным логическим операциям?

7. Как нужно представить формулу, чтобы для нее можно было бы составить РКС?

ТЕМА: СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ.

1. Совершенная дизъюнктивная нормальная форма.

2. Совершенная конъюнктивная нормальная форма.

1. Совершенная дизъюнктивная нормальная форма.

Формула , составленная для заданной таблицей истинности функции, по выше приведенному правилу обладает свойствами, которые называются свойствами совершенства. Перечислим их:

1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию.

2. Все логические слагаемые различны.

3. Ни одно слагаемое не содержит одновременно переменную и ее отрицание.

4. Ни одно слагаемое не содержит одну и ту же переменную дважды.

Каждой не тождественно ложной формуле соответствует единственная формула с такими свойствами.

Для одной и той же формулы можно составить множество равносильных ей ДНФ. Но среди них существует единственная ДНФ с перечисленными свойствами совершенства.

ДНФ, для которой выполняются свойства совершенства называется совершенной ДНФ (СДНФ).

Составленная формула по таблице истинности и является СДНФ формулы.

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

Приведем соответствующий алгоритм:

1. Путем равносильных преобразований получить какую – либо ДНФ.

2. Если какая-либо элементарная конъюнкция В не содержит переменную х_i , то вводят ее, используя равносильность . И раскрывают скобки.

3. Если в ДНФ входят две одинаковые конъюнкции В, то лишнюю отбрасывают, используя свойство идемпотентности ВV B º B.

4. Если какая-либо конъюнкция содержит x_i вместе с отрицанием, то В º 0. И В исключают из ДНФ.

5. Если какая-либо конъюнкция содержит переменную x_i дважды, то одну из них отбрасывают, используя свойство x_i x_i º x_i.

1. Составить СДНФ для формулы по таблице истинности и путем равносильных преобразований.

Составим таблицу истинности, которая содержит 4 строки.

Получим какую-либо ДНФА и преобразованиями доведем до совершенства:

2. Аналогичное задание для формулы

Составим таблицу истинности, содержащую 8 строк.

a

b

c

Преобразуем формулу:

3. Путем равносильных преобразований получить СДНФА.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше. 9505 – | 7531 – или читать все.