8)Критерий тождественной истинности и тождественной ложности.
Критерий тождественной истинности формул. Для того, чтобы формула алгебры высказываний была тождественно истинной, необходимо и достаточно, чтобы в равносильной ей КНФ были тождественно истинны все элементарные дизъюнкции.
Критерий тождественной истинности элементарной дизъюнкции. Для того, чтобы элементарная дизъюнкция была тождественно истинна, необходимо и достаточно, чтобы в ней существовала хотя бы для одной переменной пара-переменная и её отрицание.
Критерий тождественной ложности формул. Для того, чтобы формула алгебры высказываний была тождественно ложной, необходимо и достаточно, чтобы в равносильной ей ДНФ все ЭК были тождественно ложны.
Критерий тождественной ложности элементарной конъюнкции. Для того, чтобы ЭК была тождественно ложной, необходимо и достаточно, чтобы в ней существовала хотя бы для одной переменной пара-переменная и её отрицание.
9)Реле и его функция проводимости.
Реле бывают 2 типов: нормально-разомкнутые и нормально-замкнутные. Нормально разомкнутое реле имеет тождественную функцию проводимости, а нормально-замкнутое – отрицание управляющего сигнала. Если управляющий сигнал обозначить х, то
нормально-разомкнутое
реле будет обозначать: -
-
нормально-замкнутое
реле будет обозначать: -
-
Последовательное соединение реле реализует конъюнкцию. Параллельное - дизъюнкцию
10)Схемы и их функции проводимости.
Функцией проводимости схемы называется способность или не проводить ток через схему соединения контактных групп реле в зависимости от комбинации управляющих сигналов, поданной на обмотки всех реле образующих схему.
11)Машина голосования.
1)Построить таблицу за и против. 2)Выписать по таблице СДНФ. 3)Упростить СДНФ. 4)Нарисовать схему получения формулы.
12)Одноразрядный и многоразрядный двоичный сумматор.
13)Алгоритмы минимизации булевых функций.
Число элементов элементарной конъюнкции назовем ее длиной.
Дизъюнктивная форма называется минимальной если она содержит наименьшее число букв из всех возможных дизъюнктивных форм представляющих данную функцию.
Свойства:
xy\/x
x;
xy\/x
x
(склеивание); xy\/
x
xy\/
x
\/x(полусклеивание)
Алгоритм QWAIN
Пусть функция задана в виде СДНФ считаем что длина конъюнкции = n
Проводим все возможные полусклеивания для элементарных конъюнкций длины n
Проводим все возможные поглащения конъюнкций длины n полученные в результате 1 пункта конъюнкциями длины n-1
Повторяем 1,2 пункты с заменой n-1, n-2 т.д. до естественного обрыва процесса
Дизъюнктивная форма полученная при использовании алгоритма Qwain’а называется сокращенной.
Построение минимизирующей таблицы.
Отметим те случаи, когда короткая конъюнкция является частью длинной.
Очевидно, что короткая конъюнкция равна 1 в таблице истинности на той же строчке.
Выберем из элементарных конъюнкций сокращенные формы, подмножества конъюнкций таким образом, чтобы в каждом столбце было хоть по одной звездочке.
14)Логическое следствие и метод резолюции.
Правило резолюции: Из дизъюнктов ˥P (t1, ..., tn) \/ F и P (s1, ..., sn) \/ G выводИм дизъюнкт
(F) \/
(G) ,
где
наиболее общий
унификатор множества
{P (t1, ..., tn), P
(s1, ..., sn)}.
Дизъюнкт
(F) \/
(G) называется
бинарной
резольвентой,
а литералы ˥ P
(t1, ..., tn) и P
(s1, ..., sn) отрезаемыми
литералами.
Системы автоматического доказательства используют метод резолюций, впервые описанный Дж. Робинсоном в 1965 году. Метод предусматривает использование следующей последовательности доказательства:
1. Сначала к доказываемой формуле применяется операция отрицания.
2. Затем предпринимается попытка доказать, что формула, полученная в результате отрицания, противоречива.
Если полученная в результате отрицания формула действительно является противоречивой, то исходная формула должна представлять собой тавто-логию (то есть должна быть истинной при любой интерпретации). Процесс, направленный на обнаружение противоречия, состоит из после-довательного применения правила резолюции к дизъюнктам. Метод резолюций – это метод доказательства того, что формула G являет-ся логическим следствием формул F1, F2, ..., Fk.
Задача о логическом следствии сводится к задаче о выполнимости: Формула G есть логическое следствие формул F1, F2, ..., Fk тогда и только тогда, когда множество формул
{F1, F2, ..., Fk, ˥ G} невыполнимо.
Особенности метода резолюций:
1. Метод устанавливает невыполнимость.
2. Метод оперирует не с произвольными формулами, а с дизъюнктами.
Метод резолюций является обобщением метода доказательства от про-тивного. Вместо того чтобы пытаться вывести некоторую формулу-гипотезу из имеющегося непротиворечивого множества аксиом, добавля-ется отрицание формулы к множеству аксиом и делается попытка вывести из полученного множества противоречие. Если удаѐтся это сделать, то приходят к выводу (пользуясь законом исключенного третьего), что ис-ходная формула выводИма из множества аксиом. Процесс применения правила резолюции продолжается до тех пор, пока не получится пустой дизъюнкт. Возможны, вообще говоря, три случая:
1. Этот процесс никогда не завершается.
2. Среди текущего множества дизъюнктов не окажется таких, к кото-рым можно применить правило резолюции. Это означает, что мно-жество дизъюнктов выполнимо, и значит исходная формула не вы-водИма.
3. На очередном шаге получена пустая резольвента. Это означает, что множество дизъюнктов невыполнимо и, следовательно, начальная формула выводИма.
Имеет место теорема о том, что процесс обязательно завершится за конеч-ное число шагов, если множество дизъюнктов было невыполнимым.