Математическая логика и теория алгоритмов: Методические указания к практическим занятиям, страница 4

2)  различны все члены каждой дизъюнкции;

3)  ни одна дизъюнкция  не содержит переменную вместе с её отрицанием;

4)  каждая дизъюнкция содержит все переменные, входящие в исходную формулу.

Примеры  решения  задач

1. Дана формула   . Найти её СДНФ.

Решение.  Имеем  , здесь опущен для удобства записи  знак конъюнкции.

здесь использовано соотношение 

Так как второй член      не содержит переменной  , добавим сомножитель     Получим  

здесь убрали один из  повторяющихся  членов . Итак,  СДНФ формулы     Заметим,  что 

т. е. исходная форма допускает упрощение: переменную    можно без ущерба опустить.

2. Дана формула     Найти её  СКНФ.

Решение. Имеем 

здесь мы воспользовались дистрибутивным законом дизъюнкции относительно  конъюнкции (выражения     относительно  ), т. е.  «первую скобку» не изменили, а  «вторую скобку» записали как произведение трёх  «новых скобок».

Далее имеем  

, т. е. получим искомую  СКНФ  исходной формулы.

Упражнения

1.  Привести к  СКНФ следующие формулы:

а)       б)       в)  

2.   Привести к  СКНФ следующие формулы:

а)                      б)            в)  

Задания на самостоятельную  работу

1.  Привести к  СКНФ следующие формулы:

а)   б)    в) 

2. Привести к  СКНФ следующие формулы:

а)            б)              в) 

Занятие 3. Конструирование и упрощение контактных схем

      Определение 7. Релейно-контактной  (просто контактной)  схемой  называется устройство, состоящее из проводников и двухпозиционных контактов, которые соединяют источник тока с потребителем.

Если реле срабатывает, то соответствующая ему переменная     принимает значение 1 (не срабатывает, тогда   ). Контакты бывают замыкающие и размыкающие и обозначаются  на схеме соответственно  буквами       и     Всей схеме ставится в соответствие булева функция – функция проводимости, которая равна 1, если схема проводит ток (0, в противном случае).

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

Примеры. 

1)  Схемы         A                                                              B

a)                                                                           

б)          A                                                                B

                                  

в)           А                           В

г)             А              В

имеют соответственно следующие функции проводимости: 

2)  Функция проводимости схемы

                                                                     

А                                                                                      В

                    

имеет вид   .

3) Сконструировать релейно-контактную схему с заданной функций  проводимости

Решение. Данной функции проводимости соответствует, например, следующая схема:

                                                                      

A                                                                              B

4) Построить цепь с тремя независимыми контактами, которая проводит ток тогда и только тогда, когда замкнуты ровно два контакта.

Решение. Искомой  схеме соответствует формула    

,  и сама схема имеет вид:

                                                                      

                                                                                         

                                             

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

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

когда контакт, соответствующий переменной    оказывается «лишним».

5)  Упростить схему